Aprendizado por Reforço: Uma Aplicação do Aprendizado Q

Rafael Souza Nader

Ciência da Computação – DCC – IM

Agenda

• Introdução: Aprendizado de Máquina• Aprendizado Por Reforço– Aprendizado Q

• Exemplo simples: labirinto• Problema Mundo do Wumpus• Conclusão e Trabalhos Futuros

Aprendizado de Máquina

• Inteligência Artificial– Conceito principal

• Agentes Inteligentes X Agentes com Aprendizado

Aprendizado de Máquina

• Aprendizado Supervisionado– Par de treinamento– Conhecimento do Modelo

• Aprendizado Não-Supervisionado– Classificação de dados

• Aprendizado Por Reforço– “Livre de Modelo”– Treinamento contínuo

Aprendizado Por Reforço

• Histórico– Origens na psicologia– Interesse desde 1950– Aplicação na década de 1980

• Aplicações em geral– Jogos– Ajuste de parâmetros– Tarefas cotidianas

Aprendizado Por Reforço

• Características– Processos seqüenciais: Condição de Markov• P((st+1, a) | st, st-1, st-2, st-3...) = P((st+1, a) | st)

– Recompensa adiada– Exploração– Ambiente parcialmente observável– Aprendizado “duradouro”

Aprendizado Por Reforço

• Funcionamento– Estado s, ação a, política π, valor acumulado Vπ(s)– Vπ(st) ≡ rt + γrt+1 + γ²rt+2 + γ³rt+3… ≡ ∑ γ i rt+i

– π* ≡ argmaxπ Vπ(s), ( s)∀

Aprendizado Q

• π*(s) = argmaxa (r(s, a) + γV*(δ(s, a)))

• Q(s, a) = r(s, a) + γ maxa’ Q(s’, a’)

•

Aprendizado QFunção APRENDIZADO_QVariáveis estáticas:Grupo de estados S;Grupo de ações A;Estados s, s’;Ações a, a’;Tabela de valores S x A; 1. Para todo s2. Para todo a3. inicializa a tabela Q(s, a) com 04. Para sempre faça5. seleciona uma ação a em A6. guarda a recompensa imediata r(s, a)7. s’ recebe o novo estado, δ(s, a)8. atualiza Q(s, a) com r(s, a) + γ maxa’ Q(s’, a’)9. estado atual s recebe s’

Aprendizado Q

Implementação

• Linguagem Delphi•

Primeiro Exemplo: Grid Básico

• Verificar funcionamento do algoritmo e da implementação

• Configurações do Grid– Estado é a posição (x, y) no grid– Ações possíveis: cima, direita, baixo, esquerda e

ficar– Estados objetivos com recompensa

• Aprende o menor caminho a partir de cada estado

Primeiro Exemplo

• Demonstração da aplicação

Mundo do Wumpus

• Problema clássico de Inteligência Artificial•

Mundo do Wumpus

• Primeira Abordagem– Posicional (semelhante ao GRID)– Desconhecimento por parte do agente das

características do problema– “vento” com penalidade– “vento” sem penalidade

Mundo do Wumpus

• Primeira Abordagem– Demonstração da aplicação

Mundo do Wumpus

• Primeira abordagem: resultados– Aprendeu a desviar dos estados ruins– Mesmo o “vento” sem penalidade, o agente se

afasta do buraco– Encontra um caminho até o ouro, não

necessariamente o menor

Mundo do Wumpus

• Segunda abordagem– Objetivo: generalizar o aprendizado

• Tirar a informação de “posição” do estado do agente

• Estado representado pelas propriedades da posição do agente e das posições adjacentes– Uso da memória– Inserção de uma nova propriedade:

“desconhecido”

Mundo do Wumpus

• Não-determinismo– Tabela de freqüências• Treino: Q(s, a) = (Q(s, a)+v)• Cálculo do valor: Q(s, a)/F(s, a)

• Novo objetivo: sobreviver– Recompensa por explorar

Mundo do Wumpus

• Segunda Abordagem– Demonstração da aplicação

Mundo do Wumpus

• Segunda abordagem: Resultados– Aprende algumas implicações lógicas do modelo:

•

– Age de forma aleatória em outros casos:

•

Conclusão

• Aprendizado com ampla aplicabilidade– “liberdade de modelo” é o grande diferencial

• Resultados– Conseguiu aprender o modelo em algumas

situações.– Necessita de uma melhor adaptação do problema

para melhores resultados

Trabalhos Futuros

• Novas abordagens– Outras representações de estado– Outros tipos de ações

• Interação com outros métodos de aprendizado– A Tabela Q pode ser treinada em uma Rede

Neural para generalizar estados não treinados