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

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

## Key facts

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

## Placed in

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

## Builds on (most cited first, 16 of 16)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Off-Policy Deep Reinforcement Learning without Exploration](https://mlsanity.com/paper/1812.02900/) (2018)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Off-Policy Evaluation via the Regularized Lagrangian](https://mlsanity.com/paper/2007.03438/) (2020)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency](https://mlsanity.com/paper/2102.02981/) (2021)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension](https://mlsanity.com/paper/2005.10804/) (2020)
- [Accountable Off-Policy Evaluation With Kernel Bellman Statistics](https://mlsanity.com/paper/2008.06668/) (2020)
- [Near-Optimal Provable Uniform Convergence in Offline Policy Evaluation for Reinforcement Learning](https://mlsanity.com/paper/2007.03760/) (2020)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [A maximum-entropy approach to off-policy evaluation in average-reward MDPs](https://mlsanity.com/paper/2006.12620/) (2020)

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

- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2111.03947/) (2021)
- [Variance-Aware Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2106.11960/) (2021)
- [Why Should I Trust You, Bellman? The Bellman Error is a Poor Replacement for Value Error](https://mlsanity.com/paper/2201.12417/) (2022)
- [Model-based Offline Reinforcement Learning with Local Misspecification](https://mlsanity.com/paper/2301.11426/) (2023)
- [The Curse of Passive Data Collection in Batch Reinforcement Learning](https://mlsanity.com/paper/2106.09973/) (2021)
- [Cascaded Gaps: Towards Gap-Dependent Regret for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2203.03110/) (2022)
- [Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity](https://mlsanity.com/paper/2310.01616/) (2023)
- [On the Limited Representational Power of Value Functions and its Links to Statistical (In)Efficiency](https://mlsanity.com/paper/2403.07136/) (2024)
- [Learning to Play Blackjack: A Curriculum Learning Perspective](https://mlsanity.com/paper/2604.00076/) (2026)

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