RL-Introducao_1aula

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 2t
s
1ts 3ts
ta 1ta 2ta 3ta
1tr 2tr 3tr
... ... 
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