mlsanityData to 7 Oct 2026

Solving POMDPs by Searching the Space of Finite Policies

arXiv 1301.6720 ↗First posted 23 Jan 2013cs.AIcited by 25

Not on the map. Why?

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.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Jan 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 4; 2023: 5; 2024: 4; 2025: 4; 2026: 3.

25 papers.

Sort:

By area:

  1. 2024Bridging State and History Representations: Understanding Self-Predictive RLcited by 52
  2. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  3. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  4. 2023Safe Policy Improvement for POMDPs via Finite-State Controllerscited by 10
  5. 2023Decision-Making Under Uncertainty: Beyond Probabilitiescited by 8
  6. 2024Pessimistic Iterative Planning with RNNs for Robust POMDPscited by 7
  7. 2022Under-Approximating Expected Total Rewards in POMDPscited by 5
  8. 2025Robust Finite-Memory Policy Gradients for Hidden-Model POMDPscited by 5
  9. 2021Solving infinite-horizon Dec-POMDPs using Finite State Controllers within JESPcited by 4
  10. 2024Learning Explainable and Better Performing Representations of POMDP Strategiescited by 4
  11. 2021Computing Policies That Account For The Effects Of Human Agent Uncertainty During Execution In Markov Decision Processescited by 3
  12. 2021Task-Guided Inverse Reinforcement Learning Under Partial Informationcited by 2
13 more
  1. 2021Learning What to Memorize: Using Intrinsic Motivation to Form Useful Memory in Partially Observable Reinforcement Learningcited by 1
  2. 2022Task-Guided IRL in POMDPs that Scalescited by 1
  3. 2023Robust Robot Planning for Human-Robot Collaborationcited by 1
  4. 2023Monte-Carlo Search for an Equilibrium in Dec-POMDPscited by 1
  5. 2025Partially Observable Monte-Carlo Graph Searchcited by 1
  6. 2025Scaling Internal-State Policy-Gradient Methods for POMDPscited by 1
  7. 2026Finite-State Controllers for (Hidden-Model) POMDPs using Deep Reinforcement Learningcited by 1
  8. 2026Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPscited by 1
  9. 2021How memory architecture affects learning in a simple POMDP: the two-hypothesis testing problemcited by 0
  10. 2023Fast exploration and learning of latent graphs with aliased observationscited by 0
  11. 2024Anticipating Oblivious Opponents in Stochastic Gamescited by 0
  12. 2025Memoryless Policy Iteration for Episodic POMDPscited by 0
  13. 2026Robustness Analysis of POMDP Policies to Observation Perturbationscited by 0