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”
Decision Theoretic Agent

Agente capaz de ...
 Tomar decisões racionais baseado no que acredita e deseja

Diferentemente de um agente lógico
 Pode 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
Funções de Utilidade

Resulti(A): Todos os possíveis estados de saída de uma ação nãodeterminista A

Para cada saída possível é associada 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))

Principio da Maximização da Utilidade: agente racional deve escolher
ação que maximiza sua utilidade esperada !!!

Nesta aula: Tomadas de Decisões Simples

É difícil enumerar todas seqüências de ações

Custo computacional, geralmente, proibitivo
Exemplo: Cálculo da Utilidade
Esperada

Robô deve transportar uma caixa
E = caixa é de metal
a1 = Chutar:
s1, caixa no destino 20%
U(s1) = 10
s2, caixa no meio do caminho 30% U(s2) = 5
s3, caixa longe destino 50%
U(s3) = 0
a2 = Carregar: s1, caixa no destino 80%
s2, caixa na origem 20%
EU(a1) = 0,20 x 10 + 0,30 x 5 + 0,50 x 0 = 3,5
EU(a2 ) = 0,80 x 10 + 0,20 x 0 = 8
U(s1) = 10
U(s2) = 0
Preferências Racionais


Funções de Utilidade são, essencialmente, heurísticas!
Comportamento de qualquer agente racional pode ser adquirindo
supondo-se uma função de utilidade a ser maximizada

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
L = {p1.S1; p2. S2; ...; pn.Sn}
Restrições Sobre Preferências
Racionais


Axiomas da Teoria da Utilidade:

Ordenabilidade:
(A > B)  ( B > A)  (A ~ B)

Transitividade:
(A > B)  (B > C)  (A > C)

Principio da Utilidade:
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

Substitutabilidade:
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]
Exemplo: 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
C

B
Se A > B, então um agente que possui B pagaria 1 centavo para obter A
C

1c
1c
B
1c
A
Se C > A, então um agente que possuí A pagaria 1 centavo para obter C
C
1c
B
1c
A
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,



Variáveis: Segurança, Custo, Poluição sonora
U (Segurança, Custo, Poluição sonora) = ?
Existem basicamente dois casos:

Dominância:
decisões podem ser tomadas sem combinar os valores dos atributos em um
único valor da utilidade

Estrutura de Preferência e Utilidade Multi-atributo:
utilidade resultante da combinação dos valores dos atributos pode ser
especificada concisamente
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 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
P

Em S2 valor uniformemente distribuído entre $3 e
$5,2 bilhões
S1
S2
Dada a informação que utilidade decresce com
custo:

$
-5.2
- 2,8

S1 domina estocasticamente S2
 EU de S1 é pelo menos tão alta quanto EU de S2

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:


A Teoria da Utilidade Multi-atributo assume que preferências de agentes
possuem certa regularidade (estrutura)


No pior caso, serão necessários dn valores (preferência sem regularidade!)
Abordagem básica é tentar identificar essas regularidades!
Agentes com uma certa estrutura em suas preferências terá uma função:
U(x1 ... Xn) = f[ f1(x1) ..... f2(x2) ]
Onde espera-se que f seja uma função simples!
Estrutura de Preferência
(Situação Determinista)

X1 e X2 são preferencialmente independente de X3 se, e somente se:


Independência preferencial mútua (MPI): todos os pares de atributos
são preferencialmente independente com relação aos demais


Ex.: Segurança, Custo, Poluição sonora
Com MPI, o comportamento preferencial do agente pode ser descrito
como uma maximização da função:


Preferência entre {x1, x2, x3} e {x1’, x2’, x3} não depende em x3
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

Representa informações sobre

Estado atual do agente
 Possíveis ações
 Estado resultante e sua utilidade

Composto de:

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:
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
1.
Exemplo: Redes de Decisões
Info. sobre
estado atual
Info. sobre
estado
futuro
Local do Aeroporto
Trafego aéreo
Segurança
Litigação
Barulho
Construção
Custo
U
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
Cálculo 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 gere uma mudança de
plano, e se esse novo plano for significativamente melhor do que o antigo !