mlsanityData to 14 Oct 2026

Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice

arXiv 2305.13185 ↗First posted 22 May 2023cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

Mirror descent value iteration (MDVI), an abstraction of Kullback-Leibler (KL) and entropy-regularized reinforcement learning (RL), has served as the basis for recent high-performing practical RL algorithms. However, despite the use of function approximation in practice, the theoretical understanding of MDVI has been limited to tabular Markov decision processes (MDPs). We study MDVI with linear function approximation through its sample complexity required to identify an varepsilon-optimal policy with probability 1-δ under the settings of an infinite-horizon linear MDP, generative model, and G-optimal design. We demonstrate that least-squares regression weighted by the variance of an estimated optimal value function of the next state is crucial to achieving minimax optimality. Based on this observation, we present Variance-Weighted Least-Squares MDVI (VWLS-MDVI), the first theoretical algorithm that achieves nearly minimax optimal sample complexity for infinite-horizon linear MDPs. Furthermore, we propose a practical VWLS algorithm for value-based deep RL, Deep Variance Weighting (DVW). Our experiments demonstrate that DVW improves the performance of popular value-based deep RL algorithms on a set of MinAtar benchmarks.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 31 of its 59 references that are in the map. First posted on arXiv 22 May 2023.

Builds on

31 of 59 references.

References · 31

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2015Prioritized Experience Replaycited by 1,099
  4. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  5. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  6. 2022Learning robust perceptive locomotion for quadrupedal robots in the wildcited by 382
  7. 2019A Theory of Regularized Markov Decision Processescited by 286
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  9. 2020SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learningcited by 152
  10. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  11. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  12. 2019When to use parametric models in reinforcement learning?cited by 118
19 more
  1. 2019Diagnosing Bottlenecks in Deep Q-learning Algorithmscited by 73
  2. 2020DisCor: Corrective Feedback in Reinforcement Learning via Distribution Correctioncited by 71
  3. 2020Munchausen Reinforcement Learningcited by 69
  4. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 65
  5. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  6. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 55
  7. 2015Increasing the Action Gap: New Operators for Reinforcement Learningcited by 49
  8. 2021DeepThermal: Combustion Optimization for Thermal Power Generating Units Using Offline Reinforcement Learningcited by 48
  9. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  10. 2021Regularized Policies are Reward Robustcited by 32
  11. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  12. 2020Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexitycited by 28
  13. 2021Efficient Local Planning with Linear Function Approximationcited by 23
  14. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  15. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  16. 2022Confident Approximate Policy Iteration for Efficient Local Planning in qπ-realizable MDPscited by 8
  17. 2023Optimizing Audio Recommendations for the Long-Term: A Reinforcement Learning Perspectivecited by 8
  18. 2021ShinRL: A Library for Evaluating RL Algorithms from Theoretical and Practical Perspectivescited by 5
  19. 2022Best Policy Identification in Linear MDPscited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

4 papers.

  1. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  2. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  3. 2025Policy Testing in Markov Decision Processescited by 2
  4. 2026EasyPPO: Stabilizing the Critic Is Keycited by 0