Agentes Baseados em Agentes Baseados em UtilidadeUtilidade

Parte I: Decisões Parte I: Decisões SimplesSimples

“Como um agente deve tomar decisões de modo que, em média, ele consiga o que quer”

Decision Theoretic AgentDecision 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 UtilidadeFunções 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 é 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 !!! É difícil enumerar todas seqüências de ações Custo computacional, geralmente, proibitivo

Exemplo: Cálculo da Utilidade Exemplo: Cálculo da Utilidade EsperadaEsperada

Robô deve transportar uma caixaE = 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, balde no destino 80% U(s1) = 10

s2, balde na origem 20% U(s2) = 0

EU(a1) = 20x10 + 30x5 + 50x0 = 350

EU(a2 ) = 80x10 + 20x0 = 800

Preferências RacionaisPreferências Racionais 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 Restrições Sobre Preferências RacionaisRacionais

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

Substituibilidade: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]

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)

Exemplo: Restrições Sobre Exemplo: Restrições Sobre Preferências RacionaisPreferê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:

CC BB1 c

CC BB1 c AA1 c

CC BB1 c AA1 c

Se B > C, então um agente que possuí C pagaria 1 centavo para obter B

Se C > A, então um agente que possuí A pagaria 1 centavo para obter C

Se A > B, então um agente que possuí B pagaria 1 centavo para obter A

Exemplo: A Utilidade do DinheiroExemplo: 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 DinheiroExemplo: 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-AtributoFunçõ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 EstritaDominância Estrita Se um estado S1 possui valores melhores em todos seus atributos do

que S2, então existe uma dominância estrita 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 estrita raramente acontece na prática !!!

Dominância EstocásticaDominância Estocástica

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

$- 2,8-5.2

P

S1

S2

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

Dada a informação que utilidade decresce com custo:

S1 domina estocasticamente S2

EU de S1 é pelo menos tão alta quanto EU de S2

Estrutura de Preferência e Utilidade Estrutura de Preferência e Utilidade Multi-AtributoMulti-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) 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 Estrutura de Preferência (Situação Determinista) (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 de x3

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: V (x1 ... xn) = i Vi(xi) Para o exemplo acima: V(poluição sonora, custo, mortes) = -poluição sonora

x 104 –custo – mortes x 1012

Para o caso não determinista, basta estender para lidar com loterias

Redes de DecisõesRedes 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: 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

Exemplo: Redes de DecisõesExemplo: Redes de Decisões

Barulho

Segurança

Custo

Trafego aéreo

Construção

Litigação

Local do Aeroporto

U

Info. sobre estado atual Info. sobre

estado futuro

Teoria do Valor da InformaçãoTeoria 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: Cálculo do Valor da Informação: ExemploExemplo

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: ExemploValor 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

U (A1) > U (A2)

Nova evidência NE produzirá novas utilidades esperadas U1’ e U2’ 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 !

Parte 2: Decisões Parte 2: Decisões ComplexasComplexas

“Métodos para decidir o que fazer hoje, dado que nós poderemos ter que decidir de novo amanhã”

Problemas de Decisões SeqüenciaisProblemas de Decisões Seqüenciais Anteriormente estávamos lidando 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

Podem ser vistos como uma generalização do problema de planejamento

Exemplo: Problemas de Decisões Exemplo: Problemas de Decisões SeqüenciaisSeqüenciais

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) 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

Por enquanto, utilidade pode ser dada pela soma das recompensas recebidas!

1 2 43

3

2

1 INÍCIO

-1

+1

0.8

0.1 0.1

Processo de Decisão Markoviana (MDP)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

MDP: Especificação de um problema de decisão seqüencial em um ambiente totalmente observável, modelo de transição markoviana e recompensas aditivas

Como são as soluções para esse Como são as soluções para esse problema?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

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 Notação: *

1 2 43

3

2

1

-1

+1

Funções de Utilidade para Problemas Funções de Utilidade para Problemas SeqüenciaisSeqü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 InfinitosHorizontes 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: Ação ótima depende apenas do estado atual Política ótima é estacionária

1 2 43

3

2

1 INÍCIO

-1

+1

Cálculo de Utilidade para Seqüência de Cálculo de Utilidade para Seqüência de EstadosEstados

Com o que Uh ([s0, s1, ... , sn]) se parece ? Função de utilidade com vários atributos !

Deve-se supor que preferências entre seqüências de estados são estacionárias 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 no principio estacionariedade, existem apenas duas maneiras de atribuir utilidades a seqüências de estados: Recompensas aditivas Recompensas descontadas

RecompensasRecompensas 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 IterationAlgoritmo 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 IterationAlgoritmo Value Iteration Exemplo:

U(1,1) = -0.04 + max { 0.8 U(1,2) + 0.1 U(2,1) + 0.1 U(1,1), (Up) 0.9 U(1,1) + 0,1 U(2,1), (Left) 0.9 U(1,1) + 0.1 U(2,1), (Down) 0.8 U(2,1) + 0.1 U(1,2) + 0.1 U(1,1) } (Right)

Equações de Bellman são a base do algoritmo Value Iteration para resolver MDPs N estados = N equações

Algoritmo:1. Inicializar utilidades com valores arbitrários (ex.: 0)2. Calcular o lado direito da equação para cada estado3. Atualizar valor da utilidade de cada estado4. Continuar até atingir um equilíbrio

1 2 43

3

2

1

0.812

0.762

0.705

0.812 0.918

0.660 -1

+1

0.655 0.611 0.388

Algoritmo Policy IterationAlgoritmo 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 , utilizando um passo para frente baseado em Ui

Para cada estado sse ( 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 IterationAlgoritmo 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)

1 2 43

3

2

1

-1

+1

MDPs Parcialmente Observáveis MDPs Parcialmente Observáveis (POMDPs)(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

1 2 43

3

2

1

-1

+1

start

MDPs Parcialmente Observáveis MDPs Parcialmente Observáveis (POMDPs)(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 MDPs Parcialmente Observáveis (POMDPs)(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 o3. Atualize o Belief State corrente usando FORWARD (b, a, o)

Decisões com Múltiplos Agentes: Decisões com Múltiplos Agentes: Teoria dos JogosTeoria dos Jogos

O que acontece quando a incerteza é proveniente de outros agentes e de suas decisões? E se as essas decissões são influenciadas pelas nossas? A Teoria dos Jogos trata essas questões ! TJ usada para tomar decisões sérias (decisões de preço, desenvolvimento de

defesa nacional, etc)

Na Teoria fos Jogos, 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

Teoria dos Jogos: Exemplo 1Teoria dos Jogos: Exemplo 1

Dois ladrões (Alice e Bob) são presos perto da cena do crime e interrogados separadamente

Matriz de resultados:

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

Alice: testemunhar Alice: recusarBob: testemunhar A = -5; B = -5 A = -10; B = 0

Bob: recusar A = 0; B = -10 A = -1; B = -1

Teoria dos Jogos: Exemplo 1Teoria dos Jogos: Exemplo 1

Equilíbrio de Estratégia Dominante: Situação onde cada jogador possui uma 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: 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 NashEquilí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 John Nash provou que todo jogo possui um equilíbrio como 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

Exemplo:

Dois equilibrios de Nash: {dvd, dvd} e {cd, cd}

Acme: DVD Acme: CDBest: DVD A = 9; B = 9 A = -4; B = -1

Best: CD A = -3; B = -1 A = 5; B = 5