Aprendizagem por Reforço

Hugo Pimentel de Santana

(hps@[Link])
Motivação
Como um agente 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?
 Exemplos:
 Criança adquirindo coordenação motora
 Robô interagindo com um ambiente para atingir objetivo(s)

2
O que é aprendizagem por
reforço (tradicional)?
Problema de aprendizagem (não é uma
técnica)
 Um agente, em um ambiente
 A cada instante de tempo t:
 o agente está em um estado s
 executa uma ação a
 vai para um estado s’
 recebe uma recompensa r
 Problema da aprendizagem por reforço:
 Como escolher uma política de ações que maximize o
total de recompensas recebidas pelo agente

3
O problema da aprendizagem
por reforço
Agente autômato otimizador adaptativo

Estado Interno (modelo do mundo)

Percepções Reforço (+/-) Ação

Ambiente

4
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

5
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...

6
No CIn: Patrulha multi-agente
Dado um mapa, um grupo
de agentes deve visitar
continuamente locais
específicos deste mapa de
maneira a minimizar o
tempo que os nós ficam sem
serem visitados Performance comparisson 5 agents

Recompensa: ociosidade dos 100

nós visitados
90
80

Average idleness
70

Coordenação emergente
60
50
40

(mesmo sem comunicação 30

20

explícita)
10
0
Conscientious Heuristic Conscientious LearnerAgent
cognitive agent Coordinator reactive agent

7
Conceitos Básicos
Processo de decisão de Markov (MDP)
 Conjunto de estados S
 Conjunto de ações A
 Uma função de recompensa r(s,a)
 Uma função de transição de estados (pode ser
estocástica) (s,a)
Política de ações (s) :
 : S  A

8
Estados e Ações
Estado: conjunto de características indicando como
está o ambiente
 Formado pelas percepções do agente + modelo do mundo
 Deve prover informação para o agente de quais ações
podem ser executadas
A representação deste estado deve ser suficiente
para que o agente tome suas decisões (satisfaz a
propriedade de Markov)
 A decisão de que ação tomar não pode depender da
seqüência de estados anteriores
 Ex: Um tabuleiro de dama satisfaz esta propriedade, mas de
xadrez não
 O ambiente não precisa ser episódico
9
A função de recompensa
Feedback do ambiente sobre o
comportamento do agente
Indicada por r:(S  A) R
 r(s,a) indica a recompensa recebida
quando se está no estado s e se executa a
ação a
 Pode ser determinística ou estocástica

10
Função de transição de estados
: (S  A)  S
(s,a) indica em qual estado o agente está,
dado que:
 Estava no estado s
 executou a ação a
Ambientes não-determinísticos:
 escrita como (s,a,s’)
 indica a probabilidade de ir para um estado s’
dado que estava em s e executou a

11
Exemplos de MDPs
Problema Estados Ações Recompensas

Agente jogador Configurações do Mover uma #capturas –

de damas tabuleiro determinada #perdas
peça

Agente em jogo Posições/energia Mover-se em (Sangue tirado –

de luta dos lutadores, uma sangue perdido)
tempo, se está determinada
sendo atacado direção, lançar
ou não, etc... magia, dar
porrada, etc...
Agente Posição no mapa Ir para algum Ociosidade
patrulhador (atual e lugar vizinho do (tempo sem
passadas), mapa visitas) do lugar
ociosidade da visitado
vizinhança, etc... atualmente

12
Política de ações ()
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
...

13
Função valor dos estados V(s)
(S  R)
Como saber se um determinado estado é
bom ou ruim?
 A função valor expressa esta noção, em termos
das recompensas e da política de ações
 Representa a recompensa a receber em um
estado s, mais as recompensas futuras se seguir
uma política de ações 
 ex. tornar-se diretor, vale pelo que o cargo permite e
permitirá nas próximas promoções (não interessa de
onde veio - chefe de seção)
 V(s0) = r0 + r1 + r2 + r3 + ...
 Problema: se o tempo for infinito, a função valor do
estado tende a infinito 14
Função Valor dos estados
 Para garantir convergência e diferenciar
recompensas distantes do estado atual, usa-se um
fator de desconto
01
 V(st) = rt +  rt+1 + 2 rt+2 + 3 rt+3 ...
 V(st) = rt + V(s’), onde:
 rt = r(st, (st))
 s’ = (st, (st))
 Ex. Se  = 90%, então:
 V(st) = rt + 0.9 rt+1 + 0.81 rt+2 + 0.729 rt+3 ...

15
Função valor das ações
Q(s,a) : (S  A)  R

Analogamente, ela diz a soma das

recompensas a obter dado que:
 o agente está no estado s
 executou uma ação a
 a partir daí, seguiu uma política de ações 
Q(s,a) = r(s,a) + V(s’), onde:
 s’ = (s,a)
 o valor da ação é a recompensa da ação mais o
valor do estado para onde o agente vai devido
à ação 16
Aprendizagem por reforço
Tarefa de aprendizagem por reforço:
 Aprender uma política de ações * ótima,
que maximiza a função V (V*) ou a
função Q (Q*)
 * = argmax[V(s)]
Em outras palavras, de que maneira o
agente deve agir para maximizar as
suas recompensas futuras

17
Exemplo: Labirinto (c/=0.9)
Função recompensa Função V*

Função Q* Uma política de ações ótima

18
Aprendendo uma política ótima
Se o ambiente é determinístico ((s,a) = s’ é
conhecida) e r(s,a) é conhecida, a programação
dinâmica computa uma política ótima :
 V*(s) =maxa[ r(s,a) + V*((s,a) ) ]
 *(s) = argmaxa[r(s,a) + V*((s,a) )]
 Tempo polinomial
 Problema: se não temos conhecimento prévio das
recompensas e transição de estados
Se o ambiente é não-determinístico mas a função de
probabilidade de transição de estados for conhecida,
também é possível computar *
 problema: É difícil estimar estas probabilidades

19
Q Learning
É possível determinar * se eu conheço Q*
 não precisando conhecer  (função de transição
de estados) nem r
 *(s) = argmaxa[Q(s,a)]
 não é função de  nem de r

Então, vamos aprender a função Q ótima

(valor das ações) sem considerar V
 Q(st,at) = r(st,at) +  V*((st,at) )
= r(st,at) +  maxa’ [Q(st+1,a’)]
 o valor do próximo estado é o melhor Q nele
 Como atualizar Q ?
20
Q-Learning
Atualiza-se Q(st) após observar o estado st+1 e
recompensa recebida

Q(s1,aright) = r + maxa’Q(s2,a’)
= 0 + 0.9 max{63,81,100}
= 90
21
Algoritmo Q-Learning para
mundos determinísticos
Para todo estado s e ação a, inicialize a
tabela Q[s][a] = 0; Usufruir valores
conhecidos ou
Para sempre, faça: explorar valores
 Observe o estado atual s; não
computados?
 Escolha uma ação a e execute;
 Observe o próximo estado s’ e recompensa r
 Atualize a tabela Q:
 Q[s][a] = r +  maxa’ (Q[s’][a’])

22
Dilema de explorar ou usufruir
(exploration x exploitation)
Usufruir
 Escolher a ação que atualmente está com maior
valor Q(s,a)
Explorar
 Escolher uma ação randômica, para que seu valor
Q(s,a) seja atualizado
Dilema
 Dado que eu aprendi que Q(s,a) vale 100, vale a
pena tentar executar a ação a’ se Q(s,a’) por
enquanto vale 20 ?
 Depende do ambiente, da quantidade de ações já
tomadas e da quantidade de ações restantes
23
Métodos para balancear
exploration e exploitation
E-Greedy
 A cada iteração, escolhe
uma ação
exploratória(randômica)
com probabilidade E
 Ex. 10-armed bandit (caça
níqueis)
 10 caça níqueis com
distribuições de prob.
diferentes (desconhecidas)
 e = 10% acha ações
ótimas mais cedo, mas erra
9% do tempo
 e = 1% obterá melhor
performance no futuro!
 e = 0 % fica preso em uma
ação não ótima

24
Métodos para balancear
exploration e exploitation

Escolha de ações softmax

 A probabilidade de uma ação ser escolhida
varia de acordo com o valor de Q(s,a)
 Pode-se usar o conceito de temperatura de
simulated annealing:
 T = infinito, ação totalmente exploratória
 T = zero, ação totalmente gulosa

25
RL em ambiente não
determinístico
Recompensas serão não determinísticas
 V(s) = E[rt + rt+1 + rt+2 + ...]
 Problema:
 Suponha que a sequência de recompensas recebidas em
um determinado estado foi:
 100, 98, 101, 97, 90, 103, 10
 O valor da função Q vai refletir apenas o último valor !
Solução: usar uma taxa de aprendizagem 
 Qn(s,a) = (1-)Qn-1(s,a) + [r + maxa’Qn-1(s’,a’)]
 A atualização de Q não “esquece” dos valores anteriores
 Se  = 1/[1+#visitas(s,a)], Q converge para Q*
em tempo polinomial
26
Semi-MDP
Como o agente pode levar em conta o
tempo de suas ações?
 Ex. no jogo de luta: É melhor dar vários
socos fracos ou um soco forte?
 Soco forte provavelmente traria maior
recompensa
 Demoraria mais tempo para ser executado
 No problema da patrulha: como levar em
conta o a distância entre os nós?

27
Semi-MDP
O formalismo SMDP engloba este conceito
Prova-se que a atualização de Q passa a ser
dada por:
 Q[s][a] = r + t maxa’ (Q[s´][a’])
 Onde t pode ser:
 número de unidades de tempo que o agente executou a
ação (caso discreto)
 alguma função contínua do tempo
 Desta maneira, as recompensas futuras passam a
valer menos se o agente passar muito tempo
executando uma ação

28
Complexidade de Q-Learning
Escolher uma ação é barato no tempo
 No entanto, o tempo de treinamento
cresce com #S
Em espaço: O(#S x #A)
 Problemas
 o número de estados possíveis cresce
exponencialmente com a quantidade de
características representadas
 Como tratar estados contínuos?

29
Linhas de pesquisa em RL
atualmente
Substituir a tabela Q por redes neurais
 Permite generalização
 Tratar estados contínuos
Tratar casos em que o estado é
parcialmente observável
 POMDP
Aprendizagem por reforço hierárquica
Aprendizagem por reforço multi-agente

30
Aprendizagem por reforço
multi-agente - Cooperação
Abordagens usando RL tradicional:
 White box agent
 Representação de estado global
 Encontra a ação conjunta (a1, a2, ..., an) que maximiza
uma função de reforço global (única)
 Problemas
 Complexidade exponencial no número de agentes
 Como aprender as ações de maneira distribuída ?
 Black box agent
 O reforço é individual, mas é alguma função do bem
estar global
 O agente não toma conhecimento dos outros agentes
 Outros agentes passam a ser ruído no ambiente
31
Aprendizagem por reforço
multi-agente - Cooperação
Black box agent
 Problemas
 Atribuição de crédito
 Como atribuir valor a ações individuais de um agente, em
termos do bem estar global?
 Ex: Que reforço dar pra uma ação do jogador do meio de
campo em um jogo de futebol?

Gray box agent:

 O agente toma suas decisões individualmente
 Os agentes comunicam suas intenções

32
Aprendizagem por reforço
multi-agente - Competição
Min-Max Reinforcement Learning
 RL Tradicional:
 Executa ações com maior recompensa
esperada
 Min-Max RL
 Modela as ações do adversário
 Executa ações que, dado que um oponente
utiliza uma política ótima, minimiza minhas
perdas

33
Referências
Lecture slides do livro Machine
Learning, do Tom Mitchell
 [Link]
[Link]
Livro “Reinforcement Learning: An
introduction”, de Sutton & Barto
disponível online
 [Link]
[Link]

34