# The Role of Lookahead and Approximate Policy Evaluation in Reinforcement Learning with Linear Value Function Approximation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 40 references that are in the map.
- First posted on arXiv 28 Sep 2021.

## Builds on (most cited first, 16 of 16)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Monte Carlo Tree Search: A Review of Recent Modifications and Applications](https://mlsanity.com/paper/2103.04931/) (2021)
- [Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks](https://mlsanity.com/paper/1909.12292/) (2019)
- [Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control](https://mlsanity.com/paper/2108.10315/) (2021)
- [Beyond the One Step Greedy Approach in Reinforcement Learning](https://mlsanity.com/paper/1802.03654/) (2018)
- [How to Combine Tree-Search Methods in Reinforcement Learning](https://mlsanity.com/paper/1809.01843/) (2018)
- [Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups](https://mlsanity.com/paper/1406.0486/) (2014)
- [Local Search for Policy Iteration in Continuous Control](https://mlsanity.com/paper/2010.05545/) (2020)
- [Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning](https://mlsanity.com/paper/1805.07956/) (2018)
- [On Reinforcement Learning for Turn-based Zero-sum Markov Games](https://mlsanity.com/paper/2002.10620/) (2020)
- [Non-Asymptotic Analysis of Monte Carlo Tree Search](https://mlsanity.com/paper/1902.05213/) (2019)

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

- [Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithms](https://mlsanity.com/paper/2302.01450/) (2023)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach](https://mlsanity.com/paper/2510.18687/) (2025)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)
- [Generalization and Optimization of SGD with Lookahead](https://mlsanity.com/paper/2509.15776/) (2025)

## Abstract (arXiv)

Function approximation is widely used in reinforcement learning to handle the computational difficulties associated with very large state spaces. However, function approximation introduces errors which may lead to instabilities when using approximate dynamic programming techniques to obtain the optimal policy. Therefore, techniques such as lookahead for policy improvement and m-step rollout for policy evaluation are used in practice to improve the performance of approximate dynamic programming with function approximation. We quantitatively characterize, for the first time, the impact of lookahead and m-step rollout on the performance of approximate dynamic programming (DP) with function approximation: (i) without a sufficient combination of lookahead and m-step rollout, approximate DP may not converge, (ii) both lookahead and m-step rollout improve the convergence rate of approximate DP, and (iii) lookahead helps mitigate the effect of function approximation and the discount factor on the asymptotic performance of the algorithm. Our results are presented for two approximate DP methods: one which uses least-squares regression to perform function approximation and another which performs several steps of gradient descent of the least-squares objective in each iteration.