A Unifying View of Coverage in Linear Off-Policy Evaluation

AI summary

Overview

Research area: Reinforcement learning theory, specifically off-policy evaluation (OPE) with linear function approximation and the role of coverage parameters in finite-sample guarantees.

Technical level: Advanced. The paper is a theoretical statistics/RL analysis paper built on linear algebra (singular values, spectral radius, Mahalanobis norms), instrumental-variable regression, and matrix concentration. It assumes fluency with MDP notation, Bellman operators, and finite-sample bounds.

Scope: The paper derives a new finite-sample error bound for the LSTDQ algorithm under only linear realizability, introduces a new coverage parameter ("feature-dynamics coverage"), and shows it reduces to known coverage notions in special cases (tabular MDPs, γ = 0, and Bellman-complete settings).

What This Paper Is About

Linear off-policy evaluation estimates the value of a target policy from data collected under a different behavior policy, assuming the target Q-function is linear in a given feature map. Existing bounds for this setting rely on coverage parameters that are hard to interpret, and the most obvious candidate — 1/σ_min(A), where A is the key matrix LSTDQ inverts — has undesirable properties. The paper's goal is to replace that quantity with a principled coverage parameter that is scale-invariant, interpretable off-policy, and consistent with coverage definitions used elsewhere in the RL literature.

Key Contributions

1. A novel finite-sample analysis of LSTDQ under only linear realizability, motivated by an instrumental-variable (IV) view of the algorithm (crediting Bradtke and Barto, 1996, and Chen et al., 2022, for the IV framing).
2. A new coverage parameter, feature-dynamics coverage C^π_φ = (1−γ)² φ_0^T A^{-1} Σ A^{-T} φ_0, along with its empirical counterpart Ĉ^π_φ = (1−γ)² φ_0^T Â^{-1} Σ̂ Â^{-T} φ_0.
3. A dynamical-system interpretation showing that C^π_φ equals (μ^π_φ)^T Σ^{-1} μ^π_φ, where μ^π_φ is a discounted feature occupancy in a deterministic linear system driven by B^π = (Σ^{-1}Σ_cr)^T — the compressed, feature-level dynamics of the MDP.
4. Unification with existing coverage notions: the parameter recovers the χ² divergence between μ^π and μ^D in the tabular case, and recovers the standard linear coverage C^π_lin = (φ^π)^T Σ^{-1} φ^π under Bellman completeness. It also subsumes the χ² version of aggregated concentrability (Jia et al., 2024) as a special case.

Main Findings

• Theorem 1 (population coverage bound): For n ≥ n_0, with probability at least 1 − δ, |J_{Q̂_lstd}(π) − J(π)| ≲ V_max/(1−γ) · sqrt(C^π_φ · log(1/δ) / n) + o(sqrt(1/n)), where n_0 and the lower-order term may depend on d and 1/σ_min(A).

• Theorem 2 (empirical coverage bound): Under Assumptions 1 and 2, with probability at least 1 − δ, |J_{Q̂_lstd}(π) − J(π)| ≲ V_max/(1−γ) · sqrt(Ĉ^π_φ · (d + log(1/δ)) / n), with no lower-order terms. Ĉ^π_φ is treated as +∞ if  is not invertible. This removes σ_min(A) entirely from the bound at the cost of d dependence (it holds for all initial distributions μ_0 simultaneously).

• Recovers the γ = 0 regime: When γ = 0, A = Σ and C^π_φ = φ_0^T Σ^{-1} φ_0 = ||φ_0||²_{Σ^{-1}}, matching the population version of the well-established linear-regression/contextual-bandit bound of the form |J_{Q̂_lstd}(π) − J(π)| ≲ ||φ_0||_{Σ̂^{-1}} sqrt(log(1/δ)/n) V_max.

• Tabular interpretation: With unit-vector features (d = |S × A|), C^π_φ = (μ^π)^T Σ^{-1} μ^π = Σ_{s,a} μ^π(s,a)²/μ^D(s,a) = E_{μ^D}[(μ^π/μ^D)²], i.e., the χ²-divergence between target occupancy and data distribution up to a constant shift.

• Proposition 1 (dynamical-system form): With μ^π_{φ,0} := φ_0 and μ^π_{φ,t+1} = B^π μ^π_{φ,t}, and when ρ(B^π) < 1/γ, defining μ^π_φ := (1−γ) Σ_{t≥0} γ^t μ^π_{φ,t} gives C^π_φ = (μ^π_φ)^T Σ^{-1} μ^π_φ. Unlike the true expected feature φ^π = E_{(s,a)~μ^π}[φ(s,a)], which is always bounded, μ^π_φ may not be bounded and the sequence {μ^π_{φ,t}} may diverge.

• Proposition 2 (weaker on-policy condition): If φ contains a bias term (some θ_0 with φ(s,a)^T θ_0 ≡ 1), ρ(B^π) < 1/γ, and E_{μ^D}[φ(s,a)] = E_{μ^D}[φ(s',π)] = φ_0, then C^π_φ ≤ 1. Unlike prior on-policy conditions, this only requires the means of the two feature distributions to match, not the distributions themselves.

• Proposition 3 (comparison with Perdomo et al., 2023): sqrt(C^π_φ) = (1−γ) ||(I − γΣ^{-1/2}Σ_crΣ^{-1/2})^{-T} Σ^{-1/2} φ_0||2 ≤ (1−γ) ||φ_0||{Σ^{-1}} / σ_min(I − γΣ^{-1/2}Σ_crΣ^{-1/2}).

• Three defects of 1/σ_min(A) addressed: the paper argues that 1/σ_min(A) (i) lacks scale invariance (it changes if features are rescaled as φ_new = cφ), (ii) lacks an off-policy characterization and ignores the initial state distribution, and (iii) cannot be specialized to recover aggregated concentrability in state-abstraction settings, whereas the new parameter can.

• Empirical results: None are reported; the paper is purely theoretical, and the content provided is truncated partway through Section 5.1 (Proposition 3).

Methodology in Plain English

LSTDQ estimates the target Q-function by solving a linear system Aθ = b, where A = Σ − γΣ_cr is built from feature second moments and cross-moments. The authors reframe this as an instrumental-variable problem: the "true" temporal-difference feature φ_td(s,a) = φ(s,a) − γE[φ(s',a')|s,a] predicts reward linearly, but in data we only observe a noisy realization X = φ(s,a) − γφ(s',a'). Plain regression from X to the reward is therefore biased ("error in the variable"), and LSTDQ fixes this by using Z = φ(s,a) as an instrument.

Starting from this IV perspective, the authors adapt concentration tools from the IV literature (citing Xia et al., 2024, and Della Vecchia and Basu, 2025) to obtain high-probability bounds on the error of the final scalar estimate J_{Q̂_lstd}(π) = φ_0^T θ̂_lstd, where φ_0 is the expected initial feature. The resulting error decomposes into a term governed by the new coverage parameter times a statistical rate.

To interpret the parameter, they algebraically re-express A^{-1}ΣA^{-T} in terms of the matrix B^π = (Σ^{-1}Σ_cr)^T — which is the best linear predictor of next-features from current features (φ(s,a) ↦ φ(s',π)) — yielding a deterministic linear dynamical system whose discounted occupancy defines the coverage. They then specialize this expression to tabular MDPs, to γ = 0, and to Bellman-complete settings to verify it matches known quantities. Separate appendices provide the proofs (Appendix B), directional-bound discussion (Appendix A), a result eliminating 1/σ_min(A) from the population bound in exchange for 1/λ_min(Σ) (Appendix E), and function-estimation guarantees (Appendix D).

Why This Matters

Impact on research: Coverage parameters are the central currency of offline RL theory, and the linear-realizability setting was described by the authors as "starkly disconnected from the rest of the literature." This paper supplies a single parameter that reduces to tabular χ²-style density-ratio coverage, to standard linear coverage under Bellman completeness, to aggregated concentrability under state abstractions, and to the familiar ‖φ_0‖_{Σ^{-1}} term in the bandit case. It also connects LSTD analyses to the instrumental-variable literature, and sharpens the comparison with Perdomo et al. (2023), whose analysis was described as subsuming several prior tractability conditions (on-policy sampling, Bellman completeness, low distribution shift, symmetric stability, contractivity).

Real-world applications (as domains where OPE and coverage matter, since the paper reports no applied experiments):

• Healthcare treatment evaluation, where a new policy must be assessed from logged clinical data generated under a different protocol.
• Recommendation and advertising systems, where new ranking policies are evaluated from logs of an existing system.
• Robotics and control, where offline data from a safe or older controller is used to estimate the value of a new controller.
• Offline model selection, which the paper highlights as a problem where LSTDQ's realizability-only guarantees matter (citing Xie and Jiang, 2020a; Liu et al., 2025).

Industry relevance: Practitioners need to know when an offline evaluation is trustworthy. The new parameter gives an auditable diagnostic (Ĉ^π_φ) that can be computed from the same data used by the estimator, and Theorem 2's bound requires no lower-order terms and no σ_min(A), making it directly usable as a practical error scale. The fact that coverage can be quantified under mere realizability — without assuming Bellman completeness — widens the class of feature maps that are theoretically defensible in production pipelines. One author's affiliation is Microsoft Research, NYC, suggesting applied interest in large-scale offline evaluation, and the introduction cites statistical-computational trade-offs in LLMs (Foster et al., 2025) as a further consumer of coverage concepts.

Future Directions

• Sharpening the remaining regularity conditions. Theorem 1's lower-order term and burn-in constant still depend on 1/σ_min(A); Appendix E trades this for 1/λ_min(Σ), and the authors say they expect this can be further improved to leverage-score-type conditions (citing Hsu et al., 2011; Perdomo et al., 2023).
• Extending the analysis beyond LSTDQ. The paper states that the results "naturally extend" to LSTD (using state-features to approximate V^π) and off-policy LSTD via importance sampling, which remain to be worked out explicitly in the truncated content.
• Characterizing when C^π_φ is small. Proposition 2 gives one sufficient condition (bias term, ρ(B^π) < 1/γ, matching mean features), but a fuller off-policy characterization of tractability in terms of measurable data properties is left open.
• Empirical validation. The provided content contains no experiments; verifying whether Ĉ^π_φ is a practically useful diagnostic (and whether it predicts estimation error better than σ_min(A)-based quantities on real or benchmark MDPs) is an obvious next step.
• Function-estimation guarantees. Appendix D is referenced as deriving guarantees from the empirical bound, but the details are not included in the truncated content, leaving open how far the parameter reaches beyond scalar return estimation.

Target Audience

The primary audience is reinforcement learning theorists working on offline RL, off-policy evaluation, and coverage/concentrability conditions — particularly those interested in linear function approximation, LSTD/LSTDQ, or instrumental-variable methods. Secondary audiences include statisticians working on IV regression and errors-in-variables models, and applied researchers who need to understand under what data conditions linear OPE is statistically tractable. Because the paper compares directly with Perdomo et al. (2023) and the standard C^π_lin literature, readers should be comfortable with matrix algebra, singular values, spectral radius, and reading finite-sample bounds. The paper is not beginner-friendly, and it reports no experimental results.

Authors’ 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^π, 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.