Q-MMR: Off-Policy Evaluation via Recursive Reweighting and Moment Matching
arXiv:2605.06474v1 [cs.LG] 7 May 2026
Xiang Li Nanjing University [email protected]
Nan Jiang UIUC [email protected]
Abstract We present a novel theoretical framework, Q-MMR, for off-policy evaluation in finite-horizon MDPs. Q-MMR learns a set of scalar weights, one for each data point, such that the reweighted rewards approximate the expected return under the target policy. The weights are learned inductively in a top-down manner via a moment matching objective against a value-function discriminator class. Notably, and perhaps surprisingly, a data-dependent finite-sample guarantee for general function approximation can be established under only the realizability of Qπ , with a dimension-free bound—that is, the error does not depend on the statistical complexity of the function class. We also establish connections to several existing methods, such as importance sampling and linear FQE. Further theoretical analyses shed new light on the nature of coverage, a concept of fundamental importance to offline RL.
1
Introduction
Off-policy evaluation (OPE) using value-function approximation is a fundamental and core problem in the theory of reinforcement learning (RL). In this task, one estimates the expected return of a target policy π using data collected from some behavior policy, by leveraging a function class F that captures the target policy’s Q-value function Qπ . For general function approximation, the canonical approach is Fitted-Q Evaluation (FQE), which solves a sequence of least-square regression problems [Ernst et al., 2005, Chen and Jiang, 2019, Le et al., 2019]. FQE can also be viewed as the theoretical prototype of the TD algorithm, which is a foundational building block of RL. While the theory of OPE with general value-function approximation is largely considered a mature area, where finite-sample guarantees for FQE and related algorithms have been established [Jiang and Xie, 2025], there are still notable gaps in our understanding: • Dimension dependence. All existing analyses under general function approximation (GFA) need to translate the empirical loss to its population counterpart, during which one pays for the statistical dimension of the function class (e.g., log |F| for finite F or the log covering number for continuous classes). While this dependence is widely accepted, there are clearly situations where this is loose: for example, when the data is on-policy, Monte-Carlo (MC) estimate provides straightforward guarantees without any log |F | dependence, raising the question of whether the dimension dependence is real or an artifact of the algorithm design or its analysis. • Inconsistency between the general and the linear analyses. Apart from the analyses under GFA, researchers have also obtained refined, sharp (i.e., often minimax optimal) guarantees in the linear √ and the tabular settings [Duan et al., 2020, Yin and Wang, 2021]. As it turns out, the main 1/ n terms in these guarantees are indeed dimension-free. Moreover, the linear analyses hold under strictly weaker conditions than the Bellman-completeness assumption widely adopted in the GFA analyses. In fact, not only the linear analyses cannot be obtained by specializing the GFA analyses Preprint.
Table 1: Comparison between existing analyses and ours. Each entry corresponds to an analysis of an algorithm (row) in a setting (column). Columns to the right represent more specialized settings, whose results are plug-in instantiations of more general analyses to the left. (This is why “FQE” and “Linear FQE” do not coincide in the linear columns, even though they become the same algorithm there.) For our analyses, we use the population version of coverage (see Section 4) for better comparison with the existing literature. “Dim-free" refers to the property of not depending on the dimension d or log |F |-type terms in the data-dependent bound, or only depending on it in higher-order terms in the data-independent bound. (∗) Technically, the linear analysis of Duan et al. [2020] considers the linear-MDP setup which is stronger than Bellman completeness, but it is likely that their proofs and results can be adapted to the weaker settings (e.g., only realizability), especially given the later insights of Perdomo et al. [2023], Amortila et al. [2026]; see Appendix B.4 for details. General + realizability DimCoverage free?
Coverage
Dimfree?
Linear + realizability DimCoverage free?
|Edπ [f −f ′ ]| q h [(f −f ′ )2 ] f,f ′ ∈Fh EdD h
✗
N/A
sup
FQE Linear FQE Ours
General + completeness
N/A q
EdD [wh⋆ 2 ] h
Linear + completeness Coverage
Dimfree?
∥Edπh [ϕ]∥Σ−1
✗
h
N/A ✓
sup f ∈span(Fh )
(∗)
|Edπ [f ]| q h EdD [f 2 ]
✓
∥ψh ∥Σ−1 h
✓
(∗)
∥Edπh [ϕ]∥Σ−1 h
h
to the linear classes, they also give rise to novel concepts—such as seemingly unconventional notions of coverage (see Section 4)—that are nowhere to be found in the GFA analyses. In this paper, we address the above gaps with a novel algorithmic framework for OPE in finite-horizon MDPs. The Q-MMR algorithm learns a set of weights, one for each data point, inductively in a top-down manner via a moment-matching objective against a value-function discriminator class F. Our main guarantee is a data-dependent finite-sample bound (Theorem 1, Section 3), which is dimension-free in that it has no explicit dependence on the complexity of F. (A data-independent bound will be provided in Section 4, where only the higher-order term is dimension dependent.) For linear F, Q-MMR coincides with linear FQE; unlike the GFA analyses of FQE (which is dimensiondependent and requires Bellman completeness), our guarantees fully recover the key properties of the fine-grained linear and tabular analyses, under only the realizability of Qπ . A key quantity in our bound is the second moment of the learned weights, which plays the role of an empirical coverage parameter [Amortila et al., 2026]. In further analyses (Section 4), we identify its population counterpart and examine its properties, which shed light on the nature of coverage in offline RL. The high-level take-away messages are consistent with the (somewhat counterintuitive) recent findings [Perdomo et al., 2023, Amortila et al., 2026] (e.g., the coverage target is not the feature occupancy in the real MDP, but that from an approximate linear dynamical system; see Eq.(6)), but those findings were restricted to the linear setting and difficult to generalize. Our algorithms and analyses provide a much-needed generalization of such insights to GFA; see Table 1 for a summary.
2
Preliminaries
Finite-horizon MDPs We consider an H-step finite-horizon MDP, where a random trajectory takes the form of s0 , a0 , r0 , s1 , a1 , r1 , . . . , sH , aH , rH . W.l.o.g., s0 , a0 is fixed and r0 ≡ 0, which will allow us to write our algorithm in a concise and unified manner. We also assume that the state space SH is layered, i.e., S = h=0 Sh , where {Sh }H h=0 are disjoint sets and it always holds that sh ∈ Sh . The layered state space makes it convenient to use stationary notation for time-inhomogeneous objects. Let A be the action space, and we consider finite and discrete S and A although their cardinalities can be arbitrarily large. R : S × A → ∆([0, Rmax ]) is the reward function, and P : S × A → ∆(S) is the transition dynamics, where P (·|s, a) for s ∈ Sh and a ∈ A is always supported on Sh+1 . A policy π : S → ∆(A) determines a distribution of trajectories starting from the fixed s0 , a0 as rh ∼ R(·|sh , ah ), sh+1 ∼ P (·|sh , ah ), ah+1 ∼ π(·|sh+1 ), ∀h ≥ 0. We use Eπ [·] to denote 2
✓
PH the expectation under such a distribution, and J(π) := Eπ [ h=1 rh ] is the expected return. Note PH that the random return h=1 rh ∈ [0, Vmax ] where Vmax := HRmax . The occupancy distribution π dh is the marginal distribution of (sh , ah ) under π. The Q-function of π, Qπ (s, a), is defined as: PH ∀s ∈ Sh , a ∈ A, Qπ (s, a) = Eπ [ h′ =h rh′ |sh = s, ah = a]. We use Qπh to denote Qπ restricted to Sh × A. It satisfies the Bellman equation: Qπh−1 = T π Qπh , where T π is the Bellman operator: given any f : Sh × A → R and s ∈ Sh−1 , a ∈ A, (T π f )(s, a) = Er∼R(·|s,a),s′ ∼P (·|s,a) [r + f (s′ , π)]. Here f (s, π) is a shorthand for Ea∼π(·|s) [f (s, a)] and f (s′ , π) for s′ at time H + 1 is always treated as 0. Since s0 , a0 is fixed, we have Qπ (s0 , a0 ) = J(π). Off-Policy Evaluation (OPE) In OPE, we want to estimate J(π) for a given target policy π, using data trajectories collected with a behavior policy πD . We assume the dataset consists of (i) (i) (i) (i) (i) (i) n i.i.d. trajectories, {(s0 , a0 , r0 , . . . , sH , aH , rH )}ni=1 , and dD h is the marginal distribution of (sh , ah ) in the data. ED [·] denotes expectation w.r.t. the data distribution. To handle large state and action spaces, we consider the standard setting of function approximation, π where a function class F = {Fh }H h=1 is used to model Q ; each Fh consists of functions of the type Sh × A → R. Throughout the paper we assume the standard realizability assumption, that is: Assumption 1 (Realizability). Qπ ∈ F, which is shorthand for Qπh ∈ Fh , ∀h ∈ [H]. Extension to handle misspecification is routine (see comment below Eq.(5)). Note that most standard analyses of OPE algorithms, especially those that use a general function class F, typically require the stronger Bellman-completeness assumption [Antos et al., 2008, Chen and Jiang, 2019]: Assumption 2 (Bellman Completeness). T π f ∈ Fh , ∀f ∈ Fh+1 , h ∈ [H]. Our main guarantee (Theorem 1), however, does not rely on such a stronger assumption, and we discuss the implications of Bellman completeness in our results in Section 4. While our main results are derived for GFA, to develop intuitions and make connections with the literature, it will be useful to consider the special case of linear and tabular function approximation: Definition 1 (Linear function class). F is linear in a given feature map ϕ : S × A → Rd , if F = Fϕ = {(s, a) 7→ ϕ(s, a)⊤ θ : ∥θ∥2 ≤ Θ} for some boundedness parameter Θ > 0. Definition 2 (Tabular function class). F is tabular if F = Ftab = [0, Vmax ]S×A . Fixed-design analyses of linear regression We briefly recall the fixed-design analysis of linear regression (LR), which will be extremely helpful for understanding our algorithm and analyses, since they correspond to the special case of OPE with H = 1 and linear F. Consider LR over b := 1 P xi x⊤ is invertible. LR gives a dataset {(xi , yi )}ni=1 where xi ∈ Rd , and assume Σ i i n b = 1 P x⊤ Σ b −1 1 P xi yi , and thus makes the prediction of x⊤ b −1 xi yi on a new xtest . θb = Σ θ test i i test n n p Standard fixed-design analysis provides a O(∥xtest ∥Σ log(1/δ)/n) high-probability error bound b −1 q b −1 xtest is the Mahalanobis norm. This bound is for this prediction, where ∥xtest ∥Σ x⊤ b −1 = test Σ “fixed-design” as the concentration argument is w.r.t. the randomness of yi |xi , where {xi }ni=1 are treated as fixed instead of stochastic. It can be proved via a moment-matching formulation of LR, which is a special case of our Algorithm 1; see Appendix A for further detail. Math notation [H] = {1, 2, . . . , H}. ≲ and ≳ are inequalities that hold up to a positive absolute constant. We also use the big-Oh notation O(·) to highlight dependencies on selected variables. For a (1) (1) (n) (n) function f ∈ Fh , we use f |n ∈ Rn to denote its sample evaluation f (sh , ah ), . . . , f (sh , ah ) .
3
Algorithm and Analyses (i)
(i)
(i)
Our algorithm, Q-MMR, learns a scalar weight w bh for each state-action pair (sh , ah ) in the data, Pn PH (i) (i) b and forms the estimate of J(π) using the reweighted reward: J(π) := n1 i=1 h=1 w bh rh . In (i) fact, the estimate will be unbiased if w bh is set to the following expression, as well understood from 3
Algorithm 1 Q-MMR (Q-function-based Moment-Matched Reweighting) (i)
(i)
(i)
(i)
(i)
(i)
Input: Target policy π, data {(s0 , a0 , r0 , . . . , sH , aH , rH )}ni=1 , function class F = {Fh }h . Pn PH (i) (i) [n] [n] (i) b bh rh . Output: {w bh }h , where w bh := [w bh ]i ∈ Rn ; J(π) := h=1 n1 i=1 w (i) 1: Initialize w b0 ≡ 1, ∀i. 2: for h = 1 to H do [n] [n] 3: Choose w bh as the wh that (approximately) minimizes the loss n n 1 X (i) 1 X (i) (i) (i) (i) [n] [n] wh f (sh , ah ) − w b f (sh , π) . Lbh (wh ; w bh−1 ) := sup n i=1 h−1 f ∈Fh n i=1 q P (i) 2 [n] [n] (Optional) Among w bh with the same loss, minimize ∥w bh ∥[n] := n1 i (w bh ) . 4: end for
(1)
the literature on marginalized importance sampling (MIS) [Liu et al., 2018, Xie et al., 2019]: (i)
(i)
(i)
(i)
(MIS Ratio) dπh (sh , ah )/dD (2) h (sh , ah ). However, learning the MIS ratio in Eq.(2) requires strong assumptions and is sufficient but not (i) necessary for accurate OPE, and our algorithm enjoys guarantees when w bh does not learn this ratio but something more nuanced (see Section 4). Nevertheless, to develop the first intuition, it is useful to temporarily pretend that our algorithm learns such weights inductively in a top-down manner. Algorithm Intuition We now provide a non-rigorous (but relatively easy to understand) explana[n] (i) tion of our Algorithm 1, Q-MMR, which computes w bh = {w bh }ni=1 level-by-level from h = 0 to H. We do not represent such weights in a parameterized manner as standard MIS methods [Liu et al., 2018, Uehara et al., 2020], but rather learn a separate scalar weight for each of the n data points. Since (s0 , a0 ) is the fixed dummy initial state-action pair, there is no distribution shift at h = 0 and (i) dπ (s ,a ) we set w0 = dD0 (s00 ,a00 ) ≡ 1. 0
(i)
Inductively, suppose we already have w bh−1 ≈ (i)
(i)
(i)
(i)
dπ h (sh ,ah ) dD h (sh ,ah ) 1
(i)
(i)
dπ h−1 (sh−1 ,ah−1 ) (i) (i) dD h−1 (sh−1 ,ah−1 )
(i)
, and we want to compute w bh ≈
. (Again, this is generally not the case in our analysis.) By the principle of importance [n]
(i)
π sampling, w bh−1 = {w bh−1 }ni=1 reweights the data distribution at level h − 1 from dD h−1 to dh−1 . As a consequence, the following (reweighted) distributions over (sh , ah ), as characterized by their generative processes, produce the same expectations: dπ
(s
,a
)
h−1 h−1 h−1 sh ∼ P (·|sh−1 , ah−1 ), ah ∼ π(·|sh ), (sh−1 , ah−1 ) ∼ dD h−1 , reweighted by dD (sh−1 ,ah−1 ) h−1
⇔ sh ∼ P (·|sh−1 , ah−1 ), ah ∼ π(·|sh ), (sh−1 , ah−1 ) ∼ dπh−1 ⇔ (sh , ah ) ∼ dπh . This way, we successfully produce a weighted distribution that “looks like” dπh —by applying the (i) (i) weight w bh−1 at level h − 1 to the state-action pair (sh , π) at level h. To complete the induction, (i)
(i)
(i)
(i)
we will need w bh that reweight (sh , ah ), but now we only have weights that reweight (sh , π). To bridge this gap, Eq.(1) employs a moment-matching objective based on the Integral Probability (i) [n] (i) (i) Metric (IPM): we find wh such that w bh -reweighted {(sh , ah )}ni=1 is indistinguishable from [n] (i) w bh−1 -reweighted {(sh , π)}ni=1 , up to the discrimination power of Fh . 3.1
Finite-Sample Guarantee
We now present the main analyses for Q-MMR, which face two key challenges: 1. While the earlier intuition appeals to learning the MIS ratio, this is generally not guaranteed when we only assume realizability (Assumption 1). Under such a weak assumption, we need to bound [n] the OPE error without showing that w bh tracks the MIS ratio. 1 That is, given distributions p and q over X and f : X → R, we have E [f ] = E [p/q · f ] when p/q < ∞. p q
4
[n]
2. The number of free parameters ({w bh }h ) scales linearly in n, the number of data points. Under the naïve parameter counting argument, this usually results in overfitting, i.e., an error bound that does not shrink as n grows. Such a practice of assigning a separate scalar to each data point is found in distributionally robust optimization [Rahimian and Mehrotra, 2019] and balancing weights [Kallus, 2018], and its analyses often require sophisticated concentration machinery. We address both challenges by a starkly simple and elementary analysis, whose core proof takes but a few lines. Perhaps surprisingly, our analysis does not perform any union bound over the function class F at all, which avoids the statistical complexity of F (e.g., log |F| for finite F ). The analysis is given as follows, where we start with the OPE error: PH 1 Pn PH 1 Pn (i) (i) (i) (i) (r0 ≡ 0) bh rh − J(π) = bh rh − J(π) h=0 n h=1 n i=1 w i=1 w PH 1 Pn P (i) (i) (i) (i) stat bh Qπ (sh , ah ) − Qπ (sh+1 , π) − J(π) + H ≤ (3) h=0 n i=1 w h=0 ϵh PH 1 Pn (i) (i) (i) (i) (i) (i) bh+1 Qπ (sh+1 , ah+1 ) − J(π) (4) ≤ bh Qπ (sh , ah ) − w h=0 n i=1 w PH PH [n] [n] + h=1 Lbh (w bh ; w bh−1 ) + h=0 ϵstat h PH b PH stat [n] [n] = h=1 Lh (w bh ; w bh−1 ) + h=0 ϵh . We explain the derivation step by step: (i)
(i)
(i)
(i)
1. First, we replace rh with Qπ (sh , ah ) − Qπ (sh+1 , π) by paying for an error term ϵstat h , where q Pn P (i) 2 [n] (i) (i) stat 1 1 π (i) (i) π (i) ≤ ϵ ∝ ∥ w b ∥ := w b Q (s , a ) − r − Q (s , π) bh ) [n] h i=1 i (w h h h h h h+1 n n holds with high probability. This follows from a standard concentration argument, which treats (i) (i) (i) (i) (i) (i) {(sh , ah )}ni=1 as fixed and is w.r.t. the randomness of rh and sh+1 conditioned on (sh , ah ). [n]
(i)
(i)
As long as w bh are chosen only based on the trajectory prefixes up to {(sh , ah )}ni=1 and do not depend on the randomness after time h, the independence across the terms is intact, though the (i) range of each term will be amplified by the size of w bh . (i)
(i)
(i)
(i)
(i)
bh Qπ (sh+1 , π) with w bh+1 Qπ (sh+1 , ah+1 ). Their difference 2. From (3) to (4), we replace w is almost exactly the matching loss used in our algorithm, except that we do not know Qπh+1 in the algorithm and instead relax it to supf ∈Fh+1 using realizability (Assumption 1): n n 1 X (i) π (i) 1 X (i) (i) (i) bh+1 Qπ (sh+1 , ah+1 ) − b Q (sh+1 , π) w w n i=1 n i=1 h
≤
(5)
n n 1 X (i) 1 X (i) (i) (i) (i) [n] [n] w bh+1 f (sh+1 , ah+1 ) − w b f (sh+1 , π) = Lbh+1 (w bh+1 ; w bh ). n i=1 h f ∈Fh+1 n i=1
sup
If realizability is not satisfied, an additional misspecification term will occur in the above inequality. In addition, the realizability of Fh+1 can be relaxed to that of the convex hull of Fh+1 as the matching loss is convex in f [Uehara et al., 2020], which we omit for a clean presentation. 3. Finally, the first line of Eq.(4) vanishes due to telescoping, as the negative term in the h-th term (i) exactly cancels the positive term in the (h + 1)-th term, leaving only w b0 Qπ (s0 , a0 ) = J(π). This immediately leads to the following guarantee of Q-MMR; see proof in Appendix B.1. [n]
[n]
Theorem 1. For any choice of weight vectors {w bh }h in Algorithm 1 where w bh only depends on (i) (i) (i) (i) (i) {(s0 , a0 , r0 , . . . , sh , ah )}, under Assumption 1, with probability at least 1 − δ, we have PH [n] [n] b − J(π) ≤ PH Lbh (w J(π) bh ; w bh−1 ) + h=0 ϵstat h , h=1 [n]
where ϵstat bh ∥[n] · Vmax h = ∥w
q
2 log(2(H+1)/δ) . n
5
Dimension-freeness and “WYSIWYG” Standard OPE analyses in offline RL under general function approximation need to translate the empirical loss to its population counterpart, during which one pays for the statistical dimension of the function class. In contrast, our analysis only performs concentration on Qπ (Eq.(3)), and no concentration on F is needed, resulting in a dimension-free bound. In addition, the empirical matching loss Lb observed in the algorithm (Eq.(1)) shows up in the bound, which makes Theorem 1 “what you see is what you get (WYSIWYG)”. One downside is that it can be difficult to tell when the matching loss will be large vs. small; as we will see below, in special cases like linear F, there are mild sufficient conditions (i.e., invertible sample covariance matrix) which guarantee that 0 matching loss is achievable (Propositions 2 and 3). Uncertainty quantification In addition to the empirical matching loss, the other term in the [n] bound, ϵstat , depends on the 2nd moment of w bh , which is also available to the learner. Therefore, the h bound in Theorem 1 is directly computable from the data, which means that our Q-MMR algorithm automatically comes with uncertainty quantification. Similar results can be found in existing analyses of linear OPE, such as Duan et al. [2020, Theorem 4], and our bound in Theorem 1 applies more generally to GFA and improves over Duan et al. [2020] in several aspects; see Appendix B.4. “Fixed-design” analysis Theorem 1 provides a data-dependent bound, which is an unusual form of guarantee in the OPE literature. By considering the following special case, however, we see that Theorem 1 is the natural generalization of the standard fixed-design analysis in linear regression. (i)
(i)
Proposition 2. Consider H = 1 and linear F (see Definition 1). Let xi = ϕ(s1 , a1 ). For invertible (i) b −1 xi where xtest = 1 Pn ϕ(s(i) , π), we have b = 1 Pn xi x⊤ , with w Σ b1 = x⊤ test Σ i 1 i=1 i=1 n n [n]
[n]
(i) Lb1 (w b1 ; w b0 ) = 0,
[n]
(ii) ∥w b1 ∥[n] = ∥xtest ∥Σ b −1 .
and
[n] b − J(π)| ≤ ϵstat + ϵstat , where ϵstat ∝ ∥w The bound in Theorem 1 becomes |J(π) b1 ∥[n] = ∥xtest ∥Σ b −1 . 0 1 1 (i) † † b is non-invertible, the minimizer is w b When Σ b1 = x⊤ Σ x where (·) is pseudo-inverse. i test
In other words, when H = 1 and F is linear, our algorithm and guarantee exactly recover the moment-matching form of linear regression (LR) and its fixed-design analysis (see Section 2 and b Appendix A): the error bound of LR depends on ∥xtest ∥Σ b −1 , which is data dependent due to Σ and [n] stat coincides with our ∥w b1 ∥[n] in the ϵstat 1 term. Our ϵ0 term is a small overhead that corresponds to how xtest concentrates to its expectation along the direction of the true linear coefficients under the randomness of s1 ; see Footnote 5 in Appendix A for further details. Non-uniqueness of w b and the principle of least 2nd moment So far, Theorem 1 holds for any [n] [n] choice of {w bh }h , including those that do not minimize Eq.(1). Moreover, even if we require w bh [n] to exactly minimize Lbh (·; w bh−1 ), the solution is also generally not unique. As it turns out, this flexibility is a blessing which allows us to unify and make connections to several existing methods. [n] That said, it is still desirable that we fix a canonical choice of w bh to have a fully-specified algorithm. [n] Among all w bh that achieves the minimal loss, it is naturally preferred to choose the one with the [n] least 2nd moment ∥w bh ∥[n] since this quantity appears in the bound through ϵstat h . We call this the principle of least 2nd moment. In fact, in Proposition 2, the choice of weights that recovers linear regression is exactly the minimizer of the 2nd moment. [n]
In practice, there can be situations where even the 2nd moment-minimizing w bh is too large, causing stat b a poorly behaved ϵh term. This can happen, for example, when Σ is near singular in the linear setting. In such cases, one needs to balance the bias-variance trade-off, by potentially giving up [n] some matching loss in exchange for a smaller ∥w bh ∥[n] (and thus ϵstat h ). This can be implemented via [n] constraint optimization (e.g., minimizing Lb up to some budget for ∥w bh ∥[n] ), or via a Lagrangian form that corresponds to ridge regression in the linear setting (see Appendix B.5). In the rest of the [n] paper, however, we will not consider constraint or regularization on w bh to keep the analyses clean. 6
3.2
Connection to Existing Methods
We discuss the relationship between Q-MMR and several existing methods to establish connections and help provide further insights. 3.2.1
Monte-Carlo Policy Evaluation and Importance Sampling
In the special case where the data is on-policy, i.e., the trajectories are sampled from π itself, it is Pn PH (i) well known that the Monte-Carlo estimator, n1 i=1 h=1 rh , is a simple and effective method that achieves dimension-free error guarantees, since the analysis simply applies concentration arguments to the i.i.d. random returns. This also shows the looseness of standard OPE analyses that depends on log |F| [Antos et al., 2008, Chen and Jiang, 2019], as those guarantees do not automatically eliminate log |F| when data is on policy. In contrast, Q-MMR immediately recovers MC in this setting if we (i) simply choose w bh ≡ 1. (Note that this choice is not necessarily minimizing the 2nd moment of [n] [n] [n] w bh .) The matching loss Lbh (w bh ; w bh−1 ) is 0 under such weights,2 and Theorem 1 is dimension free. More generally, when the behavior policy πD is stochastic, a variant of our algorithm can also recover step-wise importance sampling, the generalization of MC to the off-policy setting. In particular, if we P (i) (i) bh−1 f (sh , π) in Eq.(1) to3 change the target embedding n1 i w (i) (i) 1 X (i) (i) (i) π(ah |sh ) w bh−1 f (sh , ah ) (i) (i) , πD (ah |sh ) n i
which produces the same target embedding after marginalizing over the action randomness, then (i) (i) Qh π(ah′ |sh′ ) [n] (i) b b[n] ; w b ) = 0. setting w b = ′ (i) (i) ensures Lh (w h
h =1 π (a |s ) D h′ h′
h
h−1
This example also demonstrates the role of F and the importance of 2nd-moment minimization: if we [n] only care about minimizing the matching loss Lb but not the size of w bh , we can always set Lb to 0 by [n] setting w bh to be the cumulative importance weights, which generally incurs exponential-in-horizon [n] variance. This is avoided when structured F admits many choices of w bh that equally minimize the matching loss, and we can choose the smallest one to significantly dampen the weight size. 3.2.2
Linear and Tabular FQE
As mentioned in Section 1, the canonical OPE method under value-function approximation is FQE, which fits Qπh in parametric forms recursively from bottom up via a series of squared-loss regressions. While our Q-MMR is a top-down procedure that learns non-parametric weights, it coincides with FQE in the linear and tabular setting (Definitions 1 and 2), which should not be surprising given the connection between Q-MMR and linear regression when H = 1 (Proposition 2). b h = 1 P ϕ(s(i) , a(i) )ϕ(s(i) , a(i) )⊤ Proposition 3. (i) In the linear setting (Definition 1), assume Σ i h h h h n is invertible for all h ≥ 1. Consider Q-MMR where in each step h we choose the least-2nd-moment [n] [n] b weight w b[n] that sets Lbh (w bh ; w bh−1 ) = 0. The final prediction of J(π) is identical to that given by linear FQE [Duan et al., 2020] without ridge regression. (ii) As a further special case in the tabular setting (Definition 2), assume every state-action pair appears in the dataset, Q-MMR and FQE both coincide with the model-based (certainty-equivalence) (i) c c D is the empirical π (s(i) , a(i) )/d D (s(i) , a(i) ) where d solution [Yin and Wang, 2021], and w bh = dc h h h h h h h π is the occupancy of π in the empirical MDP. frequency of data and dc h More detailed definitions (e.g., the FQE procedure) and the proof can be found in Appendix B.3. In the linear and tabular settings, prior works [Duan √ et al., 2020, Yin and Wang, 2021] have established fine-grained analyses where the leading O(1/ n) terms are dimension-free, which separates them from the log |F|-dependent guarantees for GFA and no unification is known to this date. Our results fill this gap in theoretical understanding, as these fine-grained results are recovered 2 This holds when π is deterministic; when π is stochastic, it still holds if we consider the IS variant of our algorithm, as described below. 3 This resembles how targets are set up in TD, such as expected SARSA vs. its off-policy version [Sutton and Barto, 2018].
7
(and sometimes improved) when we specialize our Theorem 1 to the linear/tabular settings. We provide a detailed discussion and comparison w.r.t. these prior results in Appendix B.4. Proposition 3 also provides intuition for Lbh when it takes non-zero values. In the tabular case, Lbh may not be minimized to 0 if some (s, a) ∈ Sh × A does not appear in the data at all, and the π will result in a non-zero matching loss. corresponding mass in dc h 3.3
Computational Efficiency
So far our analyses are only concerned with statistical efficiency. The computational efficiency of [n] the method boils down to whether we can efficiently minimize Lbh ( · ; w bh−1 ) (Eq. (1)), which is a standard IPM objective. As already discussed in Section 3.2, this is easy to optimize when F is linear as it simply amounts to linear regression. For general function approximation, given the minimax form (arg minw[n] supf ∈F ), we can efficiently approximate the solution via the no-regret + h best-response framework [Freund and Schapire, 1999] given standard optimization oracles over F; see further discussion in Appendix B.5.
4
Understanding the Learned Weights
The results thus far leave a few important and interrelated questions open: Boundedness of weights. Theorem 1 only assumes realizability and not Bellman completeness. In this regime, classic counterexamples against TD imply that linear FQE may diverge in the worst case, even if data covers all feature directions [Tsitsiklis and Van Roy, 1996]. Since our Q-MMR [n] coincides with FQE in the linear setting, this means that the size of w bh may blow-up exponentially [n] in the horizon. Thus, naturally we want to understand when the size of w bh stays well bounded, and how stronger conditions such as Bellman completeness help guarantee that. A priori bound. Theorem 1 is data dependent. Can we turn it into an a priori, data-independent [n] [n] bound? Recall that the bound depends on the size of w bh , ∥w bh ∥[n] . To remove the data dependence, [n]
[n]
we can define the population counterpart of w bh and use its size to replace ∥w bh ∥[n] . Note that such bounds in general will incur dimension dependence, albeit in higher-order terms [Hsu et al., 2011]. [n]
The nature of coverage. ∥w bh ∥[n] plays the role of coverage in Theorem 1. Conventional wisdom π tells us that coverage is about how the distribution dD h covers dh , and the density coverage can sometimes be refined based on structure of F; for example, in linear case, data only needs to cover the mean feature direction E(sh ,ah )∼dπh [ϕ(sh , ah )]. However, recent fine-grained linear analyses tell a very different story: Amortila et al. [2026] (see also Duan et al. [2020], Perdomo et al. [2023]) show that the target of coverage is generally not dπh or its feature expectation, but the vector defined by the following linear dynamical system: starting with ψ1 = ED [ϕ(s1 , π)], and define, ∀h ≥ 1, ⊤ −1 ⊤ cr π ⊤ ψh+1 = Bhπ ψh , where Bhπ = (Σcr h ) Σh , Σh = ED [ϕh ϕh ], Σh = ED [ϕh (ϕh+1 ) ].
(6)
Here ϕh is the shorthand of ϕ(sh , ah ) and ϕπh+1 = ϕ(sh+1 , π). In fact, linear FQE can be thought of as fitting such a system and using it to predict J(π) [Duan et al., 2020]. While this system mimics the feature evolution in the real MDP, they are generally different (i.e., ψh ̸= Edπh [ϕ]). In the fine-grained analyses of linear OPE, it is shown that what really needs to be covered is the ψh from such a “wrong” system {Bhπ }h , not the feature expectation Edπh [ϕ] from the real MDP,4 and they only coincide under Bellman completeness. However, the analyses of FQE under general function approximation rely on completeness, and this subtle distinction between ψh and Edπh [ϕ] is therefore not observed. Moreover, the key concepts such as Bhπ are defined linear-algebraically, and it is unclear how their [n] GFA counterpart should be defined. Does ∥w bh ∥[n] in our analyses (or its population counterpart) provide such a generalization, and how is it related to the concepts identified in the linear analyses? [n]
We address the above questions by providing a concentration analysis for how w bh tracks its population counterpart, defined below; throughout this section, we assume the empirical algorithm [n] performs exact minimization of Lbh with least 2nd-moment w bh . 4 There is information-theoretic lower bound against this possibility [Foster et al., 2022].
8
[n]
Definition 3. In Algorithm 1, replace w bh ∈ Rn with wh⋆ ∈ RS×A (w0⋆ ≡ 1), and Eq.(1) with ⋆ ⋆ (sh−1 , ah−1 )f (sh , π)] . (7) Lh (wh ; wh−1 ) := supf ∈Fh ED [wh (sh , ah )f (sh , ah )] − ED [wh−1
Assume exact minimization of L is performed. Among the minimizers, we choose the one that [n] minimizes ∥wh ∥2,dD := (EdD [wh2 ])1/2 . The output {wh⋆ }h is the population counterpart of {w bh }h . h h [n]
To characterize the least-2nd-moment solution w bh and its population counterpart wh⋆ , we will use a Hilbert-space viewpoint based on the linear span of Fh . PM Definition 4. For each h ∈ [H], define span(Fh ) = { m=1 am fm : M < ∞, am ∈ R, fm ∈ Fh }. Let F h := span(Fh ) be the closure of span(Fh ) under ∥f ∥2,dD = (E(s,a)∼dD [f (s, a)2 ])1/2 , the h h dD = E(s,a)∼dD [f (s, a)g(s, a)]. h -weighted (semi-)norm. We also define ⟨f, g⟩dD h h Proposition 4 (2nd-Moment Minimizers are in F). The population least-2nd-moment weight wh⋆ ∈ [n] [n] F h . In addition, for the least-2nd-moment w bh , there exists w̄h ∈ F h such that w̄h |n = w bh , where (i) (i) |n denotes the sample evaluation with (w̄h |n )i = w̄h (sh , ah ), ∀i ∈ [n]. 4.1
[n]
Tracking Error of w bh and Data-independent Guarantee [n]
We now introduce a few assumptions and provide finite-sample guarantees for how w bh tracks wh⋆ . When specialized to the linear setting, these assumptions recover familiar conditions in the literature. Assumption 3 (Bounded generalized leverage). ∀h ∈ [H], there exists κh ∈ (0, ∞) such that √ |f (s, a)| ≤ κh ∥f ∥2,dD , ∀f ∈ F h , ∀(s, a) ∈ Sh × A. h This assumption generalizes the standard condition of bounded statistical leverage in the linear √ −1/2 setting ∥Σh ϕ(sh , ah )∥2 ≤ κh , ∀(sh , ah ), which is often assumed in random-design analyses [Hsu et al., 2011]. It also implies that ∥ · ∥2,dD is identifiable on F h , in the sense that ∥f ∥2,dD =0 h h implies f = 0 on Sh × A. This immediately leads to the following implication: Proposition 5 (Population 0 matching loss). For each h ∈ [H], under Assumption 3, the population ⋆ matching problem in Definition 3 achieves 0 loss, i.e., Lh (wh⋆ ; wh−1 ) = 0. As mentioned earlier, FQE without completeness may produce run-away predictions even when data provides good coverage, so we need some additional quantities (weaker than completeness assumption) to characterize and prevent the exponential blow-up of weights. In the linear setting, prior works have identified the operator norm of Bhπ (Eq.(6)) as the key quantity that controls the blow-up [Perdomo et al., 2023, Amortila et al., 2026]. Below we define the counterpart of these concepts for Q-MMR under GFA: Definition 5. For each h ∈ [H − 1], define the projected transition operator Khπ : F h+1 → F h , such that ∀f ∈ F h+1 , Khπ f ∈ F h is the unique minimizer of the least square problem Khπ f := arg ming∈F h ED (g(sh , ah ) − f (sh+1 , π))2 . π π Define ρt:h = supf ∈F h :∥f ∥∞ ≤1 ∥Ktπ Kt+1 · · · Kh−1 f ∥∞ as the multi-step ∞-operator norm of π π π Kt Kt+1 · · · Kh−1 : F h → F t , where ∥g∥∞ = sup(s,a)∈Sj ×A |g(s, a)| for g ∈ F j . Let ρh:h = 1.
Proposition 6 (Connection between Khπ and Bhπ ). In the linear setting, for f ∈ F h+1 , let θh+1 be its linear coefficient (i.e., f (s, a) = ϕ(s, a)⊤ θh+1 ), and let θh be that of Khπ f ∈ F h . We have −1/2 π π θh = (Bhπ )⊤ θh+1 , and ρt:h ≤ supst ,at ∥Σh Bh−1 · · · Bt+1 Btπ ϕ(st , at )∥2 . π Just as the operator norm of Bhπ controls the size of ψh = Bh−1 · · · B1π ψ1 in the linear case [Amortila π π et al., 2026], we have ρ1:h , the operator norm of K1 · · · Kh−1 , controls EdD [wh⋆ f ]. h
Proposition 7. Under Assumption 3, |EdD [wh⋆ (sh , ah )f (sh , ah )]| ≤ ρ1:h ∥f ∥∞ , ∀h ∈ [H], f ∈ F h . h Note that wh⋆ may have a large size for two reasons: (1) data dD h does not provide sufficient coverage (for linear, this corresponds to near-singular Σh ), and (2) the algorithm’s iterations are unstable and 9
produce run-away predictions even when data has good coverage (for linear, this corresponds to large ∥ψh ∥). Proposition 7 separates out these two factors and only studies the instability in (2) by examining wh⋆ · dD h . Such instability can be eliminated with Bellman completeness, and Proposition 7 provides more quantitative understanding and is strictly weaker than completeness (see Section 4.2). We are now ready to give the tracking error guarantee, where the bound depends on ρ(·):h (iteration ⋆ stability), the generalized leverage, the size of w(·) (which is determined by both iteration stability and the data), and the log-covering number of F (·) which is the statistical dimension term. Theorem 8 (Empirical weight tracks its population counterpart). Define the empirical-population 1/2 Pn [n] (i) (i) (i) bh − wh⋆ |n [n] := n1 i=1 (w bh − wh⋆ (sh , ah ))2 tracking error by w . Under Assumptions 3, fix any h ∈ [H] and δ ∈ (0, 1), and let Nt be the 1/8-covering number of {u ∈ F t : ∥u∥2,dD ≤ 1}. t Ph 2 2 2 If n ≳ (maxt≤h κt ) ( t=1 ρt:h ) log(H Nt Nh /δ) for all t ≤ h, then with probability ≥ 1 − δ, r h X κ2h log(H 2 Nt Nh /δ) [n] ⋆ w bh − wh |n ≲ ρt:h (∥wt⋆ ∥2,dD + 1). t n [n] t=1 This result also allows us to obtain a data-independent, “random-design” version of Theorem 1, where [n] we replace ∥w bh ∥[n] with ∥wh⋆ ∥2,dD and incur a higher-order term that corresponds to Theorem 8; h √ such bounds are only dimension-free in the leading O(1/ n) term, but incur dimension dependence in the higher-order terms, which is consistent with the prior specialized analyses [Hsu et al., 2011, Duan et al., 2020]. For the Lbh term which is also data-dependent, we can show that it becomes 0: Proposition 9 (Empirical 0 matching loss). Under Assumption 3, if n ≳ κh log(HNh /δ) for all [n] [n] h ∈ [H], then Q-MMR achieves 0 matching loss w.h.p, i.e., Lbh (w bh ; w bh−1 ) = 0. Corollary 10 (Random-design bound). Assume realizability and exact minimization, and suppose PH Assumptions 3 hold. If n ≳ (maxh κh )2 ( h=1 ρh:H )2 log(H 2 Nh NH /δ) for all h ∈ [H], then with probability ≥ 1 − δ, s q H H h log Hδ X ⋆ 2 Vmax X X 2 log H Nt Nh ∥w ⋆ ∥ b D |J(π)−J(π)| ≲ Vmax ∥wh ∥2,dD ρ κ + + 1 . t:h t 2,dt h δ h n n t=1 h=0
4.2
h=1
Implications of Bellman Completeness
Below we discuss the implications of Bellman completeness (Assumption 2), which is consistent with and generalizes similar conclusions in the linear setting [Perdomo et al., 2023, Amortila et al., π 2026]. Under completeness, wh⋆ · dD h learns dh up to the discrimination power of Fh , and the stability term ρ1:h is always well controlled so no exponential blow-up will occur. Proposition 11. Under Assumptions 2 and 3, assuming 0 ∈ Fh for all h ∈ [H], we have, (1) E(sh ,ah )∼dD [wh⋆ (sh , ah )f (sh , ah )] = E(sh ,ah )∼dπh [f (sh , ah )], ∀f ∈ F h . h π π (2) (Ktπ Kt+1 · · · Kh−1 f )(s, a) = Eπ [f (sh , π) | st = s, at = a], ∀(s, a) ∈ St × A, f ∈ F h . (3) ρt:h ≤ 1, ∀1 ≤ t < h ≤ H. We also compare ∥wh⋆ ∥2,dD as a coverage parameter to the literature under various additional assumph tions; see Table 1 for a summary. (Edπ [f ])2
Proposition 12. Under the assumptions of Proposition 11, we have ∥wh⋆ ∥22,dD = supf ∈F h E Dh [f ]2 . h
d
h
In the linear setting, without completeness, we have ∥wh⋆ ∥2,dD = ∥ψh ∥Σ−1 , the finite-horizon version h h of “feature-dynamics coverage” identified by Amortila et al. [2026]. If completeness is further assumed, ∥wh⋆ ∥2,dD = ∥E(sh ,ah )∼dπh [ϕ(sh , ah )]∥Σ−1 . h h
When completeness holds, ∥wh⋆ ∥2,dD almost coincides with the coverage parameter of FQE, up to a h minor difference in the function space we take sup over. In the linear case, we also recover previously identified coverage parameters, providing unification of our understanding. 10
5
Other Related Works
Throughout the paper we have discussed the connection and comparison to FQE. Here we discuss several other related methods. Marginalized Importance Sampling (MIS) Our method is closely related to MIS methods [Liu et al., 2018, Nachum et al., 2019]; for example, MWL [Uehara et al., 2020] also solves a similar minimax problem (min over weights and max over value functions), whose loss is similar to our Eq. (1). Both losses are related to the Bellman flow equation, and roughly speaking, MWL can P be viewed as using h Lbh as a loss to optimize the weights at all levels simultaneously. As a [n] (i) consequence, however, this introduces dependencies of w bh on {sh+1 }i and violates the condition in our Theorem 1, so MWL cannot learn a weight per data point but must introduce a weight class W ⊂ (S × A → R) and learn a parametric form of weight w bh ∈ W instead. This means an extra realizability condition (of W) and a complexity term (e.g., log |W|) compared to our analyses. Besides the difference in loss and parameterization, there is also a significant difference between the existing analyses of MIS methods and ours, and some insights from our analyses may be transferred to MIS. For example, we may use our proof techniques to provide data-dependent bounds for MWL that avoid the log |F| term (see Appendix D). In addition, while most MIS methods assume W models the MIS ratio (Eq.(2)), Uehara et al. [2020] point out that the method may learn degenerate weights when F is structured, but a systematic understanding of what the learned weights really represent is still lacking, which our analyses shed light on given the close connection between the methods. Methods that only rely on realizability The main guarantee of our method (Theorem 1) only relies on realizability Qπ ∈ F and not the stronger and more widely used Bellman-completeness assumption. Getting such results is also the central focus of the model selection problem in offline RL, where we want to select Qπ (or sometimes Q⋆ ) from a set of candidates on holdout data. Given challenges such as the double-sampling problem, these model-selection algorithms often require a tournament procedure and is only computationally efficient for a small number of candidates [Xie and Jiang, 2021, Liu et al., 2025]. In comparison, our Q-MMR is computationally efficient for rich function classes under standard optimization oracles. Top-down algorithms Our algorithm design bears structural similarities to some of the existing methods. For example, Sun et al. [2019] designs an online imitation-learning algorithm with a dataset that does not contain actions, which performs top-down, level-by-level moment matching against a value discriminator class similar to Q-MMR. However, they have online access to the MDP and the task is to imitate the expert policy, and their analysis requires Bellman completeness for the discriminator class. Huang et al. [2023] learns the parametric form of the MIS ratio (Eq.(2)) in finite-horizon MDPs in a top-down manner, but they do not use a value-function discriminator but relies on a squared-loss objective, and their analyses also require a version of completeness for the MIS ratio.
6
Limitations and Future Work
We conclude the paper by discussing limitations and future work. One major limitation is that we need i.i.d. trajectory data; an adaptively collected dataset will break the conditional independence (i) (i) (i) (i) between w bh and sh+1 |sh , ah . A straightforward extension of our results to the infinite-horizon discounted case will result in similar difficulties. One potential solution is to leverage the fact that [n] w bh always lies in F h (Proposition 4), so we can union bound over F. However, doing so will incur the dimension dependence in the leading term, and we hope to resolve this issue in the future with more advanced concentration tools. [n]
As another limitation, our weights w bh are computed to minimize matching loss and variance at [n] level h in a rather greedy and local manner, as the effects of w bh on downstream levels h′ > h are not considered in optimization. One might attempt to address this issue by optimizing the sum of losses across all levels simultaneously, which essentially recovers MIS methods and runs into a 11
double-sampling issue with non-parametric weights (Appendix D.1). It remains an open question [n] whether we can optimize the weights w bh across levels while circumventing the issue.
Acknowledgement NJ thanks Philip Amortila, Audrey Huang, Akshay Krishnamurthy, and Steven Wu for helpful discussions in the early phases of the project.
References Yasin Abbasi-Yadkori, David Pal, and Csaba Szepesvari. Online-to-confidence-set conversions and application to sparse stochastic bandits. In AISTATS, volume 22, pages 1–9, 2012. Philip Amortila, Audrey Huang, Akshay Krishnamurthy, and Nan Jiang. A unifying view of coverage in linear off-policy evaluation. arXiv preprint arXiv:2601.19030, 2026. András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellmanresidual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008. Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, pages 1042–1051, 2019. Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On oracle-efficient pac rl with rich observations. Advances in Neural Information Processing Systems, 2018:1422–1432, 2018. Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pages 2701–2709. PMLR, 2020. Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6:503–556, 2005. Dylan J Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Conference on Learning Theory, pages 3489–3489. PMLR, 2022. Yoav Freund and Robert E Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29(1-2):79–103, 1999. Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 (3-4):157–325, 2016. Daniel Hsu, Sham M Kakade, and Tong Zhang. An analysis of random design linear regression. arXiv preprint arXiv:1106.2363, 6, 2011. Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforcement learning in low-rank MDPs with density features. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 13710–13752. PMLR, 23–29 Jul 2023. Nan Jiang and Jiawei Huang. Minimax value interval for off-policy evaluation and policy optimization. Advances in Neural Information Processing Systems, 33, 2020. Nan Jiang and Tengyang Xie. Offline reinforcement learning in large state spaces: Algorithms and guarantees. arXiv preprint arXiv:2510.04088, 2025. Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137–2143. PMLR, 2020. Nathan Kallus. Balanced policy evaluation and learning. Advances in neural information processing systems, 31, 2018. 12
Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In International Conference on Machine Learning, pages 3703–3712, 2019. 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. Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinitehorizon off-policy estimation. In Advances in Neural Information Processing Systems, pages 5356–5366, 2018. Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforcement learning with convex constraints. Advances in neural information processing systems, 32, 2019. Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. Advances in Neural Information Processing Systems, 32, 2019. Juan C Perdomo, Akshay Krishnamurthy, Peter Bartlett, and Sham Kakade. A complete characterization of linear estimators for offline policy evaluation. Journal of Machine Learning Research, 24 (284):1–50, 2023. Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.05659, 2019. Wen Sun, Anirudh Vemula, Byron Boots, and Drew Bagnell. Provably efficient imitation learning from observation alone. In International conference on machine learning, pages 6036–6045. PMLR, 2019. Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. John N Tsitsiklis and Benjamin Van Roy. Feature-based methods for large scale dynamic programming. Machine Learning, 22(1):59–94, 1996. Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax Weight and Q-Function Learning for Off-Policy Evaluation. In Proceedings of the 37th International Conference on Machine Learning, pages 1023–1032, 2020. Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11404–11413. PMLR, 2021. Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. Advances in neural information processing systems, 32, 2019. Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3948–3958. PMLR, 2020. Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems, 34:4065–4078, 2021. Yaoliang Yu and Csaba Szepesvári. Analysis of kernel mean matching under covariate shift. arXiv preprint arXiv:1206.4650, 2012.
13
A
Linear Regression under Covariate Shift
The form of our main theoretical guarantee in Section 3 can feel somewhat unconventional in the OPE literature due to its data dependence. As we will see, however, in the special case of H = 1 with a linear function class, our algorithm and analyses recover those of linear regression under covariate shift [Yu and Szepesvári, 2012], where the data-dependent bound corresponds to a standard fixed-design analysis of linear regression [Hsu et al., 2011]. Therefore, it is instructive to quickly review such an analysis, which will help clarify the nature of our results. The covariate shift problem We consider (x, y) pairs that satisfy y = x⊤ θ⋆ + ϵ, where x ∈ Rd , θ⋆ is the unknown linear coefficients, and ϵ is some 0-mean i.i.d. noise. We are given training data (i) (i) points {(xtrain , ytrain )}ni=1 sampled i.i.d. from distribution Ptrain , and some test data points without y (i) m labels {xtest }i=1 sampled i.i.d. from distribution Ptest , which is potentially different from Ptrain . Now the goal is to estimate EPtest [ytest ]. Note that this problem naturally arises in our OPE setup when H = 1 and F is linear in ϕ (Defini(i) (i) (i) (i) (i) (i) (i) tion 1): our ϕ(s1 , a1 ) is xtrain , r1 is ytrain , ϕ(s1 , π) is xtest (so that m = n), and the estimand is exactly J(π); see also Amortila et al. [2026] for the connection between these two problems. Fixed-design analysis of linear regression Consider a natural algorithm that (1) performs linear ⊤b b and (2) outputs the estimate as 1 Pm (x(i) regression from the training data to estimate θ, i=1 test ) θ = m P (i) m 1 b x⊤ test θ, where xtest := m i=1 xtest . A standard analysis shows that the error can be bounded as: Proposition 13 (Informal). Under appropriate with probability at least q boundedness assumptions, P (i) (i) n 1 1 ⊤ b b := 1 − δ, |EP [ytest ] − x θ| ≤ O(∥xtest ∥ b −1 log /n), where Σ x (x )⊤ is the test
test
Σ
δ
n
i=1
train
train
sample covariance matrix from the training data. To understand the guarantee, the first observation is that we only care about how accurate θb is when probed in the mean direction of xtest , EPtest [xtest ] ≈ xtest , instead of individual xtest ∼ Ptest . The accuracy of the estimation then depends on how well this direction is covered in the training distribution, measured by ∥xtest ∥Σ b −1 . For readers familiar with the online RL literature, one may q directly recall a bound of O(∥xtest ∥Σ (d + log 1δ )/n) that is widely used in the linear bandit/MDP b −1 √ analyses [Abbasi-Yadkori et al., 2012, Jin et al., 2020]. However, we can avoid paying the d factor here because the online RL bound needs to hold for all probing directions simultaneously, whereas in the covariate shift (OPE) problem we only care about a single probing direction xtest . Concretely, Proposition 13 can be proved by rewriting the estimate as ! n n X 1 1 X (i) (i) (i) (i) ⊤ b −1 b x⊤ xtrain ytrain =: w b ytrain . test θ = xtest Σ n i=1 n i=1 (i)
b −1 x That is, we are effectively computing weights w b(i) = x⊤ test Σ train and using them to compute the weighted average of training labels. These weights satisfy n
1 X (i) (i) w b xtrain = xtest . n i=1 (i)
(8) (i)
Intuitively, if {w b(i) } reweight {xtrain } to match xtest in mean, then {w b(i) }-weighted ytrain will also match the mean of ytest . Based on this intuition, we can rewrite the error as5 n
⊤ ⋆ b x⊤ test θ − xtest θ =
1 X (i) (i) (i) w b (ytrain − (xtrain )⊤ θ⋆ ). n i=1
5 A component of the final error (x⊤ θ ⊤ ⋆ b test − EPtest [ytest ]) is omitted here, namely, (xtest − EPtest [xtest ]) θ . While this term reflects the finite sample error of using xtest to approximate its expectation, we only need to perform concentration along the direction of θ⋆ , so the error term is dimension-free and incurs a negligible overhead. In our analyses (e.g., Proposition 2), this corresponds to the ϵstat 0 term.
14
(i)
(i)
Note that ytrain − (xtrain )⊤ θ⋆ are 0-mean i.i.d. random variables, and {w b(i) } are chosen with no (i) dependence on the randomness of {ytrain }, so by a standard concentration argument we can bound the error using theq2nd moment of w b(i) (see the proof of Theorem 1 in Appendix B.1), which is exactly P n 1 b(i) )2 . ∥xtest ∥Σ b −1 = i=1 (w n A few remarks are in order: b which is data • Proposition 13 is a fixed-design result, as the bound depends on the matrix Σ (i) dependent, and the analysis applies to settings where {xtrain } is arbitrarily chosen (as in e.g., online learning) and not sampled from some distribution. This contrasts with the random-design analysis b that has the population Σ = EPtrain [xtrain x⊤ train ] in the bound instead of Σ. Random-design bounds typically require additional assumptions and/or have extra (dimension-dependent) higher-order terms [Hsu et al., 2011], as is the case for our analyses in Section 4. b is invertible. This is implicitly an assumption on our matching loss • The above analysis assumes Σ b invertible Σ b implies that Eq.(8) has solution(s), and Eq.(8) can be written as: ∀θ, L: n m 1 X (i) (i) ⊤ 1 X (i) ⊤ w b (xtrain ) θ − (x ) θ = 0. n i=1 m i=1 test
Translating this back to the OPE notation system, we have 0 = sup θ
n n 1 X (i) 1X (i) (i) (i) w b1 ϕ(s1 , a1 )⊤ θ − ϕ(s1 , π)⊤ θ n i=1 n i=1
n n 1 X (i) 1X (i) (i) (i) [n] [n] w b1 f (s1 , a1 ) − f (s1 , π) = Lb1 (w b1 ; w b0 ). n n f ∈Fϕ i=1 i=1
= sup
(9)
b and the violation of Eq.(8) will b is not invertible, we can still use pseudo-inverse to compute θ, If Σ appear in the error bound as a bias term. Such a term exactly corresponds to the matching error term in Theorem 1.
B
Proofs and Additional Results for Section 3
B.1
Proof of Theorem 1
For each h ∈ {0, 1, . . . , H}, define the prefix sigma-field n on (i) (i) (i) (i) (i) (i) (i) (i) Gh := σ (s0 , a0 , r0 , . . . , sh−1 , ah−1 , rh−1 , sh , ah ) . i=1
(i)
(i)
(i)
(i)
(i)
For each h ∈ {0, . . . , H} and sample i ∈ [n], define εh := Qπh (sh , ah ) − rh − Qπh+1 (sh+1 , π) (i)
as the Bellman error. By the Bellman equation, we know that E[εh | Gh ] = 0. Also, since rewards (i) lie in [0, Rmax ] and total return lies in [0, Vmax ], we have |εh | ≤ Vmax almost surely. (i)
(i)
Now, condition on Gh . Because the n trajectories are i.i.d., once the prefixes up to (sh , ah ) are (i) [n] fixed, the random variables {εh }ni=1 remain conditionally independent across i. Since w bh is (i) (i) (i) Gh -measurable, the weighted variables Xh := w bh εh are also conditionally independent given Gh , satisfy (i)
(i)
E[Xh | Gh ] = 0,
(i)
|Xh | ≤ |w bh |Vmax .
Applying Hoeffding’s inequality conditionally on Gh , for every t > 0, " # ! n 2 1 X (i) n2 t2 nt . P X ≥ t Gh ≤ 2 exp − Pn = 2 exp − (i) [n] 2 ∥w n i=1 h 2 (Vmax w b )2 2Vmax b ∥2 i=1
15
h
h
[n]
q [n] 2 log(2(H+1)/δ) Setting t = ϵstat := V ∥ w b ∥ and taking a union bound over h = 0, 1, . . . , H, max [n] h h n we obtain an event E with Pr[E] ≥ 1 − δ such that on E, simultaneously for all h = 0, . . . , H, n 1 X (i) π (i) (i) (i) (i) w bh Qh (sh , ah ) − rh − Qπh+1 (sh+1 , π) ≤ ϵstat h . n i=1
(10)
After obtaining the statistical concentration rate, we can follow the idea in Section 3 to finish the proof, which reduces the OPE error to matching losses plus the statistical errors. Fix the event E. (i) Since r0 ≡ 0 and w b0 ≡ 1, b − J(π)| = |J(π)
H n X 1X h=0
≤
n i=1
H n X 1X h=0
n i=1
(i) (i)
w bh rh − J(π) (i)
w bh
H X (i) (i) (i) Qπh (sh , ah ) − Qπh+1 (sh+1 , π) − J(π) + ϵstat h , h=0
(i) (i) (i) (i) where we used Eq. (10) and the triangle inequality. Now abbreviate Qh := Qπh (sh , ah ), Qh,π := (i) Qπh (sh , π). Then the first term becomes n H X 1X h=0
n i=1
(i)
w bh
(i) (i) Qh − Qh+1,π − J(π) .
For each h = 1, . . . , H, realizability gives Qπh ∈ Fh . Hence, by plugging f = Qπh into the definition of Lbh (Eq. (1)), n n 1 X (i) (i) 1 X (i) (i) [n] [n] w bh Qh − w b Q ≤ Lbh (w bh ; w bh−1 ). n i=1 n i=1 h−1 h,π Thus, for h = 1, 2, . . . , H, we have H n X 1X h=0
≤
n i=1
(i)
w bh
(i) (i) Qh − Qh+1,π − J(π)
H n H X X 1 X (i) (i) (i) (i) [n] [n] w bh Qh − w bh+1 Qh+1 − J(π) + Lbh (w bh ; w bh−1 ) n i=1
h=0
h=1
H n X 1 X (i) (i) [n] [n] (i) (i) Lbh (w bh ; w bh−1 ), w b0 Q0 − w bH+1 QH+1 − J(π) + = n i=1 h=1
(i) (i) where the second equality is due to telescoping. Since w b0 = 1, QH+1 = 0, and Qπ0 (s0 , a0 ) = J(π)
due to the dummy initial pair (s0 , a0 ) is fixed, thus the absolute value term above is exactly zero. Therefore, the OPE error reduces to matching losses plus the statistical errors, i.e., b − J(π)| ≤ |J(π)
H X
[n] [n] Lbh (w bh ; w bh−1 ) +
h=1
H X
ϵstat h
h=0
on the event E. Since P[E] ≥ 1 − δ, the theorem follows. B.2
Proof of Proposition 2
We now give the proof for Proposition 2, which heavily relies on the analysis of linear regression with covariate shift (see Appendix A). Proof of Proposition 2. Consider H = 1 and linear F1 . Write n
(i) (i) xi := ϕ(s1 , a1 ),
1X (i) xtest := ϕ(s1 , π), n i=1 16
n 1X b Σ := xi x⊤ i . n i=1
(i) b is invertible, define w b −1 xi for i ∈ [n]. Take any We first consider the case where Σ b1 := x⊤ test Σ ⊤ f ∈ F1 such that f (s, a) = ϕ(s, a) θ, then we have n n 1 X (i) 1 X ⊤ b −1 ⊤ (i) (i) w b1 f (s1 , a1 ) = x Σ xi xi θ = x⊤ test θ, n i=1 n i=1 test Pn b since n1 i=1 xi x⊤ i cancels with Σ. On the other hand, by the definition of xtest , we have n n 1X 1X (i) (i) f (s1 , π) = ϕ(s1 , π)⊤ θ = x⊤ test θ. n i=1 n i=1 (i)
Therefore, for any f ∈ F1 , since w b0 = 1 for all i ∈ [n], n n X 1 1 X (i) (i) (i) (i) (i) w b f (s1 , a1 ) = w b f (s1 , π), n i=1 1 n i=1 0 [n]
[n]
which indicates that 0 empirical matching loss can be achieved, i.e., Lb1 (w b1 ; w b0 ) = 0. This proves the first claim. For the empirical 2nd-moment of the weight, we have ! n n X 2 1X 1 [n] 2 ⊤ −1 ⊤ −1 b b −1 xtest = x⊤ Σ b −1 xtest , b xi = x Σ xi xi Σ w b1 [n] = xtest Σ test test n i=1 n i=1 [n] b = 1 Pn xi x⊤ . Hence, ∥w where we again use Σ b1 ∥[n] = ∥xtest ∥Σ b −1 , which proves the second i i=1 n claim. And the OPE error bound can be obtained immediately by Theorem 1: r 2 log(4/δ) stat stat b J(π) − J(π) ≤ ϵ0 + ϵ1 = Vmax 1 + ∥xtest ∥Σ b −1 . n (i) b define w b† b† For non-invertible Σ, b1 := x⊤ test Σ xi for i ∈ [n], where Σ is the Moore-Penrose pseudob inverse of Σ. We show that this weight choice minimizes the matching loss. Pn For any w ∈ Rn , define its induced empirical feature moment µ(w) := n1 i=1 w(i) xi . Since F1 is linear and ∥θ∥2 ≤ Θ, we have n 1 X (i) ⊤ [n] sup |⟨µ(w)−xtest , θ⟩| = Θ∥µ(w)−xtest ∥2 , w xi θ − x⊤ Lb1 (w; w b0 ) = sup test θ = θ:∥θ∥2 ≤Θ θ:∥θ∥2 ≤Θ n i=1
where the last step is due to Cauchy-Schwarz inequality. Thus minimizing the empirical matching loss is equivalent to choosing µ(w) as close as possible to xtest in Euclidean norm. Let X := span(x1 , . . . , xn ). For every w, clearly µ(w) Pn ∈ X by its definition. Conversely, for any v ∈ X , there exist coefficients αi such that v = i=1 αi xi , and choosing w(i) = nαi gives µ(w) = v. Hence the set of all achievable empirical moments is exactly X . b is Range(Σ) b = X . This is because Σ b = 1 Pn xi x⊤ , so that Moreover, the range space of Σ i i=1 n b ⊆ X . On the other hand, since Σ b is symmetric, Range(Σ) b = Null(Σ) b ⊥ , where Null(Σ) b Range(Σ) P n 1 ⊤ ⊤ 2 b But v Σv b = b is the nullspace of Σ. i=1 (v xi ) , so v ∈ Null(Σ) is equivalent to v⊥xi for all n ⊥ ⊥ b b = X. i ∈ [n], thus v ∈ X . Therefore, Null(Σ) = X , and hence Range(Σ) It follows that the minimum empirical matching loss is obtained by projecting xtest onto the range b whose projection operator is indeed Σ bΣ b †: space of Σ, bΣ b † xtest . µ(w) = ΠX xtest = Σ The proposed weights indeed achieve this moment, since ! n n n 1 X ⊤ b† 1X 1 X (i) b † xtest = Σ bΣ b † xtest . w b xi = x Σ xi xi = xi x⊤ Σ i n i=1 1 n i=1 test n i=1 [n]
Therefore w b1 minimizes the empirical matching loss. The minimum loss is [n] [n] bΣ b † )xtest . Lb1 (w b1 ; w b0 ) = Θ (I − Σ 2
b In particular, empirical 0 matching loss is achievable if and only if xtest ∈ Range(Σ). 17
B.3
Proof of Proposition 3
Now we consider Proposition 3 which connects our Q-MMR algorithm to the canonical FQE algorithm in the linear and the tabular settings. Recall that FQE estimates the target-policy value functions recursively from the last step to the first step by solving a sequence of supervised regression b π , the next estimate Q b π is obtained by regressing the problems: given the current estimate Q h+1 h π b Bellman target rh + Q (s , π) onto the current state-action features. h+1 h+1 Linear setting In the linear case, this admits a simple matrix-vector implementation. In particular, b H+1 ≡ 0, or equivalently θbH+1 = 0, and for h = H, H − 1, . . . , 1, computes linear FQE sets Q π b (s, a) = ϕ(s, a)⊤ θbh , where Q h n 2 1 X (i) (i) ⊤ (i) (i) θbh = arg min ϕ(sh , ah ) θ − rh − ϕ(sh+1 , π)⊤ θbh+1 . n i=1 θ∈Rd Equivalently, by the normal equation, n X (i) (i) (i) (i) b h θbh = 1 ϕ(sh , ah ) rh + ϕ(sh+1 , π)⊤ θbh+1 . Σ n i=1 Since s0 , a0 is fixed and r0 ≡ 0, the FQE estimate of J(π) is n n 1X 1 X b π (i) (i) Q1 (s1 , π) = ϕ1 (s1 , π)⊤ θb1 . JbFQE (π) := n i=1 n i=1
(11)
The following proof shows that the Q-MMR algorithm produces exactly the same J(π) estimate as linear FQE in Eq. (11). Proof of Proposition 3(1). We first characterize the Q-MMR weights in the linear case. At level h, empirical 0 matching loss means that, for all linear functions f (s, a) = ϕ(s, a)⊤ θ, n n 1 X (i) 1 X (i) (i) (i) ⊤ (i) w b ϕ(sh , ah ) θ = w b ϕ(sh , π)⊤ θ. n i=1 h n i=1 h−1 Pn (i) (i) [n] bh−1 ϕ(sh , π) as the target moment. Then Q-MMR needs to choose w Define ψbh := n1 i=1 w bh such that n 1 X (i) (i) (i) w b ϕ(sh , ah ) = ψbh . n i=1 h By the same linear-regression / moment-matching calculation as in Proposition 2, the least-2nd(i) (i) (i) b −1 ψbh for moment solution that achieves empirical 0 matching loss is given by w bh = ϕ(sh , ah )⊤ Σ h b h is assumed to be invertible. It remains to show that the final Q-MMR prediction all i ∈ [n], since Σ equals to the FQE prediction JbFQE (π). Define, for h ∈ [H], n n 1 X (i) b π (i) 1 X (i) (i) Vh := w bh−1 Qh (sh , π) = w b ϕ(sh , π)⊤ θbh . n i=1 n i=1 h−1 Since w b0 ≡ 1, we have V1 = JbFQE (π) in Eq. (11). We now prove the recursion n 1 X (i) (i) Vh = w b r + Vh+1 , VH+1 ≡ 0. n i=1 h h
(12)
(i) (i) (i) Let yh := rh + ϕ(sh+1 , π)⊤ θbh+1 . By the linear FQE normal equation, the target moment can b h θbh = 1 Pn ϕ(s(i) , a(i) )y (i) . Therefore, using the closed form of the Q-MMR be rewritten as Σ i=1 h h h n (i) (i) (i) b −1 ψbh , we obtain weights w bh = ϕ(sh , ah )⊤ Σ h ! n n n 1 X (i) (i) 1X 1X (i) (i) ⊤ b −1 b (i) (i) (i) (i) ⊤ b −1 b w b y = ϕ(sh , ah ) Σh ψh yh = ψh Σh ϕ(sh , ah )yh n i=1 h h n i=1 n i=1 n
b −1 · Σ b h θbh = ψbh⊤ θbh = = ψbh⊤ Σ h
18
1 X (i) (i) w b ϕ(sh , π)⊤ θbh = Vh , n i=1 h−1
(i)
where the first equality is by the definition of w bh , the second equality is by rearranging, the third b the fifth equation is by equality is by the linear FQE normal equation, the fourth equation cancels Σ, b the definition of ψh , and the last equation is by the definition of Vh . Therefore, Vh =
n n 1 X (i) (i) 1 X (i) (i) (i) w bh rh + ϕ(sh+1 , π)⊤ θbh+1 = w b r + Vh+1 . n i=1 n i=1 h h
This proves the recursion in Eq. (12). Unrolling this recursion from h = 1 to H, and using VH+1 = 0, yields H n X 1 X (i) (i) JbFQE (π) = V1 = w b r , n i=1 h h h=1
b while the RHS is exactly the Q-MMR estimate J(π) in Algorithm 1. This proves the claim that in b h }h , our Q-MMR algorithm is equivalent to linear FQE. linear setting with invertible {Σ Tabular setting Now we consider the tabular function class Ftab = [0, Vmax ]S×A in Definition 2. As in Proposition 3(2), we assume every state-action pair at each level appears in the dataset, i.e., for any h ∈ [H] and (s, a) ∈ Sh × A, n
dbh (s, a) > 0,
where dbh (s, a) :=
1X (i) (i) 1{sh = s, ah = a}. n i=1
For tabular FQE. Define the empirical reward and empirical transition respectively by Pn Pn (i) (i) (i) (i) (i) (i) ′ i=1 1{sh = s, ah = a, sh+1 = s } ′ i=1 1{sh = s, ah = a}rh b rbh (s, a) := Pn , P (s |s, a) := . h P (i) (i) (i) (i) n i=1 1{sh = s, ah = a} i=1 1{sh = s, ah = a} b Together, {b rh , Pbh }H h=1 define the empirical MDP. Tabular FQE computes QH+1 ≡ 0, and for h = H, H − 1, . . . , 1, solves the squared-loss regression problem bh ∈ Q
n 2 1 X (i) (i) (i) b h+1 (s(i) , π) . Q(sh , ah ) − rh − Q h+1 Q:Sh ×A→[0,Vmax ] n i=1
arg min
Since the function class is , the regression separates over each state-action pair (s, a). Therefore, for every (s, a), X b h (s, a) = rbh (s, a) + b h+1 (s′ , π). Q Pbh (s′ | s, a)Q s′
Thus, tabular FQE is exactly Bellman evaluation of π in the empirical MDP. Hence its prediction is the model-based certainty-equivalence value JbFQE (π) = Jbψb(π),
(13)
where ψb denotes the empirical MDP (S, A, {b rh }h , {Pbh }h ). The following proof shows that the Q-MMR algorithm produces exactly same J(π) estimate as tabular FQE (or model-based certaintyequivalence) in Eq. (13). Proof of Proposition 3(2). We first characterize the Q-MMR weights in the tabular case. Let dbπh be (i) b Since s0 , a0 is fixed and w the occupancy distribution of π in the empirical MDP ψ. b0 ≡ 1, the empirical occupancy is recursively defined by X dbπh = π(a | s) dbπh−1 (s̃, ã)Pbh−1 (s | s̃, ã). s̃,ã [n]
We prove by induction on h that the least-2nd-moment weight w bh that achieves empirical 0 matching loss satisfy (i) (i) dbπ (s , a ) (i) w bh = h h(i) h(i) . dbD (s , a ) h
19
h
h
Fix h. Since the tabular class contains state-action indicators, empirical 0 matching loss at level h is equivalent to matching every state-action pair: n n 1 X (i) 1 X (i) (i) (i) (i) w bh 1{sh = s, ah = a} = w b 1{sh = s}π(a | s), n i=1 n i=1 h−1
for all (s, a) ∈ Sh × A. By the induction hypothesis, the RHS becomes n
1 X (i) (i) w b 1{sh = s}π(a | s) n i=1 h−1 X dbπh−1 (s̃, ã)
n
1X (i) (i) (i) 1{sh−1 = s̃, ah−1 = ã, sh = s} D b n i=1 s̃,ã dh−1 (s̃, ã) X π b b = π(a | s) dh−1 (s̃, ã)Ph−1 (s | s̃, ã)
= π(a | s)
·
s̃,ã
= dbπh (s, a). P (i) On the other hand, the LHS can be written as n1 i:s(i) =s,a(i) =a w bh . Thus, empirical 0 matching h h P (i) loss requires i:s(i) =s,a(i) =a w bh = ndbπh (s, a) for all (s, a) ∈ Sh × A. h
h
Among all weights satisfying this cell-wise constraint, the least-2nd-moment solution is constant P (i) within each cell. This is because for a fixed cell (s, a), minimizing i:s(i) =s,a(i) =a (w bh )2 subject to h h the fixed sum constraint is achieved when all weights in that cell are equal. Hence, for every i with (i) (i) (sh , ah ) = (s, a), dbπh (s, a) ndbπh (s, a) (i) w bh = Pn = . (j) (j) dbD h (s, a) j=1 1{sh = s, ah = a} [n]
This proves the desired formula for the Q-MMR weights w bh . It remains to compare the final estimates. Recall the Q-MMR estimate in Algorithm 1 is given by b J(π) =
n H X 1X h=1
n i=1
(i) (i)
w bh rh .
Using the weight formula above, we get b J(π) =
H X X 1 h=1 s,a
n
X (i)
(i)
i:sh =s,ah =a
dbπh (s, a) (i) rh dbD (s, a) h
P (i) r (i) (i) i:sh =s,ah =a h π = dbh (s, a) Pn (i) (i) h=1 s,a i=1 1{sh = s, ah = a} H X X
=
H X X
dbπh (s, a)b rh (s, a),
h=1 s,a
b i.e., where the last expression is exactly the expected return of π in the empirical MDP ψ, Jbψb(π) =
H X X
dbπh (s, a)b rh (s, a).
h=1 s,a
b Therefore, by Eq. (13), J(π) = JbFQE (π). This tells that in the tabular setting with full empirical support, Q-MMR and tabular FQE both coincide with the model-based certainty-equivalence solution, and the Q-MMR weights are exactly the empirical occupancy ratios. 20
B.4
Comparison to Prior Analyses in Linear and Tabular Settings
In this section we compare our guarantees with those of Duan et al. [2020] in the linear setting. By b h , Q-MMR Proposition 3(1), in the linear setting with invertible empirical covariance matrices Σ with exact minimization and the least-2nd-moment rule produces exactly the same estimator as linear FQE without ridge regularization. We now compare their data-independent bound to ours, and will comment on the data-dependent bounds below. For our result, we specialize Corollary 10 to the linear setting: r H log(H/δ) X ⋆ b |J(π) − J(π)| ≲ Vmax ∥wh ∥2,dD + higher-order terms. (14) h n h=0
Duan et al. [2020, Theorem 2] also give a finite sample error bound; after translation between settings and notation,6 it is: r H X log(1/δ) b − J(π)| ≲ |J(π) Vh · ∥Edπh [ϕ]∥Σ−1 + higher-order terms (15) h n h=0
where Vh := (H − h + 1)Rmax = O(Vmax ) is a stage-dependent range. • Same coverage term. As we recognize ∥wh⋆ ∥2,dD as the coverage term in Eq. (14), the correh sponding term in Eq. (15) is ∥Edπh [ϕ]∥Σ−1 . These two terms are exactly identical under Bellman h completeness in the linear setting (Proposition 16). • Same n−1/2 rate. Both bounds have the same leading n−1/2 statistical rate, horizon dependence on H, and the range parameter up to minor differences √ (e.g., Vmax vs. Vh and the log H factor). Both bounds are dimension-free in the leading O(1/ n) term. • Burn-in condition and higher-order term. The burn-in condition (i.e., requirement of sample size n ≳ (·)) and the higher-order term of Duan et al. [2020] depend on a more stringent notion of −1/2 −1/2 π coverage, such as cond(Σh Σπh Σh ), where Σh is the feature covariance under dD h and Σh is π that under dh . This “squared” version coverage requires data to cover all feature directions under π, instead of just the mean direction Edπh [ϕ] [Jiang and Xie, 2025]. In contrast, the higher-order term in our bound in Eq. (14) relies on the tracking analysis (Theorem 1), where only the size of wh⋆ shows up and no squared coverage is needed. • Data-dependent bounds. Both our work and Duan et al. [2020] also feature data-dependent bounds that are computable from data, i.e., our Theorem 1 and their Theorem 4. The bounds look structurally similar to Eqs.(14) and (15), except that the coverage terms become their empirical counterparts. Moreover, our Theorem 1 is dimension-free while their bound incurs dependence √ on d; this might be due to the fact that their Theorem 4 (data-dependent bound) assumes i.i.d. transitions (their data-independent bound in Theorem 1 assumes i.i.d. trajectories), whereas all our results are under i.i.d. trajectories and the telescoping step in the proof of our Theorem 1 relies on trajectory data to have perfect cancellation. In addition, their Theorem 4 also has additional higher-order terms, whereas our Theorem 1 is very clean and only has the leading term. • Assumptions and setup. Technically speaking, Duan et al. [2020] considers the linear-MDP setup which is even stronger than Bellman completeness, but their proofs and results can be adapted to much weaker settings (e.g., only realizability), especially given the later insights of Perdomo et al. [2023], Amortila et al. [2026]. In particular, Amortila et al. [2026] analyze LSTDQ, an algorithm closely related to linear FQE, in the infinite-horizon discounted setting under only realizability, and their data-independent bound matches that of Duan et al. [2020] in the stable regime (∥B π ∥op ≤ 1) under the standard conversion between finite-horizon and discounted results. On top of that, key 6We apply the bound of Duan et al. [2020] to our setup of disjoint state spaces, which admits (nominally) time-homogeneous dynamics and q featurePmap that match their setup. In their bound, the coverage term is H 1 2 supf ∈F |E(s,a)∼dπ [fh (s, a)]|/ ED [ H h=1 fh (s, a) ]. When {Sh }h are disjoint and feature/linear coefficients are h essentially independent across levels, the supf is always achieved by setting fh′ ≡ 0, ∀h′ ̸= h. This way, their coverage p √ √ becomes H · supfh ∈Fh |E(s,a)∼dπ [fh (s, a)]|]/ ED [fh (s, a)2 ] = H∥Edπ [ϕ]∥Σ−1 (Proposition 12). The extra h h h √ √ √ H cancels out when we replace their 1/ N with 1/ n, as their N is the number of transitions and hence N = nH.
21
quantities such as ψh also appear in Duan et al. [2020]’s analysis, so there is good reason to believe that Duan et al. [2020]’s bound applies to the setting where only realizability of Qπ is assumed, where the Edπh [ϕ] term in Eq.(15) will be replaced by ψh . We also note that similar dimension-free bounds have also been obtained in the tabular setting [Yin and Wang, 2020, Theorem 3.1], and the leading term matches the form of Eqs.(14) and (15). One improvement in Yin and Wang [2020] is that they replace the range (Vmax or Vh ) with (the square-root of) the variance of reward and value function V π w.r.t. state transitions; indeed, they show that this is the form of the asymptotically minimax-optimal bound. This improvement is very easy to implement in our analyses, as we can simply replace the Hoeffding’s inequality in Eq.(10) with a Bernstein’s inequality, where the variance of V π w.r.t. state transitions will naturally replace Vmax in the leading term. B.5
Computational Efficiency
For linear F, the computational efficiency of Q-MMR is clear given that it reduces to linear FQE, where the computation involved is just a sequence of linear regressions. For general F, computational guarantees are often given in the form of oracle efficiency [Dann et al., 2018], and below we show that the computation is efficient given access to some optimization primitives over F. [n]
Recall the only computation-heavy step in Q-MMR is the matching step, which is (wh in Eq.(1) is [n] replaced with w for notational simplicity) arg minw∈Rn Lbh (w; w bh−1 ) := supf ∈Fh |ℓ(w, f )|, where ℓ(w, f ) =
n n 1 X (i) 1 X (i) (i) (i) (i) w f (sh , ah ) − w b f (sh , π) n i=1 n i=1 h−1
To remove the absolute value, we would like to assume Fh is a symmetric function class in the following discussion. That is, Fh is closed under negation: −f ∈ Fh , ∀f ∈ Fh . [n]
Now, this version only minimizes the matching loss but does not control the second moment of w bh . [n] 2 To enable second-moment control, we can either add a regularization term λ∥w∥[n] to ℓ(wh , f ) for an appropriate λ > 0, or add constraint on w that we can only choose from WC = {w : ∥w∥[n] ≤ C} for some budget C. Below we discuss the latter which admits cleaner results, i.e., we want to solve arg min sup ℓ(w, f ).
(16)
w∈WC f ∈Fh
To solve the above minimax problems, we apply the standard no-regret + best-response framework [Freund and Schapire, 1999] (see [Miryoosefi et al., 2019] for an example), where a w player and an f player alternately play a sequence of w1 , w2 , . . . , wT ∈ WC and f1 , f2 , . . . , fT ∈ Fh , respectively, PT [n] and we finally output w bh = T1 t=1 wt . No regret on w and best response on f In this case, after each wt ∈ WC is chosen, ft is chosen as the best response to maximize ℓ(wt , ·), which requires a standard linear-optimization oracle over Fh [Dann et al., 2018]: 7 ( n ) n 1 X (i) 1 X (i) (i) (i) (i) ft ∈ BR(wt ) := arg max w f (sh , ah ) − w b f (sh , π) . n i=1 t n i=1 h−1 f ∈Fh From the point of view of the w player, it receives a loss ℓw t (·) = ℓ(·, ft ), which is a convex function and we have access to the gradient information, so standard online learning algorithm such as projected OGD [Hazan, 2016] can be applied to obtain a regret guarantee: 1 (1) (1) (n) (n) wt+1 = ΠWC [wt − η∇w ℓ(wt , ft )], ∇w ℓ(wt , ft ) = ft (sh , ah ), . . . , ft (sh , ah ) . n 7 Here are some examples: if F is an RKHS ball, the oracle has a kernel witness-function form; if F is a neural network h h class, it corresponds to training a discriminator/value network to maximize the following weighted empirical objective; if Fh is finite, it is just choosing the function in the finite class with largest signed score.
22
[n]
Proposition 14 (Optimization error from no-regret on w and best response on f ). Fix h and w bh−1 . Pn (i) (i) 2 1/2 1 Let Gh := supf ∈Fh n i=1 f (sh , ah ) . Assume that each ft is an exact best response to wt , and run projected OGD over WC with a standard step-size. Then, the averaged output PT [n] w bh = T1 t=1 wt satisfies CG [n] [n] [n] b b Lh (w bh ; w bh−1 ) ≤ min Lh (w; w bh−1 ) + O √ . w∈WC T (i)
(i)
In particular, if |f (s,√a)| ≤ Vmax for all f ∈ Fh and all data points (sh , ah ), then the optimization error is O(CVmax / T ). √ Proof sketch. For the OGD losses ℓw ∥∇w ℓw t (w) := ℓ(w, ft ), we have t ∥2 ≤ Gh / n and WC = √ √ {w ∈ Rn : ∥w∥2 ≤ C n}. Hence the OGD regret is O(CGh T ). Since ft is the best response, [n] b t; w ℓ(wt , ft ) = supf ∈Fh ℓ(wt , f ) = L(w bh−1 ). Therefore, T
1Xb [n] [n] Lh (wt ; w bh−1 ) ≤ min Lbh (w; w bh−1 ) + O w∈WC T t=1
CG √ T
.
[n] The claim follows by Jensen’s inequality, since w 7→ Lbh (w; w bh−1 ) is convex.
No regret on f and best response on w We can also swap the roles of f and w. For each fixed ft , we solve wt ∈ arg minw∈WC ℓ(w, ft ). Since WC is a Euclidean ball and ℓ(·, ft ) is linear, this best response has a closed form: ft |n (1) (1) (n) (n) wt = −C , ft |n = f (sh , ah ), . . . , f (sh , ah ) ∈ Rn , ∥ft |n ∥[n] for ft |n ̸= 0; and if ft |n = 0, then any wt ∈ WC is a best response. Then, from the point of view of the f player, it receives a loss ℓft (·) = ℓ(wt , ·), which is linear in f . Similar to before, if f ∈ Fh is parametrized in a differentiable manner, we would need an online learning oracle over Fh for the reward sequences f 7→ ℓft f (). In particular, if the oracle guarantees reward regret RegfT , i.e., P P maxf ∈Fh t ℓ(wt , f ) − t ℓ(wt , ft ) ≤ RegfT , then the same averaging argument gives f
RegT [n] [n] [n] . Lbh (w bh ; w bh−1 ) ≤ min Lbh (w; w bh−1 ) + w∈WC T For instance, in the linear case fθ (s, a) = ϕ(s, a)⊤ θ with ∥θ∥2 ≤ Θ, this oracle can be implemented P (i) (i) (i) by OGD/ascent on θ for the linear rewards θ 7→ θ⊤ m(wt ), where m(wt ) = n1 i wt ϕ(sh , ah ) − √ P (i) (i) 1 bh−1 ϕ(sh , π). If ∥m(wt )∥2 ≤ M for all t, then RegfT = O(ΘM T ), which immediately iw n √ implies an O(ΘM/ T ) optimization error. For general function classes, the same statement might be formulated non-parametrically by assuming such an online learning oracle over Fh . In the special case where the data is on-policy, i.e., the trajectories are sampled from π itself, it is Pn PH (i) well known that the Monte-Carlo estimator, n1 i=1 h=1 rh , is a simple and effective method that achieves dimension-free error guarantees, since the analysis simply applies concentration arguments to the i.i.d. random returns. This also shows the looseness of standard OPE analyses that depends on log |F| [Antos et al., 2008, Chen and Jiang, 2019], as those guarantees do not automatically eliminate log |F| when data is on policy. In contrast, Q-MMR immediately recovers MC in this setting if we (i) simply choose w bh ≡ 1. (Note that this choice is not necessarily minimizing the 2nd moment of [n] [n] [n] w bh .) The matching loss Lbh (w bh ; w bh−1 ) is 0 under such weights,8 and Theorem 1 is dimension free. More generally, when the behavior policy πD is stochastic, a variant of our algorithm can also recover step-wise importance sampling, the generalization of MC to the off-policy setting. In particular, if we 8 This holds when π is deterministic; when π is stochastic, it still holds if we consider the IS variant of our algorithm, as
described below.
23
change the target embedding n1
(i) (i) bh−1 f (sh , π) in Eq.(1) to9 iw
P
(i) (i) 1 X (i) (i) (i) π(ah |sh ) w bh−1 f (sh , ah ) (i) (i) , πD (ah |sh ) n i
which produces the same target embedding after marginalizing over the action randomness, then (i) (i) Qh π(ah′ |sh′ ) (i) [n] b b[n] ; w setting w b = b ) = 0. ′ (i) (i) ensures Lh (w h
h =1 π (a |s ) D h′ h′
h
h−1
This example also demonstrates the role of F and the importance of 2nd-moment minimization: if we [n] only care about minimizing the matching loss Lb but not the size of w bh , we can always set Lb to 0 by [n] setting w bh to be the cumulative importance weights, which generally incurs exponential-in-horizon [n] variance. This is avoided when structured F admits many choices of w bh that equally minimize the matching loss, and we can choose the smallest one to significantly dampen the weight size.
C
Proofs and Additional Results of Section 4
C.1
Auxiliary functionals and representers
In this section, we introduce several auxiliary concepts that will be used in the subsequent proofs and in our understanding of the learned weights. The main idea is to view the population and empirical moment-matching problems through the lens of Hilbert-space linear functionals. This viewpoint will be useful for two reasons. First, it explains why the population exact-matching problem is feasible under the bounded generalized leverage assumption (Assumption 3). Second, it allows us to compare [n] the empirical weights {w bh }h with their population counterparts {wh⋆ }h by representing both of them inside the same Hilbert space. Recall from Definition 4 that the Hilbert space F h is the closure of span(Fh ) under the dD h -weighted π D [f g]. For any f ∈ F h , let P f denote the L2 norm, equipped with the inner product ⟨f, g⟩dD = E d h h one-step transition of f under the target policy, i.e., (P π f )(s, a) = Es′ ∼P (·|s,a) [f (s′ , π)]. Given the population weight, define the propagated signed measure ⋆ νh⋆ := P π (wh−1 · dD h−1 ).
Equivalently, νh⋆ is the signed measure satisfying, for every f ∈ F h , ⋆ E(sh ,ah )∼νh⋆ [f (sh , ah )] = E(sh−1 ,ah−1 )∼dD [wh−1 (sh−1 , ah−1 ) · (P π f )(sh−1 , ah−1 )]. h−1 ⋆ ⋆ We call νh⋆ a signed measure because wh−1 is not required to be nonnegative. Therefore wh−1 dD h−1 , and hence its pushforward under P π , need not be a probability distribution.
Definition 6 (Population and empirical target functionals). For each h ∈ [H], define the population target functional Λ⋆h : F h → R by ⋆ Λ⋆h (f ) := Eνh⋆ [f ] = EdD [wh−1 · (P π f )]. h−1 [n] b : F h → R by Given the empirical weights w bh−1 , define the empirical target functional Λ n X (i) (i) b h (f ) := 1 Λ w b f (sh , π). n i=1 h−1
b h is its empirical Thus, Λ⋆h is the population moment that the level-h weight should match, while Λ analogue induced by the already-learned weights at level h − 1. The next proposition shows that these linear functionals admit Riesz representers in F h . It also shows that, whenever empirical 0 matching loss is feasible (which is shown in Proposition 9 as a high-probability corollary under population 0 matching loss), the least-2nd-moment empirical weight vector can be viewed as the sample evaluation of some function in F h . 9 This resembles how targets are set up in TD, such as expected SARSA vs. its off-policy version [Sutton and Barto, 2018].
24
Proposition 15 (Existence of representers). Under Assumption 3, for each h ∈ [H], we have: (i) The population target functional Λ⋆h is a continuous linear functional on F h . Hence, the wh⋆ defined in Definition 3 satisfies wh⋆ ∈ F h , and ⟨wh⋆ , f ⟩dD = Λ⋆h (f ) for all f ∈ F h . h ⋆ Moreover, wh is the unique least-2nd-moment solution among all L2 (dD h ) functions w ⋆ satisfying ⟨w, f ⟩dD = Λ (f ) for all f ∈ F . h h h b h is also a continuous linear functional on F h . Hence there exists (ii) The empirical functional Λ b h (f ) for all f ∈ F h . =Λ a unique auxiliary representer w eh ∈ F h such that ⟨w eh , f ⟩dD h [n]
(iii) Suppose empirical 0 matching loss is feasible at level h, and let w bh be the least-2nd[n] moment weight vector. Then, there exists a lift representer w̄h ∈ F h such that w̄h |n = w bh . P (i) (i) (i) (i) n b h (f ) for all f ∈ F h . Consequently, n1 i=1 w̄(sh , ah )f (sh , ah ) = Λ Proof. For (i), linearity of Λ⋆h follows directly from its definition (Definition 6), so we need to √ show its continuity. By Assumption 3, every f ∈ F h satisfies |f (s, a)| ≤ κh ∥f ∥2,dD . Therefore, h √ |f (s, π)| ≤ κh ∥f ∥2,dD as well. It follows that h ⋆ |Λ⋆h (f )| ≤ EdD [|wh−1 | · |P π f |] ≤ h−1
√
⋆ κh · EdD [|wh−1 |]∥f ∥D 2,dh . h−1
⋆ ⋆ Using Cauchy-Schwarz, EdD [|wh−1 |] ≤ ∥wh−1 ∥2,dD . Hence Λ⋆h is bounded, and therefore h−1 h−1
continuous, on F h . Therefore, by the Riesz representation theorem, there exists a unique w⋆ ∈ F h such that ⟨w⋆ , f ⟩dD = Λ⋆h (f ) for all f ∈ F h . This already proves that the population 0 matching h loss is feasible (Proposition 5): the feasible set is nonempty because w⋆ itself satisfies all the required moment equations. Since wh⋆ defined in Definition 3 minimizes the matching loss, we have wh⋆ = w⋆ . It remains to justify the minimum-norm claim. Let w ∈ L2 (dD h ) be any other function satisfying the ⋆ same moment equations, namely ⟨w, f ⟩dD = Λ (f ) for all f ∈ F h . Then w − wh⋆ is orthogonal to h h = 0. Therefore, every element of F h . Since wh⋆ ∈ F h , we have ⟨w − wh⋆ , wh⋆ ⟩dD h ∥w∥22,dD = ∥wh⋆ ∥22,dD + ∥w − wh⋆ ∥22,dD ≥ ∥wh⋆ ∥22,dD . h
h
h
h
Thus wh⋆ is the unique minimum-norm solution, up to dD h -almost-sure equivalence. b h is linear in f . Moreover, under For (ii), the argument is similar. The empirical functional Λ Assumption 3, we have X n n X √ 1 (i) (i) (i) b h (f )| ≤ 1 |w bh−1 | · |f (sh , π)| ≤ κh |w bh−1 | ∥f ∥2,dD |Λ . h n i=1 n i=1 b h is continuous on F h . Applying the Riesz representation theorem again yields a unique Therefore Λ b h (f ) for all f ∈ F h . w eh ∈ F h such that ⟨w eh , f ⟩dD =Λ h For (iii), let F h |n := {f |n : f ∈ F h } ⊆ Rn be the sample-evaluation subspace of F h . The empirical matching constraints only depend on the projection of the weight vector onto F h |n , because every constraint is tested against some vector f |n ∈ F h |n . Decompose the least-2nd-moment solution as [n] w bh = v + v⊥ , where v ∈ F h |n and v⊥ ∈ (F h |n )⊥ . Since v⊥ is orthogonal to every f |n ∈ F h |n , [n] replacing w bh by v preserves all empirical matching constraints. If v⊥ ̸= 0, this replacement strictly [n] [n] decreases ∥w bh ∥[n] , contradicting the least-2nd-moment choice of w bh . Therefore, v⊥ = 0 and [n]
w bh ∈ F h |n . [n]
By the definition of F h |n , there exists w̄h ∈ F h such that w̄h |n = w bh . Since by our assumption, Pn [n] (i) (i) (i) (i) b h (f ) for w bh achieves empirical 0 matching loss, we obtain n1 i=1 w̄(sh , ah )f (sh , ah ) = Λ all f ∈ F h . 25
The above three representers play different roles. The population weight wh⋆ is the object we ultimately want to track. The auxiliary representer w eh converts the empirical target functional into the population geometry of F h . The lift representer w̄h converts the empirical sample weights back into a function so that empirical pairings can be compared with population pairings. In the linear setting (Definition 1) with both population and empirical 0 matching loss, these objects reduce to the familiar forms that correspond to the feature dynamical system in Eq. (6); see the following proposition. Proposition 16 (Linear forms of the three representers). Suppose F h is linear in a feature map ϕ : Sh × A → Rd . Write ϕh := ϕ(sh , ah ), ϕπh := ϕ(sh , π). Assume that the population covariance b h := matrix Σh := EdD [ϕh (ϕh )⊤ ] is invertible. For the empirical lift, additionally assume that Σ h P (i) (i) (i) (i) (i) n 1 ⊤ i=1 ϕh (ϕh ) is invertible, where ϕh := ϕ(sh , ah ). n Consider the feature dynamical system {ψh }h defined in Eq. (6), i.e., ψ1 := ED [ϕπ1 ], and for h ≥ 1, ⊤ −1 π ⊤ Bhπ := (Σcr Σcr h ) Σh , h := ED [ϕh (ϕh+1 ) ]. P (i) (i) n bh−1 ϕ(sh , π). Then the three representers in Also define the empirical target vector ψbh := n1 i=1 w Proposition 15 take the following forms: b −1 ψbh . w⋆ (s, a) = ϕ(s, a)⊤ Σ−1 ψh , w eh (s, a) = ϕ(s, a)⊤ Σ−1 ψbh , w̄h (s, a) = ϕ(s, a)⊤ Σ
ψh+1 := Bhπ ψh ,
h
h
h
h
Proof. We first identify the population representer wh⋆ via induction on h. More precisely, we prove jointly that, for every h, the population target functional satisfies Λ⋆h (f ) = ψh⊤ θ,
∀f ∈ F h such that f (s, a) = ϕ(s, a)⊤ θ,
and that its Riesz representer is wh⋆ (s, a) = ϕ(s, a)⊤ Σ−1 h ψh . For h = 1, since w0⋆ ≡ 1, for every f (s, a) = ϕ(s, a)⊤ θ, Λ⋆1 (f ) = ED [f (s1 , π)] = ED [ϕπ1 ]⊤ θ = ψ1⊤ θ. ⊤ ⋆ The Riesz representer w1⋆ therefore satisfies, for all θ, ED [w1⋆ (s1 , a1 ) · ϕ⊤ 1 θ] = ψ1 θ. Since w1 ∈ F 1 ⋆ ⊤ ⊤ ⊤ by Proposition 15(i), we can write w1 (s, a) = ϕ(s, a) α1 . This becomes α1 Σ1 θ = ψ1 θ for all θ. ⋆ ⊤ −1 Hence α1 = Σ−1 1 ψ1 for invertible Σ1 , and therefore w1 (s, a) = ϕ(s, a) Σ1 ψ1 .
Now assume the two claims hold at level h. By the definition of the population target functional, Λ⋆h+1 (f ) = ED [wh⋆ (sh , ah )f (sh+1 , π)] −1 π ⊤ = ED [ϕ⊤ h Σh ψh · (ϕh+1 ) θ] cr = ψh⊤ Σ−1 h Σh θ ⊤ = ψh+1 θ, where the first equality is due to the inductive hypothesis on wh⋆ , the second equality leverages the cr ⊤ −1 definition of Σcr h and the third equality is due to ψh+1 = (Σh ) Σh ψh . ⊤ ⋆ Similarly, since Λ⋆h+1 (f ) = ψh+1 θ for all f (s, a) = ϕ(s, a)⊤ θ, the representer wh+1 satisfies ⋆ ⊤ ED [wh+1 (sh+1 , ah+1 ) · (ϕ⊤ h+1 θ)] = ψh+1 θ,
∀θ.
⋆ ⋆ Since wh+1 ∈ F h+1 , we can write wh+1 (s, a) = ϕ(s, a)⊤ αh+1 . The above matching equation ⊤ ⊤ becomes αh+1 Σh+1 θ = ψh+1 θ for all θ and thus αh+1 = Σ−1 h+1 ψh+1 for invertible Σh+1 , indicating ⋆ ⊤ −1 wh+1 (s, a) = ϕ(s, a) Σh+1 ψh+1 . This closes the induction.
b h (f ) = ψb⊤ θ by the The proof for w eh does not require induction. For any f (s, a) = ϕ(s, a)⊤ θ, Λ h definition of ψbh . Since w eh ∈ F h by Proposition 15(ii), its linear form w eh (s, a) = ϕ(s, a)⊤ α eh ⊤ −1 b b satisfies Σh α eh = ψh , and hence w eh (s, a) = ϕ(s, a) Σh ψh . Finally, for the empirical lift w̄h , empirical 0 matching loss gives n 1X (i) (i) (i) w̄h (sh , ah )ϕh = ψbh . n i=1 b h ᾱh = ψbh . Since w̄h ∈ F h by Proposition 15(iii), its linear form w̄h (s, a) = ϕ(s, a)⊤ ᾱh satisfies Σ ⊤ b −1 b b Since Σh is invertible, it directly leads to w̄h (s, a) = ϕ(s, a) Σh ψh . 26
C.2
Proofs of Propositions 4, 5, 6, 7, 11 and 12 [n]
Proof of Proposition 4. For the second argument that for the least-2nd-moment w bh , there exists [n] some w̄h ∈ F h such that w̄h |n = w bh , the proof is exactly same as stated in Proposition 15(iii). [n] Note that in there we do not use the empirical 0 matching loss condition for w bh ∈ F h |n argument. For the first argument that the least-2nd-moment population weight wh⋆ ∈ F h , we can adopt a similar strategy to prove (which does not require Assumption 3). For any w ∈ L2 (dD h ) and any f ∈ Fh ⊆ F h , we have EdD [w · f ] = EdD [(ΠF h w) · f ], h h where ΠF h is the L2 (dD h )-projection onto F h . This is because w − ΠF h w is orthogonal to F h . ⋆ Therefore, the population matching loss Lh (w; wh−1 ) depends on w only through its projection ⋆ ⋆ ΠF h w, which means Lh (w; wh−1 ) = Lh (ΠF h w; wh−1 ). Moreover, ∥w∥22,dD = ∥ΠF h w∥22,dD + ∥w − ΠF h w∥22,dD . h
h
h
⋆ Thus, if wh⋆ is chosen among the exact minimizers of Lh (·; wh−1 ) to have least-2nd-moment, then its orthogonal component outside F h must be 0. Otherwise replacing wh⋆ by ΠF h wh⋆ would preserve the loss and strictly reduce its 2nd-moment. Hence, wh⋆ ∈ F h .
Proof of Proposition 5. Proposition 15(i) already implies this claim. Proof of Proposition 6. For a function f ∈ F h+1 , by Definition 5, its one-step backup is given by Khπ f = arg ming∈F h ED [(g(sh , ah ) − f (sh+1 , π))2 ] ∈ F h . That is, Khπ f = ΠF h P π f , where the projection step preserves linearity in ϕ of the function. Therefore, if f (s, a) = ϕ(s, a)⊤ θh+1 , we can write (Khπ f )(s, a) = ϕ(s, a)⊤ θh for some θh solved by the above least-square problem. Specifically, the normal equation for this least-square problem is Σh θh = Σcr h θh+1 , −1 cr where Σh and Σcr h are defined in Eq. (6). Thus, for invertible Σh , we have θh = Σh Σh θh+1 = π ⊤ π cr ⊤ −1 (Bh ) θh+1 , since Bh = (Σh ) Σh . This proves the first claim.
For the multi-step bound, let f ∈ F h have coefficient θh . Repeatedly applying the previous identity π π gives that Ktπ Kt+1 · · · Kh−1 f has coefficient π π π π (Btπ )⊤ (Bt+1 )⊤ · · · (Bh−1 )⊤ θh = (Bh−1 · · · Bt+1 Btπ )⊤ θh .
Therefore, for any (st , at ) ∈ St × A, π π π π (Ktπ Kt+1 · · · Kh−1 f )(st , at ) = ϕ(st , at )⊤ (Bh−1 · · · Bt+1 Btπ )⊤ θh D E −1/2 π 1/2 π = Σh Bh−1 · · · Bt+1 Btπ ϕ(st , at ), Σh θh .
By Cauchy-Schwarz, −1/2
π π (Ktπ Kt+1 · · · Kh−1 f )(st , at ) ≤ Σh
π π Bh−1 · · · Bt+1 Btπ ϕ(st , at )
1/2
2
· ∥Σh θh ∥2 .
1/2
Since ∥Σh θh ∥2 = ∥f ∥2,dD ≤ ∥f ∥∞ , we take the supremum over (st , at ) and then over all f with h ∥f ∥∞ ≤ 1 yields the bound for ρt:h . Proof of Proposition 7. By Proposition 5, we can achieve population 0 matching loss under Assumption 3, i.e., for any f ∈ F h ⋆ ⋆ π EdD [wh⋆ f ] = EdD [wh−1 · (P π f )] = EdD [wh−1 · (Kh−1 f )], h h−1 h−1 ⋆ where the last step is because wh−1 ∈ F h−1 (Proposition 15(i)), so that we can replace P π f by its D π L2 (dh−1 )-projection Kh−1 f without changing the overall inner product. Apply the same argument recursively gives π EdD [wh⋆ f ] = EdD [w1⋆ · (K1π K2π · · · Kh−1 f )]. 1 h
27
π π At level 1, L1 = 0 implies EdD [w1⋆ · (K1π K2π · · · Kh−1 f )] = EdD [w0⋆ · (P π K1π K2π · · · Kh−1 f )]. 1 0 ⋆ π π π Since w0 ≡ 1 and (s0 , a0 ) is fixed, the RHS becomes ED [(K1 K2 · · · Kh−1 f )(s1 , π)] and hence we have π EdD [wh⋆ f ] ≤ ∥K1π K2π · · · Kh−1 f ∥∞ ≤ ρ1:h ∥f ∥∞ , h
by the definition of ρ1:h . This proves the claim. Proof of Proposition 11. We first want to claim that Bellman completeness over the original function class Fh (T π f ∈ Fh−1 , ∀f ∈ Fh ) implies the backup closure property of the Hilbert space F h (P π f ∈ F h−1 , ∀f ∈ F h ). This is because we assume 0 ∈ Fh and hence r = T π 0 ∈ Fh−1 ; by Bellman completeness, T π f ∈ Fh−1 for all f ∈ Fh . Thus, P π f = T π f − r ∈ span(Fh−1 ) for all f ∈ Fh . By linearity, P π span(Fh ) ⊆ span(Fh−1 ), and by closure this extends to P π F h ⊆ F h−1 . For 1), we prove by induction that, for every f ∈ F h , EdD [wh⋆ f ] = Edπh [f ]. For h = 1, population h ⋆ ⋆ π 0 matching loss (Proposition 5) gives EdD [w1 f ] = EdD [w0 · (P π f )]. Since w0⋆ ≡ 1 and dD 0 = d0 1 0 is the fixed initial state-action pair, by Bellman flow equation, EdD [w0⋆ · (P π f )] = Edπ1 f . Thus the 0 claim holds for h = 1. Assume that the induction holds at level h − 1, and take any f ∈ F h . By our claim before, we know that P π f ∈ F h−1 . Therefore, ⋆ EdD [wh⋆ f ] = EdD [wh−1 · (P π f )] = Edπh−1 [P π f ] = Edπh f , h h−1
where the first equality is due to population 0 matching loss, the second equality is by inductive hypothesis, and the last equality uses Bellman flow equation that dπh = P π dπh−1 for h ∈ [H]. This proves 1). π For 2), let f ∈ F h . Since P π f ∈ F h−1 , by the definition of the projected backup operator Kh−1 , π π π D we have that Kh−1 f = ΠF h−1 P f = P f as an element of L2 (dh−1 ).
Under Assumption 3, equality in L2 (dD h−1 ) implies pointwise equality for all (s, a) ∈ Sh−1 × A, √ because |g(s, a)| ≤ κh−1 ∥g∥2,dD for all g ∈ F h−1 . Hence, h−1 π (Kh−1 f )(s, a) = (P π f )(s, a) = Eπ [f (sh , π) | sh−1 = s, ah−1 = a].
Iterating this identity from t to h − 1 yields π π (Ktπ Kt+1 · · · Kh−1 f )(s, a) = Eπ [f (sh , π) | st = s, at = a].
3) For any f ∈ F h with ∥f ∥∞ ≤ 1, by the multi-step identity in 2), π π |(Ktπ Kt+1 · · · Kh−1 f )(s, a)| = |Eπ [f (sh , π) | st = s, at = a]| ≤ ∥f ∥∞ ≤ 1. π π · · · Kh−1 f ∥∞ ≤ 1. Therefore, by Definition 5, ρt:h = supf ∈F h :∥f ∥∞ ≤1 ∥Ktπ Kt+1
Proof of Proposition 12. We first prove the general case with Bellman completeness. By Proposition 11(1), for any f ∈ F h , we have Edπh [f ] = EdD [wh⋆ f ] = ⟨wh⋆ , f ⟩dD for all f ∈ F h . By h h Cauchy-Schwarz inequality, we have |Edπh [f ]| = |⟨wh⋆ , f ⟩dD | ≤ ∥wh⋆ ∥2,dD ∥f ∥2,dD . h h h Moreover, the above inequality becomes equality if we take f = wh⋆ ∈ F h . Therefore we get ∥wh⋆ ∥2,dD = h
|Edπh [f ]| |Edπ [f ]| = sup q h . f ∈F h ,f ̸=0 ∥f ∥2,dD f ∈F h ,f ̸=0 E D [f 2 ] h sup
dh
Now we consider linear case. By Proposition 16, we have wh⋆ (s, a) = ϕ(s, a)⊤ Σ−1 h ψh . Therefore, −1 2 2 ∥wh⋆ ∥22,dD = EdD (ϕ⊤ = ψh⊤ Σ−1 h Σh ψh ) h ψh = ∥ψh ∥Σ−1 , h h
h
i.e., ∥wh⋆ ∥2,dD = ∥ψh ∥Σ−1 , which does NOT require Bellman completeness. h h 28
Under linear Bellman completeness, by Proposition 11(1), we have EdD [wh⋆ fθ ] = Edπh [fθ ] h holds for all θ, where fθ (s, a) = ϕ(s, a)⊤ θ. Recall wh⋆ (s, a) = ϕ(s, a)⊤ Σ−1 h ψh . The LHS of the −1 ⊤ ⊤ above equation becomes ψh θ, since EdD [ϕh ϕh ] cancels with Σh ; while the RHS of the above h equation becomes Edπh [ϕh ]⊤ θ. Therefore, ψh = Edπh [ϕh ] and hence ∥wh⋆ ∥2,dD = ∥Edπh [ϕh ]∥Σ−1 . h h This proves the claim. C.3
Concentration arguments
We state two standard concentration arguments, both obtained by Bernstein’s inequality together with a covering argument. For each f , let Nh be the 1/8-covering number of the unit ball of F h under ∥ · ∥2,dD , i.e., Bh := {f ∈ F h : ∥f ∥2,dD ≤ 1}. Define h h ! r 2κh log(8HNh2 /δ) 4κh log(8HNh2 /δ) 4 χh := + , (17) 3 n 3n and, for 1 ≤ t < h ≤ H, 4 τt:h = (ρt:h + ρt+1:h ) 3
r
! √ 2κh log(8H 2 Nt Nh /δ) 2 κt κh log(8H 2 Nt Nh /δ) + , n 3n
(18)
where ρt:h is defined in Definition 5. Now, for two elements u, v ∈ F h , we define the sample inner product and norm as n
⟨u|n , v|n ⟩[n] :=
1X (i) (i) (i) (i) u(sh , ah )v(sh , ah ), n i=1
n
∥u|n ∥2[n] :=
1X (i) (i) u(sh , ah )2 . n i=1
Lemma 17 (Near-isometry). Under Assumption 3, with probability at least 1 − δ/4, simultaneously for all h ∈ [H] and u, v ∈ F h , ⟨u|n , v|n ⟩[n] − ⟨u, v⟩dD ≤ χh ∥u∥2,dD ∥v∥2,dD , h h h where χh is given in Eq. (17). In particular, take u = v, we get the near-isometry norm bound: (1 − χh )∥u∥22,dD ≤ ∥u|n ∥2[n] ≤ (1 + χh )∥u∥22,dD . h
h
Lemma 18 (Cross-step concentration). For any f ∈ F t+1 , define the one-step sample realization (i) (i) (i) operator by (Pbt f )(st , at ) := f (st+1 , π). Under Assumption 3, with probability at least 1 − δ/4, simultaneously for all 1 ≤ t < h ≤ H, all u ∈ F t and all f ∈ F h , E D (h,f ) u|n , (Pbt − Ktπ )gt+1 |n ≤ τt:h ∥u∥2,dD ∥f ∥2,dD , t h [n]
(h,f )
where Ktπ = ΠF t P π is the projected transition operator at step t (see Definition 5), gt+1 is the π π shorthand for Kt+1 · · · Kh−1 f (that is, the backup function of f onto step t + 1 from step h), and τt:h is given in Eq. (18). Proof of Lemma 17. First, we fix an arbitrary pair of elements (u, v) ∈ F h × F h and time step (i) (i) (i) (i) h ∈ [H]. Let Yi = u(sh , ah )v(sh , ah ) and µ = E[Yi ]. Then the concentration error to be controlled becomes n 1X ⟨u|n , v|n ⟩[n] − ⟨u, v⟩dD = Yi − µ . h n i=1 Under Assumption 3, |Yi | ≤ sups,a |u(s, a)||v(s, a)| ≤ κh ∥u∥2,dD ∥v∥2,dD , and by Cauchy-Schwarz h h p 2 2 inequality, µ = |E[uv]| ≤ E[u ] · E[v ] = ∥u∥2,dD ∥v∥2,dD . Thus the range bound is given by h h ∥v∥2,dD , |Yi − µ| ≤ (κh + 1)∥u∥2,dD ∥v∥2,dD ≤ 2κh ∥u∥2,dD h h h h 29
since κh ≥ 1. On the other hand, the variance of Yi can also be bounded via Var[Yi ] ≤ E[Yi2 ] = E[u(s, a)2 · v(s, a)2 ] ≤ κh ∥v∥22,dD · E[u(s, a)2 ] = κh ∥v∥22,dD ∥u∥22,dD , h
h
h
where the inequality is also due to Assumption 3. Thus, by Bernstein’s inequality, for fixed (u, v), with probability at least 1 − δ/2, ! r n 1X 2κh log(4/δ) 4κh log(4/δ) ∥v∥2,dD Yi − µ ≤ ∥u∥2,dD + . h h n i=1 n 3n Now we complete the proof by a standard covering argument. Let Ch be a 1/8-cover of the unit ball ≤ 1} under the norm ∥ · ∥2,dD Bh := {f ∈ F h : ∥f ∥2,dD , with |Ch | = Nh . Applying the fixed-pair h h Bernstein bound above to all pairs (u0 , v0 ) ∈ Ch × Ch and all h ∈ [H], with failure probability δ/(2HNh2 ) for each pair, we obtain that with probability at least 1 − δ/2, simultaneously for all h ∈ [H] and u0 , v0 ∈ Ch , r 2κh log(8HNh2 /δ) 4κh log(8HNh2 /δ) 3 ⟨u0 |n , v0 |n ⟩[n] − ⟨u0 , v0 ⟩dD ≤ + = χh . h n 3n 4 It remains to extend this bound from the finite cover to the whole unit ball. Let Mh = supu,v∈Bh |⟨u|n , v|n ⟩[n] − ⟨u, v⟩dD | be the uniform concentration error. By the covering property, h for arbitrary u, v ∈ Bh , there exists u0 , v0 ∈ Ch such that ∥u − u0 ∥2,dD ≤ h
1 , 8
∥v − v0 ∥2,dD ≤ h
1 . 8
By bilinearity of inner product, we have ⟨u|n , v|n ⟩[n] − ⟨u, v⟩dD ≤ ⟨u0 |n , v0 |n ⟩[n] − ⟨u0 , v0 ⟩dD h h + ⟨(u − u0 )|n , v|n ⟩[n] − ⟨u − u0 , v⟩dD + ⟨u0 |n , (v − v0 )|n ⟩[n] − ⟨u0 , v − v0 ⟩dD . h h The first term is bounded by 3χh /4. For the second term, since ∥u−u0 ∥2,dD ≤ 1/8 and ∥v∥2,dD ≤ 1, h h we have 8(u − u0 ) ∈ Bh and v ∈ Bh . Therefore, by the definition of Mh , we have 1 Mh . 8 Similarly, the third term is also bounded by Mh /8. Combining the three terms, we have that for arbitrary u, v ∈ Bh , 3 1 ⟨u|n , v|n ⟩[n] − ⟨u, v⟩dD ≤ χ h + Mh . h 4 4 Taking the supremum over u, v ∈ Bh , we have Mh ≤ 3χh /4 + Mh /4, which is equivalent to Mh ≤ χh . Finally, for arbitrary u, v ∈ F h , if both norms are non-zero (if either norm is zero, then the same inequality is trivial under Assumption 3, since ∥u∥2,dD = 0 implies u(s, a) = 0 on all h sample points as well), apply the above unit-ball bound to u/∥u∥2,dD and v/∥v∥2,dD yields h h ⟨(u − u0 )|n , v|n ⟩[n] − ⟨u − u0 , v⟩dD ≤ h
⟨u|n , v|n ⟩[n] − ⟨u, v⟩dD ≤ χh ∥u∥2,dD ∥v∥2,dD , h h h
∀u, v ∈ F h ,
∀h ∈ [H].
This proves the uniform concentration bound. Proof of Lemma 18. The proof structure is similar to that of Lemma 17. We first fix t < h, u ∈ Bt and f ∈ Bh , where Bt and Bh are unit balls. Define (i) (i) (h,f ) (i) (h,f ) (i) (i) Zi := u(st , at ) gt+1 (st+1 , π) − gt (st , at ) , (h,f )
where gt becomes
(h,f )
π = Ktπ gt+1 = Ktπ · · · Kh−1 f . Then, the concentration quantity we want to control n
1X = Zi . n i=1 [n]
D E (h,f ) u|n , (Pbt − Ktπ )gt+1 |n
30
Notice that E[Zi ] = 0. This is because when we take expectation, h i (h,f ) (h,f ) E[Zi ] = E(st ,at )∼dD u(st , at ) (P π gt+1 )(st , at ) − (Ktπ gt+1 )(st , at ) . t (h,f )
(h,f )
But Ktπ gt+1 = ΠF t P π gt+1 where ΠF t is the projection onto F t . Since u ∈ F t , the projection residual is orthogonal to F t , i.e., Ktπ and P π agree when tested against functions in F t . Hence E[Zi ] = 0. √ Now we are going to bound Zi . Since ∥u∥2,dD ≤ 1, generalized leverage gives |u(s, a)| ≤ κt . t √ Also, ∥f ∥2,dD ≤ 1 implies ∥f ∥∞ ≤ κh . Thus by Definition 5, we have h √ (h,f ) ∥gt+1 ∥∞ ≤ ρt+1:h κh . √ This gives an upper bound for the range of Zi , i.e., |Zi | ≤ (ρt:h + ρt+1:h ) κt κh . On the other hand, for the variance control, we can use a slightly sharper bound that (h,f )
∥gt
√ ∥∞ ≤ ρt:h κh ,
Var[Zi ] ≤ E[Zi2 ] ≤ (ρt:h + ρt+1:h )2 κh · E(st ,at )∼dD [u(st , at )2 ] ≤ (ρt:h + ρt+1:h )2 κh , t since ∥u∥2,dD ≤ 1. Therefore, Bernstein’s inequality gives for fixed u, f , with probability at least t 1 − δ/2, ! r √ n 1X 2κh log(4/δ) 2 κt κh log(4/δ) Zi ≤ (ρt:h + ρt+1:h ) + . n i=1 n 3n The subsequent steps are similar. We can take 1/8-nets Ct ⊂ Bt and Ch ⊂ Bh , with sizes |Ct | = Nt and |Ch | = Nh . Union bound over all (u0 , f0 ) ∈ Ct × Ch and all t, h gives the same bound with log(4/δ) ⇝ log(8H 2 Nt Nh /δ). We can apply the same procedure to extend the bound from the net to the whole unit ball, by paying an additional 4/3 factor to get D E (h,f ) sup u|n , (Pbt − Ktπ )gt+1 |n ≤ τt:h . [n]
u∈Bt ,f ∈Bh
Finally, for general nonzero u, f , apply the above unit-ball result to u/∥u∥2,dD and f /∥f ∥2,dD proves t h the simultaneous concentration bound. C.4
Proof of Theorem 8
Now we are going to prove the empirical-population tracking theorem (Theorem 8). We will break the proof into three steps. Throughout, define , ηh := ∥w eh − wh⋆ ∥2,dD h
[n]
∆h := ∥w bh − wh⋆ |n ∥[n] .
Our goal is to control the tracking error ∆h . Step 1: duality conversion We will first transfer the weight error ∆h to the functional-side error ηh . This is inspired by linear case where the linear functional (dual) space corresponds to the feature space, and the dynamical system in linear case is also defined in the feature space, which is a much more convenient way to do analysis; see also Duan et al. [2020]. To see why this is a duality, define the dual norm ∥ · ∥∗ for linear functional Λ such that ∥Λ∥∗ =
|Λ(f )|.
sup f ∈F h :∥f ∥2,dD ≤1 h
The following proposition relates ηh with this functional error’s dual norm. b h , Λ⋆ : F h → R, suppose their Riesz Proposition 19 (Error duality). For two linear functionals Λ h ⋆ b h − Λ⋆ ∥∗ . representers are two elements w eh , w ∈ F h , respectively. Then, ∥w eh − w⋆ ∥2,dD = ∥Λ h
h
h
Proof. For any f ∈ F h , we have b h − Λ⋆h )(f ) = ⟨w (Λ eh − wh⋆ , f ⟩dD ≤ ∥w eh − wh⋆ ∥2,dD ∥f ∥2,dD , h h h 31
h
where the first equality is due to Riesz representation theorem, and the second inequality is by Cauchyb h − Λ⋆ ∥∗ ≤ Schwarz. Thus, taking the supremum over ∥f ∥2,dD ≤ 1 gives one direction, i.e., ∥Λ h h ∥w eh − wh⋆ ∥2,dD . h On the other hand, if w eh = wh⋆ , then the claim is trivial. Otherwise, take w eh − wh⋆ fh⋆ = ∈ F h. ∥w eh − wh⋆ ∥2,dD h b h − Λ⋆ )(f ) = ∥w b h − Λ⋆ ∥∗ ≥ ∥w Then ∥fh⋆ ∥2,dD = 1, and (Λ eh − wh⋆ ∥2,dD . Hence, ∥Λ eh − wh⋆ ∥2,dD . h h h h h Combining the two inequalities proves the claim. Now we are going to translate the tracking error ∆h with the functional error ηh ; see the following lemma. Lemma 20 (Tracking error conversion). For any h ∈ [H], assume χh ≤ 1/2 for χh in Eq. (17), which can be achieved by n ≳ κh log(HNh /δ). Then, ∆h ≤ (1 + 3χh )ηh + 2χh ∥wh⋆ ∥2,dD . h Proof. By triangular inequality, [n]
∆h = ∥w bh − wh⋆ |n ∥[n] = ∥w̄h − wh⋆ ∥[n] ≤ ∥w eh − wh⋆ ∥[n] + ∥w̄h − w eh ∥[n] . √ For the first term, Lemma 17 gives (where we use 1 + x ≤ 1 + x/2 for x ≥ 0): p 1 χ ∥w eh − wh⋆ ∥[n] ≤ 1 + χh ∥w eh − wh⋆ ∥2,dD ηh . ≤ 1 + h h 2 b h ) and w̄h (which is the For the second term, recall the definition of w eh (which is the representer of Λ [n]
sample-lift of w bh ), we have b h (f ) = ⟨w̄h , f ⟩[n] , ⟨w eh , f ⟩dD =Λ h
∀f ∈ F h .
Taking f = w̄h − w eh , we obtain ∥w̄h − w eh ∥2[n] = ⟨w̄h , w̄h − w eh ⟩[n] − ⟨w eh , w̄h − w eh ⟩[n] = ⟨w eh , w̄h − w eh ⟩dD − ⟨w eh , w̄h − w eh ⟩[n] h ≤ χh ∥w eh ∥2,dD ∥w̄h − w eh ∥2,dD h h χh ∥w eh ∥2,dD ∥w̄h − w eh ∥[n] , ≤√ h 1 − χh where the last two inequalities are both due to Lemma 17. By canceling a ∥w̄h − w eh ∥[n] , we have χh ∥w eh ∥2,dD ≤ 2χh (ηh + ∥wh⋆ ∥2,dD ∥w̄h − w eh ∥[n] ≤ √ ), h h 1 − χh where we use the fact that χh ≤ 1/2 and triangular inequality. Combining the two terms, we have 1 ) ≤ (1 + 3χh )ηh + 2χh ∥wh⋆ ∥2,dD . ∆h ≤ 1 + χh ηh + 2χh (ηh + ∥wh⋆ ∥2,dD h h 2
Step 2: functional telescoping and recursion By Proposition 19 and Lemma 20, we learned that essentially we want to control b h − Λ⋆h ∥∗ = b h (f ) − Λ⋆h (f )|. ηh = ∥Λ sup |Λ f ∈F h :∥f ∥2,dD ≤1 h
b h , since our Q-MMR The following telescoping lemma demonstrates the iterative nature of Λ⋆h and Λ algorithm is level-by-level. As we will see, the iterative property of the population functional Λ⋆h depends on the projected backup operator Khπ in Definition 5; while the operator corresponding to b h is the one-step realization operator Pbh defined in Lemma 18, i.e., the empirical functional Λ (i) (i) (i) (Pbh f )(s , a ) = f (s , π), f ∈ F h+1 . h
h
h+1
Such correspondences enable us to do functional telescoping; see the following lemma. 32
Lemma 21 (Functional telescoping). For every h ∈ [H] and f ∈ F h , b h (f ) − Λ⋆h (f ) = Λ b 1 (g (h,f ) ) − Λ⋆1 (g (h,f ) ) + Λ 1 1
h−1 XD
(h,f )
w̄t |n , ((Pbt − Ktπ )gt+1 )|n
t=1 (h,f )
where gt
E
,
[n]
π π is the shorthand for Ktπ Kt+1 · · · Kh−1 f , i.e., the multi-step backup of f ∈ F h onto F t . (h,f )
Proof. We first claim that Λ⋆h (f ) = Λ⋆t (gt
(h,f )
) = ⟨wt⋆ , gt
⟩dD for every 1 ≤ t ≤ h ≤ H and t ⋆ ⋆ (h,f ) f ∈ F h . Suppose this claim holds, we have that Λh (f ) = Λ1 (g1 ). Thus it remains to relate the (h,f ) b t+1 , we have empirical functionals. Write gt := gt ∈ F t . By the definition of Λ n X (i) (i) b t+1 (gt+1 ) = 1 Λ w b gt+1 (st+1 , π) = ⟨w̄t , Pbt gt+1 ⟩[n] , n i=1 t
and by using the matching condition (Proposition 15(iii)), we can also write n X (i) (i) (i) b t (gt ) = 1 w b gt (st , at ) = ⟨w̄t |n , gt |n ⟩[n] . Λ n i=1 t
Since gt = Ktπ gt+1 by the backup recursion, the difference of the above two equations becomes b t+1 (gt+1 ) − Λ b t (gt ) = ⟨w̄t |n , ((Pbt − Ktπ )gt+1 )|n ⟩[n] . Λ By telescoping (summing over t = 1, . . . , h − 1), we have b h (f ) − Λ b 1 (g1 ) = Λ
h−1 X
⟨w̄t |n , ((Pbt − Ktπ )gt+1 )|n ⟩[n] ,
t=1 (h,f ) since f = gh . This proves the lemma. (h,f )
Now we go back to prove the claim that Λ⋆h (f ) = Λ⋆t (gt ) = ⟨wt⋆ , gt ⟩dD . If t = h, gt = gh t so the claim trivially holds. Consider t < h. For t = h − 1, we can write
=f
⋆ π ⋆ ⋆ , Kh−1 f ⟩dD , Λ⋆h (f ) = EdD [wh−1 · (P π f )] = EdD [wh−1 · (ΠF h−1 P π f )] = ⟨wh−1 h−1 h−1 h−1 ⋆ where the second equality uses wh−1 ∈ F h−1 (Proposition 15(i)) and orthogonality of Πh−1 (the π projection onto F h−1 ), and the last equality uses the definition of Kh−1 = ΠF h−1 P π . Iterating this identity, we have π π Λ⋆h (f ) = ⟨wt⋆ , Ktπ Kt+1 · · · Kh−1 f ⟩dD = ⟨wt⋆ , gt ⟩dD = Λ⋆t (gt ), t t
where the last equality is due to the definition of Λ⋆t . Using the telescoping in Lemma 21, we can now decompose this empirical-population tracking error (in the functional space) and thereby control ηh , yielding a recursion formula to be solved later. Lemma 22 (Functional recursion). With probability at least 1 − δ, assume χt ≤ 1/2 for all t ≤ h. Then for every h ∈ [H], r h−1 h−1 X X 4 2κh log(4Nh /δ) ⋆ ηh ≤ at:h ηt + at:h ∥wt ∥2,dD + ρ1:h , t 3 n t=1 t=1 √ where at:h := τt:h + 3χt κh (ρt:h + ρt+1:h ) with χh in Eq. (17) and τt:h in Eq. (18). Proof. Fix f ∈ F h with ∥f ∥2,dD ≤ 1. By Lemma 21, we have h b h (f ) − Λ⋆h (f ) = Λ b 1 (g (h,f ) ) − Λ⋆1 (g (h,f ) ) + Λ 1 1
h−1 XD
(h,f ) w̄t |n , ((Pbt − Ktπ )gt+1 )|n
t=1
33
E [n]
.
b 1 (g) − Λ⋆ (g) with g := g (h,f ) , by Definition 6, we have For the first-step error term Λ 1 1 n X (i) (i) b 1 (g) − Λ⋆1 (g) = 1 Λ w b g(s1 , π) − ED [w0⋆ (s0 , a0 )g(s1 , π)] n i=1 0 r n 1X 2κh log(4Nh /δ) 4 (i) = g(s1 , π) − ED [g(s1 , π)] ≤ ρ1:h , n i=1 3 n
with probability at least 1 − δ/2, where we used ∥g∥∞ ≤ ρ1:h and the standard covering argument (h,f ) over Bh (since g = g1 is uniquely determined by f ∈ F h ). It remains to tackle the second summation term. For notational simplicity, we omit the |n in ⟨·|n , ·|n ⟩[n] in the following proof. We decompose this functional error into the following three terms using w̄t = (w et − wt⋆ ) + wt⋆ + (w̄t − w et ): D E (h,f ) (I) = w et − wt⋆ , (Pbt − Ktπ )gt+1 , [n]
D E (h,f ) (II) = wt⋆ , (Pbt − Ktπ )gt+1
,
[n]
(III) =
D E (h,f ) w̄t − w et , (Pbt − Ktπ )gt+1
.
[n]
. For the third term, By Lemma 18, we have (I) ≤ τt:h ηt and (II) ≤ τt:h ∥wt⋆ ∥2,dD t (h,f )
(III) ≤ ∥w̄t − w et ∥[n] · (Pbt − Ktπ )gt+1 [n] χt (h,f ) (h,f ) ⋆ b + gt , ≤√ (ηt + ∥wt ∥2,dD ) Pt gt+1 t [n] [n] 1 − χt where the first inequality is due to Cauchy-Schwarz, and the second inequality we leveraged proof of Lemma 20 to control the first ∥w̄t − w et ∥[n] term, and the triangular inequality to control the second (h,f )
term (by noticing that gt
(h,f )
= Ktπ gt+1 ).
(h,f )
For the ∥Pbt gt+1 ∥[n] term, we can bound it via Definition 5: v u n u 1 X (h,f ) (i) √ (h,f ) (h,f ) b g (s , π)2 ≤ max gt+1 (s, a) ≤ κh ρt+1:h . Pt gt+1 =t s,a n i=1 t+1 t+1 [n] (h,f )
where we use Assumption 3 and the fact that ∥f ∥2,dD ≤ 1. For the ∥gt ∥[n] term, we can similarly h bound it via Definition 5 (transferred via isometry concentration at first): p p √ √ (h,f ) (h,f ) 1 + χt · κh ρt:h ≤ 2 κh ρt:h . gt ≤ 1 + χt gt ≤ D [n]
2,dt
Hence combining the terms, the third term can be controlled by √ 2χt κh (III) ≤ √ (ρt:h + ρt+1:h )(ηt + ∥wt⋆ ∥2,dD ) t 1 − χt √ ≤ 3χt κh (ρt:h + ρt+1:h )(ηt + ∥wt⋆ ∥2,dD ). t Summing the three bounds and taking the supremum over ∥f ∥2,dD ≤ 1 controls the functional error h term. By union bound over three events: the first step concentration error with failure probability δ/2, the event in Lemma 17 with failure probability δ/4, and the event in Lemma 18 with failure probability δ/4; we prove the claim with probability at least 1 − δ. Step 3: solving the recursion As shown in Lemma 22, what we get is essentially a recursion in ηh (i.e., the RHS also appears ηt for t ≤ h). Therefore the final step of proving Theorem 8 is to solve for this recursion to control ηh , hence ∆h . 34
Proof of Theorem 8. Abbreviate ϵ1:j = 43 ρ1:j Ah := max ϵ1:j + 1≤j≤h
j−1 X
p 2κj log(4Nj /δ)/n. Let
at,j ∥wt⋆ ∥2,dD , t
Bh := max
1≤j≤h
t=1
j−1 X
at,j ,
Eh := max ηj .
t=1
1≤j≤h
By Lemma 22, with probability at least 1 − δ, for every j ≤ h, we have ηj ≤
j−1 X t=1
at,j ηt + ϵ1:j +
j−1 X
at,j ∥wt⋆ ∥2,dD ≤ Bh Eh + Ah . t
t=1
Taking the maximum over j ≤ h gives Eh ≤ Bh Eh + Ah . Hence, we have h−1 X Ah ηh ≤ max ηj = Eh ≤ ≤ 2Ah ≤ 2ϵ1:h + 2 at:h ∥wt⋆ ∥2,dD , t 1≤j≤h 1 − Bh t=1 Ph where we use Bh ≤ 1/2 since our choice of n that n ≳ (maxt≤h κt )2 ( t=1 ρt:h )2 log(H 2 Nt Nh /δ) automatically enables Bh ≤ 1/2; and the last inequality is due to the maximum of Ah is exactly taken at j = h (because all elements are non-negative; that is, at,j ∥wt⋆ ∥2,dD ≥ 0). Now we can apply t Lemma 20: h−1 X ≤ 5ϵ + 5 at:h ∥wt⋆ ∥2,dD + 2χh ∥wh⋆ ∥2,dD , ∆h ≤ (1 + 3χh )ηh + 2χh ∥wh⋆ ∥2,dD 1:h t h h t=1
where we use χh ≤ 1/2 (hence 2(1 + 3χh ) ≤ 5). By the definitions of χh in Eq. (17) and τt:h in Eq. (18), we have ∆h ≤ 5ϵ1:h + 5
h−1 X
at:h ∥wt⋆ ∥2,dD + 2χh ∥wh⋆ ∥2,dD t h
t=1 h−1 4 2κh log(4Nh /δ) 20 √ X ρ1:h + κh (ρt:h + ρt+1:h )∥wt⋆ ∥2,dD t 3 n 3 t=1 s s ! 2 2 √ 8HN 2 8HN 2 t Nh t Nh 2κh log 8H N 2 κt κh log 8H N 2κh log δ h 4κh log δ h δ δ · + +3 + n 3n n n s ! 8HN 2 8HN 2 2κh log δ h 4κh log δ h 8 ⋆ + + ∥wh ∥2,dD h 3 n 3n s s 2 h X κ2h log H Nδt Nh κh log Nδh + ρ ∥wt⋆ ∥2,dD + higher order term. ≲ ρt:h 1:h t n n t=1
r
≤
We use ≲ to ignore some universal constants (here the constant can be set to 320/3 if we combine all terms), and the higher order term is of order O(1/n) in the above equation. And we also combined the logarithmic terms and the first step term (by our choice of n ≳ Ph (maxt≤h κt )2 ( t=1 ρt:h )2 log(H 2 Nt Nh /δ)). Therefore, ignoring the higher-order term, we prove Theorem 8: for any h ∈ [H], with probability at least 1 − δ, r r h X κh log(H 2 Nt Nh /δ) ⋆ κh log(Nh /δ) [n] ⋆ w bh − wh |n ≲ ρt:h ∥wt ∥2,dD + ρ1:h . t n n [n] t=1
C.5
Proofs of Proposition 9 and Corollary 10
Here we provide the proof of Proposition 9, as well as the random-design result of the Q-MMR algorithm (Corollary 10). As stated in Proposition 9, the population 0 matching loss will imply the empirical 0 matching loss with high probability. In the linear case, this is obvious since the invertible b by matrix Bernstein inequality. However, covariance Σ implies the invertible empirical covariance Σ under GFA, we need to leverage the near-isometry concentration argument (Lemma 17). 35
Proof of Proposition 9. As we will see, the empirical 0 matching loss does not rely on the whole (1) (1) (n) (n) function f ∈ F h , but its sample-evaluation f |n = (f (sh , ah ), . . . , f (sh , ah )), where the sample evaluation map |n : F h → Rn . The near-isometry condition in Lemma 17 implies that |n is injective. Indeed, if f |n = 0, then ∥f |n ∥[n] = 0, which implies 0 = ∥f |n ∥2[n] ≥ (1 − χh )∥f ∥22,dD . h
Since χh < 1/2 by our choice of n, this gives ∥f ∥2,dD = 0, hence f = 0 as an element of F h . h Now consider the sample evaluation space F h |n = {f |n : f ∈ F h } ⊆ Rn . We can define a linear functional ℓh : F h |n → R by n X (i) (i) b h (f ) = 1 ℓh (f |n ) := Λ w b f (sh , π), n i=1 h−1
∀f |n ∈ F h |n ,
This is well defined. To see this, suppose f |n = g|n . Then (f − g)|n = 0 by linearity; and f = g in F h by injectivity of this sample evaluation operator |n , i.e., ∥f − g∥2,dD = 0. Therefore, we can h apply generalized leverage (Assumption 3) to give |f (s, a) − g(s, a)| ≤
√
κh ∥f − g∥2,dD = 0, h
∀(s, a) ∈ Sh × A. (i)
(i)
Thus f and g also agree pointwise. In particular, this implies f (sh , π) = g(sh , π) for all i ∈ [n]. b h (f ) = Λ b h (g). So the linear functional ℓh is well-defined. Hence Λ Next, since F h |n is a subspace of Rn , it is also finite-dimensional. Equip F h |n with the empirical inner product ⟨z, z ′ ⟩[n] = n1 z ⊤ z ′ . By the finite-dimensional Riesz representation theorem, there exists some vector ah ∈ F h |n ⊆ Rn such that ℓh (z) = ⟨ah , z⟩[n] ,
∀z ∈ F h |n .
Taking z = f |n , we have n X (i) (i) (i) b h (f ) = ℓh (f |n ) = ⟨ah , f |n ⟩[n] = 1 Λ a f (sh , ah ), n i=1 h
∀f ∈ F h .
[n]
By setting w bh := ah , we would achieve empirical 0 matching loss, i.e., n n X 1 X (i) (i) (i) (i) (i) b h (f ) = 1 w bh f (sh , ah ) = Λ w b f (sh , π). n i=1 n i=1 h−1
So the empirical matching loss over F h is zero. Since Fh ⊆ F h , the empirical matching loss over Fh is also zero. Thus the empirical minimizer used by Q-MMR also achieves zero loss.
The proof of Corollary 10 is a direct consequence of Theorem 8 (by leveraging the same procedure of telescoping as our fixed-design result in Theorem 1). As we will see in the following, the empiricalpopulation tracking error is paired with the average Bellman residual, leading it to a higher-order term so that the dominant term becomes random-design control. 36
Proof of Corollary 10. First, we make the following decomposition of the suboptimality gap J(π) − b J(π): n
b |J(π) − J(π)| = Qπ (s0 , a0 ) −
H
1 X X (i) (i) w bh rh n i=1 h=0
n X
n H 1 1 X X (i) (i) (i) (i) (i) w b0 Qπ (s0 , a0 ) − w bh rh n i=1 n i=1
=
h=0
n X H X
1 n i=1
=
h=0
n X H 1X (i) (i) (i) (i) (i) (i) (i) (i) w bh Qπ (sh , ah ) − w bh+1 Qπ (sh+1 , ah+1 ) − w bh rh n i=1 h=0
n H 1 X X (i) π (i) (i) (i) (i) (i) (i) = w bh Q (sh , ah ) − w bh Qπ (sh+1 , π) − w bh rh n i=1 h=0
n H 1 XX
≤
n i=1
h=0
{z
| (i)
n H 1 X X (i) (i) (i) (i) + w bh − wh⋆ (sh , ah ) εh , n i=1 h=0 } | {z }
(i) (i) (i) wh⋆ (sh , ah )εh
(I): random design control
(i)
(i)
(i)
(i)
(i)
(II): tracking error
(i)
where εh := Qπ (sh , ah ) − rh − Qπ (sh+1 , π) denotes the Bellman residual at current transition (i)
(i)
sample (sh , ah , rh , sh+1 ). We use that w b0 ≡ 1 and w bH+1 ≡ 0; and the fourth equation is due to our empirical 0 matching loss in Proposition 9. The first term is the random-design control on population weight functional wh⋆ . For each fixed (i) (i) (i) (i) (i) h, define Xh,i := wh⋆ (sh , ah )εh . Conditioned on {(sh , ah )}ni=1 , the variables {Xh,i }ni=1 are (i) (i) (i) independent, mean-zero, and satisfy |Xh,i | ≤ Vmax |wh⋆ (sh , ah )| since |εh | ≤ |Vmax |. Therefore, by standard Hoeffding’s inequality, we have: with probability at least 1 − α, r n 1X 2 log(2/α) ⋆ Xh,i ≤ Vmax ∥wh |n ∥[n] , n i=1 n where ∥wh⋆ |n ∥[n] =
P n 1 n
⋆ (i) (i) 2 i=1 wh (sh , ah )
1/2
. Using the near-isometry transfer in Lemma 17
and χh ≤ 1/2 (which is implied by our choice of n in Corollary 10), we have r p 3 ⋆ ⋆ ⋆ ∥w ∥ D ≤ 2∥wh⋆ ∥2,dD ∥wh |n ∥[n] ≤ 1 + χh ∥wh ∥2,dD ≤ . h h 2 h 2,dh Take α = δ/(2(H + 1)), then union bound over h ∈ [H], we can control the first term by r H 2 log(4(H + 1)/δ) X ⋆ (I) ≤ 2Vmax ∥wh ∥2,dD . h n h=0
(i) (i)
(i)
Now for the tracking part, define Yh,i = ∆h εh . Because w bh depends only on the trajectory prefix (i) (i) (i) (i) (i) ⋆ (i) (i) up to (sh , ah ), and wh (sh , ah ) is also measurable with respect to (sh , ah ), the coefficient ∆h is fixed when conditioning on the level-h prefixes. Therefore, conditional on those prefixes, the (i) variables {Yh,i }ni=1 are again independent, mean-zero, and |Yh,i | ≤ Vmax |∆h |. Apply Hoeffding’s inequality again, for each fixed h, with probability at least 1 − α, r r n 2 log(2/α) 2 log(2/α) [n] 1X Yh,i ≤ Vmax ∥∆h ∥[n] = Vmax ∥w bh − wh⋆ |n ∥[n] . n i=1 n n Taking again α = δ/(2(H + 1)) and union bound over h, we can control the second term by r H 2 log(4(H + 1)/δ) X [n] (II) ≤ Vmax ∥w bh − wh⋆ |n ∥[n] , n h=1
37
(i)
since w0⋆ ≡ 1 and w b0 = 1 for all i ∈ [n]. So now we can apply the tracking theorem (Theorem 8) to see that the second term is indeed a higher-order term, since both the average Bellman error and the tracking error exhibit the rate of n−1/2 (hence an overall rate of n−1 ). Combining (I) and (II) proves the corollary.
D
Further discussion on MIS
D.1
Issues with non-parametric weights in MIS
MIS methods often take a minimax form similar to our Q-MMR, and here we provide further discussion on the issue with learning non-parametric weights in MIS. Taking MQL [Uehara et al., 2020] as an example, whose population loss is (in the infinite-horizon discounted setting) arg min max Lq (f, w) := |EdD [w(s, a)(f (s, a) − r − γf (s′ , π))]| . f ∈F
w∈W
When w is not restricted to a parametric class W but is a separate scalar for each data point, one can immediately see that the loss L is ill-behaved: the original MIS derivations rely on the fact that maxw∈W L(Qπ , w) = 0 [Uehara et al., 2020, Jiang and Huang, 2020], but when w is nonparametric, L(Qπ , w) ̸= 0 in general when the environment is stochastic, since w can simply choose to be positive or negative depending on the sign of Qπ (s, a) − r − γQπ (s′ , π). (This issue can be viewed as a version of the infamous double-sampling problem.) In contrast, our algorithm and analyses forbid the choice of w to depend on the next-state randomness, which avoids this problem. Now, MQL learns f using w as discriminator, and its “dual” method such as MWL [Uehara et al., 2020] learns w using f as discriminator, which is more similar to our method. We conjecture that MWL is subject to similar issues, though a clear counterexample remains to be found. D.2
Data-dependent bounds for MIS
Consider MWL, whose population loss is (we assume initial state-action pair is fixed as (s0 , a0 )) arg min sup Lw (w, f ) := f (s0 , a0 ) + w∈W
f ∈F
1 E D [w(s, a)(γf (s′ , π) − f (s, a))] . 1−γ d
The actual algorithm optimizes the empirical loss Lbw where EdD is replaced with the empirical 1 b b dD , and forms the final prediction J(π) b expectation E = 1−γ EdD [wr] b where w b is the learned w. The standard finite-sample guarantee for MWL pays for the statistical complexities of both W and F. Below we show that the complexity of F can be avoided in a data-dependent guarantee similar to our Theorem 1: for any fixed w ∈ W, we have 1 b E D [w(s, a)r] − J(π) 1−γ d 1 b 1 b = E D [w(s, a)(Qπ (s, a) − r − γQπ (s′ , π)] − Qπ (s0 , a0 ) + E D [w(s, a)(−Qπ (s, a) + γQπ (s′ , π)) 1−γ d 1−γ d 1 b ≤ E D [w(s, a)(Qπ (s, a) − r − γQπ (s′ , π)] + sup Lbw (w, f ). (Qπ ∈ F) 1−γ d f ∈F The first term enjoys a “fixed-design” concentration bound similar to our proof of Theorem 1, but needs a union bound over w ∈ W so that the bound holds for w. b The second term is the empirically observed loss, similar to our Lbh term in Theorem 1.
38