mlsanityData to 7 Oct 2026

KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal

arXiv 2205.14211 ↗First posted 27 May 2022cs.LG cs.AI stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

In this work, we consider and analyze the sample complexity of model-free reinforcement learning with a generative model. Particularly, we analyze mirror descent value iteration (MDVI) by Geist et al. (2019) and Vieillard et al. (2020a), which uses the Kullback-Leibler divergence and entropy regularization in its value and policy updates. Our analysis shows that it is nearly minimax-optimal for finding an varepsilon-optimal policy when varepsilon is sufficiently small. This is the first theoretical result that demonstrates that a simple model-free algorithm without variance-reduction can be nearly minimax-optimal under the considered setting.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 16 of its 37 references that are in the map. First posted on arXiv 27 May 2022.

Builds on

16 of 37 references.

References · 16

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2019A Theory of Regularized Markov Decision Processescited by 279
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  6. 2017A unified view of entropy-regularized Markov decision processescited by 174
  7. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  8. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  9. 2015Taming the Noise in Reinforcement Learning via Soft Updatescited by 125
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  11. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  12. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
4 more
  1. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  2. 2020Munchausen Reinforcement Learningcited by 68
  3. 2017Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learningcited by 36
  4. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 4; 2024: 2; 2025: 2; 2026: 4.

13 papers.

Sort:

By area:

  1. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  2. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 44
  3. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 21
  4. 2026Future-KL Regularized GRPO: Process-Level Credit Assignment from f-Divergence Regularizationcited by 11
  5. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  6. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  7. 2026Near-Optimal Regret for KL-Regularized Multi-Armed Banditscited by 3
  8. 2023Generalized Munchausen Reinforcement Learning using Tsallis KL Divergencecited by 1
  9. 2023Guaranteed Trust Region Optimization via Two-Phase KL Penalizationcited by 1
  10. 2026Value Mirror Descent for Reinforcement Learningcited by 1
  11. 2024Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexitycited by 0
  12. 2025Mirror Descent Actor Critic via Bounded Advantage Learningcited by 0
1 more
  1. 2026Efficient Exploration for Iterative Nash Preference Optimizationcited by 0