mlsanityData to 7 Oct 2026

Nearly Horizon-Free Offline Reinforcement Learning

arXiv 2103.14077 ↗First posted 25 Mar 2021stat.ML cs.LGcited by 36

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

Abstract (arXiv)

We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes (MDP). For tabular MDP with S states and A actions, or linear MDP with anchor points and feature dimension d, given the collected K episodes data with minimum visiting probability of (anchor) state-action pairs dm, we obtain nearly horizon H-free sample complexity bounds for offline reinforcement learning when the total reward is upper bounded by 1. Specifically: 1. For offline policy evaluation, we obtain an tildeOleft(√frac1Kdm right) error bound for the plug-in estimator, which matches the lower bound up to logarithmic factors and does not have additional dependency on polyleft(H, S, A, dright) in higher-order term. 2.For offline policy optimization, we obtain an tildeOleft(√frac1Kdm + fracmin(S, d)Kdmright) sub-optimality gap for the empirical optimal policy, which approaches the lower bound up to logarithmic factors and a high-order term, improving upon the best known result by citecui2020plug that has additional polyleft(H, S, dright) factors in the main term. To the best of our knowledge, these are the first set of nearly horizon-free bounds for episodic time-homogeneous offline tabular MDP and linear MDP with anchor points. Central to our analysis is a simple yet effective recursion based method to bound a "total variance" term in the offline scenarios, which could be of individual interest.

Key facts. Cited by 36 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 36 of its 60 references that are in the map. First posted on arXiv 25 Mar 2021.

Builds on

36 of 60 references.

Closest ancestors · 7

Same direction, newest first

  1. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
  2. 2020Batch Value-function Approximation with Only Realizability11 Aug
  3. 2020Provably Good Batch Reinforcement Learning Without Great Exploration16 Jul
  4. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  5. 2020Conservative Q-Learning for Offline Reinforcement Learning8 Jun
  6. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  7. 2020Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison9 Mar

Other references · 29

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2018Learning Dexterous In-Hand Manipulationcited by 643
  3. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  4. 2018Is Q-learning Provably Efficient?cited by 485
  5. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  6. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  7. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  8. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  9. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  10. 2018Top-K Off-Policy Correction for a REINFORCE Recommender Systemcited by 181
  11. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  12. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
17 more
  1. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  2. 2020GenDICE: Generalized Offline Estimation of Stationary Valuescited by 122
  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. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  7. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  8. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  9. 2019Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learningcited by 75
  10. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  11. 2017Consistent On-Line Off-Policy Evaluationcited by 51
  12. 2019Off-Policy Deep Reinforcement Learning by Bootstrapping the Covariate Shiftcited by 47
  13. 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
  14. 2019Approximating Interactive Human Evaluation with Self-Play for Open-Domain Dialog Systemscited by 42
  15. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36
  16. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  17. 2020Is Plug-in Solver Sample-Efficient for Feature-based Reinforcement Learning?cited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 15; 2023: 7; 2024: 6; 2025: 2; 2026: 1.

36 papers.

Sort:

By area:

  1. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  2. 2022When Should We Prefer Offline Reinforcement Learning Over Behavioral Cloning?cited by 86
  3. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  4. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  5. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  6. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  7. 2024DiffuserLite: Towards Real-time Diffusion Planningcited by 40
  8. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  9. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  10. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  11. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  12. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
24 more
  1. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  2. 2022On Gap-dependent Bounds for Offline Reinforcement Learningcited by 13
  3. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  4. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  5. 2023Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problemscited by 12
  6. 2023Efficient Planning with Latent Diffusioncited by 11
  7. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  8. 2023Offline Meta Reinforcement Learning with In-Distribution Online Adaptationcited by 10
  9. 2024Q-SFT: Q-Learning for Language Models via Supervised Fine-Tuningcited by 10
  10. 2024Distributional Successor Features Enable Zero-Shot Policy Optimizationcited by 8
  11. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  12. 2022On the Power of Pre-training for Generalization in RL: Provable Benefits and Hardnesscited by 7
  13. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  14. 2023Offline RL with Observation Histories: Analyzing and Improving Sample Complexitycited by 7
  15. 2023Model-based Offline Reinforcement Learning with Local Misspecificationcited by 5
  16. 2022Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Pathcited by 4
  17. 2022Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimalitycited by 3
  18. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  19. 2025Structural Information-based Hierarchical Diffusion for Offline Reinforcement Learningcited by 3
  20. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  21. 2024Tractable Offline Learning of Regular Decision Processescited by 2
  22. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  23. 2026On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularizationcited by 2
  24. 2022Offline congestion games: How feedback type affects data coverage requirementcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  3. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  4. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  5. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  6. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  7. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  8. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes