Technical Summary: Missingness-MDPs (miss-MDPs)

Problem Statement

The paper addresses the challenge of sequential decision-making under uncertainty when state features are dynamically missing. While Markov Decision Processes (MDPs) assume full observability, real-world scenarios (e.g., medical diagnostics with incomplete sensor data) often involve missing features. Standard Partially Observable Markov Decision Processes (POMDPs) can model this via an observation function; however, learning this function from action-observation histories is generally unidentifiable and computationally intractable.

The authors define a specific problem setting: Given a miss-MDP with a known underlying MDP (transition function $T$) but an unknown missingness function $M$, and a dataset of action-observation trajectories, the goal is to compute a policy $\pi^*$ that is $\epsilon$-optimal. The core difficulty lies in learning $M$ from data to enable planning, a task that is impossible for general POMDPs but potentially feasible for specific subclasses.

Methodology

1. Definition of Miss-MDPs

The authors introduce Missingness-MDPs (miss-MDPs) as a proper subclass of POMDPs.

• Structure: A miss-MDP is a tuple $(S, A, T, b_0, \varrho, Z, M, \gamma)$.
• Observation Space: $Z = \times_{i \in I} (S_i \cup \{\perp\})$, where $\perp$ denotes a missing feature.
• Missingness Function ($M$): A stochastic function $M: S \to \Delta(Z)$ that determines the probability of features being observed or missing.
• Missingness Types: The framework adopts the canonical missing data taxonomy (Rubin, 1976):
  • MCAR (Missing Completely at Random): Missingness is independent of state values.
  • MAR (Missing at Random): Missingness depends only on observed features. The authors distinguish between Simple MAR (depends only on always-observed features) and general MAR.
  • MNAR (Missing Not at Random): Missingness depends on unobserved (missing) feature values.

2. Learning Algorithms (PAC Guarantees)

The paper proposes Probably Approximately Correct (PAC) learning algorithms to approximate the unknown missingness function $\hat{M}$ from a dataset $D$. The approach relies on the identifiability of specific missingness types.

• Algorithm $A_{sMAR}$ (for Simple MAR):

  • Partitions features into always-observed ($\hat{I}_{always}$) and potentially missing.
  • Estimates the probability of missingness indicators based on the values of always-observed features.
  • Theorem 1: Proves that for Simple MAR, $\hat{M}$ converges to the true $M$ with high probability as dataset size increases.

• Algorithm $A_{IMI}$ (for Independent Missingness Indicators):

  • Applicable to MCAR, Simple MAR, and a subset of identifiable MNAR.
  • Assumes: (1) Independence of missingness indicators across features, (2) No self-censoring (a feature's value does not influence its own missingness), and (3) Positivity (features have a non-zero probability of being observed).
  • Estimates missingness probabilities for each feature independently based on other observed features.
  • Theorem 2: Proves PAC guarantees for $\hat{M}$ under these assumptions.

• Policy Computation:

  • Once $\hat{M}$ is approximated, the authors construct a fully specified miss-MDP $\hat{P}$.
  • They utilize off-the-shelf POMDP solvers (e.g., SARSOP) to compute an $\epsilon$-optimal policy for $\hat{P}$.
  • Theorem 3: Proves that if $\hat{M}$ is sufficiently accurate, the resulting policy is $\epsilon$-optimal for the true miss-MDP $P$.

3. Theoretical Insights

• Ignorability: The authors prove (Remark 1) that for MAR (including MCAR), the specific probabilities of the missingness function are "ignorable" for belief updates (maintaining the current state distribution) because they cancel out in Bayes' rule. However, the function is still required to compute the policy itself, as the transition probabilities between beliefs depend on $M$.

Key Contributions

1. Formalization: Introduction of miss-MDPs, integrating missing data theory (MCAR, MAR, MNAR) into the POMDP framework to define a tractable subclass where the observation function is learnable.
2. Identifiability Analysis: Identification of specific conditions (Simple MAR, Independent/MNAR without self-censoring) under which the missingness function is learnable from histories, contrasting with the general unidentifiability of POMDP observation functions.
3. PAC Algorithms: Development of algorithms ($A_{sMAR}$, $A_{IMI}$) with formal PAC guarantees for learning the missingness function.
4. Optimality Guarantees: Proof that learning $\hat{M}$ with sufficient precision allows for the computation of $\epsilon$-optimal policies for the true system.

Experimental Results

The authors evaluated their approach on two benchmarks:

1. ICU: A medical decision-making model (doctor treating a patient) with 800 states.
2. Predator: A pursuit-evasion game (Tag variant) with up to 1,765 states.

Findings:

• Approximation Quality: Under correct assumptions, the Total Variation (TV) distance between the learned $\hat{M}$ and true $M$ converges to zero as dataset size increases.
• Policy Performance: Policies derived from the learned miss-MDP converge to the optimal policy value ($\pi^*$) as the approximation improves.
• Assumption Sensitivity: Incorrect assumptions (e.g., assuming MAR when the data is MNAR with self-censoring) lead to poor approximation and suboptimal policies.
• Comparison to Baselines: The proposed model-based approach significantly outperformed model-free baselines (PPO with/without memory, POMCP) on both benchmarks. The authors attribute the failure of model-free methods to their inability to effectively handle the specific partial observability structure of miss-MDPs, noting that these methods succeeded when missingness was removed.

Significance and Claims

The paper claims to bridge the gap between missing data theory and sequential decision-making. Its primary significance lies in providing a principled, model-based approach to handling missing data in POMDPs with statistical guarantees (PAC).

Unlike prior work that treats missingness as incidental or relies on imputation without guarantees, this work:

1. Explicitly models the missingness process.
2. Learns the missingness function from data with theoretical bounds on error.
3. Leverages this learned model to guarantee the near-optimality of the resulting policy.

The authors modestly note that their current approach assumes the underlying MDP transition function is known. They identify lifting this assumption and extending the framework to general miss-POMDPs as directions for future work. The empirical results confirm that their approach is superior to direct POMDP formulations (like POMCP) and deep reinforcement learning methods (like PPO) in settings where the missingness mechanism follows identifiable patterns.