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

2022/05/27 by Tadashi Kozuno, Kozuno, Tadashi, Wenhao Yang +23
Computer Science · #Adversarial Robustness in Machine Learning #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2205.14211

openalex publication_date 2022/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 ε-optimal policy when ε 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.

Related

• Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice
• Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm
• Model-Based Reinforcement Learning with a Generative Model is Minimax\n Optimal
• Matryoshka Policy Gradient for Entropy-Regularized RL: Convergence and Global Optimality
• Towards Minimax Optimality of Model-based Robust Reinforcement Learning