# Solving POMDPs by Searching in Policy Space

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

## Key facts

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

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

- [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)
- [Convergence of Finite Memory Q-Learning for POMDPs and Near Optimality of Learned Policies under Filter Stability](https://mlsanity.com/paper/2103.12158/) (2021)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (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)
- [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)
- [The Myhill-Nerode Theorem for Bounded Interaction: Canonical Abstractions via Agent-Bounded Indistinguishability](https://mlsanity.com/paper/2603.21399/) (2026)
- [Partially Observable Monte-Carlo Graph Search](https://mlsanity.com/paper/2507.20951/) (2025)
- [Bayesian Nonparametric Reinforcement Learning in LTE and Wi-Fi Coexistence](https://mlsanity.com/paper/2105.12249/) (2021)
- [Bayesian Nonparametric Modelling for Model-Free Reinforcement Learning in LTE-LAA and Wi-Fi Coexistence](https://mlsanity.com/paper/2107.02431/) (2021)
- [Memoryless Policy Iteration for Episodic POMDPs](https://mlsanity.com/paper/2512.11082/) (2025)

## Abstract (arXiv)

Most algorithms for solving POMDPs iteratively improve a value function that implicitly represents a policy and are said to search in value function space. This paper presents an approach to solving POMDPs that represents a policy explicitly as a finite-state controller and iteratively improves the controller by search in policy space. Two related algorithms illustrate this approach. The first is a policy iteration algorithm that can outperform value iteration in solving infinitehorizon POMDPs. It provides the foundation for a new heuristic search algorithm that promises further speedup by focusing computational effort on regions of the problem space that are reachable, or likely to be reached, from a start state.