POMDP (Processo de Decisão de Markov Parcialmente Observável)

Motivação: por que POMDPs existem

Um Processo de Decisão de Markov Parcialmente Observável (Partially Observable Markov Decision Process, POMDP) é uma estrutura matemática para tomada de decisão sequencial quando o agente não consegue observar diretamente o verdadeiro estado do ambiente. Em vez disso, o agente recebe observações ruidosas ou incompletas e deve agir sob incerteza sobre o que realmente está acontecendo.

Muitos sistemas reais são parcialmente observáveis:

Os sensores de um robô são ruidosos e têm pontos cegos.
Um sistema médico não observa diretamente o verdadeiro estado de saúde do paciente, apenas resultados de exames.
Um agente de diálogo não consegue observar diretamente a intenção do usuário, apenas enunciados.
Um veículo autônomo não consegue observar perfeitamente os objetivos e a atenção de outros motoristas.

POMDPs generalizam o Processo de Decisão de Markov (MDP): um MDP assume que o estado atual é totalmente observável; um POMDP assume que ele é oculto.

Definição formal

Uma definição comum de um POMDP é a tupla:

[ \mathcal{P} = (S, A, T, R, \Omega, O, \gamma) ]

onde:

(S): conjunto de estados (ocultos), por exemplo, “porta está trancada/destrancada”
(A): conjunto de ações, por exemplo, “empurrar a porta”, “usar a chave”, “olhar a fechadura”
(T(s' \mid s, a)): modelo de transição (dinâmica), a probabilidade do próximo estado (s') dado o estado atual (s) e a ação (a)
(R(s, a)) (ou (R(s,a,s'))): modelo de recompensa
(\Omega): conjunto de observações, por exemplo, “som de clique”, “sem clique”
(O(o \mid s', a)): modelo de observação, probabilidade de observar (o) após executar a ação (a) e chegar ao estado (s')
(\gamma \in [0,1)): fator de desconto

Loop de interação (conceitualmente):

O estado oculto é (s_t) (o agente não o vê diretamente)
O agente escolhe a ação (a_t)
O ambiente transiciona: (s_{t+1} \sim T(\cdot \mid s_t, a_t))
O agente recebe a observação: (o_{t+1} \sim O(\cdot \mid s_{t+1}, a_t))
O agente recebe a recompensa (r_t = R(s_t, a_t)) (ou uma variante)

A principal diferença em relação a um MDP é que a entrada do agente é (o_t), não (s_t).

Estados de crença: transformando estado oculto em um “estado” computável

Como o estado é oculto, o agente mantém um estado de crença (belief state):

[ b_t(s) = P(s_t = s \mid \text{histórico até o tempo } t) ]

Isso é uma distribuição de probabilidade sobre todos os estados possíveis. Sob suposições padrão (dinâmica markoviana e independência condicional das observações), a crença é uma estatística suficiente (sufficient statistic) do histórico completo: você não precisa lembrar toda a sequência observação-ação se acompanhar (b_t).

Atualização bayesiana da crença (Bayes belief update) (filtragem)

Dada a crença atual (b), a ação (a) e a nova observação (o), a crença atualizada (b') é:

[ b'(s') = \eta , O(o \mid s', a)\sum_{s \in S} T(s' \mid s, a), b(s) ]

onde (\eta) é uma constante de normalização para que (\sum_{s'} b'(s') = 1).

Intuição:

Primeiro “prediga” as probabilidades do próximo estado usando a dinâmica (T)
Depois “corrija” usando a verossimilhança da observação (O)

Pseudocódigo para atualização de crença

def belief_update(b, a, o, T, O):
    # b: dict state->prob, or vector
    # T[s][a][s2] = P(s2|s,a)
    # O[s2][a][o] = P(o|s2,a)
    b_pred = {s2: 0.0 for s2 in b}
    for s, p in b.items():
        for s2, p_trans in T[s][a].items():
            b_pred[s2] += p * p_trans

    b_post = {s2: O[s2][a][o] * p for s2, p in b_pred.items()}
    Z = sum(b_post.values())
    return {s2: p / Z for s2, p in b_post.items()}

Em espaços de estados contínuos ou de alta dimensionalidade, atualizações exatas de crença podem ser substituídas por filtragem bayesiana aproximada (approximate Bayesian filtering), como o Filtro de Kalman (linear-gaussiano (linear-Gaussian)) ou o Filtro de Partículas.

Políticas sobre crenças (não sobre observações)

Em um MDP, uma política (policy) (estacionária) mapeia estados para ações: (\pi(a \mid s)).

Em um POMDP, a teoria padrão de otimalidade usa crenças:

[ \pi(a \mid b) ]

Isso é importante: uma única observação pode ser ambígua; a crença captura o que o agente sabe dado o histórico completo.

Funções de valor no espaço de crenças

Defina o valor de uma política a partir da crença (b):

[ V^\pi(b) = \mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^t r_t \mid b_0=b, \pi\right] ]

O valor ótimo satisfaz uma equação ao estilo de Bellman sobre crenças:

[ V^*(b) = \max_{a \in A}\left[ R(b,a) + \gamma \sum_{o \in \Omega} P(o \mid b,a), V^*(b_{a,o}) \right] ]

onde:

(R(b,a) = \sum_s b(s) R(s,a))
(b_{a,o}) é a crença atualizada após executar a ação (a) e ver a observação (o)

Isso se assemelha à Iteração de Valor, mas em um espaço contínuo (o símplex de crenças), o que é uma grande fonte de dificuldade computacional.

Relação com MDPs (e por que POMDPs são “mais difíceis”)

MDP como caso especial

Se as observações revelam perfeitamente o estado, isto é, (o = s) deterministicamente, então a crença colapsa para uma massa pontual (probabilidade 1 no estado verdadeiro). Nesse caso, o POMDP se reduz a um MDP.

A redução para o “MDP de crença (belief-MDP)”

Um resultado fundamental: um POMDP pode ser convertido em um MDP totalmente observável cujo estado é a crença (b). Esse MDP de crença é conceitualmente poderoso:

Estado: (b) (uma distribuição sobre (S))
Ação: (a \in A)
Transição: induzida por (T) e (O) por meio da atualização de crença
Recompensa: (R(b,a))

Isso significa que planejar em POMDP é “apenas planejar em um MDP”… mas o espaço de crenças é contínuo e tipicamente de alta dimensionalidade.

Complexidade e as “maldições”

POMDPs sofrem de várias dificuldades bem conhecidas:

Maldição da dimensionalidade (curse of dimensionality): crenças vivem em um símplex de dimensão (|S|-1)
Maldição do histórico (curse of history): a política deve considerar ações de coleta de informação (exploração para estimação de estado, não apenas recompensa)
Muitos problemas de planejamento exato são computacionalmente difíceis (planejamento de POMDP em horizonte finito (finite-horizon) é PSPACE-difícil (PSPACE-hard) em geral)

Exemplos práticos (o que a observabilidade parcial muda)

Exemplo 1: “problema do tigre (Tiger problem)” (clássico)

Duas portas: atrás de uma há um tigre (ruim), atrás da outra há um tesouro (bom). A localização do tigre é oculta. Ações:

Ouvir: obter uma observação ruidosa de onde o tigre está (pequeno custo)
Abrir esquerda/direita: termina o episódio com grande recompensa ou penalidade

Comportamento-chave de POMDP: a política ótima frequentemente ouve até ficar suficientemente confiante, e então abre a porta provavelmente segura. Um MDP sem estado oculto não consegue modelar a necessidade de coletar informação.

Exemplo 2: Um robô de serviço em uma casa

Estado oculto: se há um copo sobre a mesa. Observações: detecções da câmera (falhas/falsos positivos). Ações: mover, olhar de perto, pegar.

Uma boa política às vezes escolhe ações como “olhar de perto” que têm baixa recompensa imediata, mas melhoram a crença, permitindo melhores decisões a jusante.

Exemplo 3: Tratamento médico

Estado oculto: estágio de progressão da doença. Observações: exames laboratoriais e sintomas (ruidosos, atrasados). Ações: tratar, esperar, solicitar exames.

Políticas de POMDP capturam naturalmente o valor de testes diagnósticos como ações de coleta de informação.

Métodos de planejamento exato (quando o modelo é conhecido)

O planejamento exato em POMDP normalmente assume que (T), (O) e (R) são conhecidos.

Programação dinâmica de horizonte finito e vetores α (α-vectors)

Para espaços discretos de estado/ação/observação e horizonte finito, a função de valor ótima sobre crenças é linear por partes e convexa (piecewise-linear and convex, PWLC). Ela pode ser representada como:

[ V(b) = \max_{i} \alpha_i \cdot b ]

Cada (\alpha_i) é um vetor sobre estados. Isso leva a algoritmos semelhantes à iteração de valor, manipulando conjuntos de vetores α.

Na prática, o número de vetores α pode explodir, o que limita a escalabilidade.

Planejamento online (planejar enquanto atua)

Em vez de computar uma política completa offline, métodos online planejam a partir da crença atual e de uma profundidade de busca limitada.

Uma abordagem amplamente usada é o planejamento no estilo Busca em Árvore de Monte Carlo (Monte Carlo Tree Search) no espaço de crença/partículas (por exemplo, ideias do tipo POMCP), intimamente relacionada à Busca em Árvore de Monte Carlo. A ideia é:

Representar a crença com partículas amostradas
Simular trajetórias de ação-observação
Escolher ações que gerem bom retorno esperado

Métodos online frequentemente escalam melhor porque concentram computação nas crenças alcançáveis a partir da situação atual.

Métodos aproximados e escaláveis (o caso usual)

A maioria dos problemas reais exige aproximação.

Iteração de valor baseada em pontos (Point-based value iteration, família PBVI)

Em vez de resolver sobre todo o símplex de crenças, métodos baseados em pontos:

Amostram ou coletam um conjunto de crenças alcançáveis (B = {b^{(1)}, ..., b^{(N)}})
Fazem backups apenas nessas crenças

Isso pode produzir políticas fortes em problemas com espaços de estados discretos moderados. Variantes modernas melhoram como os pontos de crença são selecionados (frequentemente focando em crenças alcançáveis e relevantes).

Aproximação QMDP (tratar como totalmente observável “após um passo”)

Uma heurística comum:

Resolver o MDP totalmente observável subjacente sobre estados (s), produzindo (Q_{\text{MDP}}(s,a))
Escolher ações fazendo a média sobre a crença: [ Q(b,a) \approx \sum_s b(s) Q_{\text{MDP}}(s,a) ]

Isso funciona quando a incerteza se resolve rapidamente, mas pode falhar feio quando ações de coleta de informação são críticas (porque a aproximação as subvaloriza).

Controladores de estado finito (finite-state controllers) (política com memória)

Em vez de uma distribuição de crença, represente a política como um pequeno autômato:

Nós internos = “estados de memória”
Arestas condicionadas a observações
Cada nó escolhe uma ação

Isso pode ser prático quando rastrear crença é caro ou quando você quer uma política compacta, embora encontrar controladores ótimos seja desafiador.

Compressão de crença e aproximação de função

Em (S) discreto grande, crenças são vetores de probabilidade de alta dimensionalidade. É possível comprimir crenças em uma representação de menor dimensionalidade (por exemplo, via métodos lineares ou codificadores aprendidos (learned encoders)) e planejar/agir nesse espaço.

Em sistemas modernos de aprendizado por reforço (reinforcement learning), a observabilidade parcial é frequentemente tratada aprendendo um estado latente “tipo crença” com modelos de sequência como Redes Neurais Recorrentes ou transformers, e então aplicando métodos padrão de aprendizado por reforço nesse estado latente (veja “aprendizado” abaixo). Isso não é garantidamente ótimo em Bayes, mas pode funcionar bem empiricamente.

Aprendizado em cenários de POMDP (modelo desconhecido)

Quando (T) e (O) são desconhecidos, o problema se torna aprendizado por reforço parcialmente observável (partially observable reinforcement learning). Há duas estratégias amplas.

1) Aprender um modelo + fazer planejamento (aproximado) (baseado em modelo (model-based))

Você pode aprender componentes do POMDP:

dinâmica/modelo de transição
modelo de observação
modelo de recompensa

Depois, realizar rastreamento de crença aproximado e planejamento. Isso se alinha com ideias de aprendizado por reforço baseado em modelo em Aprendizado por Reforço, mas com ênfase adicional em estimação de estado.

Os desafios incluem identificabilidade (diferentes modelos de estado oculto podem explicar as mesmas observações) e erros que se acumulam em previsões de longo horizonte.

2) Aprender uma política diretamente a partir de históricos (livre de modelo (model-free))

Em vez de crenças explícitas, aprenda políticas da forma:

[ \pi(a_t \mid o_{1:t}, a_{1:t-1}) ]

Isso é comumente implementado com redes recorrentes (por exemplo, ideias do tipo DRQN) ou transformers que resumem o histórico em uma representação oculta. Esses métodos se conectam a algoritmos padrão como Aprendizado Q e Métodos de Gradiente de Política, adaptados a arquiteturas recorrentes.

Um aprendizado prático: em aprendizado por reforço profundo (deep RL), “lidar com POMDP” frequentemente significa adicionar memória (recorrência/atenção) e treinar de ponta a ponta, em vez de manter explicitamente crenças bayesianas.

Aplicações

POMDPs (e métodos inspirados em POMDP) aparecem em muitos domínios:

Robótica: navegação com localização incerta (crença sobre a pose), manipulação com estados de objetos incertos, percepção ativa
Direção autônoma: raciocínio sobre intenções ocultas de outros agentes, oclusões e ruído de sensores
Saúde: políticas de tratamento sob progressão latente da doença; valoração de testes diagnósticos
Sistemas de diálogo: rastreamento de intenção/slots do usuário como um estado de crença; escolha de perguntas para reduzir ambiguidade
Cibersegurança: resposta a intrusões sob detecção parcial; decidir quando isolar sistemas vs monitorar
Operações/estoque: a demanda é parcialmente observada; decisões dependem da crença sobre regimes futuros de demanda

Extensões multiagente relacionadas como Dec-POMDPs modelam múltiplos agentes com observabilidade parcial, mas são substancialmente mais complexas.

Intuições-chave e armadilhas comuns

Informação tem valor (e POMDPs modelam isso explicitamente)

Uma característica distintiva de políticas ótimas em POMDP é a presença de ações de coleta de informação. Elas podem parecer “subótimas” se você ignorar o estado oculto, porque trocam recompensa imediata por melhor qualidade de decisão futura.

A recompensa depende do estado oculto, não apenas da observação

Se você definir erroneamente recompensas como função apenas da observação, pode inadvertidamente criar políticas que exploram ruído de observação em vez de alcançar resultados reais.

Rastreamento de crença é parte da solução

Em POMDPs, “estimação de estado” e “controle” são acoplados:

Uma crença melhor leva a melhores decisões
Ações influenciam observações futuras (sensoriamento ativo)

Isso às vezes é contrastado com cenários clássicos (por exemplo, controle linear-quadrático-gaussiano) em que estimação e controle se separam parcialmente, mas, em geral, POMDPs não se decompõem de forma limpa.

Observabilidade parcial não é apenas “estocasticidade”

Mesmo que o ambiente seja determinístico, a observabilidade parcial pode tornar a experiência do agente incerta. Confundir essas coisas leva a escolhas de modelagem incorretas e políticas ruins.

Como isso se encaixa com outros conceitos de RL

POMDPs estendem Processo de Decisão de Markov adicionando estado oculto e observações.
Muitas ideias de planejamento se parecem com métodos de MDP como Iteração de Valor e Iteração de Política, mas aplicadas ao espaço de crenças.
Na prática, o aprendizado por reforço profundo comumente aproxima crença com memória e aprendizado de representações (políticas baseadas em recorrência/atenção), conectando-se a Ator-Crítico e às famílias de gradiente de política.
Para uma visão geral mais ampla e variantes, veja o artigo relacionado POMDPs.

Resumo

Um POMDP modela a tomada de decisão quando o verdadeiro estado é oculto e apenas observações ruidosas estão disponíveis. O conceito central é o estado de crença, uma distribuição de probabilidade sobre estados ocultos atualizada via regra de Bayes. Políticas ótimas em POMDP atuam sobre crenças, equilibrando maximização de recompensa com aquisição de informação. Embora existam soluções exatas para pequenos problemas discretos (frequentemente usando a estrutura de vetores α), aplicações reais dependem de planejamento aproximado (baseado em pontos, busca online, heurísticas como QMDP) ou de abordagens baseadas em aprendizado que aproximam crenças implicitamente usando memória e aproximação de função.

Se você consegue modelar a incerteza sobre estado oculto e o valor da informação, POMDPs fornecem uma das fundações mais principiadas disponíveis para planejamento sob observabilidade parcial.