# Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlo

arXiv: https://arxiv.org/abs/2503.21224 · HTML: https://mlsanity.com/paper/2503.21224/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 27 Mar 2025.

## Builds on (most cited first, 19 of 19)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Taming the Noise in Reinforcement Learning via Soft Updates](https://mlsanity.com/paper/1512.08562/) (2015)
- [Policy Gradient and Actor-Critic Learning in Continuous Time and Space: Theory and Algorithms](https://mlsanity.com/paper/2111.11232/) (2021)
- [Approximately Solving Mean Field Games via Entropy-Regularized Deep Reinforcement Learning](https://mlsanity.com/paper/2102.01585/) (2021)
- [Entropy Regularization for Mean Field Games with Learning](https://mlsanity.com/paper/2010.00145/) (2020)
- [Q-Learning in Regularized Mean-field Games](https://mlsanity.com/paper/2003.12151/) (2020)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Planning in Markov Decision Processes with Gap-Dependent Sample Complexity](https://mlsanity.com/paper/2006.05879/) (2020)
- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Convergence of policy gradient methods for finite-horizon exploratory linear-quadratic control problems](https://mlsanity.com/paper/2211.00617/) (2022)
- [A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces](https://mlsanity.com/paper/2310.02951/) (2023)
- [Regularity and stability of feedback relaxed controls](https://mlsanity.com/paper/2001.03148/) (2020)
- [Fast Policy Learning for Linear Quadratic Control with Entropy Regularization](https://mlsanity.com/paper/2311.14168/) (2023)
- [Nonlinear Monte Carlo methods with polynomial runtime for Bellman equations of discrete time high-dimensional stochastic optimal control problems](https://mlsanity.com/paper/2303.03390/) (2023)
- [Optimal randomized multilevel Monte Carlo for repeatedly nested expectations](https://mlsanity.com/paper/2301.04095/) (2023)

## Built on by (most cited first, 3 of 3)

- [Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergence](https://mlsanity.com/paper/2603.03523/) (2026)
- [Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing](https://mlsanity.com/paper/2609.06484/) (2026)
- [Mean-Field Generalisation Bounds for Learning Controls in Stochastic Environments](https://mlsanity.com/paper/2508.16001/) (2025)

## Abstract (arXiv)

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 dimensions or cardinalities of the state and action spaces, distinguishing our approach from existing algorithms whose complexities scale with the sizes of these spaces. We validate these theoretical performance guarantees through numerical experiments.