Online Planning Algorithms for POMDPs

By Stéphane Ross, Joelle Pineau, Sébastien Paquet, Brahim Chaib-draa. 2008

607 citations recorded by the source corpus.

Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Hilbert Space Embeddings of POMDPs (2012, methodology): “H is known to be isotonic, contractive, and Vd is guaranteed to be more accurate than Vd−1; that is, if Vd−1 satisfies ε = supb |V ∗(b)− Vd−1(b)|, then Vd has an error bound of |V ∗(b)− V̂d(b)| ≤ γε where γ ∈ (0, 1) [Ross et al., 2008].”
Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings (2021, background): “…is intractable for all but the smallest problems, most work focuses on approximate solutions, including of-ﬂine methods to compute approximate policies as well as approximate search algorithms, although these are still typically restricted to small grid-world environments (Ross et al., 2008).”
Deep Variational Reinforcement Learning for POMDPs (2018, background): “…POMDP literature focusses on planning algorithms, where the transition and observation functions, as well as a representation of the latent state space, are known (Barto et al., 1995; McAllester & Singh, 1999; Pineau et al., 2003; Ross et al., 2008; Oliehoek et al., 2008; Roijers et al., 2015).”
Intention-aware online POMDP planning for autonomous driving in a crowd (2015, background): “In contrast, online planning interleaves planning and plan execution (see, e.g., [6], [12], [15], [17]).”
DESPOT: Online POMDP Planning with Regularization (2013, methodology): “AEMS2 is an early successful online POMDP algorithm [16, 17].”
Scalable Planning and Learning for Multiagent POMDPs (2014, methodology): “POMCP and similar sample-based planning methods have already been shown to be state-of-the-art methods in both POMDP planning Silver and Veness (2010) and learning Ross et al.”
Adaptive Information Gathering via Imitation Learning (2017, background): “Online POMDP planning also has a large body of work (see Ross et al. [32]).”
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization (2010, methodology): “Unfortunately, solving POMDPs is PSPACE hard (Papadimitriou and Tsitsiklis, 1987), thus typically heuristic algorithms with no approximation guarantees are applied (Pineau et al., 2006; Ross et al., 2008).”
Learning deep neural network policies with continuous memory states (2015, background): “Discrete partially observed tasks have been tackled using a variety of reinforcement learning and dynamic programming methods [11], [1].”
Policy Learning with Continuous Memory States for Partially Observed Robotic Control (2015, background): “Discrete partially observed tasks have been tackled using a variety of reinforcement learning and dynamic programming methods [12, 13].”
Convex Optimization: Algorithms and Complexity (2015, positive): “We can extend the BAMDP model to capture uncertainty over the parameters of a POMDP (as defined in §2.3) by introducing the BayesAdaptive POMDP (BAPOMDP) model [Ross et al., 2008a, 2011].”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “The literature on online planning algorithms in this setting is large and we refer the interested reader to [Ross et al., 2008] for a complete overview.”
Potential-based reward shaping for finite horizon online POMDP planning (2016, methodology): “[18] for a recent survey of online planning methods).”
A survey of uncertainty in deep neural networks (2021, methodology): “In case of planning and control, estimation problems are widely treated as Bayesian sequential learning problems, and sequential decision making frameworks such as POMDPs [310], [311] assume a probabilistic treatment of the underlying planning problems.”
Algorithms for Reinforcement Learning (2010, background): “The multi-step extension of SARSA follows along the lines of the similar extension of TD(0), giving rise to the SARSA(λ) algorithm due to Rummery and Niranjan (1994); Rummery (1995).”
Monte-Carlo Planning in Large POMDPs (2010, methodology): “When provided with an exactly factored representation, online full-width planners have been successful in rocksample (7, 8) [13], and an offline full-width planner has been successful in the much larger rocksample (11, 11) problem [11].”