INF 1771 Inteligência Artificial  
Aula 20 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  
Inicialmente todas as setas  
possuem o mesmo valor de  
força.  
S3  
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  
(
associação).  
ponderado pela força da  
S3  
A primeira ação 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  
Vamos supor que S7 é escolhido  
aleatoriamente.  
S3  
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  
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 caminho a ser seguido.  
S1  
S4  
S2  
S3  
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  
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.  
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  
tabuleiro.  
Mover uma  
determinada  
peça.  
+ Capturas  
Perdas  
Agente em jogo  
de luta.  
Posição,energia dos  
lutadores,  
tempo, estar ou estar bater, etc...  
sendo atacado, etc...  
Mover-se em uma  
direção, lançar magia, oponente.  
+ Tirar energia do  
- Perder energia.  
Agente patrulhador.  
Posição no mapa  
atual e passadas),  
ociosidade da  
Ir para algum  
lugar vizinho do  
Mapa  
Ociosidade  
(tempo sem  
visitas) do lugar  
visitado  
(
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.  
Q Learning  
Algoritmo Q Learning  
Para todo estado s e ação a, inicialize a tabela Q[s][a] = 0;  
Usufruir valores  
Para sempre, faça:  
conhecidos ou  
explorar valores não  
Observe o estado atual s;  
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’])  
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.  
Leitura Complementar  
Mitchell, T. Machine Learning, McGrawHill  
Science/Engineering/Math, 1997.  
Duda, R., Hart, P., Stork, D., Pattern Classification,  
John Wiley & Sons, 2000