# Sample Complexity of Variance-reduced Distributionally Robust Q-learning

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

## 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 (most cited first, 15 of 15)

- [An Introduction to Deep Reinforcement Learning](https://mlsanity.com/paper/1811.12560/) (2018)
- [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)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learning](https://mlsanity.com/paper/1905.06265/) (2019)
- [Variance-reduced Q-learning is minimax optimal](https://mlsanity.com/paper/1906.04697/) (2019)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Non-asymptotic Analysis of Biased Stochastic Approximation Scheme](https://mlsanity.com/paper/1902.00629/) (2019)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Sequential Transfer in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2007.00722/) (2020)

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

- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlation](https://mlsanity.com/paper/2307.07907/) (2023)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [On the Foundation of Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2311.09018/) (2023)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes](https://mlsanity.com/paper/2403.12946/) (2024)
- [Model-Free Robust Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2406.17096/) (2024)
- [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025)
- [Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Data](https://mlsanity.com/paper/2405.05468/) (2024)
- [Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning](https://mlsanity.com/paper/2506.07040/) (2025)
- [Model-free policy gradient for discrete-time mean-field control](https://mlsanity.com/paper/2601.11217/) (2026)
- [Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlo](https://mlsanity.com/paper/2503.21224/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty](https://mlsanity.com/paper/2506.12622/) (2025)
- [Planning and Learning in Average Risk-aware MDPs](https://mlsanity.com/paper/2503.17629/) (2025)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [Online Robust Reinforcement Learning Through Monte-Carlo Planning](https://mlsanity.com/paper/2609.18599/) (2026)
- [Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2505.12202/) (2025)
- [Distributionally Robust Deep Q-Learning](https://mlsanity.com/paper/2505.19058/) (2025)
- [Distributionally Robust Self Paced Curriculum Reinforcement Learning](https://mlsanity.com/paper/2511.05694/) (2025)
- [Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPs](https://mlsanity.com/paper/2511.05758/) (2025)
- [Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spaces](https://mlsanity.com/paper/2406.11281/) (2024)
- [Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation](https://mlsanity.com/paper/2510.01721/) (2025)
- [Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Sets](https://mlsanity.com/paper/2510.19950/) (2025)
- [OEUVRE: OnlinE Unbiased Variance-Reduced loss Estimation](https://mlsanity.com/paper/2510.22744/) (2025)
- [Robust Transfer Learning with Side Information](https://mlsanity.com/paper/2603.07921/) (2026)
- [Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL](https://mlsanity.com/paper/2605.08417/) (2026)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)
- [Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes](https://mlsanity.com/paper/2610.02131/) (2026)

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