Efficient Learning For Entropy-regularized Markov Decision Processes Via Multilevel Monte Carlo

Abstract

Designing efficient learning algorithms with complexity guarantees for Markov decision processes (MDPs) with large or continuous state and action spaces remains a fundamental challenge. We address this challenge for entropy-regularized MDPs with Polish state and action spaces, assuming access to a generative model of the environment. We propose a novel family of multilevel Monte Carlo (MLMC) algorithms that integrate fixed-point iteration with MLMC techniques and a generic stochastic approximation of the Bellman operator. We quantify the precise impact of the chosen approximate Bellman operator on the accuracy of the resulting MLMC estimator. Leveraging this error analysis, we show that using a biased plain MC estimate for the Bellman operator results in quasi-polynomial sample complexity, whereas an unbiased randomized multilevel approximation of the Bellman operator achieves polynomial sample complexity in expectation. Notably, these complexity bounds are independent of the dimension

Stats

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

Related papers

• Robust Anytime Learning Of Markov Decision Processes (2022)0.00
• Parameterized Mdps And Reinforcement Learning Problems -- A Maximum Entropy Principle Based Framework (2020)8.60
• Randomized Exploration For Reinforcement Learning With Multinomial Logistic Function Approximation (2024)0.00
• Projection By Convolution: Optimal Sample Complexity For Reinforcement Learning In Continuous-space Mdps (2024)0.00
• Entropic Regularization Of Markov Decision Processes (2019)6.77
• Sample-efficient Reinforcement Learning For Linearly-parameterized Mdps With A Generative Model (2021)0.00
• Optimal Sample Complexity For Average Reward Markov Decision Processes (2023)0.00
• Model-based Reinforcement Learning With Multinomial Logistic Function Approximation (2022)2.26