PEGASUS: A policy search method for large MDPs and POMDPs

By Andrew Y. Ng, Michael I. Jordan. 2000

501 citations recorded by the source corpus.

We propose a new approach to the problem of searching a space of policies for a Markov decision process (MDP) or a partially observable Markov decision process (POMDP), given a model. Our approach is based on the following observation: Any (PO)MDP can be transformed into an "equivalent" POMDP in which all state transitions (given the current state and action) are deterministic. This reduces the general problem of policy search to one in which we need only consider POMDPs with deterministic transitions. We give a natural way of estimating the value of all policies in these transformed POMDPs. Policy search is then simply performed by searching for a policy with high estimated value. We also establish conditions under which our value estimates will be good, recovering theoretical results similar to those of Kearns, Mansour and Ng [7], but with "sample complexity" bounds that have only a polynomial rather than exponential dependence on the horizon time. Our method applies to arbitrary POMDPs, including ones with infinite state and action spaces. We also present empirical results for our approach on a small discrete problem, and on a complex continuous state/continuous action problem involving learning to ride a bicycle.

Subfields: Artificial Intelligence, Computer Networks and Communications, Reinforcement Learning

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

In Reinforcement Learning

Citations in the corpus

Trust Region Policy Optimization (2015, background): “2 for additional discussion on Monte-Carlo estimation ofQ-values and [23] for further discussion of common random numbers in reinforcement learning.”
Search-based structured prediction (2009, neutral): “Single Monte-Carlo sampling: draw a single path and use the corresponding cost, with tied randomization as per Pegasus (Ng and Jordan 2000).”
PIPPS: Flexible Model-Based Policy Search Robust to the Curse of Chaos (2019, background): “The full update equations become: Deterministic optimizer: The random number seed can be ﬁxed to turn a stochastic problem deterministic, also known as the PEGASUS trick (Ng & Jordan, 2000).”
A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning (2010, methodology): “When carrying out direct policy search [Ng and Jordan, 2000], the Bayesian optimization approach has several advantages over the policy gradients method [Baxter and Bartlett, 2001]: it is derivative free, it is less prone to be caught in the first local minimum, and it is explicitly designed to…”
Autonomous helicopter control using reinforcement learning policy search methods (2001, methodology): “See [7] and [3] for more discussion about policy search and the complexity of uniform bounds on evaluations.”
Data-Efficient Reinforcement Learning with Probabilistic Model Predictive Control (2017, background): “The key idea is to reformulate the optimal control problem with learned GP models as an equivalent deterministic problem, an idea similar to [27].”
Robust Solutions to Markov Decision Problems with Uncertain Transition Matrices (2005, background): “Recent references on approximate dynamicprogramminginclude (Farias and Roy, 2002) and (Ng and Jordan, 2000).”
Policy Search using Paired Comparisons (2003, background): “The number of scenarios required for V PEG (w) to be a good estimate for V (w) is a polynomial in horizon time, and in various measures of the complexity of states, actions, rewards, system dynamics , and policies (Ng and Jordan, 2000).”
Policy Gradient Methods for Robotics (2006, background): “There are different ways of choosing the reference value J ref , e.g. forward-difference estimators with J ref = J ( θ h ) and central-difference estimators with J ref = J ( θ h − ∆ θ i ) .”
Finite-Time Bounds for Fitted Value Iteration (2008, methodology): “This model has been used in a number of previous works (e.g., Kearns et al., 1999; Ng and Jordan, 2000; Kakade and Langford, 2002; Kakade, 2003).”
Active Policy Learning for Robot Planning and Exploration under Uncertainty (2008, methodology): “Given a policy parameter vector and a set of fixed scenarios, the simulation is deterministic and yields an empirical estimate of the expected cost [25].”
Portfolio Allocation for Bayesian Optimization (2010, methodology): “The figure also shows that gradient based methods, even when using smart tricks such as PEGASUS [31], perform badly in comparison as the reward is severely multi-modal with large plateaus in between.”
TTree: Tree-Based State Generalization with Temporally Abstract Actions (2002, background): “Because future values decay exponentially, MAXTIME does not have to be very large to accurately approximate the trajectory value [12].”
A Survey of Collaborative Filtering Techniques (2009, background): “As the computational and representational complexity of POMDPs is high, appropriate approaches to tackling these problems must be developed, which are generally classified into three broad strategies: value function approximation [92], policy based optimization [84, 93], and stochastic sampling [94]”
Learning decisions: robustness, uncertainty, and approximation (2004, methodology): “The Pegasus algorithm, for instance, settles the sample complexity issue by providing a bound [Draft: 10 January 2005—11:1 ] CHAPTER 1.”
Synthesizing Neural Network Controllers with Probabilistic Model-Based Reinforcement Learning (2018, background): “Fixing random numbers in the context of policy search is known as the PEGASUS(1) algorithm [29].”