Resumo Técnico: MDPs de Ausência (miss-MDPs)

Declaração do Problema

O artigo aborda o desafio da tomada de decisão sequencial sob incerteza quando as características do estado estão dinamicamente ausentes. Enquanto os Processos de Decisão de Markov (MDPs) assumem observabilidade total, cenários do mundo real (por exemplo, diagnósticos médicos com dados de sensores incompletos) frequentemente envolvem características ausentes. Os Processos de Decisão de Markov Parcialmente Observáveis (POMDPs) padrão podem modelar isso por meio de uma função de observação; no entanto, aprender essa função a partir de históricos de ação-observação é geralmente não identificável e computacionalmente intratável.

Os autores definem um cenário de problema específico: Dado um miss-MDP com um MDP subjacente conhecido (função de transição $T$) mas uma função de ausência $M$ desconhecida, e um conjunto de dados de trajetórias de ação-observação, o objetivo é calcular uma política $\pi^*$ que seja $\epsilon$-ótima. A dificuldade central reside em aprender $M$ a partir dos dados para permitir o planejamento, uma tarefa que é impossível para POMDPs gerais, mas potencialmente viável para subclasses específicas.

Metodologia

1. Definição de miss-MDPs

Os autores introduzem os MDPs de Ausência (miss-MDPs) como uma subclassificação adequada de POMDPs.

• Estrutura: Um miss-MDP é uma tupla $(S, A, T, b_0, \varrho, Z, M, \gamma)$.
• Espaço de Observação: $Z = \times_{i \in I} (S_i \cup \{\perp\})$, onde $\perp$ denota uma característica ausente.
• Função de Ausência ($M$): Uma função estocástica $M: S \to \Delta(Z)$ que determina a probabilidade de as características serem observadas ou ausentes.
• Tipos de Ausência: O framework adota a taxonomia canônica de dados ausentes (Rubin, 1976):
  • MCAR (Ausência Completamente ao Acaso): A ausência é independente dos valores do estado.
  • MAR (Ausência ao Acaso): A ausência depende apenas das características observadas. Os autores distinguem entre MAR Simples (depende apenas de características sempre observadas) e MAR geral.
  • MNAR (Ausência Não ao Acaso): A ausência depende dos valores das características não observadas (ausentes).

2. Algoritmos de Aprendizado (Garantias PAC)

O artigo propõe algoritmos de aprendizado Probavelmente Aproximadamente Corretos (PAC) para aproximar a função de ausência desconhecida $\hat{M}$ a partir de um conjunto de dados $D$. A abordagem baseia-se na identificabilidade de tipos específicos de ausência.

• Algoritmo $A_{sMAR}$ (para MAR Simples):

  • Particiona as características em sempre observadas ($\hat{I}_{always}$) e potencialmente ausentes.
  • Estima a probabilidade de indicadores de ausência com base nos valores das características sempre observadas.
  • Teorema 1: Prova que, para MAR Simples, $\hat{M}$ converge para a verdadeira $M$ com alta probabilidade à medida que o tamanho do conjunto de dados aumenta.

• Algoritmo $A_{IMI}$ (para Indicadores de Ausência Independentes):

  • Aplicável a MCAR, MAR Simples e um subconjunto de MNAR identificável.
  • Assume: (1) Independência dos indicadores de ausência entre as características, (2) Ausência de autocensura (o valor de uma característica não influencia sua própria ausência) e (3) Positividade (as características têm probabilidade não nula de serem observadas).
  • Estima as probabilidades de ausência para cada característica independentemente com base em outras características observadas.
  • Teorema 2: Prova garantias PAC para $\hat{M}$ sob essas suposições.

• Cálculo da Política:

  • Uma vez que $\hat{M}$ é aproximado, os autores constroem um miss-MDP totalmente especificado $\hat{P}$.
  • Eles utilizam solucionadores de POMDP prontos (por exemplo, SARSOP) para calcular uma política $\epsilon$-ótima para $\hat{P}$.
  • Teorema 3: Prova que, se $\hat{M}$ for suficientemente preciso, a política resultante é $\epsilon$-ótima para o verdadeiro miss-MDP $P$.

3. Insights Teóricos

• Ignorabilidade: Os autores provam (Observação 1) que, para MAR (incluindo MCAR), as probabilidades específicas da função de ausência são "ignoráveis" para atualizações de crença (manutenção da distribuição atual do estado) porque elas se cancelam na regra de Bayes. No entanto, a função ainda é necessária para calcular a própria política, pois as probabilidades de transição entre crenças dependem de $M$.

Contribuições Principais

1. Formalização: Introdução dos miss-MDPs, integrando a teoria de dados ausentes (MCAR, MAR, MNAR) ao framework POMDP para definir uma subclassificação tratável onde a função de observação é aprendível.
2. Análise de Identificabilidade: Identificação de condições específicas (MAR Simples, Independente/MNAR sem autocensura) sob as quais a função de ausência é aprendível a partir de históricos, contrastando com a não identificabilidade geral das funções de observação de POMDPs.
3. Algoritmos PAC: Desenvolvimento de algoritmos ($A_{sMAR}$, $A_{IMI}$) com garantias formais PAC para aprender a função de ausência.
4. Garantias de Otimalidade: Prova de que aprender $\hat{M}$ com precisão suficiente permite o cálculo de políticas $\epsilon-ótimas$ para o sistema verdadeiro.

Resultados Experimentais

Os autores avaliaram sua abordagem em dois benchmarks:

1. ICU: Um modelo de tomada de decisão médica (médico tratando um paciente) com 800 estados.
2. Predador: Um jogo de perseguição-evasão (variação de Tag) com até 1.765 estados.

Descobertas:

• Qualidade da Aproximação: Sob suposições corretas, a distância de Variação Total (TV) entre o $\hat{M}$ aprendido e o verdadeiro $M$ converge para zero à medida que o tamanho do conjunto de dados aumenta.
• Desempenho da Política: Políticas derivadas do miss-MDP aprendido convergem para o valor da política ótima ($\pi^*$) à medida que a aproximação melhora.
• Sensibilidade às Suposições: Suposições incorretas (por exemplo, assumir MAR quando os dados são MNAR com autocensura) levam a uma aproximação pobre e políticas subótimas.
• Comparação com Baselines: A abordagem baseada em modelo proposta superou significativamente as baselines sem modelo (PPO com/sem memória, POMCP) em ambos os benchmarks. Os autores atribuem a falha dos métodos sem modelo à sua incapacidade de lidar efetivamente com a estrutura específica de observabilidade parcial dos miss-MDPs, observando que esses métodos tiveram sucesso quando a ausência foi removida.

Significado e Alegações

O artigo afirma preencher a lacuna entre a teoria de dados ausentes e a tomada de decisão sequencial. Seu significado principal reside em fornecer uma abordagem baseada em modelo e principial para lidar com dados ausentes em POMDPs com garantias estatísticas (PAC).

Diferentemente de trabalhos anteriores que tratam a ausência como incidental ou dependem de imputação sem garantias, este trabalho:

1. Modela explicitamente o processo de ausência.
2. Aprende a função de ausência a partir de dados com limites teóricos sobre o erro.
3. Aproveita esse modelo aprendido para garantir a quase otimalidade da política resultante.

Os autores observam modestamente que sua abordagem atual assume que a função de transição do MDP subjacente é conhecida. Eles identificam a elevação dessa suposição e a extensão do framework para miss-POMDPs gerais como direções para trabalhos futuros. Os resultados empíricos confirmam que sua abordagem é superior a formulações diretas de POMDP (como POMCP) e métodos de aprendizado por reforço profundo (como PPO) em configurações onde o mecanismo de ausência segue padrões identificáveis.