Agentes Baseados em
Utilidade
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. BBB: 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 !!!
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 representam preferências!

Utilidade(Fusca75) > Utilidade(BMW2014)
 O agente que maximiza tal utilidade continua sendo racional

O modelo de racionalidade mais utilizado é aquele que maximiza EU

Notação (Relações de Preferência):




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 podem levar a comportamentos irracionais

Exemplo: agente com preferências estritas 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
Utilidade do Dinheiro
Fonte: AIMA, 3rd ed, p 617
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 (de Pareto)

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(S1)  Xi(S2) (e portanto U(S1)  U(S2))

Ex.: Local S1 para Aeroporto custa menos e é mais seguro que S2

Dominância total raramente acontece na prática !!!
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

X1 e X2 são preferencialmente independente de X3 se, e somente se:


Independência total: todos os atributos são preferencialmente
independente com relação aos demais


Preferência entre {x1, x2, x3} e {x1’, x2’, x3} não depende em x3
Ex.: Segurança, Custo, Poluição sonora
Sob a premissa de independência total, o comportamento preferencial
do agente pode ser descrito como uma maximização da função aditiva:

V (x1 ... xn) = i Vi(xi)
Modelos Gráficos para Decisão sob
Risco

Modelos gráficos básicos para decisão sob risco

Árvores de decisão
 Redes de Decisões ou Diagramas de Influência

Árvores de decisão

Arborescência que representa um problema de decisão sob risco
 Representa as diferentes sequências possíveis de decisões e acontecimentos
(ou estados)

Redes de decisão

Representação mais compacta e intuitiva para problemas de decisão
 No entanto os aspectos temporais de uma decisão são menos explícitos

Computacionalmente, árvores de decisão e redes de decisão são
equivalentes
Árvores de decisão

Três tipos de vértice:

Decisão: representados por quadrados, correspondem a etapas de decisão.
 Chance: representados por círculos, correspondem às realizações dos estados.
 Terminais: indicam se os resultados possíveis do processo de decisão;
associamos a cada vértice terminal o valor do critério de avaliação para a
situação obtido a partir das decisões e dos eventos associados ao caminho que
vai dar raiz a este vértices
Decisão
Chance
Terminal
Árvores de decisão

Dois tipos de arestas:
As arestas que saem de vértices “decisão” representam as diferentes ações
possíveis
 As arestas que saem dos vértices de “chance” representam a possibilidade de
realização dos estados da natureza ou do ambiente. Esses arcos podem ser
eventualmente valorados pela probabilidade de ocorrência do estado associado

p11
p12
Ação 1
p13
Ação 2
p21
p22
p23
pxx são probabilidades
p11 + p12 + p13 = 1
p21 + p22 + p23 = 1
Árvores de decisão

Cenário

Caminho da árvore partindo da raiz até um vértice terminal. Ele é definido por
uma decisão tomada a cada “nó decisão” e a realização de um estado
observado a cada “nó de chance”.
p11
p12
Ação 1
p13
Ação 2
Cenário: foi tomada a Ação 1 e ocorreu
o evento com probabilidade p13
p21
p22
p23
Exemplo

Ao aproximar-se o fim do ano, um atacadista de lembrancinhas de
empresas prepara sua estratégia de comercialização. Ele considera duas
reações possíveis de sua clientela:

r1: reação favorável
 r2: reação mista




Chamaremos de p a probabilidade de observar a reação r1.
O atacadista estima que em caso de reação mista, o lucro líquido realizado
será de um montante x. Ele deverá ser 3 vezes mais alto no caso de
reação favorável.
O atacadista se pergunta então sobre a oportunidade de efetuar uma
campanha publicitária. O custo desta campanha é estimado também em x.
Considera-se que uma campanha publicitária permitirá dobrar o lucro
previsto em caso de reação favorável (r1). Ela não terá nenhum efeito em
caso de reação mista (r2).

Desenhe uma árvore de decisão que represente o problema de escolha de uma
estratégia de comunicação
 Considerando um critério de MEU do lucro, obtenha o valor mínimo de p que
torna preferível lançar a campanha de publicidade.
Redes de Decisões

Formalismo para expressar e resolver problemas de decisão: estende
Redes Bayesianas adicionando ações e utilidades

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:

Suponha que uma empresa de petróleo pretenda comprar o direito de
perfuração de poços de um de n blocos a serem postos à venda. Suponha,
ainda, que exatamente um dos blocos contenha óleo avaliado em $ C, enquanto
os outros não contém nada. O preço de cada bloco é C/n dólares.
 Suponha agora que um geólogo oferece à empresa os resultados de uma
pesquisa referente ao bloco 3, que indica com certeza se o bloco contém óleo.
 Quanto a empresa deve estar disposta a pagar pela informação?

Solução:
Sem a informação, a esperança do lucro ao comprar é 0: 1/n*C – C/n
 A maneira de responder a essa pergunta é examinar o que a empresa faria se
tivesse a informação:




Com probabilidade 1/n, a pesquisa irá indicar que há óleo no bloco 3. Neste caso, a
empresa vai comprar o bloco 3 por C/n e vai faturar C – C / n = (n – 1)C / n
Com probabilidade (n – 1)/n, a pesquisa vai mostrar que o bloco 3 não contém petróleo,
o que fará a empresa comprar outro bloco. Agora a probabilidade de encontrar óleo em
um dos outros blocos é 1/(n-1), então a esperança do lucro é C / (n-1) – C/n = C / n(n1)
1
𝑛
Então o lucro esperado com a informação é ×
𝑛−1 𝐶
𝑛
+
𝑛−1
𝑛
×
𝐶
𝑛 𝑛−1
=𝐶 𝑛
Cálculo do Valor da Informação:
Exemplo

Exemplo:

Suponha que uma empresa de petróleo pretenda comprar o direito de
perfuração de poços de um de n blocos a serem postos à venda. Suponha,
ainda, que exatamente um dos blocos contenha óleo avaliado em $ C, enquanto
os outros não contém nada. O preço de cada bloco é C/n dólares.
 Suponha agora que um geólogo oferece à empresa os resultados de uma
pesquisa referente ao bloco 3, que indica com certeza se o bloco contém óleo.
 Quanto a empresa deve estar disposta a pagar pela informação?

Solução:
Sem a informação, a esperança do lucro ao comprar é 0: 1/n*C – C/n
 A maneira de responder a essa pergunta é examinar o que a empresa faria se
tivesse a informação:

Com probabilidade 1/n, a pesquisa irá indicar que há óleo no bloco 3. Neste caso, a
empresa vai comprar o bloco 3 por C/n e vai faturar C – C / n = (n – 1)C / n
Logo,
se essa informação custar menos que C/n, vale a pena pagar!
 Com probabilidade (n – 1)/n, a pesquisa vai mostrar que o bloco 3 não contém petróleo,
Veja oque
informação
tanto
quanto
preçoacobrado
por um
bloco! óleo em
queafará
a empresavale
comprar
outro
bloco.o Agora
probabilidade
de encontrar
um dos outros blocos é 1/(n-1), então a esperança do lucro é C / (n-1) – C/n = C / n(n1)


1
𝑛
Então o lucro esperado com a informação é ×
𝑛−1 𝐶
𝑛
+
𝑛−1
𝑛
×
𝐶
𝑛 𝑛−1
=𝐶 𝑛
Parte 2: Decisões
Sequenciais
“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:


Utilidade de cada resultado de uma ação conhecido!
Problemas de decisões seqüenciais:

Utilidade do agente depende de uma seqüência de decisões
 Envolvem utilidades, incertezas e percepção
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


Ações não confiáveis




+1
2
-1
1
INÍCIO
Locomoção estocástica
Se agente bater em uma parede permanecerá no mesmo
quadrado
Em cada estado s agente recebe uma Recompensa R(s):


Agente sabe onde está!
3
1
2
3
4
R(s) = -0.04 para todos estados não terminais
Dois estados finais R(s) = +1 ou R(s) = -1
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 a curto prazo 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:


Ações não confiáveis não geram estados deterministicamente
Solução: construir uma Política (Policy):
 (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 *:

Política que produz a mais alta utilidade
esperada
3

2

1

1


+1

-1



2
3
4
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

Utilidade de um estado é dado pela equação de Bellman:

U(s) = R(s) +  maxa s’ T(s,a,s’) U(s’)
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’)
Algoritmo Value Iteration

Algoritmo:
Inicializar utilidades com valores arbitrários (ex.: 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.
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
Value Iteration Applet: http://www.cs.ubc.ca/~poole/demos/mdp/vi.html
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 , 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
Referência Bibliográfica

AIMA, Stuart Russel

Cap. 16 e Cap. 17