# On The Convergence Of Policy Iteration-Based Reinforcement Learning With Monte Carlo Policy Evaluation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 23 Jan 2023.

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

- [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)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [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)
- [From Reinforcement Learning to Optimal Control: A unified framework for sequential decisions](https://mlsanity.com/paper/1912.03513/) (2019)
- [Monte Carlo Tree Search with Heuristic Evaluations using Implicit Minimax Backups](https://mlsanity.com/paper/1406.0486/) (2014)
- [On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning](https://mlsanity.com/paper/2002.03585/) (2020)
- [On the convergence of optimistic policy iteration for stochastic shortest path problem](https://mlsanity.com/paper/1808.08763/) (2018)
- [On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts](https://mlsanity.com/paper/2007.10916/) (2020)
- [Multiple-Step Greedy Policies in Online and Approximate Reinforcement Learning](https://mlsanity.com/paper/1805.07956/) (2018)
- [Optimistic Policy Iteration for MDPs with Acyclic Transient State Structure](https://mlsanity.com/paper/2102.00030/) (2021)
- [Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation](https://mlsanity.com/paper/2210.07338/) (2022)
- [Monte-Carlo Tree Search for Policy Optimization](https://mlsanity.com/paper/1912.10648/) (2019)

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

- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [On the Convergence of Policy Mirror Descent with Temporal Difference Evaluation](https://mlsanity.com/paper/2509.18822/) (2025)
- [Convergence of Monte Carlo Optimistic Policy Iteration: Beyond Uniform State-Action Updates](https://mlsanity.com/paper/2606.10580/) (2026)
- [Scaling policy iteration based reinforcement learning for unknown discrete-time linear systems](https://mlsanity.com/paper/2411.07825/) (2024)
- [Stochastic Path Planning in Correlated Obstacle Fields](https://mlsanity.com/paper/2509.19559/) (2025)
- [A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games](https://mlsanity.com/paper/2303.09716/) (2023)
- [Simulation-Based Optimistic Policy Iteration For Multi-Agent MDPs with Kullback-Leibler Control Cost](https://mlsanity.com/paper/2410.15156/) (2024)
- [Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization](https://mlsanity.com/paper/2601.17570/) (2026)
- [Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts](https://mlsanity.com/paper/2606.15247/) (2026)

## Abstract (arXiv)

A common technique in reinforcement learning is to evaluate the value function from Monte Carlo simulations of a given policy, and use the estimated value function to obtain a new policy which is greedy with respect to the estimated value function. A well-known longstanding open problem in this context is to prove the convergence of such a scheme when the value function of a policy is estimated from data collected from a single sample path obtained from implementing the policy (see page 99 of [Sutton and Barto, 2018], page 8 of [Tsitsiklis, 2002]). We present a solution to the open problem by showing that a first-visit version of such a policy iteration scheme indeed converges to the optimal policy provided that the policy improvement step uses lookahead [Silver et al., 2016, Mnih et al., 2016, Silver et al., 2017b] rather than a simple greedy policy improvement. We provide results both for the original open problem in the tabular setting and also present extensions to the function approximation setting, where we show that the policy resulting from the algorithm performs close to the optimal policy within a function approximation error.