Agentes Baseados em
Utilidade
Métodos da Computação Inteligente
Universidade Federal de Pernambuco
Aluno: Rodrigo Barros de Vasconcelos Lima
Parte I: Decisões
Simples
“Como um agente deve tomar decisões de modo que,
em média, ele consiga o que quer”
Decision Theoretic Agents

Agente capaz de ...

Tomar decisões racionais baseado no que acredita e deseja
 Tomar decisões em ambientes com incertezas e objetivos conflitantes

Possui uma escala contínua de medida de qualidade sobre os estados


Valores associados a cada estado (utilidade) indicando a “felicidade” do agente !
Funções de Utilidade associam um valor a um estado
Indica o “desejo” por estar nesse estado
 U(S) = utilidade estado S de acordo com o agente


Ex.: s1 = {rico, famoso}, s2 = {pobre, famoso}
U(s1) = 10
U(s2) = 5
Determinando Função de Utilidade

Resulti(A):


Todos os possíveis estados de saída de uma ação não-determinista A
Para cada saída possível é associado uma probabilidade:

P (Resulti(A) | Do(A), E)
 Onde,
E resume a evidência que o agente possuí do mundo
Do(A) indica que a ação A foi executada no estado atual

Utilidade esperada de uma ação A dado a evidência do mundo E:
EU(A|E) = i P(Resulti(A)|Do(A),E) U(Resulti(A))

Problemas:

Todas ações teriam que ser enumeradas
 P, Result nem sempre disponíveis
 EU pode ser de custo computacional proibitivo
Exemplo: Utilidade Esperada

Robô deve transportar uma caixa
E = caixa é de metal
a1 = Chutar: s1, caixa no destino 20%
s2, caixa no meio 30%
s3, caixa longe destino 50%
U(s1) = 10
U(s2) = 5
U(s3) = 0
a2 = Carregar: s1, balde no destino 80%
s2, balde na origem 20%
U(s1) = 10
U(s2) = 0
EU(a1) = 20x10 + 30x5 + 50x0 = 350
EU(a2) = 80x10 + 20x0 = 800
Preferências Racionais

Principio da Maximização da Utilidade: agente racional deve escolher
ação que maximiza sua utilidade esperada

Preferências racionais permitem descrever o melhor comportamento
como aquele que maximiza EU

Notação:




A  B: A é preferível a B
A ~ B: agente indiferente entre A e B
A  B: agente prefere A à B ou é indiferente
Para ações não deterministas:

A e B são loterias, i.e., distribuições probabilísticas sobre um
conjunto de estados de saída (os “prêmios” de uma loteria)
L = {p1.S1; p2. S2; ...; pn.Sn}
Restrições Sobre Preferências
Racionais

Axiomas da Teoria da Utilidade:

Orderabilidade:
(A > B)  ( B > A)  (A ~ B)

Transitividade:
(A > B)  (B > C)  (A > C)


Preferências que satisfaçam os
axiomas garantem a existência de
uma função real U, tal que:



U(A) > U(B)  A > B
U(A) = U(B)  A ~ B
U (p1.S1; ... ; pn.Sn) = i pi U(Si)
Continuidade:
A > B > C  p [p.A; 1 - p.C] ~ B

Substitutability:
A ~ B  [p.A; 1 – p.C] ~ [p.B; 1 – p.C]

Monoticidade:
A > B  ( p  q  [p.A; 1 – p.B]  [q.A; 1 – q.B] )

Decomposabilidade:
[p.A; 1 – p. [q.B; 1 – q.C] ] ~ [p.A; (1 – p)q.B; (1 – p)(1 – q). C]
Restrições Sobre Preferências
Racionais

Violação das restrições levam a comportamentos irracionais

Exemplo: agente com preferências não transitivas pode ser induzido a dar
todo o seu dinheiro:

Se B > C, então um agente que possuí C pagaria 1 centavo para obter B
Se A > B, então um agente que possuí B pagaria 1 centavo para obter A
Se C > A, então um agente que possuí A pagaria 1 centavo para obter C


Exemplo: A Utilidade do Dinheiro

Um jogador ganhou um prêmio de R$ 1.000.000 em um programa de TV

Apresentador oferece uma aposta:
Se ele jogar a moeda e aparecer cara  jogador perde tudo
 Se aparecer coroa  jogador ganha R$ 3.000.000


O Valor Monetário Esperado da aposta é:

0.5 (R$ 0) + 0.5 (R$ 3.000.000) = $ 1.500.000

O Valor Monetário Esperado de recusar a aposta é de R$ 1.000.000
(menor)

Isso indica que seria melhor aceitar a aposta ?
Exemplo: A Utilidade do Dinheiro

Utilidade Esperada para cada uma das duas ações:

EU (Aceitar) = 0.5 U(Sk) + 0.5 U(Sk+3.000.000)
 EU (Rejeitar) = U(Sk+1.000.000)


Onde, Sk = riqueza atual do jogador
Deve-se atribuir valores de utilidade para cada estado de saída:

Sk = 5;
 Sk+3.000.000 = 10;
 Sk+1.000.000 = 8

Ação racional: rejeitar !

Conclusão: Utilidade não é diretamente proporcional ao valor monetário

Utilidade (mudança no estilo de vida) para o primeiro R$ 1.000.000 é muito alta
Funções de Utilidade Multi-Atributo

Como tratar funções de utilidades com várias variáveis X1, ..., Xn ?


Ex.: Construir aeroporto - U(Mortes, Barulho, Custo)
Existem basicamente dois casos:

Decisões podem ser tomadas sem combinar os valores dos atributos em um
único valor da utilidade (Dominância)

A utilidade resultante da combinação dos valores dos atributos pode ser
especificada concisamente (Estrutura de Preferência e Utilidade Multi-atributo)
Dominância Total

Se um estado S1 possui valores melhores em todos seus atributos do
que S2, então existe uma dominância total de S1 sobre S2

 i Xi(B)  Xi(A) (e portanto U(B)  U(A))

Ex.: Local S1 para Aeroporto custa menos, gera menos poluição
sonora e é mais seguro que S2

Dominância total raramente acontece na prática !!!
Dominância Estocástica

Exemplo, custo de construir aeroporto :
Em
S1 valor uniformemente distribuído entre $2,8 e
$4,8 bilhões;
Em
S2 valor uniformemente distribuído entre $3 e
$5,2 bilhões;
P
S1
S2
Dada a informação que utilidade decresce com
custo:

S1

domina estocasticamente S2
$
-5.2
- 2,8
Na prática, dominância estocástica pode geralmente ser definida
usando apenas um raciocínio qualitativo

Ex.: custo de construção aumenta com a distância para a cidade:

S1 é mais próximo da cidade do que S2  S1 domina S2 estocasticamente
sobre o custo
Estrutura de Preferência e Utilidade
Multi-Atributo

Supondo que existem n atributos com d possíveis valores:

No pior caso, serão necessários dn valores (preferência sem regularidade!)

A Teoria da Utilidade Multi-atributo assume que preferências de agentes
possuem certa regularidade (estrutura)

Tenta mostrar que a Utilidade de um agente possui uma função de utilidade
do tipo:
U(x1 ... Xn) = f[ f1(x1) ..... f2(x2) ]
Onde f seja uma função o mais simples possível
Estrutura de Preferência
(Situação Determinista)

X1 e X2 são preferencialmente independente de X3 sss:

Preferência entre {x1, x2, x3} e {x1’, x2’, x3} não depende em x3

Independência preferencial mútua (MPI): todos os pares de atributos
são preferencialmente independente com relação aos demais

Com MPI, o comportamento preferencial do agente pode ser descrito
como uma maximização da função:


V (x1 ... xn) = i Vi(xi)
Para o caso não determinista, basta estender para lidar com loterias
Redes de Decisões

Formalismo para expressar e resolver
problemas de decisão: estende Redes
Bayesianas adicionando ações e utilidades

Nós de Chance (ovais): representam
variáveis como nas redes Bayesianas

Nós de Decisão (retângulo): pontos onde
agente deve escolher uma ação

Nós de Utilidade (diamantes): representam
as funções de utilidade do agente
 Algoritmo
de avaliação:
1. Atribuir
os valores das variáveis para o estado corrente;
2. Calcular o valor esperado do nó de utilidade dado a ação e os valores das variáveis;
3. Retornar a ação com maior Utilidade Máxima Esperada
Teoria do Valor da Informação

Problemas anteriores assumiam que todas as informações estavam
disponíveis

O que acontece quando elas não estão?


Cabe ao agente buscar as informações necessárias ...
No entanto ...

Obtenção de informações tem um custo associado
 Ex.: solicitação de um exame por parte de um medico

A Teoria do Valor da Informação permite que o agente escolha quais
informações adquirir
Calculo do Valor da Informação:
Exemplo

Exemplo: comprar os direitos de exploração de reservas de petróleo:






Dois blocos A e B, apenas um possui óleo com valor C;
Probabilidade de comprar o bloco certo = 0,5
O preço de cada bloco é C/2
Consultor oferece uma pesquisa para detectar qual bloco possui petróleo.
Qual o valor dessa informação?
Solução:

Calcular o valor esperado da informação = valor esperado da melhor ação dada
a informação – valor esperado da melhor ação sem a informação;
 Pesquisador irá informar: “há óleo em A” ou “não há óleo em A” (p = 0,5)
 Então:
0,5 x valor de “comprar A” dado que “há óleo em A” + 0,5 x valor de “comprar B” dado
que “não há óleo em A” – 0 =
= (0,5 x C/2) + (0,5 x C/2) – 0 = C/2
Valor da Informação: Exemplo

A1 e A2 duas rotas distintas através de uma montanha no inverno

A1 e A2 são as únicas ações possíveis, com EU = U1 e U2, respectivamente
 A1 = caminho mais baixo, sem muito vento
 A2 = caminho mais alto, com muito vento


Nova evidência NE produzirá novas utilidades esperadas U1’ e U2’


U (A1) > U (A2)
Vale a pena adquirir NE?
E se mudássemos o cenário?

II) A1 e A2 são duas estradas onde venta muito, de mesmo tamanho e levamos
um ferido grave
 III) Mesmas estradas A1 e A2 mas agora no verão

Conclusão: uma informação só terá valor caso ela gere uma mudança de
plano, e se esse novo plano for significante melhor do que o antigo !
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

Exemplo:
3
+1
2
-1
1
0.1
0.1
INÍCIO
1

0.8
2
3
4
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 (agente sabe onde está!)
 Ações não confiáveis (locomoção estocástica)
Processo de Decisão Markoviana (MDP)

Definido pelos seguintes componentes:

Estado Inicial: S0
 Modelo de Transição: T(s,a,s’)
 Função de Recompensa: R(s)

Modelo de Transição T(s, a, s’): probabilidade de chegar a s’ como
resultado da execução da ação a em s

Hipótese de transições Markovianas: próximo estado depende apenas da
ação atual e estado atual, não passados

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

Utilidade pode ser dada pela soma das recompensas recebidas
Como são as soluções para esse
problema?

Seqüência fixa de ações não resolvem o problema

Uma solução deve especificar o que o agente deve fazer em qualquer um
dos estados que ele possa chegar:


Política (Policy):  (s) = ação recomendada para estado s
Política Ótima:

Política que produz a mais alta utilidade esperada
 Notação: *
3

2

1

1


+1

-1



2
3
4
Funções de Utilidade para Problemas
Seqüenciais

Como definir funções de utilidades para problemas seqüenciais?


Uh ([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 (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ção Up
 N = 100  tempo suficiente para executar ação Left (rota mais segura)

Política ótima para um ambiente finito é não estacionária

Para horizontes infinitos:
3
+1
2
-1

Ação ótima depende apenas do estado atual
 Política ótima é estacionária
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 !
[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 no principio estacionariedade, existem apenas duas maneiras de
atribuir utilidades a seqüência de utilidades:

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 com 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
Algoritmo Value Iteration

Idéia: calcular a utilidade de cada estado e as usar para escolher uma ação
ótima em cada estado

Utilidade de cada estado definida em termos da utilidade das seqüências
de ações que podem se seguir a partir dele

Utilidade de um estado é dado pela
equação de Bellman:


U(s) = R(s) +  maxa s’ T(s,a,s’) U(s’)
Exemplo:

3
0.812
2
0.762
1
0.705
1
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) }
0.812
0.918
+1
0.660
-1
0.655
0.611
0.388
2
3
4
(Up)
(Left)
(Down)
(Right)
Algoritmo Value Iteration

Equações de Bellman são a base do algoritmo Value Iteration para resolver
MDPs

N estados = N equações

Algoritmo:
Inicializar utilidades com valores arbitrários (tipicamente 0)
2. Calcular o lado direito da equação para cada estado
3. Atualizar valor da utilidade de cada estado
4. Continuar até atingir um equilíbrio
1.

Prova-se que essa iteração eventualmente converge para um único
conjunto de soluções (algoritmo atinge equilíbrio !)
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:
Avaliação da Política: dada política i , calcular Ui = U  i
 Melhora da Política: calcular nova política i+1

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
MDPs Parcialmente Observáveis
(POMDPs)

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
 Utilidade do estado s e a ação ótima depende não só de s, mas de quanto o
agente conhece sobre s


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
start
1
1
2
3
4
MDPs Parcialmente Observáveis
(POMDPs)

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

Em POMDPs um Belief State b, é uma distribuição probabilística 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
MDPs Parcialmente Observáveis
(POMDPs)

b = Belief State atual

Agente executa a ação a e percebe a observação o, então:


Novo Belief State b’ = FORWARD (b, a, o)
Ponto fundamental em POMDs:

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 POMDP:
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?


A Teoria dos Jogos trata essa questão !
Jogos na Teoria dos Jogos são compostos de:

Jogadores
 Ações
 Matriz de Resultado

Cada jogador adota uma Estratégia (diretriz)

Estratégia Pura: diretriz deterministica, uma ação para cada situação
 Estratégia Mista: ações selecionadas sobre uma distribuição probabilística

Perfil de Estratégia: associação de uma estratégia a um jogador

Solução é um perfil de estratégia racional
Teoria dos Jogos: Exemplo 1

Dois ladrões (Alice e Bob) são presos perto da cena do crime e
interrogados separadamente

Matriz de resultados:

Alice: testemunhar
Alice: recusar
Bob: testemunhar
A = -5; B = -5
A = -10; B = 0
Bob: 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?

Estratégia Dominante:

Estratégia que domina todas as outras
 É irracional não usar uma estratégia dominante, caso uma 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 desviar da estratégia especificada
 Condição necessária para uma solução

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

Exemplo:

Acme: DVD
Acme: CD
Best: DVD
A = 9; B = 9
A = -4; B = -1
Best: CD
A = -3; B = -1
A = 5; B = 5
Dois equilibrios de Nash:

{dvd, dvd} e {cd, cd}