mlsanityData to 7 Oct 2026

Near-Optimal Offline Reinforcement Learning via Double Variance Reduction

arXiv 2102.01748 ↗First posted 2 Feb 2021cs.LG cs.AI stat.MLcited by 56

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

We consider the problem of offline reinforcement learning (RL) -- a well-motivated setting of RL that aims at policy optimization using only historical data. Despite its wide applicability, theoretical understandings of offline RL, such as its optimal sample complexity, remain largely open even in basic settings such as tabular Markov Decision Processes (MDPs). In this paper, we propose Off-Policy Double Variance Reduction (OPDVR), a new variance reduction based algorithm for offline RL. Our main result shows that OPDVR provably identifies an ε-optimal policy with widetildeO(H2/dmε2) episodes of offline data in the finite-horizon stationary transition setting, where H is the horizon length and dm is the minimal marginal state-action distribution induced by the behavior policy. This improves over the best known upper bound by a factor of H. Moreover, we establish an information-theoretic lower bound of Omega(H2/dmε2) which certifies that OPDVR is optimal up to logarithmic factors. Lastly, we show that OPDVR also achieves rate-optimal sample complexity under alternative settings such as the finite-horizon MDPs with non-stationary transitions and the infinite horizon MDPs with discounted rewards.

Key facts. Cited by 56 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 38 of its 66 references that are in the map. First posted on arXiv 2 Feb 2021.

Builds on

38 of 66 references.

Closest ancestors · 6

Same direction, newest first

  1. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  3. 2020Batch Value-function Approximation with Only Realizability11 Aug
  4. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  5. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  6. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 32

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  6. 2019Batch Policy Learning under Constraintscited by 242
  7. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  12. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
20 more
  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  3. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  4. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  5. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  6. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  7. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  8. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  9. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 93
  10. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  11. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  12. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  13. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  14. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 56
  15. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  16. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  17. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 41
  18. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  19. 2019Understanding the Curse of Horizon in Off-Policy Evaluation via Conditional Importance Samplingcited by 36
  20. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 18; 2023: 15; 2024: 3; 2025: 2; 2026: 1.

56 papers.

Sort:

By area:

  1. 2021Offline Reinforcement Learning as One Big Sequence Modeling Problemcited by 636
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  4. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  5. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
  6. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexitycited by 84
  8. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  9. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  10. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 51
  11. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  12. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
38 more
  1. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  2. 2021Nearly Horizon-Free Offline Reinforcement Learningcited by 36
  3. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  4. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  5. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  6. 2022Optimal Conservative Offline RL with General Function Approximation via Augmented Lagrangiancited by 29
  7. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28
  8. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  9. 2021Mitigating Covariate Shift in Imitation Learning via Offline Data Without Great Coveragecited by 26
  10. 2021UMBRELLA: Uncertainty-Aware Model-Based Offline Reinforcement Learning Leveraging Planningcited by 23
  11. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  12. 2023Offline Learning in Markov Games with General Function Approximationcited by 16
  13. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  14. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  15. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  16. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  17. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  18. 2021Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RLcited by 12
  19. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  20. 2022Data-Efficient Pipeline for Offline Reinforcement Learning with Limited Datacited by 12
  21. 2023Offline Meta Reinforcement Learning with In-Distribution Online Adaptationcited by 10
  22. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
  23. 2023Regret-Optimal Model-Free Reinforcement Learning for Discounted MDPs with Short Burn-In Timecited by 8
  24. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  25. 2022Optimizing Pessimism in Dynamic Treatment Regimes: A Bayesian Learning Approachcited by 7
  26. 2023Robust Offline Reinforcement learning with Heavy-Tailed Rewardscited by 7
  27. 2024VC Theory for Inventory Policiescited by 7
  28. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  29. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  30. 2023Model-based Offline Reinforcement Learning with Local Misspecificationcited by 5
  31. 2023Provably Efficient Offline Goal-Conditioned Reinforcement Learning with General Function Approximation and Single-Policy Concentrabilitycited by 5
  32. 2023Bi-Level Offline Policy Optimization with Limited Explorationcited by 5
  33. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  34. 2022Incorporating Explicit Uncertainty Estimates into Deep Offline Reinforcement Learningcited by 4
  35. 2021Improving Long-Term Metrics in Recommendation Systems using Short-Horizon Reinforcement Learningcited by 2
  36. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  37. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  38. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1

50 most cited of 56 All 56 (JSON)

Similar, not cited

Close in wording, no citation either way

  1. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPs
  2. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  3. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  4. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  5. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  6. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  7. 2023Statistically Efficient Variance Reduction with Double Policy Estimation for Off-Policy Evaluation in Sequence-Modeled Reinforcement Learning
  8. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game