On the Convergence of Reinforcement Learning with Monte Carlo Exploring Starts
A basic simulation-based reinforcement learning algorithm is the Monte Carlo Exploring States (MCES) method, also known as optimistic policy iteration, in which the value function is approximated by simulated returns and a greedy policy is selected at each iteration. The convergence of this algorithm in the general setting has been an open question. In this paper, we investigate the convergence of this algorithm for the case with undiscounted costs, also known as the stochastic shortest path problem. The results complement existing partial results on this topic and thereby helps further settle the open problem. As a side result, we also provide a proof of a version of the supermartingale convergence theorem commonly used in stochastic approximation.
Code (0)
등록된 구현이 없습니다.
Tasks
Open-Ended Question Answeringreinforcement-learningReinforcement Learning (RL)Similar Papers 제목 키워드 기반
Exploring Starts Are Not Enough: Counterexamples and a Fix for Monte Carlo Exploring Starts
The asymptotic behaviour of Monte Carlo Exploring Starts (MCES) is a long-standing open question in reinforcement learning, even in the tabular setting. We investigated the convergence properties of tabular MCES by const…
Reinforcement LearningFinite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
Monte Carlo Exploring Starts (MCES), which aims to learn the optimal policy using only sample returns, is a simple and natural algorithm in reinforcement learning which has been shown to converge under various conditions…
On the Convergence of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning
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 action…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Convergence Bounds for Sequential Monte Carlo on Multimodal Distributions using Soft Decomposition
We prove bounds on the variance of a function $f$ under the empirical measure of the samples obtained by the Sequential Monte Carlo (SMC) algorithm, with time complexity depending on local rather than global Markov chain…
Tail-Sensitive KL and Rényi Convergence of Unadjusted Hamiltonian Monte Carlo via One-Shot Couplings
Hamiltonian Monte Carlo (HMC) algorithms are among the most widely used sampling methods in high dimensional settings, yet their convergence properties are poorly understood in divergences that quantify relative density …