Baixe o app para aproveitar ainda mais
Prévia do material em texto
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 1 Existem três classes principais de métodos: • Programação Dinâmica • Métodos de Monte Carlo • Métodos de Diferenças Temporais Reinforcement Learning Problema da aprendizagem por reforço: Como escolher uma política de ações que maximize o total de recompensas recebidas pelo agente Programação Dinâmica - PD Matematicamente fundamentados aassssP tttass ,'Pr 1' ,,',E 11' aassssrR ttttass Necessitam de um modelo completo e preciso do ambiente O termo PD (Programação Dinâmica) se refere a uma coleção de algoritmos que podem ser usados para calcular políticas ótimas, dado um modelo perfeito do ambiente em MDP (Markov Decision Process) onde Ras,s′ é o valor esperado do retorno rt+1, sempre que o estado st no instante t passe a ser o estado s′ no instante t + 1 quando o agente implementa a ação at igual a. Pas,s′ representa a probabilidade do estado st+1ser s′, sempre que o estado st for igual a s e a ação at for igual a. Probabilidade de transição Programação Dinâmica - PD Ambiente é modelado por um PDM; Modelagem perfeita exige custo computacional, mas fornece fundamento teórico para outros métodos. A dinâmica do sistema é dada por conjuntos de probabilidade de transição de s para s’ e de reforços imediatos esperados (modelagem PDM) – S, conjunto de estados – A(s), ações possíveis no estado s – Ps,s’a = Pr{st+1 = s’ | st = s, at = a} – Rs,s’a = E{rt+1 | st+1 = s’, st = s, at = a} Programação Dinâmica - PD Retornos para tarefas episódicas Retornos para tarefas contínuas 0 13 2 21 ... k kt k tttt rrrrR Ttttt rrrrR ...321 Expressão genérica para tarefas contínuas ou episódicas ( ) 1ou T Para qualquer e s a função de valor de s em é avaliada para os possíveis s´: Equação de Bellman: Relação valor do estado e dos valores dos estados sucessivos 6 PD: Função de Valor A eq. Bellman realiza a média sobre todas as possibilidades, onde o peso são as probabilidades de ocorrência. Programação Dinâmica - PD ' '' 111 )]'([),( |)()( s k a ss a ss a ttktk sVRPas sssVrEsV Atualização das Funções Valor Funções de valor são calculadas a partir de um sistema de equações lineares que apresenta com alto custo computacional. Como solução: o cálculo iterativo para uma seqüência de Vk’s usando a equação de Bellman: Valor deste estado é o valor esperado para o próximo estado + reforço esperado diagramas: formam a base das operações de atualização 8 PD: Função de Valor Política de Ações Avaliar uma política π consiste em determinar o valor V (s) induzido por π para todo o estado s. Resolvendo as equações Bellman de consistência. Avaliação de uma política: Robô Reciclador 10 V π (l) = 41, 20 V π (h) = 48, 46 Solucionar RL encontrar a política ótima. A é melhor ´ se o retorno esperado é maior ou igual para todos os estados. Se >= ´, V (s) >= V ´ (s) para todo s S Se existe (e sempre existe) uma que é melhor ou igual a todas as outras políticas, então é ótima 13 Melhora na política A partir V, a nova política vem a ser ' '' 11 )]'([maxarg ,|)(maxarg)(' s a ss a ss a tttt a sVRP aasssVrEs Programação Dinâmica - PD Organiza e estrutura a busca de boas políticas a partir das funções valor-estado e valor-ação. Políticas ótimas são obtidas sempre que funções valor ótimas são obtidas Programação Dinâmica - PD Funções Valor Ótimas Para encontrar a função valor ótima: aassasQrE asQasQ sssVrE sVsV tttt sa ttt a sa ,|)',(max ),(max),( |)(max )(max)( 1 * 1 * )( * 1 * 1 * )( * A A Estas são as equações de otimalidade de Bellman 15 Funções Valor Ótimas Estas são as duas formas para a Equação de otimalidade de Bellman 16 Funcões Valor ótimas aassasQrE asQasQ sssVrE sVsV ttt a t sa ttt a sa ,|)',(max ),(max),( |)(max )(max)( 1 * ' 1 * )( * 11 * )( * A A Das equações de Bellman, a forma de enxergar o ótimo é: 17 Funções Valor ótimas: Políticas Ótimas Existem funções de valor ótimas (que maximizam o retorno ao longo prazo): Que representam políticas ótimas: )(max)(* sVsV ),(max),(* asQasQ ),(maxarg)(* * asQs Desta forma, * representa a política mais ambiciosa respeito de Q* 18 Funções Valor ótimas: Políticas Ótimas Funções Valor ótimas: Políticas Ótimas Funções Valor ótimas: Políticas Ótimas Observe: os valores V∗(l) e V∗ (h) são bem superiores aos obtidos com a política equiprovável π, V (l) = 41, 20 e V (h) = 48, 46. A política de controle ótima π∗ obtida a partir de Q ∗ é: π(h) = s e π(l) = r o robô deve vasculhar o ambiente enquanto a bateria estiver em nível alto de energia, mas recarregá-la sempre que o nível de energia se tornar baixo. Funções Valor ótimas: Políticas Ótimas Funções Valor ótimas: Políticas Ótimas Três Suposições Verdadeiras: • A dinâmica do ambiente é conhecida; • Recurso computacional suficiente; • Propriedades de Markov. 23 Exemplo: Labirinto (c/=0.9) Função recompensa Função V* Função Q* Uma política de ações ótima Interação entre a Política e a Função Valor (GPI – Generalized Policy Iteration) QV , * **,QV Atualização da política Fazendo com que a política seja cada vez mais ambiciosa Avaliação da política Atualiza funções valor Política Função Valor Programação Dinâmica (Bellman, 1957) possui um bom desenvolvimento matemático, mas exige uma modelagem muito precisa do ambiente como um Processo de Decisão de Markov. Reinforcement Learning: Vantagens e Desvantagens dos Métodos Plano de Aulas: Reinforcement Learning – Conceitos básicos – Elementos de um sistema RL/Características Fundamentos Teóricos – Processos de Decisão de Markov – Propriedade de Markov – Funções de Valor – Aprendizado RL Métodos básicos 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 AHC – Eligibility Traces Estudo de Casos
Compartilhar