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

2013/02/06 by Anthony R. Cassandra, Michael L. Littman, Cassandra, Anthony R. +4 · 5 citations
Computer Science · #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #FOS: Computer and information sciences #Machine Learning and Algorithms #Reinforcement Learning in Robotics #cs.AI

paper · pdf · doi:10.48550/arxiv.1302.1525

Appears in Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence (UAI1997)

arxiv created 2013/02/06 · openalex publication_date 2013/02/06 · arxiv updated 2013/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• The Optimal Control of Partially Observable Markov Processes over a Finite Horizon

Cited by

• Remote Tracking with State-Dependent Sensing in Pull-Based Systems: A POMDP Framework
• Adaptive Network Security Policies via Belief Aggregation and Rollout
• MDPs with a State Sensing Cost
• Sequential Monte Carlo for Policy Optimization in Continuous POMDPs
• Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method
• Value-Directed Belief State Approximation for POMDPs
• LLM-Guided Probabilistic Program Induction for POMDP Model Estimation
• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• My Brain is Full: When More Memory Helps

Related

• Region-Based Incremental Pruning for POMDPs
• A Method for Speeding Up Value Iteration in Partially Observable Markov Decision Processes
• Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method
• Linear Programming for Decision Processes with Partial Information
• Recursively-Constrained Partially Observable Markov Decision Processes