# A Unifying View of Coverage in Linear Off-Policy Evaluation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 35 of its 67 references that are in the map.
- First posted on arXiv 26 Jan 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [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)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [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)
- [Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learning](https://mlsanity.com/paper/2001.10742/) (2020)
- [Instabilities of Offline RL with Pre-Trained Neural Representation](https://mlsanity.com/paper/2103.04947/) (2021)
- [Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Exploration](https://mlsanity.com/paper/2503.07453/) (2025)
- [Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices](https://mlsanity.com/paper/1912.10754/) (2019)
- [Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learning](https://mlsanity.com/paper/2110.14000/) (2021)
- [Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus](https://mlsanity.com/paper/2206.00159/) (2022)
- [A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Setting](https://mlsanity.com/paper/2011.01075/) (2020)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [On Instrumental Variable Regression for Deep Offline Policy Evaluation](https://mlsanity.com/paper/2105.10148/) (2021)
- [Offline Learning in Markov Games with General Function Approximation](https://mlsanity.com/paper/2302.02571/) (2023)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Harnessing Density Ratios for Online Reinforcement Learning](https://mlsanity.com/paper/2401.09681/) (2024)
- [Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data](https://mlsanity.com/paper/2403.17091/) (2024)
- [Optimal oracle inequalities for solving projected fixed-point equations](https://mlsanity.com/paper/2012.05299/) (2020)
- [Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency](https://mlsanity.com/paper/2209.13075/) (2022)
- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Scalable Online Exploration via Coverability](https://mlsanity.com/paper/2403.06571/) (2024)
- [Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees](https://mlsanity.com/paper/2510.04088/) (2025)
- [Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions](https://mlsanity.com/paper/2210.15543/) (2022)
- [A Complete Characterization of Linear Estimators for Offline Policy Evaluation](https://mlsanity.com/paper/2203.04236/) (2022)

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

- [Q-MMR: Off-Policy Evaluation via Recursive Reweighting and Moment Matching](https://mlsanity.com/paper/2605.06474/) (2026)

## Abstract (arXiv)

Off-policy evaluation (OPE) is a fundamental task in reinforcement learning (RL). In the classic setting of linear OPE, finite-sample guarantees often take the form  textrmEvaluation error ≤ textrmpoly(Cπ, d, 1/n,log(1/δ)),  where d is the dimension of the features and Cπ is a coverage parameter that characterizes the degree to which the visited features lie in the span of the data distribution. While such guarantees are well-understood for several popular algorithms under stronger assumptions (e.g. Bellman completeness), the understanding is lacking and fragmented in the minimal setting where only the target value function is linearly realizable in the features. Despite recent interest in tight characterizations of the statistical rate in this setting, the right notion of coverage remains unclear, and candidate definitions from prior analyses have undesirable properties and are starkly disconnected from more standard definitions in the literature. We provide a novel finite-sample analysis of a canonical algorithm for this setting, LSTDQ. Inspired by an instrumental-variable view, we develop error bounds that depend on a novel coverage parameter, the feature-dynamics coverage, which can be interpreted as linear coverage in an induced dynamical system for feature evolution. With further assumptions -- such as Bellman-completeness -- our definition successfully recovers the coverage parameters specialized to those settings, finally yielding a unified understanding for coverage in linear OPE.