POMDPs

Visão geral

Um Processo de Decisão de Markov Parcialmente Observável (Partially Observable Markov Decision Process, POMDP) é uma estrutura matemática padrão para tomada de decisão sequencial (sequential decision-making) quando o agente não consegue observar diretamente o verdadeiro estado do ambiente. Em vez disso, o agente recebe observações ruidosas e/ou incompletas e deve agir com base no que ele acredita sobre o estado oculto.

POMDPs estendem Processos de Decisão de Markov (MDPs) ao adicionar estado oculto e um modelo de observação (observation model). Eles são amplamente usados em robótica, sistemas de diálogo, suporte à decisão médica, direção autônoma e em qualquer cenário em que sensores sejam imperfeitos ou as variáveis relevantes sejam latentes.

O principal salto conceitual é o estado de crença (belief state): uma distribuição de probabilidade sobre possíveis estados ocultos. Com a regra de atualização correta, estados de crença restauram uma propriedade de Markov e permitem planejar “como se” a crença fosse o estado.

Definição formal

Um POMDP (finito) é tipicamente definido como uma tupla:

[ \mathcal{P} = \langle \mathcal{S}, \mathcal{A}, \mathcal{O}, T, Z, R, \gamma \rangle ]

Onde:

• (\mathcal{S}): conjunto de estados ocultos do ambiente
• (\mathcal{A}): conjunto de ações
• (\mathcal{O}): conjunto de observações
• (T(s' \mid s, a)): modelo de transição (transition model) (dinâmica)
• (Z(o \mid s', a)): modelo de observação (modelo de sensor/emissão)
• (R(s, a)) (ou (R(s,a,s'))): função de recompensa (reward function)
• (\gamma \in [0,1)): fator de desconto (discount factor) (em problemas de horizonte infinito)

O processo se desenrola assim:

1. O ambiente está no estado oculto (s_t).
2. O agente escolhe a ação (a_t).
3. O ambiente transita para (s_{t+1} \sim T(\cdot \mid s_t, a_t)).
4. O agente recebe a observação (o_{t+1} \sim Z(\cdot \mid s_{t+1}, a_t)).
5. O agente recebe a recompensa (r_t = R(s_t, a_t)) (ou similar).

Como POMDPs se relacionam com MDPs

Um MDP é um caso especial de POMDP em que as observações revelam o estado perfeitamente:

• (\mathcal{O} = \mathcal{S})
• (Z(o \mid s', a) = 1) se (o=s'), caso contrário (0)

Nesse caso, o estado de crença colapsa para uma distribuição one-hot, e o planejamento em POMDP se torna planejamento padrão em MDP (por exemplo, Iteração de Valor).

Estados de crença: tornando a observabilidade parcial tratável

Como o agente não pode condicionar suas decisões ao estado verdadeiro (s_t), ele condiciona ao histórico (h_t = (o_1, a_1, o_2, a_2, \dots, o_t)). Históricos crescem com o tempo e são difíceis de manejar.

A propriedade-chave de um POMDP é que o agente pode resumir todo o histórico por um estado de crença:

[ b_t(s) = \Pr(s_t = s \mid h_t) ]

Essa crença é uma distribuição de probabilidade sobre (\mathcal{S}). A crença é atualizada usando a regra de Bayes após cada ação e observação. Isso é estreitamente relacionado à estimação de estado em Filtragem Bayesiana (incluindo variantes de Filtro de Kalman e Filtro de Partículas).

Atualização de crença (filtro de Bayes)

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

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

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

Em pseudocódigo:

def belief_update(b, a, o, T, Z):
    # b: dict or array over states s
    # T[s][a][s_next] = P(s_next | s, a)
    # Z[s_next][a][o] = P(o | s_next, a)
    b_pred = {}
    for s_next in S:
        b_pred[s_next] = sum(T[s][a][s_next] * b[s] for s in S)

    b_new_unnorm = {s_next: Z[s_next][a][o] * b_pred[s_next] for s_next in S}
    norm = sum(b_new_unnorm.values())
    return {s: v / norm for s, v in b_new_unnorm.items()}

A visão de “MDP de crenças (belief-MDP)”

Crenças transformam o POMDP em um MDP totalmente observável em um espaço de estados contínuo:

• Estado: (b \in \Delta(\mathcal{S})) (o simplex de probabilidade)
• Ação: a mesma (\mathcal{A})
• Transição: determinada por (T, Z) e pela atualização de crença
• Recompensa: recompensa esperada sob a crença, por exemplo
  [ R(b,a)=\sum_s b(s)R(s,a) ]

Esse MDP de crenças é fundamental: a maioria dos algoritmos de planejamento para POMDPs são, na prática, algoritmos para resolver esse MDP de estado contínuo.

Políticas em POMDPs

Uma política em POMDP tipicamente mapeia crenças para ações:

[ \pi: \Delta(\mathcal{S}) \to \mathcal{A} ]

Isso difere de políticas em MDP (\pi(s)) porque o estado é desconhecido. Em POMDPs de horizonte finito, políticas às vezes são representadas como árvores de política (policy trees) (ramificando por observações). Em configurações descontadas de horizonte infinito, busca-se uma política estacionária sobre crenças (\pi(b)).

Funções de valor e equações de Bellman

Para uma crença (b), defina o valor ótimo:

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

A equação de otimalidade de Bellman (Bellman optimality equation) no espaço de crenças é:

[ V^(b) = \max_{a \in \mathcal{A}}\left( R(b,a) + \gamma \sum_{o \in \mathcal{O}} \Pr(o \mid b,a); V^(\tau(b,a,o)) \right) ]

Onde:

• (\Pr(o \mid b,a) = \sum_{s'} Z(o\mid s',a)\sum_s T(s'\mid s,a)b(s))
• (\tau(b,a,o)) é o operador de atualização de crença que produz (b')

Estrutura linear por partes e convexa (finite state/action/observation)

Um resultado clássico e extremamente importante: para (\mathcal{S},\mathcal{A},\mathcal{O}) finitos e recompensa descontada, 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_{\alpha \in \Gamma} \sum_s \alpha(s), b(s) ]

Cada vetor (\alpha) corresponde (grosso modo) ao valor de um plano condicional específico. Essa estrutura de “vetores (\alpha) ((\alpha)-vectors)” viabiliza métodos exatos de programação dinâmica (dynamic programming) — mas também evidencia por que a complexidade explode: o conjunto (\Gamma) pode crescer exponencialmente.

Um exemplo concreto: navegação de robô com sensoriamento ruidoso

Imagine um robô em um corredor com duas posições possíveis:

• (S={\text{Left}, \text{Right}})
• Ações: (A={\text{GoLeft}, \text{GoRight}})
• Observações: (O={\text{SeeLeftWall}, \text{SeeRightWall}})

Os sensores são ruidosos: quando está em Left, ele vê “LeftWall” com probabilidade 0,8 e “RightWall” com probabilidade 0,2 (e vice-versa em Right). O robô recebe recompensa +10 por alcançar a extremidade Right, mas bater no lado errado custa -5.

Se o robô está incerto (crença (b(\text{Right})=0.55)), ele pode escolher uma ação que primeiro reduza a incerteza (por exemplo, mover-se para um local com melhor sensoriamento ou executar uma ação de “sentir”) se o valor esperado de longo prazo for maior do que agir imediatamente. Isso é a marca registrada do comportamento em POMDP: coleta de informação pode ser ótima, mesmo que não tenha recompensa imediata.

Abordagens comuns de solução

Métodos exatos para resolver POMDPs são teoricamente elegantes, mas muitas vezes computacionalmente caros (muitas variantes são PSPACE-hard em geral). O trabalho prático com POMDPs depende fortemente de aproximações.

1) Métodos exatos (problemas pequenos)

Esses métodos exploram a estrutura PWLC e operam sobre vetores (\alpha).

Iteração de valor (value iteration) no espaço de crenças

A iteração de valor “exata” em POMDP computa um conjunto crescente de vetores (\alpha) via backups de programação dinâmica. Operações-chave incluem:

• fazer backup do valor através de ações e observações
• podar vetores (\alpha) dominados (vetores que nunca são ótimos para nenhuma crença)

Algoritmos incluem a iteração de valor de Sondik (Sondik’s value iteration) e a poda incremental (incremental pruning).

Quando funciona bem: espaços de estado pequenos (dezenas de estados) com observações e ações limitadas.

Limitações: o número de vetores (\alpha) pode explodir rapidamente com o horizonte e o tamanho do problema.

Variantes de iteração de política (policy iteration)

Existem abordagens de iteração de política para POMDPs, mas elas são menos usadas em cenários de grande escala do que em MDPs devido a desafios de representação e avaliação. Em vez disso, muitos planejadores práticos fazem melhoria aproximada de políticas.

2) Métodos baseados em pontos (point-based methods) (espaços de crenças grandes)

O espaço de crenças é contínuo, mas muitas crenças nunca são encontradas (ou são muito improváveis) sob boas políticas. Métodos baseados em pontos aproximam a função de valor focando o cálculo em um conjunto finito de crenças alcançáveis (reachable beliefs).

Algoritmos populares baseados em pontos incluem:

• PBVI (Point-Based Value Iteration)
• Perseus
• SARSOP (um dos solucionadores offline práticos mais conhecidos para muitos problemas de porte médio)

Esboço de alto nível do PBVI:

# B: selected belief points (e.g., sampled from simulations)
# Gamma: alpha-vectors approximating value on B

initialize Gamma arbitrarily
repeat:
    for b in B:
        alpha_b = backup(b, Gamma)   # choose best action + observation branches
        add alpha_b to new set
    prune dominated alpha-vectors (optional)
    Gamma = new set
until convergence or budget exhausted

Por que é eficaz: o algoritmo investe esforço onde importa — crenças prováveis sob a política.

O que você perde: você deixa de garantir otimalidade global sobre todas as crenças, apenas uma boa aproximação em/ao redor do conjunto amostrado.

3) Planejamento online (online planning) (cálculo no momento da decisão)

Em vez de calcular uma política completa offline, planejadores online computam a próxima ação a partir da crença atual construindo uma árvore de lookahead. Essa costuma ser a melhor escolha quando:

• o modelo é conhecido,
• o espaço de estados é grande,
• e você só precisa de uma boa ação agora.

Famílias comuns:

• Busca em árvore de crenças (belief-tree search): constrói uma árvore sobre (crença, ação, observação).
• Métodos de Monte Carlo (Monte Carlo methods): aproximam a evolução da crença via amostragem.

Uma abordagem famosa é POMCP (Partially Observable Monte Carlo Planning), que combina:

• Busca em Árvore de Monte Carlo (Busca em Árvore de Monte Carlo)
• filtragem por partículas para representar a crença
• políticas de rollout para estimativas de valor em nós folha

Solucionadores online relacionados (com pressupostos e limites diferentes) incluem DESPOT e outras abordagens de árvores esparsas amostradas.

Pontos fortes: escala para problemas grandes, pode funcionar com modelos gerativos (simuladores) em vez de tabelas explícitas.

Pontos fracos: requer computação em tempo de execução; o desempenho depende da qualidade do rollout e do orçamento de amostragem.

4) Aprendizado em POMDPs (modelo desconhecido)

Em muitas tarefas reais, os modelos de transição e observação não são conhecidos. Então o agente deve aprender enquanto atua — isso se cruza com Aprendizado por Reforço e especialmente com Aprendizado por Reforço Profundo.

Duas abordagens amplas:

Aprendizado baseado em modelo (model-based learning) (aprender \(T\) e \(Z\), depois planejar)

Você pode aprender um modelo de dinâmica e observação, manter uma crença com um filtro aprendido ou estruturado e então planejar no espaço de crenças. Isso se encaixa em Aprendizado por Reforço Baseado em Modelo.

Abordagens sem modelo / ponta a ponta (model-free / end-to-end) (aprender memória)

Se você não mantiver crenças explicitamente, pode treinar uma política/função de valor que condicione em históricos de observações usando recorrência ou atenção (por exemplo, agentes no estilo “DRQN” baseados em RNN). Na prática, a rede aprende um estado de crença implícito.

Isso se conecta a:

• variantes parcialmente observadas de aprendizado de valor (relacionadas a Aprendizado Q)
• otimização de políticas sobre políticas recorrentes (relacionada a Gradientes de Política)

Nota prática: rastreamento explícito de crença costuma ser mais eficiente em dados quando existe um bom modelo; métodos profundos ponta a ponta podem ser mais simples de implantar quando modelar é difícil, mas podem exigir mais dados e treinamento cuidadoso.

Aplicações (onde POMDPs se destacam)

Robótica: localização e navegação

Robôs raramente conhecem sua pose exata. POMDPs combinam naturalmente:

• incerteza sobre a posição (estado)
• sensores ruidosos (observações)
• incerteza de atuação (transições estocásticas)

Planejadores de POMDP também podem equilibrar explicitamente movimento vs. coleta de informação (por exemplo, mover-se para reduzir ambiguidade antes de se comprometer com um corredor arriscado).

Sistemas de diálogo e agentes conversacionais

A intenção do usuário é oculta; enunciados são evidência ruidosa. POMDPs modelam:

• objetivos ocultos do usuário
• saídas ruidosas de ASR/NLU como observações
• ações como respostas do sistema

Rastreamento de crença é uma ideia central em diálogo orientado a tarefas (hoje frequentemente implementado com rastreadores de crença aprendidos).

Tomada de decisão médica

O estado da doença é latente; testes são observações com falsos positivos/negativos; tratamentos são ações com custos/efeitos colaterais.

Um POMDP pode escolher entre:

• solicitar agora um teste informativo porém caro
• tratar imediatamente com base na crença atual
• esperar por observações adicionais

Segurança e inspeção

Você pode não observar a localização ou a intenção de um adversário; você só obtém sinais parciais de sensores. POMDPs capturam patrulhamento, triagem e inspeção ótimos sob incerteza.

POMDPs e arquiteturas de agentes

Uma visão útil de sistemas é que POMDPs formalizam um ciclo clássico sentir–estimar–planejar–agir (sense–estimate–plan–act):

1. Sensoriamento: receber observação (o_t)
2. Estimação de estado (state estimation): atualizar crença (b_t) (filtragem)
3. Planejamento/controle: computar ação (a_t = \pi(b_t))
4. Atuação: executar (a_t)

Essa modularidade corresponde a muitas arquiteturas reais de agentes:

• Estimador: filtro bayesiano / filtro de partículas / atualizador de crença aprendido
• Planejador: solucionador baseado em pontos, MCTS online, ou programação dinâmica aproximada
• Execução de política: selecionar ação, opcionalmente com restrições de segurança

Em sistemas de aprendizado por reforço profundo, a “crença” frequentemente é representada implicitamente em um estado oculto aprendido (RNN/Transformer), fundindo as etapas (2) e (3) em uma única rede.

Escolhas práticas de modelagem e armadilhas

Escolhendo o estado

O estado deve ser Markov em princípio, mesmo que oculto. Erros comuns incluem:

• omitir variáveis latentes de mudança lenta (por exemplo, identidade do mapa, objetivo do usuário)
• misturar variáveis de “observação” no “estado” sem dinâmica clara

O realismo do modelo de observação importa

Se (Z(o\mid s,a)) estiver mal especificado, atualizações de crença se tornam enganosas, e planejadores podem tomar ações frágeis (por exemplo, confiar demais em sensores).

Considerações computacionais

• A crença é contínua; representações exatas são inviáveis para (|S|) grande.
• Filtros de partículas escalam melhor, mas introduzem ruído de amostragem.
• Solucionadores offline podem ser caros, mas fornecem ações rápidas em tempo de execução.
• Solucionadores online deslocam o custo para o tempo de execução e exigem orçamento de latência.

Modelagem de recompensa vs. valor da informação

Em POMDPs, coleta de informação pode ser ótima mesmo sem recompensa explícita por informação. Modelar demais a recompensa para “incentivar exploração” pode distorcer as trocas desejadas.

Resumo

POMDPs são a estrutura canônica para tomada de decisão sob observabilidade parcial, estendendo MDPs com:

• estado oculto (s),
• observações ruidosas (o),
• e estados de crença (b(s)=P(s\mid \text{histórico})) que permitem planejamento Markoviano no espaço de crenças.

Ideias centrais incluem:

• atualizações bayesianas de crença (filtragem) e a construção de MDP de crenças
• funções de valor PWLC (para POMDPs finitos), viabilizando solucionadores exatos em problemas pequenos
• métodos aproximados para escalar, especialmente:
  • planejamento offline baseado em pontos (PBVI, SARSOP)
  • planejamento online com amostragem (por exemplo, POMCP via Busca em Árvore de Monte Carlo)
  • representações aprendidas e implícitas de crença/estado em Aprendizado por Reforço Profundo

Na prática, POMDPs são tanto uma teoria de ação ótima sob incerteza quanto um modelo de projeto para agentes reais que precisam combinar estimação de estado + planejamento em mundos observados de forma imperfeita.

---