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

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

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

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 30 of 41)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [D4RL: Datasets for Deep Data-Driven Reinforcement Learning](https://mlsanity.com/paper/2004.07219/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Batch Policy Learning under Constraints](https://mlsanity.com/paper/1903.08738/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Adversarially Trained Actor Critic for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02446/) (2022)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/1905.03814/) (2019)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Near-Optimal Offline Reinforcement Learning via Double Variance Reduction](https://mlsanity.com/paper/2102.01748/) (2021)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [Learning When-to-Treat Policies](https://mlsanity.com/paper/1905.09751/) (2019)
- [Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap](https://mlsanity.com/paper/2102.04692/) (2021)
- [Near-optimal Representation Learning for Linear Bandits and Linear RL](https://mlsanity.com/paper/2102.04132/) (2021)
- [Off-Policy Policy Gradient with State Distribution Correction](https://mlsanity.com/paper/1904.08473/) (2019)
- [Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning](https://mlsanity.com/paper/2103.13883/) (2021)
- [Statistical Inference with M-Estimators on Adaptively Collected Data](https://mlsanity.com/paper/2104.14074/) (2021)
- [Off-Policy Evaluation via Adaptive Weighting with Data from Contextual Bandits](https://mlsanity.com/paper/2106.02029/) (2021)

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

- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage](https://mlsanity.com/paper/2302.02392/) (2023)
- [Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.01380/) (2023)
- [Gap-Dependent Bounds for Q-Learning using Reference-Advantage Decomposition](https://mlsanity.com/paper/2410.07574/) (2024)
- [On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond](https://mlsanity.com/paper/2401.03301/) (2024)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)
- [Gap-Dependent Bounds for Federated Q-learning](https://mlsanity.com/paper/2502.02859/) (2025)
- [Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs](https://mlsanity.com/paper/2506.06521/) (2025)
- [VIPeR: Provably Efficient Algorithm for Offline RL with Neural Function Approximation](https://mlsanity.com/paper/2302.12780/) (2023)
- [Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2310.18919/) (2023)
- [Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces](https://mlsanity.com/paper/2401.05233/) (2024)
- [Tractable Offline Learning of Regular Decision Processes](https://mlsanity.com/paper/2409.02747/) (2024)
- [NetworkGym: Reinforcement Learning Environments for Multi-Access Traffic Management in Network Simulation](https://mlsanity.com/paper/2411.04138/) (2024)
- [On The Statistical Complexity of Offline Decision-Making](https://mlsanity.com/paper/2501.06339/) (2025)
- [Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learning](https://mlsanity.com/paper/2506.04626/) (2025)
- [On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures](https://mlsanity.com/paper/2501.02089/) (2025)
- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)
- [Q-Learning with Fine-Grained Gap-Dependent Regret](https://mlsanity.com/paper/2510.06647/) (2025)
- [Robust Offline Reinforcement Learning -- Certify the Confidence Interval](https://mlsanity.com/paper/2309.16631/) (2023)
- [Robust Offline Reinforcement Learning for Non-Markovian Decision Processes](https://mlsanity.com/paper/2411.07514/) (2024)
- [On the Complexity of Offline Reinforcement Learning with Q^star-Approximation and Partial Coverage](https://mlsanity.com/paper/2602.12107/) (2026)
- [From Weak Data to Strong Policy: Q-Targets Enable Provable In-Context Reinforcement Learning](https://mlsanity.com/paper/2609.30391/) (2026)

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