Resumen Técnico: MDPs de Ausencia (miss-MDPs)

Enunciado del Problema

El artículo aborda el desafío de la toma de decisiones secuenciales bajo incertidumbre cuando las características del estado están dinámicamente ausentes. Mientras que los Procesos de Decisión de Markov (MDPs) asumen una observabilidad completa, los escenarios del mundo real (por ejemplo, diagnósticos médicos con datos de sensores incompletos) a menudo implican características faltantes. Los Procesos de Decisión de Markov Parcialmente Observables (POMDPs) estándar pueden modelar esto mediante una función de observación; sin embargo, aprender esta función a partir de historias de acciones y observaciones es generalmente no identificable y computacionalmente intratable.

Los autores definen un escenario de problema específico: Dado un miss-MDP con un MDP subyacente conocido (función de transición $T$) pero una función de ausencia $M$ desconocida, y un conjunto de datos de trayectorias de acción-observación, el objetivo es calcular una política $\pi^*$ que sea $\epsilon$-óptima. La dificultad central radica en aprender $M$ a partir de los datos para habilitar la planificación, una tarea que es imposible para POMDPs generales pero potencialmente factible para subclases específicas.

Metodología

1. Definición de miss-MDPs

Los autores introducen los MDPs de Ausencia (miss-MDPs) como una subclase propia de POMDPs.

• Estructura: Un miss-MDP es una tupla $(S, A, T, b_0, \varrho, Z, M, \gamma)$.
• Espacio de Observación: $Z = \times_{i \in I} (S_i \cup \{\perp\})$, donde $\perp$ denota una característica ausente.
• Función de Ausencia ($M$): Una función estocástica $M: S \to \Delta(Z)$ que determina la probabilidad de que las características sean observadas o estén ausentes.
• Tipos de Ausencia: El marco adopta la taxonomía canónica de datos faltantes (Rubin, 1976):
  • MCAR (Ausente Completamente al Azar): La ausencia es independiente de los valores del estado.
  • MAR (Ausente al Azar): La ausencia depende solo de las características observadas. Los autores distinguen entre MAR Simple (depende solo de las características siempre observadas) y MAR general.
  • MNAR (Ausente No al Azar): La ausencia depende de los valores de las características no observadas (faltantes).

2. Algoritmos de Aprendizaje (Garantías PAC)

El artículo propone algoritmos de aprendizaje Probablemente Aproximadamente Correctos (PAC) para aproximar la función de ausencia desconocida $\hat{M}$ a partir de un conjunto de datos $D$. El enfoque se basa en la identificabilidad de tipos específicos de ausencia.

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

  • Particiona las características en siempre observadas ($\hat{I}_{always}$) y potencialmente ausentes.
  • Estima la probabilidad de los indicadores de ausencia basándose en los valores de las características siempre observadas.
  • Teorema 1: Demuestra que para MAR Simple, $\hat{M}$ converge a la verdadera $M$ con alta probabilidad a medida que aumenta el tamaño del conjunto de datos.

• Algoritmo $A_{IMI}$ (para Indicadores de Ausencia Independientes):

  • Aplicable a MCAR, MAR Simple y un subconjunto de MNAR identificable.
  • Asume: (1) Independencia de los indicadores de ausencia entre características, (2) Ausencia de autocensura (el valor de una característica no influye en su propia ausencia) y (3) Positividad (las características tienen una probabilidad no nula de ser observadas).
  • Estima las probabilidades de ausencia para cada característica independientemente basándose en otras características observadas.
  • Teorema 2: Demuestra garantías PAC para $\hat{M}$ bajo estos supuestos.

• Cálculo de la Política:

  • Una vez aproximado $\hat{M}$, los autores construyen un miss-MDP completamente especificado $\hat{P}$.
  • Utilizan solucionadores de POMDP estándar (por ejemplo, SARSOP) para calcular una política $\epsilon$-óptima para $\hat{P}$.
  • Teorema 3: Demuestra que si $\hat{M}$ es suficientemente preciso, la política resultante es $\epsilon$-óptima para el miss-MDP verdadero $P$.

3. Perspectivas Teóricas

• Ignorabilidad: Los autores demuestran (Observación 1) que para MAR (incluido MCAR), las probabilidades específicas de la función de ausencia son "ignorables" para las actualizaciones de creencia (mantener la distribución actual del estado) porque se cancelan en la regla de Bayes. Sin embargo, la función sigue siendo necesaria para calcular la política en sí, ya que las probabilidades de transición entre creencias dependen de $M$.

Contribuciones Clave

1. Formalización: Introducción de miss-MDPs, integrando la teoría de datos faltantes (MCAR, MAR, MNAR) en el marco de POMDP para definir una subclase tratable donde la función de observación es aprendible.
2. Análisis de Identificabilidad: Identificación de condiciones específicas (MAR Simple, Independiente/MNAR sin autocensura) bajo las cuales la función de ausencia es aprendible a partir de historias, en contraste con la no identificabilidad general de las funciones de observación de POMDP.
3. Algoritmos PAC: Desarrollo de algoritmos ($A_{sMAR}$, $A_{IMI}$) con garantías PAC formales para aprender la función de ausencia.
4. Garantías de Optimalidad: Demostración de que aprender $\hat{M}$ con precisión suficiente permite el cálculo de políticas $\epsilon$-óptimas para el sistema real.

Resultados Experimentales

Los autores evaluaron su enfoque en dos puntos de referencia:

1. UCI: Un modelo de toma de decisiones médicas (médico tratando a un paciente) con 800 estados.
2. Depredador: Un juego de persecución-evasión (variante de Tag) con hasta 1.765 estados.

Hallazgos:

• Calidad de la Aproximación: Bajo supuestos correctos, la distancia de Variación Total (TV) entre el $\hat{M}$ aprendido y el verdadero $M$ converge a cero a medida que aumenta el tamaño del conjunto de datos.
• Rendimiento de la Política: Las políticas derivadas del miss-MDP aprendido convergen al valor de la política óptima ($\pi^*$) a medida que mejora la aproximación.
• Sensibilidad a los Supuestos: Supuestos incorrectos (por ejemplo, asumir MAR cuando los datos son MNAR con autocensura) conducen a una mala aproximación y políticas subóptimas.
• Comparación con Líneas Base: El enfoque basado en modelos propuesto superó significativamente a las líneas base sin modelo (PPO con/sin memoria, POMCP) en ambos puntos de referencia. Los autores atribuyen el fracaso de los métodos sin modelo a su incapacidad para manejar eficazmente la estructura específica de observabilidad parcial de los miss-MDPs, señalando que estos métodos tuvieron éxito cuando se eliminó la ausencia.

Significado y Afirmaciones

El artículo afirma cerrar la brecha entre la teoría de datos faltantes y la toma de decisiones secuenciales. Su principal significado radica en proporcionar un enfoque basado en modelos y principiado para manejar datos faltantes en POMDPs con garantías estadísticas (PAC).

A diferencia de trabajos anteriores que tratan la ausencia como incidental o se basan en imputación sin garantías, este trabajo:

1. Modela explícitamente el proceso de ausencia.
2. Aprende la función de ausencia a partir de datos con límites teóricos sobre el error.
3. Aprovecha este modelo aprendido para garantizar la near-optimalidad de la política resultante.

Los autores notan modestamente que su enfoque actual asume que la función de transición del MDP subyacente es conocida. Identifican levantar este supuesto y extender el marco a miss-POMDPs generales como direcciones para trabajos futuros. Los resultados empíricos confirman que su enfoque es superior a las formulaciones directas de POMDP (como POMCP) y a los métodos de aprendizaje por refuerzo profundo (como PPO) en configuraciones donde el mecanismo de ausencia sigue patrones identificables.