mlsanityData to 7 Oct 2026

Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm

arXiv 2103.09847 ↗First posted 17 Mar 2021cs.LG cs.AI math.OCcited by 10

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

Abstract (arXiv)

In this paper, we investigate the sample complexity of policy evaluation in infinite-horizon offline reinforcement learning (also known as the off-policy evaluation problem) with linear function approximation. We identify a hard regime dγ2>1, where d is the dimension of the feature vector and γ is the discount rate. In this regime, for any q∈[γ2,1], we can construct a hard instance such that the smallest eigenvalue of its feature covariance matrix is q/d and it requires Omegaleft(fracdγ2left(q-γ2right)varepsilon2expleft(Thetaleft(dγ2right)right)right) samples to approximate the value function up to an additive error varepsilon. Note that the lower bound of the sample complexity is exponential in d. If q=γ2, even infinite data cannot suffice. Under the low distribution shift assumption, we show that there is an algorithm that needs at most Oleft(maxleft fracleftVert θπrightVert 24varepsilon4logfracdδ,frac1varepsilon2left(d+logfrac1δright)right right) samples (θπ is the parameter of the policy in linear function approximation) and guarantees approximation to the value function up to an additive error of varepsilon with probability at least 1-δ.

Key facts. Cited by 10 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 16 of its 27 references that are in the map. First posted on arXiv 17 Mar 2021.

Builds on

16 of 27 references.

Closest ancestors · 4

Same direction, newest first

  1. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  2. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  3. 2020Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning7 Jul
  4. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 12

  1. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  6. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  7. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  8. 2020Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RLcited by 55
  9. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 36
  10. 2020Accountable Off-Policy Evaluation With Kernel Bellman Statisticscited by 36
  11. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 24
  12. 2020A maximum-entropy approach to off-policy evaluation in average-reward MDPscited by 9

Built on by

Cited by year (2026 to 7 Oct)

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

10 papers.

  1. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  2. 2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
  3. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  4. 2022Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Errorcited by 31
  5. 2023Model-based Offline Reinforcement Learning with Local Misspecificationcited by 5
  6. 2021The Curse of Passive Data Collection in Batch Reinforcement Learningcited by 2
  7. 2022Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learningcited by 2
  8. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  9. 2024On the Limited Representational Power of Value Functions and its Links to Statistical (In)Efficiencycited by 0
  10. 2026Learning to Play Blackjack: A Curriculum Learning Perspectivecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  2. 2021Nearly Horizon-Free Offline Reinforcement Learning
  3. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  4. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation
  5. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  6. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  7. 2025Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear qπ-Realizability and Concentrability
  8. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints