Optimal Value Inference for Reinforcement Learning

1 Introduction

• The target is the optimal average reward J∗, the best long-run performance attainable by a stationary Markov policy, with uncertainty quantification from observational trajectories.This distinguishes the problem from evaluating a prespecified policy or learning a policy with low suboptimality.Source: §1 · pp. 1–2
• Optimal-value inference is difficult because action ties make optimality nonsmooth, while maximization recursively determines continuation values and future decisions.The method separates inference about achievable value from the algorithmic question of whether a near-optimal policy has already been learned.Source: §1 · p. 2
• The proposed method replaces Bellman maximization with softmax and estimates the resulting self-induced fixed-point nuisances (Qβ, Jβ) using a Neyman-orthogonal score.The score’s remainder depends on estimation errors for (Qβ, Jβ) and an adjoint weight function rather than on an optimal-policy estimator rate.Source: §1 · pp. 2–3
• The inference procedure allows time-varying behavior policies and yields NH-rate asymptotic normality when either the number of trajectories or horizon diverges, under regular mixing conditions.The required nuisance rate is op((NH)^-1/4), and the result applies when NH diverges.Source: §1 · pp. 2–3

1.1 Related Work

• The paper’s distinction from prior work is that policy generation and evaluation are jointly smoothed through one Bellman fixed point before orthogonalization, rather than handled by post-hoc policy smoothing or fixed-policy evaluation.This construction also supports time-varying behavior policies and fixed or diverging trajectory horizons.Source: §1.1 · pp. 3–4
• Unlike related average-reward and operations research work focused on fixed-policy estimation, policy learning, or deployment, this paper quantifies uncertainty about the best achievable long-run performance before deployment.The scope includes recommendation, experimentation, language-model evaluation, and agentic systems.Source: §1.1 · p. 4

Data and model

• The data consist of N independent H-transition trajectories with states, actions, rewards, and next states generated under a common initial-state and behavior-data law.The behavior policy can vary across time, while each time-specific decision rule remains Markov.Source: §2 · p. 5
• The environment is a finite, tabular, time-homogeneous Markov decision process specified by state and action spaces, a transition kernel P, and a conditional mean reward function R∗.The transition kernel also acts as a linear operator mapping state functions to state-action functions.Source: §2 · p. 5

Policies

• Policies are stationary Markov maps from states to action distributions, whereas the behavior policy is generally nonstationary because its Markov decision rules may differ across time.The stationary behavior case is the special case in which all time-specific decision rules are identical.Source: §2 · p. 5

Average-reward formulation

• The paper imposes irreducibility for every stationary policy, ensuring that each policy’s average reward is independent of the initial state and can be denoted Jπ.This condition is identified as analogous to Assumption 1 in Liao et al. [2022], with the initial-state independence supported by Puterman [2014, Theorem 8.2.6].Source: §2 · p. 5

Target parameter

• The parameter of interest is the optimal average reward J∗, attained by an optimal stationary policy, together with the uniquely anchored relative action-value function Q∗ common to all optimal policies.The relative-value representation is anchored by requiring zero arithmetic mean, resolving its additive-constant ambiguity; the optimal function satisfies the Bellman optimality equation.Source: §2 · p. 6

3 Self-Induced Bellman Equation

• Post-hoc softmax changes future-state action probabilities without recomputing continuation values, leaving a separate policy-evaluation problem and upstream learning error.Fixed-policy orthogonality removes first-order evaluation-nuisance sensitivity but does not automatically control policy-learning error, especially near nonunique optima.Source: §3 · pp. 6–7
• The self-induced equation jointly defines a softened policy and the action-value function evaluating continuation values under that same policy, smoothing the optimal value problem itself.The induced policy remains a smooth function of Qβ, so policy dependence is handled within one fixed-point formulation.Source: §3 · pp. 7–8
• Qβ is identifiable only up to an additive constant, so the analysis anchors it; under Assumptions 2.1 and 3.4, the anchored solution exists and is unique for every β > 0.Existence follows from Brouwer’s fixed-point theorem, while Assumption 3.4 excludes perturbation directions invisible to the Bellman residual.Source: §3 · pp. 7–8
• Any self-induced solution is also the ordinary Bellman solution for its induced policy, so Jβ equals that policy’s long-run average reward under the original objective.Thus Qβ both induces πβ through softmax and evaluates its continuation values, eliminating the population-level split of the post-hoc route.Source: §3 · p. 8
• Theorem 3.8 bounds the smoothed pair’s deviation from the optimal pair uniformly over β under Assumptions 2.1 and 3.4, with the comparison based on the smallest positive optimality gap Γ.When Γ = +∞, Jβ = J∗ for every β > 0.Source: §3 · p. 8

4.1 Adjoint Weights and Orthogonal Scores

• A unique adjoint weight defines the orthogonal score, eliminating first-order sensitivity to estimating the Bellman pair and softened policy.The derivative operator captures both direct Q perturbations and induced softmax-policy variation; the score is φβ(Z; J, Q, λ) = J + λ(S, A)(R − J + Vβ(Q)(S′) − Q(S, A)).Source: §4.1 · pp. 9–10
• Cross-fitting estimates J, Q, and λ on training folds and evaluates the orthogonal score on held-out trajectories.The construction allows any fixed number K ≥ 2 of folds, with K = 2 sufficient for the theoretical results.Source: §4.1 · p. 10

4.2 Theoretical Results on Inference

• Under bounded rewards, positivity, nondegenerate conditional variation, and suitable nuisance rates, the estimator is asymptotically normal for both fixed and diverging horizons.For diverging horizons, uniformly summable strong mixing controls dependence from nuisance replacement and variance estimation, while Bellman-score increments form a martingale-difference sequence.Source: §4.2 · pp. 10–11
• The H transitions within each trajectory contribute first-order information because cross-time covariances of the leading score increments vanish.When H diverges, this information accumulation produces the stated N H rate under the mixing condition.Source: §4.2 · p. 11
• A single variance estimator is consistent in both regimes, enabling asymptotically valid confidence intervals for the optimal value.Consistency uses trajectory averaging for fixed H and a quadratic-variation argument when H grows; as β increases, the inference quantities converge to those for the uniform policy over tied optimal actions.Source: §4.2 · p. 12

5.1 Estimation of the Nuisances from the Self-Induced Bellman Equation

• The Bellman nuisance estimator minimizes a regularized minimax criterion over bounded Q and J, converting the conditional Bellman restriction into observable unconditional moments despite the nonlinear self-induced value map.Uniform boundedness ensures optimization over a fixed bounded subset with an exact empirical minimizer; identification uses an exact secant representation of the nonlinear residual.Source: §5.1 · p. 13
• Theorem 5.1 provides a high-probability finite-sample error rate for the Bellman nuisance estimator under Assumptions 3.4 and 4.4.The bound holds for n ≥ 2 and δ ∈ (0, 1), with a constant independent of n, β, and δ.Source: §5.1 · p. 13

5.2 Estimation of the Adjoint Weight

• The adjoint-weight estimator replaces unknown derivative weights with weights evaluated at a first-stage Q estimator and stabilizes the empirical quadratic criterion with a finite-state-action norm.The stabilized norm prevents degeneracy along poorly sampled directions, while boundedness restricts optimization to a fixed class containing λβ.Source: §5.2 · pp. 13–14
• Theorem 5.2 bounds adjoint-weight error in terms of a generic first-stage Q error, with plug-in error of order βrQ because the derivative-weight map is O(β)-Lipschitz.Combining this generic result with the Bellman estimator yields Corollary 5.3’s nuisance rate.Source: §5.2 · p. 14
• Choosing β ≫ log n makes the exponential smoothing bias o(n^-1/2), while β ≪ √n (log n)^3/2 ensures the nuisance rates satisfy Assumption 4.7.These sufficient conditions combine the smoothing-bias result with finite-state norm equivalence, Theorem 5.1, and Corollary 5.3.Source: §5.2 · p. 14

6.1 Synthetic Experiments

• The synthetic design tests nonunique optimal actions under stationary, linear, and polynomial behavior mixtures, comparing Proposed with Oracle and Hardmax-based estimators using coverage, RMSE, and interval length.The experiment uses |S| = 100, |A| = 100, N independent trajectories of H transitions, and β = 4 selected within 0.5% of the optimum.Source: §6.1 · pp. 14–16
• Proposed stays near Oracle with near-nominal coverage and RMSE declining approximately at H^-1/2 and N^-1/2 rates, while Hardmax-DR undercovers and sequential Hardmax becomes highly variable.These results support the theory for fixed and diverging horizons; studentized errors also closely follow the standard normal benchmark across stationary and time-varying behavior policies.Source: §6.1 · pp. 15–16, Figure 1 · p. 15, Figure 3 · p. 18

6.2 Bike Repositioning

• The bike application uses 2.03 million Citi Bike trips aggregated hourly into a 27-state, five-action MARO simulator with 16-day behavior trajectories.The abstract state records low, middle, or high inventory across three zones, and rewards served demand net of unmet demand and repositioning cost.Source: §6.2 · p. 16
• In the bike simulator, Proposed approaches the reference optimum while substantially exceeding Hardmax-DR and behavior, using markedly fewer bike moves and leaving less demand unmet.At selected bβ = 16, the reference optimal average reward is Jref = 0.7996, and confidence intervals tighten as N increases.Source: §6.2 · p. 16, Figure 4 · p. 18

6.3 AI Agentic Tool Use

• The ToolSandbox application analyzes 296 episodes and 1,047 micro-steps across 30 states and 36 actions, using task-clustered two-fold cross-fitting and strata Lmin = 1 versus Lmin ≥2.The empirical greedy-policy benchmark is 0.8002, and plug-in smoothing selects bβ = 0.5.Source: §6.3 · pp. 16–17
• Across ToolSandbox task strata, Proposed estimates remain near empirical references, whereas Hardmax-DR falls below benchmarks and develops unstable fitted action values and large Bellman residuals.For Lmin = 1, the reference is 0.9825; for Lmin ≥2, it is 0.4386, with instability worsening on harder multi-step tasks and fitted Q-functions reaching 10^4–10^5.Source: §6.3 · pp. 17–18, Figure 5 · p. 19, Figure 6 · p. 19

• A self-induced Bellman equation converts recursively coupled, statistically irregular maximization into a smooth policy–value object for optimal value inference.The adjoint weight yields an orthogonal score, while approximation analysis controls the smoothing bias J∗−Jβ.Source: §7 · p. 19
• The framework provides estimable Bellman and adjoint-weight nuisances with finite-sample rates sufficient for a cross-fitted procedure under fixed and diverging horizons.Source: §7 · pp. 19–20
• Promising extensions include alternative smooth maximum approximations, continuous or high-dimensional spaces, learned rewards, discounted or finite-horizon objectives, and structured applied settings.Discounted and finite-horizon problems would use discount-weighted or time-dependent Bellman and adjoint equations; domain structure could improve estimation in pricing, recommendation, and agentic systems.Source: §7 · p. 20
• A further direction connects offline inference with online deployment by quantifying improvement from historical data before updating policies with accumulating operational evidence.Source: §7 · p. 20

A Notation Summary

• The framework uses state and action spaces S and A, transition kernel P, conditional mean reward R∗, stationary policies Π, and behavior policy πb.Observed data consist of trajectories τi and one-step transitions Zt = (St, At, Rt+1, St+1).Source: A Notation Summary · p. 25
• Jπ denotes long-run average reward, while Qπ is the zero-average fixed-policy relative action-value function.The optimal quantities are J∗, the optimal average reward, and Q∗, the common anchored relative action-value function of optimal stationary policies.Source: A Notation Summary · p. 25
• The softmax policy πβ,Q is induced by a generic action-value function Q, and Vβ(Q) is its softmax-smoothed value map.The anchored self-induced Bellman solution is (Qβ, Jβ), with induced policy πβ,Qβ.Source: A Notation Summary · p. 25
• Γ denotes the smallest positive optimality gap of Q∗, quantifying separation in the optimal relative action values.This gap is part of the notation for the optimal-policy characterization.Source: A Notation Summary · p. 25
• The orthogonal-score notation includes the anchored action-value space Q, derivative weights ωβ,Q, aggregation operator Dβ, and orthogonal score φβ(Z; J, Q, λ).The score targets Jβ and uses the adjoint weight λβ.Source: A Notation Summary · p. 25
• Trajectory-data notation includes the pooled behavior law ¯P, state-action marginal ¯µ, next-state marginal ¯ν, martingale increment ξi,t, nuisance remainder bk, and score variance σ2.The increment is defined as φβ(Zi,t) − Jβ.Source: A Notation Summary · p. 25

B Proof for Section 2

• Optimal policies share a unique anchored relative action-value function Q∗ satisfying the Bellman optimality equation.Full-support stationary distributions force every action used by an optimal policy to attain the statewise maximum, yielding a common fixed-policy solution and uniqueness under the anchoring constraint.Source: B Proof for Section 2 · pp. 25–26

C.1 Proof of Lemma 3.2

• Adding a constant to Qβ leaves the softmax policy unchanged while shifting its induced value by the same constant, preserving the self-induced Bellman equation.Thus (eQ, Jβ) also satisfies equation (3.1).Source: §C.1 · p. 26

C.2 Proof of Theorem 3.3

• A softmax fixed point Qβ exists because policy evaluation is continuous on a compact invariant set, so Brouwer’s theorem yields Qβ = Qπβ satisfying (3.1).Assumption 2.1 makes every stationary policy irreducible and unichain, ensuring unique anchored evaluation and continuity of π 7→Qπ.Source: §C.2 · pp. 26–27

C.3.1 Uniform Bound on Signed Weights

• The signed softmax weights satisfy a uniform envelope ∑a∈A |ωβ,Q(a | s)| ≤ 1+2 log |A|, independent of Q, s, and β.The proof combines the row-sum identity with entropy bounds for the softmax probabilities.Source: §C.3.1 · p. 27

C.3.2 A Sufficient Condition for Signed Aggregation Identification

• If CAρ(P) < 1, the signed aggregation identification condition holds because Dobrushin contraction and the aggregation span bound force every anchored null-space solution to vanish.Specifically, sp(PDq) ≤ ρ(P)sp(Dq) and sp(Dq) ≤ CA sp(q), implying q = 0 and j = 0.Source: §C.3.2 · p. 28
• The Dobrushin argument uses span-seminorm invariance to additive constants and contraction of state-function spans under P.This supplies the contraction component needed to establish signed aggregation identification.Source: §C.3.2 · p. 28

C.3.3 Proof of Proposition 3.6

• Theorem 3.3’s anchored solution is unique, so together with existence it yields a unique anchored pair (Qβ, Jβ).The proof uses an allowable state-wise signed action aggregation operator and Assumption 3.4 to show the difference between two anchored solutions is zero.Source: §C.3.3 · p. 29

C.4 Uniform Boundedness and Approximation

• The approximation analysis also establishes convergence results for the continuation value, induced policy, and derivative operator needed later.These results are introduced as part of the bounds and approximation framework for Theorem 3.8.Source: §C.4 · p. 29

C.4.1 Preliminary Bounds

• The self-induced solutions remain uniformly bounded over all β > 0, with both supβ>0 ∥Qβ∥∞ and supβ>0 |Jβ| finite.Compactness of the stationary policy class and continuity of fixed-policy evaluation imply boundedness of Qβ and Jβ.Source: §C.4.1 · p. 29
• Assumption 3.4 yields a quantitative inverse bound uniformly over all allowable aggregation operators, independent of D, β, n, N, and H.The supremum-norm counterpart is horizon-free and depends only on P and |A|.Source: §C.4.1 · pp. 29–30

C.4.2 Approximation to the Optimal Bellman Pair

• The optimal Bellman pair approximation is uniformly controlled in β under Assumptions 2.1 and 3.4, through the smoothing error at Q∗.The proof uses a path-averaged derivative aggregation operator, an exact secant equation, and the uniform inverse bound.Source: §C.4.2 · p. 30
• If Γ = +∞, then Qβ = Q∗ and Jβ = J∗ exactly for every β > 0.With no suboptimal actions contributing to the smoother, the smoothing error is zero and the uniform inverse forces exact equality.Source: §C.4.2 · p. 30
• The average-reward gap satisfies 0 ≤ J∗ − Jβ ≤ Ce^-βΓ, and equality holds exactly when Γ = +∞.Because Jβ is the average reward of πβ and J∗ is optimal over Π, Jβ ≤ J∗; Proposition C.6 supplies the exponential bound.Source: §C.4.2 · p. 31

C.4.3 Convergence of the Induced Objects

• As β increases, the induced value and policy converge to the optimal value and the uniform policy over Bellman-maximizing actions, with exact equality when Γ = +∞.The derivative operator Dβ likewise converges to Dπunif, and equals it exactly when Γ = +∞.Source: §C.4.3 · pp. 31–32

D Proofs for Section 4

• The proofs for Section 4 cover derivative and orthogonality tools, cross-fitted remainder control, diverging-horizon dependence arguments, and martingale and quadratic-variation results.They culminate in proofs for the fixed- and diverging-horizon inference theorem and its corollary.Source: D Proofs for Section 4 · p. 32

D.1.1 Derivative Calculus and Taylor Remainder of the Smoothed Value Map

• The smoothed value map admits a uniform second-order Taylor remainder bound, controlling Q-estimation error in the cross-fitted score.The bound follows from uniformly bounded first derivatives and a Hessian operator norm of order Cβ.Source: §D.1.1 · pp. 33–34

D.1.2 Adjoint Weight Existence and Neyman Orthogonality

• The adjoint weight exists uniquely, and the score is Neyman-orthogonal because normalization, the adjoint equation, and the Bellman residual eliminate the truth-direction derivatives.The construction uses the one-dimensional left nullspace of Aβ and full support of the pooled one-step law.Source: §D.1.2 · p. 34

D.2.1 Cross-Fitted Decomposition

• The cross-fitted estimator decomposes into a leading oracle term, a foldwise population bias term, and a centered empirical remainder.The decomposition is obtained by adding and subtracting the oracle score and foldwise conditional means.Source: §D.2.1 · p. 35

D.2.2 Score Perturbation Expansion and Population Bias

• Under Assumptions 2.1, 3.4, 4.1, and 4.4, BN,H = op(N −1/2) under Assumption 4.7 and BN,H = op((NH)−1/2) under Assumption 4.8.Source: §D.2.2 · p. 36

D.2.3 Perturbation Bounds and Empirical Score Replacement

• On the estimator boundedness event, score perturbations satisfy uniform foldwise bounds, and Assumption 4.6 implies that event occurs with probability tending to one.These bounds support replacing empirical plug-in scores with their oracle counterparts.Source: §D.2.3 · p. 37
• Cross-fitted empirical score replacement is op(1) in the pooled L2 norm when nuisance errors satisfy the stated nonlinear consistency condition.The result holds uniformly across folds under Assumptions 2.1, 3.4, 4.1, 4.4, and 4.6, with the high-probability bounded-error event established from common support and nuisance-rate conditions.Source: §D.2.3 · p. 38

D.3.1 Discussion of Assumption 4.9

• Time-varying behavior changes the distribution of state-action pairs but not the conditional reward-transition law, allowing pooled one-step centering and strong-mixing covariance control.Conditional on training data, the predictable nuisance drift is fixed and bounded; Assumption 4.9 transfers strong mixing to the covariance bounds needed for diverging-horizon fluctuations.Source: §D.3 · p. 39, §D.3.1 · p. 39

D.3.2 Cross-Fitted Diverging-Horizon Empirical Fluctuation

• The cross-fitted nuisance fluctuation decomposes into martingale and centered predictable-drift components, with the martingale component op((NH)^−1/2) and the predictable drift op(1).Cross-fitting gives conditional independence across evaluation trajectories, while Assumption 4.8 and the score-replacement bounds imply max_k ∥∆β,−k∥¯ PH,2 = op(1).Source: §D.3.2 · pp. 39–42

D.4 Oracle Score and Variance

• The oracle score increments have conditional mean zero and form a martingale-difference array after inserting zero boundary increments between trajectories.The filtration reveals each current state-action pair before its reward and next state, and the self-induced Bellman equation yields E[ξi,t | Fi,t−1] = 0.Source: §D.4 · p. 42
• The realized average quadratic variation converges to σ2, which remains bounded above and below uniformly whenever β ≥ C/v∗min.Predictable and realized quadratic variations differ by op(1), and Proposition D.17 gives constants 0 < c < C < ∞ independent of N, H, and β over relevant horizons.Source: §D.4 · pp. 43–44

C.4.3 Convergence of the Induced Objects

• When Γ<∞, ||v_β−v*||∞≤C/β, whereas Γ=+∞ implies v_β=v* exactly.The finite-Γ bound absorbs the fixed MDP quantity Γ−1 into C.Source: §D.4 · p. 44

D.4 Oracle Score and Variance

• The nondegeneracy condition requires 2 min_(s,a) v*(s,a)>0 under the stated threshold on β.Source: §D.4 · p. 44
• By (3.1), the Bellman residual in ξ_i,t has conditional mean zero given (S_i,t,A_i,t).Source: §D.4 · p. 44
• The oracle variance satisfies c≤σ^2≤C, using adjoint normalization, Jensen’s inequality, and uniform bounds on v_β and λ_β.The lower bound follows from ĒP_H[λ_β(S,A)]=1 and the lower bound on v_β; the upper bound uses Assumption 4.4, Corollary C.4, and Corollary F.2.Source: §D.4 · p. 44

Fixed-H regime

• For fixed H, the bias and empirical remainders are op(N^-1/2), hence negligible relative to σ.The decomposition yields BN,H = op(N^-1/2) and EN,H = op(N^-1/2), while Proposition D.17 ensures σ ≥ c eventually.Source: §D.5 · pp. 44–45
• A bounded independent triangular-array CLT and Slutsky’s theorem establish the smoothed-value conclusion for fixed H.Martingale orthogonality gives the variance structure, bounded increments ensure Lindeberg conditions, and the remainders are negligible.Source: §D.5 · p. 45

Growing-H regime

• For growing H, both remainders are op((NH)^-1/2), and a martingale CLT for the augmented lexicographic array yields the smoothed-value conclusion.Uniform variance lower bounds and bounded increments validate the normalization and McLeish’s martingale central limit theorem [McLeish, 1974, Theorem 2.3].Source: §D.5 · p. 45

Optimal-value conclusion

• The smoothed and optimal values differ by a normalized term converging to zero, so Slutsky’s theorem proves the optimal-value conclusion.Specifically, NH(Jβ − J*)/σ → 0 because σ ≥ c.Source: §D.5 · p. 45

D.6 Convergence to Uniform Optimal-Policy Evaluation

• For each horizon H, a unique λunif exists for ordinary fixed-policy evaluation under the uniform policy over maximizing actions.The construction uses derivative-operator convergence and the allowability of the uniform-policy operator.Source: §D.6 · pp. 45–46
• When Γ = +∞, λβ = λunif and σ2 = σ2_PE exactly for every β > 0.In this case, the softmax derivative operator equals the uniform-policy operator and Vβ(Qβ) = V∗.Source: §D.6 · pp. 45–46
• Under the cited assumptions, the softmax adjoint weight satisfies ∥λβ − λunif∥¯µH,2 ≤ C(1 + β)e−βΓ, with C independent of β, N, and H.Source: §D.6 · pp. 45–46

D.7 Feasible Variance Estimation

• The unified feasible scale estimator provides the variance-estimation procedure used for inference.Its consistency is established separately under fixed-horizon and growing-horizon conditions.Source: §D.7 · p. 46

D.7.1 Fixed-Horizon Consistency of the Unified Estimator

• Under the fixed-H conditions of Theorem 4.11, the unified estimator satisfies bσ2 − σ2 = op(1) and bσ/σ →p 1.The proof combines quadratic-variation and nuisance-replacement bounds with the eventual lower bound σ2 ≥ c > 0.Source: §D.7.1 · pp. 46–47

D.7.2 Diverging-Horizon Consistency of the Unified Estimator

• Under the growing-H conditions of Theorem 4.11, the unified estimator likewise satisfies bσ2 − σ2 = op(1) and bσ/σ →p 1.The result follows from growing-H nuisance-rate conditions, replacement-error control, uniform envelope bounds, and a lower bound on σ2.Source: §D.7.2 · p. 47

D.7.3 Proof of Corollary 4.13

• In both fixed- and growing-H regimes, studentization yields d−→N(0, 1), and inversion gives the unified Wald interval.The variance estimator is consistent in both regimes by the cited lemmas, enabling Slutsky’s theorem.Source: §D.7.3 · p. 47

E Proofs for Section 5.1

• The proof of Theorem 5.1 combines an exact secant identity, a uniform residual lower bound, high-probability empirical bounds, and estimator analysis.The residual is δQ,J(Z) := R −J + Vβ(Q)(S′) −Q(S, A), with conditional mean mQ,J(s, a).Source: E Proofs for Section 5.1 · p. 48

E.1 Exact Secant Geometry and Global Residual Identification

• The nonlinear Bellman residual is represented through an operator Dβ,Q that averages the derivative of Vβ along the segment from Qβ to Q.The operator is allowable because the path-averaged weights satisfy the required row-sum and signed-envelope constraints.Source: §E.1 · p. 48
• Uniform quantitative identification bounds the residual by c(∥q∥¯µ,2 + |j|) over every allowable operator, with c independent of n and β.Compactness of the allowable operator family and injectivity under Assumption 3.4 yield the uniform constant.Source: §E.1 · pp. 48–49
• Applying the allowable-operator bound to Dβ,Q gives quantitative identification through the Bellman residual for every (Q, J).The residual difference is −δJ1 −δQ + PDβ,QδQ, while mQβ,Jβ = 0.Source: §E.1 · p. 49

E.2 Bounds for the Empirical Rate Argument

• Residual increments satisfy ∥δQ,J −δQβ,Jβ∥2 ≤ C(∥Q −Qβ∥¯µ,2 + |J −Jβ|) and the same order almost surely.The bound follows from finite support, full support of ¯µ, and the uniform signed-weight envelope.Source: §E.2 · pp. 49–50
• With probability at least 1 −δ, empirical norm, truth-criterion, and residual-increment process bounds jointly control the fast-rate argument.The constants are independent of n, β, and δ, and remain horizon-uniform for pooled one-step laws with common support.Source: §E.2 · pp. 50, 52

E.3 Proof of Theorem 5.1

• Theorem 5.1’s proof combines localized empirical optimality with star-shapedness to establish e ≤ Cη_n, yielding the theorem’s displayed rate.The argument holds for every n ≥ 2 and δ ∈ (0, 1) on the event E_n.Source: §E.3 · p. 53

F Proofs for Section 5.2

• The Section 5.2 proofs derive a population lower bound, compare reference and feasible criteria, and combine these ingredients with empirical optimality of bλ_β.The comparison distinguishes population, reference empirical, and feasible criteria before proving Theorem 5.2.Source: F Proofs for Section 5.2 · p. 53, §F.2 · p. 55

F.1 From Primal Injectivity to Dual Quantitative Identification

• Primal injectivity implies a uniform quantitative lower bound for adjoint moments and normalization discrepancies, with constants independent of n and β, and also N and H in pooled-law settings.The proof uses bijectivity of T_D, full-support nondegeneracy, compactness, and homogeneity.Source: §F.1 · pp. 53–54
• The quantitative identification result yields a uniformly bounded adjoint weight λ_β, and the adjoint criterion is exactly minimized at λ_β.The bound is independent of n and β, and under Assumption 4.1 also independent of N and H.Source: §F.1 · p. 54

F.2 Comparison of the Empirical Criteria

• The empirical-criterion comparison separates reference sampling error Δ_n from plug-in error Π_n caused by replacing Q_β with bQ.The reference criterion keeps derivative weights at Q_β, whereas the feasible criterion evaluates them at bQ.Source: §F.2 · p. 55

F.2.1 Reference Empirical Criterion Deviation

• Localization restricts all inner suprema to a common deterministic ball, after which finite-dimensional covering and concentration control the reference empirical deviation.The ball is fixed and independent of n, N, H, and β.Source: §F.2.1 · pp. 55–57

F.2.2 Plug-in Criterion Perturbation

• The plug-in criterion perturbation satisfies Π_n = O_P(βr_Q) when ∥bQ − Q_β∥_{μ̄,2} = O_P(r_Q).The derivative-weight perturbation is order β∥bQ − Q_β∥_{μ̄,2}, while the normalization term is unchanged.Source: §F.2.2 · p. 57

Proof of Theorem 5.2

• The empirical criterion comparisons yield Gβ(bλβ) ≤ 2∆n + 2Πn, which implies ¯µ,2 ≤ c^-1(2∆n + 2Πn).The stochastic rate then follows by substituting the rates established in Lemmas F.4 and F.5.Source: §F.3 · p. 58