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
0
0
0
0
G
100
0
0
0
100
0
0
0
recompensas imediatas
90
72
81
81
81
90 90
72
90
100
81
90
0
100
G
100
81
Ação valor
G
Função utilidade
G
100
81
0
seqüência ótima
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 atributos
nã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
U = Utilidade
N = No de vezes alcançadas
+1
e = percepção
e21
N++
e22
N++
-1
U=f
U=f
start
Percepts = e1
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
• transição (probabilísticas) de um estado para outro
• 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
U = Probabilidade de transição
N = No de vezes alcançadas
+1
e = percepção
M = Probabilidade
e21
N++
e22
N++
-1
U = f(M)
U = f(M)
start
Percepts = e1
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
U = Probabilidade de transição
N = No de vezes alcançadas
+1
e = percepção
e21
N++
e22
N++
-1
U = f(i-1)
U = f(i-1)
start
Percepts = e1
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
• transição (probabilísticas) de um estado para outro
• 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
• transição (probabilísticas) de um estado para outro
• 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.
Exploração
• Possui como principal objetivo qual o melhor elementoperformance o agente deve retornar.
Sempre a que levar a uma melhor
utilidade no novo estado.
Pode simplesmente descobrir
uma rota aceitável.
• Características básica
Explorar novos estados sem se
preocupar com a utilidade.
Sempre atrás de novos
conhecimentos sem os colocar
em prática
?
– 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.
Exploração
• Solução encontrada:
– Explorar no início para aprender mais sobre o ambiente
e depois se concentrar no melhor caminho.
Estimativa ótima da utilidade
– U+(i)  R(i) + maxa f(j(MaijU+(j)), N(a,i)).
– f(u,n) = R+ se n < Ne
u caso contrário
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:
Ação do próximo estado
– Q(a,i) = R(i) + j(Mija 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))
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
• transição (probabilísticas) de um estado para outro
• Representação do conhecimento
– política de ação.
– em extensão x em intenção (ex, com atributos ou lógica)
• sub-tarefa de classificação envolvida
– 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
32%
111010101100
111010010111
000110010111
000110101100
111010101100
111010101001
001110101001
001110101100
24%
111010101100
24%
001110101001
20%
111011011100
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