mlsanityData to 7 Oct 2026

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

arXiv 2109.13419 ↗First posted 28 Sep 2021cs.LG cs.AI cs.SYcited by 5

Not on the map. Why?

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.

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

Builds on

16 of 40 references.

References · 16

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  3. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 723
  4. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  5. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  6. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  7. 2021Monte Carlo Tree Search: A Review of Recent Modifications and Applicationscited by 158
  8. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
  9. 2021Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Controlcited by 22
  10. 2018Beyond the One Step Greedy Approach in Reinforcement Learningcited by 20
  11. 2018How to Combine Tree-Search Methods in Reinforcement Learningcited by 16
  12. 2014Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backupscited by 11
4 more
  1. 2020Local Search for Policy Iteration in Continuous Controlcited by 9
  2. 2018Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learningcited by 7
  3. 2020On Reinforcement Learning for Turn-based Zero-sum Markov Gamescited by 4
  4. 2019Non-Asymptotic Analysis of Monte Carlo Tree Searchcited by 1

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 2; 2025: 2.

5 papers.

  1. 2023Performance Bounds for Policy-Based Average Reward Reinforcement Learning Algorithmscited by 6
  2. 2024Policy Mirror Descent with Lookaheadcited by 6
  3. 2025Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approachcited by 3
  4. 2024Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Costcited by 0
  5. 2025Generalization and Optimization of SGD with Lookaheadcited by 0