# PEGASUS: A Policy Search Method for Large MDPs and POMDPs

arXiv: https://arxiv.org/abs/1301.3878 · HTML: https://mlsanity.com/paper/1301.3878/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2013.

## Built on by (most cited first, 22 of 22)

- [A Survey of Exploration Methods in Reinforcement Learning](https://mlsanity.com/paper/2109.00157/) (2021)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [Robot Learning from Randomized Simulations: A Review](https://mlsanity.com/paper/2111.00956/) (2021)
- [Discovering Evolution Strategies via Meta-Black-Box Optimization](https://mlsanity.com/paper/2211.11260/) (2022)
- [Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization](https://mlsanity.com/paper/2304.03995/) (2023)
- [Robust Predictable Control](https://mlsanity.com/paper/2109.03214/) (2021)
- [Hindsight Learning for MDPs with Exogenous Inputs](https://mlsanity.com/paper/2207.06272/) (2022)
- [Average-reward model-free reinforcement learning: a systematic review and literature mapping](https://mlsanity.com/paper/2010.08920/) (2020)
- [Model-Based Policy Search Using Monte Carlo Gradient Estimation with Real Systems Application](https://mlsanity.com/paper/2101.12115/) (2021)
- [Reinforcement Learning to Optimize Lifetime Value in Cold-Start Recommendation](https://mlsanity.com/paper/2108.09141/) (2021)
- [Agent-state based policies in POMDPs: Beyond belief-state MDPs](https://mlsanity.com/paper/2409.15703/) (2024)
- [Sample Average Approximation for Black-Box VI](https://mlsanity.com/paper/2304.06803/) (2023)
- [Using Common Random Numbers for Simulation-based Planning with Rollouts](https://mlsanity.com/paper/2605.04732/) (2026)
- [Learning to Look: Seeking Information for Decision Making via Policy Factorization](https://mlsanity.com/paper/2410.18964/) (2024)
- [A Bayesian Approach to Identifying Representational Errors](https://mlsanity.com/paper/2103.15171/) (2021)
- [Relative Sparsity for Medical Decision Problems](https://mlsanity.com/paper/2211.16566/) (2022)
- [A View of the Certainty-Equivalence Method for PAC RL as an Application of the Trajectory Tree Method](https://mlsanity.com/paper/2501.02652/) (2025)
- [The Parametric Cost Function Approximation: A new approach for multistage stochastic programming](https://mlsanity.com/paper/2201.00258/) (2022)
- [Joint MDPs and Reinforcement Learning in Coupled-Dynamics Environments](https://mlsanity.com/paper/2603.06946/) (2026)
- [Treatment, evidence, imitation, and chat](https://mlsanity.com/paper/2506.23040/) (2025)
- [Luck Is Not Skill: When Do Paired Rollouts Help Group-Relative RL of LLM Agents?](https://mlsanity.com/paper/2609.24144/) (2026)
- [FlowCred: Hierarchical Credit Assignment and Functional Coordination for Joint Text-to-Video Post-Training](https://mlsanity.com/paper/2610.18142/) (2026)

## Abstract (arXiv)

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.