# Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2013.

## Built on by (most cited first, 24 of 24)

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [Planning in Observable POMDPs in Quasipolynomial Time](https://mlsanity.com/paper/2201.04735/) (2022)
- [LLM-Guided Probabilistic Program Induction for POMDP Model Estimation](https://mlsanity.com/paper/2505.02216/) (2025)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Intrusion Tolerance for Networked Systems through Two-Level Feedback Control](https://mlsanity.com/paper/2404.01741/) (2024)
- [Learning Logic Specifications for Soft Policy Guidance in POMCP](https://mlsanity.com/paper/2303.09172/) (2023)
- [Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach](https://mlsanity.com/paper/2402.19265/) (2024)
- [Periodic agent-state based Q-learning for POMDPs](https://mlsanity.com/paper/2407.06121/) (2024)
- [Welfare Maximization Algorithm for Solving Budget-Constrained Multi-Component POMDPs](https://mlsanity.com/paper/2303.10302/) (2023)
- [A Mathematical Characterization of Minimally Sufficient Robot Brains](https://mlsanity.com/paper/2308.09041/) (2023)
- [Sequential Monte Carlo for Policy Optimization in Continuous POMDPs](https://mlsanity.com/paper/2505.16732/) (2025)
- [Multi-Objective Coordination Graphs for the Expected Scalarised Returns with Generative Flow Models](https://mlsanity.com/paper/2207.00368/) (2022)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)
- [Rule-based Shielding for Partially Observable Monte-Carlo Planning](https://mlsanity.com/paper/2104.13791/) (2021)
- [Task-Guided Inverse Reinforcement Learning Under Partial Information](https://mlsanity.com/paper/2105.14073/) (2021)
- [Reconciling Rewards with Predictive State Representations](https://mlsanity.com/paper/2106.03926/) (2021)
- [Approximation Methods for Partially Observed Markov Decision Processes (POMDPs)](https://mlsanity.com/paper/2108.13965/) (2021)
- [Filter-Aware Model-Predictive Control](https://mlsanity.com/paper/2304.10246/) (2023)
- [Online Planning in POMDPs with State-Requests](https://mlsanity.com/paper/2407.18812/) (2024)
- [Towards Intention Recognition for Robotic Assistants Through Online POMDP Planning](https://mlsanity.com/paper/2411.17326/) (2024)
- [MDPs with a State Sensing Cost](https://mlsanity.com/paper/2505.03280/) (2025)
- [Fast exploration and learning of latent graphs with aliased observations](https://mlsanity.com/paper/2303.07397/) (2023)
- [A Novel Point-based Algorithm for Multi-agent Control Using the Common Information Approach](https://mlsanity.com/paper/2304.04346/) (2023)

## Abstract (arXiv)

Most exact algorithms for general partially observable Markov decision processes (POMDPs) use a form of dynamic programming in which a piecewise-linear and convex representation of one value function is transformed into another. We examine variations of the "incremental pruning" method for solving this problem and compare them to earlier algorithms from theoretical and empirical perspectives. We find that incremental pruning is presently the most efficient exact method for solving POMDPs.