On The Convergence Of The Monte Carlo Exploring Starts Algorithm For Reinforcement Learning

Abstract

A simple and natural algorithm for reinforcement learning (RL) is Monte Carlo Exploring Starts (MCES), where the Q-function is estimated by averaging the Monte Carlo returns, and the policy is improved by choosing actions that maximize the current estimate of the Q-function. Exploration is performed by "exploring starts", that is, each episode begins with a randomly chosen state and action, and then follows the current policy to the terminal state. In the classic book on RL by Sutton & Barto (2018), it is stated that establishing convergence for the MCES algorithm is one of the most important remaining open theoretical problems in RL. However, the convergence question for MCES turns out to be quite nuanced. Bertsekas & Tsitsiklis (1996) provide a counter-example showing that the MCES algorithm does not necessarily converge. Tsitsiklis (2002) further shows that if the original MCES algorithm is modified so that the Q-function estimates are updated at the same rate for all state-action p

Stats

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

Related papers

• On The Convergence Of Reinforcement Learning With Monte Carlo Exploring Starts (2020)0.00
• Finite-sample Analysis Of The Monte Carlo Exploring Starts Algorithm For Reinforcement Learning (2024)0.00
• On The Convergence Of Policy Iteration-based Reinforcement Learning With Monte Carlo Policy Evaluation (2023)0.00
• Renewal Monte Carlo: Renewal Theory Based Reinforcement Learning (2018)7.50
• Guided Exploration In Reinforcement Learning Via Monte Carlo Critic Optimization (2022)0.00
• PC-MLP: Model-based Reinforcement Learning With Policy Cover Guided Exploration (2021)0.00
• The Effective Horizon Explains Deep RL Performance In Stochastic Environments (2023)3.42
• Uncertainty Quantification And Exploration For Reinforcement Learning (2019)6.77