# Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2018.

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

- [Generalised Policy Improvement with Geometric Policy Composition](https://mlsanity.com/paper/2206.08736/) (2022)
- [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)
- [The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation](https://mlsanity.com/paper/2109.13419/) (2021)
- [Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation](https://mlsanity.com/paper/2210.07338/) (2022)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)

## Abstract (arXiv)

Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work citeefroni2018beyond, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.