Model Selection for Off-Policy Evaluation via Pairwise Bellman Validation

Model Selection for Off-Policy Evaluation via Pairwise Bellman Validation

arXiv:2610.35748v1 [stat.ML] 26 Oct 2026

Lars van der Laan Stanford University vdlaan@stanford.edu

Vasilis Syrgkanis Stanford University

Nathan Kallus Netflix and Cornell University

Abstract Model selection and hyperparameter tuning pose a central challenge in off-policy evaluation (OPE) because the estimation errors of fitted Q-functions and occupancy-ratio estimates cannot be directly evaluated from held-out transitions. Bellman-residual and minimax validation methods often require auxiliary regressions or optimization over separate critic classes, adding computational and tuning costs. We introduce pairwise Bellman validation (PBV), a tuning-free minimax procedure for selecting among finite classes of fitted Q-functions and occupancy-ratio estimators using held-out transitions. PBV constructs critics from pairwise differences between candidates, reducing validation to computing a finite collection of penalized empirical moments, without fitting auxiliary validation models or optimizing over a separate critic class. We establish finite-sample oracle inequalities relative to the best available candidate, even under candidate-class misspecification. Our key insight is that Q-function errors and log ratios between candidate and true occupancy ratios provide oracle critics whose Bellman and adjoint Bellman moments control estimation error. These unknown critics can be approximated using pairwise differences between candidates, while penalties account for comparator approximation error. For Q-function selection, we first develop unweighted PBV, which evaluates pairwise Bellman moments under the offline distribution and admits oracle guarantees under a pairwise coercivity condition relating the offline distribution to the target-policy dynamics. We then develop target-aligned PBV (TA-PBV), which uses marginalized importance weighting to provide error control without pairwise coercivity. For occupancy-ratio selection, we develop adjoint PBV (A-PBV), which evaluates adjoint Bellman moments against log-ratio critics. On Hopper and Deep OPE, unweighted PBV performs competitively, while target-occupancy weighting can improve performance in settings with controlled overlap. Keywords: Model selection, hyperparameter tuning, off-policy evaluation, Bellman equations, occupancy-ratio estimation, value-function estimation, infinite-horizon reinforcement learning

1. Introduction 1.1. Motivation The goal of off-policy evaluation (OPE) is to estimate the value of a target policy using data collected under a different policy in a Markov decision process (MDP). In offline reinforcement learning, two central objects are the target-policy action-value function, or Q-function, and the discounted occupancy ratio (Uehara et al., 2026). These functions underlie direct, importance-weighted, and doubly robust OPE, as well as semiparametrically efficient inference (Jiang and Li, 2016; Kallus and Uehara, 2020, 2022; van der Laan et al., 2025; Xie et al., 2019). They are characterized, respectively, as fixed points of the Bellman and adjoint Bellman operators (Uehara et al., 2021). Leveraging this structure, the Q-function and occupancy ratio can be learned using fitted-iteration methods, such as FQE, or minimax methods that test Bellman residuals against a class of critic functions, such as DualDICE and minimax Q-learning (Munos and Szepesvári, 2008; Nachum et al., 2019; Uehara et al., 2020, 2021; van der Laan and Kallus, 2026). A central challenge in OPE is model selection and hyperparameter tuning. Different choices of algorithms, function classes, regularization, and hyperparameters produce competing Q-function and occupancy-ratio estimates, but neither admits a supervised validation loss that can be directly evaluated from logged data. For Q-functions, squared temporal-difference error is generally unsuitable for comparing candidates under 1

stochastic transitions because it includes a candidate-dependent conditional-variance term (Baird III, 1995). Bellman-residual validation instead estimates the Bellman residual Q − Bπ Q, where Bπ denotes the targetpolicy Bellman operator, and selects the candidate with the smallest estimated mean-squared residual. This typically requires fitting a separate regression for each candidate (Zitovsky et al., 2023), which can be computationally prohibitive and introduces an additional tuning problem. An alternative is minimax moment validation, which avoids regression by evaluating moments of the Bellman residual against a class of critic functions and selecting the candidate that minimizes the largest absolute empirical moment over that class (Miyaguchi, 2026; Uehara et al., 2021). This approach requires specifying and potentially tuning a critic class and can involve computationally demanding and numerically delicate optimization, particularly with flexible critics. More recently, LSTD-Tournament (Liu et al., 2025) avoids specifying a separate critic class by comparing candidates pairwise using least-squares temporal-difference Q-learning (LSTDQ). However, its theoretical guarantees require the true Q-function to belong to the finite candidate class, a strong realizability assumption, as well as matrix-conditioning assumptions linking the offline distribution to the target-policy dynamics.

1.2. Contributions We introduce pairwise Bellman validation (PBV), a tuning-free minimax procedure for selecting among finite classes of fitted Q-functions and occupancy-ratio estimators using held-out transitions. PBV provides oracle selection guarantees without requiring realizability. Operationally, PBV constructs a finite class of critics from pairwise comparisons between candidates and evaluates each candidate using empirical moments of its Bellman or adjoint Bellman residual against these critics. For Q-function selection, each moment is the held-out average of a one-step temporal-difference residual multiplied by a critic. PBV subtracts a penalty for critic size from each empirical moment and selects the candidate with the smallest maximum score over its pairwise critics. Validation therefore reduces to computing a finite collection of sample averages, without fitting auxiliary validation models or separately optimizing critic functions. Our key observation is that estimation errors provide oracle critics whose corresponding moments control estimation error. Under suitable conditions, we show that evaluating the Bellman residual of Qi against Qi − Qπ controls its squared L2 error, while evaluating the adjoint Bellman residual of wi against log(wi /wπ ) controls its generalized-KL error. Since these oracle critics depend on unknown targets, we approximate them using pairwise differences: Qi − Qj for Q-function selection and log(wi /wj ) for occupancy-ratio selection. These pairwise critics recover the oracle critics when the comparator equals the truth and approximate them when it is close. Together with a penalty for critic size, this construction yields oracle guarantees relative to the best available candidate, even under candidate-class misspecification. For Q-function selection, we first develop unweighted PBV, which evaluates these moments under the offline distribution with a quadratic critic penalty. Because the target-policy Bellman operator need not be contractive in the corresponding L2 norm, our guarantees require a pairwise coercivity condition analogous to matrix-conditioning assumptions in LSTD-Tournament and linear TD learning (Amortila et al., 2026; Bradtke and Barto, 1996; Lagoudakis and Parr, 2003; Tsitsiklis and Van Roy, 1997). We then develop target-aligned PBV (TA-PBV), which uses marginalized importance weighting to evaluate the same moments under the discounted target-occupancy distribution, where contraction provides error control without pairwise coercivity. Thus, unweighted PBV avoids occupancy-ratio estimation, whereas TA-PBV removes the coercivity requirement at the cost of importance weighting. For occupancy-ratio selection, we develop adjoint PBV (A-PBV), which evaluates adjoint Bellman residuals against log-ratio critics with a penalty proportional to the squared Hellinger distance between candidate ratios. A-PBV requires neither importance weighting nor a coercivity condition because the adjoint Bellman operator is already contractive in KL divergence under the offline distribution (van der Laan and Kallus, 2026). To our knowledge, unweighted PBV and TA-PBV are the first tuning-free procedures for selecting among fitted Q-functions with finite-sample oracle guarantees under candidate-class misspecification. A-PBV provides an analogous first result for selecting among fitted occupancy-ratio estimators, without auxiliary estimation or additional tuning. In summary, our contributions are: 2

1. We develop pairwise validation procedures for Q-function and occupancy-ratio selection that require no auxiliary critic fitting and allow heterogeneous and misspecified candidate classes. 2. For unweighted PBV, we establish a finite-sample oracle inequality under pairwise coercivity, without occupancy-ratio estimation. 3. For A-PBV and TA-PBV, we establish joint finite-sample oracle inequalities that separate occupancyratio and Q-function approximation errors and quantify how occupancy-ratio selection error propagates to Q-function selection. The validation rates are near-parametric, with logarithmic dependence on candidateclass sizes.

1.3. Related work Model selection for Q-functions and occupancy ratios. Existing OPE model-selection methods have focused primarily on Q-functions, using Bellman residuals, candidate-dependent projections, nested classes, or auxiliary regressions and critics in place of the unavailable supervised loss (Farahmand and Szepesvári, 2011; Lee et al., 2022; Miyaguchi, 2026; Xie and Jiang, 2021; Zhang and Jiang, 2021; Zitovsky et al., 2023). These approaches generally introduce additional estimation or structural requirements beyond the candidate class itself; LSTD-Tournament is an important exception and is discussed separately below. By contrast, model selection among already-fitted occupancy-ratio estimators has received substantially less attention, despite extensive work on occupancy-ratio estimation (Nachum et al., 2019; Uehara et al., 2020, 2021; van der Laan and Kallus, 2026). Extended discussion appears in Appendix E. Comparison with LSTD-Tournament. LSTD-Tournament (Liu et al., 2025) selects among candidate Q-functions using a tournament criterion derived from pairwise LSTDQ. For each pair (Qi , Qj ), it constructs a two-dimensional feature map from the candidates and evaluates the corresponding LSTDQ normal-equation residuals (Lagoudakis and Parr, 2003). Its selection criterion (Equation 10 in their work) can equivalently be viewed as a minimax procedure that evaluates the Bellman residual of each candidate Qi against the candidate Q-functions themselves as critics. Its theoretical guarantees assume candidate-class realizability and depend on the conditioning of pair-specific LSTD matrices. In their experiments, Liu et al. (2025) use a variant with normalized features Qi /ci and (Qj − Qi )/cij , motivated by numerical stability. Although these features span the same linear space as Qi and Qj , they induce different comparisons. The resulting empirical procedure can be viewed as a minimax moment selector with critics comprising normalized candidate functions and pairwise differences. Our analysis provides a theoretical explanation for why including pairwise differences as features may improve LSTD-Tournament: when Qj is close to the truth, Qi − Qj approximates the oracle critic Qi − Qπ , whose Bellman moment controls the estimation error of Qi . This approach is most closely related to unweighted PBV but differs in several important respects. In particular, unweighted PBV uses unnormalized pairwise differences and introduces quadratic critic penalties to account for comparator approximation error, allowing us to establish oracle inequalities under candidate-class misspecification. Our guarantees for unweighted PBV require a pairwise coercivity condition under the offline distribution, analogous to but distinct from the invertibility requirement for pair-specific LSTD matrices. TA-PBV further avoids both matrix-conditioning and pairwise coercivity requirements through importance weighting, while A-PBV extends pairwise validation to occupancy-ratio estimation using adjoint Bellman residuals.

2. OPE setup 2.1. MDP and validation data Consider a time-homogeneous Markov decision process with state space S, action space A, transition kernel P (ds′ | s, a), reward R, and discount factor γ ∈ [0, 1). Write X = (S, A) and let r(x) := E[R | X = x] denote the mean reward function. Fix a target policy π(da | s) and an initial state–action distribution d0 , and let Pπ (ds′ , da′ | s, a) := P (ds′ | s, a)π(da′ | Rs′ ) denote the induced state–action transition kernel. For any R ′ state–action function f , define (πf )(s′ ) := f (s′ , a′ ) π(da′ | s′ ) and (P f )(s, a) := (πf )(s ) P (ds′ | s, a). π P ∞ The goal of OPE is to estimate the discounted value V π := Eπ [ t=0 γ t Rt | X0 ∼ d0 ], where Eπ denotes expectation over trajectories generated by the MDP under π and initialized from d0 . 3

For model selection, we use sample splitting. Candidate Q-functions and occupancy-ratio estimates are fitted on a training sample and evaluated on an independent validation sample Dn := {(Xt , Rt , St′ )}nt=1 . We condition on the training sample and assume that (Xt )t≥1 is a stationary Markov chain with invariant offline distribution ν and transition operator (Pb f )(x) := E[f (Xt+1 ) | Xt = x]. This includes trajectories from a stationary behavior policy b(da | s); for independent transitions, (Pb f )(x) = Eν [f (X)]. In both cases, conditional on the observed trajectory history through Xt , the law of (Rt , St′ ) is the one-step MDP law at Xt . For any state–action distribution ρ, square-integrable f, g, and positive integer m, write ⟨f, g⟩ρ := Eρ [f (X)g(X)] and 1/2 ∥f ∥2,ρ := ⟨f, f ⟩ρ , and set [m] := {1, . . . , m}.

2.2. Bellman and adjoint Bellman equations The two nuisance functions we study are the target Q-function and the discounted occupancy ratio. Both can be used to recover the policy value and satisfy P∞ Bellman and adjoint Bellman equations, respectively. The target Q-function is defined by Qπ (x) := Eπ [ t=0 γ t Rt | X0 = x]. It yields the policy value V π = Ed0 [Qπ (X)] and satisfies the Bellman fixed-point equation Qπ = Bπ Qπ ,

Bπ Q := r + γPπ Q,

(1)

where Bπ is the Bellman operator (Sutton and Barto, 1998). The normalized discounted occupancy ratio is wπ :=

ddπ,γ , dν

dπ,γ := (1 − γ)

∞ X

γ t Lπ (Xt ),

X0 ∼ d0 ,

t=0

where Lπ (Xt ) denotes the marginal law of Xt under the target policy. We assume dπ,γ ≪ ν. The ratio yields V π = (1 − γ)−1 Edπ,γ [r(X)] = (1 − γ)−1 Eν [wπ (X)r(X)]. Moreover, wπ satisfies the adjoint Bellman fixed-point equation (van der Laan and Kallus, 2026) Bπ∗ wπ = wπ ,

Bπ∗ w := (1 − γ)

dd0 + γPπ∗ w, dν

Pπ∗ w :=

d{(wν)Pπ } , dν

(2)

which follows from the occupancy identity dπ,γ = (1 − γ)d0 + γdπ,γ Pπ (Nachum et al., 2019). The terminology “adjoint” reflects that Pπ∗ is the adjoint of Pπ under the ν-inner product, so ⟨Pπ∗ w, Q⟩ν = ⟨w, Pπ Q⟩ν (Uehara et al., 2021).

3. Validation for Q-function selection We first motivate pairwise Bellman validation and explain its key ideas before presenting the algorithms in Section 4.

3.1. Limitations of standard validation criteria Let Q1 , . . . , QK be a finite class of candidate Q-functions fitted on the training sample. A natural approach, which we refer to as Bellman-residual validation, selects a candidate by minimizing the mean-squared Bellman residual under the offline distribution ν (Antos et al., 2008; Farahmand and Szepesvári, 2011): LBR (Q) := ∥Q − Bπ Q∥22,ν . Because Qπ is a Bellman fixed point, LBR (Qπ ) = 0, so the minimum over a class containing Qπ is attained at Qπ . The criterion is not directly estimable because (Bπ Q)(X) depends on unknown conditional laws. Without an MDP model, evaluating it generally requires estimating the Bellman residual Qi − Bπ Qi , for example by separately regressing Qi (X) − R − γ(πQi )(S ′ ) on X for each candidate (Zitovsky et al., 2023). This introduces additional computation, tuning, and estimation error. A natural but generally invalid surrogate for Bellman-residual validation is to select candidates based on the squared one-step temporal-difference (TD) error (Sutton, 1988),   LTD (Q) := Eν {Q(X) − R − γ(πQ)(S ′ )}2 , 4

which involves observable TD residuals Q(X) − R − γ(πQ)(S ′ ) and can be estimated directly from held-out transitions. Although the TD residual is conditionally unbiased for the Bellman residual, E[Q(X) − R − γ(πQ)(S ′ ) | X] = Q(X) − (Bπ Q)(X), squaring introduces a conditional-variance term into the objective: LTD (Q) = LBR (Q) + Eν [Var(R + γ(πQ)(S ′ ) | X)] . For γ > 0 and stochastic transitions, this term generally depends on Q, so minimizing squared TD error need not minimize the Bellman-residual error LBR (Q) or select Qπ , even when it belongs to the candidate class (Zitovsky et al., 2023). Directly estimating the squared Bellman residual without this variance term encounters the classical double-sampling obstruction: unbiased estimation generally requires two conditionally independent targets at the same state–action pair (Baird III, 1995; Feng et al., 2019). A natural way around this obstruction is to construct a minimax criterion based on moments of the Bellman residual against critic functions (Antos et al., 2008; Feng et al., 2019; Uehara et al., 2020; Zanette and Wainwright, 2022). Since Qπ is a Bellman fixed point, ⟨f, Qπ − Bπ Qπ ⟩ν = 0 for every suitable critic f . These moments can be estimated directly from one-step transitions because Eν [f (X){Q(X) − R − γ(πQ)(S ′ )}] = ⟨f, Q − Bπ Q⟩ν . Given a critic class F, this motivates the minimax population criterion LF (Q) :=

sup

|Eν [f (X){Q(X) − R − γ(πQ)(S ′ )}]| ,

f ∈F : ∥f ∥2,ν ≤1

which measures the largest violation over the critic class. We refer to model selection based on an empirical analogue of this criterion as minimax moment validation. The empirical criterion replaces the expectation with a validation-sample average and may include additional critic regularization. The main practical challenge is choosing a critic class F for which these moments distinguish among candidate Q-functions. If F contains the normalized Bellman residual (Qi − Bπ Qi )/∥Qi − Bπ Qi ∥2,ν for each i ∈ [K] with nonzero residual, then Cauchy–Schwarz and inclusion of this critic give LF (Qi ) = ∥Qi − Bπ Qi ∥2,ν (Uehara et al., 2021). Thus, minimax moment validation recovers Bellman-residual validation without directly estimating Bπ Qi . The remaining difficulty is constructing, regularizing, and tuning an informative critic class: restrictive classes may fail to distinguish among candidates, whereas richer classes increase statistical and computational complexity (Uehara et al., 2020; Zanette and Wainwright, 2022).

3.2. Key ideas behind pairwise Bellman validation We depart from standard analyses of minimax methods by identifying oracle critics whose moments directly control candidate estimation error, rather than choosing critics to recover or approximate the Bellman-residual error LBR (Qi ). We then show that these critics can be approximated using pairwise differences between candidates. The following three observations motivate the algorithms in Section 4. The first observation is that the candidate estimation error ∆i := Qi − Qπ defines an oracle critic whose Bellman moment is a quadratic form in ∆i . Specifically, L⋆ (Qi ) := Eν [∆i (X) {Qi (X) − R − γ(πQi )(S ′ )}] = ⟨∆i , Qi − Bπ Qi ⟩ν = ⟨∆i , (I − γPπ )∆i ⟩ν , where the final equality follows from the fixed-point identity Bπ Qπ = Qπ . In contrast to squared Bellmanresidual criteria, L⋆ (Qi ) is linear in the Bellman residual and, if ∆i were known, could be estimated directly from one-step transitions without estimating Bπ Qi . If the quadratic form induced by I − γPπ is coercive along the candidate error directions, candidate mean-squared error is bounded by a constant multiple of the oracle criterion. Specifically, suppose that, for some κν > 0 and every i ∈ [K], ⟨∆i , (I − γPπ )∆i ⟩ν ≥ κν ∥∆i ∥22,ν . (3) An upper bound follows under the standard one-step concentrability condition Cν,π := ∥d(νPπ )/dν∥∞ < ∞. By Cauchy–Schwarz and Jensen’s inequality, for every i ∈ [K], p ⟨∆i , (I − γPπ )∆i ⟩ν ≤ (1 + γ Cν,π )∥∆i ∥22,ν . 5

Consequently, under coercivity and one-step concentrability, L⋆ (Qi ) is comparable to ∥∆i ∥22,ν up to constant factors. It follows that any oracle selector i⋆oracle ∈ arg min1≤i≤K L⋆ (Qi ) satisfies !1/2 p 1 + γ Cν,π π min ∥Qi − Qπ ∥2,ν . ∥Qi⋆oracle − Q ∥2,ν ≤ 1≤i≤K κν The second observation is that pairwise differences between candidate Q-functions provide approximations to the unavailable oracle critics. Indeed, for any j ∈ [K], Qi − Qj = ∆i − ∆j . Under realizability, some Qi⋆ = Qπ , so Qi − Qi⋆ = ∆i exactly. More generally, Qi − Qj differs from the oracle critic ∆i by −∆j , so a comparison candidate close to Qπ provides an accurate approximation. Because the best comparison candidate is unknown, we evaluate the Bellman residual of each Qi against all K pairwise critics and take the largest resulting moment as its worst-case score. These K 2 comparisons require no auxiliary critic fitting. Specifically, define the population unweighted PBV moments munw := Eν [(Qi − Qj )(X) {Qi (X) − R − γ(πQi )(S ′ )}] , ij and the corresponding unpenalized population selector arg mini∈[K] maxj∈[K] munw ij . Under realizability, Qi⋆ = Qπ has a worst-case score of zero. For any candidate Qi , comparison with Qi⋆ and coercivity imply that its worst-case score is at least κν ∥∆i ∥22,ν . Consequently, the population selector recovers Qπ in L2 (ν). In the next section, we introduce a penalized empirical version that accounts for critic approximation error under misspecification. The error guarantees for unweighted PBV, however, rely on coercivity under the offline distribution ν, as in (3). This condition depends on the relationship between the offline distribution and the target-policy dynamics. A simple sufficient condition is ∥Pπ ∆i ∥2,ν ≤ c∥∆i ∥2,ν for every i ∈ [K] and some c < γ −1 , inpwhich case Cauchy–Schwarz gives (3) with κν = 1 − γc. Under one-step concentrability, one may take c = Cν,π , so coercivity holds whenever Cν,π < γ −2 . In particular, under stationary on-policy sampling, Cν,π = 1 and Pπ is an L2 (ν) contraction, so coercivity holds automatically with κν = 1 − γ. When Qπ and the candidate Q-functions lie in a common linear span, this condition is analogous to matrix-conditioning assumptions in linear TD learning (Amortila et al., 2026; Bradtke and Barto, 1996; Lagoudakis and Parr, 2003; Tsitsiklis and Van Roy, 1997). Under a general offline distribution, however, coercivity need not hold. The third observation is that the coercivity requirement can be removed by marginalized importance weighting each moment by wπ = ddπ,γ /dν. This allows the pairwise Bellman moments to be evaluated under √ the discounted target-occupancy distribution, with respect to which γPπ is a γ-contraction in L2 (dπ,γ ) (van der Laan and Kallus, 2025), and hence √ √ (1 − γ)∥∆i ∥22,dπ,γ ≤ ⟨∆i , (I − γPπ )∆i ⟩dπ,γ ≤ (1 + γ)∥∆i ∥22,dπ,γ . (4) The weighted oracle criterion is therefore comparable, up to constants, to mean-squared Q-function error under the discounted target occupancy, without requiring (3). The tradeoff is that the occupancy ratio wπ must be estimated sufficiently accurately, introducing an additional model-selection problem that we address in the next section. Combining target-occupancy weighting with pairwise difference critics yields our target-aligned PBV criterion. For candidate i and comparator j, let hij := Qi − Qj and define the target-aligned pairwise moment π ′ mTA ij := Eν [w (X)hij (X) {Qi (X) − R − γ(πQi )(S )}] = ⟨hij , Qi − Bπ Qi ⟩dπ,γ .

As with unweighted PBV, we select the candidate minimizing the worst-case population moment maxj∈[K] mTA ij . Under realizability, this criterion recovers Qπ in L2 (dπ,γ ), since the oracle critic is among the pairwise differences and the contraction property provides the required error bound without coercivity under the offline distribution.

4. Pairwise Bellman validation algorithms We now develop empirical Q-function selectors based on the population constructions in Section 3.2, along with A-PBV for occupancy-ratio selection. Under candidate-class misspecification, even the best candidate 6

may have a nonzero Bellman residual, and comparisons with distant candidates can produce large unpenalized moments. Without penalization, the selected candidate can have arbitrarily larger error than the best candidate (Proposition S24). To prevent these comparisons from dominating the worst-case score, we penalize each pairwise Bellman moment by a suitable squared-discrepancy term.

4.1. Unweighted PBV Let hij := Qi − Qj and define the unweighted PBV scores and selector by n X cunw := 1 M hij (Xt ){Qi (Xt ) − Rt − γ(πQi )(St′ )} ij n t=1 ( ) n 1 1X ′ − max 0, hij (Xt ){hij (Xt ) − γ(πhij )(St )} , 4 n t=1

biunw := min arg min Q

cunw , max M ij

1≤i≤K 1≤j≤K

(5)

where both the moments and their penalties are evaluated under the offline distribution. By iterated expectation, the population counterpart of the untruncated penalty is 14 ⟨hij , (I − γPπ )hij ⟩ν , which is bounded below by 14 κν ∥hij ∥22,ν under coercivity along the pairwise differences. Using the quadratic form rather than its coercivity lower bound avoids the need to know κν . The quadratic penalty can be multiplied by any coefficient λ ∈ (0, 1); λ = 1/4 minimizes the population upper bound derived in our analysis. Because unweighted PBV does not require estimating an occupancy ratio, it may be preferable when reliable importance weighting is difficult.

4.2. Adjoint PBV and target-aligned PBV To implement TA-PBV, we first introduce adjoint PBV (A-PBV), which applies pairwise validation to the adjoint Bellman equation to select an occupancy-ratio estimate. We summarize the construction here and defer further details and intuition to Appendix A. As in the Q-function case, adjoint Bellman moments for fixed critics can be estimated directly from one-step transitions and independent draws from d0 (Nachum et al., 2019). For nonnegative integrable functions p and q, define the generalized KL divergence   p(X) Dν (p∥q) := Eν p(X) log − p(X) + q(X) . q(X) Unlike the usual KL divergence, Dν does not require p and q to integrate to one and therefore permits √ √ unnormalized ratio candidates. Write Hν (p, q) := ∥ p − q∥2,ν . When the three divergences below are finite, the Bregman three-point identity (Bauschke and Combettes, 2017), together with contraction of the adjoint Bellman operator in generalized KL divergence (van der Laan and Kallus, 2026), gives ⟨w − Bπ∗ w, log(w/wπ )⟩ν = Dν (w∥wπ ) − Dν (Bπ∗ w∥wπ ) + Dν (Bπ∗ w∥w) ≥ (1 − γ)Dν (w∥wπ ). Thus, the oracle critic is log(w/wπ ). Given M candidate occupancy ratios w1 , . . . , wM , we approximate this critic using pairwise log ratios ℓab := log(wa /wb ) and select an occupancy-ratio candidate using the resulting adjoint Bellman moments. As in unweighted PBV, we account for critic-approximation error under misspecification by penalizing the pairwise moments. We use Hellinger and Bellman quadratic penalties for A-PBV and TA-PBV, respectively. Let X0,1 , . . . , X0,n be independent draws from d0 . If expectations under d0 are known, we may replace the

7

corresponding empirical averages by their population values. Define the penalized empirical pairwise scores n n 1−γ X 1X adj ′ b wa (Xt ){ℓab (Xt ) − γ(πℓab )(St )} − ℓab (X0,t ) Sab := n t=1 n t=1 n

−

p 1−γ X p { wa (Xt ) − wb (Xt )}2 , 4n t=1

n 1X cTA w(Xt )hij (Xt ){Qi (Xt ) − Rt − γ(πQi )(St′ )} M (w) := ij n t=1 ( ) n 1X 1 w(Xt )hij (Xt ){hij (Xt ) − γ(πhij )(St′ )} . − max 0, 4 n t=1

The Q-function penalty uses the same quadratic form as unweighted PBV, evaluated under the fitted occupancy ratio. This choice yields an oracle inequality without requiring candidate-class realizability. We combine the two stages in Algorithm 1, evaluating M 2 + K 2 pairwise scores without fitting auxiliary validation models or critics.

Algorithm 1 Adjoint and target-aligned pairwise Bellman validation Require: Ratio candidates w1 , . . . , wM ; Q-function candidates Q1 , . . . , QK ; validation trajectory Dn ; independent draws X0,1 , . . . , X0,n ∼ d0 (or exact d0 moments); discount factor γ adj b := wbi . 1: Select b iw as the smallest index in arg min1≤a≤M max1≤b≤M Sbab and set w w cTA (w) b := Q . b and set Q 2: Select b iQ as the smallest index in arg min1≤i≤K max1≤j≤K M ij bi Q

b b Q). 3: return (w,

5. Finite-sample guarantees We establish finite-sample oracle inequalities for unweighted PBV and the two-stage procedure combining A-PBV and TA-PBV. To accommodate temporal dependence in the validation trajectory, we impose the following spectral-gap condition, which holds with gb = 1 for independent transitions (Jiang et al., 2025). (A1) Behavior-process spectral gap. There exists gb ∈ (0, 1] such that ∥Pb f ∥2,ν ≤ (1 − gb )∥f ∥2,ν

for every real-valued f ∈ L2 (ν) with Eν f = 0.

(6)

Alternatively, Pb is self-adjoint in L2 (ν) and ⟨f, Pb f ⟩ν ≤ (1 − gb )∥f ∥22,ν for every such f .

5.1. Unweighted PBV In unweighted PBV, we avoid occupancy-ratio estimation but require coercivity along candidate comparisons under the offline distribution. Let k ⋆ ∈ arg mini∈[K] ∥Qi − Qπ ∥2,ν index a best candidate. (A2) Pairwise coercivity. There exists a constant κν ∈ (0, 1] such that ⟨hik⋆ , (I − γPπ )hik⋆ ⟩ν ≥ κν ∥hik⋆ ∥22,ν

for every i ∈ [K].

Theorem 5.1 (Unweighted PBV oracle guarantee). Suppose Conditions A1, A2, B2, B3, and B5 hold. Then there exists a finite constant CQ,unw > 0, depending only on HQ , GQ , σQ , such that, for every δ ∈ (0, 1), with probability at least 1 − δ, s 2 C log(12K/δ) Q,unw ∥Qbiunw − Qπ ∥2,ν ≤ ∥Qk⋆ − Qπ ∥2,ν + ∥Qk⋆ − Bπ Qk⋆ ∥2,ν + . Q κν κν ngb

8

If, for some Lν ∈ [0, ∞), ∥Qk⋆ − Bπ Qk⋆ ∥2,ν ≤ Lν ∥Qk⋆ − Qπ ∥2,ν , the theorem gives the oracle inequality s   CQ,unw log(12K/δ) 2Lν π π min ∥Qi − Q ∥2,ν + . ∥Qbiunw − Q ∥2,ν ≤ 1 + Q κν i∈[K] κν ngb p One-step concentrability is sufficient, with Lν = 1 + γ Cν,π . Temporal dependence reduces the effective validation sample size from n to ngb , while dependence on the candidate class size is only logarithmic.

5.2. Adjoint PBV and target-aligned PBV We next establish guarantees for the two-stage procedure, which estimates the discounted occupancy ratio to avoid requiring coercivity under the offline distribution. For A-PBV, we impose the following condition to ensure uniform boundedness of the pairwise log-ratio critics. (A3) One-step coverage and bounded ratio candidates. The measures d0 and νPπ are absolutely continuous with respect to ν. There are constants w < ∞ and Cw ≥ 1 such that, ν-almost surely, 0 < wa ≤ w

(a ∈ [M ]),

−1 Cw ≤

wi ≤ Cw wj

(i, j ∈ [M ]).

Theorem 5.2 (A-PBV and TA-PBV oracle guarantee). Suppose Conditions A1 and A3 hold, together with the technical conditions in Appendix B.1. Then there exist finite constants Cratio , CTA > 0, independent of n, M, K, δ, and γ, such that, for every δ ∈ (0, 1), with probability at least 1 − δ, the output of Algorithm 1 satisfies s ( ) log(48M/δ) Cratio min Hν (wa , wπ ) + . 1 − γ a∈[M ] ngb s " π min ∥Q − Q ∥ 1 log(24M K/δ) i 2,d i∈[K] π,γ b − Qπ ∥2,d ≤ CTA √ + ∥Q π,γ 1−γ ngb 1−γ s ( )# 1 log(48M/δ) π + min Hν (wa , w ) + . ngb (1 − γ)3/2 a∈[M ] Hν (w, b wπ ) ≤

(7)

(8)

Unlike unweighted PBV, we obtain a Q-function error guarantee without requiring coercivity under the offline distribution. We obtain separate terms for candidate approximation and validation error and for error due to occupancy-ratio estimation. The horizon dependence is (1 − γ)−1/2 for Q-function approximation, (1 − γ)−1 for direct validation error, and (1 − γ)−3/2 for the terms due to occupancy-ratio error. Under the corresponding moment conditions, pairwise coercivity under the fitted measure wν b instead yields an oracle bound in L2 (wν) b analogous to that for unweighted PBV, with weighted approximation, comparator Bellman-residual, and validation errors but no separate occupancy-ratio estimation-error term. π b b For Q-functions, Cauchy–Schwarz gives the plug-in value bound |Ed0 [Q(X)]−V | ≤ ∥dd0 /ddπ,γ ∥2,dπ,γ ∥Q− π 2 Q ∥2,dπ,γ , where the Q-function error is bounded in (8). For occupancy ratios, if r ∈ L (ν) ∩ b − V π ≤ (1 − γ)−1 {2w∥r∥22,ν + L2 (dπ,γ ), the analogous plug-in estimator satisfies (1 − γ)−1 Eν [w(X)r(X)] 2 1/2 π 2∥r∥2,dπ,γ } Hν (w, b w ), where the Hellinger error is bounded in (7). A doubly robust bound is given in Appendix C.

6. Experimental investigation We evaluate PBV on Hopper (Liu et al., 2025) and Deep OPE/D4RL (Fu et al., 2020, 2021). We compare unweighted PBV, its variant without the quadratic penalty, TA-PBV, squared temporal-difference (TD) error, and LSTD-Tournament using the normalized-difference implementation of Liu et al. (2025). We consider both the original benchmarks and controlled-overlap benchmarks constructed to examine target-occupancy weighting when overlap is favorable. In the controlled-overlap benchmarks, the logging policy samples one benchmark policy uniformly for each trajectory, and each component policy is treated in turn as the target. 9

Thus, the expected on-policy fraction is 1/10 for Hopper and 1/11 for Deep OPE, and the corresponding trajectory and discounted occupancy ratios are bounded by 10 and 11, respectively. Each Q-class contains 15 candidates. For the original Hopper benchmark, we use the candidates provided with the benchmark; for Deep OPE and controlled-overlap Hopper, we use two-hidden-layer neural FQE networks with widths 64, 128, or 256, saved after 50, 100, 200, 400, or 800 FQE iterations. For TA-PBV (T = 5), A-PBV first selects among 28 ratio candidates obtained by fitted occupancy-ratio evaluation (FORE). The selected ratio is then used to select a Q-function on an independent validation sample of nQ = 3,200 transitions. Following Sinha et al. (2022), we temper the selected ratio as w1/5 /Pn,w [w1/5 ] to reduce weight variance and improve stability. Sensitivity analyses, uncertainty intervals, and additional experimental details are given in Appendix D. Table 1: Selected-Q performance at nQ = 3,200 (lower is better). Absolute policy-value error is the primary metric. Initial-state value RMSE is the square root of the mean estimated state-value MSE under the reset-state law. Both metrics average over settings and validation resamples. Bold marks the smallest displayed mean within each setting, benchmark, and metric.

Absolute value error Initial-state value RMSE

Setting

Selector

Original

Unweighted PBV Unweighted PBV (no penalty) TA-PBV (T = 5) LSTD-Tournament Squared TD error

4.2 4.8 5.2 5.6 9.4

265.6 265.1 262.1 258.8 276.2

9.4 9.5 10.7 11.4 17.6

350.2 350.1 347.3 341.4 363.4

Unweighted PBV Unweighted PBV (no penalty) Controlled overlap TA-PBV (T = 5) LSTD-Tournament Squared TD error

15.4 15.1 14.2 15.9 15.5

70.1 75.9 65.1 74.7 177.8

25.9 25.1 21.3 34.0 22.8

139.3 144.1 127.0 142.9 300.6

Hopper

Deep OPE Hopper

Deep OPE

On the original benchmarks, unweighted PBV has the lowest mean value error on Hopper, while LSTDTournament performs best on Deep OPE (Table 1). The paired mean differences in absolute value error between unweighted PBV and LSTD-Tournament are −1.41 (90% bootstrap interval [−2.66, −0.37]) on Hopper and 6.81 ([−19.37, 31.80]) on Deep OPE. Relative to unweighted PBV, the corresponding differences for TA-PBV are 1.07 ([0.14, 2.43]) on Hopper and −3.55 ([−9.98, 2.88]) on Deep OPE (Table S2). Performance varies across policies, as shown in Figures S1 and S2. On the controlled-overlap benchmarks, TA-PBV achieves the lowest mean value error on both Hopper and Deep OPE (Table 1). Relative to unweighted PBV, its paired mean differences are −1.20 (90% bootstrap interval [−5.83, 2.69]) on Hopper and −4.95 ([−14.40, 1.54]) on Deep OPE. Its mean errors are also lower than those of LSTD-Tournament, although all four bootstrap intervals for comparisons involving TA-PBV include zero (Table S2). The policy-level differences vary across settings (Figures S1 and S2). TA-PBV has the lowest mean initial-state value RMSE on both benchmarks.

7. Discussion The competitive performance of PBV and LSTD-Tournament (Liu et al., 2025) suggests that candidateinduced critics provide an effective approach to offline model selection. We recommend unweighted PBV and TA-PBV with tempered ratios as practical choices. Unweighted PBV requires no occupancy-ratio estimation. Its oracle inequality allows candidate-class misspecification but requires pairwise coercivity under the offline distribution. TA-PBV avoids this requirement through target-occupancy weighting, at the cost of occupancy-ratio estimation, and can provide additional gains when overlap is favorable. 10

AI use statement Generative AI tools were used to assist with manuscript drafting and editing, as well as reviewing and checking mathematical proofs. The authors independently verified all mathematical arguments and take full responsibility for the paper.

References Felix Abramovich, Daniela De Canditiis, and Marianna Pensky. Solution of linear ill-posed problems by model selection and aggregation. Electronic Journal of Statistics, 12(1):1822–1841, 2018. doi: 10.1214/18-EJS1447. URL https://doi.org/10.1214/18-EJS1447. Shun-ichi Amari and Hiroshi Nagaoka. Methods of Information Geometry, volume 191 of Translations of Mathematical Monographs. American Mathematical Society and Oxford University Press, 2000. doi: 10.1090/mmono/191. URL https://doi.org/10.1090/mmono/191. Philip Amortila, Audrey Huang, Akshay Krishnamurthy, and Nan Jiang. A unifying view of coverage in linear off-policy evaluation. In International Conference on Learning Representations, 2026. URL https://proceedings.iclr.cc/paper_files/paper/2026/hash/858e773f5c99a4186b548f3f531fb0 7e-Abstract-Conference.html. András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 71(1):89–129, 2008. doi: 10.1007/s10994-007-5038-2. URL https://doi.org/10.1007/s10994-007-5038-2. Leemon C. Baird III. Residual algorithms: Reinforcement learning with function approximation. In Armand Prieditis and Stuart J. Russell, editors, Machine Learning Proceedings 1995, pages 30–37. Morgan Kaufmann, 1995. doi: 10.1016/B978-1-55860-377-6.50013-X. URL https://doi.org/10.1016/B978-1-55860-377 -6.50013-X. Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Springer, Cham, 2 edition, 2017. doi: 10.1007/978-3-319-48311-5. URL https://doi.org/10.1007/978-3-319-48311-5. Steven J. Bradtke and Andrew G. Barto. Linear least-squares algorithms for temporal difference learning. Machine Learning, 22(1–3):33–57, 1996. doi: 10.1007/BF00114723. URL https://doi.org/10.1007/BF 00114723. L. Cavalier, G. K. Golubev, D. Picard, and A. B. Tsybakov. Oracle inequalities for inverse problems. The Annals of Statistics, 30(3):843–874, 2002. doi: 10.1214/aos/1028674843. URL https://doi.org/10.121 4/aos/1028674843. Matej Cief, Branislav Kveton, and Michal Kompan. Cross-validated off-policy evaluation. Proceedings of the AAAI Conference on Artificial Intelligence, 39(15):16073–16081, 2025. doi: 10.1609/aaai.v39i15.33765. URL https://ojs.aaai.org/index.php/AAAI/article/view/33765. Dong Dai, Philippe Rigollet, and Tong Zhang. Deviation optimal learning using greedy Q-aggregation. The Annals of Statistics, 40(3):1878–1905, 2012. doi: 10.1214/12-AOS1025. URL https://doi.org/10.1214/ 12-AOS1025. Victor H. de la Peña. A general class of exponential inequalities for martingales and ratios. The Annals of Probability, 27(1):537–564, 1999. doi: 10.1214/aop/1022677271. URL https://doi.org/10.1214/aop/10 22677271. Amir-massoud Farahmand and Csaba Szepesvári. Model selection in reinforcement learning. Machine Learning, 85(3):299–332, 2011. doi: 10.1007/s10994-011-5254-7. URL https://doi.org/10.1007/s10994 -011-5254-7. 11

Yihao Feng, Lihong Li, and Qiang Liu. A kernel loss for solving the bellman equation. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings. neurips.cc/paper/2019/hash/48e59000d7dfcf6c1d96ce4a603ed738-Abstract.html. David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975. doi: 10.1214/aop/1176996452. URL https://doi.org/10.1214/aop/1176996452. Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4RL: datasets for deep data-driven reinforcement learning. CoRR, abs/2004.07219, 2020. URL https://arxiv.org/abs/2004.07219. Justin Fu, Mohammad Norouzi, Ofir Nachum, George Tucker, Ziyu Wang, Alexander Novikov, Mengjiao Yang, Michael R. Zhang, Yutian Chen, Aviral Kumar, Cosmin Paduraru, Sergey Levine, and Tom Le Paine. Benchmarks for deep off-policy evaluation. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=kWSeGEeHvF8. Audrey Huang and Nan Jiang. Occupancy-based policy gradient: Estimation, convergence, and optimality. In Advances in Neural Information Processing Systems, 2024. URL https://proceedings.neurips.cc /paper_files/paper/2024/file/010c855df402b443e0c16e5b7434e74c-Paper-Conference.pdf. Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforcement learning in low-rank MDPs with density features. In International Conference on Machine Learning, pages 13710–13752, 2023. URL https: //proceedings.mlr.press/v202/huang23a.html. Alexander Irpan, Kanishka Rao, Konstantinos Bousmalis, Chris Harris, Julian Ibarz, and Sergey Levine. Off-policy evaluation via off-policy classification. In Advances in Neural Information Processing Systems, volume 32, pages 5438–5449, 2019. URL https://proceedings.neurips.cc/paper/2019/hash/b5b03 f06271f8917685d14cea7c6c50a-Abstract.html. Bai Jiang, Qiang Sun, and Jianqing Fan. Bernstein’s inequalities for general markov chains. arXiv preprint arXiv:1805.10721v4, 2025. URL https://arxiv.org/abs/1805.10721v4. Nan Jiang and Lihong Li. Doubly robust off-policy value evaluation for reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 652–661, New York, New York, USA, 20–22 Jun 2016. PMLR. URL https://proceedings.mlr.press/v48/jiang16.html. Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient off-policy evaluation in markov decision processes. Journal of Machine Learning Research, 21(167):1–63, 2020. URL http: //jmlr.org/papers/v21/19-827.html. Nathan Kallus and Masatoshi Uehara. Efficiently breaking the curse of horizon in off-policy evaluation with double reinforcement learning. Oper. Res., 70(6):3282–3302, 2022. doi: 10.1287/OPRE.2021.2249. URL https://doi.org/10.1287/opre.2021.2249. Michail G. Lagoudakis and Ronald Parr. Least-squares policy iteration. J. Mach. Learn. Res., 4:1107–1149, 2003. URL https://jmlr.org/papers/v4/lagoudakis03a.html. Hui Lan and Vasilis Syrgkanis. Causal Q-aggregation for CATE model selection. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pages 4366–4374. PMLR, 2024. URL https://proceedings.mlr.press/v238/lan24 a.html. Jonathan N. Lee, George Tucker, Ofir Nachum, Bo Dai, and Emma Brunskill. Oracle inequalities for model selection in offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 35, pages 28194–28207, 2022. doi: 10.52202/068431-2044. URL https://proceedings.neurips.cc/paper_f iles/paper/2022/hash/b51693c2ba5b5ddf67429966576fb962-Abstract-Conference.html. 12

Zihao Li, Hui Lan, Vasilis Syrgkanis, Mengdi Wang, and Masatoshi Uehara. Regularized DeepIV with model selection. arXiv preprint arXiv:2403.04236, 2024. URL https://arxiv.org/abs/2403.04236. 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. In Advances in Neural Information Processing Systems, volume 38, 2025. URL https://papers.neurips.cc/paper_files/pa per/2025/hash/3d4dc72d715bd6415d356293079adf3d-Abstract-Conference.html. Kohei Miyaguchi. Duality-based residual estimation for fully offline value-based reinforcement learning. In Emtiyaz Khan, Yingzhen Li, Arno Solin, and Aaditya Ramdas, editors, Proceedings of the 29th International Conference on Artificial Intelligence and Statistics, volume 300 of Proceedings of Machine Learning Research, pages 1576–1584. PMLR, 02–05 May 2026. URL https://proceedings.mlr.press/v300/miyaguchi26 a.html. Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(27):815–857, 2008. URL http://jmlr.org/papers/v9/munos08a.html. Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/cf9a242b70f45 317ffd281241fa66502-Paper.pdf. Allen Nie, Yannis Flet-Berliac, Deon R. Jordan, William Steenbergen, and Emma Brunskill. Data-efficient pipeline for offline reinforcement learning with limited data. In Advances in Neural Information Processing Systems, volume 35, pages 14810–14823, 2022. doi: 10.52202/068431-1077. URL https://proceedings. neurips.cc/paper_files/paper/2022/hash/5ee7ed60a7e8169012224dec5fe0d27f-Abstract-Confe rence.html. Allen Nie, Yash Chandak, Christina J. Yuan, Anirudhan Badrinath, Yannis Flet-Berliac, and Emma Brunskill. OPERA: Automatic offline policy evaluation with re-weighted aggregates of multiple estimators. In Advances in Neural Information Processing Systems, volume 37, pages 103652–103680, 2024. doi: 10.52202 /079017-3292. URL https://proceedings.neurips.cc/paper_files/paper/2024/hash/bba9be4bc52 6c5d515a9d3c16ccfe138-Abstract-Conference.html. Tom Le Paine, Cosmin Paduraru, Andrea Michi, Caglar Gulcehre, Konrad Zolna, Alexander Novikov, Ziyu Wang, and Nando de Freitas. Hyperparameter selection for offline reinforcement learning. arXiv preprint arXiv:2007.09055, 2020. URL https://arxiv.org/abs/2007.09055. Samarth Sinha, Jiaming Song, Animesh Garg, and Stefano Ermon. Experience replay with likelihood-free importance weights. In Proceedings of the 4th Annual Learning for Dynamics and Control Conference, volume 168 of Proceedings of Machine Learning Research, pages 110–123. PMLR, 2022. URL https: //proceedings.mlr.press/v168/sinha22a.html. M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society: Series B (Methodological), 36(2):111–133, 1974. doi: 10.1111/j.2517-6161.1974.tb00994.x. URL https://doi.org/10.1111/j.2517-6161.1974.tb00994.x. Yi Su, Maria Dimakopoulou, Akshay Krishnamurthy, and Miroslav Dudík. Doubly robust off-policy evaluation with shrinkage. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9167–9176. PMLR, 2020a. URL https://proceedings. mlr.press/v119/su20a.html. Yi Su, Pavithra Srinath, and Akshay Krishnamurthy. Adaptive estimator selection for off-policy evaluation. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of 13

Machine Learning Research, pages 9196–9205. PMLR, 2020b. URL https://proceedings.mlr.press/v1 19/su20d.html. Richard S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3(1):9–44, 1988. doi: 10.1007/BF00115009. URL https://doi.org/10.1007/BF00115009. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 1998. ISBN 9780262193986. URL https://mitpress.mit.edu/9780262193986/reinforcement-l earning/. Shengpu Tang and Jenna Wiens. Model selection for offline reinforcement learning: Practical considerations for healthcare settings. In Proceedings of the 6th Machine Learning for Healthcare Conference, volume 149 of Proceedings of Machine Learning Research, pages 2–35. PMLR, 2021. URL https://proceedings.mlr. press/v149/tang21a.html. Philip Thomas and Emma Brunskill. Data-efficient off-policy policy evaluation for reinforcement learning. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2139–2148, New York, New York, USA, 20–22 Jun 2016. PMLR. URL https://proceedings.mlr.press/v48/thomasa16.html. John N. Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674–690, 1997. doi: 10.1109/9.580874. URL https://doi.org/10.1109/9.580874. Takuma Udagawa, Haruka Kiyohara, Yusuke Narita, Yuta Saito, and Kei Tateno. Policy-adaptive estimator selection for off-policy evaluation. Proceedings of the AAAI Conference on Artificial Intelligence, 37(8): 10025–10033, 2023. doi: 10.1609/aaai.v37i8.26195. URL https://ojs.aaai.org/index.php/AAAI/arti cle/view/26195. Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for off-policy evaluation. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9659–9668. PMLR, 13–18 Jul 2020. URL https://proceedings.mlr.press/v119/uehara20a.html. Masatoshi Uehara, Masaaki Imaizumi, Nan Jiang, Nathan Kallus, Wen Sun, and Tengyang Xie. Finite sample analysis of minimax offline reinforcement learning: Completeness, fast rates and first-order efficiency. CoRR, abs/2102.02981, 2021. URL https://arxiv.org/abs/2102.02981. Masatoshi Uehara, Chengchun Shi, and Nathan Kallus. A review of off-policy evaluation in reinforcement learning. Statistical Science, 41(3):561–581, 2026. doi: 10.1214/25-STS985. URL https://doi.org/10.1 214/25-STS985. Lars van der Laan and Nathan Kallus. Fitted Q-evaluation without Bellman completeness via occupancy weighting. CoRR, abs/2512.23805, 2025. doi: 10.48550/ARXIV.2512.23805. URL https://doi.org/10.4 8550/arXiv.2512.23805. Lars van der Laan and Nathan Kallus. Fitted occupancy-ratio evaluation without bellman completeness. arXiv preprint arXiv:2607.05375, 2026. doi: 10.48550/arXiv.2607.05375. URL https://arxiv.org/abs/ 2607.05375. Lars van der Laan, David Hubbard, Allen Tran, Nathan Kallus, and Aurélien Bibaut. Semiparametric double reinforcement learning with applications to long-term causal inference. arXiv preprint arXiv:2501.06926, 2025. doi: 10.48550/arXiv.2501.06926. URL https://arxiv.org/abs/2501.06926.

14

Mark J. van der Laan and Sandrine Dudoit. Unified cross-validation methodology for selection among estimators and a general cross-validated adaptive epsilon-net estimator: Finite sample oracle inequalities and examples. Working Paper 130, Division of Biostatistics, University of California, Berkeley, November 2003. URL https://biostats.bepress.com/ucbbiostat/paper130/. Mark J. van der Laan, Eric C. Polley, and Alan E. Hubbard. Super learner. Statistical Applications in Genetics and Molecular Biology, 6(1):Article 25, 2007. doi: 10.2202/1544-6115.1309. URL https: //doi.org/10.2202/1544-6115.1309. Yu-Xiang Wang, Alekh Agarwal, and Miroslav Dudík. Optimal and adaptive off-policy evaluation in contextual bandits. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3589–3597. PMLR, 2017. URL https://proceedings.mlr.press/ v70/wang17a.html. David H. Wolpert. Stacked generalization. Neural Networks, 5(2):241–259, 1992. doi: 10.1016/S0893-6080(05 )80023-1. URL https://doi.org/10.1016/S0893-6080(05)80023-1. Tengyang Xie and Nan Jiang. Batch value-function approximation with only realizability. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 11404–11413. PMLR, 2021. URL https://proceedings.mlr.press/v139/xie21d.html. Tengyang Xie, Yifei Ma, and Yu-Xiang Wang. Towards optimal off-policy evaluation for reinforcement learning with marginalized importance sampling. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/4ffb0 d2ba92f664c2281970110a2e071-Paper.pdf. Mengjiao Yang, Bo Dai, Ofir Nachum, George Tucker, and Dale Schuurmans. Offline policy selection under uncertainty. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 4376–4396. PMLR, 2022. URL https://proceedings.mlr.press/v151/yang22a.html. Andrea Zanette and Martin J. Wainwright. Bellman residual orthogonalization for offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 35, pages 3137–3151, 2022. doi: 10.52202/068431-0227. URL https://proceedings.neurips.cc/paper_files/paper/2022/hash/14e cbfb2216bab76195b60bfac7efb1f-Abstract-Conference.html. Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. GenDICE: Generalized offline estimation of stationary values. In International Conference on Learning Representations, 2020. URL https://openreview.net/f orum?id=HkxlcnVFwB. Siyuan Zhang and Nan Jiang. Towards hyperparameter-free policy selection for offline reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 12864–12875, 2021. URL https:// proceedings.neurips.cc/paper/2021/hash/6add07cf50424b14fdf649da87843d01-Abstract.html. Joshua P. Zitovsky, Daniel De Marchi, Rishabh Agarwal, and Michael Rene Kosorok. Revisiting Bellman errors for offline model selection. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 43369–43406. PMLR, 2023. URL https://proceedings.mlr.press/v202/zitovsky23a.html.

15

A. Adjoint PBV for occupancy-ratio selection The first stage of Algorithm 1 selects the discounted occupancy ratio used by its TA-PBV stage. We consider a finite class of candidates w1 , . . . , wM fitted on the training sample and, conditional on that sample, treat them as fixed and independent of the validation data. As in the Q-function setting, we use a minimax criterion based on adjoint Bellman moments and construct the critics directly from the candidate class. (C1) Target-relative support and comparability. Let X π := {x : wπ (x) > 0}. Each candidate satisfies wi = 0 ν-almost surely on (X π )c , and there exists Λw ≥ 1 such that Λ−1 w ≤

wi (X) ≤ Λw wπ (X)

ν-almost surely on X π ,

i = 1, . . . , M.

A.1. From oracle log-ratio critics to pairwise selection For every bounded critic f , the adjoint Bellman residual satisfies the moment identity (Nachum et al., 2019) Eν [{w(X) − (Bπ∗ w)(X)}f (X)] = Eν [w(X){f (X) − γ(πf )(S ′ )}] − (1 − γ)Ed0 [f (X)].

(S1)

In particular, this moment vanishes at w = wπ for every bounded critic f . We measure occupancy-ratio error using the generalized Kullback–Leibler divergence, defined for nonnegative integrable functions p and q by   p(X) − p(X) + q(X) . (S2) Dν (p∥q) := Eν p(X) log q(X) Unlike the standard KL divergence, Dν does not require p and q to integrate to one and therefore accommodates unnormalized candidates. We use 0 log(0/q) = 0 and p log(p/0) = +∞ for p > 0. The adjoint Bellman operator is a contraction in generalized KL divergence (van der Laan and Kallus, 2026): Dν (Bπ∗ w∥wπ ) ≤ γDν (w∥wπ ).

(S3)

We therefore seek a critic whose adjoint Bellman moment directly controls generalized-KL error. In the Q-function case, pairing the Bellman residual with Q − Qπ yields a criterion comparable to squared L2 error. For occupancy ratios, the relevant error is generalized KL, which is the Bregman divergence generated pointwise by ϕ(u) = u log u − u: Dν (p∥q) = Eν [ϕ{p(X)} − ϕ{q(X)} − ϕ′ {q(X)}{p(X) − q(X)}] , where ϕ′ (u) = log u is the corresponding dual coordinate (Amari and Nagaoka, 2000). The natural analogue of the Q-function error is therefore the dual-coordinate error ϕ′ {w(X)} − ϕ′ {wπ (X)} = log{w(X)/wπ (X)}. By the Bregman three-point identity (Bauschke and Combettes, 2017), Eν [{w(X) − (Bπ∗ w)(X)}{ϕ′ (w(X)) − ϕ′ (wπ (X))}] = Dν (w∥wπ ) − Dν (Bπ∗ w∥wπ ) + Dν (Bπ∗ w∥w) ≥ Dν (w∥wπ ) − Dν (Bπ∗ w∥wπ ). By this inequality and the contraction property of Bπ∗ in (S3), Eν [{w(X) − (Bπ∗ w)(X)} log{w(X)/wπ (X)}] ≥ (1 − γ)Dν (w∥wπ ). This motivates the oracle criterion       w  ′ w(X) w(X) ⋆ − γ π log π (S ) − (1 − γ)Ed0 log π , S (w) := Eν w(X) log π w (X) w w (X)

(S4)

which, by (S1), directly controls generalized-KL error. Unlike in the Q-function case, the adjoint contraction holds under the offline law ν, so no distributional correction or additional coercivity condition is required. Under Condition C1, the pairwise log-ratio critics satisfy |log{wi (X)/wj (X)}| ≤ 2 log Λw ν-almost surely for every i, j ∈ [M ]. Under this boundedness, the following two-sided comparison holds. 16

Lemma S1 (Oracle log-ratio equivalence). Suppose Condition C1 holds. Then, for every i ∈ {1, . . . , M }, √ √ (1 − γ)Dν (wi ∥wπ ) ≤ S ⋆ (wi ) ≤ 2 2 Λw (1 + γ) Dν (wi ∥wπ ). (S5) By Lemma S1, a minimizer of the oracle score has generalized-KL error within a fixed factor of the best candidate in the class. The remaining obstacle is that the oracle critic log(wi /wπ ) is unknown. As in the wi Q-function construction, we replace it by pairwise critics from the candidate class. Define ℓij := log w and j the corresponding pairwise score Sij := Eν [wi (X){ℓij (X) − γ(πℓij )(S ′ )}] − (1 − γ)Ed0 [ℓij (X)]. We then select the candidate with the smallest worst-case score max1≤j≤M Sij . Under realizability, if wi⋆ = wπ , then ℓii⋆ = log(wi /wπ ) is the oracle critic and hence max Sij ≥ Sii⋆ = S ⋆ (wi ) ≥ (1 − γ)Dν (wi ∥wπ ).

1≤j≤M

By contrast, Si⋆ j = 0 for every j, since wi⋆ = wπ satisfies the adjoint Bellman equation. Thus, minimizing the worst-case pairwise score recovers wπ under realizability.

A.2. Penalized score and selector The remaining challenge is misspecification. When wπ is not contained in the class, pairwise log ratios only approximate the oracle critics. We therefore penalize each pairwise score to account for the error from using a comparison candidate wj in place of wπ . We use Hellinger distance because it provides a symmetric measure of separation between the two candidate ratios that can be controlled by their generalized-KL errors relative to wπ . For nonnegative p and q, define the squared Hellinger distance h p i p Hν2 (p, q) := Eν { p(X) − q(X)}2 . For each ordered pair (i, j), define the penalized population score adj Sij := Sij −

1−γ 2 Hν (wi , wj ). 4

The factor 1 − γ comes from the lower bound for the oracle score in (S5). The coefficient (1 − γ)/4 allows the error from replacing the oracle critic by a pairwise critic to be absorbed in the oracle comparison. The A-PBV population selector is eiw ∈ arg min max S adj . ij 1≤i≤M 1≤j≤M

To implement A-PBV, we evaluate empirical versions of the penalized pairwise scores using held-out one-step transitions {(Xt , St′ )}nt=1 and independent initial state–action draws {X0,t }nt=1 from d0 . Algorithm S1 summarizes the resulting procedure, which requires only M 2 directly computable pairwise scores and no additional nuisance or critic fitting.

A.3. Theoretical guarantees for occupancy-ratio selection Population oracle inequality. The following population oracle inequality compares A-PBV with the best candidate in generalized KL, allowing candidate-class misspecification. Theorem S2 (Population A-PBV oracle inequality). Suppose Condition C1 holds. Then every population minimizer eiw satisfies  √  q p 4 2 Λw 2 π + Dν (wei ∥w ) ≤ min Dν (wi ∥wπ ). (S6) √ w 1− γ 3 1≤i≤M Finite-sample oracle inequality. We allow the initial-distribution sample size to differ from the number of validation transitions. 17

Algorithm S1 Adjoint PBV selector for occupancy ratios Require: Candidate ratios w1 , . . . , wM ; validation transitions {(Xt , St′ )}nt=1 ; initial draws {X0,t }nt=1 ; discount factor γ 1: for each pair (i, j) ∈ {1, . . . , M }2 do 2: Set ℓij := log(wi /wj ) and compute adj Sbij :=

n n 1X 1−γ X wi (Xt ){ℓij (Xt ) − γ(πℓij )(St′ )} − ℓij (X0,t ) n t=1 n t=1

−

n q q 1−γ X { wi (Xt ) − wj (Xt )}2 . 4n t=1

3: end for adj

4: Let b iw be the smallest index in arg min1≤i≤M max1≤j≤M Sbij

.

5: return wbi . w

(C2) Initial-distribution draws. Conditional on the training sample, X0,1 , . . . , X0,m are independent and identically distributed according to d0 . In Condition C2, we assume access to samples from the target state–action distribution d0 used to initialize the discounted occupancy distribution and to evaluate the adjoint Bellman moments. If the target initial-state law equals the state marginalPνS of ν, one may reuse the validation states and replace the initial-sample average n of each critic ℓij by n−1 t=1 (πℓij )(St ), yielding d0 (ds, da) = νS (ds)π(da | s). If expectations under d0 are known exactly, they may replace the empirical initial-sample averages in Algorithm S1, and Condition C2 is unnecessary. Theorem S3 (Hellinger oracle inequality for A-PBV). Suppose Conditions A1 and A3 hold. Use either Condition C2, exact d0 moments, or the validation-state initial averages described above when d0 (ds, da) = νS (ds)π(da | s). There is a finite constant Cw,H > 0, depending only on Cw and w, such that, for every δ ∈ (0, 1), conditional on the training sample, with probability at least 1 − δ, the output of Algorithm S1, with its initial average computed from m draws, satisfies s ( ) log(24M/δ) C w,H Hν (wbi , wπ ) ≤ min Hν (wa , wπ ) + w 1 − γ a∈[M ] ngb r Cw,H log(24M/δ) +√ . m 1−γ The final term is omitted when the initial moments are known exactly. If d0 (ds, da) = νS (ds)π(da | s), the validation-state average described above satisfies the same bound with the final term omitted.

B. Theoretical guarantees for Q-function selection We now establish population and finite-sample guarantees for the target-aligned and unweighted PBV selectors.

B.1. Regularity conditions for the joint TA-PBV guarantee For Theorem 5.2, we additionally assume Conditions B1–B3 and either exact d0 moments or Condition C2 with m = n.

B.2. Target-aligned PBV Population oracle inequality. We now justify TA-PBV’s quadratic penalty under candidate-class misspecification, extending the realizable argument in Section 3.2. We require only the following second-moment 18

condition. (B1) Second moments under the target occupancy. The candidate functions and rewards satisfy max ∥Qi ∥22,dπ,γ + Eν [wπ (X)R2 ] < ∞.

1≤i≤K

Condition B1 holds, for example, when the rewards and candidate functions are uniformly bounded. 1 Define the penalized population score MTA ij := ⟨hij , Qi − Bπ Qi ⟩dπ,γ − 4 ⟨hij , (I − γPπ )hij ⟩dπ,γ and let TA eiQ ∈ arg mini∈[K] maxj∈[K] Mij . Theorem S4 (Population TA-PBV oracle inequality). Suppose Condition B1 holds. Then every population minimizer eiQ satisfies s ( √ ) 1+ γ π ∥Qei − Q ∥2,dπ,γ ≤ 1 + 2 min ∥Qi − Qπ ∥2,dπ,γ . (S7) √ Q 1 − γ 1≤i≤K Thus, every minimizer of the penalized population criterion has error within a factor depending only on γ of that of the best candidate, without requiring realizability. In particular, if Qπ belongs to the candidate class, every population minimizer equals Qπ in L2 (dπ,γ ). Finite-sample oracle inequality. We next account for the two additional sources of error in the practical selector: estimation of wπ and sampling variability in the pairwise scores computed on the validation sample. For each candidate, define the TD residual εi := Qi (X) − R − γ(πQi )(S ′ ). The following conditions are also required for the finite-sample analysis. (B2) Bounded candidate differences and conditional TD means. There are finite constants HQ and GQ such that, almost surely, max |hij (X)| ≤ HQ ,

1≤i,j≤K

max |E[εi | X]| ≤ GQ .

1≤i≤K

(B3) Conditional subexponential TD noise. There is a finite constant σQ > 0 such that, almost surely,     |εi − E[εi | X]| max E exp X ≤ 2. 1≤i≤K σQ (B4) Bounded fitted weights. There is a finite constant WQ such that 0 ≤ w(X) b ≤ WQ , ν-almost surely. Under Condition A1, Bernstein concentration holds for the stationary validation process with effective sample size of order ngb . Independent validation transitions correspond to gb = 1 (Jiang et al., 2025). Under Condition B2, the candidate differences and the conditional means of the TD residuals are bounded. Under Condition B3, the centered TD residuals are conditionally subexponential; the residuals themselves need not be bounded. If |εi | ≤ ḠQ almost surely for every i and some ḠQ > 0, then the conditional-mean bound in Condition B2 holds with GQ = ḠQ , and Condition B3 holds with σQ = 2ḠQ / log 2. Finally, the fitted-weight multiplier in the validation scores is bounded under Condition B4. Theorem S5 (Finite-sample TA-PBV oracle inequality). Suppose Condition A1 and Conditions B1–B4 hold, and suppose the Q-validation fold is independent of all data used to construct w. b There are finite constants CQ,wt , CQ,val > 0, depending only on HQ , GQ , σQ , and WQ , such that, for every δ ∈ (0, 1), conditional on the training sample and the data used to construct w, b with probability at least 1 − δ, the TA-PBV selector in Algorithm 1 satisfies s ( √ ) 1+ γ π ∥Qbi − Q ∥2,dπ,γ ≤ 1 + 2 min ∥Qi − Qπ ∥2,dπ,γ √ Q 1 − γ 1≤i≤K CQ,wt +p b wπ ) √ Hν (w, 1− γ s CQ,val log(12K/δ) + . √ 1− γ ngb 19

(S8)

Explicit choices for CQ,wt and CQ,val are given in Appendix H.3. The bound in Theorem S5 consists of the p best-candidate error, √a Hellinger error for the fitted occupancy ratio, and a validation term of order log(12K/δ)/(ngb )/(1 − γ). Thus, temporal dependence enters through the effective sample size ngb , while the class size enters only logarithmically. For fixed γ and envelope constants, the validation term vanishes whenever log K = o(ngb ). Consistency follows when the best-candidate error and Hellinger weight error also vanish. If w b = wπ , the weight-error term is identically zero. A plug-in value-error bound also holds. Since dπ,γ ≥ (1 − γ)d0 , we have cconc := ∥dd0 /ddπ,γ ∥∞ ≤ (1 − γ)−1 , √ and Cauchy–Schwarz gives |Ed0 [Qbi (X)] − V π | ≤ cconc ∥Qbi − Qπ ∥2,dπ,γ . Q

Q

B.3. Unweighted PBV The unweighted selector avoids occupancy-ratio estimation but instead requires coercivity along the oracle comparisons under the offline law ν. (B5) Second moments under the offline distribution. The true action-value function, candidate functions, rewards, and TD residuals satisfy ∥Qπ ∥22,ν + max ∥Qi ∥22,ν + Eν [R2 ] + max Eν [ε2i ] < ∞. 1≤i≤K

1≤i≤K

The corresponding population bound is given in Theorem S23 in Appendix I.1. We state here the finite-sample guarantee for the empirical selector. Theorem S6 (Finite-sample oracle inequality for unweighted PBV). Suppose Conditions A1, A2, B2, B3, and B5 hold. There is a finite constant CQ,unw > 0, depending only on HQ , GQ , and σQ , such that, for every δ ∈ (0, 1), conditional on the training sample, with probability at least 1 − δ, the selector in (5) satisfies s 2 CQ,unw log(12K/δ) π π ∥Qbiunw − Q ∥2,ν ≤ ∥Qk⋆ − Q ∥2,ν + ∥Qk⋆ − Bπ Qk⋆ ∥2,ν + . (S9) Q κν κν ngb More generally, the remaining conditions and the coercivity inequality for any fixed comparator k ∈ [K] imply the same bound with k ⋆ replaced by k. Corollary S7 (Unweighted PBV under target-policy stationarity). Suppose νPπ = ν and Conditions A1, B2, B3, and B5 hold. Then, for every δ ∈ (0, 1), conditional on training, with probability at least 1 − δ, s r   1+γ CQ,unw log(12K/δ) π π min ∥Qi − Q ∥2,ν + ∥Qbiunw − Q ∥2,ν ≤ 1 + 2 . i Q 1−γ 1−γ ngb p An explicit choice of CQ,unw is given in Appendix I.3. The validation term has the same log K/(ngb ) order as for target-aligned PBV, and there is no weight-estimation term. The tradeoff is dependence on the offline coercivity constant κν and an oracle comparison in L2 (ν). For fixed κν > 0 and envelope constants, consistency holds when ∥Qk⋆ − Qπ ∥2,ν and ∥Qk⋆ − Bπ Qk⋆ ∥2,ν vanish and log K = o(ngb ). A similar plug-in value-error bound holds in the offline norm. If d0 ≪ ν and c0,ν := ∥dd0 /dν∥2,ν < ∞, then |Ed0 [Qbiunw (X)] − V π | ≤ c0,ν ∥Qbiunw − Qπ ∥2,ν . Q

Q

C. End-to-end doubly robust OPE This appendix extends the joint TA-PBV procedure to end-to-end OPE. Its first stage selects an occupancyratio candidate, and its second stage uses that ratio to select a Q-function candidate on the same validation fold. The selected nuisances are then evaluated using a doubly robust estimator on an evaluation fold. Let the candidates Q1 , . . . , QK and w1 , . . . , wM be fitted on a training sample. Let Dsel denote the transition fold shared by the two selection stages, and let DV denote the evaluation fold, which may equal Dsel . Let D0,sel and D0,V denote the corresponding initial-distribution samples when those moments are evaluated empirically. 20

Algorithm S2 Sequential PBV doubly robust OPE Require: Candidates Q1 , . . . , QK and w1 , . . . , wM fitted only on a training sample; transition folds Dsel , DV , each of size n and independent of the training sample, with DV = Dsel permitted; when d0 moments are empirical, initial samples D0,sel , D0,V , each of size n and independent of training, with D0,V = D0,sel permitted; discount factor γ b to the b Q) 1: Run both stages of Algorithm 1 on Dsel , using D0,sel or exact d0 moments, and set (w, returned pair. b w) b on DV and D0,V , or using exact d0 moments. 2: Evaluate (Q, b 3: return VDR defined in (S10). Let Pn,V denote the empirical average over the final transition fold, and let Pn,0,V denote the empirical average over D0,V . The estimator returned by Algorithm S2 is the doubly robust estimator (Jiang and Li, 2016; Kallus and Uehara, 2020): h i b + 1 Pn,V w(X){R b ′ ) − Q(X)} b VbDR := Pn,0,V Q b + γ(π Q)(S . (S10) 1−γ The following conditions are imposed for the end-to-end analysis. (D1) Validation laws. Each transition fold follows the stationary validation setup of Section 2.1, has invariant distribution ν, and has spectral gap at least gb . Each empirical initial-distribution sample consists of independent draws from d0 . (D2) Selector regularity. Conditions B1, B2, B3, and A3 hold on the selection fold, with constants HQ , GQ , σQ , Cw , and w as defined there. (D3) Initial-value evaluation. Either Ed0 [Qi (X)] is known exactly for every candidate, or there is a finite constant σQ,0 > 0 such that   |Qi (X0 ) − Ed0 Qi | max Ed0 exp ≤ 2. 1≤i≤K σQ,0 b When the initial-state expectations under d0 are evaluated exactly, set σQ,0 := 0 and interpret Pn,0,V Q b in (S10) as Ed0 [Q(X)]. The finite candidate classes permit a uniform analysis of both PBV stages and the final estimator, including when the selection and evaluation folds coincide. For the selected ratio, Condition B4 holds by Condition A3. For the statement below, let ϵw := min Hν (wj , wπ ), 1≤j≤M s log{12(K ∨ M )/δ} ρδ := . ngb

ϵQ := min ∥Qi − Qπ ∥2,dπ,γ , 1≤i≤K

Corollary S8 (Doubly robust oracle bound for joint TA-PBV). Run Algorithm S2 and suppose Conditions D1– D3 hold. Then, conditional on the training sample, for every δ ∈ (0, 1), with probability at least 1 − δ,   ϵw ϵQ ϵ2w ϵQ ϵw 1 ρ2δ π b |VDR − V | ≲ + + + + ρδ + . (S11) 2 3 2 3 (1 − γ) (1 − γ) (1 − γ) (1 − γ) 1−γ (1 − γ)3 Here ≲ suppresses only universal constants and the fixed structural constants in Conditions D2–D3. The first two terms come from the second-order nuisance remainder. They involve the product ϵw ϵQ and the squared occupancy-ratio approximation error ϵ2w , respectively. The third term collects contributions linear in ρδ from selection and evaluation, including interactions with approximation error. The fourth is quadratic in ρδ . The selection and evaluation samples may coincide. 21

D. Additional experimental details D.1. Benchmark designs Original benchmarks. For the Hopper benchmark of Liu et al. (2025), we use the four model-free perturbation experiments, each with ten target-policy checkpoints evaluated under three environment settings, giving 120 environment–policy combinations. For Deep OPE, we use all eleven target policies of Fu et al. (2021) with the random, medium, medium-replay, medium-expert, and expert D4RL-v2 datasets (Fu et al., 2020) for HalfCheetah, Hopper, Walker2d, and Ant, giving 4 × 5 × 11 = 220 environment–dataset–policy combinations. Controlled-overlap benchmarks. For both Hopper and Deep OPE, let π1 , . . . , πL denote the benchmark policies. At the start of each trajectory, the logging policy draws J uniformly from {1, . . . , L} and follows πJ throughout the trajectory. Each πj is evaluated in turn as the target under the same logging distribution. Since PL Plog = L−1 j=1 Pπj , the target-to-logging trajectory density ratio is bounded by L, as is the corresponding discounted occupancy ratio. For Hopper, L = 10, and all ten targets are evaluated in the gravity and action-noise perturbation experiments under three environment settings, giving 60 environment–target combinations. For Deep OPE, L = 11, and all eleven targets are evaluated in each of four environments, giving 44 combinations. We use five independent occupancy-ratio data replicates per combination. The occupancy-ratio training and validation samples are independent of the samples used to fit and select the Q-function. Within each environment–target combination, the Q-candidate class and its validation sample are held fixed across the five occupancy-ratio replicates. Each occupancy-ratio training or validation sample contains at least 51,200 transitions. Deep OPE splits preserve complete trajectories and contain at least three trajectories from each mixture component.

D.2. Candidate classes and selectors Q-function candidates. The original Hopper benchmark uses the 15 candidate Q-functions from Liu et al. (2025). These candidates are induced by a grid of perturbed Hopper simulators, with either gravity or transition-noise level varied across the grid. For each target policy, candidate Q-values are computed by Monte Carlo rollouts in the corresponding simulator rather than by fitting FQE. For Deep OPE and controlledoverlap Hopper, we fit a 15-candidate neural FQE grid on an independent sample containing at least 51,200 transitions.1 Each Q-network is a multilayer perceptron with two SiLU hidden layers of width 64, 128, or 256. For each width, checkpoints are saved after 50, 100, 200, 400, and 800 fitted-Q iterations, giving 15 candidates in total. Each iteration comprises 20 AdamW updates with minibatches of size 512, learning rate 3 × 10−4 , weight decay 10−4 , and Huber loss. Inputs are standardized, the target network is updated after each fitted-Q iteration, and no early stopping is used. All fits use γ = 0.99. Deep OPE splits preserve complete trajectories. For stochastic target policies, conditional action expectations are approximated using eight draws per transition and 32 draws per reset state. Occupancy-ratio candidates. TA-PBV uses neural FORE estimators of the discounted target-to-logging occupancy ratio. The log ratio is represented by a ReLU network with either one or two 64-unit hidden layers. Each architecture is trained full-batch with AdamW at learning rate 3 × 10−4 or 10−3 and weight decay 10−4 . Snapshots after 25, 50, 100, 200, 400, 800, and 1,600 updates give 28 FORE candidates. A-PBV selects among these candidates on an independent occupancy-ratio validation sample. Before validation, fitted ratios are floored at 10−6 and rescaled on the training sample to satisfy the empirical constant adjoint moment. The selected ratio estimator is then held fixed when TA-PBV selects the Q-function. For the primary analysis, we temper the selected ratio as wT = w1/T /Pn,w [w1/T ] with T = 5, where the normalizing constant is computed on the ratio-training sample and then held fixed. Target-policy returns and selected Q-function performance are not used in occupancy-ratio selection. For the original Hopper benchmark, the ratio-training and ratio-validation samples each contain 3,200 transitions; for the original Deep OPE benchmark, each contains 25,600 transitions. The controlled-overlap comparisons use 51,200 transitions in each sample. 1

The HalfCheetah and Walker2d medium-replay datasets contain fewer than 102,400 usable transitions. For these original Deep OPE settings, we form disjoint trajectory pools and complete each nominal block by sampling complete trajectories within its pool; at least 90% of each block consists of distinct source rows.

22

LSTD-Tournament comparator. Let Pn,Q denote the empirical average over the Q-function validation sample. For candidate i, write εi = Qi (X) − R − γ(πQi )(S ′ ). We implement the normalized-difference criterion of Liu et al. (2025):   biLSTD ∈ arg min max |Pn,Q [Qi (X)εi ]| , max |Pn,Q [(Qi − Qj )(X)εi ]| , 1≤i≤K j̸=i σ bn (Qi ) σ bn (Qi − Qj ) where σ bn (f )2 = Pn,Q [(f − Pn,Q f )2 ]. Unlike PBV, the criterion uses absolute moments and no quadratic penalty. The empirical variance uses divisor n, following Liu et al. (2025). The criterion is undefined if any required empirical standard deviation is zero, and ties are resolved by candidate order. We apply this closed-form criterion directly to the fitted candidate predictions in both benchmarks; no pair-specific LSTDQ model is fitted.

D.3. Validation and evaluation The main comparisons use nQ = 3,200. We additionally evaluate the controlled-overlap selectors at nQ ∈ {3,200, 6,400, 12,800, 25,600, 51,200}. Hopper uses nested prefixes of a fixed random permutation, so the largest sample uses the full validation pool in each of five independent occupancy-ratio replicates. Deep OPE samples complete trajectories with replacement until reaching the nominal size and uses 96 validation resamples per setting. The 90% intervals in Tables S2 and S4 use 4,000 percentile-bootstrap draws over the benchmark hierarchy after averaging over the inner validation resamples. For Hopper, the hierarchy consists of perturbation condition, target policy, and occupancy-ratio replicate when present. For Deep OPE, it consists of environment–dataset combination (or environment in the controlled-overlap benchmarks), target policy, and occupancy-ratio replicate when present. Each level receives equal weight. For the paired comparisons in Table S2, we compute error differences within matched validation resamples and retain the pairing of methods in every bootstrap draw. These intervals hold the fitted candidates and saved reference values fixed. For fitted FQE candidates, the reset-value estimate averages Q(S0 , A0 ) over 51,200 independent reset-state draws, integrating over target actions as described above. Reference values are supplied by the original Hopper benchmark and otherwise are Monte Carlo means from 1,024 target-policy trajectories. Hopper and Deep OPE trajectories have horizons 1,024 and 1,000, respectively, and end at termination. Value errors are reported on the original return scale. Initial-state value-function error. Absolute policy-value error is our primary metric. As a companion diagnostic, we evaluate state-value accuracy under the initial-state distribution µ0 . For fitted candidates, define vb(s) := π b (π Q)(s), and let vH (s) denote the expected discounted return from s over H steps, with zero rewards after termination. We use H = 1,024 for Hopper and H = 1,000 for Deep OPE. We draw N0 = 1,024 reset states (k) S0j per target. From each state, we independently draw two initial actions A0j ∼ π(· | S0j ), k = 1, 2, and (k)

simulate two conditionally independent target-policy returns Gj , each starting with the corresponding action. We estimate N0 Y 2 X  b = 1 b 0j , A(k) ) − G(k) . Ebv,0 (Q) Q(S 0j j N0 j=1 k=1

π The two residuals are independent conditional on S0j , and each has conditional mean vb(S0j ) − vH (S0j ). Hence, π 2 the estimator is unbiased for Eµ0 [(b v − vH ) ], conditional on the fitted candidate. Independent initial actions are needed for stochastic target policies; using the same initial action for both simulations would instead estimate action-value error. For the simulator-defined original Hopper candidates, vb is the corresponding horizon-H state-value function. For each k = 1, 2, we replace the candidate prediction with a candidate-environment return from the same initial state. Candidate and reference environments share random numbers for each k, while the simulations for k = 1 and k = 2 remain independent. Candidate simulations are reused across ground-truth environments and corresponding on- and off-policy logging conditions after verifying identical candidate parameters and target-policy checkpoints. Deep OPE reference simulations are reused across the five dataset qualities for each environment–target pair. All selections are fixed before these evaluation simulations.

23

Table 1 reports the square root of the mean estimated state-value MSE across settings and validation resamples, termed initial-state value RMSE. Table S1 reports its uncertainty.

D.4. Supplementary analyses Table S1: Initial-state value RMSE at nQ = 3,200, with 90% hierarchical bootstrap intervals in brackets. The third line gives the Monte Carlo standard error of RMSE, obtained by the delta method from the MSE standard error. Bootstrap intervals hold the fitted candidates and reference simulations fixed; Monte Carlo standard errors account for the shared evaluation samples. Every target uses 1,024 initial states. Bold marks the smallest displayed mean within each setting and benchmark. Setting

Original

Controlled overlap

Selector

Hopper

Deep OPE

9.4

350.2

Unweighted PBV

[4.2,14.1] MCSE 0.4

[276.5,417.5] MCSE 0.1

9.5

350.1

Unweighted PBV (no penalty)

[4.9,13.8] MCSE 0.4

[276.3,418.3] MCSE 0.1

10.7

347.3

TA-PBV (T = 5)

[5.6,15.0] MCSE 0.4

[275.3,413.3] MCSE 0.1

11.4

341.4

LSTD-Tournament

[5.9,15.9] MCSE 0.4

[264.5,409.4] MCSE 0.1

17.6

363.4

Squared TD error

[10.2,23.5] MCSE 0.7

[283.9,433.3] MCSE 0.1

25.9

139.3

Unweighted PBV

[13.0,39.1] MCSE 0.4

[43.5,212.7] MCSE 0.1

25.1

144.1

Unweighted PBV (no penalty)

[13.3,37.6] MCSE 0.4

[44.1,219.3] MCSE 0.1

21.3

127.0

TA-PBV (T = 5)

[14.5,27.5] MCSE 0.5

[44.2,190.8] MCSE 0.1

34.0

142.9

LSTD-Tournament

[11.8,51.3] MCSE 0.3

[51.7,220.1] MCSE 0.1

22.8

300.6

Squared TD error

[13.8,30.1] MCSE 0.5

[76.8,469.8] MCSE 0.2

24

(a) Original Hopper: Unweighted PBV mf-g, truth 0

(b) Original Deep OPE: Unweighted PBV ant, expert

0.3

mf-g, truth 7

-0.5

mf-g, truth 14

-5.6

mf-n, truth 0

-0.0

mf-n, truth 7

-0.4

mf-n, truth 14

-0.6

mf-off-g, truth 0

101

100

-0.9

0

mf-off-g, truth 7

-3.4

mf-off-g, truth 14

-6.2

mf-off-n, truth 0

0.2

mf-off-n, truth 7

0.5

mf-off-n, truth 14

−100

−101

-0.3

policy avg -0.3 -0.5 -0.3 -0.5 -0.7 -1.8 -3.3 -2.1 -2.6 -2.0

0

1

2

3

4

5

6

7

8

9

-1.4

34.0

ant, medium

25.7

ant, medium-expert

124.0

ant, medium-replay

-10.0

ant, random

-6.5

halfcheetah, expert

-96.6

halfcheetah, medium

-174.3

halfcheetah, medium-expert

-25.5

halfcheetah, medium-replay

-19.5

halfcheetah, random

73.5

hopper, expert

17.8

hopper, medium

26.7

hopper, medium-expert

8.2

hopper, medium-replay

10.5

hopper, random

36.7

walker2d, expert

22.1

walker2d, medium

5.0

walker2d, medium-expert

105.2

walker2d, medium-replay

10.6

walker2d, random

-31.2

policy avg 39.8 14.4 -11.9-50.3 -3.9 53.5 -29.3 -0.5 7.9 -20.7 76.0

avg

0

1

2

3

Target-policy index

4

5

6

7

8

9

10

102 101 100 0 −100 −101 −102

6.8

avg

Target-policy index

(c) Modified Hopper: TA-PBV (T = 5) mf-g, truth 0

0.9

mf-g, truth 7

-0.2

mf-g, truth 14

5.0

mf-n, truth 0

-14.8

(d) Modified Deep OPE: TA-PBV (T = 5) ant

-4.5

halfcheetah

-30.3

101

10

101

0

hopper

-5.2

walker2d

1.7

0

mf-n, truth 7

-6.2

mf-n, truth 14

4.7

−10

102

100 0

0

−100 −101

−101

−102

policy avg -18.9 -0.3 -6.9 5.8

0

1

2

3

0.3

-1.2 -0.0

2.2

-3.7

5.2

-1.7

4

5

7

8

9

avg

6

policy avg -18.8 16.1 -8.4 29.2 -63.8-10.2 12.0 -19.9 6.7 -18.6-30.0

0

Target-policy index

1

2

3

4

5

6

7

8

9

10

-9.6

avg

Target-policy index

Each tile is a prespecified comparison; blue (negative) favors PBV and red (positive) favors LSTD. Right and bottom margins are row and policy means. Color scales are panel-specific symmetric logs.

Figure S1: Policy-level difference in absolute value error relative to LSTD-Tournament; negative values favor PBV. All panels use nQ = 3,200. Panels (a)–(b) show unweighted PBV on the original benchmarks, and panels (c)–(d) show TA-PBV with T = 5 on the controlled-overlap benchmarks. Margins show means across rows and target policies.

25

(a) Original Hopper benchmark

(b) Original Deep OPE benchmark

mf-g, truth 0

2.0

mf-g, truth 7

0.4

mf-g, truth 14

8.4

mf-n, truth 0

0.0

10

mf-n, truth 7

0.0

mf-n, truth 14

0.6

mf-off-g, truth 0

0.5

1

100

0

mf-off-g, truth 7

1.1

mf-off-g, truth 14

0.1

mf-off-n, truth 0

−100

0.0

−101

mf-off-n, truth 7

-0.0

mf-off-n, truth 14

-0.3

policy avg 0.6

0.0

0.1

1.5

4.2

-0.0 -0.0

1.7

2.4

0.1

1.1

0

1

2

3

4

5

7

8

9

avg

6

ant, expert

0.2

ant, medium

-4.6

ant, medium-expert

-24.3

ant, medium-replay

-0.5

ant, random

-2.2

halfcheetah, expert

19.5

halfcheetah, medium

3.8

halfcheetah, medium-expert

2.0

halfcheetah, medium-replay

5.3

halfcheetah, random

-17.5

hopper, expert

-6.1

hopper, medium

-0.2

hopper, medium-expert

-7.3

hopper, medium-replay

1.4

hopper, random

-0.7

walker2d, expert

-28.3

walker2d, medium

-0.7

walker2d, medium-expert

-29.5

walker2d, medium-replay

-2.0

walker2d, random

20.5

policy avg -12.0 -3.5 15.5 5.5 -11.7-21.9 0.4 -8.9 -3.5 8.6 -7.6

0

1

2

3

Target-policy index

4

5

6

7

8

9

10

mf-g, truth 0

-1.8

mf-g, truth 7

-1.2

mf-g, truth 14

4.9

mf-n, truth 0

-12.6

mf-n, truth 7

-0.1

mf-n, truth 14

3.7

3

2.2

-0.0 -1.4 -3.0 -4.4

2.7

-1.2

4

5

9

avg

6

7

8

−100 −101 −102

avg

ant

-0.5

halfcheetah

-18.7

101

−100

2

0

-3.6

101

hopper

2.2

0

1

100

(d) Modified Deep OPE benchmark

100

0

101

Target-policy index

(c) Modified Hopper benchmark

policy avg 0.8 -4.9 -6.7 2.7

102

0

walker2d

-2.8

−100

−101

−101

policy avg -8.4 15.5 -20.3-18.4 -5.1 -2.1 6.6 -4.8 -2.6 -3.4 -11.5

0

Target-policy index

100

1

2

3

4

5

6

7

8

9

10

-4.9

avg

Target-policy index

Each tile is TA-PBV minus unweighted-PBV absolute value error at T = 5; blue (negative) favors TA-PBV. Right and bottom margins are row and policy means. Color scales are panel-specific symmetric logs.

Figure S2: Policy-level difference in absolute value error between TA-PBV with T = 5 and unweighted PBV; negative values favor TA-PBV. All panels use nQ = 3,200. Panels (a)–(b) show the original benchmarks, and panels (c)–(d) show the controlled-overlap benchmarks. Margins show row and target-policy means.

26

Table S2: Paired differences in mean absolute value error at nQ = 3,200. Each entry reports the mean difference with its 90% hierarchical bootstrap interval below. Differences are the first selector minus the second; negative values favor the first selector. TA-PBV uses T = 5. Inner validation resamples are averaged before resampling the benchmark hierarchy, with methods paired in every bootstrap draw. Unweighted PBV minus LSTD-Tournament

TA-PBV minus LSTD-Tournament

TA-PBV minus unweighted PBV

Setting

Benchmark

−1.41

−0.34

1.07

Original

Hopper

[−2.66, −0.37]

[−1.62, 0.88]

[0.14, 2.43]

6.81

3.26

−3.55

Original

Deep OPE

[−19.37, 31.80]

[−20.20, 25.07]

[−9.98, 2.88]

−0.55

−1.75

−1.20

Controlled overlap

Hopper

[−5.23, 3.11]

[−8.36, 3.19]

[−5.83, 2.69]

−4.66

−9.61

−4.95

Controlled overlap

Deep OPE

[−20.42, 7.78]

[−28.71, 2.18]

[−14.40, 1.54]

Table S3: Setting-level absolute value error at nQ = 3,200, reported as median [25th, 75th percentile]. Inner validation resamples are averaged before computing quantiles. Lower is better; bold marks the smallest median at the displayed precision within each study and benchmark. Study

Selector

Hopper

Deep OPE

Original benchmarks

Unweighted PBV Unweighted PBV (no penalty) TA-PBV (T = 5) LSTD-Tournament Squared TD error

1.4 [0.6,4.4] 1.8 [0.7,6.2] 1.7 [0.6,6.5] 1.6 [0.5,5.4] 1.9 [0.4,17.2]

190.6 [90.5,373.3] 197.8 [86.2,373.2] 197.3 [88.6,366.9] 184.1 [85.3,410.0] 197.0 [77.6,455.5]

Controlled overlap

Unweighted PBV Unweighted PBV (no penalty) TA-PBV (T = 5) LSTD-Tournament Squared TD error

8.8 [3.0,20.7] 8.3 [3.1,20.7] 8.3 [2.8,22.1] 8.0 [2.6,20.5] 9.6 [2.8,23.1]

31.8 [13.3,75.8] 37.3 [17.5,72.5] 31.6 [13.8,71.7] 31.8 [17.2,96.5] 62.8 [25.3,190.3]

D.4.1. Validation-sample-size sensitivity under controlled overlap Table S4: Absolute value error for unweighted PBV, TA-PBV, and LSTD-Tournament on the controlled-overlap benchmarks across the Q-validation sample-size grid. Each entry reports the mean with its 90% hierarchical bootstrap interval below. Lower is better; boldface marks the smallest mean in each column. nQ Selector

3,200

6,400

12,800

25,600

51,200

Hopper 15.4

15.2

14.4

14.4

14.3

Unweighted PBV

[7.9,25.1]

[7.7,25.2]

[7.7,23.9]

[7.4,23.4]

[7.4,23.9]

14.2

12.9

12.7

12.6

12.5

TA-PBV (T = 5)

[8.2,20.8]

[7.3,19.2]

[6.8,19.3]

[6.7,19.1]

[6.7,19.1]

15.9

14.1

13.4

13.3

13.0

LSTD-Tournament

[7.3,26.9]

[6.4,24.2]

[6.1,22.8]

[5.9,22.8]

[5.9,21.9]

Deep OPE 70.1

65.5

62.0

60.4

60.2

Unweighted PBV

[26.3,131.0]

[23.8,121.3]

[23.4,114.6]

[23.2,109.5]

[23.5,109.5]

65.1

61.1

57.3

55.5

53.6

TA-PBV (T = 5)

[26.3,116.2]

[24.1,109.8]

[22.9,103.4]

[22.7,99.4]

[22.5,97.0]

74.7

70.1

66.0

63.6

61.3

LSTD-Tournament

[30.4,135.5]

[29.0,125.5]

[29.4,115.2]

[29.1,109.5]

[28.2,104.8]

27

Table S5: TA-PBV temperature sensitivity on the controlled-overlap benchmarks at nQ = 3,200. Value-error entries are means over benchmark settings and validation resamples. ESS entries are median (minimum) relative effective sample sizes, ESS/n, across benchmark settings. All temperatures use the primary benchmark draws from Table 1. The prespecified T = 5 specification follows Sinha et al. (2022). Value error T 1 2.5 5 7.5 10 ∞

ESS fraction

Hopper Deep OPE 16.2 15.6 14.2 13.6 13.4 15.4

Hopper

Deep OPE

90.3 .099 (<.001) .022 (<.001) 68.6 .106 (.066) .447 (<.001) 65.1 .198 (.167) .757 (<.001) 65.0 .409 (.387) .868 (.002) 65.5 .610 (.571) .918 (.053) 70.1 1.000 (1.000) 1.000 (1.000)

E. Additional related work Section 1.3 compares PBV with existing Bellman validation methods and LSTD-Tournament. Here we place the problem in the broader literatures on OPE model selection, occupancy-ratio estimation, supervised aggregation, and statistical inverse problems. Model selection for Q-functions and occupancy ratios. Existing OPE model-selection methods have focused primarily on Q-functions, replacing the unavailable supervised loss with structured Bellman criteria. BErMin estimates Bellman error with complexity penalties; BVFT and BVFT-PE use projected Bellman errors over candidate-dependent state aggregations; and ModBE uses relative square-loss tests for nested model classes (Farahmand and Szepesvári, 2011; Lee et al., 2022; Xie and Jiang, 2021; Zhang and Jiang, 2021). Supervised Bellman validation instead regresses the one-step TD target on the current state and action separately for each candidate. Duality-based Residual Estimation learns residual critics and selects among critic configurations on an additional split (Miyaguchi, 2026; Zitovsky et al., 2023). PBV instead uses candidate-induced critics directly, avoiding candidate-dependent projection, nestedness, and auxiliary critic fitting. Model-selection targets in OPE. Model selection arises at several levels in off-policy evaluation. One line of work selects or combines scalar value estimates, including MAGIC, SWITCH, shrinkage estimators, SLOPE, proxy-task and cross-validation methods, and OPERA (Cief et al., 2025; Nie et al., 2024; Su et al., 2020a,b; Thomas and Brunskill, 2016; Udagawa et al., 2023; Wang et al., 2017). A second line uses OPE to rank policies or tune complete offline-RL pipelines (Irpan et al., 2019; Nie et al., 2022; Paine et al., 2020; Tang and Wiens, 2021; Yang et al., 2022). Zhang and Jiang (2021) primarily study offline policy selection but also use BVFT-PE to select among candidate Qπ estimates for a fixed policy. We instead study nuisance selection for a fixed target policy. From finite classes of candidates fitted independently of the validation data, we select the Q-function or occupancy-ratio estimate used for OPE. This differs from selecting scalar value estimates or policies because neither nuisance is observed, so their target losses are not directly available. Occupancy-ratio estimation and selection. Marginalized importance sampling, DICE methods, and minimax weight learning estimate discounted occupancy ratios from adjoint Bellman equations, typically using prescribed ratio and critic classes (Nachum et al., 2019; Uehara et al., 2020, 2021; Xie et al., 2019; Zhang et al., 2020). FORE is an occupancy-ratio analogue of FQE that estimates the ratio through fitted adjoint Bellman recursion without requiring Bellman completeness (van der Laan and Kallus, 2026), while FORC is a related finite-horizon method that does require Bellman completeness (Huang and Jiang, 2024; Huang et al., 2023). These methods construct an occupancy-ratio estimate within a specified function class. A-PBV instead selects post hoc among already-fitted candidates using pairwise log-ratio critics and Hellinger-penalized adjoint Bellman scores. Supervised model selection and aggregation. In supervised prediction, held-out outcomes make the risk of a fixed candidate directly estimable. Cross-validation uses this risk to select algorithms or tuning parameters,

28

while stacking and Super Learner combine candidates using cross-validated predictions (Stone, 1974; van der Laan and Dudoit, 2003; van der Laan et al., 2007; Wolpert, 1992). Model-selection aggregation instead seeks to match the best element of a finite dictionary; under squared loss, Q-aggregation attains sharp oracle inequalities with logarithmic remainders (Dai et al., 2012; Lan and Syrgkanis, 2024). These supervised criteria are unavailable here because neither Qπ nor wπ is observed, squared temporal-difference error is not a valid target loss, and offline-distribution Bellman moments need not control target-policy error. PBV instead constructs directly estimable pairwise criteria and selects a supplied candidate rather than forming an aggregate. Model selection in linear inverse problems. Related model-selection challenges arise in statistical linear inverse problems, where instability of the inverse operator motivates operator-dependent risk estimates and penalties (Abramovich et al., 2018; Cavalier et al., 2002). For example, Regularized DeepIV uses an out-of-sample Tikhonov criterion to obtain oracle guarantees under misspecification in nonparametric instrumental-variable regression (Li et al., 2024). In general, small forward error need not control structural √ error without regularization and source or link conditions. Here, the Bellman evaluation operator is a γcontraction in L2 (dπ,γ ), while the adjoint Bellman update contracts generalized KL divergence by a factor of γ. These contractions convert pairwise Bellman moments into target-error bounds without a Tikhonov bias– variance choice or generic inverse-problem source conditions. This does not eliminate structural assumptions: TA-PBV requires coverage and occupancy-ratio accuracy, A-PBV requires an upper envelope and bounded pairwise log ratios for the fitted candidates, and unweighted PBV requires pairwise coercivity under the offline distribution.

F. Concentration along the validation trajectory The dependence argument used for all three selectors combines Bernstein concentration for bounded additive functionals of a Markov chain with martingale concentration for the one-step transition innovation. Let ′ Ft := σ(X1 , R1 , S1′ , . . . , Xt−1 , Rt−1 , St−1 , Xt ). Under the validation setup, conditional on Ft , the pair (Rt , St′ ) follows the MDP reward and transition law given Xt . Lemma S9 (Trajectory Bernstein bounds). Let U1 , . . . , Un be a stationary Markov chain with invariant law µ and transition operator PU . Suppose, for some g ∈ (0, 1], ∥PU f ∥2,µ ≤ (1 − g)∥f ∥2,µ for every centered real-valued f ∈ L2 (µ); alternatively, PU is self-adjoint and ⟨f, PU f ⟩µ ≤ (1 − g)∥f ∥22,µ for every such f . Let (Ft )n+1 t=1 be a filtration such that Ut is Ft -measurable and Yt is Ft+1 -measurable. Suppose there is a pMarkov kernel KY , not depending on t, such that L(Yt | Ft ) = KY (Ut , ·) for every t. For u ≥ 1, set rg (u) := u/(ng). (i) If |Yt | ≤ B almost surely and E(Yt2 ) ≤ v 2 , then, with probability at least 1 − 6e−u , n

1X Yt − EYt ≤ CM {vrg (u) + Brg (u)2 }. n t=1 (ii) Suppose Yt = a(Ut ){d(Ut ) + ζt }, where |a| ≤ B, |d| ≤ D, Eµ (a2 ) ≤ v 2 , σ > 0, and     |ζt | E(ζt | Ft ) = 0, E exp Ft ≤ 2. σ

(S12)

(S13)

Then, with probability at least 1 − 6e−u , n

1X Yt − EYt ≤ CM (D + σ){vrg (u) + Brg (u)2 }. n t=1

(S14)

Here CM > 0 is a universal constant. Proof of Lemma S9. We use the following consequence of Theorem 1 of Jiang et al. (2025), or their Theorem 2 under the self-adjoint alternative. If f is a bounded, time-independent function and Eµ f = 0, then, for a universal constant C > 0,   r n 1X u u f (Ut ) ≤ C ∥f ∥2,µ + ∥f ∥∞ (S15) n t=1 ng ng 29

p outside an event of probability R2e−u . For the proof, also write r1 (u) := u/n. For part (i), let m(x) := y KY (x, dy) and ηt = Yt − m(Ut ). The centered function m − EYt has variance at most v 2 and absolute value at Rmost 2B. Thus, by (S15), its empirical average is bounded by C{vrg (u) + Brg (u)2 }. Next, define q(x) := {y − m(x)}2 KY (x, dy). By conditional variance contraction, 0 ≤ q ≤ B2,

Eµ q ≤ v 2 ,

Varµ (q) ≤ B 2 v 2 .

By (S15), applied to q − Eµ q, outside an event of probability 2e−u , n

1X q(Ut ) ≤ C{v + Brg (u)}2 . n t=1

(S16)

The sequence {ηt } is a martingale difference with conditional variance process {q(Ut )} and |ηt | ≤ 2B. By the two-sided form of Freedman’s inequality (Freedman, 1975) and (S16), n

1X ηt ≤ C{vr1 (u) + Br1 (u)rg (u) + Br1 (u)2 } n t=1 outside an event of probability 4e−u . Combining this bound with the bound for the predictable component gives C{vrg (u) + Brg (u)2 + vr1 (u) + Br1 (u)rg (u) + Br1 (u)2 }. Since r1 (u) ≤ rg (u) for g ≤ 1, (S12) follows. For part (ii), apply (S15) first to the centered function ad. Its variance is at most D2 v 2 and its absolute value is at most 2BD, so its empirical average is bounded by CD{vrg (u) + Brg (u)2 }. Apply (S15) a second time to a2 − Eµ (a2 ). Since Eµ (a4 ) ≤ B 2 v 2 , n

1X a(Ut )2 ≤ C{v + Brg (u)}2 n t=1

(S17)

outside an event of probability 2e−u . Expanding the exponential in (S13) gives E(|ζt |k | Ft ) ≤ 2k!σ k for every integer k ≥ 2. Since |a|k ≤ a2 B k−2 ,
k! E |a(Ut )ζt |k Ft ≤ C 2 σ 2 a(Ut )2 (CσB)k−2 . 2 By the martingale Bernstein inequality under this conditional moment condition (de la Peña, 1999) and (S17), n 1X a(Ut )ζt ≤ Cσ{vr1 (u) + Br1 (u)rg (u) + Br1 (u)2 } n t=1 outside an event of probability 4e−u . Combining this bound with the bound for the predictable component gives   C D{vrg (u) + Brg (u)2 } + σ{vr1 (u) + Br1 (u)rg (u) + Br1 (u)2 } . Because r1 (u) ≤ rg (u), (S14) follows.

G. Proofs for occupancy-ratio model selection G.1. Generalized-KL contraction and adjoint residual identities The following contraction was established in the FORE analysis of van der Laan and Kallus (2026). We include the short generalized-KL argument for completeness. Lemma S10 (Generalized-KL contraction of the adjoint update). Let w and w e be nonnegative integrable functions whose adjoint updates exist as ν-densities. Then Dν (Bπ∗ w∥Bπ∗ w) e ≤ γDν (w∥w), e whenever the divergence on the right is finite. 30

(S18)

Proof of Lemma S10. Write D for generalized KL between finite nonnegative measures. This divergence is jointly convex and obeys the data-processing inequality for Markov kernels. Let µ = wν and µ e = wν. e By (2), joint convexity, and data processing, Dν (Bπ∗ w∥Bπ∗ w) e = D((1 − γ)d0 + γµPπ ∥ (1 − γ)d0 + γ µ ePπ ) ≤ (1 − γ)D(d0 ∥d0 ) + γD(µPπ ∥e µPπ )

≤ γD(µ∥e µ) = γDν (w∥w), e which is (S18). Lemma S11 (Generalized-KL three-point identity for the adjoint residual). Let w and v be nonnegative integrable functions that are positive on a common measurable support and vanish ν-almost surely off that support. Set log(w/v) = 0 on their common-zero set, and suppose w+ := Bπ∗ w exists as a nonnegative ν-density. If every divergence in (S19) is finite, then h wi = Dν (w∥v) − Dν (w+ ∥v) + Dν (w+ ∥w). Eν (w − w+ ) log (S19) v In particular, if v = wπ , then

S ⋆ (w) ≥ (1 − γ)Dν (w∥wπ ).

(S20)

Proof of Lemma S11. Finiteness of Dν (w+ ∥v) implies that w+ vanishes off the common support of w and v. Every integrand below therefore vanishes there. Expanding the three generalized-KL terms and canceling their linear parts gives   w w+ w+ + + + + Dν (w∥v) − Dν (w ∥v) + Dν (w ∥w) = Eν w log − w log + w log v v w (S21) i h w = Eν (w − w+ ) log . v The final expression in (S21) is the left-hand side of (S19), so that identity follows. To derive (S20), set v = wπ . By (S1) and (S4), this expression is S ⋆ (w). Now use Bπ∗ wπ = wπ in Lemma S10. By that lemma, the middle divergence in (S19) is at most γDν (w∥wπ ), while the final divergence is nonnegative. Thus, (S20) follows.

G.2. Target-relative ratio bounds Write

ei :=

p

Dν (wi ∥wπ ),

Hij := Hν (wi , wj ),

throughout the remainder of this appendix. Lemma S12 (Relative generalized-KL inequalities). Let Λ ≥ 1. For every z ∈ [Λ−1 , Λ],

For z, ze ∈ [Λ−1 , Λ], Finally, for p, q ≥ 0,

(z − 1)2 ≤ 2Λ{z log z − z + 1}.

(S22)

√ √ √ | log z − log ze| ≤ 2 Λ| z − ze|.

(S23)

p √ √ ( p − q)2 ≤ p log − p + q q

(S24)

whenever the right-hand side is finite. Proof of Lemma S12. The function ϕ(z) = z log z − z + 1 satisfies ϕ′′ (z) = 1/z ≥ 1/Λ on [Λ−1 , Λ]. By the strong-convexity inequality at z = 1, (S22) holds. By the √ mean-value theorem applied to log u on √ u ∈ [Λ−1/2 , Λ1/2 ], together with log z − log ze = 2(log z − log ze), (S23) holds. 31

For (S24), set t = p/q when q > 0. After division by q, the difference between the right- and left-hand sides is √ √ √ √ √ t log t − 2t + 2 t = 2 t{ t log t − t + 1} ≥ 0. When q > 0, the case p = 0 follows by continuity. When q = 0, finiteness of the right-hand side requires p = 0 under the convention in (S2), and both sides vanish. Lemma S13 (Occupancy-ratio plug-in value bound). Suppose Condition C1 holds and r ∈ L2 (dπ,γ ). Then, for every i ∈ {1, . . . , M }, √ p 2Λw 1 π Eν [wi (X)r(X)] − V ≤ ∥r∥2,dπ,γ Dν (wi ∥wπ ). (S25) 1−γ 1−γ Proof of Lemma S13. Fix i ∈ {1, . . . , M } and set zi = wi /wπ on X π . By Condition C1, both wi and wπ vanish off X π . By the occupancy representation of V π and the identity dπ,γ = wπ ν, 1 1 Edπ,γ [(zi (X) − 1)r(X)] . Eν [wi (X)r(X)] − V π = 1−γ 1−γ By Cauchy–Schwarz and (S22), Edπ,γ [(zi (X) − 1)r(X)] ≤ ∥r∥2,dπ,γ ∥zi − 1∥2,dπ,γ , ∥zi − 1∥22,dπ,γ ≤ 2Λw Edπ,γ [zi log zi − zi + 1] = 2Λw Dν (wi ∥wπ ). Combining these inequalities proves (S25). Proof of Lemma S1. Fix i ∈ {1, . . . , M } and abbreviate w = wi . The comparison with wπ is preserved by the adjoint update. Indeed, π π Λ−1 (S26) w w ν ≤ (1 − γ)d0 + γ(wν)Pπ ≤ Λw w ν, because wπ ν = (1 − γ)d0 + γ(wπ ν)Pπ and the corresponding bounds on wν relative to wπ ν hold by Condition C1. Thus, the middle measure in (S26) admits a ν-density w+ := Bπ∗ w. The ratios w/wπ and w+ /wπ are bounded above and away from zero on X π , so the hypotheses of Lemma S11 hold. By the lower bound in that lemma, (S20) holds. For the upper bound, define w+ w z̄ := π , z := π , w w setting both ratios equal to one on (X π )c . Apply (S22) to z and z̄ under the probability measure wπ ν = dπ,γ . By the triangle inequality and (S18), ∥z − z̄∥2,dπ,γ ≤ ∥z − 1∥2,dπ,γ + ∥z̄ − 1∥2,dπ,γ np o p p ≤ 2Λw Dν (w∥wπ ) + Dν (w+ ∥wπ ) p √ p ≤ 2Λw (1 + γ) Dν (w∥wπ ).

(S27)

Moreover, by the log-Hellinger comparison (S23) and the generalized-KL control of Hellinger distance in (S24), p p ∥ log z∥2,dπ,γ ≤ 2 Λw Dν (w∥wπ ). (S28) By (S27), (S28), (S1), (S4), and Cauchy–Schwarz, √ √ |S ⋆ (w)| ≤ 2 2 Λw (1 + γ)Dν (w∥wπ ).

(S29)

The upper bound in (S5) follows from (S29). Since i was arbitrary, the result holds for every candidate. 32

Lemma S14 (Pairwise occupancy-score bounds). Suppose Condition C1 holds. Then, for every ordered pair (i, j), √ √ Sij ≥ (1 − γ)e2i − 2 2 Λw (1 + γ)ei ej , (S30) Hij ≤ ei + ej , √ √ |Sij | ≤ 2 2 Λw (1 + γ)ei Hij .

(S31) (S32)

Proof of Lemma S14. Let wi+ := Bπ∗ wi , zi = wi /wπ , and z̄i = wi+ /wπ , setting both relative ratios equal to one on (X π )c . By (S27), p √ ∥zi − z̄i ∥2,dπ,γ ≤ 2Λw (1 + γ)ei . (S33) By the log-Hellinger comparison (S23) and the generalized-KL control of Hellinger distance in (S24), p ∥ log zj ∥2,dπ,γ ≤ 2 Λw ej . (S34) By Cauchy–Schwarz, (S33), and (S34), h √ wj i √ Eν (wi − wi+ ) log π ≤ 2 2 Λw (1 + γ)ei ej . w

(S35)

By (S1), the definition of Sij , and ℓij = log(wi /wπ ) − log(wj /wπ ), h wj i Sij = S ⋆ (wi ) − Eν (wi − wi+ ) log π . w Combining this identity with (S20) p and (S35) proves (S30). After integration, Hν (p, q) ≤ Dν (p∥q) by (S24). Therefore, by the triangle inequality in L2 (ν), Hij ≤ Hν (wi , wπ ) + Hν (wj , wπ ) ≤ ei + ej , which proves (S31). Finally, by (S23), p ∥ℓij ∥2,dπ,γ ≤ 2 Λw Hij .

(S36)

By (S33) and (S36), Cauchy–Schwarz applied to Sij = Eν [(wi − wi+ )ℓij ] gives (S32). For the penalized scores, write

adj Tiw := max Sij , 1≤j≤M

and define the population oracle constant   s √ √  √ 2 1 2 2 Λw 2 2 Λw 2  2 2 Λw + Rw := √ + + 4 √ √ + 1 . 3 1− γ 2 1− γ 1− γ

(S37)

Lemma S15 (Population A-PBV score bounds). Suppose Condition C1 holds. Then, for every i, k ∈ {1, . . . , M },   √ 3(1 − γ) 2 1−γ 1−γ 2 √ adj Tiw ≥ Sik ≥ ei − 2 2 Λw (1 + γ) + ei ek − e , (S38) 4 2 4 k √ 8Λ2w (1 + γ)2 2 Tkw ≤ ek . (S39) 1−γ Moreover,

√ 4 2 Λw 2 Rw ≤ √ + . 1− γ 3

33

(S40)

Proof of Lemma S15. By the pairwise lower bound (S30) and the triangle bound (S31), √ 1−γ √ adj Sik ≥ (1 − γ)e2i − 2 2 Λw (1 + γ)ei ek − (ei + ek )2 , 4 which is (S38). For every j, by the pairwise upper bound (S32), √ 1−γ 2 √ adj Skj ≤ 2 2 Λw (1 + γ)ek Hkj − Hkj . 4 Completing the square in Hkj , √ 1−γ 2 √ 2 2 Λw (1 + γ)ek Hkj − Hkj 4 ( )2 √ √ √ 4 2 Λw (1 + γ) 8Λ2w (1 + γ)2 2 1 − γ ek − Hkj − ek . = 1−γ 4 1−γ √ adj Hence, Skj ≤ 8Λ2w (1 + γ)2 e2k /(1 − γ). Taking the maximum over j proves (S39). √ √ √ To bound Rw , note that 2 2 Λw /(1 − γ) ≥ 1 and that 4t2 + t + 1 ≤ 2t + 1/2 for every t ≥ 1. By this elementary inequality and (S37), (S40) holds.

G.3. Population oracle inequality Proof of Theorem S2. Choose k ∈ arg min1≤i≤M ei , and write x = eei and y = ek . By population optimality, w T w ≤ Tkw . Combining this comparison with Lemma S15, eiw     √ √ 8Λ2w (1 + γ)2 3(1 − γ) 2 1−γ 1−γ √ x ≤ 2 2 Λw (1 + γ) + + xy + y2 . (S41) 4 2 4 1−γ √ √ If y = 0, then x = 0 by (S41). If y > 0, let r = x/y and t = 2 2 Λw /(1 − γ). Then (S41) is equivalent to 3 2 r − (t + 12 )r − (t2 + 14 ) ≤ 0, 4 whose nonnegative root is Rw as defined in (S37). Thus, x ≤ Rw y. By (S40), (S6) follows.

G.4. Hellinger oracle inequality Proof of Theorem S3. Condition on the training sample. Throughout this proof, C > 0 denotes a finite constant depending only on Cw and w; its value may increase between displays. Choose the smallest index k ∈ arg mina Hν (wa , wπ ), and write e := Hν (wk , wπ ),

q := (wπ ∨ wk /2) ∧ 2wk ,

d := ∥q − Bπ∗ q∥1,ν .

Condition A3 ensures that the adjoint update of every bounded nonnegative function exists as a ν-density. Comparison with a bounded density. On {wπ < wk /2}, √ √ wk − wπ ≤ ( wk − wπ )2 , 2 √ √ by expanding 2( wπ − wk /2)2 ≥ 0. On {wπ > 2wk }, √ √ wπ − 2wk ≤ 2( wπ − wk )2 , √ √ by expanding ( wπ − 2 wk )2 ≥ 0. Moreover, q lies pointwise between wk and wπ . Thus ∥q − wπ ∥1,ν ≤ 2e2 ,

Hν (q, wπ ) ≤ e,

34

Hν (wk , q) ≤ e.

(S42)

Since Bπ∗ wπ = wπ and a Markov pushforward contracts the total variation norm, d = ∥(I − γPπ∗ )(q − wπ )∥1,ν ≤ (1 + γ)∥q − wπ ∥1,ν ≤ 4e2 . (S43) √ Adjoint moment bounds. For each candidate, set Di := Dν (wi ∥q) and xi := Di . The candidate ratio bound and wk /2 ≤ q ≤ 2wk imply 1 wi ≤ ≤ 2Cw , 2Cw q

0 < q ≤ 2w.

Consequently Di is finite and log(wi /q) is bounded. Put f = wi /q. The generalized-KL variational inequality ⟨p, log f ⟩ν ≤ Dν (p∥v) + ⟨v, f − 1⟩ν holds for nonnegative integrable p, v and positive bounded f , by the pointwise inequality u log z ≤ u log u−u+z after scaling by v. Apply it with p = Bπ∗ wi and v = Bπ∗ q. By Lemma S10, ⟨Bπ∗ wi , log(wi /q)⟩ν ≤ γDi + ⟨Bπ∗ q, wi /q − 1⟩ν . Subtracting from ⟨wi , log(wi /q)⟩ν gives ⟨wi − Bπ∗ wi , log(wi /q)⟩ν ≥ (1 − γ)Di + ⟨q − Bπ∗ q, wi /q − 1⟩ν ≥ (1 − γ)x2i − Cd.

(S44)

To control the remaining moments, first note that wi − q √ q

≤ (1 +

p

2Cw )Hν (wi , q).

2,ν

For any bounded critic g, Jensen’s inequality and γPπ∗ q ≤ Bπ∗ q yield γ 2 ∥Pπ g∥22,qν ≤ γ⟨Bπ∗ q, g 2 ⟩ν ≤ γ{∥g∥22,qν + d∥g∥2∞ }. Decompose wi − Bπ∗ wi as (I − γPπ∗ )(wi − q) + (q − Bπ∗ q). Weighted Cauchy–Schwarz and the preceding two bounds give √ |⟨wi − Bπ∗ wi , g⟩ν | ≤ CHν (wi , q){∥g∥2,qν + d∥g∥∞ } + d∥g∥∞ . (S45) Here the norm ∥ · ∥2,qν is with respect to the finite measure with density q relative to ν. For positive u, v, √ √ p | log u − log v| ≤ 2| u − v|/ min(u, v). Since q/ min(wi , wj ) ≤ 2Cw and the candidate ratios are bounded, p ∥ℓij ∥2,qν ≤ 8Cw Hν (wi , wj ), ∥ℓij ∥∞ ≤ log Cw , √ ∥ log(wk /q)∥2,qν ≤ 8 Hν (wk , q), ∥ log(wk /q)∥∞ ≤ log 2. Write h := 1 − γ and Hij := Hν (wi , wj ). Using ℓik = log(wi /q) − log(wk /q) in (S44) and (S45), and then applying (S42)–(S43), we obtain Sik ≥ hx2i − Cexi − Ce2 . Moreover, Hν (wi , q) ≤ xi by Lemma S12, so Hik ≤ xi + e. Subtracting the Hellinger penalty gives adj Sik ≥

3h 2 x − Cexi − Ce2 . 4 i

(S46)

For the comparator k, (S45) applied to g = ℓkj instead gives adj Skj ≤ CeHkj + Ce2 −

h 2 H . 4 kj

(S47)

Validation deviation. For a validation transition, define Yij := wi (X){ℓij (X) − γ(πℓij )(S ′ )} − 35

h p { wi (X) − 4

q

wj (X)}2 .

2 The candidate bounds give |Yij | ≤ C. The current-state term has second moment at most CHij : indeed,

wi2 ℓ2ij ≤ 4

√ √ wi2 √ √ ( wi − wj )2 ≤ 4Cw w( wi − wj )2 . min(wi , wj )

For the successor term, use wi2 ≤ 2Cw w q and conditional Jensen’s inequality to obtain E[γ 2 wi (X)2 {(πℓij )(S ′ )}2 ] ≤ 2Cw w γ 2 Eqν Pπ (ℓ2ij ) ≤ 2Cw w γ⟨Bπ∗ q, ℓ2ij ⟩ν 2 ≤ C(Hij + d). 2 The last step uses ⟨Bπ∗ q, ℓ2ij ⟩ν ≤ ∥ℓij ∥22,qν + d∥ℓij ∥2∞ . The penalty has second moment at most CHij , since √ √ 4 2 Eν ( wi − wj ) ≤ CHij . By (S43), 2 EYij2 ≤ C(Hij + e2 ). (S48)

For the initial contribution, |hℓij (X0 )| ≤ Ch and hd0 ≤ (Bπ∗ q)ν imply 2 h2 Ed0 ℓ2ij ≤ h⟨Bπ∗ q, ℓ2ij ⟩ν ≤ Ch(Hij + e2 ).

p p Let Pkw = {(i, k) : i ∈ [M ]} ∪ {(k, j) : j ∈ [M ]}, u = log(24M/δ), rT = u/(ngb ), and r0 = u/m. Apply Lemma S9(i) to Yij along the validation chain. Apply the same lemma with g = 1 to hℓij (X0,t ) along the iid initial sequence. A union bound over both collections, each containing at most 2M − 1 ordered pairs, gives, with probability at least 1 − δ, adj adj |Sbij − Sij | ≤ C{(Hij + e)rT + rT2 } √ + C{ h(Hij + e)r0 + hr02 }

simultaneously for all (i, j) ∈ Pkw . The two concentration events use only the marginal laws of their respective samples. Their union bound does not require independence between the √ initial sequence and the validation trajectory. For exact initial moments, set r0 = 0. Writing r = rT + h r0 , we have rT2 + hr02 ≤ r2 , so the preceding bound implies adj adj |Sbij − Sij | ≤ C{(Hij + e)r + r2 }. (S49) Empirical comparison. On this event, set x = xbi and z = e + r. By (S46), (S49), and Hbi k ≤ x + e, w

w

3h 2 x − Czx − Cz 2 . max Sbadj ≥ biw j j 4 For the comparator, (S47) and (S49) give adj max Sbkj ≤ sup{Czu − hu2 /4 + Cz 2 } ≤ Cz 2 /h. j

u≥0

Empirical optimality therefore implies 3hx2 /4 ≤ Czx + Cz 2 /h. Multiplication by h and the quadratic formula yield x ≤ Cz/h. Finally, Hν (wbi , wπ ) ≤ Hν (wbi , q) + Hν (q, wπ ) ≤ x + e ≤ w

w

C C (e + rT ) + √ r0 . 1−γ 1−γ

For validation-state initial averages, incorporate −h(πℓij )(S) into Yij . Its expectation is the required initial moment, and Jensen’s inequality gives 2 h2 EνS (πℓij )2 ≤ h2 Ed0 ℓ2ij ≤ Ch(Hij + e2 ).

Thus (S48) and the same trajectory concentration argument apply with r = rT . This proves both assertions.

36

H. Proofs for TA-PBV H.1. Population score bounds Recall that

∆i := Qi − Qπ .

Lemma S16 (Discounted-occupancy operator bounds). For every f ∈ L2 (dπ,γ ), √ ∥γPπ f ∥2,dπ,γ ≤ γ∥f ∥2,dπ,γ , √ ⟨f, (I − γPπ )f ⟩dπ,γ ≥ (1 − γ)∥f ∥22,dπ,γ , √ ∥(I − γPπ )f ∥2,dπ,γ ≤ (1 + γ)∥f ∥2,dπ,γ .

(S50) (S51) (S52)

Proof. If γ = 0, then γPπ = 0 and I − γPπ = I, so all three bounds hold with equality. Suppose γ > 0. By conditional Jensen’s inequality, (Pπ f )2 ≤ Pπ (f 2 ). By the discounted-occupancy identity dπ,γ = (1 − γ)d0 + γdπ,γ Pπ ,   γEdπ,γ Pπ (f 2 ) = Edπ,γ (f 2 ) − (1 − γ)Ed0 (f 2 ) ≤ Edπ,γ (f 2 ).

(S53)

Therefore,   ∥γPπ f ∥22,dπ,γ = γ 2 Edπ,γ (Pπ f )2   ≤ γ 2 Edπ,γ Pπ (f 2 ) ≤ γEdπ,γ (f 2 ) = γ∥f ∥22,dπ,γ , This proves the contraction bound. Cauchy–Schwarz and the triangle inequality now give, respectively, √ ⟨f, (I − γPπ )f ⟩dπ,γ ≥ (1 − γ)∥f ∥22,dπ,γ , √ ∥(I − γPπ )f ∥2,dπ,γ ≤ (1 + γ)∥f ∥2,dπ,γ . These are the remaining two bounds. For f ∈ L2 (dπ,γ ), write

E(f ) := ⟨f, (I − γPπ )f ⟩dπ,γ .

Lemma S17 (Bellman operator bound). Let T be a bounded linear operator on a real Hilbert space, with ∥T ∥ ≤ c < 1, and let A = I − T . Then, for every f, g, p ∥Af ∥2 ∨ ∥A∗ f ∥2 ≤ (1 + c)⟨f, Af ⟩, |⟨f, Ag⟩| ≤ (1 + c)⟨f, Af ⟩ ∥g∥. In particular, for every f, g ∈ L2 (dπ,γ ), ⟨f, (I − γPπ )g⟩dπ,γ ≤

q √ (1 + γ)E(f )∥g∥2,dπ,γ .

(S54)

Proof. Write E = ⟨f, Af ⟩. Since ∥T ∗ ∥ = ∥T ∥ ≤ c and E ≤ (1 + c)∥f ∥2 , expansion of the squared norm gives ∥Af ∥2 = 2E − ∥f ∥2 + ∥T f ∥2 ≤ 2E − (1 − c2 )∥f ∥2 ≤ (1 + c)E. The same expansion with T ∗ proves the bound for A∗ f , because ⟨f, A∗ f ⟩ = E. Cauchy–Schwarz applied √ to ⟨A∗ f, g⟩ proves the cross-moment bound. Finally, Lemma S16 gives ∥γPπ ∥ ≤ γ in L2 (dπ,γ ), proving (S54). 37

Lemma S18 (Second moments and score integrability). Suppose Condition B1 holds. Then Qπ ∈ L2 (dπ,γ ), every Qi − Qπ belongs to L2 (dπ,γ ), and the expectations defining MTA ij are absolutely integrable for every ordered pair (i, j). Proof. Let r(x) := E(R | X = x) and m(x) := E(|R| | X = x). By conditional Jensen’s inequality, ∥r∥2,dπ,γ ≤ √ ∥m∥2,dπ,γ and ∥m∥22,dπ,γ ≤ Eν [wπ (X)R2 ] < ∞. Lemma S16 gives ∥γPπ ∥L2 (dπ,γ )→L2 (dπ,γ ) ≤ γ < 1. Thus the P Neumann series t≥0 (γPπ )t r converges in L2 (dπ,γ ). The same bound applied to m gives X

(γPπ )t m

t≥0

≤

∥m∥2,dπ,γ √ < ∞. 1− γ

2,dπ,γ

P By Tonelli’s theorem, this nonnegative series equals Eπ [ t≥0 γ t |Rt | | X0 = x] and is finite for dπ,γ -almost every x. We may therefore interchange expectation and summation in the definition of Qπ , obtaining X ∥r∥2,dπ,γ Qπ = (γPπ )t r = (I − γPπ )−1 r, ∥Qπ ∥2,dπ,γ ≤ √ . 1− γ t≥0

By Condition B1, every ∆i = Qi − Qπ and hij = Qi − Qj = ∆i − ∆j belongs to L2 (dπ,γ ). It remains to verify integrability of the one-step score. For γ > 0, by conditional Jensen’s inequality and (S53), Eν [wπ (X){(πQi )(S ′ )}2 ] ≤ γ −1 ∥Qi ∥22,dπ,γ < ∞; when γ = 0, the continuation term is identically zero. Hence Qi (X) − R − γ(πQi )(S ′ ) is square integrable under the wπ -weighted transition law. By Cauchy–Schwarz and hij ∈ L2 (dπ,γ ), Eν [wπ (X)|hij (X)||Qi (X) − R − γ(πQi )(S ′ )|] < ∞. Finally, εi − εj is square integrable under the wπ -weighted transition law. Hence Eν [wπ |hij (εi − εj )|] < ∞ by Cauchy–Schwarz, which proves absolute integrability of the penalty as well. For each i ∈ [K], let Ti := maxj MTA ij . Lemma S19 (Population score comparison). Suppose Condition B1 holds. For every i, k, j ∈ [K], q 3 √ Ti ≥ MTA ≥ E(h ) − (1 + γ)E(hik )∥∆k ∥2,dπ,γ , ik ik 4 q 1 √ MTA ≤ (1 + γ)E(hkj )∥∆k ∥2,dπ,γ − E(hkj ), kj 4 √ Tk ≤ (1 + γ)∥∆k ∥22,dπ,γ .

(S55) (S56) (S57)

Proof. Set A = I − γPπ . Conditioning on X, using the Bellman equation for Qπ , and applying Lemma S16 give 1 (S58) MTA ij = ⟨hij , A∆i ⟩dπ,γ − E(hij ). 4 The positive part in the population penalty has no effect because E(hij ) ≥ 0. Since ∆i = hik + ∆k , 3 E(hik ) + ⟨hik , A∆k ⟩dπ,γ . 4 Lemma S17 proves (S55). Applying the same lemma directly to (S58) p with i = k proves (S56). Finally, for b ≥ 0, supz≥0 (bz − z 2 /4) = b2 . Maximize the latter bound over z = E(hkj ) to obtain (S57). √ Proof of Theorem S4. Choose k ∈ arg mini ∥∆i ∥2,dπ,γ and write y = ∥∆k ∥2,dπ,γ , β = 1 + γ, and z = q E(hei k ). By the minimizing property of eiQ and Lemma S19, Q MTA ik =

3 2 p z − β yz ≤ Tei ≤ Tk ≤ βy 2 . Q 4 √ The nonnegative root of this quadratic inequality is z ≤ 2 β y. By (S51) and the triangle inequality, s ( √ ) 1+ γ z ∥∆ei ∥2,dπ,γ ≤ y + ∥hei k ∥2,dπ,γ ≤ y + p y. √ √ ≤ 1+2 Q Q 1− γ 1− γ This is the asserted population oracle inequality. 38

H.2. Concentration bound for the Q-function criterion Define the fitted-weight error by

ρw := Hν (w, b wπ ).

(S59)

Lemma S20 (Localized validation-score deviation). Suppose Condition A1 and Conditions B2–B4 hold, and suppose the Q-validation fold is independent of all data used to construct w. b There is a universal constant C0 > 0 such that, for every δ ∈ (0, 1) and every nonempty collection P ⊆ [K]2 fixed conditional on the training sample and the data used to construct w, b conditional on these data, with probability at least 1 − δ, simultaneously for all (i, j) ∈ P, cTA − MTA ≤ η∥hij ∥2,d + v, M ij ij π,γ

(S60)

where, with r = {log(6|P|/δ)/(ngb )}1/2 , η = 2GQ ρw + C0

p

WQ (GQ + σQ )r, p WQ ρw r + WQ r2 }.

v = HQ GQ ρ2w + C0 HQ (GQ + σQ ){

Proof. Condition on the training sample and the data used to construct w. b Let Pn,Q denote the empirical average over the Q-validation transitions. For i ∈ [K], put µi (X) = E(εi | X) and ξi = εi − µi (X). For an ordered pair (i, j) and τ ∈ {3/4, 1}, define Zij,τ = w(X)h b ij (X){τ εi + (1 − τ )εj },

mij,τ = τ µi + (1 − τ )µj ,

ζij,τ = τ ξi + (1 − τ )ξj .

The elementary identity a − (a − b)+ /4 = min{a, 3a/4 + b/4} gives cTA M ij = MTA ij =

min

Pn,Q Zij,τ ,

min

Eν [wπ hij mij,τ ].

τ ∈{3/4,1} τ ∈{3/4,1}

(S61)

For the second identity, the difference between the τ = 1 and τ = 3/4 expectations is E(hij )/4 ≥ 0. Since, for real numbers (a1 , a2 ) and (b1 , b2 ), | minℓ aℓ − minℓ bℓ | ≤ maxℓ |aℓ − bℓ |, it suffices to bound both branches in (S61). The branch means satisfy |mij,τ | ≤ GQ by Condition B2. Moreover, E(ζij,τ | X) = 0 and, by convexity and Condition B3, E [ exp{|ζij,τ |/σQ }| X] ≤ τ E[exp{|ξi |/σQ } | X] + (1 − τ )E[exp{|ξj |/σQ } | X] ≤ 2. Thus the branch innovations obey the same conditional subexponential bound as the individual TD innovations. The validation setup makes these innovations martingale differences conditional on the past. Write Aij = wh b ij and sij = ∥hij ∥2,dπ,γ . Under Condition B4, |Aij | ≤ WQ HQ ,

Eν (A2ij ) ≤ WQ (sij + HQ ρw )2 .

(S62)

Indeed, w b2 ≤ WQ w b and the triangle inequality give √ √ √ √ ∥ w b hij ∥2,ν ≤ ∥ wπ hij ∥2,ν + ∥( w b − wπ )hij ∥2,ν ≤ sij + HQ ρw . √ √ √ Set z = w b − wπ . Since w b − wπ = 2 wπ z + z 2 , Cauchy–Schwarz yields, for either branch, |EZij,τ − Eν [wπ hij mij,τ ]| ≤ 2GQ ρw sij + HQ GQ ρ2w .

(S63)

Bounding the critic rather than its conditional mean also gives |EZij,τ − Eν [wπ hij mij,τ ]| ≤ 2HQ ρw ∥mij,τ ∥2,dπ,γ + HQ GQ ρ2w . 39

(S64)

√ √ Indeed, the term linear in z = w b − wπ is at most 2∥z∥2,ν ∥hij mij,τ ∥2,dπ,γ , and |hij | ≤ HQ ; the term quadratic in z is bounded as in (S63). Apply Lemma S9(ii) with multiplier Aij , conditional mean mij,τ , and innovation ζij,τ . Their envelope, mean bound, and second moment are given above. Taking a union bound over the 2|P| branches with u = log(12|P|/δ) gives, simultaneously, p |Pn,Q Zij,τ − EZij,τ | ≤ C0 (GQ + σQ ){ WQ (sij + HQ ρw )r + WQ HQ r2 }, (S65) after increasing C0 , because log(12|P|/δ) ≤ 2 log(6|P|/δ). Combining (S61), the bound for the minimum, (S63), and (S65) proves (S60).

H.3. Finite-sample oracle inequality Let C0 be the universal constant in Lemma S20, and define ( VQ := HQ

GQ + C0 (GQ + σQ ) WQ +

√ √ 2 6p VQ , CQ,wt := 5 2HQ + 3 √ p 2 6p CQ,val := 2C0 WQ (GQ + σQ ) + VQ . 3

p

WQ 4

!) ,

These constants depend only on the envelopes in Conditions B2–B4. Proof of Theorem S5. Let k be the smallest index minimizing ∥∆i ∥2,dπ,γ , and apply the branchwise concentration bound (S65) from the proof of Lemma S20 to Pk = {(i, k) : i ∈ [K]} ∪ {(k, j) : j ∈ [K]}. This collection is fixed conditional on training and has at most 2K − 1 elements. Enlarge the logarithmic factor to log(12K/δ), and set s log(12K/δ) √ √ r= , α = 1 − γ, β = 1 + γ, ngb p y = ∥∆k ∥2,dπ,γ , ηs = C0 WQ (GQ + σQ )r, p vs = C0 HQ (GQ + σQ ){ WQ ρw r + WQ r2 }. On the resulting event, every branch in (S61) differs from its fitted-weight expectation by at most ηs ∥hij ∥2,dπ,γ + vs . Let A = I − γPπ . The conditional residual identity µi = A∆i holds dπ,γ -almost surely. Lemma S17 gives ∥Af ∥22,dπ,γ ≤ βE(f ). q For the selected pair, put z = E(hbi k ). Since ∆bi = hbi k + ∆k , for either τ ∈ {3/4, 1}, Q Q Q p ∥mbi k,τ ∥2,dπ,γ = ∥A(∆k + τ hbi k )∥2,dπ,γ ≤ βy + β z. Q Q Combine (S64), the branchwise concentration event, and the bound for the minimum in (S61). Using √ ∥hbi k ∥2,dπ,γ ≤ z/ α and (S55), we obtain Q

  p p 3 2 ηs TA c max Mb ≥ z − β y + 2HQ β ρw + √ z − 2HQ βρw y − HQ GQ ρ2w − vs . (S66) iQ j j 4 α p For the comparator pair (k, j), put u = E(hkj ). The empirical minimum is at most its τ = 3/4 branch. For this branch, √ β mkj,3/4 = A(∆k − hkj /4), ∥mkj,3/4 ∥2,dπ,γ ≤ βy + u. 4 40

Thus (S64), the same concentration event, and (S56) give √   p HQ β ηs 1 cTA √ β y + ρ + M ≤ u − u2 + 2HQ βρw y + HQ GQ ρ2w + vs . w kj 2 4 α Maximizing this quadratic in u ≥ 0, and writing √ p HQ β ηs bup = β y + ρw + √ , 2 α we obtain

b=

√ p 5HQ β ηs βy+ ρw + √ , 2 α

2 2 cTA max M kj ≤ bup + 2HQ βρw y + HQ GQ ρw + vs . j

The coefficient of z in (S66) is at most b. Moreover, p b2 − b2up = 2HQ β ρw (b + bup ) ≥ 4HQ βρw y. Empirical optimality consequently implies 3 2 z ≤ bz + b2 + 2(HQ GQ ρ2w + vs ). 4 √ √ √ Solving the quadratic and using a + b ≤ a + b yields √ q 2 6 HQ GQ ρ2w + vs . z ≤ 2b + 3 The triangle inequality and coercivity now give z ∥∆bi ∥2,dπ,γ ≤ y + √ Q α r ! √ r √ β 5HQ β 2 6 HQ GQ ρ2w + vs 2ηs y+ √ + . ≤ 1+2 ρw + α α 3 α α Since ρw r ≤ (ρw + r)2 /4 and ρ2w ∨ r2 ≤ (ρw + r)2 , we have HQ GQ ρ2w + vs ≤ VQ (ρw + r)2 . Finally, β ≤ 2 and α−1/2 ≤ α−1 give s ( √ ) 1+ γ CQ,wt CQ,val ∥∆bi ∥2,dπ,γ ≤ 1 + 2 y+ p √ √ r, √ ρw + Q 1− γ 1− γ 1− γ p The symmetric part of A = I − γPπ is positive definite by (S51), so E(·) is a norm. The triangle inequality, E(∆k ) ≤ βy 2 , and the bound for z therefore also give q p E(∆bi ) ≤ z + β y Q √ p p 2ηs 2 6p ≤ 3 β y + 5HQ β ρw + √ + VQ (ρw + r) 3 α   r ≤ CE y + ρw + √ , (S67) α where one may take √ CE = max 3 2, 

√ √ 2 6p 5 2HQ + VQ , 3

2C0

p

√  2 6p WQ (GQ + σQ ) + VQ . 3

This constant depends only on the stated envelopes. These bounds prove Theorem S5.

41

I. Proofs for unweighted pairwise Bellman validation For each (i, j), define

1 [Eν {hij (X)(εi − εj )}]+ , (S68) 4 where [x]+ := max{0, x}. This is the population counterpart of (5), since εi − εj = hij (X) − γ(πhij )(S ′ ). Condition B5 and Cauchy–Schwarz ensure that both expectations are finite. The corresponding population selector is eiunw ∈ arg min max Munw Q ij . Munw := Eν [hij (X)εi ] − ij

i∈[K]

j∈[K]

I.1. Population score bounds Write ∆i = Qi − Qπ , µi = E(εi | X), and Tiunw = maxj Munw ij . For pairwise differences, define Bν (f, g) = ⟨f, (I − γPπ )g⟩ν . Then µi − µj = (I − γPπ )hij , so 1 Munw = ⟨hij , µi ⟩ν − [Bν (hij , hij )]+ . ij 4

(S69)

One-step concentrability controls the oracle candidate’s mean Bellman residual by its approximation error. Indeed, if νPπ ≪ ν and Cν,π = ∥d(νPπ )/dν∥∞ < ∞, conditional p Jensen’s inequality gives ∥Pπ f ∥2,ν ≤ p Cν,π ∥f ∥2,ν . The Bellman equation then yields ∥µk ∥2,ν ≤ (1 + γ Cν,π )∥∆k ∥2,ν . Lemma S21 (Deterministic unweighted score bounds). Suppose Condition B5 holds. Fix k ∈ [K] and κν ∈ (0, 1] such that Bν (hik , hik ) ≥ κν ∥hik ∥22,ν for every i ∈ [K]. Set bk = ∥µk ∥2,ν . Then Tiunw ≥ Munw ≥ ik

3κν ∥hik ∥22,ν − bk ∥hik ∥2,ν , 4

whereas, for every j ∈ [K], Munw kj ≤ bk ∥hkj ∥2,ν −

(S70)

κν ∥hkj ∥22,ν , 4

(S71)

and consequently Tkunw ≤

b2k . κν

(S72)

Proof. The coercivity hypothesis makes the population penalties for pairs (i, k) and (k, j) nonnegative. Using µi = µk + (I − γPπ )hik in (S69) gives Munw = ik

3 Bν (hik , hik ) + ⟨hik , µk ⟩ν . 4

Coercivity and Cauchy–Schwarz give (S70). With first index k, (S69) instead gives 1 Munw kj = ⟨hkj , µk ⟩ν − Bν (hkj , hkj ). 4 The same inequalities prove (S71). Finally, bk u − κν u2 /4 ≤ b2k /κν for every u ≥ 0, which proves (S72). Lemma S22 (Population bound for a general penalty coefficient). Suppose Condition B5 holds, and let k and κν satisfy the coercivity hypothesis of Lemma S21. For λ ∈ (0, 1), define Munw,λ := ⟨hij , µi ⟩ν − λ[Bν (hij , hij )]+ , ij Then

eiλ ∈ arg min max Munw,λ . ij i∈[K]

j∈[K]

∥µ ∥ √ k 2,ν √ . ∥Qei − Qπ ∥2,ν ≤ ∥∆k ∥2,ν + λ 2κ λ(1 − λ) ν

The coefficient of ∥µk ∥2,ν is uniquely minimized at λ = 1/4. 42

(S73)

Proof. Write u = ∥hei ,k ∥2,ν and b = ∥µk ∥2,ν . As in the proof of Lemma S21, λ

Munw,λ ≥ (1 − λ)κν ∥hik ∥22,ν − b∥hik ∥2,ν , ik

Munw,λ ≤ kj

b2 . 4λκν

The defining optimality of√eiλ therefore implies (1 − λ)κν u2 − bu ≤ b2 /(4λκν ). √ √Solving√this quadratic √inequality gives u ≤ b/{2κν λ(1 − λ)}. The triangle inequality proves (S73). Since λ(1 − λ) = 1/4 − ( λ − 1/2)2 , the coefficient is uniquely minimized at λ = 1/4. Theorem S23 (Population oracle inequality for unweighted PBV). Suppose Condition B5 holds. For any k and κν satisfying the coercivity hypothesis of Lemma S21, every population minimizer satisfies 2 ∥Qeiunw − Qπ ∥2,ν ≤ ∥Qk − Qπ ∥2,ν + ∥Qk − Bπ Qk ∥2,ν . Q κν

(S74)

Proof. Apply Lemma S22 with λ = 1/4 and use µk = Qk − Bπ Qk . For the best-candidate index k ⋆ , if ∥Qk⋆ − Bπ Qk⋆ ∥2,ν ≤ Lν ∥Qk⋆ − Qπ ∥2,ν for some Lν ∈ [0, ∞), then   2Lν π min ∥Qi − Qπ ∥2,ν . ∥Qeiunw − Q ∥2,ν ≤ 1 + Q κν i∈[K] Proposition S24 (Failure of unpenalized pairwise validation under misspecification). For every γ ∈ [0, 1) and ρ > 1, there exist a two-state MDP and three bounded candidate Q-functions satisfying Conditions A2 and B5 with κν = 1, such that the unique minimizer ei0 ∈ arg min max⟨Qi − Qj , Qi − Bπ Qi ⟩ν i∈[3]

j∈[3]

satisfies ∥Qei − Qπ ∥2,ν = ρ min ∥Qi − Qπ ∥2,ν . 0 i∈[3] Proof. Take a single-action MDP on {−1, 1} with zero rewards and transitions that draw the next state uniformly, independently of the current state. Let ν be uniform and set f (s) := s. Then Qπ = 0, Pπ f = 0, and ∥f ∥2,ν = 1. Set m := ρ(ρ + 1) and choose Q1 = f , Q2 = −ρf , and Q3 = −mf . The candidates have finite second moments, νPπ = ν, and (I − γPπ )hij = hij , verifying the stated conditions. Writing (c1 , c2 , c3 ) = (1, −ρ, −m), the unpenalized scores are ci (ci − cj ), so their row maxima are T1 = m + 1,

T2 = ρ(ρ + 1) = m,

T3 = m(m + 1).

Since m > 1, the unique minimizer is ei0 = 2. Its error is ρ, whereas the smallest candidate error is 1. Thus the error ratio is unbounded as ρ → ∞, even with κν = 1 and fixed γ. Remark S25 (L2 -normalized pairwise critics). Proposition S24 shows that unnormalized pairwise-difference critics without penalization can fail under candidate-class misspecification. A population oracle inequality can also be obtained using L2 (ν)-normalized pairwise differences, but finite-sample guarantees require additional control of empirical normalization, which can be unstable when candidates are nearly identical. To see this, define ψij := hij /∥hij ∥2,ν when ∥hij ∥2,ν > 0, and ψij := 0 otherwise. Under Conditions A2 and B5, any minimizer einorm of maxj ⟨ψij , Qi − Bπ Qi ⟩ν satisfies the population oracle bound in Theorem S23. ∥2,ν , and b := ∥Qk − Bπ Qk ∥2,ν . The score of Indeed, take k = k ⋆ and write y := ∥∆k ∥2,ν , u := ∥hei norm ,k candidate k is at most b, whereas the score of the selected candidate is at least κν u − b. Optimality therefore gives u ≤ 2b/κν , and the triangle inequality yields the stated bound. To establish a finite-sample oracle inequality with empirical normalization, one must control the empirical norms of pairwise differences relative to their population norms. This can be difficult when candidates are nearly identical, since small population norms can amplify relative estimation errors. A sufficient condition is the uniform bound ∥hij ∥∞ ≤ B∥hij ∥2,ν for every i, j ∈ [K], 43

but this condition is restrictive for flexible function classes. For example, in Sobolev-type RKHSs, interpolation inequalities typically bound the supremum norm using a fractional power of the L2 norm, rather than the linear bound required here. In contrast, unweighted PBV avoids empirical normalization through its quadratic critic penalty.

I.2. Concentration bound for the unweighted Q-function criterion Lemma S26 (Localized unweighted-score deviation). Suppose Conditions A1, B2 and B3 hold. There is a universal constant C0 > 0 such that, for every δ ∈ (0, 1) and every nonempty collection P ⊆ {1, . . . , K}2 fixed conditional on the training sample, with probability at least 1 − δ, simultaneously for all (i, j) ∈ P, s ) ( log(6|P|/δ) log(6|P|/δ) unw unw cij − Mij ≤ C0 (GQ + σQ ) ∥hij ∥2,ν . (S75) M + HQ ngb ngb Proof. Condition on the training sample, and let Pn,Q denote the empirical average over the Q-validation transitions. For a fixed ordered pair (i, j), write b ij := Pn,Q [hij (X)εi ] , L bij := Pn,Q [hij (X){hij (X) − γ(πhij )(S ′ )}] , A

Lij := Eν [hij (X)εi ] , Aij := Eν [hij (X){hij (X) − γ(πhij )(S ′ )}] .

With [x]+ := max{0, x}, b ij − 1 [A cunw bij ]+ , =L M ij 4

1 Munw = Lij − [Aij ]+ . ij 4

Since the positive-part map is 1-Lipschitz, cunw b ij − Lij | + 1 |A bij − Aij |. M − Munw ≤ |L ij ij 4 Set

µi (X) := E[εi | X],

(S76)

ξi := εi − µi (X).

By the validation setup in Section 2.1, the conditional law of (Rt , St′ ) given Ft is the MDP kernel given Xt . Conditions B2 and B3 therefore verify the conditions of Lemma S9(ii) for hij (X){µi (X) + ξi } with B = HQ ,

D = GQ ,

σ = σQ ,

v = ∥hij ∥2,ν .

Thus, outside an event of probability 6e−u ,  b ij − Lij | ≤ CM (GQ + σQ ) ∥hij ∥2,ν rg (u) + HQ rg (u)2 . |L b b

(S77)

The penalty integrand can be written as hij (X){hij (X) − γ(πhij )(S ′ )} = hij (X)(εi − εj ). Its conditional mean factor is µi − µj , bounded by 2GQ . Its centered innovation is ξi − ξj . Conditional Cauchy–Schwarz gives     n h i h io1/2 |ξi − ξj | E exp X ≤ E e|ξi |/σQ X E e|ξj |/σQ X ≤ 2. 2σQ Lemma S9(ii), with a = hij , D = 2GQ , and σ = 2σQ , therefore gives, outside an event of probability 6e−u ,  bij − Aij | ≤ 2CM (GQ + σQ ) ∥hij ∥2,ν rg (u) + HQ rg (u)2 . |A (S78) b b Apply (S77) and (S78) with u = log(12|P|/δ) and take a union bound over the two deviations and all (i, j) ∈ P. Combining the resulting bounds with (S76) proves (S75) after increasing the universal constant C0 to replace log(12|P|/δ) by log(6|P|/δ); their ratio is bounded by log(12)/ log(6) because |P|/δ ≥ 1. 44

I.3. Finite-sample oracle inequality Let C0 be the universal constant in Lemma S26, and define q 2 6C0 HQ (GQ + σQ ). CQ,unw := 2C0 (GQ + σQ ) + 3 Proof of Theorems 5.1 and S6. Localized event. Fix a comparator k satisfying the stated coercivity inequality, and define Pkunw := {(i, k) : 1 ≤ i ≤ K} ∪ {(k, j) : 1 ≤ j ≤ K}. The collection Pkunw is fixed conditional on the training sample and has at most 2K − 1 elements. By Lemma S26, with conditional probability at least 1 − δ, the localized bound holds on Pkunw with its logarithmic factor enlarged to log(12K/δ). On this event, abbreviate s log(12K/δ) u := ∥hbiunw ,k ∥2,ν , y := ∥∆k ∥2,ν , rQ := . Q ngb Also set

η := C0 (GQ + σQ ) rQ ,

v := C0 HQ (GQ + σQ ) r2Q .

Empirical comparison. Set bk = ∥µk ∥2,ν . For the selected candidate, by (S70) and the localized deviation bound, cunw ≥ 3κν u2 − {bk + η}u − v. (S79) max M biunw ,j j 4 Q For the comparator k, each population score is bounded by (S71), and the corresponding empirical deviation is bounded on the localized event. Thus, for every j, κν cunw ∥hkj ∥22,ν + v. M kj ≤ {bk + η}∥hkj ∥2,ν − 4 Maximizing the right-hand side over the nonnegative value of ∥hkj ∥2,ν yields cunw ≤ max M kj j

{bk + η}2 + v. κν

(S80)

Solving the quadratic inequality. By the defining optimality of biunw and (S79)–(S80), Q 3κν 2 {bk + η}2 u − {bk + η}u − − 2v ≤ 0. 4 κν √ √ √ Solving (S81) and using a + b ≤ a + b, we obtain √ r 2{bk + η} 2 6 v u≤ + . κν 3 κν

(S81)

Finally, the triangle inequality, κν ≤ 1, and the definitions of η, v, and CQ,unw give 2bk CQ,unw ∥∆biunw ∥2,ν ≤ y + + rQ . Q κν κν This proves the bound for any fixed comparator satisfying the coercivity inequality, since bk = ∥Qk −Bπ Qk ∥2,ν . Taking k = k ⋆ proves (S9) and the main-text guarantee. Proof of Corollary S7. All norms and inner products in this proof are under ν. Stationarity and Jensen’s inequality give ∥Pπ f ∥ ≤ ∥f ∥. Let A = I − p γPπ and Eν (f ) = ⟨f, Af ⟩. Then Eν (f ) ≥ α∥f ∥2 , where α = 1 − γ. Lemma S17, with c = γ, gives |⟨f, Ag⟩| ≤ βEν (f )∥g∥, where β = 1 + γ. Let k minimize ∥Qi − Qπ ∥, and write y = ∥Qk − Qπ ∥. Use the localized event from the proof of Theorem S6. With r = {log(12K/δ)/(ngb )}1/2 , write η = C0 (GQ + σQ )r and v = C0 HQ (GQ + σQ )r2 . The 45

Bellman equation gives µi = A∆q is nonnegative, the population score equals i . Since every population √ energy √ ⟨hij , A∆i ⟩ − Eν (hij )/4. For z = Eν (hbiunw ,k ) and b = β y + η/ α, the operator bound and localized event Q

therefore imply

cunw ≥ max M bunw j

iQ

,j

3 2 z − bz − v, 4

2 2 cunw max M kj ≤ sup{bu − u /4 + v} = b + v. j

u≥0

√ √ Empirical optimality and the quadratic formula give z ≤ 2b + (2 6/3) v. By the triangle inequality and coercivity, r ! √ r β 2η 2 6 v z y+ + . ∥∆biunw ∥ ≤ y + √ ≤ 1 + 2 Q α α 3 α α √ Substituting η, v and using α ≥ α yields the asserted bound with the stated CQ,unw .

J. Proofs for joint TA-PBV and doubly robust OPE J.1. Proof of the joint TA-PBV guarantee Proof of Theorem 5.2. Apply Theorem S3 on the shared validation trajectory with failure probability δ/2. When the initial moments are estimated empirically, m = n, gb ≤ 1, and (1 − γ)−1/2 ≤ (1 − γ)−1 allow its initial-sample term to be absorbed into the validation term. When these moments are known exactly, the initial-sample term is absent. This gives (7), where Cratio depends only on Cw and w. For each a ∈ [M ], let biQ (a) be the Q-index selected when the second-stage score uses wa . Conditional on training, every wa is fixed and independent of the validation trajectory, and Condition B4 holds with WQ = w. Apply Theorem S5 to each wa , with failure probability δ/(2M ). A union bound gives an event of probability at least 1 − δ/2 on which all M conclusions hold. Their validation rate is s s log{12K/(δ/(2M ))} log(24M K/δ) = . ngb ngb b Substitute (7) into On this event, the bound also holds for a = biw , whose selected Q-function is exactly Q. its Hellinger weight-error term and use s √ 1+ γ 1−γ 5 √ 1− γ ≥ , 1+2 . √ ≤√ 2 1− γ 1−γ Absorbing the resulting universal factors into CTA gives (8), with CTA depending only on Cw , w, HQ , GQ , and σQ . The two events intersect with probability at least 1 − δ.

J.2. Proof of the doubly robust oracle bound p Proof of Corollary S8. For this proof, set ℓ = log{12(K ∨ M )/δ}, so that ρδ = ℓ/(ngb ). Selection events. Conditions D1 and D2 permit applying Theorem S3 to the shared selection fold with failure probability δ/3. Since log(72M/δ) ≤ 2ℓ, there is an event Ew of conditional probability at least 1 − δ/3 on which ϵw + ρ δ Hν (w, b wπ ) ≲ . (S82) 1−γ For each a ∈ [M ], let biQ (a) be the index selected on Dsel when the second-stage score uses wa . Conditional on training, each wa is fixed. Condition A3 gives 0 ≤ wa ≤ w. Apply the branchwise concentration event used in the proof of Theorem S5 to each of these M fixed weights, with failure probability δ/(3M ) each. Since log(36M K/δ) ≤ 2ℓ, a union bound gives an event EQ of conditional probability at least 1 − δ/3 on which (S67) holds simultaneously for all a. It therefore holds for the selected index a = biw : q ρδ b − Qπ ) ≲ ϵQ + Hν (w, E(Q b wπ ) + √ . (S83) 1−γ 46

√ Here 1 − γ ≥ (1 − γ)/2 is used only to express the validation term in 1 − γ. Doubly robust remainder. We next express the population value error as a product of the two nuisance errors. For fixed candidates Q ∈ {Q1 , . . . , QK } and w ∈ {w1 , . . . , wM }, define the population functional Ψ(Q, w) := Ed0 [Q(X)] +

1 Eν [w(X){R + γ(πQ)(S ′ ) − Q(X)}] . 1−γ

Let ∆Q = Q − Qπ and µQ (X) := E[Q(X) − R − γ(πQ)(S ′ ) | X]. Condition B2 gives |µQ | ≤ GQ , while the Bellman equation (1) gives µQ = (I − γPπ )∆Q under dπ,γ . By Lemma S18, the occupancy identity applies to ∆Q . Hence Ψ(Q, w) − V π = Ed0 ∆Q − =

1 Eν [wµQ ] 1−γ

1 Eν [(wπ − w)µQ ]. 1−γ

The expectations are finite because µQ and w are bounded, Eν wπ = 1, and ∆Q ∈ L2 (d0 ). In particular, the bias of Ψ vanishes√if either Q = Qπ or w = wπ ; hence, Ψ is doubly robust. √ √ Put z = w − wπ . The identity w − wπ = 2 wπ z + z 2 , weighted Cauchy–Schwarz, and |µQ | ≤ GQ give 2Hν (w, wπ ) GQ 2 ∥µQ ∥2,dπ,γ + H (w, wπ ) 1−γ 1−γ ν p √ p 2 1+ γ GQ 2 Hν (w, wπ ) E(Q − Qπ ) + H (w, wπ ), ≤ 1−γ 1−γ ν

|Ψ(Q, w) − V π | ≤

(S84)

√ where A = I − γPπ , and the last step uses µQ = A(Q − Qπ ) under dπ,γ and ∥Af ∥22,dπ,γ ≤ (1 + γ)E(f ). For b w), (Q, w) = (Q, b set h = 1 − γ and ρw = Hν (w, b wπ ). On Ew ∩ EQ , equations (S82), (S83), and (S84) imply   ρw ρδ 1 ρw ϵQ + ρ2w + √ h h (ϵw + ρδ )2 (ϵw + ρδ )ρδ (ϵw + ρδ )ϵQ + + ≲ h2 h3 h5/2 ϵw ϵQ ϵ2w n ϵQ ϵw o ρ2δ ≲ + 3 + + 3 ρδ + 3 . h2 h h2 h h

b w) |Ψ(Q, b − V π| ≲

(S85)

The last inequality uses h ≤ 1 and (ϵw + ρδ )ρδ ≤ (ϵw + ρδ )2 . Evaluation error. Condition on the training sample, so that all M K candidate pairs are fixed. When the initial-state expectations are estimated empirically, Bernstein’s inequality for subexponential variables and a union bound over i ∈ [K] give, with conditional probability at least 1 − δ/6, max |Pn,0,V Qi − Ed0 Qi | ≲ ρδ + ρ2δ .

i∈[K]

(S86)

Here Condition D3 supplies the subexponential moment bound, and log(12K/δ) ≤ ℓ. When the initial-state expectations are known exactly, the left-hand side is zero. For each (a, i) ∈ [M ] × [K], set Yai,t := wa (XtV ){RtV + γ(πQi )(St′,V ) − Qi (XtV )}. Writing µi (X) = E(εi | X) and ξi = εi − µi (X), apply Lemma S9(ii) with a = wa , d = −µi , ζ = −ξi , B = w, D = GQ , σ = σQ , and v = w. Conditions D1–D2 verify the spectral-gap, envelope, and conditional noise requirements. Taking u = log(36M K/δ) and a union bound over the M K pairs gives, with conditional probability at least 1 − δ/6, max |Pn,V Yai − EYai | ≲ ρδ + ρ2δ , (S87) a∈[M ], i∈[K]

47

because log(36M K/δ) ≤ 2ℓ. Both uniform bounds therefore apply to the selected pair, even when the selection and evaluation data coincide. On the two corresponding events, by (S86) and (S87), b w)| |VbDR − Ψ(Q, b ≲

ρδ + ρ2δ . 1−γ

Adding this evaluation error to the population remainder in (S85), we obtain (S11). Here 1 − γ ≤ 1 is used only to absorb ρ2δ /(1 − γ) into ρ2δ /(1 − γ)3 . By a union bound over Ew , EQ , and the two final evaluation events, the total failure probability is at most δ/3 + δ/3 + δ/6 + δ/6 = δ, which proves the corollary.

48

Related documents

• Model Selection for Off-Policy Evaluation via Pairwise Bellman Validation#1459271
• Fitted Q-Evaluation without Bellman Completeness via Occupancy Weighting#798710
• Fitted Q-Evaluation without Bellman Completeness via Occupancy Weighting#797296
• Unifying Gradient Estimators for Meta-Reinforcement Learning via Off-Policy Evaluation#1199593
• On the Selection Stability of Stability Selection and Its Applications#1399693