Aprendizagem por Reforço

Aprendizagem por Reforço

Alexandre Luiz G. Damasceno

Sumário• Motivação.

• Reforço.

• Função-utilidade x Ação-valor.

• Aprendizagem por reforço.– Passivo em um ambiente conhecido.

– Passivo em um ambiente desconhecido.

– Exploração.

– Ativo.

– Generalização

– algoritmos genéticos

• Relação da aprendizagem com reforço com outras áreas de IA e estatística

• Conclusões

Motivação

• Ambientes e aplicações pelas quais não são disponíveis: – função explícita da utilidade

• das ações do agentes para seus objetivos

• do estado do ambiente para os mesmos

– feedback detalhado a cada passo sobre utilidade • ex, RoboCup, xadrez sem professor

• feedback limitado a reforços para uma seqüência de ação

• novo problema pelo agente aprendiz: como atribuir quais ações na seqüência são responsáveis pelo reforço (positivo ou negativo)

– transições explícita de estado (as vezes nem probabilisticamente)

Reward (Reforço)

• O reward pode ser calculado de várias maneiras:– Rt + *rt+1 + 2

*rt+2 + ... = i=0 i

*rt+i , onde ri é o reward por chegar ao estado ‘i’ e um valor entre (0 e 1). ‘i’ é contado do final até o início.

hi=0 ri

– limh(1/h* hi=0 ri)

• O reward pode ser dado de várias maneiras– A cada passo.

– Ou só no final.

Função de utilidade vs. Ação-valor

• Função de utilidade: Precisa ter um modelo do ambiente, para saber a qual estado a ação o levará.

• Ação-valor: Não precisa ter o modelo do mundo, mas não pode prevê situações.

Aprendizagem: exemplo

seqüência ótima

G G

G

recompensas imediatas Função utilidade

Ação valor

0

00

0

0

0

0

0

100

100

0

0

G

81

8172

90

81

72

90

81

100

100

81

90

0 90 1000

1009081

Aprendizagem por reforço:características gerais

• Tarefas: controle

• Ambiente pode ser:– inacessível, não episódico

– discreto ou não, ruidoso

– dinâmico?, não determinístico

– grande,

– distinção relacional x atributosnão se aplica

• Por reforço

• Treino antes da ação ou durante a ação

• Incremental

• Iterativo

• Top-down x bottom-up não se aplica

• Guloso

• Local

• Pode aproveitar conhecimento prévio para podar busca da hipótese

• Aproxima qualquer função– de utilidade ou de política de ação

Representação do conhecimento:• função de utilidade dos estados do ambiente• ou função de política de ação no ambiente

Aprendizagem por reforço:variação das situações

• Ambiente: acessível ou não, discreto ou não, finito.

• Recepção do reforço:– em qualquer estado, apenas nos estados finais.

• Aprendizagem:– antes ou durante ação (passivo x ativo).

– com modelo prévio do ambiente. • política de ação

• função de utilidade dos estados

• transição (probabilísticas) de um estado para outro

• Representação do conhecimento– política de ação ou função de utilidade dos estados.

– em extensão x em intenção (ex, com atributos ou lógica).• sub-tarefa de classificação envolvida

Aprendizagem Passiva em um ambiente conhecido

• O ambiente gera estados de transição e o agente os percebe.

Aprendizagem Passiva em um ambiente conhecido

• Algorítmo Geral

function Passive-RL-Agente(e) returns na action

static: U (tabela de utilidades),

N (tabela de freqüências),

M (tabela de transição de probabilidade),

percepts (percepeções)

add e to percepts

increment N[State[e]]

U Update(U, e, percepts, M, N)

if Terminal?[e] then percepts [ ]

return the action Observe

Naïve updating (LMS)

function LMS-Update(U, e, percepts, M, N) returns an updated U

if Terminal?[e] then

reward-to-go 0

for each ei in percepts (starting at end) do

reward-to-go reward-to-go + Reward[ei]

U[State[ei]] Running-Average(U[State[ei]],

reward-to-go, percepts, N[State[ei]])

end

• U(t) = Rt + *rt+1 + 2*rt+2 + ... =

i=0 i*rt+i

– Como em redes neurais

LMS: exemplo

+1

-1

start

Percepts =

N++

U = f

e21

e1

N++ e22

U = f

U = Utilidade

N = No de vezes alcançadas

e = percepção

LMS: características• Ambiente: acessível ou não, discreto ou contínuo, finito

• Recepção do reforço:– apenas nos estados finais

• Aprendizagem:– antes da ação (passivo)

– com modelo prévio do ambiente • função de utilidade dos estados


• Representação do conhecimento– função de utilidade dos estados

– em extensão x em intenção (ex, com atributos ou lógica) • sub-tarefa de classificação envolvida

– Reduz o problema a aprendizagem indutiva.

– Não considera que a utilidade dos estados possam ser dependentes.

ADP passivo

• Programação dinâmica adaptativa (ADP)– U(i) = R(i) + j(Mij U(j)), onde R(i) é o reforço do

estado i e Mij é a probabilidade de passar do estado i para o estado j.

ADP passivo: exemplo

+1

-1

start

Percepts =

N++

U = f(M)

e21

e1

N++ e22

U = f(M)

U = Probabilidade de transição


e = percepção

M = Probabilidade

TD

• Aprendizagem por diferença temporal (TD)– U(i) = U(i) + (R(i) + U(j) - U(i)), onde é a taxa de

aprendizagem.

– Impactos do : Caso ocorra um estado novo sem o ? E com ?

function TD-Update(U, e, percepts, M, N) returns the utility table U

if Terminal?[e] then

U[State[e]] Running-Average(U[State[e]], Reward[e],U[State[e]])

else if percepts contains more than one element then

e’ the penultimate element of percepts

i, j State[e’], State[e]

U[i] U[i] + (N[i])(Reward[e’] + U[j] - U[i])

TD: exemplo

+1

-1

start

Percepts =

N++

U = f(i-1)

e21

e1

N++ e22

U = f(i-1)

U = Probabilidade de transição


e = percepção

TD: características• Ambiente: acessível ou não, discreto ou não, finito

• Recepção do reforço:– em qualquer estado

• Aprendizagem:– antes da ação (passivo)

– com modelo prévio do ambiente • função de utilidade dos estados


• Representação do conhecimento– função de utilidade dos estados

– em extensão x em intenção (ex, com atributos ou lógica)• sub-tarefa de classificação envolvida

– considera que a utilidade dos estados possam ser dependentes.

Aprendizagem Passiva em um ambiente desconhecido

• LMS e TD permanecem inalterados.

• No ADP, é preciso adicionar um passo para atualizar o modelo estimado do ambiente. E assim usar este modelo no processo de aprendizagem como se fosse o ambiente real.

ADP ativo

• Alterações no Passive-RL-Agente:– probabilidade de passar de ‘i’ para ‘j’ dada uma ação

‘a’: Mija.

– U(i) = R(i) + maxa (Mija U(j)).

– O agente deve escolher uma ação a cada passo e precisará de um elemento de performance para tanto.

• Performance-Element(e): retorna uma ação.

– Deve-se preocupar-se com a alteração estimada do ambiente, pois esta depende agora da ação tomada.

• Update-Active-Model recebe uma ação também.

Aprendizagem Ativa em um ambiente desconhecido

function Active-ADP-Agente(e) returns na action

static: U (tabela de utilidades),

N (tabela de frequüências),

R (tabela de rewards),

M (tabela de transição de probabilidade),

percepts (percepeções),

last-action, ação imediatamente executada

add e to percepts

R[State[e]] Reward[e]

M Update-Active-Model(M, percepts, last-action)

U Value-Interation(U, M, R)

if Terminal?[e] then percepts [ ]

last-action Performance-Element(e)

return the last-action

ADP: características• Ambiente: acessível ou não, discreto ou não, finito

• Recepção do reforço:– em qualquer estado.

• Aprendizagem:– antes ou durante. (passivo x ativo)

– com modelo prévio do ambiente. • função de utilidade dos estados


• Representação do conhecimento– função de utilidade dos estados.


– considera que a utilidade dos estados possam ser dependentes.

Exploração• Possui como principal objetivo qual o melhor elemento-

performance o agente deve retornar.

• Características básica– Ganha um reward do estado corrente– Afeta as percepções recebidas, bem como a habilidade do

agente de aprender - e recebe rewards nas seqüências futuras.

Sempre a que levar a uma melhor utilidade no novo estado.

Pode simplesmente descobrir uma rota aceitável.

Explorar novos estados sem se preocupar com a utilidade.

Sempre atrás de novos conhecimentos sem os colocar em prática

?

Exploração

• Solução encontrada:– Explorar no início para aprender mais sobre o ambiente

e depois se concentrar no melhor caminho.

– U+(i) R(i) + maxa f(j(MaijU+(j)), N(a,i)).

– f(u,n) = R+ se n < Ne

u caso contrário

Estimativa ótima da utilidade

Q-learning

• A utilidade está associada com a uma ação em um dado estado (Q-values).– U(i) = maxaQ(a,i)

• É importante para a aprendizagem por reforço pois:– como as regras de condição, não precisa de um modelo

para tomar decisão

– diferente das regras de condição, a função pode ser aprendida diretamente pelo reforço.

Aprendizagem Q

• Regra para manter o equilíbrio da corretude dos Q-values:– Q(a,i) = R(i) + j(Mij

a maxa’Q(a’,j))

– Como no ADP, pode-se usar esta equação como uma de atualização para um processo de atualização que calcula Q-values dado um modelo estimado.

• Já o TD Q-learning, não precisa do modelo:– Q(a,i) Q(a,i) + (R(i) + maxa’Q(a’,j) - Q(a,i))

Ação do próximo estado

Aprendizagem Q

function Q-Learning-Agente(e) returns na action

static: Q (tabela de valores das ações),

N (tabela de frequüências),

a, ação imediatamente já executada

i (estado visitado anteriormente),

r (reward recebido no estado i),

j State[e]

if i is not-null then

N[a,i] N[a,i] + 1

Q[a,i] Q[a,i] + (r + maxa’Q(a’,j) - Q(a,i))

if Terminal?[e] then percepts [ ] else

i j; r Reward[e]

a arg maxa’f(Q[a’,j], N[a’,j])

return a

Q: características• Ambiente: acessível ou não, discreto ou não, finito.

• Recepção do reforço:– em qualquer estado ou apenas nos estados finais.

• Aprendizagem:– durante ação (ativo)

– com modelo prévio do ambiente. • política de ação


• Representação do conhecimento– política de ação.


– considera que a ação dos estados possam ser dependentes.

Aprendizagem Q

• Questões: É melhor aprender um modelo e uma função de utilidade ou apenas uma função de ação-valor sem um modelo?

?

Generalização

– Forma tabular: Para cada tupla (U, M, R, Q) tem-se um valor de saída. Isto significa inviabilidade em ambientes com muitos estados diferentes (mundo real).

– Solução: uma forma de calcular a saída para cada entrada, mas da forma mais compacta que a forma tabular (representação implícita).

– Exemplo: U(i) = w1f1(i) + w2f2(i) + ... + wnfn(i). Onde f são as características do ambiente e w os pesos dado.

– Essa compressão pode levar ao poder de generalização (de estados visitados para os não visitados).

– Isso faz com que estes métodos se chamem input generalization.

Generalização

• Pode-se usar algoritmos genéticos para aproximar os pesos da função dada da função real.

• Pode-se usar redes neurais no caso de ter-se <estado-ação>-valor, onde a ação e o estado seriam o imput da rede e o valor o out-put.

• Pode-se usar aprendizagem de árvore de decisão.

Algoritmos Genéticos• Problemas:

– Qual a função de utilidade?

– Como representar o indivíduo?

– Como selecionar o indivíduo?

– Como ele se reproduz?

– (Condição de parada)

• Funções usados:– função de utilidade: quanto maior o seu retorno melhor

é o indivíduo.

– Função de escolha dos indivíduos.

– Replicação e morte.

– Cross-over e mutação.

Algoritmos Genéticos

Um exemplo:

000110010111

111010101100

001110101001

111011011100

000110010111

111010101100

111010101100

001110101001

32%

24%

24%

20%

000110101100

111010010111

111010101001

001110101100

Relação da aprendizagem com reforço com outras áreas de IA e estatística

• IA em geral• Resolução de problema com busca• Planejamento• Otimização:

– programação dinâmica

– algoritmos genéticos

Conclusões• Usado em várias áreas como:

– jogos

– robótica

• É uma pequena área da IA mais que é bastante estudada e tem grande interseção com áreas fora da IA cujas técnicas podem ser aproveitadas, pelo menos para inspiração conceitual.

• Como todo aprendizado, não deixa de ser uma busca.

• Assemelha-se ao aprendizado de um animal

FIM

Documents

Aprendizagem por Reforço