# Solving POMDPs by Searching the Space of Finite Policies

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2013.

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

- [Bridging State and History Representations: Understanding Self-Predictive RL](https://mlsanity.com/paper/2401.08898/) (2024)
- [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)
- [Safe Policy Improvement for POMDPs via Finite-State Controllers](https://mlsanity.com/paper/2301.04939/) (2023)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Pessimistic Iterative Planning with RNNs for Robust POMDPs](https://mlsanity.com/paper/2408.08770/) (2024)
- [Under-Approximating Expected Total Rewards in POMDPs](https://mlsanity.com/paper/2201.08772/) (2022)
- [Robust Finite-Memory Policy Gradients for Hidden-Model POMDPs](https://mlsanity.com/paper/2505.09518/) (2025)
- [Solving infinite-horizon Dec-POMDPs using Finite State Controllers within JESP](https://mlsanity.com/paper/2109.08755/) (2021)
- [Learning Explainable and Better Performing Representations of POMDP Strategies](https://mlsanity.com/paper/2401.07656/) (2024)
- [Computing Policies That Account For The Effects Of Human Agent Uncertainty During Execution In Markov Decision Processes](https://mlsanity.com/paper/2109.07436/) (2021)
- [Task-Guided Inverse Reinforcement Learning Under Partial Information](https://mlsanity.com/paper/2105.14073/) (2021)
- [Learning What to Memorize: Using Intrinsic Motivation to Form Useful Memory in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2110.12810/) (2021)
- [Task-Guided IRL in POMDPs that Scales](https://mlsanity.com/paper/2301.01219/) (2022)
- [Robust Robot Planning for Human-Robot Collaboration](https://mlsanity.com/paper/2302.13916/) (2023)
- [Monte-Carlo Search for an Equilibrium in Dec-POMDPs](https://mlsanity.com/paper/2305.11811/) (2023)
- [Partially Observable Monte-Carlo Graph Search](https://mlsanity.com/paper/2507.20951/) (2025)
- [Scaling Internal-State Policy-Gradient Methods for POMDPs](https://mlsanity.com/paper/2512.03204/) (2025)
- [Finite-State Controllers for (Hidden-Model) POMDPs using Deep Reinforcement Learning](https://mlsanity.com/paper/2602.08734/) (2026)
- [Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs](https://mlsanity.com/paper/2604.01024/) (2026)
- [How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problem](https://mlsanity.com/paper/2106.08849/) (2021)
- [Fast exploration and learning of latent graphs with aliased observations](https://mlsanity.com/paper/2303.07397/) (2023)
- [Anticipating Oblivious Opponents in Stochastic Games](https://mlsanity.com/paper/2409.11671/) (2024)
- [Memoryless Policy Iteration for Episodic POMDPs](https://mlsanity.com/paper/2512.11082/) (2025)
- [Robustness Analysis of POMDP Policies to Observation Perturbations](https://mlsanity.com/paper/2604.21256/) (2026)
- [On the Complexity Gap Between POMDPs and Multi-Environment POMDPs](https://mlsanity.com/paper/2610.15010/) (2026)

## Abstract (arXiv)

Solving partially observable Markov decision processes (POMDPs) is highly intractable in general, at least in part because the optimal policy may be infinitely large. In this paper, we explore the problem of finding the optimal policy from a restricted set of policies, represented as finite state automata of a given size. This problem is also intractable, but we show that the complexity can be greatly reduced when the POMDP and/or policy are further constrained. We demonstrate good empirical results with a branch-and-bound method for finding globally optimal deterministic policies, and a gradient-ascent method for finding locally optimal stochastic policies.