A Unifying View of Coverage in Linear Off-Policy Evaluation

Philip AmortilaAudrey HuangAkshay KrishnamurthyNan Jiang

article2026arXiv2 citations

Establishes a unified theory of data coverage in linear off-policy evaluation by introducing a feature-dynamics coverage parameter that supplies finite-sample error bounds for LSTDQ under minimal realizability assumptions while recovering standard coverage metrics in stronger settings.

Listen

In reinforcement learning, off-policy evaluation allows organizations to assess a newly proposed strategy using historical data collected from a different baseline strategy. This is crucial in high-stakes settings such as healthcare, finance, and autonomous operations, where deploying an unproven policy directly to the real world is risky and costly. A core theoretical challenge in this setup is distribution shift, captured by coverage, which quantifies whether historical data sufficiently covers the scenarios the target policy will encounter. In linear evaluation models, prior coverage metrics suffered from major shortcomings: they were sensitive to arbitrary changes in feature units, failed to explain off-policy data well, and remained disconnected from standard reinforcement learning theory.

The article establishes a rigorous, unified theoretical framework for linear off-policy evaluation under minimal baseline assumptions, specifically focusing on the canonical Least-Squares Temporal Difference algorithm. It aims to identify the correct coverage metric and derive finite-sample performance bounds that connect previously isolated theoretical settings.

To achieve this, the authors adopted an instrumental-variable framework from econometrics to resolve error propagation and noisy transitions in temporal-difference learning. Using concentration inequalities, they derived finite-sample error bounds for both population and empirical data settings without relying on strong assumptions such as Bellman completeness, which requires linear expressiveness across all updates.

The analysis yielded several key findings. First, the article introduced feature-dynamics coverage, a scale-invariant metric that interprets coverage as linear reachability within a compressed dynamical system. Second, the derived statistical error bounds scale tightly at the rate of one over the square root of sample size, matching the performance of standard linear regression while remaining free of feature-dimension penalties for fixed initial evaluations. Third, under stronger Bellman-completeness conditions, this new metric exactly recovers the standard linear coverage parameter. Fourth, for state-abstraction models, it directly unifies with aggregated concentrability, proving that error propagation in compressed spaces is the general case that naturally subsumes standard environment dynamics. Finally, the coverage metric bounds the variance in marginalized importance sampling algorithms, bridging two major algorithmic paradigms.

These findings provide practical and theoretical clarity for decision-makers. They show that off-policy evaluation can remain statistically reliable even when feature distributions differ, provided the expected features match across dynamics. This offers more realistic risk assessments for offline policy deployment, reduces required sample sizes, and demonstrates that simpler evaluation models can match the theoretical safety margins of complex algorithms.

Organizations should use the empirical coverage metric to pre-screen offline datasets before deploying new evaluation policies, guaranteeing numerical stability and bounded error. Further research should extend these directional bounds to non-linear neural network representations and explore adaptive online data collection schemes.

The theoretical guarantees are mathematically robust under stated invertibility and bounded feature conditions. However, users should exercise caution when sample sizes are small or when empirical covariance matrices are near-singular, as performance bounds become uninformative in those regimes.

policy evaluation value functions viewpoint linear off-policy evaluation offline reinforcement learning feature-dynamics coverage

arXiv: 2601.19030

Paper: Least-Squares Policy Iteration, Michail G. Lagoudakis et al. (2003). Introduces Least-Squares Temporal Difference for Q-values (LSTDQ) and least-squares policy evaluation under linear value-function approximation, the core algorithm analyzed in the source paper.
Paper: Learning to Predict by the Methods of Temporal Differences, Richard S. Sutton (1988). Establishes foundational temporal-difference prediction methods and linear feature-based value representations underlying linear off-policy evaluation.
Paper: Improved Algorithms for Linear Stochastic Bandits, Yasin Abbasi-Yadkori et al. (2011). Provides fundamental finite-sample concentration tools and self-normalized martingale inequalities frequently adapted for statistical guarantees in linear reinforcement learning.
Paper: Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems, Sergey Levine et al. (2020). Presents a comprehensive conceptual tutorial on the offline reinforcement learning setting, distributional shift, and coverage challenges that motivate unified off-policy evaluation theory.

No sufficiently relevant recommendations were found.

Cover for A Unifying View of Coverage in Linear Off-Policy Evaluation

Abstract

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 $\textrm{Evaluation error} \le \textrm{poly}(C^\pi, d, 1/n,\log(1/\delta)),$ where $d$ is the dimension of the features and $C^\pi$ 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.

Topics

policy evaluation value functions viewpoint interpreter control parameters adaptive algorithms optimization problems feature space

Keywords

linear off-policy evaluation offline reinforcement learning feature-dynamics coverage population coverage importance sampling finite-sample guarantees contextual bandits state-action distribution Bellman-completeness assumption

1 Introduction
2 Preliminaries
2.1 LSTDQ
3 Related Works
4 Finite-sample Analysis of LSTDQ
5 Understanding the Coverage Parameter
5.1 General Interpretation
5.2 Recovering Aggregated Concentrability
5.3 Recovering Standard Linear Coverage under Bellman-Completeness
5.4 Unification with Marginalized Importance Sampling
6 Conclusion and Discussion
References
A Dimension-Free Guarantee for Contextual Bandits
B Proofs of
B.1 Proof of
B.2 Proof of
C Proofs of
C.1 Proof of
C.2 New On-policy Condition
C.3 Proof of
C.4 On Aggregated Concentrability
C.5 Proof of
C.6 Proof of
C.7 Details on MWL
D Function Estimation Guarantees
E σmin(A)\sigma_{\mathrm{min}}(A)-Independent Population Bound via Loss Minimization Algorithm
F Technical Tools

Knowls

Knowl 1 — Feature-dynamics coverage
definition
For linear off-policy evaluation, let $\phi:S\times A\to\mathbb R^d$ be the feature map, let $(s,a)\sim\mu^D$ be a data-distributed state-action pair, and sample $s'\sim P(\cdot\mid s,a)$ and $a'\sim\pi(\cdot\mid s')$ under the target policy. Define $\Sigma=\mathbb E_{\mu^D}[\phi(s,a)\phi(s,a)^\top]$ , $\Sigma_{cr}=\mathbb E_{\mu^D}[\phi(s,a)\phi(s',a')^\top]$ , and $A=\Sigma-\gamma\Sigma_{cr}$ , assuming $\Sigma$ and $A$ are invertible. Let $\phi_0=\mathbb E_{s_0\sim\mu_0,\,a_0\sim\pi(\cdot\mid s_0)}[\phi(s_0,a_0)]$ . The feature-dynamics coverage of $\pi$ relative to the data is $C^\pi_\phi=(1-\gamma)^2\phi_0^\top A^{-1}\Sigma A^{-\top}\phi_0$ . It measures coverage in the direction needed to estimate the target return, and is invariant to rescaling the feature map.
Knowl 2 — Population finite-sample return guarantee
theoretical result
Consider $n$ i.i.d. OPE samples with $(s,a)\sim\mu^D$ , $r\sim R(\cdot\mid s,a)$ , $s'\sim P(\cdot\mid s,a)$ , and $a'\sim\pi(\cdot\mid s')$ . Suppose $Q^\pi(s,a)=\phi(s,a)^\top\theta^\star$ , $\|\phi(s,a)\|_2\le B_\phi$ , rewards lie in $[0,R_{\max}]$ , and the population matrices $\Sigma=\mathbb E_{\mu^D}[\phi\phi^\top]$ and $A=\mathbb E_{\mu^D}[\phi(s,a)(\phi(s,a)-\gamma\phi(s',a'))^\top]$ are invertible. LSTDQ sets $\widehat\theta=\widehat A^{-1}\widehat b$ , where $\widehat A$ and $\widehat b$ are the sample averages of $\phi(s,a)(\phi(s,a)-\gamma\phi(s',a'))^\top$ and $\phi(s,a)r$ , and estimates the return by $\widehat J=\phi_0^\top\widehat\theta$ . With $V_{\max}=R_{\max}/(1-\gamma)$ and $C^\pi_\phi=(1-\gamma)^2\phi_0^\top A^{-1}\Sigma A^{-\top}\phi_0$ , there is a burn-in sample size $n_0$ such that, for $n\ge n_0$ , with probability at least $1-\delta$ , $|\widehat J-J(\pi)|\lesssim \frac{V_{\max}}{1-\gamma}\sqrt{\frac{C^\pi_\phi\log(1/\delta)}{n}}+o(n^{-1/2})$ . The burn-in and lower-order term may depend on $d$ and $1/\sigma_{\min}(A)$ , but the leading $n^{-1/2}$ term does not depend on feature dimension.
Knowl 3 — Empirical feature-dynamics coverage guarantee
theoretical result
Under realizability $Q^\pi(s,a)=\phi(s,a)^\top\theta^\star$ , bounded features $\|\phi(s,a)\|_2\le B_\phi$ , and invertible population matrices $\Sigma$ and $A$ , use $n$ i.i.d. samples $(s_i,a_i,r_i,s_i',a_i')$ and define $\widehat\Sigma=n^{-1}\sum_i\phi_i\phi_i^\top$ , $\widehat A=n^{-1}\sum_i\phi_i(\phi_i-\gamma\phi_i')^\top$ , and $\widehat b=n^{-1}\sum_i\phi_i r_i$ , where $\phi_i=\phi(s_i,a_i)$ and $\phi_i'=\phi(s_i',a_i')$ . LSTDQ uses $\widehat\theta=\widehat A^{-1}\widehat b$ and $\widehat J=\phi_0^\top\widehat\theta$ , with $\phi_0=\mathbb E_{\mu_0,\pi}[\phi(s_0,a_0)]$ . Define $\widehat C^\pi_\phi=(1-\gamma)^2\phi_0^\top\widehat A^{-1}\widehat\Sigma\widehat A^{-\top}\phi_0$ , and set it to $+\infty$ if $\widehat A$ is singular. For $V_{\max}=R_{\max}/(1-\gamma)$ , with probability at least $1-\delta$ , $|\widehat J-J(\pi)|\lesssim\frac{V_{\max}}{1-\gamma}\sqrt{\frac{\widehat C^\pi_\phi\,[d+\log(1/\delta)]}{n}}$ . Unlike the population guarantee's burn-in formulation, this bound has no lower-order term or explicit dependence on $1/\sigma_{\min}(A)$ .
Knowl 4 — LSTDQ as instrumental-variable regression
model/method
With $Z=\phi(s,a)$ , $X=\phi(s,a)-\gamma\phi(s',a')$ , and $Y=r$ , the population LSTDQ equation is $\mathbb E[ZX^\top]\theta^\star=\mathbb E[ZY]$ , where the expectation is over data state-action pairs, transitions, rewards, and target-policy next actions. LSTDQ estimates this equation by $\widehat A\widehat\theta=\widehat b$ , using $\widehat A$ as the empirical average of $ZX^\top$ and $\widehat b$ as the average of $ZY$ . The current feature $Z$ acts as an instrument: the random next feature in $X$ contains transition noise, so ordinary least squares regressing $Y$ on $X$ generally does not recover the desired parameter. When $\gamma=0$ , $X=Z$ and the moment equation reduces to ordinary linear regression.
Knowl 5 — Coverage as occupancy in compressed feature dynamics
theoretical result
For the matrices $\Sigma$ and $\Sigma_{cr}$ induced by a data distribution and target policy, define $B^\pi=(\Sigma^{-1}\Sigma_{cr})^\top$ . This matrix is the population linear predictor of the next target-policy feature from the current feature: $\mathbb E[\phi(s',a')\mid s,a]\approx B^\pi\phi(s,a)$ . Starting from $x_0=\phi_0$ , form the deterministic feature sequence $x_{t+1}=B^\pi x_t$ . If $\gamma>0$ and the spectral radius satisfies $\rho(B^\pi)<1/\gamma$ , its discounted feature occupancy $m^\pi_\phi=(1-\gamma)\sum_{t\ge0}\gamma^t x_t$ is well-defined and $C^\pi_\phi=(m^\pi_\phi)^\top\Sigma^{-1}m^\pi_\phi$ . Thus the coverage coefficient measures an expected feature occupancy under compressed dynamics, not necessarily under the true MDP; the feature sequence can diverge even though the true discounted occupancy is bounded. The schematic on page 9 depicts the distinction between evolution of true state-action occupancies and evolution of feature expectations.
Knowl 6 — Bellman completeness recovers standard linear coverage
theoretical result
Let $\mathcal F_\phi=\{(s,a)\mapsto\phi(s,a)^\top\theta:\theta\in\mathbb R^d\}$ , and suppose it is Bellman-complete for target policy $\pi$ , meaning $T^\pi f\in\mathcal F_\phi$ for every $f\in\mathcal F_\phi$ . Then the compressed predictor is exact: $\mathbb E_{s'\sim P(\cdot\mid s,a)}[\phi(s',\pi)]=B^\pi\phi(s,a)$ , where $\phi(s',\pi)=\mathbb E_{a'\sim\pi(\cdot\mid s')}[\phi(s',a')]$ . The feature occupancy under $B^\pi$ equals $\phi^\pi=\mathbb E_{(s,a)\sim\mu^\pi}[\phi(s,a)]$ , with $\mu^\pi$ the normalized discounted target-policy occupancy, and $\rho(B^\pi)\le1$ . Consequently, feature-dynamics coverage equals standard linear coverage: $C^\pi_\phi=(\phi^\pi)^\top\Sigma^{-1}\phi^\pi$ . The page-9 schematic illustrates that the true-dynamics and compressed-feature routes give the same expected features under completeness; without completeness, they need not agree.
Knowl 7 — State abstractions yield aggregated concentrability
theoretical result
Let $\psi:S\to[K]$ be a state abstraction, use one-hot features $\phi(s,a)=e_{\psi(s),a}$ , and suppose the target policy depends on a state only through its abstract state, so $\pi(\cdot\mid s)=\pi(\cdot\mid\psi(s))$ . Define the data mass on abstract pairs by $\phi^D(k,a)=\sum_{s:\psi(s)=k}\mu^D(s,a)$ and the abstract transition by $P_\psi(k'\mid k,a)=\frac{\sum_{s:\psi(s)=k}\mu^D(s,a)\sum_{s':\psi(s')=k'}P(s'\mid s,a)}{\sum_{s:\psi(s)=k}\mu^D(s,a)}$ . Let $\mu^\pi_{M_\psi}(k,a)$ be the normalized discounted occupancy under this abstract MDP, initialized with $\psi_0(k)=\sum_{s:\psi(s)=k}\mu_0(s)$ . The feature-dynamics coefficient becomes $C^\pi_\phi=\sum_{k,a}\frac{(\mu^\pi_{M_\psi}(k,a))^2}{\phi^D(k,a)}=\mathbb E_{(k,a)\sim\phi^D}[(\mu^\pi_{M_\psi}(k,a)/\phi^D(k,a))^2]$ . It therefore recovers the chi-square version of aggregated concentrability, which measures shift in the data-weighted abstract dynamics.
Knowl 8 — Tabular coverage reduces to a density-ratio second moment
theoretical result
For one-hot features indexed by state-action pairs, $\phi(s,a)=e_{s,a}$ , the feature covariance is $\Sigma=\operatorname{diag}(\mu^D)$ and the compressed dynamics $B^\pi$ are the true policy-induced transition kernel over state-action pairs. The feature-dynamics coverage then equals $C^\pi_\phi=\sum_{s,a}(\mu^\pi(s,a))^2/\mu^D(s,a)=\mathbb E_{(s,a)\sim\mu^D}[(\mu^\pi(s,a)/\mu^D(s,a))^2]$ , where $\mu^\pi$ is the normalized discounted occupancy. For probability distributions with the required support, this second moment is one plus the chi-square divergence of $\mu^\pi$ from $\mu^D$ .
Knowl 9 — A mean-matching sufficient condition for coverage at most one
theoretical result
Suppose the feature map contains a bias direction: there is a vector $\theta_0$ such that $\phi(s,a)^\top\theta_0=1$ for every state-action pair. If $\rho(B^\pi)<1/\gamma$ and the data and initial target features satisfy $\mathbb E_{\mu^D}[\phi(s,a)]=\mathbb E_{\mu^D}[\phi(s',a')]=\phi_0$ , then $C^\pi_\phi\le1$ . This sufficient condition matches only the mean current and next feature vectors to the initial target feature; it does not require the current and next state-action distributions themselves to be equal.
Knowl 10 — Bounded-residual LSTDQ avoids dependence on the conditioning of A
theoretical result
A bounded-residual variant chooses $\widehat\theta\in\Theta$ to minimize $\|\widehat\Sigma^{-1/2}(\widehat A\theta-\widehat b)\|_2$ , where $\Theta\subseteq\mathbb R^d$ satisfies $\|\theta\|_2\le B_\Theta$ , and $\widehat\Sigma$ , $\widehat A$ , and $\widehat b$ are the empirical feature covariance and LSTDQ moments. Let $\kappa(\Sigma)=\lambda_{\max}(\Sigma)/\lambda_{\min}(\Sigma)$ and let $C^\pi_\phi=(1-\gamma)^2\phi_0^\top A^{-1}\Sigma A^{-\top}\phi_0$ . Under the paper's stated assumptions of realizability, invertible population moments, and bounded $\Theta$ , if $n\gtrsim \kappa(\Sigma)B_\phi^2\log(d/\delta)/\lambda_{\min}(\Sigma)$ , then with probability at least $1-\delta$ , $|J(\pi)-\widehat J(\pi)|\lesssim\frac{\sqrt{C^\pi_\phi}}{1-\gamma}\max\{B_\phi B_\Theta,R_{\max}\}^{2}\sqrt{\frac{d\log(B_\Theta n/\delta)}{\lambda_{\min}(\Sigma)n}}$ . This alternative removes the explicit dependence on $1/\sigma_{\min}(A)$ at the cost of requiring bounded parameters and dependence on the conditioning of $\Sigma$ .

Coverage note — The appendix’s weighted function-estimation guarantee and the connection to marginalized importance sampling are omitted because they extend or compare the main return-estimation coverage results rather than adding to their core unification.

References

1.Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, 2011.
2.Philip Amortila, Nan Jiang, and Tengyang Xie. A variant of the wang-foster-kakade lower bound for the discounted setting. In arXiv preprint arXiv:2011.01075, 2020.
3.Philip Amortila, Nan Jiang, and Csaba Szepesvári. The optimal approximation factors in misspecified off-policy value function estimation. In International Conference on Machine Learning, 2023.
4.Philip Amortila, Dylan J Foster, Nan Jiang, Akshay Krishnamurthy, and Zak Mhammedi. Reinforcement learning under latent dynamics: Toward statistical and algorithmic modularity. In Advances in Neural Information Processing Systems, 2024a.
5.Philip Amortila, Dylan J Foster, Nan Jiang, Ayush Sekhari, and Tengyang Xie. Harnessing density ratios for online reinforcement learning. In International Conference on Learning Representations, 2024b.
6.Philip Amortila, Dylan J Foster, and Akshay Krishnamurthy. Scalable online exploration via coverability. In International Conference on Machine Learning, 2024c.
7.András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. In Machine Learning. Springer, 2008.
8.Dimitri Bertsekas. Dynamic programming and optimal control, volume II. Athena scientific, 2007.
9.Dimitri P Bertsekas and Huizhen Yu. Projected equation methods for approximate solution of large linear systems. Journal of Computational and Applied Mathematics, 227(1):27–50, 2009.
10.Justin A Boyan. Least-squares temporal difference learning. In ICML, pp. 49–56, 1999.
11.Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1):33–57, 1996.
12.Yutian Chen, Liyuan Xu, Caglar Gulcehre, Tom Le Paine, Arthur Gretton, Nando De Freitas, and Arnaud Doucet. On instrumental variable regression for deep offline policy evaluation. Journal of Machine Learning Research, 23(302):1–40, 2022.
13.Qiwen Cui and Simon S Du. Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus. Advances in Neural Information Processing Systems, 35:11739–11751, 2022.
14.Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences: A survey and comparison. The Journal of Machine Learning Research, 15(1):809–883, 2014.
15.Riccardo Della Vecchia and Debabrota Basu. Stochastic online instrumental variable regression: Regrets for endogeneity and bandit feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 16190–16198, 2025.
16.Yaqi Duan and Mengdi Wang. Minimax-optimal Off-Policy Evaluation with Linear Function Approximation. In International Conference on Machine Learning, 2020.
17.Yaqi Duan, Mengdi Wang, and Martin J. Wainwright. Optimal policy evaluation using kernel-based temporal difference methods. In arXiv preprint arXiv:2109.12002, 2021.
18.Amir-massoud Farahmand, Csaba Szepesvári, and Rémi Munos. Error propagation for approximate policy and value iteration. In Advances in Neural Information Processing Systems, 2010.
19.Dylan J Foster, Zakaria Mhammedi, and Dhruv Rohatgi. Is a good foundation necessary for efficient reinforcement learning? the computational role of the base model in exploration. arXiv preprint arXiv:2503.07453, 2025.
20.Germano Gabbianelli, Gergely Neu, Matteo Papini, and Nneka M Okolo. Offline primal-dual reinforcement learning for linear mdps. In International Conference on Artificial Intelligence and Statistics, pp. 3169–3177. PMLR, 2024.
21.Daniel Hsu, Sham M Kakade, and Tong Zhang. An analysis of random design linear regression. arXiv preprint arXiv:1106.2363, 6, 2011.
22.Audrey Huang and Nan Jiang. Beyond the return: Off-policy function estimation under user-specified error-measuring distributions. Advances in Neural Information Processing Systems, 35:6292–6303, 2022.
23.Zeyu Jia, Alexander Rakhlin, Ayush Sekhari, and Chen-Yu Wei. Offline reinforcement learning: Role of state aggregation and trajectory data. In The Thirty Seventh Annual Conference on Learning Theory, pp. 2644–2719. PMLR, 2024.
24.Nan Jiang. Notes on state abstractions. https://nanjiang.cs.illinois.edu/files/cs542f22/note4.pdf, 2018. Version: September 28, 2018.
25.Nan Jiang and Tengyang Xie. Offline reinforcement learning in large state spaces: Algorithms and guarantees. Statistical Science, 2024.
26.Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, 2020.
27.Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, 2021.
28.J Kolter. The fixed points of off-policy td. In Advances in Neural Information Processing Systems, 2011.
29.Michail G Lagoudakis and Ronald Parr. Least-squares policy iteration. In Journal of Machine Learning Research, 2003.
30.Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Finite-sample analysis of lstd. In ICML-27th International Conference on Machine Learning, pp. 615–622, 2010.
31.Alessandro Lazaric, Mohammad Ghavamzadeh, and Rémi Munos. Finite-sample analysis of least-squares policy iteration. The Journal of Machine Learning Research, 13(1):3041–3074, 2012.
32.Lihong Li, Thomas J Walsh, and Michael L Littman. Towards a unified theory of state abstraction for mdps. In International Symposium on Artificial Intelligence and Mathematics, 2006.
33.Pai Liu, Lingfeng Zhao, Shivangi Agarwal, Jinghan Liu, Audrey Huang, Philip Amortila, and Nan Jiang. Model selection for off-policy evaluation: New algorithms and experimental protocol. arXiv preprint arXiv:2502.08021, 2025.
34.Diego Martinez-Taboada and Aaditya Ramdas. Empirical bernstein in smooth banach spaces. arXiv preprint arXiv:2409.06060, 2024.
35.Stanislav Minsker. On some extensions of bernstein’s inequality for self-adjoint operators. Statistics & Probability Letters, 127:111–119, 2017.
36.Wenlong Mou, Ashwin Pananjady, and Martin J Wainwright. Optimal oracle inequalities for solving projected fixed-point equations. In Mathematics of Operations Research. INFORMS, 2022a.
37.Wenlong Mou, Martin J. Wainwright, and Peter L. Bartlett. Off-policy estimation of linear functionals: non-asymptotic theory for semi-parametric efficiency, September 2022b. URL http://arxiv.org/abs/2209.13075. arXiv preprint arXiv:2209.13075 [cs, math, stat].
38.Rémi Munos. Performance bounds in lp-norm for approximate value iteration. In SIAM Journal on Control and Optimization. SIAM, 2007.
39.Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. In Journal of Machine Learning Research, 2008.
40.A Nedic and Dimitri P Bertsekas. Least squares policy evaluation algorithms with linear function approximation. Discrete Event Dynamic Systems, 13(1):79–110, 2003.
41.Ronald Parr, Lihong Li, Gavin Taylor, Christopher Painter-Wakefield, and Michael L Littman. An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning. In Proceedings of the 25th international conference on Machine learning, pp. 752–759, 2008.
42.Juan C. Perdomo, Akshay Krishnamurthy, Peter Bartlett, and Sham Kakade. A complete characterization of linear estimators for offline policy evaluation. In Journal of Machine Learning Research, 2023.
43.Iosif Pinelis. Optimum bounds for the distributions of martingales in banach spaces. In The Annals of Probability, volume 22. Institute of Mathematical Statistics, 1994.
44.Gilbert W Stewart and Ji-guang Sun. Matrix perturbation theory. (No Title), 1990.
45.Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
46.Joel A Tropp. User-friendly tail bounds for sums of random matrices. In Foundations of computational mathematics, volume 12. Springer, 2012.
47.John N. Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. In IEEE Transactions on Automatic Control. IEEE, 1997.
48.Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In International Conference on Machine Learning, 2020.
49.J. L. van Hemmen and T. Ando. An inequality for trace ideals. Communications in Mathematical Physics, 76(2):143–148, 1980.
50.Roman Vershynin. High-dimensional Probability: an Introduction With Applications in Data Science, volume 47. Cambridge University Press, 2018.
51.Martin J Wainwright. High-dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019.
52.Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham Kakade. Instabilities of offline rl with pre-trained neural representation. In International Conference on Machine Learning, pp. 10948–10960. PMLR, 2021.
53.Eric Xia, Martin J Wainwright, and Whitney Newey. Instrumental variables: A non-asymptotic viewpoint. arXiv preprint arXiv:2410.02015, 2024.
54.Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability, 2020a.
55.Tengyang Xie and Nan Jiang. Q* approximation schemes for batch reinforcement learning: A theoretical comparison. In Conference on Uncertainty in Artificial Intelligence, 2020b.
56.Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman-consistent pessimism for offline reinforcement learning. In Advances in Neural Information Processing Systems, 2021.
57.Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. In International Conference on Learning Representations, 2023.
58.Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pp. 3948–3958. PMLR, 2020.
59.Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065–4078, 2021.
60.Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.05804, 2022.
61.Andrea Zanette, Martin J Wainwright, and Emma Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. In Advances in Neural Information Processing Systems, 2021.
62.Siyuan Zhang and Nan Jiang. Towards hyperparameter-free policy selection for offline reinforcement learning. Advances in Neural Information Processing Systems, 34:12864–12875, 2021.
63.Yuheng Zhang and Nan Jiang. On the curses of future and history in future-dependent value functions for off-policy evaluation. Advances in Neural Information Processing Systems, 37:124756–124790, 2024.
64.Yuheng Zhang, Yu Bai, and Nan Jiang. Offline learning in markov games with general function approximation. In International Conference on Machine Learning, pp. 40804–40829. PMLR, 2023.

Citation

MLA

Amortila, P., et al. “A Unifying View of Coverage in Linear Off-Policy Evaluation”. arXiv, 2026, http://arxiv.org/abs/2601.19030v1.

APA

Amortila, P., Huang, A., Krishnamurthy, A., & Jiang, N. (2026). A Unifying View of Coverage in Linear Off-Policy Evaluation. arXiv. http://arxiv.org/abs/2601.19030v1

Chicago

Amortila, P., A. Huang, A. Krishnamurthy, and N. Jiang. 2026. “A Unifying View of Coverage in Linear Off-Policy Evaluation”. arXiv. http://arxiv.org/abs/2601.19030v1.

Harvard

Amortila, P. et al. (2026) “A Unifying View of Coverage in Linear Off-Policy Evaluation”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2601.19030v1.

Vancouver

1. Amortila P, Huang A, Krishnamurthy A, Jiang N (2026) A Unifying View of Coverage in Linear Off-Policy Evaluation. arXiv

BibTeX

@article{amortila2026unifying,
  title = {A Unifying View of Coverage in Linear Off-Policy Evaluation},
  author = {Amortila, Philip and Huang, Audrey and Krishnamurthy, Akshay and Jiang, Nan},
  year = {2026},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2601.19030v1},
  eprint = {2601.19030}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

A Unifying View of Coverage in Linear Off-Policy Evaluation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Feature-dynamics coverage

Knowl 2 — Population finite-sample return guarantee

Knowl 3 — Empirical feature-dynamics coverage guarantee

Knowl 4 — LSTDQ as instrumental-variable regression

Knowl 5 — Coverage as occupancy in compressed feature dynamics

Knowl 6 — Bellman completeness recovers standard linear coverage

Knowl 7 — State abstractions yield aggregated concentrability

Knowl 8 — Tabular coverage reduces to a density-ratio second moment

Knowl 9 — A mean-matching sufficient condition for coverage at most one

Knowl 10 — Bounded-residual LSTDQ avoids dependence on the conditioning of A

References

Citation

BibTeX

Access the Paper