Source-linked AI summary
Online algorithms for POMDPs with continuous state, action, and observation spaces
Zachary Sunberg, Mykel Kochenderfer
TL;DR
Continuous state, action, and observation spaces challenge online POMDP solvers because ordinary widening can leave beliefs collapsed and policies suboptimal. The paper proposes POMCPOW and PFT-DPW with weighted particle filtering, and reports that both overcome this challenge in experiments. Their practical use requires explicit observation-distribution knowledge, while PFT-DPW additionally requires choosing a static particle count.
Problem
Continuous spaces, especially continuous observations, challenge online POMDP solvers because DPW alone can collapse beliefs to one particle and yield suboptimal QMDP policies.
Method
The paper proposes POMCPOW and PFT-DPW, using weighted particle filtering with gradually expanding beliefs or approximate belief trajectories.
Results
POMCPOW and PFT-DPW overcome the challenge of choosing costly information-gathering actions in continuous spaces.
Takeaways & Limitations
The proposed algorithms provide a general-purpose online POMDP capability for continuous state, action, and observation spaces.
Takeaways & Limitations
PFT-DPW requires an a priori static particle count, trading off missed important states against expensive tree construction.
Abstract
from arXiv · showhide
Online solvers for partially observable Markov decision processes have been applied to problems with large discrete state spaces, but continuous state, action, and observation spaces remain a challenge. This paper begins by investigating double progressive widening (DPW) as a solution to this challenge. However, we prove that this modification alone is not sufficient because the belief representations in the search tree collapse to a single particle causing the algorithm to converge to a policy that is suboptimal regardless of the computation time. This paper proposes and evaluates two new algorithms, POMCPOW and PFT-DPW, that overcome this deficiency by using weighted particle filtering. Simulation results show that these modifications allow the algorithms to be successful where previous approaches fail.
1 Introduction
POMDP online solvers have advanced for large discrete problems, but continuous observation spaces remain difficult. The paper introduces POMCPOW and PFT-DPW to address continuous state, action, and observation spaces.
- POMDPs model sequential decisions where actions stochastically change hidden states and observations provide indirect information about those states.
- POMCP uses an unweighted particle filter to represent beliefs implicitly in its search tree.
- Continuous observation spaces cause simulations to create new observation nodes, preventing the search tree from extending deeper.
- The paper presents POMCPOW and PFT-DPW as online algorithms for POMDPs with continuous state, action, and observation spaces.
- DPW addresses tree-width growth, but belief representations can still collapse to one particle, producing overconfident, QMDP-like policies without information gathering.
2 Prior Work
Prior work includes offline and online POMDP solvers, with specialized methods for some continuous domains. A general-purpose solver for continuous observation spaces remains needed.
- Offline methods solve small and moderately sized POMDPs, whereas larger problems generally require online methods.
- Existing approaches address selected continuous problems through assumptions such as most-likely observations, Gaussian-process belief updates, or observation-space partitioning.
- POMCP shifted online planning toward shared simulations and implicitly represented beliefs composed of particles.
- DESPOT and ABT extend online planning through sparse random-outcome analysis and adaptation to environmental changes, respectively.
- General-purpose online solvers still need modification for continuous action or observation spaces, especially continuous information-gathering problems.
3 Background
POMDPs represent partially observed sequential decisions using beliefs, generative models, and Monte Carlo tree search. Continuous spaces make ordinary tree expansion shallow, motivating double progressive widening.
- 3.1 POMDPs: A POMDP extends an MDP with an observation space and observation model, while the state remains hidden from the agent.
- 3.1 POMDPs: A belief is the probability distribution over states inferred from the history of actions, observations, and initial information.
- 3.1 POMDPs: The belief is sufficient for optimal decision making, but exact Bayesian updates are computationally intensive, so particle filtering is commonly used.
- 3.1 POMDPs: A generative model samples next states, rewards, and observations, while the belief MDP treats beliefs as its state space.
- 3.2 MCTS: MCTS incrementally builds policy trees and estimates action values from simulations through a generative model.
- 3.2 MCTS: Continuous actions and states prevent repeated sampling of identical nodes, leaving ordinary MCTS trees too shallow for useful planning.
- Double Progressive Widening: Double progressive widening limits children according to visit count in both state and action spaces, reusing previously generated states after the limit is reached.
4 Algorithms
The section compares online POMDP solvers for continuous spaces, showing why DPW alone leaves belief representations degenerate and introducing weighted particle-filtering alternatives.
- 4.1 POMCP-DPW: POMCP-DPW limits newly sampled action and observation children using double progressive widening parameters.Its tree-search behavior differs from the other algorithms primarily through the SIMULATE function.
- 4.1 POMCP-DPW: Modified POMCP-DPW converges to a QMDP value and selects QMDP-like actions, which are suboptimal when information gathering matters.QMDP assumes the problem becomes fully observable after one time step and therefore neglects the value of information.
- 4.1 POMCP-DPW: In continuous observation spaces, POMCP-DPW belief nodes contain only one state particle because generated observations are almost surely unique.Consequently, each generated history effectively aliases a single state.
- 4.2 POMCPOW: POMCPOW uses weighted belief updates that expand gradually, allocating richer particle representations to more frequently visited beliefs.This contrasts with the single-particle degeneration of POMCP-DPW.
- 4.3 PFT-DPW: PFT-DPW applies double progressive widening to MCTS on the belief-space MDP, using particle-filter updates to approximate its generative model.Unlike POMCP and POMCPOW, it simulates approximate belief trajectories rather than state trajectories, supporting belief-dependent rewards.
- 4.3 PFT-DPW: PFT-DPW requires a fixed particle count m chosen in advance, creating a trade-off between missing important states and expensive tree construction.For the studied problems, m = 20 produced good performance.
5 Experiments
Experiments compare online POMDP solvers across benchmark domains with continuous spaces. POMCPOW and PFT-DPW generally handle information-gathering challenges better, while performance depends on problem structure.
- All solvers were limited to 1 second of computation time per step, with belief updates performed by an independent particle filter.
- Light Dark: In Light Dark, the optimal strategy moves toward the light region to localize before proceeding to the origin.POMCPOW and PFT-DPW perform better than QMDP-like solvers, while discretized POMCP performs best in this one-dimensional setting.
- Sub Hunt: In Sub Hunt, PFT-DPW achieves the best score, followed closely by POMCPOW, whereas other solvers perform similarly to QMDP.The optimal strategy includes active sonar despite its reduced engagement success rate when the target becomes aware.
- Van Der Pol Tag: In Van Der Pol tag, POMCPOW performs slightly better because each iteration is cheaper and therefore enables more random rollouts.The domain combines computationally expensive numerical integration with continuous states and obstacles that make heuristic rollouts difficult.
- Multilane: In multilane driving, DESPOT outperforms the other approaches because information can be gathered passively and tree depth and quality matter more than rich beliefs.POMCPOW significantly outperforms PFT-DPW in this environment.
6 Conclusion
The paper proposes a general-purpose online POMDP algorithm for continuous state, action, and observation spaces. Its experiments show that POMCPOW and PFT-DPW overcome difficulties with costly information gathering, but performance remains problem-dependent.
- The proposed algorithms solve problems with continuous state, action, and observation spaces, requiring explicit knowledge of the observation distribution.
- POMCPOW and PFT-DPW overcome the inability of previous solvers to choose costly information-gathering actions in continuous spaces.
- The theoretical properties of the algorithms remain to be proven, and better methods for choosing continuous actions could improve them.
Appendix A Discretization
The appendix evaluates discretization as a way to handle continuous observation and action spaces. Its effectiveness varies with dimensionality, granularity, solver, and hyperparameters.
- Discretization is only sometimes effective for continuous observation spaces, and Figure 6 examines performance across granularities in Light Dark and Sub Hunt.
- Light Dark: In Light Dark, fine discretization lets POMCP outperform POMCPOW, but effective granularity depends on the solver and possibly its hyperparameters.
- Sub Hunt: In Sub Hunt, discretization is ineffective at every granularity because the observation space is high-dimensional.
- Van Der Pol Tag: In Van Der Pol tag, both action and observation spaces require discretization, but no discretization produces effective results because of observation dimensionality.
Appendix B Hyperparameters
The experiments tune POMCPOW and PFT-DPW hyperparameters with the cross entropy method, but tuning was limited. Performance appears most sensitive to the exploration constant, while observation widening often uses small branching factors.
- Hyperparameters were selected using the cross entropy method, but exact tuning was not prioritized and some values were reused across solvers.The authors caution that the parameters may not be perfectly optimized and that available experiments do not support broad hyperparameter conclusions.
- Performance appears most sensitive to the exploration constant c.
- A small observation-widening α_o limits observations to approximately a fixed number k_o, allowing the tree to grow deeper.
- In practice, observation-widening branching factors k_o between 2 and 8 worked well across the studied problems.
Appendix C Proof of Theorem 1
Appendix C proves that modified POMCP-DPW converges to the QMDP value under continuous observations and the regularity hypothesis, rather than necessarily to the POMDP optimum. The proof recasts the algorithm as PUCT on an augmented fully observable MDP.
- Theorem statement: POMCP-DPW with DPW can converge to a sometimes-suboptimal solution, despite DPW’s optimal convergence guarantee on fully observable MDPs.The paper explicitly contrasts the fully observable guarantee with POMCP-DPW’s convergence behavior.
- Proof conclusion: After four algorithmic modifications, modified POMCP-DPW is equivalent to PUCT applied to the augmented MDP and therefore inherits exponential-sure convergence to its optimal value.The modifications include polynomial exploration, single-child expansion to maximum depth, least-visited proportional observation selection, and depth-dependent coefficients.
- Definitions: The QMDP value at belief b is the expected fully observable optimal state-action value over states distributed according to b.This definition identifies the limiting value computed by POMCP-DPW.
- Theorem statement: Under continuous state and observation spaces with finite observation density and the regularity hypothesis, modified POMCP-DPW converges to the QMDP value exponentially surely.The theorem states that the estimate converges to the QMDP value after n iterations with exponentially high probability.
- Proof construction: The proof defines an augmented fully observable MDP whose state space includes the original states and a special state representing the current belief.Its value function at the belief state equals the POMDP’s QMDP value.
- Proof construction: Because continuous observations are almost surely unique, each history stores only one state particle, making histories effectively aliases for state nodes.The proof uses this collapse to remove the state count and particle list, replacing them with a mapping from histories to augmented-MDP states.