mlsanityData to 13 Oct 2026

A Unifying View of Coverage in Linear Off-Policy Evaluation

arXiv 2601.19030 ↗First posted 26 Jan 2026cs.LG cs.AI stat.MLcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

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.

Key facts. Cited by 1 paper in the map (data through 13 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.

Builds on

35 of 67 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025Model Selection for Off-policy Evaluation: New Algorithms and Experimental Protocol11 Feb
  2. 2024Scalable Online Exploration via Coverability11 Mar

Other references · 33

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 515
  2. 2020Is Pessimism Provably Efficient for Offline RL?cited by 363
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 268
  4. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  5. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  6. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  7. 2020Batch Value-function Approximation with Only Realizabilitycited by 104
  8. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  9. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  10. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 64
  11. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  12. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
21 more
  1. 2025Is a Good Foundation Necessary for Efficient Reinforcement Learning? The Computational Role of the Base Model in Explorationcited by 36
  2. 2019Exact minimax risk for linear least squares, and the lower tail of sample covariance matricescited by 34
  3. 2021Towards Hyperparameter-free Policy Selection for Offline Reinforcement Learningcited by 32
  4. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 30
  5. 2020A Variant of the Wang-Foster-Kakade Lower Bound for the Discounted Settingcited by 25
  6. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  7. 2021On Instrumental Variable Regression for Deep Offline Policy Evaluationcited by 22
  8. 2023Offline Learning in Markov Games with General Function Approximationcited by 18
  9. 2023Offline Primal-Dual Reinforcement Learning for Linear MDPscited by 17
  10. 2024Harnessing Density Ratios for Online Reinforcement Learningcited by 15
  11. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
  12. 2020Optimal oracle inequalities for solving projected fixed-point equationscited by 10
  13. 2022Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiencycited by 10
  14. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 10
  15. 2025Offline Reinforcement Learning in Large State Spaces: Algorithms and Guaranteescited by 10
  16. 2022Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributionscited by 8
  17. 2022A Complete Characterization of Linear Estimators for Offline Policy Evaluationcited by 7
  18. 2023Stochastic Online Instrumental Variable Regression: Regrets for Endogeneity and Bandit Feedbackcited by 7
  19. 2023The Optimal Approximation Factors in Misspecified Off-Policy Value Function Estimationcited by 3
  20. 2024Reinforcement Learning under Latent Dynamics: Toward Statistical and Algorithmic Modularitycited by 3
  21. 2024Instrumental variables: A non-asymptotic viewpointcited by 1

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Q-MMR: Off-Policy Evaluation via Recursive Reweighting and Moment Matchingcited by 0