Fitted Occupancy-Ratio Evaluation without Bellman Completeness Lars van der Laan Stanford University [email protected]
Nathan Kallus Netflix and Cornell University
arXiv:2607.05375v1 [stat.ML] 6 Jul 2026
Abstract Occupancy ratios correct distribution shift in offline reinforcement learning and are central to off-policy evaluation. Existing primal-dual and minimax methods typically estimate these ratios by enforcing occupancybalance moments over a critic class. We propose fitted occupancy-ratio evaluation (FORE), a fitted fixed-point method that characterizes the discounted occupancy ratio through an adjoint Bellman recursion. At each iteration, FORE solves a single-level density-ratio objective on one-step-transition data, thereby projecting the adjoint Bellman image onto a log-ratio class in Kullback–Leibler (KL) divergence. Unlike analyses of fitted Q-evaluation, which typically require value-function realizability together with Bellman completeness or projected-operator stability, our central approximation condition is just realizability of the discounted occupancy ratio itself. Under this condition, the population KL-projected recursion contracts in relative entropy toward the true ratio by virtue of the adjoint Bellman operator being a KL-contraction. For the empirical recursion, we establish finite-sample regret bounds that yield convergence in KL up to log-ratio approximation error and a statistical error governed by the complexity of the ratio hypothesis class. The fitted ratio supports direct value estimation by reward reweighting, occupancy-weighted fitted Q-evaluation, and doubly robust estimation that combines the fitted ratio with a fitted Q-function. Together, these results identify discounted occupancy-ratio realizability as a sufficient condition for offline policy evaluation without any completeness assumptions.
1. Introduction Offline policy evaluation must correct the mismatch between the distribution of observed transitions and the discounted occupancy distribution induced by a target policy. Value-based and ratio-based methods address this mismatch by estimating complementary objects. On the value-function side, fitted Q-evaluation (FQE) is the canonical fitted-iteration approach: it repeatedly regresses Bellman targets onto a value-function class to estimate the Q-function (Antos et al., 2007; Ernst et al., 2005; Lagoudakis and Parr, 2003; Le et al., 2019; Munos and Szepesvári, 2008; Riedmiller, 2005; Tosatto et al., 2017). This approximates the iteration of the composition of a projection operator with the Bellman operator. Unlike the Bellman operator alone, this composition need not be contractive: the Bellman operator and the projection are naturally controlled under different measures (van der Laan and Kallus, 2025b). Contractivity can be recovered if the Bellman image already lies in the projection image, so that the composition reduces to the Bellman operator itself. This condition is called Bellman completeness, a key assumption in analyses of FQE; alternatives include directly assuming projected-Bellman stability or a small inherent Bellman error (Amortila et al., 2020; Antos et al., 2007; Chang et al., 2022; Chen and Jiang, 2019; Foster et al., 2021; Munos and Szepesvári, 2008; Wang et al., 2021a,b). The discounted occupancy ratio is the density of the target policy’s discounted state–action occupancy measure relative to the offline data distribution. It converts offline-distribution averages into target-occupancy averages and is a central ingredient in marginalized importance sampling, 1
doubly robust estimation, stationary-distribution correction, and occupancy-weighted value methods (Gelada and Bellemare, 2019; Hallak and Mannor, 2017; Jiang and Li, 2016; Kallus and Uehara, 2020a,c, 2022; Liu et al., 2018; Sutton et al., 2016; Thomas and Brunskill, 2016; van der Laan and Kallus, 2025a,b; Xie et al., 2019; Yin and Wang, 2020). This ratio satisfies an adjoint Bellman equation, equivalently a family of balance conditions indexed by state-action test functions. This perspective gives rise to primal-dual and minimax methods that seek a ratio function minimizing empirical imbalance over a class of critic functions (Liu et al., 2018; Nachum et al., 2019a; Uehara et al., 2020, 2021). Their guarantees consequently shift the approximation burden to the coupled ratio and critic classes and require critic richness, dual realizability, or completeness conditions. The same approaches also apply to Q-learning by minimizing empirical deviations of the (non-adjoint) Bellman equation, with similar requirements for guarantees. We propose fitted occupancy-ratio evaluation (FORE), a fitted-iteration method for discounted occupancy-ratio estimation. FORE is analogous to FQE, but at each iteration it approximates the composition of a projection in Kullback–Leibler (KL) divergence with the adjoint Bellman operator. Importantly, unlike FQE, this composition combines compatible contractions, yielding convergence without any completeness condition. The method requires no separate critic class, and each iteration can be implemented with standard supervised learners, such as gradient-boosted trees or neural networks. The key approximation condition for FORE is mere realizability (or approximation) of the true discounted occupancy ratio by the hypothesis class. It does not require an adjoint Bellman completeness condition: adjoint Bellman images of arbitrary candidate ratios need not remain in, or be well approximated by, the hypothesis class. The reason is that the adjoint Bellman recursion is aligned with the KL projection geometry. The unprojected adjoint Bellman map contracts relative entropy toward the true ratio by the discount factor, and FORE projects in the same geometry. Thus, when the target ratio is realizable, the projected population operator inherits this contraction. The analysis therefore replaces closure of an entire sequence of Bellman images with direct approximation of the target fixed point. This contrasts with standard FQE. The Bellman evaluation operator is naturally stable in the target-policy occupancy norm, whereas FQE uses a projection norm under the offline data distribution. Without Bellman completeness or projected-operator stability, this norm mismatch can make the projected Bellman recursion underlying FQE unstable (Patterson et al., 2022; van der Laan and Kallus, 2025b). This helps explain why value-function realizability alone does not ensure stable FQE (Amortila et al., 2020; Foster et al., 2021; Wang et al., 2021a,b). Besides realizability, the coverage requirements for FORE are standard in offline policy evaluation: the target-relevant distributions must be absolutely continuous with bounded density ratios relative to the offline data distribution. Because FORE models density ratios through log-ratios, the analysis also assumes that the target discounted occupancy ratio is positive on the support of the offline data distribution and has an integrable logarithm. Contributions. We make four contributions. 1. We characterize the discounted occupancy ratio as the unique fixed point of an adjoint Bellman recursion and introduce FORE, a fitted method that estimates this recursion through repeated single-level KL density-ratio objectives. 2. We develop a population approximation theory based directly on occupancy-ratio realizability. The KL-projected adjoint Bellman operator contracts in relative entropy toward the true ratio, up to an approximation error determined by the log-ratio class. This result does not require an 2
adjoint Bellman completeness condition. 3. We prove finite-sample guarantees for the empirical fitted recursion. The generalized KL error decomposes into a geometrically decaying initialization term, a population log-ratio approximation term, and a statistical term governed by local Rademacher critical radii for the log-ratio class and the induced multiplier class. 4. We develop three policy-evaluation applications. The fitted ratio yields reward-reweighted value estimates, a doubly robust estimator with a product-form error bound, and an occupancy-weighted FQE procedure. For the last application, we derive bounds that separate ratio error, value-function approximation error, and finite-iteration error, without imposing Bellman completeness on the value-function class. 1.1. Related Work Off-policy evaluation and occupancy corrections. Classical off-policy evaluation uses trajectory-level or per-decision importance ratios, while doubly robust estimators combine importance weighting with value-function estimates (Jiang and Li, 2016; Thomas and Brunskill, 2016). Marginalized importance sampling avoids products of trajectory ratios by correcting marginal state or state–action occupancies (Liu et al., 2018; Xie et al., 2019; Yin and Wang, 2020). Semiparametric theory likewise identifies the occupancy ratio, together with a value function, as the pair of nuisance functions underlying efficient and doubly robust off-policy evaluation (Kallus and Uehara, 2019, 2020a,b,c,d, 2022, 2024; Uehara et al., 2022; van der Laan et al., 2025a,b,c). Occupancy and stationary-distribution corrections also appear in off-policy temporal difference learning, emphatic TD, generalized projected Bellman-error objectives, stationary-weighted FQE, and stationary-reweighted soft fitted Q-iteration (Gelada and Bellemare, 2019; Hallak and Mannor, 2017; Patterson et al., 2022; Sutton et al., 2016; van der Laan and Kallus, 2025a,b). Primal-dual and minimax ratio estimation. These methods estimate occupancy corrections by enforcing balance or stationarity restrictions through saddle-point, minimax, or temporal-difference objectives. DualDICE estimates discounted distribution corrections without behavior-policy probabilities or trajectory products (Nachum et al., 2019a). GenDICE and GradientDICE extend this perspective to stationary-distribution correction and off-policy evaluation (Zhang et al., 2020a,b). Related work develops infinite-horizon density-ratio estimators, minimax weight and value-function learners, regularized-Lagrangian formulations, confidence intervals, and regression-based variants (Che et al., 2025; Dai et al., 2020; Liu et al., 2018; Uehara et al., 2020, 2021; Yang et al., 2020). Other occupancy-correction methods use successor representations, state abstractions, or distribution matching for policy optimization, constrained control, and imitation learning (Fujimoto et al., 2021; Kim et al., 2022; Kostrikov et al., 2020; Lee et al., 2021, 2022; Ma et al., 2022; Nachum et al., 2019b; Pavse and Hanna, 2023). These procedures can also be viewed as minimax estimators of the Riesz representer of the policy-value functional (Bennett et al., 2023, 2025; Dikkala et al., 2020; van der Laan et al., 2025b). In contrast, FORE uses the adjoint Bellman identity recursively and estimates each projected image through a single-level density-ratio objective, without introducing a separate critic class. Policy evaluation and Bellman completeness. A central difficulty in offline policy evaluation with function approximation is that value-function realizability alone does not ensure stable Bellman regression under distribution shift. Analyses of FQE and fitted value iteration typically control this instability through Bellman completeness, small inherent Bellman error, or contraction of the projected Bellman operator, together with coverage or concentrability conditions relating target3
policy distributions to the offline data (Antos et al., 2007; Chen and Jiang, 2019; Foster et al., 2021; Munos and Szepesvári, 2008). In tabular models, state aggregation, and discretized representations, the required stability is built into the approximation architecture (Munos and Szepesvári, 2008; Puterman, 1994). Linear function approximation provides another route when the features are compatible with the reward, transition, and coverage structure (Lagoudakis and Parr, 2003). Minimax and adversarial Bellman-error methods replace direct Bellman regression with moment conditions evaluated against an auxiliary critic class. These approaches can avoid Bellman completeness of the value class, but their analyses instead require the critic to detect the relevant residuals, through conditions such as critic richness, dual realizability or completeness, coverage, and control of saddle-point optimization (Bennett et al., 2023, 2025; Dikkala et al., 2020; Uehara et al., 2020, 2021). Weighted TD and FQE-style methods take a complementary route: they retain fitted Bellman regression but change the projection norm using emphatic, covariate-shift, or stationary occupancy weights (Gelada and Bellemare, 2019; Hallak and Mannor, 2017; Patterson et al., 2022; Sutton et al., 2016; van der Laan and Kallus, 2025a,b). These results show that an appropriate occupancy weight can stabilize projected Bellman regression. With nonlinear function approximation, however, the weight must itself be estimated, and DICE-style or minimax estimators can reintroduce critic-side realizability or completeness conditions at this first stage. FORE addresses this ratio-estimation problem directly. Its guarantees require neither Bellman completeness of a value class, adjoint Bellman completeness of a ratio class, nor dual completeness of a critic class. The central approximation condition is instead that the discounted occupancy ratio be realizable, or well approximated, by the chosen log-ratio class. This is made possible by KL projection, which aligns with the relative-entropy contraction of the adjoint Bellman recursion. We use the resulting ratio in Section 5.2 to construct an end-to-end FORE-weighted FQE procedure. For comparison, Appendix F describes a backward-regression variant that is closer to ordinary FQE but requires adjoint Bellman completeness.
2. Setup and Adjoint Bellman Identification 2.1. MDP and target occupancy Let (S, A, P, µ0 ) be an MDP with target initial state distribution µ0 . Write X = S × A and X = (S, A). We study estimation of the discounted occupancy ratio of a target policy π relative to an offline state–action distribution ν, focusing on the setting γ < 1; the undiscounted analogue is treated in Appendix E. The method uses samples from ν and their one-step target-policy successors, but does not require an explicit behavior policy. For an action distribution η, let Pη denote the induced state–action transition kernel, Pη (ds′ , da′ | s, a) = P (ds′ | s, a)η(da′ | s′ ), and write Pπ for the kernel induced by π. For a finite signed measure µ on X , let µPπ and µPπt denote its one-step and t-step pushforwards. Let d0 (ds, da) = µ0 (ds)π(da | s) be the target initial state–action distribution. For X ∼ ν, let X + | X ∼ Pπ (· | X), and write νπ+ = νPπ for the marginal distribution of X + . (C1) One-step target coverage. The measures d0 and νπ+ are absolutely continuous with respect to ν. 4
For a discount factor γ ∈ [0, 1), the normalized discounted target occupancy measure is dπ,γ = (1 − γ)
∞ X
γ t d0 Pπt .
t=0
Under Condition C1, dπ,γ ≪ ν. Our goal is to estimate the state–action occupancy ratio ωπ,γ =
ddπ,γ . dν
This ratio is useful for policy evaluation because, for any integrable reward function r, (
Vπ (r) := Ed0 ,Pπ
(1 − γ)
∞ X
)
γ r(Xt )
= Edπ,γ {r(X)} = Eν {ωπ,γ (X)r(X)},
t
t=0
where the first expectation is over trajectories {Xt }t≥0 with X0 ∼ d0 evolving according to Pπ . 2.2. Adjoint Bellman identification The discounted occupancy measure satisfies the Bellman equation dπ,γ = (1 − γ)d0 + γdπ,γ Pπ .
(1)
Taking Radon–Nikodym derivatives in (1) gives ωπ,γ = (1 − γ)ω0 + γ
d{(ωπ,γ ν)Pπ } ; dν
ω0 :=
dd0 . dν
Thus, for any ω such that (ων)Pπ ≪ ν, define the adjoint Bellman operator (Uehara et al., 2021) d{(ων)Pπ } . dν
Bπγ ω = (1 − γ)ω0 + γ
Then the occupancy ratio is characterized by the fixed-point equation ωπ,γ = Bπγ ωπ,γ .
(2)
Although Bπγ ω is generally not available pointwise, its action against critic functions can be evaluated from one-step transitions. For any measurable f for which the expectations exist, Eν {(Bπγ ω)(X)f (X)} = (1 − γ)Ed0 {f (X)} + γEν {ω(X)f (X + )},
(3)
where X + ∼ Pπ (· | X). At the fixed point, this becomes the occupancy Bellman moment identity h
i
Eν ωπ,γ (X){f (X) − γf (X + )} = (1 − γ)Ed0 {f (X)}.
(4)
Minimax occupancy-balancing methods (Liu et al., 2018; Nachum et al., 2019a; Uehara et al., 2020, 2021) estimate a ratio function by making violations of (4) small uniformly over a critic class: n
h
io
arg min sup (1 − γ)Ed0 {f (X)} − Eν ω(X){f (X) − γf (X + )} ω∈W
f ∈F
.
(5)
Here f ∈ F acts as a critic for violations of the adjoint Bellman balance equations. To make this into an estimator, one replaces true expectations with empirical ones and also regularizes ω and/or 5
f . This approach generally requires that the critic class contain witnesses for the adjoint Bellman residuals generated by candidate weights. For example, Uehara et al. (2021) require a completeness condition of the form {Bπγ ω − ω : ω ∈ W} ⊆ cF for some scaling c > 0, which, combined with ωπ,γ ∈ W, ensures that ωπ,γ is in the argmin set in (5). This completeness condition is similar to Bellman completeness, but using the adjoint Bellman operator and with the critic class allowed to be different from the hypothesis class. Nonetheless it can be quite restrictive. FORE takes a complementary fixed-point view. Instead of minimizing a worst-case balance residual, it iterates the adjoint Bellman map to reach the fixed point. The moment identity (3) provides an estimable loss for each KL-projected update.
3. FORE: Fitted Occupancy-Ratio Evaluation The adjoint Bellman identification suggests estimating the discounted occupancy ratio by iterating the adjoint Bellman map. In general state-action spaces, however, the exact image Bπγ ω is not available as a pointwise density ratio. FORE addresses this by replacing each exact Bellman image with its KL projection onto a tractable normalized ratio class. The construction rests on two population facts: the exact adjoint Bellman map is contractive in relative entropy, and the corresponding KL projection can be written using only initial-state moments and one-step target-policy transitions. 3.1. KL contraction of the adjoint Bellman operator We first establish the population stability that makes the fitted iteration well posed. Let ∆ν = {ω ≥ 0 : Eν ω = 1},
ω(X) e Dν (ω∥ω ) = Eν ω(X) log . e (X) ω
e ) = DKL (ων∥ω e ν), where DKL denotes the KL divergence between measures. Starting Thus Dν (ω∥ω from any ω (0) ∈ ∆ν , the exact adjoint Bellman iteration is
ω (k+1) = Bπγ ω (k) ,
k = 0, 1, . . . .
The next lemma shows that this exact adjoint Bellman iteration contracts relative entropy to the target ratio. Lemma 3.1 (KL contraction of the adjoint Bellman operator). Suppose Condition C1 holds and e ∈ ∆ν , γ ∈ [0, 1). Then, for any ω, ω e ) ≤ γDν (ω∥ω e ). Dν (Bπγ ω∥Bπγ ω
Consequently, for any ω ∈ ∆ν with Dν (ω∥ωπ,γ ) < ∞, Dν ((Bπγ )k ω∥ωπ,γ ) ≤ γ k Dν (ω∥ωπ,γ ),
k ≥ 0.
Proof sketch. By joint convexity of KL and the data processing inequality for the Markov kernel Pπ (Cover and Thomas, 2006), e ) = DKL {(1 − γ)d0 + γ(ων)Pπ ∥ (1 − γ)d0 + γ(ω e ν)Pπ } Dν (Bπγ ω∥Bπγ ω e ν)Pπ } ≤ (1 − γ)DKL (d0 ∥d0 ) + γDKL {(ων)Pπ ∥(ω e ν)Pπ } = γDKL {(ων)Pπ ∥(ω e ν) ≤ γDKL (ων∥ω e ). = γDν (ω∥ω
The exact adjoint Bellman iteration is infeasible because we do not know Bπγ and we cannot approximate it uniformly well over the unrestricted ratio space ∆ν . 6
3.2. KL-projected Bellman updates We now restrict to a hypothesis class of weights: given a hypothesis class H of log-ratios, let W = {ωh : h ∈ H},
ωh (x) = exp{h(x) − Λν (h)},
Λν (h) = log Eν eh(X) .
The log-partition term Λν (h) normalizes each candidate so that Eν {ωh (X)} = 1 and W ⊂ ∆ν . For u ∈ ∆ν , define the KL projection onto W by ΠKL W u ∈ arg min Dν (u∥v), v∈W
whenever the minimizer exists. The population-level KL-projected adjoint Bellman operator is the composition KL π π TKL W ω = ΠW Bγ ω ∈ arg min Dν (Bγ ω∥ω̃). ω̃∈W
Starting from any ω (0) ∈ W, the exact KL-projected adjoint Bellman iteration is (k) ω (k+1) = TKL , W ω
k = 0, . . . , K − 1.
(6)
Although Bπγ ω is generally not available pointwise, the following lemma shows that its KL projection onto W, TKL W ω, can be learned from transition-data moments using supervised learning. Lemma 3.2 (KL projection loss). Suppose Condition C1 holds. For any ω ∈ ∆ν , the KL projection of Bπγ ω onto W is obtained by solving n
o
arg min Dν (Bπγ ω∥ωh ) = arg min Λν (h) − (1 − γ)Ed0 {h(X)} − γEν {ω(X)h(X + )} , h∈H
h∈H
where X + ∼ Pπ (· | X). The contraction argument in Lemma 3.1 is not specific to KL: by joint convexity and data processing (Cover and Thomas, 2006; Raginsky, 2014), the adjoint Bellman map is a contraction with respect to any f -divergence. KL is used because, for the normalized exponential ratio class, its projection reduces to the single-level loss in Lemma 3.2. 3.3. Empirical FORE algorithm We now turn the exact KL-projected adjoint Bellman iteration into an estimator. Lemma 3.2 provides the bridge: each KL-projected step depends only on the initial moment Ed0 {h(X)}, the one-step moment Eν {ω(X)h(X + )}, and the normalizing log-partition function. Each quantity has a direct sample analogue. Suppose we observe one-step transitions Xi = (Si , Ai ) ∼ ν, Si′ ∼ P (· | Xi ), i = 1, . . . , n. For each + + 1 ′ ′ b transition, draw A+ i ∼ π(· | Si ) and set Xi = (Si , Ai ). Let P0 h denote an estimator of Ed0 {h(X)}, b where d0 is the target initial state-action distribution, with P0 1 = 1. For example, if initial samples 0 ∼ d are available, one may take P b0 h = m−1 Pm h(X 0 ). Alternatively, if the X10 ∼ d0 , . . . , Xm 0 i=1 i state marginal of ν equals the target initial state distribution µ0 , one may draw Aπi ∼ π(· | Si ) and P take Pb0 h = n−1 ni=1 h(Si , Aπi ). 1
If A is discrete, one can replace h(Xi+ ) everywhere by h(Si′ , a)π(a | Si′ ). Alternatively, one can sample a∈A Pm +,j ′ 1 Ai ∼ π(· | Si ) multiple times, for j = 1, . . . , m, and replace h(Xi+ ) everywhere by m h(Xi+,j ), or by any j=1 other unbiased estimator of the conditional expectation. This reduces the conditional Monte Carlo variance but does not affect the rates.
P
7
Algorithm 1 FORE: Fitted Occupancy-Ratio Evaluation Require: Offline transitions {Xi = (Si , Ai ), Si′ }ni=1 , initial-moment estimator Pb0 , target policy π, discount γ, function class H, iteration count K + + + 1: Draw Ai ∼ π(· | Si′ ) and set Xi = (Si′ , Ai ), i = 1, . . . , n (0) b (x) ≡ 1 2: Initialize ω 3: for k = 0, . . . , K − 1 do 4: Compute n b (k) (Xi )h(Xi+ ) 1X n−1 ni=1 ω eh(Xi ) − (1 − γ)Pb0 h − γ P b (k) (Xi ) n i=1 n−1 ni=1 ω
!
( b h k+1 ∈ arg min log h∈H
5:
P
)
.
Set b (k+1) (x) = ω
ebhk+1 (x) 1 Pn
n
bhk+1 (Xi ) i=1 e
.
6: end for
b (K) Ensure: Occupancy-ratio estimate ω
The resulting estimator replaces the population moments in Lemma 3.2 by sample averages and normalizes each exponential update empirically. Algorithm 1 states this fitted recursion, initialized b (0) ≡ 1. The objective function at ω b (h) − (1 − γ)Pb h − γ n b L(h; ω) = Λ ν 0
−1 Pn ω(X )h(X + ) i i=1 i P , n−1 ni=1 ω(Xi )
( b (h) = log Λ ν
n 1X eh(Xi ) n i=1
)
is convex in h. Thus, for a linear hypothesis class, the objective remains convex in the linear coefficients. For nonlinear classes, one can use batched stochastic gradients by writing the empirical log partition in variational form, n 1X eh(Xi )−a . a−1+ n i=1
)
( b (h) = inf Λ ν
a∈R
For a parametrized class {hθ : θ ∈ Θ}, a transition batch {(Xi , Xi+ )}bi=1 , and an initial-state batch {Xi0 }bi=1 , the corresponding stochastic gradient in (θ, a) is
b b 1X 1X hθ (Xi )−a e ∇ h (X ) − (1 − γ) ∇θ hθ (Xi0 ) − γ i θ θ b b i=1 i=1
b 1X 1− ehθ (Xi )−a b i=1
b (k) (Xi )∇θ hθ (Xi+ ) i=1 ω Pb (k) (X ) b ω i i=1
Pb
.
b (k) , after one or a few batched gradient steps, to the current empirically One may also update ω P h (x) h (X ) θ b h (x) := e b normalized ratio ω /{n−1 ni=1 e bθ i }, rather than waiting for convergence of each b θ iteration, as in practical neural fitted value iteration (Mnih et al., 2013). Regularization, such as a Tikhonov penalty, can be added to the same objective.
4. Ratio-approximation Guarantees for FORE This section establishes guarantees for how well FORE approximates ωπ,γ in KL-divergence. 8
4.1. KL-projected fixed-point recursion We begin by analyzing the idealized population version of FORE where we iterate TKL W , as given by (6). Then we compose this analysis with the sample-based approximation errors. We leverage the following conditions in addition to Condition C1: (C2) Closed convex log-ratio class. The class H is convex, closed, and totally bounded as a subset of L2 (ν). (C3) Log square-integrability. The target ratio satisfies ωπ,γ > 0 ν-a.e. and log ωπ,γ ∈ L2 (ν). (C4) Bounded log class and one-step coverage. There are finite constants R, B0 , B+ such that sup ∥h − Eν {h(X)}∥∞ ≤ R,
∥ω0 ∥∞ ≤ B0 ,
h∈H
dνπ+ ≤ B+ dν ∞
Condition C2 is mild for finite-dimensional linear classes: if hθ is continuous as a map into L2 (ν) and θ ranges over a compact convex set, then H is convex, closed, and totally bounded. Condition C3 is the corresponding regularity condition for the target log-ratio. Since FORE models density ratios through log-ratios, the target ratio must be positive on the support of the offline data distribution and have a square-integrable logarithm, so that the KL approximation floor can be quadratic in the log-ratio approximation error. This positivity requirement is relative to the offline data distribution: if the target occupancy support is known, one may instead work with the restriction of ν to that support, so that ωπ,γ > 0 holds on the working space. Condition C4 has two roles. First, the bounded centered log class uniformly bounds the normalized ratios ωh , controls empirical-process envelopes, and yields local quadratic curvature of the excess KL loss. Second, the density-ratio bounds ω0 ≤ B0 and dνπ+ /dν ≤ B+ impose coverage only on target-relevant state-action regions, as in standard analyses of value-based offline RL and FQE (Munos and Szepesvári, 2008; Xie et al., 2022). They require the initial and one-step distributions in the adjoint Bellman recursion to have bounded densities relative to the offline data distribution. Define the approximation error by εKL := inf ∥log ωπ,γ − log v∥L2 (ν) . v∈W
In particular, if we just have realizability ωπ,γ ∈ W, then εKL = 0. Theorem 4.1 (KL-projected fixed-point recursion). Let γ ∈ [0, 1). Suppose Conditions C1-C4 hold. Then there is a finite constant Capp , depending only on the constants in Condition C4, such that, for every ω ∈ W, 2 Dν (TKL W ω∥ωπ,γ ) ≤ γDν (ω∥ωπ,γ ) + Capp εKL . (k) , k = 0, . . . , K − 1, satisfy Consequently, for any ω (0) ∈ W, the iterates defined by ω (k+1) = TKL W ω
Dν (ω (K) ∥ωπ,γ ) ≤ γ K Dν (ω (0) ∥ωπ,γ ) + Capp
1 − γK 2 ε . 1 − γ KL
Proof sketch in the realizable case. Assume ωπ,γ ∈ W. Since W is a normalized exponential family with convex natural-parameter space, the KL projection satisfies the Pythagorean inequality for information projections (Banerjee et al., 2005; Csiszár, 1975). Thus π π KL Dν (TKL W ω∥ωπ,γ ) ≤ Dν (Bγ ω∥ωπ,γ ) − Dν (Bγ ω∥TW ω)
≤ Dν (Bπγ ω∥ωπ,γ ) = Dν (Bπγ ω∥Bπγ ωπ,γ ) ≤ γDν (ω∥ωπ,γ ), 9
where the last inequality is Lemma 3.1. Theorem 4.1 gives a KL error recursion for the population KL-projected fixed-point iteration. Each step decomposes into the γ-contraction of the exact adjoint Bellman map toward the target occupancy ratio and a KL projection error. Importantly, this projection error is quadratic in the best L2 (ν) log-ratio approximation error for the fixed point ωπ,γ , not in an approximation error for Bellman images of arbitrary candidate ratios. In particular, if ωπ,γ ∈ W, then the projection error vanishes and the bound reduces to Dν (ω (K) ∥ωπ,γ ) ≤ γ K Dν (ω (0) ∥ωπ,γ ). This is the main distinction from standard FQE/FVI analyses. In those settings, the standard value Bellman operator is contractive in the stationary target-policy norm, but the population algorithm composes this operator with a projection map, typically an L2 projection under the offline data distribution (Munos and Szepesvári, 2008; van der Laan and Kallus, 2025b). Because of this norm mismatch, the projection can prevent the projected recursion from inheriting the stability of the Bellman fixed point. Stability therefore typically requires Bellman completeness, approximate Bellman completeness, or a small inherent Bellman error; these conditions ensure that Bellman images of functions in the approximation class remain close to the class (Chen and Jiang, 2019; Foster et al., 2021; Munos and Szepesvári, 2008). By contrast, FORE composes the adjoint Bellman operator with a KL projection map. The adjoint Bellman step contracts relative entropy toward ωπ,γ , and the projection step uses the same KL loss. The projection error is controlled by how well the ratio class approximates ωπ,γ , rather than by a global inherent adjoint Bellman error such as π e supω∈W inf ωe∈W Dν Bγ ω ω . Thus, the analysis does not require the ratio class to be closed under adjoint Bellman updates. 4.2. Finite-sample error bounds We next incorporate sampling error into Algorithm 1. The theorem below analyzes the exact-ERM fitted recursion with the initial moment estimated from an independent sample. For the finite-sample statement, let X10 , . . . , Xn0 be iid samples from d0 , independent of a transition P iid sample with Xi ∼ ν and Si′ | Xi ∼ P (· | Xi ). Apply Algorithm 1 with Pb0 h = n−1 ni=1 h(Xi0 ) and b (0) , . . . , ω b (K) . Each output is normalized exact ERM at each fitted step. This produces iterates ω under the empirical offline data distribution. Since it need not integrate to one under ν, we measure its error using the generalized KL divergence Dνgen (f ∥g) = Eν
f (X) f (X) log − f (X) + g(X) . g(X)
This reduces to Dν (f ∥g) when both arguments integrate to one under ν, that is, f, g ∈ ∆ν . (C5) Target lower bound. There exists m⋆ > 0 such that ωπ,γ (x) ≥ m⋆ for ν-almost every x. Condition C5 strengthens Condition C3 only by imposing a uniform lower bound on the target occupancy ratio. It does not require ωπ,γ to be bounded above. The statistical error is governed by the local complexity of the log-ratio class and by the multiplier class induced by the Bellman moment terms. For a class G of square-integrable functions under a distribution P , define the local Rademacher complexity (Bartlett et al., 2005) Rn (G, r; P ) = EZ,σ
sup
g∈G: ∥g∥L2 (P ) ≤r
10
n 1X σi g(Zi ) , n i=1
where Z1 , . . . , Zn ∼ P are independent draws, and σ1 , . . . , σn are independent Rademacher variables. Let H◦ = {h − Eν {h(X)} : h ∈ H}, H∆ = {h1 − h2 : h1 , h2 ∈ H◦ }. Let Qν,∆ denote the distribution of (X, X) with X ∼ ν, and let Qν,π denote the distribution of (X, X + ) with X ∼ ν and X + | X ∼ Pπ (· | X). Define the multiplier class n
o
G× = (x, x+ ) 7→ f (x)h∆ (x+ ) : f ∈ W, h∆ ∈ H∆ . Define Cn (r) = max Rn (H∆ , r; ν), Rn (H∆ , r; d0 ), Rn (G× , r; Qν,∆ ), Rn (G× , r; Qν,π ) . Define the critical radius (Wainwright, 2019)
n
o
rn,fit = n−1/2 ∨ inf r > 0 : Cn (r) ≤ r2 .
(7)
Theorem 4.2 (Fitted FORE with empirical normalization). Let γ ∈ [0, 1). Assume Conditions C1, b (k) }K C2, C4, C3, and C5, and assume 0 ∈ H. Let {ω k=0 be the fitted FORE iterates defined (0) b by Algorithm 1, initialized at ω ≡ 1. Then, with probability at least 1 − δ, for a constant Cfit = Cfit (R, B0 , B+ , m⋆ ) < ∞, b (K) ∥ωπ,γ ) ≤ Cfit Dνgen (ω
1+γ 2
K
b (0) ∥ωπ,γ ) + Dνgen (ω
Cfit 2 Cfit log(1/δ) εKL + r2n,fit + . 2 1−γ (1 − γ) n
Bound terms. This bound decomposes the error into three terms: the fixed-point error of K iterations of the idealized population iteration, the squared L2 (ν) log-ratio approximation error for ωπ,γ , and the statistical error of estimating the idealized population iteration using data. The first term is negligible even for moderate K. For example, any K ≥ log n/ log(2/(1 + γ)) ensures this term is O(1/n). The second term crucially only depends on how well our hypothesis class W approximates ωπ,γ , not how well we approximate every iteration. This is exactly how our bounds are distinguished from (approximate) Bellman completeness. The third term is a standard statistical error for empirical risk minimization and we instantiate bounds on it for specific function classes below. Notice that unlike some analyses of fitted iterations (e.g. Chang et al., 2022; Munos and Szepesvári, 2008) we avoid splitting the data into K samples and needing to balance the number of iterations and the amount of data available for statistical estimation. Following Hu et al. (2025); van der Laan and Kallus (2025b), we control this by using a uniform statistical error, which is the reason for introducing the function class G× . Horizon dependence. In long-horizon value estimation, the powers of (1 − γ)−1 determine how the generalized-KL error bound scales with the effective horizon. The deterministic approximation term ε2KL /(1 − γ) retains the population horizon factor from Theorem 4.1, whereas the finite-sample error (r2n,fit + n−1 log(1/δ))/(1 − γ)2 pays one additional factor of (1 − γ)−1 due to the propagation of statistical error across iterations. As shown in the next section, the policy-value bounds depend on the square root of the generalized-KL ratio error. Thus, the statistical term has the familiar (1 − γ)−1 value-level horizon dependence of FQE, while the deterministic approximation term for √ FORE has the more favorable εKL / 1 − γ value-scale contribution. This favorable dependence for the approximation term contrasts with standard FQE bounds under approximate Bellman completeness, where inherent Bellman error is propagated through the Bellman recursion and appears with (1 − γ)−1 dependence at the value-error scale (Munos and Szepesvári, 2008).
11
Bounds on statistical error for specific function classes. The key statistical term in Theorem 4.2 is the critical radius rn,fit . We next discuss bounds for specific choices of our hypothesis class H. • Linear function classes. If H ⊆ {x 7→ β0 + β ⊤ ϕ(x)} where ϕ : X → Rd , then Corollary C.11 in the appendix establishes that d log(n) r2n,fit ≲ . n • Nonparametric function classes. If the hypothesis class H has a finite uniform entropy integral, then Corollary C.10 bounds rn,fit by the entropy-based critical radius associated with H (van der Laan, 2026; van der Vaart and Wellner, 2011). For bounded Hölder log-ratio balls and Sobolev balls in dimension d and smoothness s > d/2, this gives (Nickl and Pötscher, 2007) r2n,fit ≲ n−2s/(2s+d) .
5. Applications to Policy Evaluation The preceding sections focus on estimating the discounted occupancy ratio ωπ,γ = ddπ,γ /dν. This ratio can be used to evaluate any target-occupancy functional. For any g ∈ L2 (dπ,γ ), Ψπ (g) := Edπ,γ {g(X)} = Eν {ωπ,γ (X)g(X)}. Thus, a single ratio fit can evaluate rewards, costs, feature moments, and visitation probabilities under the target discounted occupancy. b (Kω ) denote the fitted FORE estimate from Section 4.2, and define Let ωfit := ω
1 εKL + rn,fit + EFORE := √ 1−γ 1−γ
s
log(1/δ) , n
∥g∥2⋆ := Edπ,γ {g(X)2 }.
Corollary 5.1 (Target-occupancy functional bound). Suppose the conditions of Theorem 4.2 hold, log n and suppose Kω ≥ log{2/(1+γ)} . Then, with probability at least 1 − δ, there is a finite constant Ceval , depending only on the constants in Conditions C4 and C5, such that sup |Eν {ωfit (X)g(X)} − Ψπ (g)| ≤ Ceval EFORE .
∥g∥⋆ ≤1
Thus the estimated functional g 7→ Eν {ωfit (X)g(X)} converges to the target occupancy functional g 7→ Edπ,γ {g(X)} in operator norm on L2 (dπ,γ ), at rate EFORE . The remainder of this section specializes Corollary 5.1 to policy-value estimation. We first combine FORE with a fitted Q-function to obtain a doubly robust estimator, and then use the FORE ratio as the projection weight in fitted Q-evaluation. 5.1. Doubly robust policy-value estimation Let Y be a reward observed with X, and define r(x) := E(Y | X = x). For policy-value estimation, assume r ∈ L2 (dπ,γ ) and take g = r, so that the normalized discounted value is Vπ (r) = Edπ,γ {r(X)} = Eν {ωπ,γ (X)r(X)} = E{ωπ,γ (X)Y }, where the last expectation is under the offline reward distribution. The plug-in estimator based on ωfit uses the sample analogue of this identity. We can also combine an estimated ratio with an 12
estimated Q-function through the standard doubly robust Bellman-residual correction (Jiang and Li, 2016; Kallus and Uehara, 2020c, 2022; van der Laan et al., 2025b). Define the policy-evaluation Bellman operator by T π Q = r + γPπ Q,
(Pπ Q)(x) = E{Q(X + ) | X = x},
where X + = (S + , A+ ) is generated by the transition distribution and target policy π. The target Q-function is the fixed point Qπ = T π Qπ , and Vπ (r) = (1 − γ)Ed0 {Qπ (X)}. For any weight ω and function Q, define the doubly robust functional ΨDR (ω, Q) = (1 − γ)Ed0 {Q(X)} + Eν [ω(X){T π Q(X) − Q(X)}] . The one-sided estimators are recovered by setting Q = 0, which gives ΨDR (ω, 0) = Eν {ω(X)r(X)}, or by setting ω = 0, which gives ΨDR (0, Q) = (1 − γ)Ed0 {Q(X)}. Theorem 5.2 (Doubly robust value bound). Suppose the conditions of Corollary 5.1 hold, and let Q ∈ L2 (dπ,γ ). Then, with probability at least 1 − δ, there is a finite constant Cχ , depending only on the constants in Conditions C4 and C5, such that |ΨDR (ωfit , Q) − Vπ (r)| ≤ Cχ EFORE ∥T π Q − Q∥⋆ . The identity yields double robustness: the value error vanishes if either ω = ω π or Q = Qπ , and otherwise it is bounded by the product of the ratio error and the Bellman residual. By Lemma D.2, √ ∥T π Q − Q∥⋆ ≤ (1 + γ)∥Q − Qπ ∥⋆ . Hence the doubly robust error is controlled, up to constants, by EFORE ∥Q − Qπ ∥⋆ . In practice, the population averages in ΨDR are replaced by sample averages. A plug-in estimator evaluates the fitted nuisance functions in the empirical functional: n
b DR = (1 − γ) Ψ
n 0 n o X 1 X ′ b b b 0) + 1 b (Xi ) Yi + γ(π Q)(S ω Q(X i ) − Q(Xi ) , i n0 i=1 n i=1
where Xi0 ∼ d0 , Xi = (Si , Ai ), Si′ is the observed next state, and Yi is the observed reward. Here R (πQ)(s) = Q(s, a)π(da | s) denotes the target-policy average. A natural approach is to estimate Q by fitted Q-evaluation. With nonlinear function approximation, however, standard convergence guarantees for FQE typically require Bellman completeness or related projected-operator stability conditions (Munos and Szepesvári, 2008). The next subsection uses the FORE ratio to stabilize FQE and obtain guarantees for the fitted Q-function. 5.2. Occupancy-weighted FQE without Bellman completeness Occupancy-weighted FQE first estimates the discounted occupancy ratio using FORE and then uses the fitted ratio ωfit as a fixed projection weight in fitted Q-evaluation. The resulting Bellman regressions are carried out in an estimated target-occupancy norm, rather than a projection norm under the offline data distribution. This gives a discounted analogue of stationary-weighted FQE and can restore contraction of the projected Bellman equation without Bellman completeness (Patterson et al., 2022; van der Laan and Kallus, 2025a,b). Let Q be a closed convex subset of L2 (dπ,γ ). For a nonnegative weight ω, define TQ,ω Q := ΠQ,ω T π Q,
ΠQ,ω g ∈ arg min Eν {ω(X)(g(X) − q(X))2 }. q∈Q
13
Let TQ,⋆ := TQ,ωπ,γ denote the oracle projected Bellman operator based on the discounted occupancy √ ratio ωπ,γ . Appendix D.1 shows that TQ,⋆ is a γ-contraction in ∥ · ∥⋆ . Let QQ,⋆ denote its unique fixed point. FORE-weighted FQE replaces the oracle weight ωπ,γ by the fitted ratio ωfit and iterates Q(j+1) = TQ,ωfit Q(j) = ΠQ,ωfit T π Q(j) ,
j = 0, . . . , KQ − 1.
Following van der Laan and Kallus (2025b), the effect of this replacement is controlled by the Bellman-projection error εBell := sup
sup
Q∈Q h∈Q−Q: ∥h∥⋆ ≤1
∥{T π Q − TQ,⋆ Q}h∥⋆ .
This error is zero under Bellman completeness: if T π Q ∈ Q, then TQ,⋆ Q = T π Q for every Q ∈ Q. (C6) Bounded target occupancy ratio. There exists M⋆ < ∞ such that ∥ωπ,γ ∥∞ ≤ M⋆ . Theorem 5.3 (FORE-weighted projected FQE). Let Q(0) ∈ Q. Suppose the conditions of Corollary 5.1 and Condition C6 hold. Then, with probability at least 1 − δ, there is a finite constant Cχ , depending only on the constants in Conditions C4, C5, and C6, such that ∥Q(KQ ) − Qπ ∥⋆ ≤ γ KQ /2 ∥Q(0) − QQ,⋆ ∥⋆ +
1 1 − γ KQ /2 √ Cχ εBell EFORE + √ inf ∥q − Qπ ∥⋆ . 1− γ 1 − γ q∈Q
The bound separates three sources of error: finite FQE iteration, use of the fitted ratio ωfit rather than the oracle occupancy ratio, and approximation bias of the oracle projected Bellman fixed point. The plug-in weight error is controlled by the product εBell EFORE , where EFORE is the fitted FORE error and εBell is the Bellman-projection error. Under Bellman completeness, this term vanishes; otherwise, the effect of ratio estimation is attenuated by the size of εBell . The oracle √ approximation bias is controlled by (1 − γ)−1 inf q∈Q ∥q − Qπ ∥⋆ . For linear or affine value classes, Lemma D.4 improves this to (1 − γ)−1/2 inf q∈Q ∥q − Qπ ∥⋆ (Tsitsiklis and Van Roy, 1997), matching the value-level horizon dependence of FORE in Theorem 4.2. A fully empirical implementation incurs an additional statistical error term controlled by the complexity of the optimization class Q; see van der Laan and Kallus (2025b) for details. Combining this FQE bound with Theorem 5.2 yields the following value bound. Corollary 5.4 (FORE-weighted doubly robust value bound). Under the conditions of Theorems 5.2 and 5.3, suppose KQ is chosen so that the finite-iteration term in Theorem 5.3 is negligible. Then, with probability at least 1 − δ, εBell EFORE 1 ) − Vπ (r) ≤ CDR EFORE + √ √ inf ∥q − Qπ ∥⋆ , 1− γ 1 − γ q∈Q "
ΨDR (ωfit , Q
(KQ )
#
with a finite constant CDR depending only on the constants in Conditions C4, C5, and C6. Thus, once the fitted-Q iteration term is negligible, the value error is the sum of a second-order √ 2 ratio-estimation term, εBell EFORE /(1 − γ), and the product of the FORE ratio error with the √ value-class approximation error, EFORE inf q∈Q ∥q − Qπ ∥⋆ /(1 − γ). If Qπ ∈ Q, the approximation term vanishes; if the class is Bellman complete, then εBell = 0.
14
6. Numerical Experiments The theory separates two requirements in offline policy evaluation: realizability of Qπ in a value class and representability of the discounted occupancy ratio in a density-ratio class. We use two examples to isolate this distinction. In both examples, Qπ belongs to the fitted value class, but linear FQE can be unstable because its Bellman update is projected in the offline data norm and the class is not Bellman complete. By contrast, log-linear FORE remains stable when the ratio class contains the true discounted occupancy ratio, even though the class is not adjoint Bellman complete. As occupancy-estimation baselines, we compare FORE with DualDICE (Nachum et al., 2019a) and minimax weight learning (MWL) (Uehara et al., 2020), using the same ratio class and favorable tuning of the critic classes. We also use the fitted FORE ratio to construct a FORE-reweighted FQE baseline, which changes only the projection distribution in FQE. 6.1. Baird-style finite MRP Our first example is a Baird-style finite MRP based on the star-shaped off-policy counterexample of Baird (1995). The state space has six symmetric upper states and one lower state. We specify a target transition kernel, an offline data distribution, and a one-dimensional feature ϕ, with ϕ(x) = 0.1 on each upper state and ϕ(x) = 1 on the lower state. The discounted occupancy ratio is exactly represented by a one-parameter normalized log-linear class: ωπ,γ (x) =
0.2211,
x upper,
15.7987,
x lower.
To illustrate the role of the occupancy ratio in stabilizing FQE, rewards are chosen from the Bellman equation r = ϕ − γP ϕ. Hence the target value function is realizable in the scalar class qβ (x) = βϕ(x), with q π = ϕ, and the policy value is 0.1. Figure 1 illustrates the population recursions. The population FORE KL recursion converges to the true ratio. In contrast, under the offline data distribution, the projected linear FQE recursion has scalar multiplier 2.103, so coefficient errors are amplified across iterations. Using the FORE ratio as the FQE projection weight changes this multiplier to 0.801. Tabular FQE is included as a Bellman-complete benchmark, for which the projected Bellman operator has contraction multiplier γ = 0.95.
Absolute value error
107 103 10 1
linear FQE multiplier = 2.1
10 5
FORI-weighted multiplier = 0.801
10 9
Occupancy ratio error
Fitted value recursion linear FQE FORI tabular FQE (Bellman complete) FORI-reweighted FQE
1011
10 13 0
5
10
15
20 25 Iteration
30
35
40
Occupancy ratio recursion
101 10 1 10 3 10 5 10 7 10 9 10 11 10 13 10 15
FORI
FORI multiplier = 0.1425
0
5
10
15
20 25 Iteration
30
35
40
Figure 1: Baird-style finite MRP. The left panel shows policy-value error for linear FQE, direct FORE, tabular FQE, and FORE-reweighted FQE. The right panel shows the FORE occupancy-ratio error in L1 (ν).
15
6.2. Linear-Gaussian policy evaluation Our second example is a continuous linear-Gaussian policy-evaluation problem with X = (S, A) ∈ R2 . Offline samples are drawn from ν = N (0, Σb ), where Σb = diag(1.5, 0.4). Under the target policy, S + = 0.7S + 0.5A + εs ,
A+ = −0.8S + + εa ,
with Gaussian noise. The initial distribution is the target stationary distribution, so the discounted occupancy distribution is Gaussian and the true density ratio is exponential quadratic. We write h⋆ for the log-density ratio, up to an additive constant, and use the normalized log-linear class with sufficient statistics (h⋆ , s, a) for FORE, MWL, and DualDICE. This class contains the target ratio but is not closed under the target transition or the corresponding adjoint Bellman update. Rewards are chosen from the Bellman equation. Specifically, we take r = q −γP q, with q quadratic in a, so that Qπ = q belongs to a three-dimensional value class of the form {β0 q + β1 s + β2 a : β ∈ R3 }. Thus the value function is realizable. However, the class is not Bellman complete, because P q contains the quadratic directions s2 and sa, which are missing from the value class. At the population level, the projected linear FQE recursion under the offline data distribution is expansive, with dominant iteration multiplier 1.22. By contrast, the FORE ratio recursion is contractive, with multiplier 0.086. Reweighting FQE by the resulting occupancy ratio also makes the projected FQE recursion contractive, with multiplier 0.68. Finite-sample runs use n ∈ {500, 1000, 2000, 5000, 10000} offline transitions and 300 independent repetitions at each sample size. FORE, MWL, and DualDICE use the same three-dimensional normalized log-linear ratio class. Linear FQE, FORE-reweighted FQE, and MQL use the same three-dimensional value class. Thus the direct ratio and value estimators are compared using classes of the same size. MWL, MQL, and DualDICE use the same random-Fourier RBF critic class, with 128 features and an intercept term. Additional numerical constants, tuning parameters, and implementation details are reported in Appendix G.2. 103
100
linear FQE multiplier = 1.2206
10 2
10 1
Occupancy error
Absolute value error
101
FORI
linear FQE FORI FORI-reweighted FQE
10 3 10 5 10 7
10 4 10 6 10 8
10 9 0
5
10
15 20 Iteration
25
30
35
FORI multiplier = 0.0855
0
5
10
15 20 Iteration
25
30
35
Figure 2: Linear-Gaussian population recursions. The left panel shows policy-value error for linear FQE, direct FORE, and FORE-reweighted FQE. The right panel shows FORE occupancy error.
16
FORI RFF-RBF MWL RFF-RBF DualDICE
1
Value RMSE
Value RMSE
1.5 1.25
0.75
6 × 10 1 0.5
Q-based
0.5 0.4 0.3 0.25 0.2 0.15 0.125 0.1 0.075
Linear FQE FORI-reweighted FQE RFF-RBF MQL
2e5 1e5
0.3 500
1000
2000
Offline transitions
5000
10000
1e5 8e4
6 × 104
0.05 0.04 0.03 0.025
0.4
linear FQE
2e5
Value RMSE
Ratio-based 2
5e4 4e4 500
1000
2000
Offline transitions
5000
10000
500
1000
2000
Offline transitions
5000
10000
Figure 3: Linear-Gaussian finite-sample value error. Curves report value RMSE over 300 repetitions; vertical bars indicate Monte Carlo uncertainty.
Direct value error 2
1 0.75
6 × 10 1 0.5
FORI RFF-RBF MWL RFF-RBF DualDICE
0.4
Density-ratio L 2 error
1.5 1.25
Value RMSE
Ratio error FORI RFF-RBF MWL RFF-RBF DualDICE
0.4
0.3 0.25 0.2 0.15 0.125
0.3 500
1000
2000
Offline transitions
5000
10000
500
1000
2000
Offline transitions
5000
10000
Figure 4: Direct ratio estimators in the linear-Gaussian experiment. The left panel reports value RMSE from direct reward reweighting; the right panel reports empirical L2 (ν) error of the fitted density ratio.
Figure 4 separates density-ratio error from the error of direct reward reweighting. In this design, FORE has the smallest density-ratio error across the reported sample sizes, while MWL has the smallest direct value RMSE among the ratio estimators. At n = 10000, MQL and FORE-reweighted FQE have value RMSEs 0.025 and 0.052, respectively, compared with 4.18×104 for linear FQE. Direct reward reweighting has value RMSEs 0.428, 0.319, and 0.543 for FORE, MWL, and DualDICE, respectively. The FORE-reweighted FQE results show that recovering the target occupancy distribution can stabilize the projected Bellman recursion even when the value class is not Bellman complete for the Bellman projection under the offline data distribution. MQL uses the same value class as FORE-reweighted FQE, so their difference reflects the fitted criterion and critic weighting rather than the size of the Q-model. We also vary the discount factor at fixed sample size n = 5000. For each γ, the reward is redefined as r = q − γP q, so the value class remains correctly specified. Figure 5 plots value RMSE against the effective horizon (1 − γ)−1 . The direct ratio estimators grow approximately linearly on this scale, consistent with the value-level horizon dependence in Theorem 4.2. The Q-based estimators, MQL and FORE-reweighted FQE, are less sensitive to the discount in this example. Linear FQE is run for the same fixed number of fitted updates at every discount, including settings in which the empirical projected Bellman recursion is noncontractive.
17
2e45 5e32
) 1)
99
97
0.9
(log scale in (1
0.9
0.5 0.6 0.7 0. 0.88 5 0.9 0.9 3 0.9 5 0.9 7 0.9 8
0.9
) 1)
0.9
(log scale in (1
99
1e-5
97
7e-3
9
5e7
95
1e20
0.02
9
Value RMSE
0.2 0.07
95
99
97
0.9
) 1)
0.9
9
95
0.9
(log scale in (1
0.9
0.5 0.6 0.7 0. 0.88 5 0.9 0.9 3 0.9 5 0.9 7 0.9 8
0.1 0.05
0.5
0.9
0.5
Linear FQE linear FQE
5e57
0.9
2
2e70
0.9
2
Q-based (1 ) 1 FORI-reweighted FQE RFF-RBF MQL
0.9
5
Value RMSE
10 5
Ratio-based (1 ) 1 FORI RFF-RBF MWL RFF-RBF DualDICE
0.5 0.6 0.7 0. 0.88 5 0.9 0.9 3 0.9 5 0.9 7 0.9 8
Value RMSE
50
Figure 5: Linear-Gaussian value error as the discount varies. Curves report value RMSE over 500 repetitions at n = 5000, with the horizontal axis scaled by the effective horizon (1 − γ)−1 . Linear FQE is evaluated after the same fixed number of fitted updates at every discount.
7. Conclusion FORE formulates discounted occupancy-ratio estimation as a fitted adjoint Bellman problem. Rather than solving a ratio–critic saddle point, it iterates adjoint Bellman updates and KL-projects each update onto a class of positive, normalized ratios. The KL geometry gives the main stability result: the population update contracts in relative entropy toward the target occupancy ratio, and the projected recursion converges up to the approximation error of the log-ratio class. The fitted analysis adds a statistical error governed by the complexity of the same class. The approximation requirement is therefore placed directly on the occupancy ratio. Instead of requiring Bellman completeness of a value class, adjoint Bellman completeness of a ratio class, or dual completeness of a critic class, the fixed-policy theory requires that the distribution shift from the offline distribution to the target discounted occupancy be representable and estimable. If log ωπ,γ is poorly approximated by the chosen class, FORE converges only up to the corresponding approximation error. This perspective contrasts with value-function realizability results in offline reinforcement learning. Realizability of Qπ alone does not control distribution shift, so finite-sample value guarantees typically require additional coverage, concentrability, completeness, or weighting conditions (Jiang and Li, 2016; Munos and Szepesvári, 2008; Patterson et al., 2022; van der Laan and Kallus, 2025b; Xie et al., 2019; Yin and Wang, 2020). Given support overlap, however, the structural realizability condition in FORE is on the discounted occupancy ratio, not on a value or critic class. Limitations. FORE does not remove the need for coverage: the target-induced state–action distributions must be supported by the offline data. In problems with limited overlap, highdimensional continuous state–action spaces, or near-deterministic target policies, occupancy-ratio estimation may be difficult and can be as hard as, or harder than, learning a value function. The guarantees also rely on boundedness and complexity control of the log-ratio class. In particular, because FORE models density ratios through log-ratios, the target discounted occupancy ratio must be bounded away from zero on the support of the offline data distribution, so that the log-ratio is well behaved and the KL-based analysis is finite.
References Philip Amortila, Nan Jiang, and Tengyang Xie. A variant of the wang-foster-kakade lower bound for the discounted setting. arXiv preprint arXiv:2011.01075, 2020.
18
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted q-iteration in continuous action-space mdps. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL https://proceedings.neur ips.cc/paper_files/paper/2007/file/da0d1111d2dc5d489242e60ebcbaf988-Paper.pdf. Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the Twelfth International Conference on Machine Learning, pages 30–37. Morgan Kaufmann, 1995. Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. Journal of machine learning research, 6(Oct):1705–1749, 2005. Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4):1497–1537, 2005. doi: 10.1214/009053605000000282. URL https://doi.org/10.1214/009053605000000282. Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, and Masatoshi Uehara. Source condition double robust inference on functionals of inverse problems. arXiv preprint arXiv:2307.13793, 2023. Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney K Newey, Vasilis Syrgkanis, and Masatoshi Uehara. Inference on strongly identified functionals of weakly identified functions. Journal of the Royal Statistical Society Series B: Statistical Methodology, page qkaf075, 2025. Olivier Bousquet. A bennett concentration inequality and its application to suprema of empirical processes. Comptes Rendus Mathematique, 334(6):495–500, 2002. Haim Brezis. Functional Analysis, Sobolev Spaces and Partial Differential Equations. Universitext. Springer, New York, NY, 2011. doi: 10.1007/978-0-387-70914-7. Jonathan Chang, Kaiwen Wang, Nathan Kallus, and Wen Sun. Learning bellman complete representations for offline policy evaluation. In International Conference on Machine Learning, pages 2938–2971. PMLR, 2022. Fengdi Che, Bryan Chan, Chen Ma, and A. Rupam Mahmood. AVG-DICE: Stationary distribution correction by regression. Reinforcement Learning Journal, 6:2415–2426, 2025. Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In International conference on machine learning, pages 1042–1051. PMLR, 2019. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, second edition, 2006. ISBN 9780471241959. Imre Csiszár. I-divergence geometry of probability distributions and minimization problems. The annals of probability, pages 146–158, 1975. Bo Dai, Ofir Nachum, Yinlam Chow, Lihong Li, Csaba Szepesvari, and Dale Schuurmans. Coindice: Off-policy confidence interval estimation. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9398–9411. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_fil es/paper/2020/file/6aaba9a124857622930ca4e50f5afed2-Paper.pdf. 19
Nishanth Dikkala, Greg Lewis, Lester Mackey, and Vasilis Syrgkanis. Minimax estimation of conditional moment models. Advances in Neural Information Processing Systems, 33:12248–12262, 2020. Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6(18):503–556, 2005. URL http://jmlr.org/papers/v6 /ernst05a.html. Dylan J Foster, Akshay Krishnamurthy, David Simchi-Levi, and Yunzong Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. arXiv preprint arXiv:2111.10919, 2021. Scott Fujimoto, David Meger, and Doina Precup. A deep reinforcement learning approach to marginalized importance sampling with the successor representation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3518–3529. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/fujimoto21a.html. Carles Gelada and Marc G. Bellemare. Off-policy deep reinforcement learning by bootstrapping the covariate shift. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 3647–3655. AAAI Press, 2019. doi: 10.1609/AAAI.V33I01.33013647. URL https://doi.org/10.1609/aaai.v33i01.33013647. Assaf Hallak and Shie Mannor. Consistent on-line off-policy evaluation. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1372–1383. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/hallak17a.html. Yichun Hu, Nathan Kallus, and Masatoshi Uehara. Fast rates for the regret of offline reinforcement learning. Mathematics of Operations Research, 50(1):633–655, 2025. 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. Intrinsically efficient, stable, and bounded off-policy evaluation for reinforcement learning. 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/fi le/59bcda7c438bad7d2afffe9e2fed00be-Paper.pdf. Nathan Kallus and Masatoshi Uehara. Double reinforcement learning for efficient and robust offpolicy 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 5078–5088. PMLR, 13–18 Jul 2020a. URL https://proceedings.mlr.press/v119/kallus20b .html. 20
Nathan Kallus and Masatoshi Uehara. Doubly robust off-policy value and gradient estimation for deterministic policies. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10420–10430. Curran Associates, Inc., 2020b. URL https://proceedings.neurips.cc/paper_files/paper/2020/ file/75df63609809c7a2052fdffe5c00a84e-Paper.pdf. 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, 2020c. URL http://jmlr.org/papers/v21/19-827.html. Nathan Kallus and Masatoshi Uehara. Statistically efficient off-policy policy gradients. 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 5089–5100. PMLR, 13–18 Jul 2020d. URL https://proceedings.mlr.press/v119/kallus20c.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. Nathan Kallus and Masatoshi Uehara. Efficient evaluation of natural stochastic policies in off-line reinforcement learning. Biometrika, 111(1):51–69, 2024. doi: 10.1093/biomet/asad059. URL https://academic.oup.com/biomet/article/111/1/51/7284104. Geon-Hyeong Kim, Jongmin Lee, Youngsoo Jang, Hongseok Yang, and Kee-Eung Kim. Lobsdice: Offline learning from observation via stationary distribution correction estimation. CoRR, abs/2202.13536, 2022. URL https://arxiv.org/abs/2202.13536. Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://openreview.net/forum?id= Hyg-JC4FDr. 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. Hoang Le, Cameron Voloshin, and Yisong Yue. Batch policy learning under constraints. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3703–3712. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr.press/v97/le19a.html. Jongmin Lee, Wonseok Jeon, Byungjun Lee, Joelle Pineau, and Kee-Eung Kim. Optidice: Offline policy optimization via stationary distribution correction estimation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6120–6130. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/lee21f.html. Jongmin Lee, Cosmin Paduraru, Daniel J. Mankowitz, Nicolas Heess, Doina Precup, Kee-Eung Kim, and Arthur Guez. Coptidice: Offline constrained reinforcement learning via stationary distribution correction estimation. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://openreview.net /forum?id=FLA55mBee6Q. 21
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinitehorizon off-policy estimation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. CesaBianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/2 018/file/dda04f9d634145a9c68d5dfe53b21272-Paper.pdf. Yecheng Ma, Andrew Shen, Dinesh Jayaraman, and Osbert Bastani. Versatile offline imitation from observations and examples via regularized state-occupancy matching. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 14639–14663. PMLR, 17–23 Jul 2022. URL https://proceedings.ml r.press/v162/ma22a.html. Sean P. Meyn and Richard L. Tweedie. Markov Chains and Stochastic Stability. Cambridge University Press, April 2009. ISBN 9780511626630. doi: 10.1017/cbo9780511626630. URL http://dx.doi.org/10.1017/CBO9780511626630. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013. 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., 2019a. URL https://proceedings.neurips.cc/p aper_files/paper/2019/file/cf9a242b70f45317ffd281241fa66502-Paper.pdf. Ofir Nachum, Bo Dai, Ilya Kostrikov, Yinlam Chow, Lihong Li, and Dale Schuurmans. Algaedice: Policy gradient from arbitrary experience. CoRR, abs/1912.02074, 2019b. URL http://arxiv. org/abs/1912.02074. Richard Nickl and Benedikt M. Pötscher. Bracketing metric entropy rates and empirical central limit theorems for function classes of Besov- and Sobolev-type. Journal of Theoretical Probability, 20(2):177–199, 2007. Andrew Patterson, Adam White, and Martha White. A generalized projected bellman error for off-policy value estimation in reinforcement learning. Journal of Machine Learning Research, 23 (145):1–61, 2022. URL http://jmlr.org/papers/v23/21-037.html. Brahma S. Pavse and Josiah P. Hanna. Scaling marginalized importance sampling to high-dimensional state-spaces via state abstraction. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, February 2023. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, April 1994. ISBN 9780470316887. doi: 10.1002/9780470316887. URL http://dx.doi.org/10. 1002/9780470316887.
22
Maxim Raginsky. Strong data processing inequalities and Φ-Sobolev inequalities for discrete channels. CoRR, abs/1411.3575, 2014. URL https://arxiv.org/abs/1411.3575. Martin Riedmiller. Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method. In European conference on machine learning, pages 317–328. Springer, 2005. Richard S. Sutton, A. Rupam Mahmood, and Martha White. An emphatic approach to the problem of off-policy temporal-difference learning. Journal of Machine Learning Research, 17(73):1–29, 2016. URL http://jmlr.org/papers/v17/14-488.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. Samuele Tosatto, Matteo Pirotta, Carlo d’Eramo, and Marcello Restelli. Boosted fitted q-iteration. In International Conference on Machine Learning, pages 3434–3443. PMLR, 2017. 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. Masatoshi Uehara, Jiawei Huang, and Nan Jiang. Minimax weight and q-function learning for offpolicy 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. CoRR, abs/2212.06355, 2022. doi: 10.48550/ARXIV.2212.06355. URL https://doi.org/10.48550/arXiv.2212.06355. Lars van der Laan. A researcher’s guide to empirical risk minimization. arXiv:2602.21501, 2026.
arXiv preprint
Lars van der Laan and Nathan Kallus. Stationary reweighting yields local convergence of soft fitted q-iteration. CoRR, abs/2512.23927, 2025a. doi: 10.48550/ARXIV.2512.23927. URL https://doi.org/10.48550/arXiv.2512.23927. Lars van der Laan and Nathan Kallus. Fitted Q evaluation without bellman completeness via stationary weighting. CoRR, abs/2512.23805, 2025b. doi: 10.48550/ARXIV.2512.23805. URL https://doi.org/10.48550/arXiv.2512.23805. Lars van der Laan, Aurélien Bibaut, and Nathan Kallus. Efficient inference for inverse reinforcement learning and dynamic discrete choice models. CoRR, abs/2512.24407, 2025a. doi: 10.48550/ARX IV.2512.24407. URL https://doi.org/10.48550/arXiv.2512.24407. 23
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, 2025b. Lars van der Laan, Nathan Kallus, and Aurélien Bibaut. Inverse reinforcement learning using just classification and a few regressions. CoRR, abs/2509.21172, 2025c. doi: 10.48550/ARXIV.2509.21 172. URL https://doi.org/10.48550/arXiv.2509.21172. Aad W. van der Vaart and Jon A. Wellner. A local maximal inequality under uniform entropy. Electronic Journal of Statistics, 5:192–203, 2011. Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/9781108627771. URL https://doi.org/10.1017/9781108627771. Ruosong Wang, Dean Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? In International Conference on Learning Representations, 2021a. URL https://arxiv.org/abs/2010.11895. Yuanhao Wang, Ruosong Wang, and Sham Kakade. An exponential lower bound for linearly realizable mdp with constant suboptimality gap. Advances in Neural Information Processing Systems, 34:9521–9533, 2021b. 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/p aper_files/paper/2019/file/4ffb0d2ba92f664c2281970110a2e071-Paper.pdf. Tengyang Xie, Dylan J Foster, Yu Bai, Nan Jiang, and Sham M Kakade. The role of coverage in online reinforcement learning. arXiv preprint arXiv:2210.04157, 2022. Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off-policy evaluation via the regularized lagrangian. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 6551–6561. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/fi le/488e4104520c6aab692863cc1dba45af-Paper.pdf. Ming Yin and Yu-Xiang Wang. Asymptotically efficient off-policy evaluation for tabular reinforcement learning. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3948–3958. PMLR, 26–28 Aug 2020. URL https://proceedi ngs.mlr.press/v108/yin20b.html. Ruiyi Zhang, Bo Dai, Lihong Li, and Dale Schuurmans. Gendice: Generalized offline estimation of stationary values. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020a. URL https://openreview.n et/forum?id=HkxlcnVFwB.
24
Shangtong Zhang, Bo Liu, and Shimon Whiteson. GradientDICE: Rethinking generalized offline estimation of stationary values. 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 11194–11203. PMLR, 13–18 Jul 2020b. URL https://proceedings.mlr.pres s/v119/zhang20r.html. The appendix is organized by proof role. Appendix A records the empirical-process and concentration tools used repeatedly below. Appendix B gives the core KL-FORE identification and projection lemmas, and Appendix C proves the fitted KL projection bound. Appendix D then proves the policyevaluation consequences in Section 5. Appendix E contains the undiscounted KL contraction result under a one-step strong data-processing condition. Appendix F contains the backward-regression variant of FORE; its L1 (ν), or total-variation, contraction and adjoint-completeness limitation are kept separate from the KL-FORE proofs. Appendix G records the numerical constructions used in Section 6.
A. Technical Tools Used in the Proofs This section records the empirical-process and concentration inequalities used to prove the finitesample theory in Section 4.2. Throughout, Z1 , . . . , Zn are independent observations with common P law P , σ1 , . . . , σn are independent Rademacher variables, and Pn = n−1 ni=1 δZi . The lemmas are the Ledoux–Talagrand contraction inequality (Wainwright, 2019, Chapter 5), Bousquet’s version of Talagrand’s maximal inequality for empirical processes (Bousquet, 2002), and the scalar Bernstein inequality (Wainwright, 2019, Chapter 2). Lemma A.1 (Rademacher contraction). Let G be a class of measurable real-valued functions and let φi : R → R, i = 1, . . . , n, be L-Lipschitz functions with φi (0) = 0. Then, conditionally on Z1 , . . . , Z n , n n 1X 1X Eσ sup σi φi (g(Zi )) ≤ 2LEσ sup σi g(Zi ) . g∈G n i=1 g∈G n i=1 The same bound holds for a common Lipschitz map φ applied pointwise. Lemma A.2 (Bousquet’s inequality). Let G be a countable class of measurable functions satisfying P g = 0, ∥g∥∞ ≤ b, and P g 2 ≤ v for all g ∈ G. Then, for every u ≥ 0, with probability at least 1 − e−u , v ( ) u u 2u bu t sup |(Pn − P )g| ≤ E sup |(Pn − P )g| + v + 2bE sup |(Pn − P )g| + . g∈G
n
g∈G
g∈G
3n
Lemma A.3 (Bernstein’s inequality). Let Y1 , . . . , Yn be independent mean-zero variables with P |Yi | ≤ b almost surely and n−1 ni=1 EYi2 ≤ v. Then, for every u ≥ 0, with probability at least 1 − e−u , r n 1X 2vu bu Yi ≤ + . n i=1 n 3n The following is a standard local Rademacher-complexity bound based on Dudley’s entropy integral; see Bartlett et al. (2005) and Wainwright (2019, Chapter 14).
25
Lemma A.4 (Localized entropy bound for Rademacher averages). Let G be a uniformly bounded class and suppose that, uniformly over probability measures Q, log N {ϵ, G, L2 (Q)} ≤ H(ϵ). Then the localized Rademacher averages used in (7) are bounded, up to a universal constant, by the corresponding Dudley integral 1 Rn (G, r; P ) ≲ √ n
Z rq
1 + H(ϵ) dϵ,
0
with the integral truncated at the uniform envelope.
B. KL-FORE Proof Details For a finite signed measure µ, write |µ| for its total variation measure. B.1. Propagation of Absolute Continuity Lemma B.1 (Propagation of absolute continuity). Assume νPπ ≪ ν. If a finite signed measure µ satisfies |µ| ≪ ν, then |µPπ | ≪ ν. Consequently, under Condition C1, dπ,γ ≪ ν for every γ ∈ [0, 1). Proof of Lemma B.1. Let B ⊆ X be measurable with ν(B) = 0. Since νPπ ≪ ν, 0 = (νPπ )(B) =
Z
Pπ (B | x) ν(dx).
The integrand is nonnegative, so Pπ (B | x) = 0 for ν-almost every x. If |µ| ≪ ν, the same exceptional set is also |µ|-null, and therefore (|µ| Pπ )(B) =
Z
Pπ (B | x) |µ| (dx) = 0.
For every measurable A, the partition definition of total variation and the triangle inequality under the integral give |µPπ | (A) ≤ (|µ| Pπ )(A). Hence |µPπ | (B) = 0 whenever B is ν-null. Under Condition C1, d0 ≪ ν. Applying the first part inductively with µ = d0 Pπt shows d0 Pπt ≪ ν for every t ≥ 0. The countable nonnegative mixture dπ,γ = (1 − γ)
∞ X
γ t d0 Pπt
t=0
is therefore also absolutely continuous with respect to ν. B.2. Occupancy Bellman moment identity The adjoint Bellman operator Bπγ ω = (1 − γ)ω0 + γ
d{(ων)Pπ } dν
can be written in measure form as (Bπγ ω)ν = (1 − γ)d0 + γ(ων)Pπ .
26
(8)
Proof of the occupancy Bellman moment identity (3). Equation (8) gives Z
f (x)(Bπγ ω)(x) ν(dx) = (1 − γ)
Z
f (x) d0 (dx) + γ
= (1 − γ)Ed0 {f (X)} + γ
Z
Z Z
f (y){(ων)Pπ }(dy)
f (y)Pπ (dy | x) ω(x)ν(dx)
= (1 − γ)Ed0 {f (X)} + γEν {ω(X)f (X + )}. This proves the occupancy Bellman moment identity (3). Proof of Lemma 3.2. For any h ∈ H, the terms in Dν (Bπγ ω∥ωh ) = Eν {(Bπγ ω)(X) log(Bπγ ω)(X)} − Eν {(Bπγ ω)(X)h(X)} + Λν (h) that depend on h are the final two terms. Applying (3) to f = h gives Eν {(Bπγ ω)(X)h(X)} = (1 − γ)Ed0 {h(X)} + γEν {ω(X)h(X + )}. Thus minimizing Dν (Bπγ ω∥ωh ) over h ∈ H is equivalent to minimizing the displayed loss in Lemma 3.2.
B.3. KL-Projected FORE For the proofs in this subsection, set H◦ = {h − Eν {h(X)} : h ∈ H}. The centering map is continuous and linear on L2 (ν), so H◦ is convex and compact in L2 (ν) under Condition C2. Condition C4 gives sup ∥h∥∞ ≤ R. h∈H◦
Moreover ωh = ωh−Eν {h(X)} , so
W = {ωh : h ∈ H◦ }.
Hence, for any ω ∈ W, we can always find a centered representative h ∈ H◦ such that ω = ωh . We first record the standard Pythagorean inequality for KL projections onto normalized exponential families (Banerjee et al., 2005; Csiszár, 1975). Lemma B.2 (Convex KL projection inequality). Assume Conditions C2 and C4. Let u ∈ ∆ν be a bounded density. Then the map h 7→ Dν (u∥ωh ) attains its minimum over H◦ . Writing ū = ΠKL W u= ⋆ ◦ ◦ ⋆ ωhu for any minimizer hu ∈ H and letting v = ωg ∈ W with g ∈ H , we have Dν (ū∥v) ≤ Dν (u∥v) − Dν (u∥ū). In particular, Dν (ū∥v) ≤ Dν (u∥v). Proof. Since u ∈ ∆ν is bounded, there is a finite constant Bu such that 0 ≤ u ≤ Bu ν-almost everywhere. Thus u log u ∈ L1 (ν) and h ∈ L1 (uν) for every h ∈ H◦ . Minimizing Dν (u∥ωh ) is therefore equivalent to minimizing Fu (h) = Λν (h) − Eν {u(X)h(X)}. 27
The set H◦ is compact in L2 (ν). If hm → h in L2 (ν) with hm , h ∈ H◦ , then ∥hm ∥∞ ∨ ∥h∥∞ ≤ R. Hence |ehm − eh | ≤ eR |hm − h|, and therefore Λν (hm ) → Λν (h). Also |Eν {u(X)(hm − h)(X)}| ≤ Bu ∥hm − h∥L1 (ν) ≤ Bu ∥hm − h∥L2 (ν) . Thus Fu is continuous on the compact set H◦ , and it attains its minimum. Let ht = (1 − t)h⋆u + tg. Since h⋆u minimizes Fu over the convex class H◦ , the right derivative at t = 0 is nonnegative. Since h⋆u and g are bounded by R, dominated convergence gives d Λν (ht ) = Eν {ωht (X)(g − h⋆u )(X)}, dt Therefore
0 ≤ t ≤ 1.
Eν {ū(X)(g − h⋆u )(X)} − Eν {u(X)(g − h⋆u )(X)} ≥ 0.
The normalized log-ratio form gives Dν (u∥v) − Dν (u∥ū) − Dν (ū∥v) = Eν {ū(X)(g − h⋆u )(X)} − Eν {u(X)(g − h⋆u )(X)}. Combining the last two displays gives the stated projection inequality. Lemma B.3 (Quadratic KL projection violation). Assume Conditions C2 and C4. Let u ∈ ∆ν be a density with 0 ≤ u ≤ Bu < ∞, let ū = ΠKL W u, and let w ∈ ∆ν satisfy w > 0 ν-almost everywhere and log w ∈ L2 (ν). Then Dν (ū∥w) ≤ Dν (u∥w) + Cproj inf ∥log w − log v∥2L2 (ν) , v∈W
where Cproj = Cproj (R, Bu ) < ∞. Proof. The projection exists by Lemma B.2. Fix v ∈ W. Lemma B.2 gives Dν (ū∥v) ≤ Dν (u∥v) − Dν (u∥ū). Therefore Dν (ū∥w) = Dν (ū∥v) +
Z
ū(x) log
≤ Dν (u∥v) − Dν (u∥ū) + = Dν (u∥w) +
Z
v(x) ν(dx) w(x) Z
ū(x) log
(u − ū)(x) log
v(x) ν(dx) w(x)
w(x) ν(dx) − Dν (u∥ū). v(x)
By Condition C4, ū ∈ W satisfies e−2R ≤ ū ≤ e2R . Set ϕ(t) = t log t − t + 1, with ϕ(0) = 1. Since 0 ≤ u/ū ≤ Bu e2R , continuity of ϕ(t)/(t − 1)2 on [0, Bu e2R ], with the value at t = 1 interpreted as 1/2, gives a constant cϕ = cϕ (R, Bu ) > 0 such that ϕ(t) ≥ cϕ (t − 1)2 on this interval. Therefore Dν (u∥ū) =
Z
ū(x)ϕ{u(x)/ū(x)} ν(dx) ≥ cϕ
Z
{u(x) − ū(x)}2 ν(dx) ≥ c0 ∥u − ū∥2L2 (ν) , ū(x)
where c0 = cϕ e−2R . For δv = log w − log v, Cauchy–Schwarz gives Z
(u − ū)(x)δv (x) ν(dx) ≤ ∥u − ū∥L2 (ν) ∥δv ∥L2 (ν) . 28
Combining the last two displays and using ab − c0 a2 ≤ b2 /(4c0 ) gives Z
(u − ū)(x)δv (x) ν(dx) − Dν (u∥ū) ≤
1 ∥δv ∥2L2 (ν) . 4c0
Taking the infimum over v ∈ W proves the lemma with Cproj = 1/(4c0 ). e = ωπ,γ and using Bπγ ωπ,γ = ωπ,γ , Proof of Theorem 4.1. Fix ω ∈ W. Lemma 3.1, applied with ω gives Dν (Bπγ ω∥ωπ,γ ) ≤ γDν (ω∥ωπ,γ ).
Set BB := (1 − γ)B0 + γe2R B+ . For any ω ∈ W, choose h ∈ H◦ such that ω = ωh . Then ∥h∥∞ ≤ R, so Λν (h) = log Eν eh ∈ [−R, R], and ω = eh−Λν (h) ≤ e2R . Hence d{(ων)Pπ } dν + ≤ e2R π ≤ e2R B+ . dν dν Thus u = Bπγ ω is bounded by BB . Since BB ≤ B0 + e2R B+ , Lemma B.3, applied with w = ωπ,γ and Bu = B0 + e2R B+ , gives π 2 2 Dν (TKL W ω∥ωπ,γ ) ≤ Dν (Bγ ω∥ωπ,γ ) + Capp εKL ≤ γDν (ω∥ωπ,γ ) + Capp εKL ,
(9)
where Capp depends only on the constants in Condition C4. Applying this one-step inequality to (k) and iterating (9) yields ω (k+1) = TKL W ω Dν (ω (K) ∥ωπ,γ ) ≤ γ K Dν (ω (0) ∥ωπ,γ ) + Capp
1 − γK 2 ε . 1 − γ KL
If ωπ,γ ∈ W, choose v = ωπ,γ in the approximation term, so εKL = 0. Since Bπγ ωπ,γ = ωπ,γ , a KL projection of Bπγ ωπ,γ onto W is ωπ,γ itself. The preceding recursion with εKL = 0 gives the realizable contraction.
C. Fitted KL Projection Bounds This section proves Theorem 4.2. We use the centered class H◦ = {h − Eν {h(X)} : h ∈ H}. We first define the population objective and minimizer targeted by FORE. For f ∈ W and h ∈ H◦ , let Lf (h) = Λν (h) − (1 − γ)Ed0 {h(X)} − γEν {f (X)h(X + )}, where X + | X ∼ Pπ (· | X). Let h⋆f ∈ arg min Lf (h),
ūf = ωh⋆f ,
h∈H◦
∆f (h) = Lf (h) − Lf (h⋆f ).
For ω ∈ W, write uω = Bπγ ω. By the occupancy Bellman moment identity (3), Lω (h) equals Dν (uω ∥ωh ) up to a term that does not depend on h, and ūω = ΠKL W uω . For sample averages, write Pn,X g = n−1
n X
Pn,0 g = n−1
g(Xi ),
i=1
i=1
and, for functions φ of a transition pair, Pn,+ φ = n
n X
−1
n X i=1
29
φ(Xi , Xi+ ).
g(Xi0 ),
For a positive input f , define the self-normalized empirical successor average + Pn,f g=
With this notation,
Pn,+ {f (X)g(X + )} . Pn,X f
b (h) − (1 − γ)P h b f (h) = Λ L ν n,0 + − γPn,f h.
b f (h + c) = L b f (h). Here Pn,X is the empirical distribution of the This empirical loss satisfies L transition covariates, Pn,0 is the empirical distribution of the initial sample, and Pn,+ is the empirical distribution of the transition pairs. The empirical-process events below are uniform over f ∈ W and h ∈ H◦ . This uniformity is what permits their later use at the data-dependent fitted inputs (k) f = ωp , without conditioning on a particular iterate.
Lemma C.1 (Critical-radius scaling). Assume Conditions C2 and C4. For every fixed A < ∞ and b > 0, there is a constant LA,b < ∞, depending only on A, b, and the boundedness constants, such that Cn (Ar) ≤ br2 for all r ≥ LA,b rn,fit . For every fixed A < ∞, there is a constant CA < ∞, depending only on A and the boundedness constants, such that Cn (A) ≤ CA rn,fit . Proof. The class H∆ is star-shaped. Indeed, if h∆ = h1 − h2 with h1 , h2 ∈ H◦ and t ∈ [0, 1], then th∆ = {th1 + (1 − t)h2 } − h2 and the convexity of H◦ implies th1 + (1 − t)h2 ∈ H◦ . The product class G× is also star-shaped: if g(x, x+ ) = f (x)h∆ (x+ ) and t ∈ [0, 1], then tg(x, x+ ) = f (x){th∆ (x+ )}, where th∆ ∈ H∆ . Therefore tg ∈ G× . Let G be any of the classes entering Cn , and let 0 < a ≤ b0 . For each g ∈ G with ∥g∥L2 (P ) ≤ b0 , the function (a/b0 )g belongs to G and has L2 (P )-norm at most a. Hence Rn (G, b0 ; P ) ≤
b0 Rn (G, a; P ). a
It follows that s 7→ Rn (G, s; P )/s is nonincreasing for each such class, and therefore s 7→ Cn (s)/s is nonincreasing. The localized classes are nested in the radius, so Cn is nondecreasing. The bounded envelopes make the fixed-point set in (7) nonempty for large radii: Cn (s) is bounded uniformly in s, while s2 → ∞. Let r⋆ denote the infimum in (7). Since r⋆ ≤ rn,fit , the definition of the infimum gives a radius t ≤ r⋆ + rn,fit ≤ 2rn,fit such that Cn (t) ≤ t2 . Let r ≥ Lrn,fit , where L ≥ 1 will be chosen below. If Ar ≥ t, then Cn (Ar) ≤
Ar 2A 2 Cn (t) ≤ Art ≤ r . t L
If Ar < t, monotonicity gives Cn (Ar) ≤ Cn (t) ≤ t2 ≤ 30
4 2 r . L2
Choosing L = LA,b large enough so that 2A/L ≤ b and 4/L2 ≤ b proves the first display. For the second display, use the same t ≤ 2rn,fit . If A ≥ t, star-shapedness gives Cn (A) ≤
A Cn (t) ≤ At ≤ 2Arn,fit . t
If A < t, then Cn (A) ≤ Cn (t) ≤ 4r2n,fit . This is bounded by a constant times rn,fit when rn,fit ≤ 1; when rn,fit > 1, the bounded envelopes give Cn (A) ≤ CA ≤ CA rn,fit . The second display follows. Lemma C.2 (Curvature and variance of the fitted KL loss). Assume Conditions C2 and C4. There is a finite constant Ccurv , depending only on the boundedness constants, such that, for every f ∈ W and h ∈ H◦ , h i ⋆ ∥h − h⋆f ∥2L2 (ν) + ∥eh − ehf ∥2L2 (ν) + Ed0 {h(X) − h⋆f (X)}2 h
i
+ E f 2 (X){h(X + ) − h⋆f (X + )}2 ≤ Ccurv ∆f (h), where the final expectation is under X ∼ ν and X + | X ∼ Pπ (· | X). Proof. Put g = h − h⋆f and let uf (x) = (1 − γ)
dd0 d{(f ν)Pπ } (x) + γ (x). dν dν
Because f ∈ W, uf is a density with respect to ν. Since H◦ is convex and h⋆f minimizes Lf over H◦ , the one-sided directional derivative of t 7→ Lf (h⋆f + t{h − h⋆f }) at t = 0 is nonnegative. Boundedness of H◦ justifies differentiating under the expectation, so, with ūf = ωh⋆f , Eν {ūf (X)g(X)} − Eν {uf (X)g(X)} ≥ 0. Consequently,
∆f (h) = Λν (h) − Λν (h⋆f ) − Eν {uf (X)g(X)} ≥ Λν (h) − Λν (h⋆f ) − Eν {ūf (X)g(X)} = Dν (ūf ∥ωh ).
Along ht = h⋆f + tg, the second derivative is Varωht {g(X)}. Because h, h⋆f ∈ H◦ , Eν {g(X)} = 0. Condition C4 gives e−2R ≤ ωht ≤ e2R . Hence Varωht {g(X)} = inf Eν {ωht (X)(g(X) − a)2 } ≥ e−2R inf Eν {(g(X) − a)2 } = e−2R ∥g∥2L2 (ν) . a
a
Therefore Dν (ūf ∥ωh ) =
1 (1 − t) Varωht {g(X)} dt ≥ e−2R ∥g∥2L2 (ν) . 2 0
Z 1
The displayed lower bound gives the L2 (ν) control. Since |eu − ev | ≤ eR |u − v| for u, v ∈ [−R, R], it also controls the exponential component. The L2 (d0 ) bound follows from dd0 /dν ≤ B0 . For the transition bound, f ≤ e2R and d{(f ν)Pπ } dν + ≤ e2R π ≤ e2R B+ , dν dν so
h
i
h
E f 2 (X)g 2 (X + ) ≤ e2R E f (X)g 2 (X + ) =e
2R
Z
i
g 2 (x){(f ν)Pπ }(dx) ≤ e4R B+ ∥g∥2L2 (ν) .
Absorbing these constants into Ccurv yields the asserted curvature bound. 31
Lemma C.3 (Uniform denominator process). Assume Conditions C2 and C4. There is a constant Cden , depending only on R, such that, for every u ≥ 0, with probability at least 1 − e−u ,
sup |(Pn,X − ν)f | ≤ Cden rn,fit +
r
f ∈W
u u . + n n
Proof. Every f ∈ W can be written as ωh for some h ∈ H◦ . Fix h0 ∈ H◦ . Since Λν (h) = log Eν eh(X) and ∥h∥∞ ≤ R, |Λν (h) − Λν (h0 )| ≤ CR ∥h − h0 ∥L2 (ν) . Write ηh = Λν (h) − Λν (h0 ). Then ωh − ωh0 = e−Λν (h) {eh − eh0 } + {e−Λν (h) − e−Λν (h0 ) }eh0 . The first term is indexed by Lipschitz transforms of h − h0 : the maps u 7→ eh0 (x)+u − eh0 (x) are CR -Lipschitz on [−2R, 2R] and vanish at u = 0. Symmetrization and Lemma A.1 therefore give n 1X σi e−Λν (h) {eh(Xi ) − eh0 (Xi ) } ≤ CR Rn (H∆ , CR ; ν). E sup ◦ n h∈H i=1
For the second term, the preceding Lipschitz bound on Λν and ∥h − h0 ∥L2 (ν) ≤ 2R give sup |e−Λν (h) − e−Λν (h0 ) | ≤ CR .
h∈H◦
Moreover, n 1X Eσ σi eh0 (Xi ) ≤ n i=1
(
n 1 X e2h0 (Xi ) n2 i=1
)1/2
≤ eR n−1/2 .
Combining the two parts gives n 1X σi {ωh (Xi ) − ωh0 (Xi )} ≤ CR Rn (H∆ , CR ; ν) + CR n−1/2 . ◦ n h∈H i=1
E sup
By Lemma C.1, Rn (H∆ , CR ; ν) ≤ CR rn,fit , after enlarging constants and using rn,fit ≥ n−1/2 . Lemma A.3 controls the fixed function ωh0 , and Lemma A.2 adds the deviation term for the supremum. Applying these two inequalities with u + log 2, and enlarging constants, gives, with probability at least 1 − e−u ,
sup |(Pn,X − ν)ωh | ≤ CR rn,fit +
h∈H◦
r
u u + . n n
This proves the claim. Lemma C.4 (Uniform fitted KL empirical-process bound). Assume Conditions C2 and C4. Let an,fit (δ) be defined as in the main text. Then, with probability at least 1 − δ, simultaneously for every f ∈ W and every h ∈ H◦ , b f (h) − Lf (h)} − {L b f (h⋆ ) − Lf (h⋆ )} {L f f
1 ≤ ∆f (h) + Crad an,fit (δ), 4 where Crad depends only on the boundedness constants. 32
Proof. For f ∈ W and h ∈ H◦ , put h† = h⋆f , gh = h − h† , and b f (h) − Lf (h)} − {L b f (h† ) − Lf (h† )}. Zf (h) = {L
Define An (g) = (Pn,0 − d0 )g, + Bn,f (g) = Pn,f g − E{f (X)g(X + )},
b (h) − Λ (h)} − {Λ b (h† ) − Λ (h† )}. Cn (h, h† ) = {Λ ν ν ν ν
(10)
bf , Using the definitions of Lf and L
Zf (h) = Cn (h, h† ) − (1 − γ)An (gh ) − γBn,f (gh ).
(11)
We first prove the following shell bound. We claim that there is a constant Csh , depending only on the boundedness constants, such that, for every r > 0 and u ≥ 0, with probability at least 1 − 5e−u , sup
f ∈W, h∈H◦ : ∆f (h)≤r2
|Zf (h)| ≤ Csh Cn (Csh r) + rrn,fit + r
r
u u + . n n
(12)
We now prove (12). The empirical-process bounds below are applied to centered versions of the displayed localized classes. For each localized class, Condition C4 gives a constant envelope, and the p 2 shell bounds below give variance at most Cr . Thus Lemma A.2 yields the displayed r u/n + u/n deviation terms after symmetrization controls the mean supremum, using Lemma A.1 when a Lipschitz transform is applied. Scalar fixed-function terms are controlled by Lemma A.3. By Lemma C.2 and the density bounds in Condition C4, the slice ∆f (h) ≤ r2 implies ∥gh ∥L2 (ν) + ∥gh ∥L2 (d0 ) + {Ef 2 (X)gh2 (X + )}1/2 ≤ Cr. Moreover gh = h−h⋆f ∈ H∆ , because both h and h⋆f belong to H◦ . For An (gh ) in (11), symmetrization bounds the expectation of the centered localized difference class {h−h0 : h, h0 ∈ H◦ }, and Lemma A.2 gives r u u sup |(Pn,0 − d0 )gh | ≤ C Rn (H∆ , Cr; d0 ) + r + n n f ∈W, h∈H◦ : ∆f (h)≤r2
with probability at least 1 − e−u , uniformly over f ∈ W. P For Bn,f (gh ) in (11), write Pn,X f = n−1 i f (Xi ). Since f ∈ W, e−2R ≤ f ≤ e2R , and hence Pn,X f ≥ e−2R deterministically. Also Eν f = 1. Therefore, for each gh , + Pn,f gh − E{f (X)gh (X + )} =
(Pn,+ − Qν,π ){f (X)gh (X + )} − E{f (X)gh (X + )}(Pn,X f − 1) . (13) Pn,X f
On the shell, the first numerator in (13) is indexed by functions in G× with L2 (Qν,π )-norm at most Cr. Symmetrization bounds the expectation by the localized Rademacher complexity, and Lemma A.2 therefore gives sup
f ∈W, h∈H◦ : ∆f (h)≤r2
|(Pn,+ − Qν,π ){f (X)gh (X + )}| ≤ C Rn (G× , Cr; Qν,π ) + r
33
r
u u + n n
with probability at least 1 − e−u . In the second numerator in (13), the curvature bound gives |E{f (X)gh (X + )}| ≤ Cr on the shell, while uniform boundedness gives |E{f (X)gh (X + )}| ≤ CR . Thus the multiplier may be taken as C(r ∧ CR ). Lemma C.3 gives
sup |(Pn,X − ν)f | ≤ C rn,fit +
r
f ∈W
u u + n n
with probability at least 1 − e−u . Hence the part of (13) containing Pn,X f − 1 is bounded by
C rrn,fit + r
r
u u , + n n
after enlarging C. Combining this display with the bound on the first numerator in (13) gives sup
f ∈W, h∈H◦ : ∆f (h)≤r2
|Bn,f (gh )| ≤ C Rn (G× , Cr; Qν,π ) + rrn,fit + r
r
u u . + n n
(14)
To bound Cn (h, h† ) in (11), set ht = h† + tgh and ωt = ωht for t ∈ [0, 1]. Since H◦ is convex, ht ∈ H◦ and ωt ∈ W. Differentiating along this path gives †
|Cn (h, h )|
≤
Z 1 0
Pn,X {ωt gh } − Eν {ωt (X)gh (X)} dt. Pn,X ωt
(15)
b (h )/dt = P Indeed, dΛ ν t n,X {ωt gh }/Pn,X ωt , because multiplying exp(ht ) by the population normalizing constant cancels in the empirical ratio, while dΛν (ht )/dt = Eν {ωt gh }. For each t,
Pn,X {ωt gh } (Pn,X − ν)(ωt gh ) − Eν {ωt (X)gh (X)}(Pn,X ωt − 1) − Eν {ωt (X)gh (X)} = . Pn,X ωt Pn,X ωt
(16)
Because ωt ∈ W, Pn,X ωt ≥ e−2R deterministically. On the slice ∆f (h) ≤ r2 , Lemma C.2 gives ∥gh ∥L2 (ν) ≤ Cr. Since ωt ≤ e2R , {Eν ωt2 (X)gh2 (X)}1/2 + |Eν {ωt (X)gh (X)}| ≤ Cr. Thus the first numerator in (16) is indexed by G× under Qν,∆ , with L2 (Qν,∆ ) norm at most Cr. Symmetrization bounds the expectation by the localized Rademacher complexity, and Lemma A.2 gives r u u sup sup |(Pn,X − ν)(ωt gh )| ≤ C Rn (G× , Cr; Qν,∆ ) + r + n n f ∈W, h∈H◦ : t∈[0,1] ∆f (h)≤r2
with probability at least 1 − e−u . The second numerator in (16) is bounded by C(r ∧ CR ) supf ∈W |(Pn,X − ν)f |, which is controlled by Lemma C.3. Since Pn,X ωt ≥ e−2R , Cn (h, h† ) is bounded by r u u C Rn (G× , Cr; Qν,∆ ) + rrn,fit + r + . n n Combining the bounds for An , Bn,f , and Cn in (11), intersecting the component events, and applying a union bound gives (12). Let Lsh ≥ 1 be the constant from Lemma C.1, applied with A = Csh and b = (32Csh )−1 , and set r̄n = Lsh rn,fit . For every r ≥ r̄n , Csh Cn (Csh r) ≤ r2 /32. 34
Young’s inequality, with the quadratic coefficient chosen sufficiently small, gives Csh rrn,fit + Csh r
r
r2 u u . ≤ + C r2n,fit + n 32 n
Hence, for r ≥ r̄n , sup
f ∈W, h∈H◦ : ∆f (h)≤r2
|Zf (h)| ≤
r2 u . + C r2n,fit + 16 n
The boundedness of H◦ , W, ω0 , and dνπ+ /dν implies supf ∈W,h∈H◦ ∆f (h) ≤ CR . Apply this bound on the dyadic shells 2j r̄n2 < ∆f (h) ≤ 2j+1 r̄n2 , with radius rj = 2(j+1)/2 r̄n and uj = log(10/δ) + 2j log 2, and take a union bound over j ≥ 0. On shell j, rj2 /16 = 2j−3 r̄n2 ≤ ∆f (h)/8. Let C0 be the constant multiplying uj /n in the preceding display. For every η > 0 there is Cη < ∞ such that j ≤ η2j + Cη for all j ≥ 0. Choosing η so that 2C0 η log 2 ≤ 1/8, we obtain log(10/δ) uj ≤ C r2n,fit + n n
C0
+
1 j 2 2 r̄n , 8
where r̄n2 = L2sh r2n,fit . Since r2n,fit ≥ n−1 , the term Cη /n is absorbed after enlarging constants. On the same shell, 2j r̄n2 < ∆f (h). The inner shell ∆f (h) ≤ r̄n2 is bounded by applying the same display with r = r̄n , in which case the r̄n2 term is included in Crad {r2n,fit + log(1/δ)/n}. The peeling event therefore gives 1 log(1/δ) 2 |Zf (h)| ≤ ∆f (h) + Crad rn,fit + , 4 n after enlarging Crad . This completes the proof. Lemma C.5 (Uniform empirical-normalizer bound). Assume Conditions C2 and C4. There is a constant Cnorm , depending only on R, such that, with probability at least 1 − δ, b (h) − Λ (h)| ≤ C sup |Λ ν ν norm
h∈H◦
s
r
n,fit
+
log(1/δ) . n
Proof. Choose any h0 ∈ H◦ . Condition C4 gives e−R ≤ eh ≤ eR for all h ∈ H◦ . Thus both Pn,X eh and Eν eh lie in [e−R , eR ], and h b (h) − Λ (h)| ≤ C sup |(P sup |Λ ν ν R n,X − ν)e |.
h∈H◦
Moreover,
h∈H◦
sup |(Pn,X − ν)eh | ≤ |(Pn,X − ν)eh0 | + sup |(Pn,X − ν)(eh − eh0 )|.
h∈H◦
h∈H◦
The first term is at most CR u/n with probability at least 1 − e−u by Lemma A.3. For the second term, define F0 = {eh − eh0 : h ∈ H◦ }. For each h ∈ H◦ , the difference h − h0 belongs to H∆ and satisfies ∥h − h0 ∥L2 (ν) ≤ 2R. Since the maps u 7→ eh0 (x)+u − eh0 (x) are CR -Lipschitz on [−2R, 2R] and vanish at u = 0, the contraction inequality in Lemma A.1 gives p
E sup |(Pn,X − ν)g| ≤ CR Rn (H∆ , 2R; ν). g∈F0
35
By Lemma C.1, the right-hand side is at most CR rn,fit , after enlarging constants. Lemma A.2, p applied to the bounded class F0 , adds CR u/n + CR u/n. Hence, with probability at least 1 − 2e−u , b (h) − Λ (h)| ≤ C sup |Λ ν
h∈H◦
ν
R
rn,fit +
r
u u + . n n
Taking u = log(2/δ) and using u/n ≤ u1/2 /n1/2 after enlarging the constant when u ≤ n gives the b (h) − Λ (h)| ≤ 2R stated uniform normalizer bound. If u > n, the deterministic bound suph∈H◦ |Λ ν ν gives the same conclusion after another enlargement of the constant. Lemma C.6 (Empirical normalization is a scalar KL perturbation). Let h ∈ H◦ , ωh = eh−Λν (h) , bν (h) b (h) − Λ (h), then b h = eh−Λ and ω . If ℓh = Λ ν ν b h = e−ℓh ωh ω
and b h ∥ωπ,γ ) = e−ℓh Dν (ωh ∥ωπ,γ ) + e−ℓh (−ℓh ) − e−ℓh + 1. Dνgen (ω
Consequently, because |ℓh | ≤ 2R, b h ∥ωπ,γ ) ≤ e|ℓh | Dν (ωh ∥ωπ,γ ) + CR ℓ2h , Dνgen (ω
|e−ℓh − 1|2 ≤ CR ℓ2h .
b h = e−ℓh ωh follows directly from the definitions. Since Proof. The identity ω
Dνgen (e−ℓh ωh ∥ωπ,γ ) =
Z
e−ℓh ωh log
R
ωh dν =
R
ωπ,γ dν = 1,
e−ℓh ωh dν − e−ℓh + 1 ωπ,γ
= e−ℓh Dν (ωh ∥ωπ,γ ) + e−ℓh (−ℓh ) − e−ℓh + 1. The functions u 7→ e−u (−u) − e−u + 1 and u 7→ e−u − 1 have first derivative zero and finite second derivative on [−2R, 2R]. Taylor’s theorem on this compact interval gives the two bounds. Lemma C.7 (Projected KL recursion). Assume Conditions C1, C2, C4, and C3. Then there is a finite constant Capp , depending only on the constants in Condition C4, such that, for every ω ∈ W,
π 2 Dν ΠKL W Bγ ω ωπ,γ ≤ γDν (ω∥ωπ,γ ) + Capp εKL .
e = ωπ,γ and using Bπγ ωπ,γ = ωπ,γ , gives Proof. Lemma 3.1, applied with ω
Dν (Bπγ ω∥ωπ,γ ) ≤ γDν (ω∥ωπ,γ ) under Condition C1. Every ω ∈ W satisfies ω ≤ e2R by Condition C4. As in the proof of Theorem 4.1, u = Bπγ ω is bounded by B0 + e2R B+ . Lemma B.3, applied with w = ωπ,γ and Bu = B0 + e2R B+ , therefore gives π Dν ΠKL B ω ω ≤ Dν (Bπγ ω∥ωπ,γ ) + Capp ε2KL , π,γ W γ where Capp depends only on the constants in Condition C4. Combining these two displays establishes the one-step projected-KL recursion. Lemma C.8 (Fitted KL ERM excess). On the event in Lemma C.4, the exact empirical minimizer b b (k) (h) obeys, for every k = 0, . . . , K − 1 such that ωp(k) ∈ W, h k+1 ∈ arg minh∈H◦ Lω b b Lω(k) (h k+1 ) − inf ◦ Lω (k) (h) ≤ Cerm an,fit (δ), p
h∈H
p
(k)
b (k) /Eν ω b (k) and Cerm depends only on the boundedness constants. where ωp = ω 36
(k)
⋆ ⋆ b =h b b −L b (k) (h⋆ ) ≤ 0. b (k) (h) Proof. Fix k, write f = ωp , h k+1 , and h = hf . Exact ERM gives Lω ω b b b −L b (k) = L b f , so L b f (h) b f (h⋆ ) ≤ 0. No conditioning on By self-normalization of the input weights, L ω b b (k) is required here: the event in Lemma C.4 holds simultaneously for every deterministic f ∈ W, ω (k) and the theorem proof verifies that the random input ωp belongs to W. Thus
b ≤ {L b − L (h)} b − {L b f (h) b f (h⋆ ) − Lf (h⋆ )} ∆f (h) f
1 b +C a ≤ ∆f (h) rad n,fit (δ). 4 Moving the first term to the left and absorbing constants into Cerm proves the stated excess-loss bound. Lemma C.9 (Approximate KL projection perturbation). Assume Conditions C1, C2, C4, and C5. e ∈ H◦ and ω e = ωe . If Fix ω ∈ W, and let h h e − inf Lω (h) ≤ ∆, Lω (h) ◦ h∈H
then, for every λ > 0, e ∥ωπ,γ ) ≤ (1 + λ)Dν (ūω ∥ωπ,γ ) + Cpert (λ)∆, Dν (ω
where Cpert (λ) depends only on (R, m⋆ , λ). Moreover, for some constant Cpert,0 < ∞ depending only on (R, m⋆ ), it may be chosen so that Cpert (λ) ≤ Cpert,0 (1 + λ−1 ). Proof. Because Lω (h) differs from Dν (uω ∥ωh ) by an additive constant independent of h, e − Lω (h⋆ ) ≤ ∆. e ) − Dν (uω ∥ūω ) = Lω (h) Dν (uω ∥ω ω e, By Lemma B.2, with u = uω , ū = ūω , and v = ω e ) ≤ Dν (uω ∥ω e ) − Dν (uω ∥ūω ) ≤ ∆. Dν (ūω ∥ω e ∈ [e−2R , e2R ], the ratio ω e /ūω lies in [e−4R , e4R ]. On this compact interval, the functions Since ūω , ω 2 (v − 1) , v log v − v + 1, and − log v + v − 1 all vanish only at v = 1, have positive second derivative at v = 1, and are continuous away from v = 1. Hence their ratios are bounded above and below by e /ūω , the preceding constants depending only on R. Applying this pointwise comparison with v = ω KL bound implies Z e − ūω )2 (ω e Dν (ω ∥ūω ) + dν ≤ CR ∆. ūω
Condition C5 gives ωπ,γ ≥ m⋆ ν-almost everywhere. With r = ūω /ωπ,γ , we have 0 ≤ r ≤ e2R /m⋆ . Hence r(log r)2 ≤ CR,m⋆ {r log r − r + 1}, where the inequality follows by continuity on [0, e2R /m⋆ ], with the values at 0 and 1 interpreted in the limiting sense. Because ūω and ωπ,γ both integrate to one, (
Z
ūω
ūω log ωπ,γ
)2
dν =
Z
ωπ,γ r(log r)2 dν
≤ CR,m⋆ Dν (ūω ∥ωπ,γ ). 37
Using the identity e ∥ωπ,γ ) = Dν (ūω ∥ωπ,γ ) + Dν (ω e ∥ūω ) + Dν (ω
Z
e − ūω ) log (ω
ūω dν, ωπ,γ
the cross term satisfies, by Cauchy–Schwarz, Z
ūω e − ūω ) log dν ≤ (ω ωπ,γ
(Z
e − ūω )2 (ω dν ūω
≤ CR,m⋆
q
)1/2 Z
ūω
ūω log ωπ,γ
!2
dν
1/2
∆Dν (ūω ∥ωπ,γ ).
Combining this decomposition with the cross-term bound gives e ∥ωπ,γ ) ≤ Dν (ūω ∥ωπ,γ ) + CR ∆ + CR,m⋆ Dν (ω
q
∆Dν (ūω ∥ωπ,γ ).
Let D = Dν (ūω ∥ωπ,γ ). For any λ > 0, the form 2ab ≤ λa2 + λ−1 b2 of Young’s inequality, applied with a = D1/2 and b = CR,m⋆ ∆1/2 /2, gives 2 √ CR,m ⋆ CR,m⋆ ∆D ≤ λD + ∆. 4λ
Therefore
e ∥ωπ,γ ) ≤ (1 + λ)Dν (ūω ∥ωπ,γ ) + Cpert (λ)∆. Dν (ω
2 Enlarging Cpert (λ) to absorb CR + CR,m /(4λ) gives the claimed inequality. The same display gives ⋆ −1 the bound Cpert (λ) ≤ Cpert,0 (1 + λ ).
Proof of Theorem 4.2. Throughout the proof Cfit denotes a finite constant depending only on R, B0 , B+ , and m⋆ . Set ρ = (1 + γ)/2 and bn = an,fit (δ),
ζn = 2R ∧ Cnorm
r
s
n,fit
+
log(1/δ) . n
Apply Lemmas C.4 and C.5 with failure probabilities δ/2 each. Since log(2/δ) ≤ log(1/δ) + log 2, replacing δ by δ/2 only enlarges the universal constants multiplying an,fit (δ). Work on the intersection of these two events, which has probability at least 1 − δ. Both events are uniform over the logratio class, so they may be evaluated at the random iterates constructed by the algorithm; no union bound over k is needed. For each k, define the normalizing constant and the corresponding population-normalized ratio b (k) ω b (k) . ωp(k) = , cbk = Eν ω b (k) Eν ω (0)
b (0) ≡ 1, we have ωp = ω b (0) and cb0 = 1. Set ℓ0 = 0. For each fitted iterate choose a centered Since ω b . This is valid because, for any constant c, replacing h by h + c changes neither representative h k b (h)}; see Appendix B.3. Thus, for k ≥ 1, exp{h − Λν (h)} nor exp{h − Λ ν b − Λ ν (h b )} ∈ W, ωp(k) = exp{h k k (0)
while ωp = 1 ∈ W because 0 ∈ H. Hence all fitted inputs belong to W. For 1 ≤ k ≤ K, b (h b b bk , ℓk := Λ ν k ) − Λν (hk ) = − log c 38
b (k) = e−ℓk ωp(k) , ω
so Lemma C.5 gives max |ℓk | ≤ ζn ,
b (k) − 1 ≤ Cnorm ζn , max Eν ω
1≤k≤K
1≤k≤K
where the second inequality follows from cbk = e−ℓk and |eu −1| ≤ CR |u| on [−2R, 2R]. By Lemma C.8, for k = 0, . . . , K − 1, b Lω(k) (h k+1 ) − inf ◦ Lω (k) (h) ≤ Cerm bn . h∈H
p
p
Applying Lemma C.9 with ∆ = Cerm bn gives, for every λ > 0,
π (k) Dν (ωp(k+1) ∥ωπ,γ ) ≤ (1 + λ)Dν ΠKL ωπ,γ + Cpert (λ)Cerm bn . W B γ ωp
By Lemma C.7,
π (k) ωπ,γ ≤ γDν (ωp(k) ∥ωπ,γ ) + Capp ε2KL . Dν ΠKL W B γ ωp
The proof of Lemma C.9 gives Cpert (λ)Cerm ≤ Cfit (1 + λ−1 ). Choose λρ = 1 if γ = 0, and otherwise choose ρ−γ λρ = 1 ∧ . 2γ Then (1 + λρ )γ ≤ ρ. Indeed, if λρ = (ρ − γ)/(2γ), then (1 + λρ )γ = (ρ + γ)/2 ≤ ρ; if λρ = 1, then ρ ≥ 3γ, so (1 + λρ )γ = 2γ ≤ ρ. Moreover, 1 + λ−1 ρ ≤
1 + λρ ≤ 2,
C , ρ−γ
with the same conclusion when γ = 0. Substituting λ = λρ in the preceding recursion and using these bounds gives Dν (ωp(k+1) ∥ωπ,γ ) ≤ ρDν (ωp(k) ∥ωπ,γ ) + Cfit ε2KL +
Cfit bn . ρ−γ
(17)
Iterating (17) gives Dν (ωp(K) ∥ωπ,γ ) ≤ ρK Dν (ωp(0) ∥ωπ,γ ) + Cfit
1 − ρK 2 Cfit 1 − ρK εKL + bn . 1−ρ ρ−γ 1−ρ
(K)
b (K) = e−ℓK ωp , Lemmas C.5 and C.6 give For ω b (K) ∥ωπ,γ ) ≤ eζn Dν (ωp(K) ∥ωπ,γ ) + CR ζn2 . Dνgen (ω
Since ζn ≤ 2R and ζn2 ≤ C
log(1/δ) r2n,fit + n
(K)
= Cbn , (0)
b (0) , and enlarging Cfit gives substituting the preceding display for Dν (ωp ∥ωπ,γ ), using ωp = ω b (K) ∥ωπ,γ ) ≤ Cfit ρK Dνgen (ω b (0) ∥ωπ,γ ) + Dνgen (ω
Cfit 2 Cfit εKL + bn . 1−ρ (ρ − γ)(1 − ρ)
With ρ = (1 + γ)/2, we have (1 − ρ)−1 = 2(1 − γ)−1 and {(ρ − γ)(1 − ρ)}−1 = 4(1 − γ)−2 . The last display is therefore the stated generalized-KL bound. 39
Corollary C.10 (Uniform entropy-integral bound). Assume the conditions of Theorem 4.2. For ϵ > 0, let Z q HH (ϵ) = sup log N {ϵ, H◦ , L2 (Q)},
r
JH (r) =
Q
0
1 + HH (ϵ) dϵ,
where the supremum is over probability distributions on the state-action space. Suppose JH (2R) < ∞. Define JH (r) −1/2 2 rn,ent = n ∨ inf r > 0 : √ ≤r . n Then the fitted critical radius in (7) satisfies rn,fit ≤ CR rn,ent . Consequently, with probability at least 1 − δ, b (K) ∥ωπ,γ ) ≤ Cfit Dνgen (ω
1+γ 2
K
b (0) ∥ωπ,γ ) + Dνgen (ω
Cfit 2 Cfit ε + 1 − γ KL (1 − γ)2
r2n,ent +
log(1/δ) , n
where Cfit has the same dependencies as in Theorem 4.2. Proof. Throughout the proof, CR denotes a finite constant depending only on the boundedness constants in Conditions C4 and C5. For any probability distribution P on the state-action space, log N {ϵ, H∆ , L2 (P )} ≤ 2HH (ϵ/2),
ϵ > 0.
Lemma A.4 therefore gives, uniformly over P ∈ {ν, d0 }, Rn (H∆ , r; P ) ≤
CR JH (CR r) √ . n
√ Thus the two H∆ terms in Cn (r) are each bounded by CR JH (CR r)/ n. It remains to control the product class. Since W = {ωa : a ∈ H◦ }, the definition of G× gives n
o
G× = (x, x+ ) 7→ ωa (x)b∆ (x+ ) : a ∈ H◦ , b∆ ∈ H∆ ,
ωa = ea−Λν (a) .
Let Qν,π be the distribution of (X, X + ). Its marginals are ν and νπ+ . For a, a′ ∈ H◦ and b∆ , b′∆ ∈ H∆ , the Lipschitz property of Λν on the bounded class and the boundedness of H∆ give ωa (X)b∆ (X + ) − ωa′ (X)b′∆ (X + ) L2 (Qν,π ) n
o
≤ CR ∥a − a′ ∥L2 (ν) + ∥b∆ − b′∆ ∥L2 (νπ+ ) . Hence
log N {ϵ, G× , L2 (Qν,π )} ≤ CR + 3HH (ϵ/CR ),
ϵ > 0.
Applying Lemma A.4 to the product class yields Rn (G× , r; Qν,π ) ≤
CR JH (CR r) √ . n
Replacing Qν,π by Qν,∆ changes the second marginal from νπ+ to ν, so the same argument gives the same bound for Rn (G× , r; Qν,∆ ). Combining the last two displays, Cn (s) ≤
CR JH (CR s) √ n 40
for every s > 0.
Because covering numbers decrease as the radius increases, r 7→ JH (r)/r is nonincreasing. By the √ definition of rn,ent as an infimum, there is t ≤ 2rn,ent such that JH (t)/ n ≤ t2 . Let s = Lrn,ent , where L ≥ 1 will be chosen large enough depending only on CR . If CR s ≥ t, then 2 JH (CR s) CR s JH (t) 2CR √ √ ≤ ≤ CR st ≤ s2 . n t n L
If CR s < t, monotonicity gives JH (CR s) JH (t) 4 √ ≤ √ ≤ t2 ≤ 2 s2 . n n L Combining these two cases with the preceding bound on Cn (s), and choosing L large enough, gives Cn (s) ≤ s2 . Therefore inf{r > 0 : Cn (r) ≤ r2 } ≤ Lrn,ent . Since L ≥ 1 and rn,ent ≥ n−1/2 , the leading n−1/2 term in (7) is also bounded by Lrn,ent . Hence rn,fit ≤ Lrn,ent . Renaming L as part of the constant CR , substituting this bound into an,fit (δ), and applying Theorem 4.2 proves the displayed result. Corollary C.11 (Finite-dimensional bounded log class). Assume the conditions of Theorem 4.2. If, in addition, {h − Eν {h(X)} : h ∈ H} is contained in a d-dimensional linear span with d ≥ 1, then the Rademacher critical radius in (7) satisfies s
rn,fit ≤ CR
d log(en) , n
where CR depends only on the boundedness constants. Consequently, an,fit (δ) ≤ CR
d log(en) + log(1/δ) , n
so the finite-dimensional statistical term an,fit (δ) in Theorem 4.2 has order {d log(en) + log(1/δ)}/n. Proof. Fix any P ∈ {ν, d0 } and any center h0 ∈ H◦ . The localized difference class {h − h0 : h ∈ H◦ , ∥h − h0 ∥L2 (P ) ≤ r} is contained in a d-dimensional linear space, has L2 (P )-radius r, and has a bounded envelope depending only on R. Its covering numbers obey log N {ϵ, {h − h0 : h ∈ H◦ , ∥h − h0 ∥L2 (P ) ≤ r}, L2 (P )} ≤ d log
CR r , ϵ
0 < ϵ ≤ CR r.
The localized entropy bound in Lemma A.4, applied to this finite-dimensional class, gives s
Rn (H∆ , r; P ) ≤ CR r
d n
uniformly over P ∈ {ν, d0 }. Hence the two H∆ terms in Cn (r) are each bounded by CR r d/n. The product class is contained in the bounded parametric class p
{(x, x+ ) 7→ ωa (x)b∆ (x+ ) : a ∈ H◦ , b∆ ∈ H∆ }. 41
Let Q denote either Qν,π or Qν,∆ , and write G× (r; Q) for the L2 (Q)-localized product class. If ωa b∆ ∈ G× (r; Q), then ∥b∆ ∥L2 (Q2 ) ≤ CR r, where Q2 is the second marginal of Q, because ωa ≥ e−2R . For two products, ∥ωa b∆ − ωa′ b′∆ ∥L2 (Q) n
o
≤ CR ∥a − a′ ∥L2 (Q1 ) + ∥b∆ − b′∆ ∥L2 (Q2 ) , where Q1 is the first marginal. This uses the Lipschitz property of a 7→ ωa = exp{a − Λν (a)} on H◦ under Condition C4, together with the bounded envelope of H∆ . The finite-dimensional covering bound therefore gives CR log N {ϵ, G× (r; Q), L (Q)} ≤ Cd log , ϵ
2
0 < ϵ ≤ CR r.
Since the critical radius is at least n−1/2 , Lemma A.4 applied to this localized product class gives, for the relevant radii, s d log(en) Rn (G× , r; Q) ≤ CR r . n Therefore the fixed-point inequality in (7) holds whenever r ≥ CR d log(en)/n. Since d ≥ 1, p
s
n
−1/2
≤
d log(en) , n
so the initial n−1/2 term in (7) is no larger than this radius. Substituting these bounds into the definition of an,fit (δ) gives the displayed finite-dimensional rate.
D. Proofs for Section 5 D.1. Discounted-occupancy contraction for FQE Throughout this appendix, write ∥f ∥2⋆ = Edπ,γ {f (X)2 } = Eν {ωπ,γ (X)f (X)2 }. For a nonnegative weight ω, write ∥f ∥2ω = Eν {ω(X)f (X)2 }. Lemma D.1 (Weighted projection existence). Assume r ∈ L2 (dπ,γ ), and let Q be nonempty, closed, and convex in L2 (dπ,γ ). If a nonnegative weight ω satisfies ω(x) ≤ M < ∞,
ωπ,γ (x) ≥ m > 0
ν-a.e.,
then, for every Q ∈ Q, the Bellman target T π Q belongs to both L2 (dπ,γ ) and L2 (ω dν), and the oracle projection ΠQ,ωπ,γ T π Q exists and is unique. If Q is also closed in L2 (ω dν), then ΠQ,ω T π Q exists and is unique. Under the displayed bounds, the additional closedness assumption in L2 (ω dν) may be replaced by the one-sided comparison ω ≥ cωπ,γ ν-almost everywhere for some c > 0. Proof. Fix Q ∈ Q. If γ = 0, then T π Q = r, so T π Q ∈ L2 (dπ,γ ) by assumption. If γ > 0, conditional Jensen’s inequality and the discounted occupancy identity imply Edπ,γ {(Pπ Q)(X)2 } ≤ Edπ,γ Pπ {Q(X)2 } ≤ γ −1 Edπ,γ {Q(X)2 }. 42
It follows that Pπ Q ∈ L2 (dπ,γ ), and hence T π Q = r + γPπ Q ∈ L2 (dπ,γ ). The lower bound on ωπ,γ , together with the upper bound on ω, gives, for every measurable f , Eν {ω(X)f (X)2 } ≤
M ∥f ∥2⋆ . m
Thus T π Q ∈ L2 (ω dν). Since Q is closed and convex in L2 (dπ,γ ), the Hilbert projection theorem (Brezis, 2011) gives existence and uniqueness of the oracle projection. The same argument gives existence and uniqueness of the ω-weighted projection whenever Q is closed in L2 (ω dν). It remains only to verify this closedness under the one-sided comparison ω ≥ cωπ,γ . For every h ∈ Q − Q, c∥h∥2⋆ ≤ ∥h∥2ω . If (qn ) ⊂ Q is Cauchy in L2 (ω dν), the lower bound shows that it is Cauchy in L2 (dπ,γ ). Since Q is closed in L2 (dπ,γ ), there is q ∈ Q with qn → q in ∥ · ∥⋆ . Applying ∥f ∥2ω ≤ (M/m)∥f ∥2⋆ to f = qn − q then implies qn → q in L2 (ω dν). Hence Q is closed in L2 (ω dν), and the ω-weighted projection exists and is unique. Lemma D.2 (Bellman contraction under discounted occupancy). Let γ ∈ [0, 1). For any measurable Q1 , Q2 , √ ∥T π Q1 − T π Q2 ∥⋆ ≤ γ ∥Q1 − Q2 ∥⋆ . Consequently, for the oracle projected Bellman operator, ∥TQ,⋆ Q1 − TQ,⋆ Q2 ∥⋆ ≤
√
γ ∥Q1 − Q2 ∥⋆ .
Proof. If γ = 0, then T π Q1 = T π Q2 = r, so the first claim holds. Assume γ > 0, and write ∆ = Q1 − Q2 . Since the reward cancels, T π Q1 − T π Q2 = γPπ ∆. By conditional Jensen’s inequality, |(Pπ ∆)(X)|2 ≤ E{∆(X + )2 | X}. Integrating with respect to dπ,γ gives ∥Pπ ∆∥2⋆ ≤ Edπ,γ Pπ {∆(X)2 }. The discounted occupancy identity dπ,γ = (1 − γ)d0 + γdπ,γ Pπ implies γdπ,γ Pπ ≤ dπ,γ . Therefore Edπ,γ Pπ {∆(X)2 } ≤
1 1 Edπ,γ {∆(X)2 } = ∥∆∥2⋆ . γ γ
Combining the preceding two displays gives ∥T π Q1 − T π Q2 ∥2⋆ = γ 2 ∥Pπ ∆∥2⋆ ≤ γ∥∆∥2⋆ .
43
Taking square roots proves the first claim. The second follows from the nonexpansiveness of Hilbert-space projection onto a closed convex set (Brezis, 2011): ∥TQ,⋆ Q1 − TQ,⋆ Q2 ∥⋆ = ∥ΠQ,ωπ,γ T π Q1 − ΠQ,ωπ,γ T π Q2 ∥⋆ ≤ ∥T π Q1 − T π Q2 ∥⋆ √ ≤ γ ∥Q1 − Q2 ∥⋆ . Lemma D.3 (Projected fixed-point bias). Assume the oracle-projection conditions of Lemma D.1 and the contraction conditions of Lemma D.2. Let QQ,⋆ be the fixed point of TQ,⋆ . Then 1 ∥QQ,⋆ − Qπ ∥⋆ ≤ √ inf ∥q − Qπ ∥⋆ . 1 − γ q∈Q Proof. By Lemmas D.1 and D.2, the oracle projected Bellman operator is a contraction on Q. The Banach fixed-point theorem (Brezis, 2011) therefore gives a unique fixed point QQ,⋆ . The bias bound uses only this fixed-point identity. Let q ◦ = ΠQ,ωπ,γ Qπ . Since Qπ = T π Qπ , ∥QQ,⋆ − q ◦ ∥⋆ = ∥ΠQ,ωπ,γ T π QQ,⋆ − ΠQ,ωπ,γ Qπ ∥⋆ ≤ ∥T π QQ,⋆ − T π Qπ ∥⋆ √ ≤ γ ∥QQ,⋆ − Qπ ∥⋆ . The triangle inequality gives ∥QQ,⋆ − Qπ ∥⋆ ≤ ∥QQ,⋆ − q ◦ ∥⋆ + ∥q ◦ − Qπ ∥⋆ √ ≤ γ ∥QQ,⋆ − Qπ ∥⋆ + inf ∥q − Qπ ∥⋆ . q∈Q
Rearranging this inequality gives the claimed bound. Lemma D.4 (Linear or affine projected fixed-point bias). Let QQ,⋆ be the fixed point of TQ,⋆ . Suppose, in addition to the conditions of Lemma D.3, that Q is a closed affine subspace of L2 (dπ,γ ). Then 1 ∥QQ,⋆ − Qπ ∥⋆ ≤ √ inf ∥q − Qπ ∥⋆ . 1 − γ q∈Q Proof. Let Π⋆ = ΠQ,ωπ,γ , and set q ◦ = Π⋆ Qπ ,
e = QQ,⋆ − Qπ ,
v = QQ,⋆ − q ◦ .
Because Q is a closed affine subspace of L2 (dπ,γ ), the Hilbert projection theorem gives ⟨Qπ − q ◦ , q − q ◦ ⟩⋆ = 0
for every q ∈ Q.
Taking q = QQ,⋆ and applying the Pythagorean identity gives ∥e∥2⋆ = ∥v∥2⋆ + ∥q ◦ − Qπ ∥2⋆ . Since Qπ = T π Qπ and QQ,⋆ = Π⋆ T π QQ,⋆ , ∥v∥⋆ = ∥Π⋆ T π QQ,⋆ − Π⋆ T π Qπ ∥⋆ √ ≤ ∥T π QQ,⋆ − T π Qπ ∥⋆ ≤ γ ∥e∥⋆ , where the first inequality is nonexpansiveness of Hilbert projection and the second is Lemma D.2. Combining the last two displays yields ∥e∥2⋆ ≤ γ∥e∥2⋆ + ∥q ◦ − Qπ ∥2⋆ . Rearranging and using ∥q ◦ − Qπ ∥⋆ = inf q∈Q ∥q − Qπ ∥⋆ proves the displayed bound. 44
D.2. Target-functional and weight-conversion bounds For nonnegative weights a and b with b > 0 ν-almost everywhere, write (
χ⋆ (a, b) =
{a(X) − b(X)}2 Eν b(X)
)1/2
.
Lemma D.5 (Generalized KL controls target chi-square under one-sided bounds). Suppose a and b are nonnegative functions satisfying a(x) ≤ M < ∞ and b(x) ≥ m > 0 for ν-almost every x. Then there is a finite constant Cχ = Cχ (m, M ) such that (
{a(X) − b(X)}2 Eν b(X)
)1/2
≤ Cχ {Dνgen (a∥b)}1/2 .
If a and b both integrate to one under ν, then Dνgen (a∥b) = Dν (a∥b). Proof. Let ϕ(t) = t log t − t + 1. Since 0 ≤ a/b ≤ M/m, cm,M :=
ϕ(t) 0≤t≤M/m (t − 1)2 inf
is strictly positive, where the ratio is interpreted as 1/2 at t = 1. Thus (t − 1)2 ≤ c−1 m,M ϕ(t) on this interval. By the definition of the generalized KL divergence, Dνgen (a∥b) = Eν [b(X)ϕ{a(X)/b(X)}] . Therefore
2 {a(X) − b(X)}2 a(X) = Eν b(X) −1 Eν b(X) b(X)
"
#
gen ≤ c−1 m,M Dν (a∥b). −1/2
Taking square roots proves the lemma with Cχ = cm,M . Lemma D.6 (FORE weight bounds from log-ratio bounds). Assume Conditions C4 and C5. Then there are constants 0 < mF ≤ MF < ∞, depending only on the constants in those conditions, such that mF ≤ ωfit (x) ≤ MF , ωπ,γ (x) ≥ mF ν-a.e. Proof. Let h ∈ H, and write hc = h − Eν {h(X)}. By Condition C4, e−R ≤ ehc (x) ≤ eR for ν-almost b h denotes the empirical normalization of eh over any offline-data block, then, on the every x. If ω probability-one event that the block lies in this full-measure set, b h (x) = ω
n
ehc (x) . hc (Xi ) i=1 e
Pn −1
The denominator lies in [e−R , eR ], so b h (x) ≤ e2R e−2R ≤ ω
ν-a.e.
The fitted output ωfit has this form for some fitted h ∈ H. Condition C5 gives ωπ,γ (x) ≥ m⋆ ν-almost everywhere. Taking mF = min{e−2R , m⋆ }, MF = e2R gives the assertion. 45
Proof of Corollary 5.1. By Lemma D.6, ωfit is bounded above and ωπ,γ is bounded below by constants depending only on Conditions C4 and C5. Lemma D.5, applied with a = ωfit and b = ωπ,γ , gives χ⋆ (ωfit , ωπ,γ ) ≤ C{Dνgen (ωfit ∥ωπ,γ )}1/2 . b (0) ≡ 1 Theorem 4.2, with K = Kω , gives a high-probability bound on Dνgen (ωfit ∥ωπ,γ ). Because ω and Condition C5 gives ωπ,γ ≥ m⋆ , b (0) ∥ωπ,γ ) = Eν {− log ωπ,γ (X)} ≤ log(1/m⋆ ). Dνgen (ω
The assumed lower bound on Kω implies {(1 + γ)/2}Kω ≤ n−1 , so the finite-iteration term in Theorem 4.2 is bounded by C/n. Since rn,fit ≥ n−1/2 , this term is absorbed into the statistical term √ √ √ √ in EFORE . Taking square roots and using x + y + z ≤ x + y + z, together with the definition of EFORE , gives, on an event of probability at least 1 − δ, χ⋆ (ωfit , ωπ,γ ) ≤ Cχ EFORE .
(18)
For every g ∈ L2 (dπ,γ ) with ∥g∥⋆ ≤ 1, Cauchy–Schwarz with respect to dπ,γ = ωπ,γ ν yields |Eν {ωfit (X)g(X)} − Ψπ (g)| = |Eν {(ωfit (X) − ωπ,γ (X))g(X)}| ≤ χ⋆ (ωfit , ωπ,γ )∥g∥⋆ ≤ Ceval EFORE . Taking the supremum over ∥g∥⋆ ≤ 1 proves Corollary 5.1. D.3. Weight perturbation and FORE-weighted FQE Lemma D.7 (Projection perturbation). Suppose the projections TQ,ω Q and TQ,⋆ Q are well defined for the Q ∈ Q under consideration. Suppose also that there is a constant cω > 0 such that ∥h∥2ω ≥ cω ∥h∥2⋆ for every h ∈ Q − Q. Then ∥TQ,ω Q − TQ,⋆ Q∥⋆ ≤
εBell χ⋆ (ω, ωπ,γ ) . cω
Proof. Fix Q ∈ Q, and set m = T π Q,
q⋆ = TQ,⋆ Q,
qω = TQ,ω Q,
h = qω − q ⋆ .
Let rQ = m − q⋆ . The projection optimality condition (Brezis, 2011) for qω = ΠQ,ω m, evaluated at q⋆ ∈ Q, gives Eν {ω(X)(m(X) − qω (X))(q⋆ (X) − qω (X))} ≤ 0. Since m − qω = rQ − h, this implies ∥h∥2ω ≤ Eν {ω(X)rQ (X)h(X)}. Similarly, the projection optimality condition for q⋆ = ΠQ,ωπ,γ m, evaluated at qω ∈ Q, gives Eν {ωπ,γ (X)rQ (X)h(X)} ≤ 0. Therefore
∥h∥2ω ≤ Eν {ω(X)rQ (X)h(X)} = Eν {ωπ,γ (X)rQ (X)h(X)} + Eν {(ω(X) − ωπ,γ (X))rQ (X)h(X)} ≤ |Eν {(ω(X) − ωπ,γ (X))rQ (X)h(X)}| . 46
The assumed one-sided comparison gives ∥h∥2ω ≥ cω ∥h∥2⋆ . Because h = qω − q⋆ belongs to Q − Q, Cauchy–Schwarz under dπ,γ = ωπ,γ ν and the definition of εBell give |Eν {(ω − ωπ,γ )rQ h}| ≤ χ⋆ (ω, ωπ,γ ) εBell ∥h∥⋆ . Combining this lower bound with the preceding upper bound gives cω ∥h∥2⋆ ≤ εBell χ⋆ (ω, ωπ,γ )∥h∥⋆ . If ∥h∥⋆ = 0, the asserted inequality is immediate. Otherwise, dividing the last display by ∥h∥⋆ proves the lemma. Proof of Theorem 5.3. By Lemma D.6, ωfit is bounded above and below, and ωπ,γ is bounded below. Let R and M⋆ be the constants in Conditions C4 and C6, respectively. The proof of Lemma D.6 gives ωfit ≥ e−2R . Since ωπ,γ ≤ M⋆ , for every h ∈ Q − Q, ∥h∥2ωfit = Eν {ωfit (X)h(X)2 } ≥
e−2R ∥h∥2⋆ . M⋆
Lemma D.1 gives the required integrability and existence of the oracle and ωfit -weighted projected Bellman operators. On the event in Corollary 5.1, which has probability at least 1 − δ, the weightconversion bound (18) holds. Lemma D.7 and (18) imply that, for every Q ∈ Q, ∥TQ,ωfit Q − TQ,⋆ Q∥⋆ ≤ εF ,
εF := Cχ εBell EFORE ,
where Cχ is enlarged by a factor depending only on the constants in Conditions C4 and C6. Combining this perturbation bound with Lemma D.2 yields ∥Q(j+1) − QQ,⋆ ∥⋆ = ∥TQ,ωfit Q(j) − TQ,⋆ QQ,⋆ ∥⋆ ≤ ∥TQ,⋆ Q(j) − TQ,⋆ QQ,⋆ ∥⋆ + ∥TQ,ωfit Q(j) − TQ,⋆ Q(j) ∥⋆ √ ≤ γ ∥Q(j) − QQ,⋆ ∥⋆ + εF .
(19)
Iterating (19) gives ∥Q(KQ ) − QQ,⋆ ∥⋆ ≤ γ KQ /2 ∥Q(0) − QQ,⋆ ∥⋆ +
1 − γ KQ /2 √ εF . 1− γ
This gives the intermediate error bound relative to the oracle projected fixed point. Combining it with the triangle inequality and Lemma D.3 gives ∥Q(KQ ) − Qπ ∥⋆ ≤ γ KQ /2 ∥Q(0) − QQ,⋆ ∥⋆ +
1 − γ KQ /2 1 √ εF + √ inf ∥q − Qπ ∥⋆ . 1− γ 1 − γ q∈Q
Substituting the definition of εF gives the displayed bound and proves the theorem.
47
D.4. Doubly robust value identity Proof of Theorem 5.2. Since r ∈ L2 (dπ,γ ), T π 0 = r belongs to L2 (dπ,γ ). Lemma D.2 therefore makes T π a contraction on L2 (dπ,γ ). The Banach fixed-point theorem gives Qπ ∈ L2 (dπ,γ ). Because dπ,γ contains the component (1 − γ)d0 , Q ∈ L2 (dπ,γ ) implies Ed0 |Q(X)| < ∞. Moreover, Lemma D.2, applied with Q1 = Q and Q2 = Qπ , gives ∥T π Q − Qπ ∥⋆ = ∥T π Q − T π Qπ ∥⋆ ≤
√
γ ∥Q − Qπ ∥⋆ .
Thus T π Q − Q ∈ L2 (dπ,γ ). Taking f = Q in the occupancy Bellman moment identity (4) and conditioning on X gives (1 − γ)Ed0 {Q(X)} = Eν {ωπ,γ (X)[Q(X) − γPπ Q(X)]}. Therefore
ΨDR (ω, Q) = Eν {ωπ,γ (X)[Q(X) − γPπ Q(X)]} + Eν {ω(X)[r(X) + γPπ Q(X) − Q(X)]}.
Subtracting Vπ (r) = Eν {ωπ,γ (X)r(X)} gives ΨDR (ω, Q) − Vπ (r) = Eν {ω(X)[r(X) + γPπ Q(X) − Q(X)]} − Eν {ωπ,γ (X)[r(X) + γPπ Q(X) − Q(X)]} = Eν [{ω(X) − ωπ,γ (X)}{T π Q(X) − Q(X)}] . This is the standard doubly robust identity. Taking ω = ωfit and applying Cauchy–Schwarz with respect to dπ,γ = ωπ,γ ν gives {ωfit (X) − ωπ,γ (X)}2 Eν ωπ,γ (X)
(
|ΨDR (ωfit , Q) − Vπ (r)| ≤
)1/2
∥T π Q − Q∥⋆
= χ⋆ (ωfit , ωπ,γ )∥T π Q − Q∥⋆ . Combining the last display with (18) proves the bound in Theorem 5.2. Proof of Corollary 5.4. For Q = Q(KQ ) , Lemma D.2 gives ∥T π Q − Q∥⋆ ≤ ∥T π Q − T π Qπ ∥⋆ + ∥Q − Qπ ∥⋆ √ ≤ (1 + γ)∥Q − Qπ ∥⋆ . On the event (18), which has probability at least 1 − δ, Theorem 5.3 and the assumption that the finite-iteration term is negligible give εBell EFORE 1 − Q ∥⋆ ≤ C + √ √ inf ∥q − Qπ ∥⋆ . 1− γ 1 − γ q∈Q "
(KQ )
∥Q
#
π
Substituting this bound into Theorem 5.2 and using 1 + CDR .
48
√
γ ≤ 2 proves the corollary, after enlarging
E. Undiscounted KL contraction under strong KL data processing The main text obtains a strict KL recursion from discounting. When γ = 1, the common initialdistribution component disappears, and ordinary data processing gives only nonexpansiveness (Cover and Thomas, 2006). This section therefore states the additional mixing requirement directly as a one-step KL strong data-processing inequality for the target-policy kernel (Raginsky, 2014). For γ = 1, the population adjoint Bellman update satisfies (Bπ1 ω)ν = (ων)Pπ . Let
∆ν = ω ∈ L1 (ν) : ω ≥ 0 ν-a.e.,
Z
ω dν = 1
denote the set of ν-densities of probability distributions. The one-step KL strong data-processing condition used below is the following. (C7) One-step KL strong data processing. There exists α ∈ [0, 1) such that, for all probability distributions µ, ξ ≪ ν with 0 < DKL (µ∥ξ) < ∞, DKL (µPπ ∥ξPπ ) ≤ αDKL (µ∥ξ). A simple sufficient condition is a one-step Doeblin minorization: if there exist ϵ > 0 and a probability distribution λ such that Pπ (· | x) ≥ ϵλ(·) for all x, then Condition C7 holds with α ≤ 1 − ϵ. Indeed, writing Pπ = ϵλ + (1 − ϵ)R for the residual Markov kernel R, joint convexity of relative entropy and data processing (Cover and Thomas, 2006) yield, for any probability measures ρ and η, DKL (ρPπ ∥ ηPπ ) ≤ (1 − ϵ)DKL (ρR ∥ ηR) ≤ (1 − ϵ)DKL (ρ ∥ η). Minorization conditions of this type are standard sufficient conditions for uniform ergodicity in Markov-chain theory (Meyn and Tweedie, 2009). Theorem E.1 (Undiscounted adjoint KL contraction). Assume Conditions C1 and C7. The map Bπ1 maps ∆ν into itself, and, for any ω, ξ ∈ ∆ν with Dν (ω∥ξ) < ∞, Dν Bπ1 ω Bπ1 ξ ≤ αDν (ω∥ξ).
If there exists a stationary distribution dπ,1 ≪ ν, with ratio ωπ,1 = ddπ,1 /dν, then
Dν (Bπ1 )K ω ωπ,1 ≤ αK Dν (ω∥ωπ,1 )
for all ω ∈ ∆ν with Dν (ω∥ωπ,1 ) < ∞.
This stationary distribution is unique among stationary distributions d˜ = ω̃ν satisfying Dν (ω̃∥ωπ,1 ) < ∞. Proof of Theorem E.1. Condition C1 and Lemma B.1 imply that (ων)Pπ ≪ ν whenever ω ∈ ∆ν . Hence Bπ1 ω is well defined as a ν-density. Since (ων)Pπ is a probability distribution, Bπ1 ∆ν ⊆ ∆ν . For ω, ξ ∈ ∆ν , applying Condition C7 to the probability measures ων and ξν gives Dν Bπ1 ω Bπ1 ξ = DKL {(ων)Pπ ∥(ξν)Pπ }
≤ αDKL (ων∥ξν) = αDν (ω∥ξ). 49
If dπ,1 = ωπ,1 ν is stationary, then Bπ1 ωπ,1 = ωπ,1 . Iterating the preceding display with ξ = ωπ,1 gives the asserted geometric KL bound. If ω̃ν is another stationary distribution and Dν (ω̃∥ωπ,1 ) < ∞, then Dν (ω̃∥ωπ,1 ) = Dν Bπ1 ω̃ Bπ1 ωπ,1 ≤ αDν (ω̃∥ωπ,1 ). Since α < 1, the finite divergence must be zero. Hence d˜ = dπ,1 , proving uniqueness in the stated class. Proposition E.2 (Projected undiscounted KL recursion). Assume γ = 1, Condition C1, Conditions C2, C4, and C7. Suppose there exists a stationary ratio ωπ,1 ∈ ∆ν with ωπ,1 > 0 ν-a.e. and log ωπ,1 ∈ L1 (ν). Assume that Bπ1 ω is bounded ν-a.e. for every ω ∈ W. For ω ∈ W, let uω = Bπ1 ω,
KL TKL W,1 ω = ΠW uω .
Define the projection violation violKL,1 (ω) = inf
v∈W
Z
{uω (x) − TKL W,1 ω(x)} log
ωπ,1 (x) ν(dx) . v(x)
Then
Dν TKL W,1 ω ωπ,1 ≤ αDν (ω∥ωπ,1 ) + violKL,1 (ω). (j) satisfy Consequently, if supω∈W violKL,1 (ω) ≤ ε1 , the projected iterates ω (j+1) = TKL W,1 ω
Dν (ω (J) ∥ωπ,1 ) ≤ αJ Dν (ω (0) ∥ωπ,1 ) +
1 − αJ ε1 . 1−α
If ωπ,1 ∈ W, then ε1 = 0, TKL W,1 ωπ,1 = ωπ,1 , and
Dν TKL W,1 ω ωπ,1 ≤ αDν (ω∥ωπ,1 ). Proof. Let ū = TKL W,1 ω and u = uω . The convex projection inequality in Lemma B.2, applied to the bounded image u, gives Dν (ū∥v) ≤ Dν (u∥v) for every v ∈ W. Therefore v(x) ν(dx) ωπ,1 (x) Z v(x) ≤ Dν (u∥v) + ū(x) log ν(dx) ωπ,1 (x) Z ωπ,1 (x) = Dν (u∥ωπ,1 ) + {u(x) − ū(x)} log ν(dx). v(x)
Dν (ū∥ωπ,1 ) = Dν (ū∥v) +
Z
ū(x) log
Bounding the last integral by its absolute value and then taking the infimum over v ∈ W yields Dν (ū∥ωπ,1 ) ≤ Dν (u∥ωπ,1 ) + violKL,1 (ω).
(20)
Theorem E.1, with ξ = ωπ,1 , gives Dν (u∥ωπ,1 ) ≤ αDν (ω∥ωπ,1 ).
(21)
Combining (20) and (21) proves the one-step inequality in the theorem. Iterating that inequality gives the displayed bound for ω (J) . If ωπ,1 ∈ W, choose v = ωπ,1 in the violation term. Since uωπ,1 = ωπ,1 , its KL projection is ωπ,1 , and the realizable contraction follows. 50
F. Backward-Regression Variant of FORE The backward-regression variant is a fitted-regression version of the adjoint occupancy-ratio recursion. It estimates the initial density ratio and the one-step target-coverage ratio, repeatedly fits the backward conditional mean in the backward-regression factorization of the adjoint Bellman operator, and uses that regression to form the next ratio iterate. It is the density-ratio analogue of fitted Q-evaluation: FQE regresses Bellman targets for value functions, whereas this variant regresses the adjoint Bellman image for density ratios. This variant also makes explicit the role of adjoint Bellman completeness. The main KL-projected method in Section 4.1 works with occupancy Bellman moment identities and projects the resulting density in KL. It is positive and normalized by construction, and its population analysis does not require a regression class to contain every adjoint Bellman image. The backward-regression variant below is more direct, but its projected population error vanishes only under adjoint Bellman completeness, the density-ratio analogue of Bellman completeness in FQE. For this reason, we recommend using the FORE algorithm studied in the main text. F.1. Backward-regression adjoint factorization Recall that νπ+ = νPπ ,
cπ =
dνπ+ . dν
Let Tπ f (x) = E{f (X + ) | X = x} be the forward transition operator. For ω ∈ L1 (ν), define Tπ′ ω as the ν-density of the pushed-forward signed measure (ων)Pπ . When the functions are squareintegrable, Tπ′ agrees with the L2 (ν)-adjoint: ⟨ω, Tπ f ⟩ν = ⟨Tπ′ ω, f ⟩ν . Define the backward conditional-mean operator ← Pπ,ν ω(x) = E{ω(X) | X + = x},
where X ∼ ν and X + | X ∼ Pπ (· | X). Lemma F.1 (Backward-regression factorization of the adjoint transition). Suppose Condition C1 ← ω ∈ L1 (ν + ), and holds. For every ω ∈ L1 (ν), we have Pπ,ν π ← Tπ′ ω = cπ Pπ,ν ω
ν-a.e.
(22)
← ω is the ν-density of (ων)P . Equivalently, cπ Pπ,ν π
Proof of Lemma F.1. Let J be the joint distribution of (X, X + ) generated by X ∼ ν and X + | X ∼ Pπ (· | X). The second marginal of J is νπ+ = νPπ . Since ω ∈ L1 (ν), EJ [|ω(X)|] = ∥ω∥L1 (ν) < ∞, ← ω(x) = E[ω(X) | X + = x] exists as a ν + -almost-everywhere so the conditional expectation Pπ,ν π equivalence class in L1 (νπ+ ). Choose any measurable version and extend it by zero outside a full-νπ+ -measure set. Jensen’s inequality gives ← Pπ,ν ω
L1 (νπ+ )
= EJ [ E[ω(X) | X + ] ] ≤ EJ [|ω(X)|] = ∥ω∥L1 (ν) . 51
For any measurable B ⊆ X , Z B
← cπ (x)Pπ,ν ω(x) ν(dx) =
Z B
← Pπ,ν ω(x) νπ+ (dx)
← = EJ [Pπ,ν ω(X + )1{X + ∈ B}]
= EJ [ω(X)1{X + ∈ B}] =
Z
Pπ (B | x)ω(x) ν(dx)
= ((ων)Pπ )(B). ← ω is a Radon–Nikodym derivative of ((ων)P ) with respect to ν. If a different ν + Thus cπ Pπ,ν π π ← ω is chosen, then c P ← ω changes only on a ν-null set because almost-everywhere version of Pπ,ν π π,ν νπ+ (dx) = cπ (x)ν(dx). Adding the initial measure gives
(1 − γ)d0 + γ(ων)Pπ ≪ ν,
d[(1 − γ)d0 + γ(ων)Pπ ] ← = (1 − γ)ω0 + γcπ Pπ,ν ω. dν
Combining Lemma F.1 with (2) gives the backward-regression adjoint Bellman equation ← ωπ,γ = (1 − γ)ω0 + γcπ Pπ,ν ωπ,γ .
(23)
Equivalently, the measure-level update has the density representation ← Bπγ ω = (1 − γ)ω0 + γcπ Pπ,ν ω.
The regression algorithm uses this representation. F.2. Backward-regression fitted adjoint Bellman iteration ′ Given offline transitions (Si , Ai , Si′ )ni=1 , let Xi = (Si , Ai ). For each transition, draw A+ i ∼ π(· | Si ) + n n and set Xi+ = (Si′ , A+ i ). Thus {Xi }i=1 is an offline data sample from ν, while {Xi }i=1 is a sample + from the one-step target-policy successor distribution νπ = νPπ . b 0 and cbπ , the backward-regression variant estimates the discounted Given first-stage estimates ω b (0) , iteration occupancy ratio by fitted adjoint Bellman iteration. Starting from an initial estimate ω b (k) (Xi ) on the successor covariates Xi+ . k performs a backward conditional-mean regression of ω With squared-error regression class Mk , define n n o2 1X b (k) (Xi ) − m(Xi+ ) . ω m∈Mk n i=1
b k ∈ arg min m
b (k) (X) | X + = x}. The fitted This regression estimates the backward conditional mean x 7→ E{ω adjoint Bellman update is then b (k+1) (x) = (1 − γ)ω b 0 (x) + γ cbπ (x)m b k (x). ω
After the first-stage ratio estimates are fixed, the iterative learning step is supervised backward conditional-mean regression. A clipped and empirically normalized update uses a level M < ∞ and sets ω̃ (k+1) (x) b (k+1) (x), 0}, M }, b (k+1) (x) ← ω̃ (k+1) (x) = min{max{ω ω . P n−1 ni=1 ω̃ (k+1) (Xi ) Algorithm 2 summarizes the procedure. 52
Algorithm 2 Backward-regression FORE Require: Offline transitions {Xi = (Si , Ai ), Si′ }ni=1 , target policy π, target initial distribution d0 = µ0 π, discount γ, iteration count K, and regression classes Mk + + + 1: Draw Ai ∼ π(· | Si′ ) and set Xi = (Si′ , Ai ) for i = 1, . . . , n b 0 ≈ ω0 = dd0 /dν 2: Estimate ω bπ ≈ cπ = dνπ+ /dν 3: Estimate c 4: for k = 0, . . . , K − 1 do 5:
b k ∈ arg minm∈Mk n1 Fit backward conditional-mean regression m
Pn
i=1
n
b (k) (Xi ) − m(Xi+ ) ω
o2
b (k+1) (x) = (1 − γ)ω b 0 (x) + γ cbπ (x)m b k (x) Set ω (k+1) b 7: Truncate and normalize ω if clipping is used 8: end for b (K) Ensure: Occupancy-ratio estimate ω 6:
F.3. First-stage density-ratio estimation The fitted iteration requires estimates of two density ratios: the initial ratio ω0 =
dd0 , dν
d0 (ds, da) = µ0 (ds)π(da | s),
and the one-step ratio
dνπ+ . dν The initial distribution µ0 specifies the starting-state population whose target occupancy is being evaluated. Given samples Sj0 ∼ µ0 , drawing A0j ∼ π(· | Sj0 ) gives Xj0 = (Sj0 , A0j ) ∼ d0 . These numerator samples, together with the offline data sample {Xi }ni=1 ∼ ν, can be used to estimate + ′ + ω0 . Similarly, the successor pairs Xi+ = (Si′ , A+ i ), with Ai ∼ π(· | Si ), are sampled from νπ = νPπ . + n Hence {Xi }i=1 , together with the same offline data sample, can be used to estimate cπ . b 0 and cbπ , Any density-ratio learner that targets these two ratios can be used to construct ω including methods based on classification, f -divergence, or Bregman-risk objectives. These estimates are then held fixed throughout the adjoint Bellman iteration. For numerical stability, implementations may clip extreme ratios or apply post-hoc moment calibration. cπ =
F.4. Population contraction The backward-regression representation in Lemma F.1 identifies the population update underlying Algorithm 2. The next result states its L1 (ν) contraction and fixed point. Theorem F.2 (Backward-regression FORE contraction). Assume Condition C1 and let γ ∈ [0, 1). Then Bπγ : L1 (ν) → L1 (ν) is well defined and satisfies Bπγ ω − Bπγ ω ′
L1 (ν)
≤ γ ω − ω ′ L1 (ν)
for all ω, ω ′ ∈ L1 (ν).
Moreover, dπ,γ ≪ ν, and ωπ,γ = ddπ,γ /dν is the unique fixed point of Bπγ in L1 (ν). Hence, for any ω ∈ L1 (ν), (Bπγ )K ω − ωπ,γ 1 ≤ γ K ∥ω − ωπ,γ ∥L1 (ν) . L (ν)
53
Proof. Lemma F.1 identifies Bπγ ω − Bπγ ω ′ as the ν-density of the signed measure γ{(ω − ω ′ )ν}Pπ . Nonexpansiveness of Markov kernels for finite signed measures (Cover and Thomas, 2006) gives Bπγ ω − Bπγ ω ′
≤ γ|(ω − ω ′ )ν|(X ) = γ ω − ω ′ L1 (ν) .
L1 (ν)
The discounted occupancy recursion dπ,γ = (1 − γ)d0 + γdπ,γ Pπ shows that ωπ,γ is a fixed point after taking Radon–Nikodym derivatives. The contraction gives uniqueness in L1 (ν), and iterating it yields the geometric bound. F.5. Projection error and adjoint Bellman completeness Theorem F.2 describes the ideal population iteration, in which the backward conditional mean ← ω is evaluated exactly. Algorithm 2 instead estimates this backward conditional mean within a Pπ,ν supervised-learning class. We isolate the population effect of this projection. 2 + For a regression class M, let Π+ M g denote an L (νπ )-projection of g onto M. The corresponding population FORE update is e π ω = (1 − γ)ω0 + γcπ Π+ P ← ω. B γ M π,ν e π differs from the exact adjoint Bellman update only by replacing the exact backward Thus, B γ conditional mean with its population projection onto M. For a set W ⊆ L1 (ν) of possible iterates, define the inherent adjoint Bellman error
bM (W) = sup inf
ω∈W m∈M
← m − Pπ,ν ω
L2 (νπ+ )
.
← ω ∈ M for every ω ∈ W (Uehara We say that M is adjoint Bellman complete over W if Pπ,ν et al., 2021). This is the direct analogue of Bellman completeness for FQE: the regression class must contain the one-step adjoint Bellman image of every iterate encountered by the fitted procedure. In this case, bM (W) = 0.
Lemma F.3 (Population projected FORE perturbation). Assume Condition C1 and let γ ∈ [0, 1). (k) , and set W = {ω eπω e (k+1) = B e (0) , . . . , ω e (K−1) }. Then Let ω K γe e (K) − ωπ,γ ω
L1 (ν)
e (0) − ωπ,γ ≤ γK ω
L1 (ν)
+
γ(1 − γ K ) bM (WK ). 1−γ
Consequently, if M is adjoint Bellman complete over WK , then e (K) − ωπ,γ ω
L1 (ν)
e (0) − ωπ,γ ≤ γK ω
L1 (ν)
.
e (k) . The Proof of Lemma F.3. For each k, add and subtract the exact population update Bπγ ω contraction in Theorem F.2 gives e (k+1) − ωπ,γ ω
L1 (ν)
e (k) − ωπ,γ ≤γ ω
L1 (ν)
(k) eπω e (k) + B − Bπγ ω γe
54
L1 (ν)
.
The perturbation term is (k) eπω e (k) B − Bπγ ω γe
n
← (k) ← (k) e e − Pπ,ν ω = γ cπ Π+ M Pπ,ν ω
L1 (ν)
o L1 (ν)
← (k) ← (k) e e = γ Π+ − Pπ,ν ω M Pπ,ν ω
L1 (νπ+ )
← (k) ← (k) e e ≤ γ Π+ − Pπ,ν ω M Pπ,ν ω
L2 (νπ+ )
= γ inf
m∈M
← (k) e m − Pπ,ν ω
L2 (νπ+ )
≤ γbM (WK ), where the second equality uses νπ+ (dx) = cπ (x)ν(dx), the next inequality uses that νπ+ is a probability distribution, and the final equality is the defining property of the L2 (νπ+ )-projection. Hence e (k+1) − ωπ,γ ω
L1 (ν)
e (k) − ωπ,γ ≤γ ω
L1 (ν)
+ γbM (WK ).
Iterating this recursion gives e (K) − ωπ,γ ω
L1 (ν)
e (0) − ωπ,γ ≤ γK ω
L1 (ν)
+γ
K−1 X
γ j bM (WK ).
j=0
Evaluating the geometric sum gives the first displayed bound in the lemma. Under adjoint Bellman completeness over WK , the inherent adjoint Bellman error is zero, giving the final display. Lemma F.3 makes the limitation of this variant of FORE explicit. Without adjoint Bellman completeness, the backward-regression variant converges only up to the inherent adjoint Bellman error.
G. Numerical Experiment Details This appendix records the exact constructions used for Section 6. The reported finite-sample summaries use common random draws across estimators at a fixed sample size and repetition index. G.1. Baird-style finite MRP The state space is X = {u1 , . . . , u6 , ℓ}. The six states uj are symmetric upper states and ℓ is the lower state. We use γ = 0.95, ν(uj ) = 0.95/6,
ν(ℓ) = 0.05,
d0 (uj ) = 1/6,
d0 (ℓ) = 0.
The target transition matrix has the aggregate form P (uj , um ) = 0.05/6,
P (uj , ℓ) = 0.95,
The scalar value feature is
P (ℓ, um ) = 0.20/6,
ϕ(uj ) = 0.1,
P (ℓ, ℓ) = 0.80.
ϕ(ℓ) = 1.
Rewards are defined by r = ϕ − γP ϕ, so r(uj ) = −0.80725,
r(ℓ) = 0.221, 55
Qπ = ϕ,
Vπ = 0.1.
This construction keeps the six-upper/one-lower star layout and chooses the target transition, offline data distribution, and rewards to isolate fitted policy evaluation. For linear FQE with qβ = βϕ, the population update has the one-dimensional form βk+1 = 1 − λ + λβk ,
λ=γ
Eν {ϕ(X)ϕ(X + )} = 2.1031722689. Eν {ϕ(X)2 }
Thus Qπ ∈ Q, but the projected Bellman recursion expands errors under the Bellman projection induced by the offline data distribution. The discounted occupancy ratio is constant on the upper states and equal to ωπ,γ (uj ) = 0.2211217321,
ωπ,γ (ℓ) = 15.7986870897.
It is represented exactly by the normalized log-linear class ωθ (x) =
exp{θ 1(x = ℓ)} . Eν [exp{θ 1(X = ℓ)}]
The fixed point is θ⋆ = 4.7432986067. The derivative of the scalar FORE update at θ⋆ has magnitude 0.1425. Projecting FQE under the target occupancy distribution gives scalar multiplier 0.8009962427. With tabular FQE, the value feature matrix is the 7 × 7 identity. The Bellman image remains in the fitted value class, the projected Bellman operator has contraction multiplier γ = 0.95, and the population iterates converge to the exact value function. The tabular finite-dimensional objectives for DualDICE, MWL, and MQL are solved exactly in this finite example. The Baird-style panel in the main text focuses on the population recursions, where the separation between offline-data projection and target-occupancy projection is algebraic. G.2. Linear-Gaussian policy evaluation The continuous example uses X = (S, A) ∈ R2 . Offline samples are drawn from ν = N (0, Σb ), where !
Σb =
1.5 0 . 0 0.4
Under the target policy, S + = 0.7S + 0.5A + εs ,
A+ = −0.8S + + εa ,
where εs ∼ N (0, 0.4) and εa ∼ N (0, 0.25) are independent. The initial distribution is the stationary Gaussian distribution of this target transition, with covariance !
Σ⋆ =
0.508242 −0.406593 . −0.406593 0.575275
Thus the target density ratio relative to ν is exponential quadratic: ω⋆ (x) ∝ exp{θ1⋆ s2 + θ2⋆ sa + θ3⋆ a2 }, Let
θ⋆ = (−1.9304504505, −3.2, −0.75).
h⋆ (x) = θ1⋆ s2 + θ2⋆ sa + θ3⋆ a2 .
56
The normalized log-linear ratio class used by FORE, MWL, and DualDICE has sufficient statistics (h⋆ (x), s, a). The target ratio has coefficient (1, 0, 0) in this class. The class is not closed under the target transition or the corresponding adjoint Bellman update. For the main finite-sample experiment, the discount is γ = γ0 . The value feature is q(x) = a2 + 0.7241380519, and the reward is set to
r(x) = q(x) − γE{q(X + ) | X = x}.
It follows that Qπ = q. Since the initial distribution is stationary under the target policy, the true policy value is Vπ = EΣ⋆ {q(X)} = 1.299413. Linear FQE, FORE-reweighted FQE, and MQL use the value class {β0 q + β1 s + β2 a : β ∈ R3 }, whose true coefficient is (1, 0, 0). The class is not Bellman complete, because Pπ q contains the missing quadratic terms s2 and sa. The corresponding population multipliers are as follows. Under the offline data distribution, the linear FQE multiplier is 1.220598. The population FORE recursion has effective contraction multiplier 0.085500. When the FQE projection distribution is replaced by the target occupancy distribution recovered by FORE, the dominant projected FQE multiplier is 0.682476. Finite-sample experiments use n ∈ {500, 1000, 2000, 5000, 10000} offline transitions and 300 independent repetitions at each sample size. For FORE, each update solves the empirical moment equation for the three log-ratio sufficient statistics. FORE-reweighted FQE uses the same value class as linear FQE, but replaces the empirical least-squares weights by the fitted FORE density weights from the same sample. MWL, MQL, and DualDICE use a random-Fourier RBF critic with 128 features and an intercept term. The RBF bandwidths, critic ridge penalties, and MWL density shrinkage coefficient are fixed once using an independent offline-data population calculation and then held fixed across all sample sizes and repetitions. MWL and MQL use bandwidth 2.2 and ridge penalty 0.1. MWL uses density shrinkage 10−3 . DualDICE uses bandwidth 0.4, ridge penalty 10−4 , and no density shrinkage. The DualDICE potential ridge is used only to stabilize the finite critic solve. For the discount sweep in Figure 5, we use γ ∈ {0.5, 0.6, 0.7, 0.8, 0.85, 0.9, 0.93, 0.95, 0.97, 0.98, 0.99, 0.995, 0.997, 0.999}. The sample size is n = 5000, with 500 repetitions at each discount. The transition distribution, initial distribution, offline data distribution, value class, ratio class, and critic classes are the same as in the main experiment. At each discount, rewards are set to rγ (x) = q(x) − γE{q(X + ) | X = x}. Linear FQE and FORE-reweighted FQE use 500 fitted-Q updates for every repetition and discount. FORE iterates until the relative change in the log-ratio parameter is below 10−7 , with a maximum of 100 updates. The linear FQE panel reports the fixed-iteration error at every discount, including discounts for which the empirical projected Bellman recursion is noncontractive. 57