Processo de Decisão de Markov

Processo de Decisão de Markov

(Parte 5 de 10)

POMDPs onde o estado de informação é representado desta forma são muitas vezes chamados de POMDPs de crença (belief POMDPs). Em um POMDP com |S| estados, o espaço dos estados de crença é um (|S| − 1)-simplex. Denotaremos estados de crença por b, e quando conveniente b é usado como um vetor, sendo b(s) o s-ésimo elemento do vetor (que é o valor da probabilidade de o sistema estar no estado s).

3.2 Modelos de observação

Em POMDPs, observações estão sempre associadas a estados e ações. Há várias maneiras de definir como esta relação ocorre. Algumas delas são:

• Modelo de observações para a frente (forward triggered): a observação na época de decisão k está relacionada à ação anterior (em k −1) e ao estado resultante (em k). Ou seja, a função de probabilidade de observação poderia ser denotada O(ok|sk,ak−1), se índices fossem usados para indicar as épocas de decisão de o, s e a;

Processos de Decisão de Markov: um tutorial

• Modelo de observações para trás (backward triggered): a observação na época de decisão k depende do estado e da ação na época de decisão k −1. Ou seja, a função de probabilidade de observação poderia ser denotada como O(ok|sk−1,ak−1);

• Modelo de observações com atraso (delayed): uma ação na época de decisão k acarreta uma observação em alguma outra época de decisão k +j (possivelmente várias épocas à frente); a função O poderia ser denotada por O(ok|sk−j,ak−j).

É possível formular problemas como POMDPs de crença para os modelos para trás, para a frente e também para combinações de ambos (onde algumas ações acarretam observações no futuro e outras imediatamente). Para o modelo com atraso, não é possível usar apenas um estado de crença como estatística suficiente para o estado de informação, mas Hauskrecht mostra que para este caso é possível usar o estado de crença e a lista das últimas k observações, onde k é a maior demora possível para uma observação [7].

A escolha do modelo de observação depende do problema sendo modelado, e é possível usar diferentes modelos de observação para diferentes observações no mesmo POMDP. O modelo “para a frente” é usado nas discussões teóricas a seguir.

3.3 POMDPs como MDPs sobre estados de crença

Um POMDP pode ser formulado como um MDP onde o conjunto de estados é o simplex de estados de crença, da seguinte maneira:

(o espaço de estados é infinito);

• As ações A são as mesmas que no POMDP original;

• O estimador de estados de informação τ : B ×A×Ω 7→ B define o próximo estado de crença, dados o estado de crença anterior (b), a última ação (a) e a última observação (o). Se as observações sempre forem causadas pela ação executada na época de decisão imediatamente anterior, e sabemos que o estado de crença atual é b, a última ação executada foi a e a observação resultante foi o, o estimador de estados pode calcular o próximo estado de crença b′ a partir do estado anterior b usando o teorema de Bayes.

Seja ba(s) a probabilidade de o novo estado ser s, dado que a ação a foi executada:

Processos de Decisão de Markov: um tutorial e seja ba(o) a probabilidade de a próxima observação ser o, sendo que a foi executada:

O novo estado de crença b′ é composto pelas probabilidades b′(s):

• A função T′ dá a probabilidade de o sistema passar de um estado de crença b para outro, b′, após executar uma ação a:

onde

0 em caso contrário;

• A função de recompensa ρ é definida para estados de crença, e dá a esperança da recompensa de cada ação, dadas as probabilidades de o sistema estar em cada estado:

A solução para o MDP sobre espaço contínuo de estados (B,A,T′,ρ) é a solução para o POMDP usado para construí-lo [7, 26].

3.4 Política para um POMDP

Da mesma forma que políticas para MDPs, a política para um POMDP pode ou não ser Markoviana, determinística e estacionária.

Uma política para um POMDP de crença pode ser vista como uma política para o MDP sobre estados de informação. A definição 3.3 é de uma política para POMDPs, Markoviana com relação aos estados de informação, mas não-Markoviana com relação aos estados do POMDP como originalmente descrito.

Processos de Decisão de Markov: um tutorial

Definição 3.3 (Política para um POMDP) Dado um POMDP P = (S,A,T,R, Ω,O), uma regra de decisão para P em uma época de decisão k é uma função dk : I 7→ A que determina uma ação, dado um estado de informação para P. Para POMDPs de crença, a regra de decisão pode ser dk : B 7→ A.

É possível definir políticas reativas para POMDPs, onde o tomador de decisões consulta apenas a observação mais recente para escolher a próxima ação (sendo então estritamente Markovianas, uma vez que não dependem do histórico de ações e observações passadas).

Basta que as regras de decisão sejam definidas como funções dk : Ω 7→ A que determinam uma ação, dada uma observação. As políticas reativas podem ter desempenho pior que as políticas que fazem uso do estado de informação. Singh, Jaakkola e Jordan [27] mostraram que políticas reativas determinísticas podem ser arbitrariamente piores que políticas reativas estocásticas. As políticas estritamente Markovianas não serão discutidas neste tutorial.

Os mesmos critérios de otimalidade usados para MDPs podem ser usados para POMDPs, e a definição de política otimal para POMDP é a mesma que para MDPs, exceto por um fato: a política para POMDPs onde deve mapear estados de informação, e não estados, em ações. Similarmente, funções valor são definidas para POMDPs (mapeando estados de informação em valores).

A função valor ótima para um POMDP de crença é única, existe uma política otimal determinística, e para horizonte infinito existe uma política otimal que é estacionária. Isto decorre trivialmente do POMDP ser um MDP sobre estados de crença.

Definição 3.4 (Função valor de uma política para um POMDP) Seja P um POMDP e pi uma política para P. A função valor da política P é um mapeamento V pi : I 7→ R de estados de informação em recompensas esperadas para a política pi, de acordo com o critério de otimalidade escolhido.

As definições de espaço de estados e política otimal para MDPs podem ser usadas para POMDPs, com I (ou B) no lugar de S. Também a função Q é definida para POMDPs como

onde τ é a função de transição para estados de crença (definida na seção 3.3) e ρ(b,a) é a recompensa imediata para uma ação em um estado de crença b, definida na Equação 5 (na página 154).

Enquanto políticas para MDPs podem ser representadas de maneira simples, políticas para POMDPs devem representar o mapeamento de um espaço infinito de estados em ações

Processos de Decisão de Markov: um tutorial

(ou valores). A Definição 3.3 para política é direta e simples, mas a representação usada para a política depende da maneira como estados de informação são representados e dos algoritmos usados para a solução do POMDP. Na discussão a seguir o termo “política” tem seu significado estendido para funções valor, planos condicionais e outras formas de representar o mapeamento de estados de informação em ações.

3.4.1 Representação por hiperplanos Esta é a representação normalmente usada em algoritmos exatos. Mantém-se um conjunto de vetores associado a cada ação, onde cada vetor define um hiperplano, dando a recompensa esperada para aquela ação, dado o estado de crença (ou seja, mantém-se uma função valor). Cada vetor, quando multiplicado por um estado de crença b, dará a recompensa esperada desde que a ação associada a ele seja tomada e uma política otimal seja seguida até a última época de decisão. Este conjunto de hiperplanos é normalmente denotado por Γ. Neste tutorial usaremos Γ para denotar um vetor de conjun- tos, sendo que Γi é a política da i-ésima época de decisão. Quando a política for estacionária, todos os Γi serão iguais.

A representação por hiperplanos só é possível devido a um fato demonstrado por Sondik [28]: a função valor ótima para um POMDP com horizonte finito é formada por segmentos de hiperplanos, conforme o Teorema 3.1.

Definição 3.5 (PWLC) Uma função valor V (que pode ser descrita por um conjunto Γ de vetores) é PWLC (“piecewise convex and linear”, ou “convexa e composta de segmentos de hiperplanos”) se pode ser calculada como

Teorema 3.1 (da forma das funções valor para POMDPs) A função valor ótima em qualquer época de decisão para um POMDP de horizonte finito é PWLC.

A Figura 3 mostra um exemplo de política usando esta representação. Nesta figura, o

Cada hiperplano representa o valor esperado para uma ação; o trecho onde um hiperplano domina todos os outros é aquele onde a ação representada por ele é otimal. Na figura,

Para determinar uma ação otimal dado um estado de crença b, basta escolher o vetor α

Processos de Decisão de Markov: um tutorial

Figura 3. Política para POMDP representada como conjunto de hiperplanos.

que, multiplicado por b, dá o maior valor:

Para horizonte infinito, a função valor ótima pode não ser da forma descrita por Sondik, mas é aproximável por uma política desta forma.

3.4.2 Representação por discretização O simplex do espaço dos estados de crença pode ser discretizado e mapeado em ações [29–31]. Esta técnica é utilizada com algoritmos de aprendizado, e claramente leva a uma solução não-exata. A grade obtida pela discretização pode ter granularidade e regularidade diferentes dependendo do algoritmo. Alguns destes algoritmos são apresentados na subseção 3.5.4.

3.4.3 Representação por planos condicionais Um plano condicional [32] é uma estrutura recursiva que pode ser usada para representar políticas para POMDPs. Um plano condicional é composto de:

(Parte 5 de 10)

Comentários