RL-Introducao_2aula_partea

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