Agentes Baseados em
Utilidade
Gustavo Danzi de Andrade
Geber Ramalho
{gda,glr}@cin.ufpe.br
Relembrando

Um agente
 Está
em um mundo descrito por um conjunto de
estados
S ={s1, s2,...,sn}
 Pode realizar, neste mundo, um conjunto de ações
A ={a1, a2,...,at}
 As conseqüências de suas ações são descritas por
uma função de transição


Mundo determinístico T(si,aj)  sk
Mundo não-determinístico (função estocástica)
(si,aj)  {(pt,st), (pk,sk), ... (ps,ss)}
onde pk é a probabilidade do estado ser ak
O que veremos

Agentes capazes de ...


Diferentemente de um agente lógico



Tomar decisões racionais baseado no que acredita e deseja
Pode tomar decisões em ambientes com incertezas e
objetivos conflitantes
Possui uma escala contínua de medida de qualidade sobre os
estados
Funções de Utilidade associam um valor a um estado



Indica a “felicidade” 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
Roteiro

Ambientes Determinísticos e Não-Determinísticos

Funções de Utilidade

Funções de Utilidade Multi-atributo

Teoria do Valor da Informação

Teoria dos Jogos
Escolha de ações

Princípio da Maximização da Utilidade: agente
racional deve escolher ações que maximizam sua
utilidade !

Mundo determinístico


Isto é feito escolhendo diretamente a ação de maior utilidade
Mundo determinístico

É preciso considerar todos os possíveis estados de saída de cada
ação não-determinista e escolher a que maximiza a utilidade
esperada
Ambiente determinístico: exemplo

Exemplo:





S = {(rico,famoso), (rico,desconhecido),
(pobre,famoso),(pobre,desconhecido)}
A = {trabalhar, participar do BigBrother}
Transições de estados (dinâmica do ambiente):
 T[(pobre,desconhecido), trabalhar] = (rico, desconhecido)
 T[(pobre,desconhecido), part. BB] = (rico, famoso)
Função de Utilidade:
 U(rico,famoso) = 10
 U(rico,desconhecido) = 8
 U(pobre,famoso) = 5
 U(pobre,desconhecido) = 0
Supondo que o agente é pobre e desconhecido (estado inicial), qual a
melhor ação a executar?
 Participar do BigBrother...
Em ambientes não-determinísticos

Para cada saída possível é associada uma
probabilidade:

P (Result(A) | Do(A), E)

Onde, E resume a evidência que o agente possui 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:
UE(A|E) = i P(Resulti(A)|Do(A),E) x U(Resulti(A))

Nesta aula: Tomadas de Decisões Simples

O agente decide apenas uma vez
Exemplo 1

Um Robô deve transportar uma caixa
E = a 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%
s4, caixa na origem 20%
UE(a1) = 0,20 x 10 + 0,30 x 5 + 0,50 x 0 = 3,5
UE(a2 ) = 0,80 x 10 + 0,20 x 0 = 8
A melhor ação é Carregar (a2)
U(s1) = 10
U(s4) = 0
Roteiro

Ambientes Determinísticos e Não-Determinísticos

Funções de Utilidade

Funções de Utilidade Multi-atributo

Teoria do Valor da Informação

Teoria dos Jogos
Funções de Utilidade

Funções de Utilidade são, essencialmente,
heurísticas!

Preferências racionais permitem descrever o
melhor comportamento como aquele que maximiza
UE



Propriedades do “desejo” do agente
Caso satisfaçam as restrições racionais, pode-se garantir
a existência de uma Função de Utilidade U(S)  R
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: distribuições probabilísticas sobre um
conjunto de estados de saída
Restrições Racionais

Axiomas da Teoria da Utilidade:

Ordenabilidade: (A > B)  ( B > A)  (A ~ B)

Transitividade: (A > B)  (B > C)  (A > C)

Continuidade: A > B > C  p [p.A; 1 - p.C] ~ B

Substitutibilidade: A ~ B  [p.A; 1 – p.C] ~ [p.B; 1 – p.C]

Monotonicidade:
A > B  ( p  q  [p.A; 1 – p.B]  [q.A; 1 – q.B] )

Decomponibilidade:
[p.A; 1 – p. [q.B; 1 – q.C] ] ~ [p.A; (1 – p)q.B; (1 – p)(1 – q). C]
Exemplo 2: A Utilidade do Dinheiro

Como seria a função de utilidade do dinheiro?

Situação:


Um jogador está ganhando um prêmio de R$ 1.000.000
É oferecida uma aposta: Cara ou Coroa



Se aparecer cara  jogador perde tudo
Se aparecer coroa  jogador ganha R$ 3.000.000
Hipótese 1: Linear?


U(x) = x
Calculando o Valor Monetário Esperado de Aceitar a Aposta:


Calculando o Valor Monetário Esperado de Recusar a Aposta:


0.5 U(R$ 0) + 0.5 U(R$ 3.000.000) = $ 1.500.000
1 U(R$ 1.000.000) = R$ 1.000.000 (menor)
Isso indica que seria melhor aceitar a aposta...
Exemplo 2: A Utilidade do Dinheiro

Hipótese 2: Não-linear?
U(0) = 0
 U(1.000.000) = 100
 U(3.000.000) = 150
 Calculando o Valor Monetário Esperado:




A melhor opção é rejeitar a aposta...


EU (Aceitar) = 0.5 U(0) + 0.5 U(3.000.000 ) = 75
EU (Rejeitar) = U(1.000.000) = 100
Onde, Sk = riqueza atual do jogador
Na prática, o valor do dinheiro depende da situação atual:
U(k,n) = onde k é a riqueza atual e n o novo ganho
 À medida que k cresce, a utilidade de n diminui....


Conclusão:
Utilidade não é diretamente proporcional ao valor monetário
 Dependa da mudança no estilo de vida...

Roteiro

Ambientes Determinísticos e Não-Determinísticos

Funções de Utilidade

Funções de Utilidade Multi-atributo

Teoria do Valor da Informação

Teoria dos Jogos
Funções 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 duas situações:


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))
Dominância Estocástica

Exemplo, custo de construir um aeroporto:

Em S1 valor uniformemente distribuído entre $2,8
e $4,8 bilhões
P
S1

Em S2 valor uniformemente distribuído entre $3 e
$5,2 bilhões
S2
$
Dada a informação que a utilidade decresce
com custo:

-5.2
- 2,8

S1 domina estocasticamente S2
 UE de S1 é pelo menos tão alta quanto UE de S2

Na prática, dominância estocástica pode 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ão uma função:


U(x1,...,Xn) = f[ f1(x1),...,f2(x2) ]
Onde espera-se que f seja uma função simples!
Se os atributos forem mutuamente independentes...
Estrutura de Preferência e Utilidade Multi-atributo

Atributos mutuamente independentes:


Independência preferencial mútua (MPI): todos os
pares de atributos são preferencialmente
independente com relação aos demais


X1 e X2 são preferencialmente independente de X3 se, e
somente se: Preferência entre {x1, x2, x3} e {x1’, x2’, x3} não
depende em x3
Ex.: Segurança, Custo, Poluição sonora
Com MPI, o comportamento preferencial do agente
pode ser descrito como uma maximização da função:


Caso determinista: V (x1 ... xn) = i Vi(xi) (somatório)
Caso não-determinista: basta estender para lidar com
loterias
Exemplo 3

Construir aeroporto:
 Variáveis:
Segurança, Custo, Poluição sonora
 U (Segurança, Custo, Poluição sonora) =




V(Segurança) – V(Custo) – V(Poluição sonora)
V(Segurança) = Número de itens de segurança construídos
V(Custo) = Custo total da construção em milhões de R$
V(Poluição sonora) = População afetada (taxa por 100 mil
hab.)
Roteiro

Ambientes Determinísticos e Não-Determinísticos

Funções de Utilidade

Funções de Utilidade Multi-atributo

Teoria do Valor da Informação

Teoria dos Jogos
Teoria do Valor da Informação

Problemas anteriores assumiam que todas as
informações estavam disponíveis

O que acontece quando:




Cabe ao agente buscar as informações necessárias
Obtenção de informações tem um custo associado
Ex.: solicitação de um exame por parte de um médico
A Teoria do Valor da Informação permite que o
agente escolha quais informações adquirir
Exemplo 4

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?
Exemplo 4

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 “há óleo
em B”. Então:



Melhor ação com a informação: C
Melhor ação sem a informação: (0,5 x C) + (0,5 x 0) = C/2
Valor esperado da informação: C – C/2 = C/2
Exemplo 4

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.

S1 e S2: dois estados distintos


U1 (S1) > U2 (S2)
Nova evidência NE produzirá novas utilidades esperadas
U1’ e U2’

Vale a pena adquirir NE?


Para uma situação clara, a informação não é necessária...
Para uma escolha obscura, a informação é valiosa...
Roteiro

Ambientes Determinísticos e Não-Determinísticos

Funções de Utilidade

Funções de Utilidade Multi-atributo

Teoria do Valor da Informação

Teoria dos Jogos
Teoria dos Jogos

Agentes baseados em utilidade podem atuar em
ambientes incertos...

Mas 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)
Teoria dos Jogos

Na Teoria dos Jogos, jogos são compostos de:




Jogadores
Ações
Matriz de Resultado
Cada jogador adota uma Estratégia (diretriz)

Estratégia Pura:


Diretriz determinística: uma ação para cada situação
Estratégia Mista:

Ações selecionadas sobre uma distribuição probabilística
Exemplo 5

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
Testemunhar
Recusar
Bob 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?


Estratégia Dominante:
Estratégia que domina todas as outras
 É irracional não usar uma estratégia dominante, caso exista

Exemplo 5

Qual será a decisão de Alice se ela for racional? E de Bob?


Equilíbrio de Estratégia Dominante:


Testemunhar (estratégia dominante)
Situação onde cada jogador possui uma estratégia dominante
Então, eis que surge o dilema:
Resultado para o ponto de equilíbrio é Pareto Dominated pelo
resultado {recusar, recusar} !
 Um resultado é dito “Pareto Dominated” por outro se todos
jogadores preferirem esse outro resultado


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

Mas esse conceito afirma mais:

Existem estratégias que se equilibram mesmo que não existam
estratégias dominantes
Exemplo 6

Exemplo:


Uma companhia de fabricante de hardware (Best) e outra de
discos (ACME)
Dois equilibrios de Nash:
 {dvd, dvd} e {cd, cd}
 Um equilíbrio Pareto Dominated
ACME
Best
DVD
CD
DVD
A = 9; B = 9
A = -1; B = -5
CD
A = -5; B = -1
A = 5; B = 5
Roteiro

Ambientes Determinísticos e Não-Determinísticos

Funções de Utilidade

Funções de Utilidade Multi-atributo

Teoria do Valor da Informação

Teoria dos Jogos
Em resumo...

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)
Teoria dos Jogos:

Estratégias dominantes e equilíbrios