# Missingness-MDPs: Bridging the Theory of Missing Data and POMDPs

arXiv: https://arxiv.org/abs/2605.12262 · HTML: https://mlsanity.com/paper/2605.12262/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 65 references that are in the map.
- First posted on arXiv 12 May 2026.

## Builds on (most cited first, 17 of 17)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Graphical Models for Processing Missing Data](https://mlsanity.com/paper/1801.03583/) (2018)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [POPCORN: Partially Observed Prediction COnstrained ReiNforcement Learning](https://mlsanity.com/paper/2001.04032/) (2020)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Full Law Identification In Graphical Models Of Missing Data: Completeness Results](https://mlsanity.com/paper/2004.04872/) (2020)
- [Identification In Missing Data Models Represented By Directed Acyclic Graphs](https://mlsanity.com/paper/1907.00241/) (2019)
- [Sublinear Regret for Learning POMDPs](https://mlsanity.com/paper/2107.03635/) (2021)
- [ASAC: Active Sensing using Actor-Critic models](https://mlsanity.com/paper/1906.06796/) (2019)
- [Optimal Cost Almost-sure Reachability in POMDPs](https://mlsanity.com/paper/1411.3880/) (2014)
- [Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddings](https://mlsanity.com/paper/2206.12081/) (2022)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Robust Reinforcement Learning in POMDPs with Incomplete and Noisy Observations](https://mlsanity.com/paper/1902.05795/) (2019)
- [Faster Statistical Model Checking for Unbounded Temporal Properties](https://mlsanity.com/paper/1504.05739/) (2015)
- [Efficient Algorithms for Bayesian Network Parameter Learning from Incomplete Data](https://mlsanity.com/paper/1411.7014/) (2014)
- [Sound Statistical Model Checking for Probabilities and Expected Rewards (extended version)](https://mlsanity.com/paper/2411.00559/) (2024)

## Abstract (arXiv)

We introduce missingness-MDPs (miss-MDPs), a novel subclass of partially observable Markov decision processes (POMDPs) that incorporates the theory of missing data. A miss-MDP is a POMDP whose observation function is a missingness function, specifying the probability that individual state features are missing (i.e., unobserved) at a time step. The literature distinguishes three canonical missingness types: missing (1) completely at random (MCAR), (2) at random (MAR), and (3) not at random (MNAR). Our planning problem is to compute near-optimal policies for a miss-MDP with an unknown missingness function, given a dataset of action-observation trajectories. Achieving such optimality guarantees for policies requires learning the missingness function from data, which is infeasible for general POMDPs. To overcome this challenge, we exploit the structural properties of different missingness types to derive probably approximately correct (PAC) algorithms for learning the missingness function. These algorithms yield an approximate but fully specified miss-MDP that we solve using off-the-shelf planning methods. We prove that, with high probability, the resulting policies are epsilon-optimal in the true miss-MDP. Empirical results confirm the theory and demonstrate superior performance of our approach over two model-free POMDP methods.