Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlo
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918045228728320 |
|---|---|
| author | Meunier, Matthieu Reisinger, Christoph Zhang, Yufei |
| author_facet | Meunier, Matthieu Reisinger, Christoph Zhang, Yufei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21224 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlo Meunier, Matthieu Reisinger, Christoph Zhang, Yufei Machine Learning Optimization and Control Probability 65C05, 90C40 (Primary) 90C39, 60J20, 68Q32 (Secondary) 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. |
| title | Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlo |
| topic | Machine Learning Optimization and Control Probability 65C05, 90C40 (Primary) 90C39, 60J20, 68Q32 (Secondary) |
| url | https://arxiv.org/abs/2503.21224 |