Baixe o app para aproveitar ainda mais
Prévia do material em texto
Reinforcement Learning (Aprendizado por Reforço) Karla Figueiredo DEE/PUC-Rio 1 Sumário Introdução – Motivação – Histórico – Conceitos básicos Fundamentos Teóricos – Processos de Decisão de Markov – Propriedade de Markov – Funções de Valor – Aprendizado RL Métodos para a solução do problema de RL – Programação Dinâmica – Monte Carlo – Diferenças Temporais TD Aprendizado on-policy e off-policy – Q-Learning – SARSA Eligibility Traces Estudo de Casos 2 Bibliografia SUTTON, R.S., BARTO, A.G., Reinforcement Learning: An Introduction, 1998. http://www.cs.ualberta.ca/~sutton/book/ebook/the-book.html KAELBLING, L.P.; LITTMAN M. L.; MOORE, W.A. Reinforcement Learning: A Survey, JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH 4, May 1996, p. 237-285. http://www.jair.org/media/301/live-301-1562-jair.pdf RIBEIRO, C.H.C. A Tutorial on Reinforcement Learning Techniques In: International Joint Conference on Neural Networks ed. : INNS Press, 1999. http://student.vub.ac.be/~aackerma/rlearn2.pdf SINGH, S.P.; SUTTON, R.S. Reinforcement learning with replacing eligibility traces, Machine Learning, vol. 22, no. 1, 1996, p. 123-158. SUTTON, R.S. Temporal Credit Assignment in Reinforcement Learning, Ph.D. thesis, University Massachusetts, Amherst, MA., 1984. BERTSEKAS, D.P. Dynamic Programming: Deterministic and Stochastic Models. Prentice Hall, Englewood Cliffs, NJ, 1987 BELLMAN, R.E. Dynamic Programming, Princeton, NJ, Princeton University Press, 1957. 3 • BARTO, A.G. Reinforcement Learning and Adaptive Critic Methods, HANDBOOK OF INTELLIGENT CONTROL: NEURAL, FUZZY, AND ADAPTIVE APPROACHES, NY, White, D.A.; Sofge, D.A. (eds), Van Nostrand, Reinhold, 1992. p.469-491. • Boyan, J.A.; Moore, A.W. Generalization in reinforcement learning: Safely approximating the value function, G. Tesauro, D. S. Touretzky, and T. K. Leen, editors, ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 7, Cambridge, MA, The MIT Press, 1995. • BAIRD, L. Residual algorithms: Reinforcement learning with function approximation, Armand Prieditis and Stuart Russell, editors, Proceedings of the Twelfth International Conference on Machine Learning, San Francisco, CA, 1995, Morgan Kaufmann., p 30- 37. Bibliografia 4 Reinforcement Learning Conceitos Básicos 5 Motivação Exemplo: Criança adquirindo coordenação motora Robô interagindo com um ambiente para atingir objetivo(s) 6 • Como se aprende a escolher ações apenas interagindo com o ambiente? Muitas vezes é impraticável o uso de aprendizagem supervisionada • Como obter exemplos do comportamento correto e representativo para qualquer situação ? • E se o agente for atuar em um ambiente desconhecido? Teste de Turing: Alan Turing (1950) propôs um teste operacional como definição de Inteligência Artificial Motivação 7 “um agente artificial é dito inteligente se obtém desempenho equivalente ao humano em todas as tarefas cognitivas, de forma a enganar um interrogador” 8 Para Passar no Teste de Turing- “Habilidades” necessárias: Motivação 8 – processamento de linguagem natural:- comunicação eficaz na língua falada; – representação do conhecimento: armazenar informação suprida antes e durante a interrogação; – raciocínio automatizado: usar a informação armazenada para responder questões e chegar a conclusões; – aprendizagem de máquina: se adaptar a novas circunstâncias, bem como detectar e extrapolar padrões; 9 ● Busca por métodos automáticos, capazes de operar sistemas complexos; ● Convergência para solução ótima global; ● Variedade de aplicações em diversos domínios; 9 Motivação Histórico Reinforcement Learning Moderno Psicologia Controle Bellman, 1950s Thorndike, 1910s Lei do Efeito seleção e associação 10 Histórico Lei do efeito (Thorndike, 1910s) • todo e qualquer ato que produz satisfação associa-se a esta situação que, quando ela se reproduz, a probabilidade de repetição do ato é maior do que antes; 11 • a punição e o desprazer não se comparam em absoluto ao efeito positivo da recompensa a uma determinada resposta; • o efeito de prazer é, portanto, o que fixa o acerto (resposta) acidental; • em termos pedagógicos, o agradável é o sucesso do ensaio realizado pelo sujeito e o desagradável é o fracasso decorrente de obstáculos; 12 Sob idênticas condições: • a associação exercitada com maior freqüência será a mais utilizada pelo sujeito; 12 Histórico Lei do exercício (Thorndike, 1910s) • a associação exercitada com menor freqüência será a menos utilizada pelo sujeito; • a associação exercitada mais recentemente será mais forte no conjunto de repertório de respostas do sujeito; Conceitos Básicos Reinforcement Learning: Aprender por meio de interações com o ambiente – Uma criança não tem um professor, mas possui habilidades cognitivas; – Através das interações, a criança descobre as relações de causa e efeito; – Aprender por meio de interações é uma idéia fundamental de quase todas as teorias de aprendizagem e inteligência 13 O que é aprendizagem por reforço? 14 Uma classe de problemas de aprendizagem para a qual existe uma grande diversidade de técnicas Aprendizagem: – da utilidade dos estados do ambiente com respeito a esse(s) objetivo(s) – ou de uma política de ação maximizando o grau de satisfação desse(s) objetivo(s) – indiretamente via recepção de reforço (ou dica) positivo ou negativo quando se encontra em alguns estados – ou como resultado da execução de uma ação ou uma serie de ações Conceitos Básicos Reinforcement Learning Supervised Learning Aprendizado a partir da interação “learner – environment” Baseado em “tentativa e erro” Existe processo de busca (exploration) no espaço Orientado a objetivo Aprendizado a partir de padrões entrada - saída. Baseado em minimizar um erro. Busca limitada ao valores dos padrões padrões entrada-saída Orientado a aproximação de função 15 Conceitos Básicos • O agente recebe do ambiente um valor de resposta (recompensa). • Esta recompensa avalia o desempenho do agente durante o processo de aprendizado. st+1 Ambiente Estado st S Reforço rt rt+1 ação at A(st) Agente Reinforcement Learning 16 Algumas aplicações [Tesauro, 1995] Modelagem do jogo de gamão como um problema de aprendizagem por reforço: – Vitória: +100 – Derrota: – 100 – Zero para os demais estados do jogo (delayed reward) – Após 1 milhão de partidas contra ele mesmo, joga tão bem quanto o melhor jogador humano 17 Algumas aplicações Time Brainstormers da Robocup (entre os 3 melhores nos 3 últimos anos) – Objetivo: Time cujo conhecimento é obtido 100% por técnicas de aprendizagem por reforço – RL em situações específicas 2 atacantes contra 2 defensores habilidades básicas Inúmeras aplicações em problemas de otimização, de controle, jogos e outros... 18 Reinforcement Learning Model-Based Model-Free off-policy on-policy Diferença Temporal SARSA Q-learning R-learning Qyna Programação Dinâmica + Monte Carlo AHC (Actor Heuristic Critic ou Actor-Critic Method) Markov 19 Aprendizado por reforçoAgente Percepções (sensores) Estado (modelo do mundo) Ambiente Ação Reforço (+/-) 20 Conceitos Básicos Reinforcement Learning Ao aprendiz não é dito que ação tomar - ele deve aprender quais ações produzem maior ganho por meio de interações; 21 Aprendizagem por reforço consiste em aprender o que fazer— como mapear situações em ações de maneira a maximizar um sinal de ganho; Nas situações mais desafiadores, o ganho não é imediato, mas futuro; Sumário Introdução – Motivação – Histórico – Conceitos básicos Fundamentos Teóricos – Processos de Decisão de Markov – Propriedade de Markov – Funções de Valor – Aprendizado RL Métodos para a solução do problema de RL – Programação Dinâmica – Monte Carlo – Diferenças Temporais TD Aprendizado on-policy e off-policy – Q-Learning – SARSA Eligibility Traces Estudo de Casos 22 Reinforcement Learning Fundamentos Teóricos 23 Propriedade de Markov 00111111 ,,,,,,,,,'Pr asrrasrasrrss tttttttt No caso mais geral, se a resposta do ambiente em t+1, para uma ação em t depende de todo o histórico de ações até o momento atual, a dinâmica do ambiente é definida pela especificação completa da distribuição de probabilidades: 24 25 Propriedade de Markov Quando a probabilidade de transição de um estado s para um estado s’ depende apenas do estado s e da ação a adotada em s, isso significa que o estado corrente fornece informação suficiente para o sistema de aprendizado decidir que ação deve ser tomada. Quando o sistema possui esta característica, diz-se que ele satisfaz a propriedade de Markov (Bellman, 1957). Propriedade de Markov Se a resposta do ambiente em t+1 depende apenas do estado atual, pela propriedade de Markov, o estado atual contém a informação dos estados anteriores. tttt asrrss ,|,'Pr 11 Se o ambiente tem propriedade de Markov, então ele pode prever o próximo estado e o valor esperado para o retorno dado o estado e a ação atual. É possível criar soluções incrementais, facilitando a implementação computacional. 26 Assim, a decisão de que ação tomar não pode depender da seqüência de estados anteriores Exemplo: Um tabuleiro de dama satisfaz esta propriedade Propriedade de Markov 27 Processos de Decisão de Markov – PDM Em RL, o ambiente deve ser modelado como um Processo de Decisão de Markov (Markovian Decision Process MDP) Um MDP : Um conjunto de estados S Um conjunto de ações A(s) Uma função de reforço R(s, s’,a), onde R = S × A → R, Uma função de probabilidade P(s, s’,a), onde P = S × A → P de transição entre estados Se o espaço de estados e ações é finito PDM – 90% dos problemas RL ts 2t s 1ts 3ts ta 1ta 2ta 3ta 1tr 2tr 3tr ... ... 28 Características: • ambiente evolui probabilisticamente baseado num conjunto finito e discreto de estados; • o estado possui conjunto finito de ações, onde a mais adequada deve ser aprendida; • cada ação executada deve ser avaliada; • os estados são observados, ações são executadas e reforços são relacionados; Processos de Decisão de Markov – PDM 29 Exemplos de PDMs Problema Estados Ações Recompensas Agente jogador de damas Configurações do tabuleiro Mover uma determinada peça #capturas – #perdas Agente em jogo de luta Posições/energia dos lutadores, tempo, se está sendo atacado ou não, etc... Mover-se em uma determinada direção, lançar magia, bater, etc... (Sangue tirado – sangue perdido) Agente patrulhador Posição no mapa (atual e passadas) Ir para algum lugar vizinho do mapa Ociosidade (tempo sem visitas) do lugar visitado atualmente 30 Processos de Decisão de Markov – PDM Probabilidades de Transição Valor Esperado do Reforço 31 Exemplo: Robô Reciclador Lixo Obstáculo Domínio robô Exemplo: Robô Reciclador As decisões devem ser tomadas periodicamente ou quando um evento ocorre: Estado: O agente toma decisões com base no nível de energia da bateria – S = {high, low}. Ações: – A(high) = {search, wait} – A(low) = {search, wait, recharge} 32 Tabela de Transições 33 Grafo de Transições 34 -3 35 Para os problemas de Reinforcement Learning é suposto que o ambiente tenha a forma de um Processo de Decisão de Markov, desde que seja satisfeita no ambiente a Propriedade de Markov Obs: Nem todos os algoritmos de RL necessitam de uma modelagem PDM completa do ambiente, mas é necessário ter-se pelo menos a visão do ambiente como um conjunto de estados e ações. Processos de Decisão de Markov – PDM 35 Elementos de um sistema RL Agente Estado Ambiente Política Função de Reforço 36 Elementos RL: Agente e Estado Estado (s): A condição atual do ambiente especificada por um conjunto de variáveis adequadas ao problema – Tipicamente, estados podem agregar muitas informações além dos sinais sensoriais – Formado pelas percepções do agente + modelo do mundo; – Deve prover informação para o agente de quais ações podem ser executadas; 37 A representação deste estado deve ser suficiente para que o agente tome suas decisões (satisfaz a propriedade de Markov) Agente: É o aprendiz que inserido no ambiente, toma ações que mudam o ambiente. 38 Modelo perceptivo: mapeia percepções para representação interna do estado do ambiente – mp: (percepção(t), modelo(estado(ambiente(t-1)))) modelo(estado(ambiente(t))) Elementos RL: Modelo do ambiente Modelo efetivo: mapeia ação a efetuar para representação interna do estado do ambiente resultando dessa ação – me: (ação(t), modelo(estado(ambiente(t)))) modelo(estado(ambiente(t+1))) 39 39 Cada um desses modelos pode ser: – representado em extensão por uma tabela, ou – representado em intenção por algum formalismo de representação do conhecimento como: – operadores de próximo estado, regras, lógica, operadores de planejamento – manualmente codificado, ou – aprendido com aprendizagem supervisionada Elementos RL: Modelo do ambiente Imita o comportamento do ambiente 40 • Modelos do ambiente são usados para planejamento: ― Planejamento é qualquer método de decidir um curso de ação ao considerarmos futuras situações antes de encontrá-las. Elementos RL: Modelo do ambiente Dados um estado e uma ação, o modelo antecipa o próximo estado e o ganho – Estado corrente no instante t: st – Ação a ser tomada: at – Modelo antecipa o próximo estado: – P(st+1=s | st, at) Elementos RL: com x sem modelo prévio do ambiente 41 Com modelo prévio do ambiente Agente possui modelo do ambiente para prever transições de estado do ambiente causada pelas suas ações Em ambiente não determinista, o modelo pode ser apenas estocástico Sem modelo prévio do ambiente Agente ignora a priori: – tanto o valor de cada estado do ambiente com respeito a seus objetivos – quanto as transições de estado do ambiente que suas ações podem causar Elementos RL: sem modelo prévio do ambiente 42 Dois tipos de técnicas: – As que permitem ao agente aprender o valor de açãopara a realização dos seus objetivos sem conhecer o estado do ambiente – As que permitem aprender ambas a função valor e a função de transição de estado 43 Mapeia estados do ambiente ou transição do ambiente de um estado para um outro, indicando a satisfação imediata do agente no estado resultando da transição em relação aos seus objetivos • R: estado(ambiente) real, ou • R: (estado1(ambiente), estado2(ambiente)) real • R: codifica os objetivos do agente de maneira imediata local • R: pode ser determinista ou estocástica 43 Elementos RL: Função de Reforço O uso de um sinal de reforço é uma da características mais importantes de RL; 44 • Em geral não se penaliza um agente por não ter acesso a alguma informação relevante, mas por ter tido conhecimento e depois esquecido. Reforço(r): É um valor escalar, resposta do ambiente dada uma ação executada pelo agente; é a qualidade imediata da ação tomada para o estado atual. Elementos RL: Função de Reforço O sinal de reforço é a maneira de se comunicar ao agente o que desejamos que ele faça, não como ele deve executar a tarefa; O objetivo do agente é maximizar a seqüência de recompensas recebidas, ou seja, maximizar o Reforço esperado. Ttttt rrrrR 321 Elementos RL: Função de Reforço 45 A função acima faz sentido quando a interação agente- ambiente pode ser quebrada em subseqüências chamadas episódios. 46 46 O fim de um episódio é um estado terminal – Em tarefas episódicas, distingue-se estados não terminais, S, dos estados terminais, S+ . Elementos RL: Função de Reforço Quando a interação agente-ambiente não pode ser quebrada naturalmente em episódios, dizemos que a tarefa é contínua. 47 47 Funções de reforço adequadas a cada um dos 3 tipos de problemas: Elementos RL: Função de Reforço • Reforços no estado final: em geral as recompensas são todas zero, exceto no estado final. • Como o objetivo é maximizar o reforço, o agente aprende que os estados correspondentes a uma recompensa são bons, e os que levaram a uma penalidade devem ser evitados. •Tempo mínimo ao objetivo: nesta classe fazem com que o agente realize ações que produzam o caminho ou trajetória mais curta para um estado objetivo. • Toda transição tem penalidade (−1) exceto aquela que leva ao estado terminal (0). • O Agente aprende a maximizar valores de reforço, escolhendo ações que minimizam o tempo que leva a alcançar o estado final. • Minimizar reforços: nem sempre o agente precisa ou deve tentar maximizar a função de reforço. • Útil quando o reforço é uma função para recursos limitados e o agente deve aprender a conservá-los ao mesmo tempo em que alcança o objetivo. 48 Reforço em todos os estados Agente recebe reforço em todos os estados Pode facilmente atribuir esse reforço a esse estado ou a última ação que executou Simplifica a atualização da estimativa do valor desse estado ou ação Reforço em poucos estados Agente recebe reforço apenas em poucos estados Enfrenta o problema da distribuição desse reforço entre as várias ações que executou desde o último reforço Dificulta atualização da estimativa do valor dos estados ou das ações Elementos RL: Função de Reforço • As ações são escolhas feitas pelos agentes; • As recompensas são a base para avaliação das escolhas; • Os estados são a base para se fazer as escolhas; Elementos de um sistema RL 49 Enquanto a função de reforço indica os movimento promissores imediatos, a função valor indica o ganho total que pode ser acumulado no futuro se iniciarmos no estado em consideração. 50 Elementos RL: Função de Valor A função valor indica o ganho potencial de longo termo de um estado, levando em conta os estados que sucedem o estado em consideração. Função de Valor: Valor esperado condicional da função de reforço para um estado e uma ação, seguindo uma política 0 1)( k tkt k tt ssrEssREsV 0 1 ,,),( k ttkt k ttt aassrEaassREasQ A função de valor representa o reforço esperado a longo prazo. Função de valor do estado para Função de valor da ação para Elementos RL: Função de Valor 51 Reforços futuros mantêm dependências das ações futura As funções valor dependem também da política π que o agente adota Elementos RL: Política de ações () A política Πt (s,a) é a probabilidade da ação at= a se st=s 52 Função que modela o comportamento do agente – Mapeia estados em ações Pode ser vista como um conjunto de regras do tipo sn am – Exemplo: Se estado s = (inimigo próximo, estou perdendo e tempo acabando) então ação a = (usar magia); Se estado s =(outro estado) então ... Objetivo do RL O objetivo do RL é maximizar o reforço total (função valor) obtido a longo prazo Através a busca de uma política que maximize o valor esperado de reforço para cada estado s do conjunto S. )(: sAaSs 53
Compartilhar