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