INF 1771 Inteligência Artificial  
Aula 24 Aprendizado Por Reforço  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Formas de Aprendizado  
Aprendizado Supervisionado  
Árvores de Decisão.  
K-Nearest Neighbor (KNN).  
Support Vector Machines (SVM).  
Redes Neurais.  
Aprendizado Não-Supervisionado  
Aprendizado Por Reforço  
Aprendizado Supervisionado  
Informação de Treinanento = Entradas + Saídas  
Sistema de Aprendizado  
Supervisionado  
Entrada  
Saída  
Aprendizado Não-Supervisionado  
Sistema de Aprendizado  
Não-Supervisionado  
Entrada  
Saída  
Objetivo: Agrupar objetos semelhantes  
Aprendizado Por Reforço  
Informação de Treinanento = Avaliação(Recompenças, Punições)  
Sistema de Aprendizado  
Por Reforço  
Entrada  
Saída  
Objetivo: Conseguir o máximo de reforço possível  
Introdução  
Como um agente aprende a escolher ações  
apenas interagindo com o ambiente?  
Muitas vezes é impraticável o uso de aprendizado  
supervisionado.  
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 objetivos.  
Exemplo  
As setas indicam a “força”  
entre dois estados.  
S1  
S4  
S2  
S3  
Inicialmente todas as  
setas possuem o mesmo  
valor de força.  
S8  
S7  
Iniciando em S1 como  
chegar em S6?  
S5  
S6  
Exemplo  
Próximo estado é  
escolhido aleatoriamente  
de um dos próximos  
estados possíveis  
S1  
S4  
S2  
S3  
(
ponderado pela força da  
associação).  
A primeira ação só pode  
levar para S2.  
S8  
S7  
S5  
S6  
Exemplo  
Supondo que a próxima  
escolha leve a S3.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
Em S3, as possíveis  
escolhas são S2, S4, ou  
S7.  
S1  
S4  
S2  
S3  
Vamos supor que S7 é  
escolhido aleatoriamente.  
S8  
S7  
S5  
S6  
Exemplo  
Por sorteio, S3 é o  
próximo escolhido.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
O próximo é S4.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
E então S5 é escolhido  
aleatoriamente.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
E finalmente atingimos o  
objetivo S6.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
Quando o estado objetivo  
é atingida, reforça-se a  
conexão entre ele e o  
estado que levou a ele.  
S1  
S4  
S2  
S3  
Na próxima vez que S5  
for alcançado, parte da  
força de associação será  
passada para S4.  
S8  
S7  
S5  
S6  
Exemplo  
Quando o estado objetivo  
é atingida, reforça-se a  
conexão entre ele e o  
estado que levou a ele.  
S1  
S4  
S2  
S3  
Na próxima vez que S5  
for alcançado, parte da  
força de associação será  
passada para S4.  
S8  
S7  
S5  
S6  
Exemplo  
Iniciando novamente o  
percurso.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
Supondo que após alguns  
movimentos o agente  
chega novamente em S5.  
S1  
S4  
S2  
S3  
S8  
S7  
S5  
S6  
Exemplo  
S5 tem grande chance de  
atingir a meta pela rota  
com mais força.  
S1  
S4  
S2  
S3  
Em aprendizado por  
reforço, essa “força” é  
passada de volta para o  
estado anterior.  
S8  
S7  
Esse processo leva a criar  
um caminho entre o início  
e a meta.  
S5  
S6  
Exemplo  
Após reiniciar o percurso  
varias vezes, o agente  
aprenderia o melhor  
S1  
S4  
S2  
S3  
caminho a ser seguido.  
S8  
S7  
S5  
S6  
Aprendizado Por Reforço  
Um agente em um ambiente.  
A cada instante do 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.  
Aprendizado Por Reforço  
Agente autômato otimizador adaptativo  
Estado Interno (modelo do mundo)  
Percepções  
Reforço (+/-)  
Ação  
Ambiente  
Aprendizado Por Reforço  
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 α(s, a).  
Política de ações π(s):  
π : S A  
Estados e Ações  
Estado: conjunto de características que descrevem 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.  
A decisão de que ação tomar não pode depender  
da sequência de estados anteriores.  
Um tabuleiro de dama satisfaz esta propriedade, mas de xadrez não.  
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 o agente está no estado s e  
executa a ação a.  
Pode ser determinística ou estocástica  
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:  
α(s, a, s’)  
Indica a probabilidade de ir para um estado s’ dado que  
estava em s e executou a ação a.  
Exemplos de Problemas  
Problema  
Estados  
Ações  
Recompensas  
Agente jogador  
de damas.  
Configurações do Mover uma  
+ Capturas  
Perdas  
tabuleiro.  
determinada  
peça.  
Agente em jogo Posição,energia  
Mover-se em  
uma direção,  
+ Tirar energia  
do oponente.  
- Perder energia.  
de luta.  
dos lutadores,  
tempo, estar ou lançar magia,  
estar sendo  
bater, etc...  
atacado, etc...  
Agente  
patrulhador.  
Posição no mapa Ir para algum Ociosidade  
lugar vizinho do (tempo sem  
Mapa visitas) do lugar  
visitado  
(atual e  
passadas),  
ociosidade da  
vizinhança, etc...  
Atualmente.  
Política de Ações (s)  
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) então  
ação a = (usar magia);  
Se estado s =(outro estado) então  
ação a = (outra ação);  
Função Valor dos Estados V(s) (S R)  
Como saber se um determinado estado é  
bom ou ruim?  
A função valor Vπ(s) 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 ele  
seguir uma política de ações π.  
Exemplo: tornar-se diretor é bom pelo que o cargo  
permite e permitirá nas próximas promoções.  
Vπ(s0) = r0 + r1 + r2 + r3 + ...  
Problema: se o tempo for infinito, a função valor do  
estado tende a infinito.  
Função Valor das Ações Q(s, a) : (S, A) → R  
A função valor das ações Qπ(s, a) indica 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) = indica em qual estado o agente está,  
dado que ele estava no estado s e executou a ação  
a.  
O valor da ação é a recompensa da ação mais  
o valor do estado para onde o agente vai  
devido à ação.  
Aprendizado Por Reforço  
O aprendizado por reforço consiste em  
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.  
Aprendendo uma Política Ótima  
Se o ambiente é determinístico α(s, a) = s’ (função  
de transição de estados) é conhecida e r(s, a) (função  
de recompensa) é conhecida, é possível computar  
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 probabilidades.  
Q Learning  
Algoritmo Q Learning  
Para todo estado s e ação a, inicialize a  
tabela Q[s][a] = 0;  
Usufruir valores  
conhecidos ou  
explorar valores  
não computados?  
Para sempre, faça:  
Observe o estado atual s;  
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’])  
Dilema de Explorar ou Usufruir  
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.  
Aplicações  
[
Tesauro, 1995] Modelagem do jogo  
de gamão como um problema de  
aprendizagem por reforço:  
Vitória: +100  
Derrota: 100  
Após 1 milhão de partidas contra ele  
mesmo, joga tão bem quanto o melhor  
jogador humano.  
Aplicações  
TD-Gammon  
7
0%  
self-play  
Tesauro, 1992  
performance  
against  
Neurogammon  
gammontool  
trained with 15,000  
expert-labeled examples  
5
0%  
0
10  
20  
40  
80  
Aplicações  
[Crites and Barto, 1996] Controle de Elevadores  
1
0 andares, 4 cabines  
Estados: estados dos botões;  
posição, direção, e estado  
de movimentação dos  
elevadores; passageiros nos  
elevadores e esperando.  
Ações: parar em, passar,  
próximo andar.  
Recompensas: simplesmente  
-
1 por tempo em que cada  
pessoa ficava esperando.