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

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

## Key facts

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

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (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)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Taming the Noise in Reinforcement Learning via Soft Updates](https://mlsanity.com/paper/1512.08562/) (2015)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Munchausen Reinforcement Learning](https://mlsanity.com/paper/2007.14430/) (2020)
- [Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learning](https://mlsanity.com/paper/1709.06293/) (2017)
- [Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning](https://mlsanity.com/paper/2106.14352/) (2021)

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

- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Towards Minimax Optimality of Model-based Robust Reinforcement Learning](https://mlsanity.com/paper/2302.05372/) (2023)
- [Future-KL Regularized GRPO: Process-Level Credit Assignment from f-Divergence Regularization](https://mlsanity.com/paper/2601.10201/) (2026)
- [Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Bandits](https://mlsanity.com/paper/2502.06051/) (2025)
- [Near-Optimal Regret for KL-Regularized Multi-Armed Bandits](https://mlsanity.com/paper/2603.02155/) (2026)
- [Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice](https://mlsanity.com/paper/2305.13185/) (2023)
- [Generalized Munchausen Reinforcement Learning using Tsallis KL Divergence](https://mlsanity.com/paper/2301.11476/) (2023)
- [Guaranteed Trust Region Optimization via Two-Phase KL Penalization](https://mlsanity.com/paper/2312.05405/) (2023)
- [Mirror Descent Actor Critic via Bounded Advantage Learning](https://mlsanity.com/paper/2502.03854/) (2025)
- [Value Mirror Descent for Reinforcement Learning](https://mlsanity.com/paper/2604.06039/) (2026)
- [Variance-Reduced Cascade Q-learning: Algorithms and Sample Complexity](https://mlsanity.com/paper/2408.06544/) (2024)
- [Efficient Exploration for Iterative Nash Preference Optimization](https://mlsanity.com/paper/2606.01382/) (2026)

## 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.