PEGASUS: A Policy Search Method for Large MDPs and POMDPs

Abstract

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 (1999), 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.

Appears in Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI2000)

References in corpus (1)

• Learning Finite-State Controllers for Partially Observable Environments

Cited by in corpus (34)

• Trust Region Policy Optimization
• A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning
• Gaussian Processes for Data-Efficient Learning in Robotics and Control
• Deep Reinforcement Learning for Page-wise Recommendations
• Recommendations with Negative Feedback via Pairwise Deep Reinforcement Learning
• Finding Approximate POMDP solutions Through Belief Compression
• DESPOT: Online POMDP Planning with Regularization
• Search-based Structured Prediction
• Body Schema Acquisition through Active Learning
• New inference strategies for solving Markov Decision Processes using reversible jump MCMC
• Efficient Gradient Estimation for Motor Control Learning
• Model-Based Policy Search Using Monte Carlo Gradient Estimation with Real Systems Application
• Monte Carlo Bayesian Reinforcement Learning
• A Sampling-Based Approach to Computing Equilibria in Succinct Extensive-Form Games
• On Minimax Optimal Offline Policy Evaluation
• Robust Predictable Control
• Monte-Carlo Planning: Theoretically Fast Convergence Meets Practical Efficiency
• A Credit Assignment Compiler for Joint Prediction
• Reinforcement Learning of POMDPs using Spectral Methods
• Locally Persistent Exploration in Continuous Control Tasks with Sparse Rewards
• Reinforcement Learning via Parametric Cost Function Approximation for Multistage Stochastic Programming
• A Survey of Exploration Methods in Reinforcement Learning
• On Value Functions and the Agent-Environment Boundary
• Real-Time Stochastic Predictive Control for Hybrid Vehicle Energy Management
• Stochastic Optimization with Parametric Cost Function Approximations
• Influence-aware Memory Architectures for Deep Reinforcement Learning
• Black-Box Data-efficient Policy Search for Robotics
• Efficient Learning and Planning with Compressed Predictive States
• FiDi-RL: Incorporating Deep Reinforcement Learning with Finite-Difference Policy Search for Efficient Learning of Continuous Control
• A Bayesian Approach to Identifying Representational Errors
• Optimal decentralized control of coupled subsystems with control sharing
• Unsupervised Search-based Structured Prediction
• Improving Gradient Estimation by Incorporating Sensor Data
• A Hybrid Approach for Trajectory Control Design