On the convergence of reinforcement learning with Monte Carlo exploring starts

DOI10.1016/J.AUTOMATICA.2021.109693MaRDI QIDQ2665181zbMATH OpenOpenAlexFDO

Authors Jun Liu

Publication date 18 November 2021

Published in Automatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.10916

zbMATH Keywords

convergenceMarkov decision processesMonte Carlo exploring startsoptimistic policy iterationreinforcement learningstochastic controlstochastic shortest path problem

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Markov and semi-Markov decision processes (90C40) Stochastic systems in control theory (general) (93E03)

Abstract: 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.

Recommendations

• 10.1162/153244303768966102
• Convergence results for single-step on-policy reinforcement-learning algorithms
• Simulation‐based Uniform Value Function Estimates of Markov Decision Processes
• \({\mathcal Q}\)-learning
• On the Convergence of Stochastic Iterative Dynamic Programming Algorithms

Cites work

• 10.1162/153244303768966102
• \({\mathcal Q}\)-learning
• A Stochastic Approximation Method
• An Analysis of Stochastic Shortest Path Problems
• Contraction Mappings in the Theory Underlying Dynamic Programming
• scientific article; zbMATH DE number 3538599 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• scientific article; zbMATH DE number 1095138 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 6846220 (Why is no real title available?)
• Probability with Martingales
• Q-learning and enhanced policy iteration in discounted dynamic programming
• Reinforcement learning. An introduction

Cited in

(7)

• Convergence results for single-step on-policy reinforcement-learning algorithms
• Reinforcement learning, sequential Monte Carlo and the EM algorithm
• 10.1162/153244303768966102
• Renewal Monte Carlo: Renewal Theory-Based Reinforcement Learning
• Improved DRL-based energy-efficient UAV control for maximum lifecycle
• Slowly changing adversarial bandit algorithms are efficient for discounted MDPs
• Markov decision processes: on the convergence of the Monte-Carlo first-visit algorithm

This page was built for publication: On the convergence of reinforcement learning with Monte Carlo exploring starts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2665181)