mlsanityData to 14 Oct 2026

On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation

arXiv 2211.13208 ↗First posted 23 Nov 2022cs.LGcited by 22

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

Abstract (arXiv)

Sample-efficient offline reinforcement learning (RL) with linear function approximation has recently been studied extensively. Much of prior work has yielded the minimax-optimal bound of tildeO(frac1√K), with K being the number of episodes in the offline data. In this work, we seek to understand instance-dependent bounds for offline RL with function approximation. We present an algorithm called Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI), which leverages data bootstrapping and constrained optimization on top of pessimism. We show that under a partial data coverage assumption, that of concentrability with respect to an optimal policy, the proposed algorithm yields a fast rate of tildeO(frac1K) for offline RL when there is a positive gap in the optimal Q-value functions, even when the offline data were adaptively collected. Moreover, when the linear features of the optimal actions in the states reachable by an optimal policy span those reachable by the behavior policy and the optimal actions are unique, offline RL achieves absolute zero sub-optimality error when K exceeds a (finite) instance-dependent threshold. To the best of our knowledge, these are the first tildeO(frac1K) bound and absolute zero sub-optimality bound respectively for offline RL with linear function approximation from adaptive data with partial coverage. We also provide instance-agnostic and instance-dependent information-theoretical lower bounds to complement our upper bounds.

Key facts. Cited by 22 papers in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 41 of its 64 references that are in the map. First posted on arXiv 23 Nov 2022.

Builds on

41 of 64 references.

Closest ancestors · 17

Same direction, newest first

  1. 2022On Gap-dependent Bounds for Offline Reinforcement Learning1 Jun
  2. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  3. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  4. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learning5 Feb
  5. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization27 Nov
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism17 Oct
  7. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  8. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  9. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  10. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning25 Mar
  11. 2021Sample Complexity of Offline Reinforcement Learning with Deep ReLU Networks11 Mar
  12. 2021Near-Optimal Offline Reinforcement Learning via Double Variance Reduction2 Feb
5 more
  1. 2021Fast Rates for the Regret of Offline Reinforcement Learning31 Jan
  2. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  3. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?22 Oct
  4. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  5. 2020D4RL: Datasets for Deep Data-Driven Reinforcement Learning15 Apr

Other references · 24

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  3. 2019Batch Policy Learning under Constraintscited by 244
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  6. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  7. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  8. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2020Q-learning with Logarithmic Regretcited by 60
  11. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  12. 2019Learning When-to-Treat Policiescited by 49
12 more
  1. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  2. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  3. 2019Off-Policy Policy Gradient with State Distribution Correctioncited by 43
  4. 2021Statistical Inference with M-Estimators on Adaptively Collected Datacited by 40
  5. 2021Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Banditscited by 40
  6. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  7. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  8. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  9. 2021Policy Learning with Adaptively Collected Datacited by 21
  10. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 18
  11. 2022Sample Complexity of Nonparametric Off-Policy Evaluation on Low-Dimensional Manifolds using Deep Networkscited by 12
  12. 2022Two-Stage Neural Contextual Bandits for Personalised News Recommendationcited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 6; 2024: 7; 2025: 7; 2026: 2.

22 papers.

Sort:

By area:

  1. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  2. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 10
  3. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  4. 2024Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decompositioncited by 8
  5. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyondcited by 6
  6. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 6
  7. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  8. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  9. 2023VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximationcited by 3
  10. 2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
  11. 2024Taming "data-hungry" reinforcement learning? Stability in continuous state-action spacescited by 3
  12. 2024Tractable Offline Learning of Regular Decision Processescited by 3
10 more
  1. 2024NetworkGym: Reinforcement Learning Environments for Multi-Access Traffic Management in Network Simulationcited by 2
  2. 2025On The Statistical Complexity of Offline Decision-Makingcited by 2
  3. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  4. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structurescited by 1
  5. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
  6. 2025Q-Learning with Fine-Grained Gap-Dependent Regretcited by 1
  7. 2023Robust Offline Reinforcement Learning -- Certify the Confidence Intervalcited by 0
  8. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processescited by 0
  9. 2026On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coveragecited by 0
  10. 2026From Weak Data to Strong Policy: Q-Targets Enable Provable In-Context Reinforcement Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  2. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrability
  3. 2024A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs
  4. 2023Offline Reinforcement Learning with Additional Covering Distributions
  5. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  6. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  7. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning
  8. 2025Offline Constrained Reinforcement Learning under Partial Data Coverage