Teoria da Decisão
Métodos de Computação Inteligente
Universidade Federal de Pernambuco
Centro de Informática – Cin
Maria Uilma Rodrigues dos Santos de Sousa
Sandra Wanderley Lubambo
Roteiro da apresentação
Teoria da Decisão – conceitos básicos
Decisões Simples
Princípio da Utilidade Máxima Esperada (UME)
Função Utilidade
Função Utilidade Multiatributo
Redes de Decisão
Valor da Informação
Sistemas Especialistas
Decisões Complexas
Processo Decisão de Markov (MDP)
Algoritmo de Iteração de Valor
Algoritmo de Iteração de Política
MDP em ambiente Parcialmente Observável
Agente de teoria da decisão
Roteiro da apresentação
Teoria da Decisão – conceitos básicos
Decisões Simples
Princípio da Utilidade Máxima Esperada (UME)
Função Utilidade
Função Utilidade Multiatributo
Redes de Decisão
Valor da Informação
Sistemas Especialistas
Decisões Complexas
Processo Decisão de Markov (MDP)
Algoritmo de Iteração de Valor
Algoritmo de Iteração de Política
MDP em ambiente Parcialmente Observável
Agente de teoria da decisão
Teoria da decisão – conceitos básicos
A combinação da Teoria da Probabilidade com a Teoria da Utilidade permite
ao agente escolher a ação que maximiza seu desempenho esperado.
Teoria da
probabilidade
Descreve aquilo que
um agente deve
acreditar com base
nas evidências
Teoria da
utilidade
Descreve o que um
agente deseja
Teoria da
Decisão
Descreve o que
um agente deve
fazer
A teoria da decisão pode ser usada para construir um agente que toma decisões
considerando todas as ações possíveis e escolhendo aquela que leva ao melhor resultado
esperado. Tal agente é denominado Agente racional.
Teoria da decisão – conceitos básicos
O agente da teoria da decisão pode tomar decisões racionais baseadas em
suas crenças e no que ele deseja em contextos nos quais a incerteza e
objetivos conflitantes deixam um agente lógico sem meios para decidir;
Um agente lógico faz distinção binária entre estados bons (objetivos) e
estados ruins (não-objetivos), enquanto um agente de teoria da decisão tem
uma medida contínua da qualidade do estado;
Em resumo:
O princípio básico da teoria da decisão é a maximização da utilidade
esperada (UME).
Roteiro da apresentação
Teoria da Decisão – conceitos básicos
Decisões Simples
Princípio da Utilidade Máxima Esperada (UME)
Função Utilidade
Função Utilidade Multiatributo
Redes de Decisão
Valor da Informação
Sistemas Especialistas
Decisões Complexas
Processo Decisão de Markov (MDP)
Algoritmo de Iteração de Valor
Algoritmo de Iteração de Política
MDP em ambiente Parcialmente Observável
Agente de teoria da decisão
Decisões Simples
“Como um agente deve tomar
decisões de modo que, em média, ele
consiga o que quer”
Princípio da
(1/2)
Utilidade Máxima Esperada (UME)
No texto Port-Royal Logic, escrito em 1662, o filósofo francês Arnauld
declarou:
Para julgar o que se deve fazer para obter um bem ou evitar um mal, é
necessário considerar não apenas o bem e o mal em si, mas também a
probabilidade de ele acontecer ou não acontecer, e ainda visualizar
geometricamente a proporção que todos esses itens têm em conjunto.
(grifo nosso)
Pág. 566, AIMA- 2ª ed. – (Português).
Princípio da
(2/2)
Utilidade Máxima Esperada (UME)
afirma que um agente racional deve escolher uma ação que
maximize a utilidade esperada do agente;
se relaciona com a idéia de medida de desempenho;
é um modo razoável de tomar decisões.
ou seja:
O agente usa um modelo do mundo junto com a função
utilidade (que mede suas preferências entre os estados do
mundo), em seguida escolhe a ação que leva à melhor utilidade
esperada.
Função utilidade
(1/2)
• Capta as preferências de um agente entre estados de mundo e atribui
um único número para expressar a desejabilidade de um estado;
Função de Utilidade:
 associa um valor a um estado;
 indica o “desejo” por estar nesse estado;
As utilidades são combinadas com probabilidades de resultados de
ação para fornecer uma Utilidade Esperada (EU).
Função Utilidade
(2/2)
A Utilidade Esperada (EU) da ação A dada a evidência E é calculada usando
a fórmula:
EU(A|E) = i P(Resultadoi(A)|Fazer(A),E) * U(Resultadoi(A))
onde,
E = evidências disponíveis;
Fazer(A) = proposição de execução da ação A;
Resultadoi(A) = estados possíveis de saída da ação A;
P = probabilidade para cada saída possível;
U = é a utilidade de cada estado.
Preferências Racionais
(1/4)
As preferências do agente são descritas utilizando as notações a seguir:
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
Em ambientes deterministas: A e B são estados resultantes concretos e totalmente
especificados;
Em ambientes 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” da loteria).
Preferências Racionais
(2/4)
Uma loteria L com resultados possíveis C1,...,Cn que pode
ocorrer com as probabilidades p1,...pn é descrita como:
L = (p1.C1; p2. C2; ...; pn.Cn)
A principal questão para a teoria da utilidade é
compreender como as preferências entre loterias complexas
estão relacionadas a preferências entre estados subjacentes
nessas loterias;
Para fazer isso, impomos restrições razoáveis sobre a
relação de preferências.
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)
– Continuidade:
A > B > C  p [p,A; 1 – p,C] ~ B
(3/4)
Preferências que satisfaçam os axiomas
garantem a existência de uma função
valores reais U, tal que:
– U(A) > U(B)  A > B
– U(A) = U(B)  A ~ B
– U (p1.S1; ... ; pn.Sn) = i pi U(Si)
– Substitutibilidade:
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] )
– Decomponibilidade:
[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
(4/4)
Exemplo:
Supondo um agente com preferências não transitivas (A > B > C >A) , onde A, B e C são
bens que podem ser livremente trocados. O agente possui o bem A e recebe uma proposta
para trocar C por A oferecendo, quantia em dinheiro pela troca.
Se C > A, então um agente que possui A pagaria 1 centavo para obter C
Se B > C, então um agente que possui C pagaria 1 centavo para obter B
Se A > B, então um agente que possui B pagaria 1 centavo para obter A
Conclusão: Violação das restrições levam a comportamentos irracionais.
Exemplo:
A Utilidade do Dinheiro (1/2)
Um jogador ganhou um prêmio de R$ 1.000.000 em um programa de TV;
Apresentador oferece uma proposta:
– Se ele jogar a moeda e aparecer cara  jogador perde tudo;
– Se aparecer coroa  jogador ganha R$ 3.000.000;
Supondo que a moeda é justa o Valor Monetário Esperado (VME) de aceitar
proposta é:
VME = 0.5 (R$ 0) + 0.5 (R$ 3.000.000) = R$ 1.500.000;
O Valor Monetário Esperado de recusar a proposta é de R$ 1.000.000 (menor);
Isso indica que seria melhor aceitar a aposta ?
Exemplo:
A Utilidade do Dinheiro (1/2)
A Utilidade Esperada (EU) para cada uma das duas ações, Sk = riqueza atual do
jogador é:
– EU (Aceitar) = 0.5 U(Sk) + 0.5 U(Sk+3.000.000)
– EU (Rejeitar) = U(Sk+1.000.000)
Ação racional: rejeitar !
Calculando a Utilidade Esperada (EU) para cada uma das duas ações temos que a
decisão depende do estado de riqueza atual do jogador, uma vez que a utilidade
(mudança no estilo de vida) para o primeiro R$ 1.000.000 é muito alta.
Conclusão: a utilidade não é diretamente proporcional ao valor monetário;
Funções de Utilidade Multiatributo
Existem problemas em que resultados são caracterizados por dois ou mais
atributos.
Como tratar funções de utilidades com várias variáveis X1, ..., Xn ?
Ex.: Construir aeroporto - U(Morte, 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 Multiatributo);
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;
Exemplo:
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 , vamos supor :
– 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  Isso não decorre da comparação entre custos
esperados
P
S1
S2
$
-5.2
- 2,8
Dominância Estocástica
Na prática, dominância estocástica pode geralmente ser definida usando
apenas um raciocínio qualitativo;
Existem algoritmos envolvendo “redes probabilísticas qualitativas” permitindo
sistemas de tomada de decisão baseado em dominância estocástica sem
usar valor;
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 Multiatributo
Supondo que existem n atributos com d possíveis valores:
– No pior caso, serão necessários dn valores para especificar a função de utilidade
completa;
A Teoria da Utilidade Multiatributo assume que preferências de agentes
possuem certa regularidade (estrutura);
- A abordagem básica é identificar regularidades no comportamento de preferências;
- Tenta mostrar que um agente com certo tipo de estrutura de preferências possui uma
função de utilidade do tipo:
U(x1 ... Xn) = f[ f1(x1) ..... fn (xn) ]
Onde f seja uma função o mais simples possível
Estrutura de Preferência:
Determinista
A regularidade básica que surge em estruturas de preferências
determinísticas é chamada Independência de Preferências;
X1 e X2 são preferencialmente independente de X3 :
– Se a Preferência entre resultados {x1, x2, x3} e {x1’, x2’, x3} não depende
do valor específico x3 para o atributo X3
– Ex.: {barulho, custo, morte}
{20.000 sofrem; $4,6 bilhões; 0,06 mortes/mhm} vs. {70.000 sofrem; $4,2
bilhões; 0,06 mortes/mhm}
Estrutura de Preferência:
Determinista
Independência preferencial mútua (MPI): todos os pares de atributos são
preferencialmente independente com relação aos demais;
– Ex.: {custo e morte} são preferencialmente independente de barulho
{barulho e morte} são preferencialmente independente de custo
(Debreu, 1960) Com MPI, o comportamento preferencial do agente pode ser
descrito como uma maximização da função:
V (x1 ... xn) = i Vi(xi)
– Ex.: V(barulho,custo,morte ) = - barulho x 10⁴ - custo - morte x 10¹²
Estrutura de Preferência:
Estocástica
Deve-se levar em consideração preferências sobre loterias;
( distribuição de probabilidades sobre um conjunto de resultados reais )
Conjunto de atributo X é independente de utilidade com relação ao conjunto de atributo Y :
– Se a preferência sobre loterias em X não dependem dos valores dos atributos em Y
Independência de utilidade mútua (MUI)
Um conjuto de atributos é mutuamente indepentente da utilidade :
- Se cada um dos seus subconjuntos de atributos é independente de
utilidade dos atributos restantes;
(Keeney, 1974 ) Existe MUI então, comportamento do agente pode ser descrito usando a
função:
U = k1U1 + k2U2 + k3U3 + k1 k2U1U2 + k2 k3U2U3 + k3 k1U3U1 + k1k2k3U1U2U3
Estrutura de Preferência:
Estocástica
(Keeney, 1974 ) Existe MUI então, comportamento do agente pode ser
descrito usando a função:
U = k1U1 + k2U2 + k3U3 + k1 k2U1U2 + k2 k3U2U3 + k3 k1U3U1 + k1k2k3U1U2U3
Em geral, um problema de “n” atributos que exibe MUI pode ser modelado
com a utilização de “n” utilidades de um único atributo e “n” constantes
Cada uma das funções utilidades de único atributo pode ser desenvolvida
independente e a combinação oferecerá a garantia de gerar preferências
globais corretas.
Redes de Decisões
Mecanismo geral para tomada de decisões
racionais
Representam : Estado atual do agente,
suas ações possíveis, estado resultante, e
a utilidade desse estado;
Extende Redes Bayesianas com ações e
utilidades;
– Nós de acaso (ovais): representam
variáveis aleatórias;
– 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;
As ações são selecionadas pela avaliação
da rede
Redes de Decisões
Descrição da
Utilidade do
Agente
ou
V (x1 ... xn) = i Vi(xi)
Área A
Área B
Nível de Tráfego
Aéreo
Nível de Tráfego
Aéreo
Potencial para
Litígio
Potencial para
Litígio
U
F(u)=Y
F(u)=X
Custo da
Construção
U
Custo da
Construção
U= k1U1 + k2U2 + k3U3 + k1 k2U1U2 + k2 k3U2U3 + k3 k1U3U1 + k1k2k3U1U2U3
EU(A|E) = i P(Resultado(A)|Fazer(A),E) * U(Resultado(A))
(Tabela de ação-utilidade)
(versão simplificada )
Redes de Decisões
Aplicação do 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 para cada valor possível do nó
de decisão;
3. Retornar a ação com maior Utilidade
Máxima Esperada
Área B
Área A
Morte
(3)
Morte
(3)
Barulho
(2)
Barulho
(4000)
Custo da
Construção
(200)
U
F(u)=X
f.utilidade = - barulho x 10⁴
10 - custo - morte x 10¹²
morte barulho custo f. utilidade
area A
3
2
200
-3.000.000.020.200
area B
3
4000
150
-3.000.040.000.150

Custo da
Construção
(150)
U
F(u)=Y
Onde: X > Y
Retorna : AREA A
Teoria do Valor da Informação
Até agora, informações fornecidas ao agente antes da tomada de decisão;
A Teoria do Valor da Informação permite que o agente escolha quais informações adquirir;
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 =
A informação é tão valiosa
= (0,5 x C/2) + (0,5 x C/2) – 0 = C/2
quanto o próprio bloco
Valor da Informação:
Exemplo
A1 e A2 duas rotas distintas através de uma montanha;
– A1 e A2 são as únicas ações possíveis, com EU U1 e U2;
– 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 ela gere uma mudança de plano, e se esse
novo plano for significante melhor do que o antigo !
Sistemas Especialistas
No campo da Análise de Decisões temos a aplicação da Teoria da Decisão a
problemas reais (principalmente envolvendo altos riscos);
No início os Sistemas Especialistas concentravam-se em responder
perguntas e não em tomadas de decisão;
Hoje temos que os Sistemas Especialistas envolvem um Processo de
Engenharia do Conhecimento com etapas definidas e que fornecem as
seguintes capacidades:
– tomar decisões;
– usar valor da informação para decidir se deve adquirir;
– calcular a sensibilidade de suas decisões.
Sistemas Especialistas
Um exemplo:
( Selecionar
tratamento médico
para doença do
coração em
crianças )
Etapas do processo de Engenharia do Conhecimento
Crie um Modelo
1) Determinar ( sintomas, doenças,
Causal
tratamentos e resultados ); 2)
Desenhar arcos ( que doenças
causam cada sintoma ); 3) Desenhar
arcos ( que tratamentos aliviam os
sintomas de cada doença)
Simplifique até chegar Remover variáveis não estão
a um modelo de
envolvidas em decisões de tratamento
decisão qualitativa
Atribua Probabilidades 1) Pode vir de Banco de Dados de
Pacientes; 2) Estudos de Literatura; 3)
Avaliação de Especialistas
Atribua Utilidade
Criar escala do melhor ao pior
resultado: Recuperação Completa = 0
e Morte = -1000
Verifique e Refine o
Necessita conjunto de pares (entrada ,
modelo
saída) --> ( sintomas, solicitar
tratamento )
Execute a análise de
sensibilidade
Verifica se a melhor decisão é
sensível a pequenas mudanças nas
probabilidades e utilidades atribuídas
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
Onde a utilidade do agente depende de uma seqüência de decisões;
Exemplo: (que explica como os problemas de decisão seqüenciais são definidos)
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: Acima, Abaixo, Esquerda e Direita;
Ambiente totalmente observável;
Ações não confiáveis (locomoção estocástica);
Processo de Decisão Markoviana (MDP)
É a especificação de um problema de decisão seqüencial para ambiente TO 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)
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 é a soma das recompensas recebidas;
– Exemplo:
Se Agente alcançar +1 em “10” passos
Teremos ( 1 - ( 0,04 x 10 ) ) Então a U = 0,6
Processo de Decisão Markoviana (MDP)
EXEMPLO
Problema
Agente
jogador de
damas
Agente em
jogo de
luta
Estados
Configuraçõ
es do
tabuleiro
Posições /
energia dos
lutadores,
tempo, se
está sendo
atacado ou
não etc...
Agente
Posição no
patrulhador mapa (atual
e passada)
Ações
Mover uma
determinada
peça
Mover-se em
uma
determinada
direção,
lançar, magia,
bater etc..
Recompensas
Capturas Perdas
Ir para algum
lugar vizinho
do mapa
Ociosidade
(tempo sem
visitas) do lugar
visitado
atualmente
(sangue tirado sangue
perdido)
A manutenção de um equilíbrio cuidadoso entre Risco e Recompensa é uma das
características dos MDP’s
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:  (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
Soma das recompensas é uma escolha para medida de desempenho do
agente;
Outras escolhas possíveis podem ser escritas por:
Uh ([s0, s1, ... , sn])
Como definir funções de utilidades para problemas seqüenciais?
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 ?
Funções de Utilidade para
Problemas Seqüenciais
O Horizonte Temporal para a tomada de decisão é Finito ou
Infinito ?
Exemplo.:
– Supondo que o agente inicia em (3,1)
– N = 3  para atingir +1 agente deve executar ação Acima
– N = 100  tempo suficiente para executar ação Esquerda
(rota mais segura)
Funções de Utilidade para
Problemas Seqüenciais
Como calcular a utilidade de uma seqüência de estados ?
Pode ser visualizado como uma questão de Teoria da
Utilidade Multiatributo
onde: Cada “si“ é visualizado como um atributo da
seqüência de estados [so,s 1,...,s n]
Baseado no princípio 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 de
Iteração de Valor
(1/3)
A idéia básica do algorítmo é: calcular a utilidade de cada estado e
depois empregar as utilidades de estados para selecionar uma ação ótima;
Proposto para calcular uma política ótima;
A Utilidade de cada estado é definida em termos da utilidade das
seqüências de ações que podem se seguir a partir dele;
Equações de Bellman (1957) são a base do algoritmo de Iteração de valor
para resolver MDPs;
Se houver n estados possíveis, então haverá n equações de Bellman, uma
para cada estado.
Algoritmo de
Iteração de Valor
(2/3)
Utilidade de um estado, dada pela equação de Bellman,é a
recompensa imediata correspondente a este estado R(s),
somada à utilidade descontada esperada do próximo estado,
supondo que o agente escolha a ação ótima.
U(s) = R(s),+  maxa s’ T(s,a,s’) U(s’)
Algoritmo:
1.
2.
3.
4.
Inicializar utilidades com valores iniciais arbitrários
(tipicamente 0);
Calcular o lado direito da equação para cada estado;
Atualizar valor da utilidade de cada estado;
Continuar até convergir para um único conjunto de
soluções
Algoritmo de
Iteração de Valor
(3/3)
Exemplo: U(1,1) = -0.04 +  max
(Acima) {
(Esquerda)
(Abaixo)
(Direita)
0.8 U(1,2) + 0.1 U(2,1) + 0.1 U(1,1),
0.9 U(1,1) + 0,1 U(1,2),
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) }
•Utilidades dos estados no mundo 4 x 3,
calculadas com y = 1 e R(s)= -0,04 para
estados não terminais.
•Note que: as utilidades são mais altas para
estados mais próximos à saída, porque são
necessários menos passos para alcançar a
saída.
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
Algoritmo de
Iteração de política
(1/2)
A idéia básica do algorítmo é: se uma ação é claramente melhor que todas as
outras, então a magnitude exata das utilidades nos estados envolvidos não precisa
ser exata;
Essa idéia sugere um caminho alternativo para encontrar políticas ótimas;
O algoritmo alterna entre as duas etapas a seguir, iniciando a partir de uma política
inicial 0:
1. Avaliação da Política: dada política i , calcular Ui = U  i , se  i tivesse de ser executada;
2. Aperfeiçoamento da Política: calcular nova política UMEi+1, utilizando a observação
antecipada de um passo baseada em Ui.
Algoritmo encerra quando o passo Melhora da Política não produz nenhuma mudança
nas utilidades;
Algoritmo de
Iteração de política
(2/2)
Equação de Bellman para avaliar a utilidade de um estado:
Ui(s) = R(s) +  s’ T(s, i(s), s’) Ui(s’)
Exemplo:
Supondo que i seja a política mostrada na figura ao lado. Então, para os
estados (1,1) e (1,2), temos i(1,1) = Acima, i(1,2) = Acima, conforme
demonstrado e, assim por diante:
Ui (1,1) = 0.8 Ui(1,2) + 0.1 Ui(1,1) + 0.1 Ui(2,1)



3
Ui (1,2) = 0.8 Ui(1,3) + 0.2 Ui(1,2) ,
.
.
.
2

1

1
+1

-1



2
3
4
MDPs Parcialmente Observáveis
(POMDPs)
(1/3)
Os MDPs assumem que o ambiente é totalmente observável e a política ótima
depende apenas estado atual;
Em ambientes parcialmente observáveis o agente não sabe necessariamente onde ele
está, portanto:
• Não pode executar a ação (s) recomendada para esse estado;
• A utilidade de um estado s e a ação ótima no s depende não só de s, mas também
do quanto o agente sabe quando está em s;
Por esta razão:
• MDPs em ambientes parcialmente observáveis (POMDPs) em geral são
muito mais difíceis;
• Não podemos evitá-los o mundo real é um deles.
MDPs Parcialmente Observáveis
(POMDPs)
(2/3)
Os POMDPs possuem os mesmo elementos de um MDPs acrescentando apenas:
• O Modelo de Observação: O(s, o), o qual especifica a probabilidade de perceber
a observação o no estado s;
Estado de crença = conjunto de estados reais em que o agente pode estar.
Em POMDPs um estado de crença b, é uma distribuição probabilística sobre todos
os estados possíveis:
• Exemplo:
Para o mundo 4 x 3 o estado de crença inicial poderia ser descrito como:
{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 atribuída ao estado s pelo estado de crença b;
MDPs Parcialmente Observáveis
(POMDPs)
(3/3)
Em POMDPs:
Uma ação altera tanto o estado físico quanto o estado de crença;
O valor da informação é incluído como componente do processo de
decisão;
A ação ótima depende apenas do estado de crença atual do agente, ou
seja, não depende do estado real em que ele se encontra;
Roteiro da apresentação
Teoria da Decisão – conceitos básicos
Decisões Simples
Princípio da Utilidade Máxima Esperada (UME)
Função Utilidade
Função Utilidade Multiatributo
Redes de Decisão
Valor da Informação
Sistemas Especialistas
Decisões Complexas
Processo Decisão de Markov (MDP)
Algoritmo de Iteração de Valor
Algoritmo de Iteração de Política
MDP em ambiente Parcialmente Observável
Agente de teoria da decisão
Agente de teoria da decisão (1/2)
Agente da Teoria da decisão:
• Pode tomar decisões racionais baseado no que acredita e deseja;
• É capaz de tomar decisões em ambientes onde incertezas e objetivos conflitantes
deixariam um agente lógico sem poder decidir;
• Possui uma escala contínua de medida de qualidade sobre os estados;
Pode ser construído para um ambiente POMDP usando Redes de Decisões
Dinâmicas para:
• Representar os modelos de Transição e Observação;
• Atualizar o Estado de crença;
• Projetar possíveis seqüências de ações;
Decisões são tomadas projetando para frente possíveis seqüências de ações e
escolhendo a melhor;
Agente da teoria da decisão (2/2)
Sensores
Interpretador de percepções
Regras: percepção(t)  modelo(t-1)  modelo(t)
Modelo dos
ambientes
(passados)
e atual
Atualizador do modelo do ambiente
Regras: modelo(t)  modelo(t)
Ambiente
Atualizador dos objetivos
Regras: modelo(t)  objetivos(t-1)  objetivos(t)
Utilidades
Objetivos
u:modelos x objetivos  R
Escolhedor de ação
Atuadores
faz(argmax
ação1
i
 U(resultado([ ação  ação ]) | objeti vos(t))
i
i
i
1
n
Iteração de Valor
(diagrama de classe)
MDP
Estados
FuncaoUtilidade : utilidade
FuncaoRecompensa :
recompensa
Iteração Valor
Utilidade ( estado: estado,
maxerror: Int ) : utilidade
Gama : desconto
Delta : int
Transição
Probabilidade () : probabilidade
Ação
Iteração de Política
(diagrama de classe)
MDP
Estados
FuncaoUtilidade : utilidade
Iteração Valor
Política ( estado: estado ) :
política
Pi : política
Transição
Probabilidade () : probabilidade
Ação