Aula_08_-_Processos_de_Deciso_de_Markov

Prévia do material em texto

Inteligência Artificial
Processos de Decisão de Markov (MDP)
Professor: Felipe Alberto B. S. Ferreira
felipe.bsferreira@ufrpe.br
mailto:felipe.bsferreira@ufrpe.br
Busca Não-Determinística
Exemplo: Mundo em Grid
§ Um problema tipo labirinto
§ Os agentes “vivem” em um grid
§ Muros bloqueiam o caminho
§ Movimento incerto: ações não ocorrem como planejadas
§ 80% do tempo, uma ação leva o agente para o local 
esperado (caso não exista um muro no caminho)
§ 10% do tempo, leva para a esquerda, e 10% para a direita
§ Se existe um muro na direção do movimento, o agente
permanece imóvel
§ O agente recebe uma recompensa a cada passo
§ Pequena recompensa a curto prazo por passo (pode ser 
negativa)
§ Grandes recompensas no fim (boa ou ruim)
§ Objetivo: maximizar a soma das recompensas
Ações do Mundo em Grid
Mundo determinístico Mundo estocástico
Processos de Decisão de Markov (MDP)
§ Um MDP é definido por:
§ Um conjunto de estados s Î S
§ Um conjunto de ações a Î A
§ Uma função de transição T(s, a, s’)
§ Probabilidade de s levar para s’, ou seja, P(s’| s, a)
§ Também chamada de modelo do problema
§ Uma função de recompensa R(s, a, s’) 
§ Pode ser apenas R(s) ou R(s’)
§ Um estado inicial
§ Talvez um estado terminal
§ MDPs são problemas de busca estocásticos
§ Uma forma de resolver é com busca expectimax
§ Veremos uma nova ferramenta a seguir
Demo Mundo em Grid - Manual
Processos de Decisão de Markov?
§ “Markov” normalmente significa que dado um estado atual, os
estados futuro e o passado são independentes
§ Em MDPs, “Markov” significa que o resultado de uma ação
depende apenas do estado atual
§ Similar a problemas de busca em que os sucessores de um 
estado dependem apenas do estado atual (independente do 
trajeto)
Andrey Markov 
(1856-1922)
Políticas
Política ótima com R(s, a, s’) = -0.4 para 
todos os nós s não terminais
§ Em problemas de busca determinísticos de 
único agente, queremos o planejamento
ótimo, ou sequência de ações, do início até o 
objetivo
§ Em MDPs, queremos uma política ótima
§ p*: S → A
§ Uma política p nos dá uma ação para cada estado
§ Uma política ótima maximiza a utilidade esperada se 
seguida corretamente
§ Uma política explícita define um agente reativo
§ Expectimax não calcula toda política
§ Apenas recomenda uma ação dado um estado
Políticas Ótimas
R(s) = -2.0R(s) = -0.4
R(s) = -0.03R(s) = -0.01
Exemplo: Corrida
Exemplo: Corrida
§ Um carro autônomo quer viajar longas distâncias, rapidamente
§ Três estados: Frio, Quente, Superaquecido
§ Duas ações: Devagar, Rápido
§ Ir rápido trás o dobro de recompensa
Frio
Quente
Superaquecido
Rápido
Rápido
Devagar
Devagar
50% 
50% 
50% 
50% 
100% 
100% 
+1 
+1 
+1 
+2 
+2 
-10
Exemplo: Corrida - Árvore de Busca
MDP – Árvores de Busca
§ Cada estado em um MDP “projeta” uma árvore de busca expectimax
a
s
s’
s, a
(s,a,s’) executa uma transição
T(s,a,s’) = P(s’|s,a)
R(s,a,s’)
s,a,s’
s é um 
estado
(s, a) é um 
q-estado
Utilidade de Sequências
Utilidade de Sequências
§ Qual preferência um agente deve ter em sequências de recompensas? 
§ Mais ou menos?
§ Agora ou depois?
[1, 2, 2] [2, 3, 4]ou
[0, 0, 1] [1, 0, 0]ou
Recompensas Descontadas
§ É razoável maximizar a soma das recompensas
§ Também é razoável prefererir recompensas agora do que mais tarde
§ Uma solução: o valor das recompensas decai exponencialmente
Valor agora Valor após um passo Valor após dois passos
Recompensas Descontadas
§ Como descontar?
§ Cada vez que descemos um nível, o 
desconto é aplicado
§ Porquê descontar?
§ Recompensas instantâneas
normalmente tem maior utilidade
§ Também ajuda o algoritmo a 
convergir
§ Exemplo: desconto de 50%
§ U([1,2,3]) = 1*1 + 0.5*2 + 0.25*3
§ U([1,2,3]) < U([3,2,1])
Preferências Estacionárias
§ Teorema: se assumirmos preferências estacionárias:
§ Então: existe apenas duas formas de definir utilidade
§ Utilidade aditiva:
§ Utilidade descontada:
Quiz: Recompensas Descontadas
§ Dado o grid:
§ Ações: Leste, Oeste, e Sair (disponível apenas em estados terminais, a e e)
§ Transições: determinísticas
§ Quiz 1: Para g = 1, qual é a política ótima?
§ Quiz 2: Para g = 0.1, qual é a política ótima?
§ Quiz 3: Para qual g, Oeste e Leste são igualmente bons no estado d?
§ Problema: E se o jogo durar para sempre? Recompensa infinita?
§ Soluções:
§ Horizonte finito: (similar a busca em profundidade limitada)
§ Finaliza após T passos
§ Temos políticas não-estacionárias (p depende do tempo restante)
§ Desconto: entre 0 < g < 1
§ Um g menor implica em um horizonte menor
§ Estado de absorção: garantia de que para cada política, um estado terminal pode
ser alcançado eventualmente (como “superquecido” no exemplo da corrida)
Utilidade Infinita?!
Resumo: Definindo MDPs
§ Processos de Decisão de Markov:
§ Conjunto de estados S
§ Estado inicial s0
§ Conjunto de ações A
§ Transições P(s’|s,a) (or T(s,a,s’))
§ Recompensas R(s,a,s’) (e desconto g)
§ Quantidades calculadas em MDPs (até agora):
§ Política = escolha de uma ação para cada estado
§ Utilidade = soma de recompensas (descontadas)
a
s
s, a
s,a,s’
s’
Resolvendo MDPs
Quantidades Ótimas
§ Valor (utilidade) de um estado s:
V*(s) = utilidade esperada a partir de s e 
agindo otimamente
§ Valor (utilidade) de um q-estado (s,a):
Q*(s, a) = utilidade esperada após ação a, 
a partir do estado s e agindo
otimamente em seguida
§ Política ótima:
p*(s) = ação ótima a partir do estado s
a
s
s’
s, a
(s,a,s’) é uma
transição
s,a,s’
s é um 
estado
(s, a) é um 
q-estado
Demo – Valores V
Ruído = 0
Desconto = 1
Recompensa = 0
Demo – Valores Q
Ruído = 0
Desconto = 1
Recompensa = 0
Demo – Valores V
Ruído = 0.2
Desconto = 1
Recompensa = 0
Demo – Valores Q
Ruído = 0.2
Desconto = 1
Recompensa = 0
Demo – Valores V
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
Demo – Valores Q
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
Demo – Valores V
Ruído = 0.2
Desconto = 0.9
Recompensa = -0.1
Demo – Valores Q
Ruído = 0.2
Desconto = 0.9
Recompensa = -0.1
Valor dos Estados
§ Operação fundamental: calcular o valor de um estado (expectimax)
§ Utilidade esperada considerando ação ótima
§ Média da soma das recompensas (descontadas)
§ É exatamente o que expectimax calcula!
§ Definição recursiva do valor:
a
s
s, a
s,a,s’
s’
Exemplo: Corrida - Árvore de Busca
Exemplo: Corrida - Árvore de Busca
Exemplo: Corrida - Árvore de Busca
§ Temos bastante retrabalho
com expectimax!
§ Problema: estados repetidos
§ Ideia: calcular quantidades
necessárias uma única vez
§ Problema: árvore infinita
§ Ideia: cálculo com limite de 
profundidade, 
§ Limite aumenta até que as 
mudanças sejam “pequenas”
§ Nota: níveis muito profundos são
menos importantes se γ < 1
Valores Limitados por Tempo
§ Ideia chave: valores limitados por tempo
§ Seja Vk(s) o valor ótimo de s se o jogo termina em mais k
passos
§ De modo equivalente, é o que o expectimax limitado em k iria
retornar a partir do estado s
k=0
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=1
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=2
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=3
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=4
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=5
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=6
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=7
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=8
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=9
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=10
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=11
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=12
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
k=100
Ruído = 0.2
Desconto = 0.9
Recompensa = 0
Calculando Valores Limitados por Tempo
Algoritmo Iteração de Valor (Value Iteration)
Algoritmo Iteração de Valor
§ Inicia com V0(s) = 0: sem passos restantes significa que a utilidade esperada é zero
§ Dado um vetor de Vk(s) valores, execute uma iteração do expectimax para cada
estado:§ Repita até convergência
§ Complecidade de cada iteração: O(S2A)
§ Teorema: irá convergir para valores ótimos
§ A política pode convergir antes dos valores
a
Vk+1(s)
s, a
s,a,s’
Vk(s’)
Exemplo: Iteração de Valor
0 0 0
2 1 0
3.5 2.5 0
Assuma desconto 𝛾 = 1!
Referência
§ Stuart RUSSEL e Peter NORVIG, Inteligência Artificial. 3ª ed.
§ Capítulo 17: seções 17.1 até 17.3.