PaperlayerView exact revision on arXiv

Source-linked AI summary

DESPOT: Online POMDP Planning with Regularization

Nan Ye, Adhiraj Somani, David Hsu, Wee Sun Lee

arXiv:1609.03250v3cs.AI

TL;DR

POMDP planning is computationally difficult because belief and action-observation spaces grow exponentially. The paper introduces DESPOT, a sampled-scenario sparse tree with regularized anytime search, and reports near-optimal guarantees and strong performance on large and real-world tasks. Its scope includes a planning-time constraint and worst-case scenario requirements that may be exponentially large.

  • Problem

    POMDP planning faces computationally intractable optimal solution and approximation problems caused by the curses of dimensionality and history.

  • Method

    DESPOT sparsifies belief-tree search using sampled scenarios and combines anytime heuristic search with regularization penalizing large policies.

  • Results

    DESPOT yields a near-optimal policy when a compact near-optimal policy exists and shows strong performance, scaling to POMDPs with up to 10^56 states.

  • Takeaways & Limitations

    DESPOT is competitive with SARSOP and AEMS2 on moderate POMDPs, scales better, and matches or sometimes outperforms POMCP on large-scale POMDPs.

  • Takeaways & Limitations

    Online planning must produce actions within short time, and the required scenario count K may be exponentially large in the worst case.

Abstract

from arXiv · show

The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the "curse of dimensionality" and the "curse of history". To overcome these challenges, we introduce the Determinized Sparse Partially Observable Tree (DESPOT), a sparse approximation of the standard belief tree, for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the "execution" of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of the optimal policy. Leveraging this result, we give an anytime online planning algorithm, which searches a DESPOT for a policy that optimizes a regularized objective function. Regularization balances the estimated value of a policy under the sampled scenarios and the policy size, thus avoiding overfitting. The algorithm demonstrates strong experimental results, compared with some of the best online POMDP algorithms available. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online.

1. Introduction

POMDP planning is challenged by exponential growth in belief and action-observation spaces. DESPOT addresses these curses through sampled scenarios, regularized anytime search, and shows strong performance on large and real-world tasks.

  • Motivation: POMDPs provide a general framework for planning in partially observable stochastic environments, but optimal and approximate solutions are computationally difficult.The difficulty arises across applications including robot control, resource management, and medical diagnosis.
  • Motivation: The curse of dimensionality comes from exponential growth in states and beliefs, while the curse of history comes from exponential growth in action-observation histories.Together, these curses create major barriers to large-scale POMDP planning.
  • Approach: DESPOT is a sparse approximation of the belief tree that uses randomly sampled scenarios to represent policy execution under uncertainty.Sampling states and observations reduces the standard tree from O(|A|^D|Z|^D) belief nodes to O(|A|^DK) nodes, and the approximation converges as K grows.
  • Theory and results: K ∈ O(|π| ln(|π||A||Z|)) scenarios suffice for near-optimal lookahead when a near-optimal policy π has representation size |π|.Experiments also report that K as small as 500 can work well for some large POMDPs.
  • Approach: The algorithm combines incremental heuristic search with regularization that balances sampled-scenario value against policy size to reduce overfitting.It returns the best regularized action when the planning-time limit is reached; with an admissible heuristic, it eventually finds the optimal action given sufficient time.
  • Experiments and applications: The anytime DESPOT algorithm handles POMDPs with up to 10^56 states, achieves real-time autonomous-driving performance, and supports a winning autonomous mine-detection strategy.The driving system operated among many pedestrians, and the mine-detection strategy won the 2015 Humanitarian Robotics and Automation Technology Challenge.

2. Background

This section introduces POMDP beliefs, policies, value-based lookahead, and online planning, then places DESPOT among heuristic, pruning, and sampling approaches. DESPOT shares sparse-tree ideas with prior methods while using regularization and policy structure to address sampled-scenario overfitting and efficiency.

  • POMDP foundations: A POMDP models partially observable stochastic interaction with states, actions, observations, transitions, observation probabilities, and rewards.The agent does not directly know the state and instead maintains a belief distribution over possible states.
  • POMDP foundations: A belief is a sufficient statistic for the history of actions and observations, and Bayes’ rule updates it after each action-observation pair.The belief update is represented by the transition function τ.
  • POMDP foundations: A policy maps beliefs to actions, while its value is the expected total discounted reward under the policy.The discount factor γ expresses preference for immediate rewards over future rewards.
  • Online planning: Online planning repeatedly searches from the current belief, executes the best selected action immediately, receives an observation, and updates the belief.This local planning approach must produce an executable plan within short time in some applications.
  • Online planning: Truncated belief-tree search evaluates default policies at leaves and applies Bellman backups to choose the best root action.At internal nodes, action branches are maximized and observation branches are averaged using observation probabilities.
  • Related work: Prior online methods use heuristic search, branch-and-bound pruning, or Monte Carlo sampling, with rollout limited by its one-step lookahead horizon.Hindsight optimization builds separate scenario trees, whereas DESPOT shares a sparse tree across sampled scenarios.
  • Related work: DESPOT uses O(|A|^DK) nodes versus sparse sampling’s O(|A|^DC^D), and K can be much smaller than C^D when a small near-optimal policy exists.Its distinctive regularization balances estimated policy value and policy size to avoid overfitting sampled scenarios.
  • Contribution: The paper extends earlier work with an improved anytime planner, analysis of the algorithm, and new experimental results.The extension concerns the same sampled-scenario online-planning framework.

3. Determinized Sparse Partially Observable Trees

DESPOT sparsifies belief-tree planning by evaluating policies on randomly sampled scenarios, enabling compact approximate policy search. Its regularized objective trades sampled empirical value against policy size, with theoretical guarantees tied to compact policies.

  • DESPOT construction: A DESPOT captures all action branches but only observation branches encountered under K randomly sampled scenarios.It is a randomly sampled subtree of the standard belief tree, whose nodes also represent beliefs and scenario sets.
  • DESPOT construction: Each scenario determinizes uncertain execution into a trajectory, and the DESPOT encodes every policy’s execution under the fixed sampled scenario set.Scenario suffixes are assigned to reached belief nodes during constructive expansion.
  • Policy evaluation: The empirical value of a policy is its average total discounted reward across the scenarios passing through the relevant DESPOT node.As K increases, this empirical value converges almost surely to the policy’s belief-state value.
  • Regularization: Regularization penalizes large policy trees to control overfitting to finitely sampled scenarios.The resulting objective has the form of a regularized utility function balancing empirical value and policy size.
  • Guarantees: Maximizing the regularized bound yields a policy competitive with the best small policy, while K trades computation cost against approximation accuracy.The approximation error is correspondingly small when the optimal policy, or a good approximation to it, has small representation size.

4. Online Planning with DESPOTs

Online DESPOT planning searches incrementally with regularized value bounds, expanding promising subtrees while pruning expansions that are too large for the sampled evidence. The anytime algorithm returns the best action available when its error target or time budget is reached.

  • Online planning: The algorithm alternates action selection and particle-filter belief update, using either full DESPOT dynamic programming or incremental anytime heuristic search.Full construction is impractical for very large POMDPs, motivating the incremental method.
  • Regularized objective: The planner derives a policy maximizing regularized empirical value, where the penalty is weighted by policy-subtree size and scenario reach probability.The ratio |Φb|/K estimates the probability of reaching node b, while γ discounts future rewards.
  • Dynamic programming: At each node, dynamic programming compares expanding the subtree with executing the default policy, and expansion is beneficial only when the subtree is relatively small.Regularization prevents large subtrees when too few sampled scenarios support accurate value estimation.
  • Dynamic programming: The full dynamic-programming procedure runs in O(|A|DK) time after constructing the DESPOT.Its cost is linear in the number of DESPOT nodes.
  • Anytime heuristic search: Anytime search incrementally builds the DESPOT, maintains upper and lower RWDU bounds, and explores paths selected by heuristic uncertainty.It stops when the root gap reaches ϵ0 or the online planning time expires.
  • Anytime heuristic search: With an admissible heuristic, sufficient search time eventually yields the optimal action; the updated algorithm directly optimizes RWDU during construction.This differs from the earlier method, which constructed without regularization before optimizing afterward.
  • Anytime heuristic search: The anytime search constructs at most N(D+K) nodes, typically fewer than the full algorithm’s |A|DK nodes, at the cost of slightly more time per node.The overall trade-off is beneficial because pruning reduces DESPOT size.

4.3 Initial Upper Bounds

DESPOT initializes search with flexible upper and lower bounds, including hindsight-optimization variants, then analyzes how approximation error and partial search affect regularized-policy performance.

  • Upper-bound construction: Upper bounds can be initialized using uninformed bounds, hindsight optimization, approximate hindsight optimization, or domain-specific heuristics.Exact hindsight optimization can be pre-computed per scenario, while approximate variants trade tightness for simpler computation.
  • Upper-bound construction: Approximate upper bounds are acceptable because DESPOT is robust to their error, with performance degrading gracefully.This flexibility in constructing bounds is presented as a practical strength of DESPOT.
  • Upper-bound construction: The MDP hindsight-optimization bound averages fully observable optimal values over sampled start states, but is only an approximation to the sampled-scenario objective.It requires O(|S|^2|A|D) time with value iteration, potentially less for sparse transitions.
  • Default policies: Scenario-based default policies map beliefs to representative states and then select actions through a state-based policy, simplifying default-policy construction.The mode-MDP policy uses the most frequent sampled start state and an optimal policy for the underlying MDP.
  • Default policies: The mode-MDP default policy violates the independence assumption behind Theorem 3.1 and may overfit sampled scenarios, although its practical benefits may outweigh this concern.A default policy is simulated across scenarios to obtain the initial lower bound.
  • Anytime analysis: Anytime search incrementally builds a partial DESPOT and outputs its best regularized action, with performance approaching the full-tree optimum as planning time increases.With bounded planning time, the remaining root gap decreases monotonically with runtime; with unbounded time, finite-time guarantees require stated conditions such as δ=0 and λ>0 for exact optimality.

5. Experiments

The experiments compare DESPOT with established POMDP planners across domains from small to extremely large, and examine regularization, initialization choices, and search behavior. DESPOT shows strong overall performance, while regularization is especially useful when large observation spaces cause overfitting.

  • 5.1 Performance Comparison: The evaluation compares DESPOT with SARSOP, AEMS2, and POMCP using implementations run under the same experimental platform.
  • 5.1 Performance Comparison: DESPOT has strong overall performance: it matches SARSOP and AEMS2 on smaller domains and matches or sometimes outperforms POMCP on larger domains.
  • 5.1.1 TAG: On Tag, SARSOP achieves the best result, while AEMS2 and DESPOT have comparable performance and POMCP is much weaker.
  • 5.1.2 LASER TAG: With a very large observation space in Laser Tag, SARSOP and AEMS2 cannot run successfully, while DESPOT substantially outperforms POMCP.
  • 5.1.3 ROCK SAMPLE: On Rock Sample, DESPOT is the best online algorithm on RS(7, 8), matches SARSOP on RS(11, 11), and outperforms POMCP on the largest instance.
  • 5.2 Effect of Regularization: Regularization benefits Laser Tag and Pocman more significantly than Tag, Rock Sample, and Bridge Crossing, which have fewer observations.
  • 5.2 Effect of Regularization: With 50 observations, only about five scenarios reach each observation branch on average, making DESPOT prone to sampling variance and overfitting.
  • 5.2 Effect of Regularization: −6.06 ± 0.24 without regularization versus 0 ± 0 with regularization shows that regularization can recover the optimal reward in the examined setting.

6. Discussion

The discussion frames DESPOT as a flexible and robust approach whose sampled-scenario method can extend beyond POMDPs. It also identifies trade-offs involving search simplicity, large observation spaces, and default-policy quality.

  • Sampled scenarios provide an approximate uncertainty representation that works well when a compact, near-optimal policy exists.
  • The anytime DESPOT search is asymptotically sound and complete, robust to imperfect heuristics, and flexible enough to incorporate domain knowledge.
  • Compared with UCT, DESPOT trades greater robustness for additional bound-computation overhead and implementation complexity.
  • Large observation spaces, including those produced by cameras and laser range finders, may cause DESPOT to overfit sampled scenarios; regularization alleviates this difficulty.
  • A good default policy can reduce optimal-policy size and guide heuristic search, so incorporating domain knowledge into it is useful in practice.

7. Conclusions

DESPOT plans online POMDP actions from sampled scenarios while regularization controls overfitting. Experiments indicate strong performance, including scalability to large POMDPs where it matches or sometimes outperforms POMCP.

  • DESPOT plans according to sampled scenarios while avoiding overfitting to those samples.Its theoretical analysis supports this sampled-scenario approach and the use of regularization.
  • DESPOT is competitive with SARSOP and AEMS2 on moderately sized POMDPs while scaling better to larger problems.
  • On large-scale POMDPs with up to 1056 states, DESPOT matches and sometimes outperforms POMCP.

Proof of Theorem 3.1

The proof bounds how empirical values over sampled scenarios differ from true policy values by controlling policy-tree complexity and applying concentration arguments. The resulting guarantee penalizes larger policy representations.

  • Haussler’s bound controls deviations between empirical and expected values for the policy classes.The concentration argument assumes bounded i.i.d. random variables and applies a union bound across policy classes.
  • Policy trees are grouped by size, and their count is bounded using rooted-tree enumeration together with action and observation labels.The proof uses bounds involving |A|, |Z|, and the policy-tree size.
  • With probability at least 1 −τ, every DESPOT policy satisfies a regularized lower-bound expression involving empirical value, reward range, confidence, and policy size.The displayed bound includes the complexity term |π| ln(KD|A||Z|).
  • The proof treats the true policy value as an expectation over random scenarios and the empirical value as an average over K independently sampled scenarios.This connects the policy’s actual performance to its sampled-scenario estimate.

Proof of Theorem 3.2

The proof compares an arbitrary policy with a subtree that shares its sampled trajectories through the DESPOT horizon. It then combines empirical-value concentration with policy-size and truncation bounds to establish the theorem.

  • For a fixed policy, Hoeffding’s inequality bounds the difference between its true and empirical values.
  • The theorem considers policies derived from a DESPOT of height D built from K scenarios sampled from the initial belief.
  • A subtree of the arbitrary policy can preserve the same sampled trajectories through depth D while using no more policy nodes.The proof uses |π| ≥ |π′| and accounts for the value difference after depth D.
  • A union bound combines the concentration and subtree arguments to obtain the theorem’s near-optimality inequality.

Proof of Theorem 4.1 and Theorem 4.2

The analysis shows how DESPOT’s search bounds and pruning support regularized-policy guarantees. Finite target gaps yield near-optimality, while zero-gap search can terminate with an optimal regularized policy under stated conditions.

  • If a DESPOT node has positive exploration error, selecting the action with maximal expected value supports the search’s node-expansion argument.
  • Theorem 4.1 relates the partial-DESPOT policy value to the full-DESPOT optimum through the root gap and the upper-bound slack δ.The resulting loss is bounded by ϵ(b0) + δ.
  • When the target gap ϵ0 is positive, the anytime algorithm terminates in finite time with a near-optimal policy.
  • If ϵ0 = 0, δ = 0, and λ > 0, pruning limits expansion depth and finite search ends with an optimal regularized policy.
  • Only nodes within a suitable finite depth d0 need be considered, because deeper-node errors are bounded by discounted future rewards.
  • Since each considered node is expanded or closed at most once, the root gap eventually falls below ϵ0 and search terminates.

Appendix B. Pseudocode for Anytime DESPOT

Appendix B presents pseudocode for the Anytime DESPOT algorithm.

  • Algorithm 6 is titled “Anytime DESPOT.”
  • The appendix specifies the procedure for Anytime DESPOT.
  • Anytime DESPOT is presented as an algorithmic procedure in pseudocode.

Input

Anytime DESPOT samples scenarios from the current belief, builds and initializes a DESPOT, then repeatedly explores, expands, backs up, and prunes within time and depth limits.

  • Parameters: The DESPOT has maximum depth D, uses K sampled scenarios, targets gap-reduction rate ξ, and operates under per-step limit Tmax.
  • Initialization: The algorithm samples K scenarios randomly from the current belief b0 and creates a DESPOT with a single root node.
  • Initialization: It initializes U(b0), L0(b0), µ(b0), and ℓ(b0) at the root before exploration.
  • Anytime exploration: Exploration continues while the target gap exceeds ϵ0 and total running time remains below Tmax.
  • Tree expansion: When a leaf is reached, the algorithm expands one level and initializes U, L0, µ, and ℓ for each new child.
  • Backup: The procedure performs backups on µ(x), ℓ(x), and U(x) along the path from the explored node to the root.
Loading 1609.03250v3…