# Beyond the One Step Greedy Approach in Reinforcement Learning

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2018.

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

- [Heuristic-Guided Reinforcement Learning](https://mlsanity.com/paper/2106.02757/) (2021)
- [Generalised Policy Improvement with Geometric Policy Composition](https://mlsanity.com/paper/2206.08736/) (2022)
- [Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction](https://mlsanity.com/paper/2107.01715/) (2021)
- [On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation](https://mlsanity.com/paper/2301.09709/) (2023)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation](https://mlsanity.com/paper/2109.13419/) (2021)
- [Spectral Bellman Method: Unifying Representation and Exploration in RL](https://mlsanity.com/paper/2507.13181/) (2025)
- [Policy Gradient with Tree Expansion](https://mlsanity.com/paper/2301.13236/) (2023)
- [Multi-Bellman operator for convergence of Q-learning with linear function approximation](https://mlsanity.com/paper/2309.16819/) (2023)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Highway Reinforcement Learning](https://mlsanity.com/paper/2405.18289/) (2024)
- [Counting Hours, Counting Losses: The Toll of Unpredictable Work Schedules on Financial Security](https://mlsanity.com/paper/2504.07719/) (2025)
- [Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead](https://mlsanity.com/paper/2506.07054/) (2025)
- [Monotone and Conservative Policy Iteration Beyond the Tabular Case](https://mlsanity.com/paper/2506.07134/) (2025)
- [Greedy-Step Off-Policy Reinforcement Learning](https://mlsanity.com/paper/2102.11717/) (2021)
- [Learning to Plan via a Multi-Step Policy Regression Method](https://mlsanity.com/paper/2106.10075/) (2021)
- [On the Convergence of Modified Policy Iteration in Risk Sensitive Exponential Cost Markov Decision Processes](https://mlsanity.com/paper/2302.03811/) (2023)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Partial Policy Gradients for RL in LLMs](https://mlsanity.com/paper/2603.06138/) (2026)

## Abstract (arXiv)

The famous Policy Iteration algorithm alternates between policy improvement and policy evaluation. Implementations of this algorithm with several variants of the latter evaluation stage, e.g, n-step and trace-based returns, have been analyzed in previous works. However, the case of multiple-step lookahead policy improvement, despite the recent increase in empirical evidence of its strength, has to our knowledge not been carefully analyzed yet. In this work, we introduce the first such analysis. Namely, we formulate variants of multiple-step policy improvement, derive new algorithms using these definitions and prove their convergence. Moreover, we show that recent prominent Reinforcement Learning algorithms are, in fact, instances of our framework. We thus shed light on their empirical success and give a recipe for deriving new algorithms for future study.