Agentes Baseados em
Utilidade
Gustavo Danzi de Andrade
Patrícia Tedesco
{gda,pcart}@cin.ufpe.br
Parte I:
Decisões Simples
“Como um agente deve tomar
decisões de modo que, em média, ele
consiga o que quer”
Na aula passada...
Agentes
Percebem um estado s
sensores
Executam uma ação a
atuadores
sS
(espaço de estados)
aA
(espaço de ações)
T(s,a,s’)  
(probabilidade de transição de estados, em mundos dinâmicos)
U(s)  
(função de utilidade)
Na aula passada...

Funções de Utilidade:



Associam a cada estado um valor real
Indica a “felicidade” do agente em estar em cada estado
Princípio de Maximização da Utilidade:
“Um agente racional deve escolher a ação que maximiza sua
utilidade esperada”

Utilidade Esperada

Indica a utilidade de uma ação a que pode resultar em diversos
estados s i
UE(s,a) = ∑ i T(s,a,s i) . U(s i)
Parte 2: Decisões
Complexas
“Métodos para decidir o que fazer
hoje, dado que nós poderemos ter
que decidir de novo amanhã”
Problemas de Decisões Seqüenciais

Anteriormente estávamos lidando com problemas de
decisão episódicos:


Problemas de decisões seqüenciais:



Utilidade de cada resultado de uma ação conhecido!
Utilidade do agente depende de uma seqüência de decisões
Envolvem utilidades, incertezas e percepção
Podem ser vistos como uma generalização do
problema de planejamento
Exemplo: Ambiente 4x3



Interação termina quando agente alcança
um dos estados finais (+1 ou -1)
Ações disponíveis:
 Up, Down, Left e Right
Ambiente totalmente observável




2
-1
1
INÍCIO
1
2
3
4
Locomoção estocástica
Se agente bater em uma parede
permanecerá no mesmo quadrado
Em cada estado s agente recebe uma
Recompensa R(s):

R(s) = -0.04 para todos estados não terminais
 Dois estados finais R(s) = +1 ou R(s) = -1

+1
Agente sabe onde está!
Ações não confiáveis

3
Por enquanto, utilidade pode ser dada pela
soma das recompensas recebidas!
0.8
0.1
0.1
Processo de Decisão de Markov (PDM)
Especificação de um problema de decisão seqüencial em um
ambiente totalmente observável com um modelo de transição de
Markov e recompensas aditivas

Definido pelos seguintes componentes:


Estado Inicial: S0
Modelo de Transição: T(s,a,s’)


Função de Recompensa: R(s)


Probabilidade de chegar a s’ como resultado da execução da
ação a no estado s
Utilidade do estado s para o agente
Hipótese de transições Markovianas:

Próximo estado depende apenas da ação atual e do estado
atual, não dependendo de estados passados
Como são as soluções desse problema?


Uma solução deve especificar o que o agente deve
fazer em qualquer estados em que possa chegar
Seqüência fixa de ações não o resolvem:


Solução: construir uma Política (Policy):




Ações não confiáveis não geram estados deterministicamente
 (s) = ação recomendada para estado s
Assim, o agente sabe como atuar em qualquer estado
Utilidade esperada de uma política é dada pelas
seqüências de ações que ela pode gerar
Política Ótima *:



3

Política que produz a mais alta utilidade
esperada
2

1

1
+1

-1



2
3
4
Funções de Utilidade para
Problemas Seqüenciais

Como definir funções de utilidade para problemas
seqüenciais?
U ([s0, s1, ... , sn])

Primeiro deve-se responder as seguintes perguntas:


O Horizonte Temporal para a tomada de decisão é Finito ou
Infinito ?
Como calcular a utilidade de uma seqüência de estados?
Horizontes Finitos e Infinitos

Horizontes Finitos:

Existe um tempo limite N após o qual nada mais importa



Exemplo: Game Over
Uh ([s0, s1, ... , sn+k]) = Uh ([s0, s1, ... , sN]), para todo k > 0
Exemplo:
Supondo que o agente inicia em (3,1)
 N = 3: para atingir +1 agente deve executar a ação Up
 N = 100: há tempo suficiente para executar a ação Left e seguir a
rota mais segura
 Política ótima para um ambiente finito é não estacionária



Pode mudar com o passar do tempo
Horizontes infinitos:
 Ação ótima depende apenas do estado atual
 Política ótima é estacionária
3
+1
2
-1
1
INÍCIO
1
2
3
4
Cálculo de Utilidade para
Seqüência de Estados

Com o que Uh ([s0, s1, ... , sn]) se parece ?


Deve-se supor que preferências entre seqüências de
estados são estacionárias


Função de utilidade com vários atributos...
Dado [s0, s1, s2, ... ] e [s0’, s1’, s2’, ... ],
se s0 = s0’ então,
[s1, s2, ... ] e [s1’, s2’, ... ] devem estar ordenados segundo a
mesma preferência
Baseado nesse princípio, existem apenas duas
maneiras de atribuir utilidades a seqüências de
estados:


Recompensas aditivas
Recompensas descontadas
Recompensas

Recompensas Aditivas:



Uh ([s0, s1, ... , sn]) = R(s0) + R(s1) + R(s2) + ...
Recompensas Descontadas:

Uh ([s0, s1, ... , sn]) = R(s0) +  R(s1) + 2 R(s2) + ...

Onde  é chamado fator de desconto e tem valor entre 0 e 1
Fator de desconto:



Descreve a preferência de um agente com relação a
recompensas atuais sobre recompensas futuras
 próximo a 0  recompensas no futuro distante são
irrelevantes
 = 1  recompensa aditiva
Solução 1: Algoritmo Value Iteration

Idéia: calcular a utilidade dos estados e utilizá-las
para escolher uma ação ótima

Utilidade de cada estado definida em termos da
utilidade das seqüências de ações que podem se
seguir a partir dele



R(s): recompensa a “curto prazo” por se estar em s
U(s): recompensa total a “longo prazo” a partir de s
Utilidade de um estado é dada pela recompensa
imediata para aquele estado mais a utilidade
esperada descontada do próximo estado, assumindo
que o agente escolhe a ação ótima
Algoritmo Value Iteration

Exemplo:


U(1,1) = -0.04 +  max {
0.8 U(1,2) + 0.1 U(2,1) + 0.1 U(1,1),
0.9 U(1,1) + 0,1 U(2,1),
0.9 U(1,1) + 0.1 U(2,1),
0.8 U(2,1) + 0.1 U(1,2) + 0.1 U(1,1) }
(Up)
(Left)
(Down)
(Right)
Equações de Bellman são a base do algoritmo Value
Iteration para resolver PDMs
U(s) = R(s) +  maxa ∑s’ T(s,a,s’).U(s’)

Com N estados, existem N equações
Algoritmo Value Iteration

Algoritmo:
1.
2.
3.
4.
Inicializar utilidades com valores arbitrários (ex.: 0)
Calcular o lado direito da equação para cada estado
Atualizar valor da utilidade de cada estado
Continuar até atingir um equilíbrio
3
0.812
2
0.762
1
0.705
1
0.812
0.918
+1
0.660
-1
0.655
0.611
0.388
2
3
4
Algoritmo Policy Iteration

Idéia: se uma ação é claramente melhor que outras,
então a magnitude exata da utilidade de cada estado
não necessita ser precisa

Alterna entre dois passos, iniciando a partir de uma
política inicial 0 qualquer:


Avaliação da Política: dada política i , calcular Ui = U  i
Melhora da Política: calcular nova política i+1 , utilizando um
passo para frente baseado em Ui
Algoritmo Policy Iteration

Algoritmo:
Enquanto não (mudouPolítica)
Para cada estado s
se ( maxa s’ T(s,a,s’) U[s’] ) > ( s’ T(s,  i(s),s’) U[s’])
então
[s] = argmaxa s’ T(s,a,s’) U[s’]
mudouPolítica = true;

Algoritmo encerra quando passo Melhora da Política
não produz nenhuma mudança nas utilidades
Algoritmo Policy Iteration

Mais simples para Avaliar a Utilidade de um estado:

Policy Iteration:
Ui(s) = R(s) +  s’ T(s, i(s), s’) Ui(s’)

Value Iteration:
U(s) = R(s) +  maxa s’ T(s,a,s’) U(s’)

Exemplo:

Ui (1,1) = 0.8 Ui(1,2) + 0.1 Ui(1,1) + 0.1 Ui(2,1)
3

2

1

1


+1

-1



2
3
4
PDMs Parcialmente Observáveis (PDMPOs)

MDPs assumem que o ambiente é totalmente
observável

Política ótima depende apenas estado atual

Em ambientes parcialmente observáveis agente não
sabe necessariamente onde ele está

Quais os problemas que surgem?


Agente não pode executar ação (s) recomendada para o
estado, pois não consegue identificar o s atual
Utilidade do estado s e a ação ótima depende não só de s, mas
de quanto o agente conhece sobre s
PDMs Parcialmente Observáveis (PDMPOs)

Exemplo: agente não tem menor idéia de onde está


S0 pode ser qualquer estado menos os finais
Solução: Mover Left 5 vezes
Up 5 vezes e Right 5 vezes
3
+1
2
-1
1
1
2
3
4
PDMs Parcialmente Observáveis (PDMPOs)

Possui os mesmo elementos de um MDP
acrescentando apenas:



Modelo de Observação: O(s, o)
Especifica a probabilidade de perceber a observação o no
estado s
Conjunto de estados reais que o agente pode estar =
Belief State (ou estado de crenças)



Em PDMPOs um Belief State b, é uma distribuição de
probabilidade sobre todos os estados possíveis:
Ex.: estado inicial na figura = {1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9,
1/9, 1/9, 0, 0}
b(s) denota a probabilidade associada ao estado s pelo Belief
State b
PDMs Parcialmente Observáveis (PDMPOs)


b = Belief State atual
Agente executa a ação a e percebe a observação o,
então:


Ponto fundamental em PDMPOs:



Novo Belief State b’ = FORWARD (b, a, o)
A ação ótima depende apenas do Belief State corrente do
agente
* (b): mapeamento de crenças em ações
Ciclo de decisão de um agente PDMPO:
1. Dado o Belief State corrente b, execute ação a = * (b)
2. Receba observação o
3. Atualize o Belief State corrente usando FORWARD (b, a, o)
Decisões com Múltiplos Agentes:
Teoria dos Jogos

O que acontece quando a incerteza é proveniente de
outros agentes e de suas decisões? E se as essas
decisões são influenciadas pelas nossas?



A Teoria dos Jogos trata essas questões!
É usada para tomar decisões sérias (decisões de preço,
desenvolvimento de defesa nacional, etc)
Na Teoria dos Jogos, jogos são compostos de:



Jogadores
Ações
Matriz de Resultado
Decisões com Múltiplos Agentes:
Teoria dos Jogos

Cada jogador adota uma Estratégia (diretriz)

Estratégia Pura:


Estratégia Mista:


Diretriz determinística: uma ação para cada situação
Ações selecionadas sobre uma distribuição probabilística
Perfil de Estratégia: associação de uma estratégia a
um jogador
Teoria dos Jogos: Exemplo 1



Dois ladrões (Alice e Bob) são presos perto da cena
do crime e interrogados separadamente
Ações: testemunhar, recusar
Matriz de resultados:
Alice
Bob

Testemunhar
Recusar
Testemunhar
A = -5; B = -5
A = -10; B = 0
Recusar
A = 0; B = -10
A = -1; B = -1
Dilema do Prisioneiro:


Eles devem testemunhar ou se recusarem a testemunhar?
Ou seja, qual estratégia adotar?
Teoria dos Jogos: Exemplo 1

Estratégia Dominante:



Estratégia que domina todas as outras
É irracional não usar uma estratégia dominante, caso exista
Um resultado é dito “Pareto Dominated” por outro se
todos jogadores preferirem esse outro resultado
Teoria dos Jogos: Exemplo 1

Equilíbrio de Estratégia Dominante:


Qual será a decisão de Alice se ela for racional ?


Bob irá testemunhar, então {Testemunhar} !
Então, eis que surge o dilema:


Situação onde cada jogador possui uma estratégia dominante
Resultado para o ponto de equilíbrio é Pareto Dominated pelo
resultado {recusar, recusar} !
Há alguma maneira de Alice e Bob chegarem ao
resultado (-1, -1)?


Opção permitida mais pouco provável
Poder atrativo do ponto de equilíbrio !
Equilíbrio de Nash

Equilíbrio de Nash:





Agentes não possuem intenção de mudar de estratégia
Condição necessária para uma solução
John Nash provou que todo jogo possui um equilíbrio assim
definido
Equilíbrio de Estratégia Dominante é um Equilíbrio
de Nash
Esse conceito afirma que existem estratégias que se
equilibram mesmo que não existam estratégias
dominantes
Teoria dos Jogos: Exemplo 2

Exemplo:


Uma companhia de fabricante de hardware (Best) e outra de
discos (ACME)
Dois equilibrios de Nash:
 {dvd, dvd} e {cd, cd}
ACME
Best
DVD
CD
DVD
A = 9; B = 9
A = -4; B = -1
CD
A = -3; B = -1
A = 5; B = 5