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

Abstract

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 app

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keywinnicki2023on

Related papers

• On The Convergence Of Reinforcement Learning With Monte Carlo Exploring Starts (2020)0.00
• On The Convergence Of The Monte Carlo Exploring Starts Algorithm For Reinforcement Learning (2020)0.00
• On The Second-order Convergence Of Biased Policy Gradient Algorithms (2023)0.00
• Kalman Meets Bellman: Improving Policy Evaluation Through Value Tracking (2020)0.00
• An Approximate Policy Iteration Viewpoint Of Actor-critic Algorithms (2022)2.26
• Finite-sample Analysis Of The Monte Carlo Exploring Starts Algorithm For Reinforcement Learning (2024)0.00
• Certrl: Formalizing Convergence Proofs For Value And Policy Iteration In Coq (2020)5.84
• Adaptive Temporal-difference Learning For Policy Evaluation With Per-state Uncertainty Estimates (2019)0.00