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 Q
Função APRENDIZADO_Q
Variá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.
2.
3.
4.
5.
6.
7.
8.
9.
Para todo s
Para todo a
inicializa a tabela Q(s, a) com 0
Para sempre faça
seleciona uma ação a em A
guarda a recompensa imediata r(s, a)
s’ recebe o novo estado, δ(s, a)
atualiza Q(s, a) com r(s, a) + γ maxa’ Q(s’, a’)
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