mlsanityData to 14 Oct 2026

Sample Complexity of Variance-reduced Distributionally Robust Q-learning

arXiv 2305.18420 ↗First posted 28 May 2023cs.LG math.OC stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

Dynamic decision-making under distributional shifts is of fundamental interest in theory and applications of reinforcement learning: The distribution of the environment in which the data is collected can differ from that of the environment in which the model is deployed. This paper presents two novel model-free algorithms, namely the distributionally robust Q-learning and its variance-reduced counterpart, that can effectively learn a robust policy despite distributional shifts. These algorithms are designed to efficiently approximate the q-function of an infinite-horizon γ-discounted robust Markov decision process with Kullback-Leibler ambiguity set to an entry-wise ε-degree of precision. Further, the variance-reduced distributionally robust Q-learning combines the synchronous Q-learning with variance-reduction techniques to enhance its performance. Consequently, we establish that it attains a minimax sample complexity upper bound of tilde O(|S||A|(1-γ)-4ε-2), where S and A denote the state and action spaces. This is the first complexity result that is independent of the ambiguity size δ, thereby providing new complexity theoretic insights. Additionally, a series of numerical experiments confirm the theoretical findings and the efficiency of the algorithms in handling distributional shifts.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). Builds on 15 of its 39 references that are in the map. First posted on arXiv 28 May 2023.

Builds on

15 of 39 references.

References · 15

  1. 2018An Introduction to Deep Reinforcement Learningcited by 206
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  4. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  5. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  6. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  7. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learningcited by 83
  8. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 77
  9. 2019Variance-reduced Q-learning is minimax optimalcited by 73
  10. 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
  11. 2019Non-asymptotic Analysis of Biased Stochastic Approximation Schemecited by 45
  12. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
3 more
  1. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  2. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  3. 2020Sequential Transfer in Reinforcement Learning with a Generative Modelcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 14; 2026: 6.

29 papers.

Sort:

By area:

  1. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
  2. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  3. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  4. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  5. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  6. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
  7. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
  8. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  9. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 4
  10. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 4
  11. 2026Model-free policy gradient for discrete-time mean-field controlcited by 4
  12. 2025Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlocited by 3
17 more
  1. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  2. 2025DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertaintycited by 3
  3. 2025Planning and Learning in Average Risk-aware MDPscited by 2
  4. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 2
  5. 2026Online Robust Reinforcement Learning Through Monte-Carlo Planningcited by 2
  6. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learningcited by 1
  7. 2025Distributionally Robust Deep Q-Learningcited by 1
  8. 2025Distributionally Robust Self Paced Curriculum Reinforcement Learningcited by 1
  9. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  10. 2024Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spacescited by 0
  11. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  12. 2025Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Setscited by 0
  13. 2025OEUVRE: OnlinE Unbiased Variance-Reduced loss Estimationcited by 0
  14. 2026Robust Transfer Learning with Side Informationcited by 0
  15. 2026Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RLcited by 0
  16. 2026Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processescited by 0
  17. 2026Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processescited by 0