A unifying view of coverage in linear off-policy evaluation
Philip Amortila, Audrey Huang, Akshay Krishnamurthy, Nan Jiang · 2026
Read A unifying view of coverage in linear off-policy evaluation by Philip Amortila, Audrey Huang, Akshay Krishnamurthy, Nan Jiang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19030.txt.
Introduction
Philip Amortila, Audrey Huang, Akshay Krishnamurthy, and Nan Jiang unify a key idea in judging policies from logged data. Off-policy evaluation asks how well a new rule would do, using data logged under an old one. In the linear case, error bounds hinge on a coverage number that says how well the old data covers the new rule's path.
Many past bounds each define coverage in their own way. The team gives one view that ties them together. A single lens on coverage helps researchers compare results and spot which assumptions truly drive the error in such studies.
Catalog record
| CREATOR | Philip Amortila, Audrey Huang, Akshay Krishnamurthy, Nan Jiang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 114 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-19030
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A unifying view of coverage in linear off-policy evaluation Philip Amortila, Audrey Huang, Akshay Krishnamurthy, Nan Jiang 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 Evaluation error ≤ poly ( C π , d , 1 / n , log ( 1 / δ ) ) , \textrm{Evaluation error}\leq\textrm{poly}(C^{\pi},d,1/n,\log(1/\delta)), where d d is the dimension of the features and C π 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. 1 Introduction Coverage is a foundational concept in reinforcement learning (RL) theory. In off-policy evaluation (OPE), the task of evaluating a target policy based on data collected from a different behavior policy, coverage characterizes the degree to which the data distribution contains relevant information about the target policy. The relevance of coverage extends beyond OPE, and the concept plays important roles in offline policy learning ( 27 ; 54 ) , online RL ( 55 ; 3 ; 4 ) , or even statistical-computational trade-offs in LLMs ( 19 ) . Coverage provides a mathematical characterization of distribution shift which is a central challenge in RL. Mathematically, coverage is manifested as coverage parameters in finite-sample guarantees: for example, standard OPE guarantees often take the form \displaystyle\textrm{Evaluation error}\leq\textrm{poly}(C^{\pi},d,1/n,\log(1/\delta)), (1) where n is sample size, \delta is the failure probability, d is the statistical dimension of the function class, \delta is the failure probability, and C^{\pi} is the coverage parameter. The definition of C^{\pi} can take many different forms depending on the algorithm and the assumptions, as well as how the proof handles error propagation through the dynamics of the MDP ( 18 ) . The most naïve definition is \|\mu^{\pi}/\mu^{D}\|_{\infty} , the boundedness of density ratio between the target policy’s discounted occupancy \mu^{\pi} and the data distribution \mu^{D} . More refined definitions often take advantage of the structure of the underlying MDP or the function-approximation scheme. Comparisons between these definitions offer connections and unified understanding across different learning settings, such as policy evaluation vs. optimization ( 17 ; 27 ) , offline vs. online ( 55 ) , tabular vs. function approximation ( 60 ) , Markovian vs. partially observed ( 64 ) , and single-agent vs. multi-agent RL ( 13 ; 63 ) . While a unified understanding of RL through the lens of coverage is emerging, one of the most fundamental settings—where the target value function is linearly realizable in a given feature map—eludes such understanding and remains starkly disconnected from the rest of the literature. The most natural algorithm for this setting is arguably LSTD(Q) ( 10 ; 29 ) . Despite recent statistical results for this method ( 16 ; 36 ; 42 ) , the error bounds often come with obscure conditions and are hard to interpret, with little or no understanding of which quantities play the role of coverage and how they connect to coverage parameters in related settings and algorithms. On the other hand, simpler analyses do provide more interpretable candidates, such as 1/\sigma_{\min}(A) with A=\mathbb{E}_{\mu^{D}}[\phi(s,a)(\phi(s,a)^{\top}-\gamma\phi(s^{\prime},\pi)^{\top})] being the key matrix estimated in LSTDQ ( Section 2.1 ). Given that LSTDQ approximates Q^{\pi}\approx\phi^{\top}\theta by solving a linear equation in the form of A\theta=b , 1/\sigma_{\min}(A) is a very natural candidate as it determines the invertibility of A and the solution’s numerical stability. While bounds in the form of Eq. ( 1 ) can be established with C^{\pi}=1/\sigma_{\min}(A) , the quantity 1/\sigma_{\min}(A) is unsatisfactory in many aspects as a coverage parameter: 1. Lacking scale invariance. The value of \sigma_{\min}(A) can change arbitrarily if we simply redefine the features as \phi_{\textrm{new}}=c\phi . 1 1 1 42 provide a bound that depends on a term related to our coverage parameter and is scale invariant. We will compare and connect to their results in Section 4 . While seemingly unrelated, this issue is mathematically tied to the fact that \sigma_{\min}(A) as a coverage parameter has no concern over the initial state distribution of the MDP which should play an important role in the definition of coverage. 2. Lacking off-policy characterization. Coverage parameters provide important understanding for when data contains relevant information about the target policy. For 1/\sigma_{\min}(A) , however, the only known characterization to our knowledge is its boundedness in the restrictive on-policy case, and its magnitude is hard to interpret for general off-policy distributions. 3. Lacking unification with other analyses. State abstractions are a special case of linear function approximation, under which LSTDQ coincides with the model-based solution. Prior works have established aggregated concentrability ( 23 ) as the appropriate coverage parameter for this setting, which cannot be recovered by specializing 1/\sigma_{\min}(A) . Moreover, both concepts differ significantly from standard definitions of coverage in linear OPE when analyzed under the Bellman-completeness assumption: standard definitions measure coverage by analyzing how errors propagate under the groundtruth dynamics , whereas aggregated concentrability does so under the compressed dynamics determined by the abstraction scheme. In this paper, we provide a novel finite-sample analysis of LSTDQ inspired by an instrument-variable (IV) view ( 11 ; 12 ) , which comes with a new coverage parameter that we call feature-dynamics coverage , C^{\pi}_{\phi} . Feature-dynamics coverage replaces 1/\sigma_{\min}(A) and elegantly addresses the above problems. Furthermore, it corresponds to feature coverage in a linear dynamical system induced by the features (first studied by 41 ). The system is the transition dynamics of the true MDP compressed through the given features, and naturally subsumes the \chi^{2} version of aggregated concentrability as a special case. Furthermore, given Bellman-completeness as an additional assumption, feature-dynamics coverage recovers the standard notion of linear coverage, successfully unifying the previously fragmented understanding. 2 Preliminaries Markov Decision Process (MDP) We consider the groundtruth environment modeled as an infinite-horizon discounted MDP (\mathcal{S},\mathcal{A},P,R,\gamma,\mu_{0}) , where \mathcal{S} is the state space, \mathcal{A} is the action space, P:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S}) is the transition dynamics ( \Delta(\cdot) is the probability simplex), R:\mathcal{S}\times\mathcal{A}\to\Delta([0,R_{\max}]) is the reward function, \gamma\in[0,1) is the discount factor, and \mu_{0}\in\Delta(\mathcal{S}) is the initial state distribution. We assume \mathcal{S} , \mathcal{A} are finite, but their cardinalities can be prohibitively large and thus should not appear in sample-complexity guarantees. A policy \pi:\mathcal{S}\to\Delta(\mathcal{A}) induces a distribution over random trajectories, generated as s_{0}\sim\mu_{0} , a_{t}\sim\pi(\cdot|s_{t}) (or simply