Perseus: Randomized Point-based Value Iteration for POMDPs

By Matthijs T. J. Spaan, Nikos A. Vlassis. 2005

785 citations recorded by the source corpus.

Partially observable Markov decision processes (POMDPs) form an attractive and principled framework for agent planning under uncertainty. Point-based approximate techniques for POMDPs compute a policy based on a finite set of points collected in advance from the agent's belief space. We present a randomized point-based value iteration algorithm called PERSEUS. The algorithm performs approximate value backup stages, ensuring that in each backup stage the value of each point in the belief set is improved; the key observation is that a single backup may improve the value of many belief points. Contrary to other point-based methods, PERSEUS backs up only a (randomly selected) subset of points in the belief set, sufficient for improving the value of each belief point in the set. We show how the same idea can be extended to dealing with continuous action spaces. Experimental results show the potential of PERSEUS in large scale POMDP problems.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Hilbert Space Embeddings of POMDPs (2012, methodology): “These include tractable parametric models of the system (parametric POMDPs [Poupart et al., 2006, Even-dar, 2005]); Monte Carlo methods for more complex models (Monte Carlo POMDPs [Silver and Veness, 2010, Thrun, 2000]); and methods that take advantage of the piece-wise linear and convex (PWLC) prop”
Optimal and Approximate Q-value Functions for Decentralized POMDPs (2008, methodology): “This property is exploited by many approximate POMDP solution methods (Pineau, Gordon, & Thrun, 2003; Spaan & Vlassis, 2005).”
Winning Isn't Everything: Training Human-Like Agents for Playtesting and Game AI (2019, background): “While the problem of a huge state space [39], [40], [41], a continuous action space [42], and a parametric actions space [43] could be dealt with, these techniques are not directly applicable to our problem.”
Point-Based Value Iteration for Continuous POMDPs (2006, methodology): “This is exploited by recent point-based POMDP algorithms to efficiently approximate Vn on a fixed set of belief points (Pineau et al., 2003a; Spaan and Vlassis, 2005).”
Convex Optimization: Algorithms and Complexity (2015, positive): “The set of α-functions can then be constructed incrementally by applying Bellman updates at the sampled hyper-states using standard point-based POMDP methods [Spaan and Vlassis, 2005, Pineau et al., 2003].”
Partially observable Markov decision processes for spoken dialog systems (2007, neutral): “To illustrate how this POMDP framework is used in a spoken dialog system, an example will now be presented in some detail.”
A Survey of Multi-Objective Sequential Decision-Making (2013, methodology): “Approximate point-based POMDP methods (Spaan & Vlassis, 2005; Pineau, Gordon, & Thrun, 2006) do not meet conditions (1) and (2) but could be adapted to compute an approximate convex hull, by choosing a prior distribution for the weights from which they could sample.”
POMDP-Based Statistical Spoken Dialog Systems: A Review (2013, methodology): “These models define a classical POMDP in summary space and admit standard methods for planning under uncertainty, including different versions of point-based value iteration [16], [18], SARSOP [52], heuristic search value iteration [17], [19], and short lookaheads [22], [53].”
Decentralized planning under uncertainty for teams of communicating agents (2006, methodology): “Perseus: Randomized point-based value iteration for POMDPs.”
A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes (2011, methodology): “Online POMDP solvers (Paquet et al., 2005; Ross et al., 2008c) have a clear advantage over offline finite POMDP solvers (Pineau et al., 2003; Spaan and Vlassis, 2005; Smith and Simmons, 2004) in the context of the BAPOMDP as they can be applied directly in infinite POMDPs, provided we have an…”
Bayesian Reinforcement Learning (2010, methodology): “For instance, Poupart et al (2006) proposed the BEETLE algorithm for Bayesian RL, which is an extension of the Perseus algorithm for discrete POMDPs (Spaan and Vlassis, 2005).”
QueryPOMDP: POMDP-Based Communication in Multiagent Systems (2011, methodology): “This POMDP is then solved using the Perseus approximate solver [23].”
Multi-task Reinforcement Learning in Partially Observable Stochastic Environments (2009, background): “…planning algorithms (Sondik 1971 1978; Cheng 1988; Lovejoy 1991; Hansen 1997; Kaelbling et al. 1998; Poupart and Boutilier 2003; Pineau et al. 2003; Spaan and Vlassis 2005; Smith and Simmons 2005; Li et al. 2006ab) have been proposed, addressing problems of increasing complexity as the algorithms…”
Reinforcement Learning in Continuous State and Action Spaces (2012, background): “Its many derivatives include Perseus (Spaan and Vlassis, 2005), Delayed Q-learning (Strehl et al, 2006) and Bayesian Qlearning (Dearden et al, 1998; see also Chapter ??).”
Online Planning Algorithms for POMDPs (2008, methodology): “In the last few years, POMDPs have generated significant interest in the AI community and many approximation algorithms have been developed (Hauskrecht, 2000; Pineau, Gordon, & Thrun, 2003; Braziunas & Boutilier, 2004; Poupart, 2005; Smith & Simmons, 2005; Spaan & Vlassis, 2005).”
Control: A perspective (2014, methodology): “With the advent of powerful computation, the problem of “partially observed Markov decision processes,” (POMDPs) [606], has acquired great attention as a methodology for modeling and solving problems in machine learning and artificial intelligence [531,619,501,641,493,245,596].”