Markov decision processes: on the convergence of the Monte-Carlo first visit algorithm

2025/01/15 by Delattre, Sylvain, Fournier, Nicolas
#FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR)

paper · doi:10.48550/arxiv.2501.08800

Abstract

We consider the Monte-Carlo first visit algorithm, of which the goal is to find the optimal control in a Markov decision process with finite state space and finite number of possible actions. We show its convergence when the discount factor is smaller than 1/2.

Related

• Markov Chain Monte Carlo on Finite State Spaces
• On the Convergence Rate of MCTS for the Optimal Value Estimation in Markov Decision Processes
• Mean Field Markov Decision Processes
• Convergence Rates of Posterior Distributions in Markov Decision Process
• On the Convergence of Optimal Actions for Markov Decision Processes and\n the Optimality of (s,S) Inventory Policies