Online Inference in Distributional Temporal-Difference Learning

Online Inference in Distributional Temporal-Difference Learning Yang Peng∗

Liangyu Zhang†

Abstract We study online statistical inference for functionals of the return distribution under a fixed

arXiv:2608.14408v1 [stat.ML] 14 Aug 2026

policy. The return distribution is estimated by nonparametric distributional temporal-difference learning from a single Markov trajectory. For the Polyak–Ruppert averaged estimator, we prove that its root-T error converges weakly to a centered Gaussian random element in Cramér space. We also prove that, conditionally on the observed trajectory, the root-T difference between the bootstrap and original averages converges weakly to the same Gaussian limit. These results justify bootstrap inference for smooth statistical functionals, including variance, CVaR, expected shortfall, and expectiles. For nonsmooth statistical functionals, we develop a local asymptotic theory for the estimated return CDF over T −1/2 -neighborhoods of finitely many thresholds, together with its bootstrap analogue. This theory allows us to conduct inference for nonsmooth statistical functionals characterized by CDF equations, including return quantiles.

1

Introduction

Statistical inference for policy evaluation has focused on the value function, which is the conditional mean of the discounted return. An established literature develops inference for classical temporaldifference estimators of this mean [12, 20, 21, 22]. The mean, however, does not determine other features that can matter for policy evaluation. Policies with similar expected returns may have substantially different variability, downside risk, or probabilities of adverse outcomes. These features are described by statistical functionals of the return distribution beyond its mean. This paper studies online inference for such functionals from a single Markov trajectory. Distributional reinforcement learning provides the estimation tool by modeling the complete return distribution [8, 1, 2]. Under a fixed policy, distributional temporal-difference learning recursively ∗ †

Yau Mathematical Sciences Center, Tsinghua University. School of Statistics and Data Science, Shanghai University of Finance and Economics. Authors are listed in alphabetical order.

1

updates an estimate of this distribution at each step of the observed trajectory [18, 13]. We use nonparametric distributional TD, which does not restrict the return distribution to a finitedimensional parametric family. The inferential targets include variances, CVaR, expected shortfall, expectiles, quantiles, and parameters defined by CDF equations. Let η π = (η π (s))s∈S denote the return-distribution vector under policy π. Given a transition (St , At , Rt , St+1 ), nonparametric distributional TD updates the return-distribution estimate at the visited state according to ηt (St ) = (1 − αt )ηt−1 (St ) + αt (x 7→ Rt + γx)# ηt−1 (St+1 ), while leaving the other state components unchanged. Writing ηt = (ηt (s))s∈S , we estimate Φ(η π ) by P applying the statistical functional Φ to the Polyak–Ruppert average η̄T = T −1 Tt=1 ηt . The online multiplier bootstrap runs the same recursion with the step size αt multiplied by an independent P bootstrap weight Wt∗ , producing iterates ηt∗ and their average η̄T∗ = T −1 Tt=1 ηt∗ . The conditional √ √ law of T {Φ(η̄T∗ ) − Φ(η̄T )} then approximates the sampling law of T {Φ(η̄T ) − Φ(η π )}. √ The analysis has two parts. First, we prove that T (η̄T − η π ) converges weakly to a centered Gaussian random element in Cramér space and that, conditionally on the observed trajectory, √ T (η̄T∗ − η̄T ) converges weakly to the same limit. For a smooth functional Φ, these results give the √ √ weak limit of T {Φ(η̄T ) − Φ(η π )} and show that its bootstrap counterpart T {Φ(η̄T∗ ) − Φ(η̄T )} converges conditionally to the same limit. Second, for a nonsmooth functional Φ characterized by CDF equations, we establish sampling and bootstrap local CDF expansions over T −1/2 -neighborhoods of the relevant thresholds and use them to derive the corresponding sampling and bootstrap limits for Φ. Related work.

Existing work on statistical inference for TD learning focuses on the value function.

For Polyak–Ruppert averaged TD, Ramprasad et al. established the validity of an online bootstrap under Markovian sampling, and Wu et al. subsequently developed distributional approximations and confidence regions under independent and Markovian sampling [12, 20, 21]. More recently, Zeng et al. considered constant-stepsize TD and constructed self-normalized confidence regions from a single Markov trajectory [22]. Work on distributional policy evaluation initially focused on learning the return distribution itself. Early analyses established the asymptotic convergence of categorical and quantile TD [13, 14], while subsequent work derived statistical guarantees for offline, model-based, and model-free distributional 2

policy evaluation [19, 3, 15, 9, 10, 6, 7]. Inference for the return distribution has been studied using off-policy CDF estimators [4, 5] and a model-based estimator under a generative-model formulation [23]. The present paper instead develops online inference for statistical functionals of the return distribution estimated by distributional TD from a single Markov trajectory. Organization.

Section 2 presents online nonparametric distributional TD and the online multiplier

bootstrap. Section 3 develops inference for smooth functionals, and Section 4 develops inference for nonsmooth functionals characterized by CDF equations.

2

Preliminaries

2.1

Return distributions and the distributional Bellman equation

Consider a discounted tabular Markov decision process M = ⟨S, A, PR , P, γ⟩, where S and A are finite state and action spaces, P is the transition kernel, PR is the conditional reward distribution, and γ ∈ (0, 1). We use ∆(E) for the set of probability measures on a measurable space E. Throughout the main text, rewards are bounded and normalized so that 0 ≤ Rt ≤ 1 almost surely. Thus every discounted return lies in [0, (1 − γ)−1 ]. This is a bounded-reward assumption, not a finite-support assumption: the conditional reward distributions may be discrete, continuous, or mixed. Let π : S → ∆(A) be a fixed policy. We assume that the Markov chain induced by π is irreducible and aperiodic. Because S is finite, the chain is geometrically ergodic and has a unique stationary distribution µπ , with mins∈S µπ (s) > 0. The initial state may have an arbitrary distribution. Conditional on S0 = s, a trajectory is generated by sampling At ∼ π(· | St ), P t Rt ∼ PR (· | St , At ), and St+1 ∼ P (· | St , At ). The discounted return is Gπ (s) = ∞ t=0 γ Rt , with distribution η π (s) = L (Gπ (s) | S0 = s). We write η π = (η π (s))s∈S and use Fs for the CDF of R η π (s). The classical value function is the first moment V π (s) = x η π (s)(dx); distributional policy evaluation seeks the full vector η π . Let br,γ (x) = r + γx, and let (br,γ )# ν denote the pushforward of a probability measure ν through br,γ . The distributional Bellman operator T π is defined by [T π η] (s) = E [(bR0 ,γ )# η(S1 ) | S0 = s] ,

η = (η(s))s∈S .

The expectation on the right is an expectation of probability measures, or equivalently their mixture. The return-distribution vector is the unique fixed point η π = T π η π . The operator is a 3

√

γ-contraction in the supremum Cramér metric [2, Proposition 4.20].

2.2

Online distributional TD learning

If the transition kernel P and conditional reward distribution PR were known, one could evaluate η π by repeatedly applying the population Bellman operator T π . In practice, however, neither P nor PR is known, so the expectation defining T π cannot be computed directly. The learner therefore estimates η π from a single trajectory generated under π. At time t, the learner uses the transition (St , At , Rt , St+1 ) to form a sampled Bellman update for St . For a vector of distributions η, define this update by [Ttπ η] (St ) = (bRt ,γ )# η(St+1 ). Conditional on St = s, the sampled update is unbiased: E [[Ttπ η] (s) | St = s] = [T π η] (s). Starting from a deterministic η0 ∈ ∆([0, (1 − γ)−1 ])S , distributional TD uses the following stochastic-approximation recursion for the fixed point η π = T π η π : ηt = (I − αt Λt ) ηt−1 + αt Λt Ttπ ηt−1 ,

t ≥ 1.

(1)

The recursion is nonparametric because its return-distribution estimates are not restricted to a finite-dimensional parametric family. We use step sizes αt = a(t + t0 )−κ , where a > 0, t0 ≥ 0, and 1/2 < κ < 1, and assume 0 < αt ≤ 1 for every t. Here, Λt = diag (1{St = s} : s ∈ S) selects the St -coordinate. For s = ̸ St , set [Ttπ η] (s) = η(s); this convention does not affect the recursion because Λt removes the unvisited coordinates. The estimator used for inference is the Polyak–Ruppert P average η̄T = T −1 Tt=1 ηt [17, 11].

2.3

Online multiplier bootstrap

To conduct statistical inference without resampling the observed trajectory, we maintain a bootstrap iterate for each replicate. After observing the transition at time t, each bootstrap iterate uses the same transition as distributional TD, with the step size multiplied by an independent bootstrap weight. For each replicate, the bootstrap multipliers (Wt∗ )t≥1 are i.i.d., independent of the observed trajectory, and take the values 0 and 2 with probability 1/2 each. The corresponding randomly weighted recursion is ∗ ∗ ηt∗ = (I − αt Wt∗ Λt ) ηt−1 + αt Wt∗ Λt Ttπ ηt−1 ,

4

η0∗ = η0 .

(2)

Its Polyak–Ruppert average is η̄T∗ = T −1

PT

∗ t=1 ηt .

Throughout, P denotes probability under the data-generating law of the observed trajectory. Conditional probability, expectation, and distribution given the trajectory are denoted by P∗ , E∗ , and L∗ , respectively. Under this conditional law, the trajectory is fixed and only the bootstrap multipliers are random. The conditional law of η̄T∗ − η̄T will be used to approximate the sampling law of η̄T − η π . Conditional stochastic orders are denoted by Op∗ and op∗ ; convergence in probability of a conditional law is always with respect to the unstarred data-generating law P.

3

Inference for smooth functionals

This section first develops an asymptotic theory for the Polyak–Ruppert averaged distributional TD estimator in Cramér space and then uses that theory for inference on smooth functionals. We represent the distributional TD error as a zero-mass signed measure in Cramér space and derive the recursion underlying the Polyak–Ruppert analysis. From this recursion, we establish an asymptotic linear representation and Gaussian limit for the averaged estimator. We further show that the online multiplier bootstrap consistently reproduces this limit. Finally, the functional delta method transfers the Gaussian and bootstrap limits to smooth functionals, providing inference for means, variances, CVaR, expected shortfall, and expectiles.

3.1

Zero-mass signed measures and error recursion

We adopt the zero-mass signed-measure formulation. Let M0 be the space of finite signed measures µ supported on [0, (1 − γ)−1 ] with µ([0, (1 − γ)−1 ]) = 0. For µ ∈ M0 , define its cumulative function by R (1−γ)−1 Fµ (x) = µ([0, x]), and equip M0 with the Cramér inner product ⟨µ, ν⟩ℓ2 = 0 Fµ (x)Fν (x) dx 1/2

and the induced norm ∥µ∥ℓ2 = ⟨µ, µ⟩ℓ2 . Since M0 is not complete under this norm, let M be its Hilbert completion. For any probability measures µ1 , µ2 ∈ ∆([0, (1 − γ)−1 ]), their difference belongs to M and ∥µ1 − µ2 ∥ℓ2 equals their Cramér distance. We work in the separable product Hilbert P space H = MS , equipped with ⟨h, g⟩H = s∈S ⟨h(s), g(s)⟩ℓ2 . A proof of separability is given in Appendix A. We let T π and Ttπ act on signed-measure vectors by the same pushforward formulas as above. The Cramér contraction property implies that these operators are bounded on MS0 , so they extend uniquely to H [16]; we retain the same notation for the extensions. To study the evolution of the TD iterate around η π , let et = ηt − η π . Using the TD update and

5

the Bellman fixed-point identity gives et = et−1 − αt Λt (I − Ttπ ) et−1 + αt Λt (Ttπ η π − η π ) .

(3)

For simplicity of notation, set At := Λt (I − Ttπ ) ,

mt := Λt (Ttπ η π − η π ) .

(4)

The error recursion can then be written compactly as et = et−1 − αt At et−1 + αt mt .

(5)

Let Dµπ = diag(µπ (s) : s ∈ S). To separate the deterministic part of At from its random fluctuation, define its stationary average by A :=

X

µπ (s)E [At | St = s] = Dµπ (I − T π ) .

(6)

s∈S

The contraction property of T π , together with µπ (s) > 0 for every s ∈ S, implies that A is boundedly invertible; see Lemma A.1. Adding and subtracting Aet−1 in (5) gives Aet−1 = αt−1 (et−1 − et ) + mt + (A − At )et−1 . Below we show that, after summing (7) over t = 1, . . . , T and dividing by

(7) √

T , the first and third

terms on the right-hand side are negligible. The limiting distribution of the averaged error is P therefore determined by T −1/2 Tt=1 mt .

3.2

Asymptotic normality in Cramér space

The following theorem gives an asymptotic linear representation of the Polyak–Ruppert average. The Gaussian limit then follows by applying a Hilbert-space martingale CLT to the leading term. Throughout, ⇒ denotes weak convergence. Theorem 1 (Cramér-space central limit theorem). Let ZT :=

√

T (η̄T − η π ). Then

T

−1

ZT = A

1 X √ mt + op (1) T t=1 6

in H.

Consequently, ZT ⇒ G in H, where G is a centered Gaussian random element with covariance A−1 Σ(A−1 )∗ . The operator Σ appearing in the covariance is defined by Σ :=

X

µπ (s)E [mt ⊗ mt | St = s] .

(8)

s∈S

By the Bellman fixed-point identity, E[mt | St = s] = 0 for every s ∈ S, so Σ is the covariance operator of mt under the stationary distribution of St . Here u ⊗ v denotes the rank-one operator h 7→ ⟨v, h⟩H u. Proof sketch.

Summing (7) and dividing by

√

T gives

T T T T 1 X 1 X −1 1 X 1 X A√ et−1 = √ αt (et−1 − et ) + √ mt + √ (A − At )et−1 . T t=1 T t=1 T t=1 T t=1

It remains to show that the first and third terms are op (1) and apply a martingale central limit theorem to the middle term. Step 1: establish a bound for et . Both terms contain et , so we first prove E ∥et ∥2H ≤ Cαt . This rate ultimately follows from contraction of the distributional Bellman operator. Indeed, defining the P stationary-distribution-weighted norm by ∥h∥2µπ := s∈S µπ (s) ∥h(s)∥2ℓ2 , we have ∥T π h∥µπ ≤ where c0 = (1 −

√

√

γ ∥h∥µπ ,

⟨h, Ah⟩H ≥ (1 −

√

γ) ∥h∥2µπ ≥ c0 ∥h∥2H

γ) mins∈S µπ (s) > 0.

Let A(s) := E[At | St = s], so that A = ES∼µπ [A(S)]. Expanding ∥et ∥2H in (5) and taking expectations gives E ∥et ∥2H ≤ E ∥et−1 ∥2H − 2αt E ⟨et−1 , A(St )et−1 ⟩H + Cαt2 . For any bounded operator B, ⟨h, Bh⟩H = ⟨h, (B + B ∗ )h/2⟩H , so only the self-adjoint part of A(St ) affects the inner product in the preceding display. Consider the operator Poisson equation Q(s) − (P π Q)(s) =

A(s) + A(s)∗ A + A∗ − , 2 2

s ∈ S.

Its right-hand side has expectation zero under S ∼ µπ , and geometric ergodicity gives a bounded

7

solution Q. Define the Lyapunov function Vt := ∥et ∥2H − 2αt+1 ⟨et , Q(St+1 )et ⟩H . Because E[Q(St+1 ) | St ] = (P π Q)(St ), the Poisson equation implies, for every h ∈ H and s ∈ S, ⟨h, [A(s) + (P π Q)(s) − Q(s)] h⟩H = ⟨h, Ah⟩H . Substituting (5) into the definition of Vt , taking expectations, and using this identity gives EVt ≤ EVt−1 − 2αt E ⟨et−1 , Aet−1 ⟩H + Cαt2 . Since Q is bounded and αt → 0, Vt is equivalent to ∥et ∥2H for large t. The lower bound for ⟨h, Ah⟩H above therefore yields EVt ≤ (1 − cαt )EVt−1 + Cαt2 , and hence E ∥et ∥2H ≤ Cαt . Step 2: control the first and third terms. For the first term, Abel summation gives T X

αt−1 (et−1 − et ) = α1−1 e0 +

T −1 X

t=1

−1 αt+1 − αt−1 et − αT−1 eT .

t=1

The estimate E ∥et ∥2H ≤ Cαt , together with αt ≍ t−κ and κ < 1, shows that the right-hand side is √ op ( T ). For the third term, write (A − At )et−1 = [A − A(St )] et−1 + [A(St ) − At ] et−1 . Since the second term has conditional mean zero given the history through St ,

E

T X t=1

2

[A(St ) − At ] et−1

=

T X

E ∥[A(St ) − At ] et−1 ∥2H .

t=1

H

Uniform boundedness of At and the estimate E ∥et ∥2H ≤ Cαt from Step 1 then imply √ op ( T ). For [A − A(St )] et−1 , consider the operator Poisson equation R(s) − (P π R)(s) = A − A(s),

8

s ∈ S.

PT

t=1 [A(St ) − At ] et−1 =

Its right-hand side has expectation zero under S ∼ µπ , so it admits a bounded solution R. Along the trajectory, [A − A(St )] et−1 = [R(St ) − R(St+1 )] et−1 + [R(St+1 ) − (P π R)(St )] et−1 . Given the history through St , the second term on the right has mean zero. Boundedness of R and √ E ∥et ∥2H ≤ Cαt imply that its sum is op ( T ). For the first term, summation by parts gives T X

[R(St ) − R(St+1 )] et−1 = R(S1 )e0 − R(ST +1 )eT −1 +

t=1

T −1 X

R(St+1 )(et − et−1 ).

t=1

√ Boundedness of R, E ∥et ∥2H ≤ Cαt , and the recursion (5) make the right-hand side op ( T ). Thus the third term also vanishes. We obtain T T 1 X 1 X A√ et−1 = √ mt + op (1). T t=1 T t=1

Replacing the average of et−1 by the average of et changes only the two endpoints. These are negligible by the same bound. Applying A−1 to both sides gives the asserted linear representation. Step 3: identify the limit of the leading term. The Bellman fixed-point identity implies that (mt ) is a bounded H-valued martingale difference sequence. Ergodicity of (St ) makes the average conditional covariance converge to Σ. For each finite-rank orthogonal projection Pq , the multivariate martingale CLT gives T

1 X Pq √ mt ⇒ NPq H (0, Pq ΣPq ). T t=1 Moreover, T

1 X E (I − Pq ) √ mt T t=1

2

T

=

1X E ∥(I − Pq )mt ∥2H . T t=1

H

Ergodicity then yields T

1X E ∥(I − Pq )mt ∥2H = tr{(I − Pq )Σ} −→ 0 T →∞ T lim

(q → ∞).

t=1

Hence T −1/2

PT

−1 −1 ∗ t=1 mt ⇒ NH (0, Σ) in H. The resulting Gaussian limit has covariance A Σ(A ) ,

which completes the proof. The technical lemmas and complete proof are given in Appendix A.

9

3.3

Bootstrap validity

The preceding central limit theorem characterizes the sampling distribution of the Polyak–Ruppert averaged estimator. We now show that the online multiplier bootstrap introduced in the preceding section reproduces the same Gaussian limit conditionally on the observed trajectory. Define the normalized bootstrap error by Z∗T =

√

T (η̄T∗ − η̄T ) .

Given the trajectory, its conditional law L∗ (Z∗T ) is generated solely by the bootstrap multipliers. We use ⇒∗ to denote conditional weak convergence given the observed trajectory, in P-probability. Theorem 2 (Bootstrap validity in Cramér space). Assume α1 ≤ 1/2. Then Z∗T ⇒∗ G

in H, in P-probability,

where G is the centered Gaussian random element identified in Theorem 1. Theorem 1 identifies G as the weak limit of the normalized estimation error ZT , while Theorem 2 shows that the conditional law of Z∗T converges to the same Gaussian law. Thus, the online multiplier bootstrap consistently reproduces the asymptotic sampling distribution of ZT . Each bootstrap replicate reuses the observed transitions through recursion (2), so the procedure neither resamples the trajectory nor explicitly estimates A−1 or the covariance operator A−1 Σ(A−1 )∗ . Proof sketch.

The bootstrap Polyak–Ruppert expansion proved in Appendix A gives T

1 X ∗ Z∗T = A−1 √ (Wt − 1)mt + op∗ (1) T t=1

in H,

in P-probability. It therefore remains to establish the conditional Gaussian limit of the leading multiplier sum and then show that the conditionally negligible remainder does not alter this limit. Conditional limit of the leading term. Let Pq be the finite-rank projections used in the proof of Theorem 1. For each fixed q, the martingale law of large numbers and the Markov ergodic theorem give T

1X Pq mt ⊗ Pq mt −→ Pq ΣPq T t=1

10

P-almost surely.

Since E∗ [(Wt∗ − 1)2 ] = 1, this is the conditional covariance of the projected multiplier sum. Boundedness of mt and Wt∗ − 1 makes the conditional Lindeberg condition immediate. Hence, for P-almost every observed trajectory, every fixed finite-dimensional projection has the required conditional Gaussian limit. For the same projections, conditional independence and centering give 2

T

∗

E

1 X ∗ (I − Pq ) √ (Wt − 1)mt T t=1

T

= H

1X ∥(I − Pq )mt ∥2H . T t=1

For every fixed q, the right-hand side converges P-almost surely to tr{(I − Pq )Σ}, and these convergences hold simultaneously for all q on a single event of P-probability one. Boundedness of mt gives tr(Σ) =

X

h i µπ (s)E ∥mt ∥2H | St = s < ∞,

s∈S

so tr{(I − Pq )Σ} → 0 as q → ∞. Conditional Markov’s inequality therefore gives, on that event, ( lim lim sup P∗

q→∞ T →∞

T

1 X ∗ (I − Pq ) √ (Wt − 1)mt T t=1

) >ε

=0

H

for every ε > 0. Together with the finite-dimensional conditional convergence, this establishes T

1 X ∗ √ (Wt − 1)mt ⇒∗ NH (0, Σ) T t=1

for P-almost every observed trajectory.

Applying the bounded operator A−1 gives the corresponding conditional limit G for the leading term in the first display. Effect of the remainder. The conditional order in the first display means that, for every ε, η > 0, " P P∗

(

T

1 X ∗ Z∗T − A−1 √ (Wt − 1)mt T t=1

) >ε

# > η −→ 0.

H

Together with the almost-sure conditional limit of the leading term, this conditional negligibility gives Z∗T ⇒∗ G

in H, in P-probability.

The full proof is given in Appendix A.

11

3.4

Inferential consequences and examples

Theorem 3 (Inference for smooth functionals). Let Φ be an Rd -valued functional of the returndistribution vector, and suppose that it is Hadamard differentiable at η π in the Cramér geometry tangentially to the full space H, with continuous linear derivative Φ̇ηπ : H → Rd . Then √  T Φ(η̄T ) − Φ(η π ) √  T Φ(η̄T∗ ) − Φ(η̄T )

⇒ Φ̇ηπ (G), ⇒∗ Φ̇ηπ (G).

The second convergence holds in P-probability. Suppose now that d = 1 and that Φ̇ηπ (G) is √ ∗ nondegenerate. For p ∈ (0, 1), let qT,p be the conditional p-quantile of T {Φ(η̄T∗ ) − Φ(η̄T )}. Then, for every α ∈ (0, 1), define the basic bootstrap confidence interval ∗ qT,1−α/2 ∗ IT,1−α := Φ(η̄T ) − √ , T

"

# ∗ qT,α/2 Φ(η̄T ) − √ . T

∗ It satisfies P{Φ(η π ) ∈ IT,1−α } → 1 − α.

The following examples illustrate common smooth functionals of the discounted-return distribution. Fix a state s and a direction h ∈ H. To keep derivative subscripts short, we use s to indicate evaluation at the return distribution η π (s). Example 1 (Mean and variance). The mean of the discounted return is π

π

Z (1−γ)−1

ϕmean (η (s)) := V (s) =

x η π (s)(dx) = E[Gπ (s) | S0 = s] .

0

Its derivative in the direction h(s) is Z (1−γ)−1 ϕ̇mean,s (h(s)) = −

Fh(s) (x) dx. 0

The variance is treated separately as

ϕvar (η

π

(s)) := σπ2 (s) =

Z (1−γ)−1

{x − V π (s)}2 η π (s)(dx) = Var(Gπ (s) | S0 = s) ,

0

and its derivative is Z (1−γ)−1 ϕ̇var,s (h(s)) = −2 0

12

{x − V π (s)}Fh(s) (x) dx.

Both derivatives are continuous because their integral weights are square-integrable on [0, (1 − γ)−1 ]. Example 2 (CVaR). For u ∈ (0, 1), let quπ (s) = inf{x : Fηπ (s) (x) ≥ u}. The lower-tail CVaR of the discounted return is 1 π ϕCVaR (η π (s)) := CVaR− τ τ (G (s) | S0 = s) =

Z τ

τ

quπ (s) du,

τ ∈ (0, 1).

0

Suppose that {q : Fηπ (s) (q−) ≤ τ ≤ Fηπ (s) (q)} = {qτπ (s)}. Under this uniqueness condition, the functional is smooth in the Cramér geometry, with derivative ϕ̇CVaR (h(s)) = − τ,s

1 τ

Z qτπ (s) Fh(s) (x) dx. 0

The derivative is continuous because it integrates Fh(s) over a bounded interval. Example 3 (Expected shortfall). For u ∈ (0, 1), let quπ (s) = inf{x : Fηπ (s) (x) ≥ u}. The upper-tail expected shortfall of the discounted return is π + π ϕES τ (η (s)) := ESτ (G (s) | S0 = s) =

1 1−τ

Z 1

quπ (s) du,

τ ∈ (0, 1).

τ

Suppose that {q : Fηπ (s) (q−) ≤ τ ≤ Fηπ (s) (q)} = {qτπ (s)}. Under this uniqueness condition, the functional is smooth in the Cramér geometry, with derivative ϕ̇ES τ,s (h(s)) = −

1 1−τ

Z (1−γ)−1 qτπ (s)

Fh(s) (x) dx.

The derivative is continuous because it integrates Fh(s) over a bounded interval. Example 4 (Expectiles). For τ ∈ (0, 1), the expectile functional evaluated at the return distribution is π π ϕexp τ (η (s)) := eτ (s),

where eπτ (s) is the unique solution of τ E[{Gπ (s) − eπτ (s)}+ | S0 = s] = (1 − τ )E[{eπτ (s) − Gπ (s)}+ | S0 = s] . If Fηπ (s) is continuous at eπτ (s), the expectile functional is smooth in the Cramér geometry, with

13

derivative

Z (1−γ)−1 τ ϕ̇exp τ,s (h(s)) = −

eπ τ (s)

Z eπτ (s) Fh(s) (x) dx + (1 − τ )

Fh(s) (x) dx 0

τ {1 − Fηπ (s) (eπτ (s))} + (1 − τ )Fηπ (s) (eπτ (s))

.

The denominator is strictly positive, while the numerator is a continuous linear functional of Fh(s) .

4

Inference for nonsmooth functionals

This section studies online inference for nonsmooth functionals of the return distribution. To this end, we develop a local asymptotic theory for the estimated return CDF over T −1/2 -neighborhoods of finitely many thresholds, together with its bootstrap analogue. These results yield inference for nonsmooth statistical functionals characterized by CDF equations, including return quantiles.

4.1

Local asymptotics of the return CDF

Many common functionals of the return distribution are nonsmooth in the Cramér topology. A basic example is a return quantile: its first-order expansion depends on the CDF error evaluated at the unknown quantile, whereas point evaluation is not continuous under the Cramér norm. Such nonsmooth functionals are not covered by the theory in Section 3. We address this difficulty by establishing local asymptotic control of the estimated return CDF over T −1/2 -neighborhoods of finitely many thresholds. Fix thresholds x = (x1 , . . . , xk )T ∈ (0, (1 − γ)−1 )k . For s ∈ S, write Fs = Fηπ (s) ,

F̄T,s = Fη̄T (s) .

For h = (hs,j )s∈S, 1≤j≤k ∈ R|S|k , define the stacked local CDF process by      √ hs,j FT,x (h) := T F̄T,s xj + √ − Fs (xj ) T s∈S, 1≤j≤k We next show that FT,x converges weakly to a Gaussian process with a deterministic linear drift. The local CDF analysis requires the following mild regularity conditions. Assumption 1 (Local regularity conditions). Every return distribution η π (s) is absolutely continuous on [0, (1 − γ)−1 ], with a continuous density fs , and KF := max ∥fs ∥∞ < ∞. s∈S

14

Also, the distributional TD initialization η0 has absolutely continuous components on [0, (1 − γ)−1 ], with densities bounded uniformly over s ∈ S. Under Assumption 1, write
fxS := fs (xj ) s∈S, 1≤j≤k . Theorem 4 (Local asymptotics of the return CDF). Suppose that 3/5 < κ < 3/4. For every s ∈ S and j = 1, . . . , k, define ψs,xj ,t := F(A−1 mt )(s) (xj ),
and write ψtS (x) = ψs,xj ,t s∈S, 1≤j≤k . Let ΩSx =

X

h i µπ (r)E ψtS (x)ψtS (x)T | St = r .

(9)

r∈S

Let GSx = Gs,xj s∈S, 1≤j≤k ∼ N|S|k (0, ΩSx ). Then, for every fixed M < ∞, the local process converges weakly as   FT,x ⇒ h 7→ GSx + fxS ⊙ h in ℓ∞ ([−M, M ]|S|k ; R|S|k ), where ⊙ denotes componentwise multiplication. Proof sketch.

Step 1: obtain a local influence representation. For z in a neighborhood of xj ,

define the pointwise influence variable ψs,z,t := F(A−1 mt )(s) (z). √ Repeating the argument for Theorem 1, now uniformly over |z − xj | ≤ M/ T , gives, for every fixed M < ∞, every s ∈ S, and every j = 1, . . . , k, √ sup

√ |z−xj |≤M/ T

T

1 X T {F̄T,s (z) − Fs (z)} − √ ψs,z,t = op (1). T t=1

The required uniform local bounds are established in Appendix B, and their remainder rates vanish when 3/5 < κ < 3/4. Step 2: identify the limit at the fixed thresholds. The Bellman fixed-point identity implies that
ψtS (x) is a bounded R|S|k -valued martingale-difference sequence. Ergodicity of (St ) makes its average conditional covariance converge to ΩSx . The multivariate martingale central limit theorem 15

therefore gives T

1 X S √ ψt (x) ⇒ GSx . T t=1 Evaluating the representation from Step 1 at z = xj and stacking the coordinates gives T

1 X S ψt (x) + op (1), FT,x (0) = √ T t=1 and hence FT,x (0) ⇒ GSx . Step 3: pass from the fixed thresholds to the local processes. By definition, for every h, √ T

    hs,j hs,j − F s xj + √ FT,x (h) − FT,x (0) = F̄T,s xj + √ T T s∈S, 1≤j≤k √  − T {F̄T,s (xj ) − Fs (xj )} s∈S, 1≤j≤k      √ hs,j . T Fs xj + √ − Fs (xj ) + T s∈S, 1≤j≤k 



We control the centered CDF increment in the first two lines and the population CDF increment in the last line separately. For the centered CDF increment, the main point is to control how the influence variable changes with its threshold. Expand A−1 = (I − T π )−1 Dµ−1 as its Neumann series. Affine rescaling inside π the q-th Bellman iterate bounds the difference between the corresponding terms by C |z − z ′ | γ −q , while the local small-ball bound gives the complementary estimate Cγ q . Hence ψs,z,t − ψs,z ′ ,t ≤ C

∞ X

min{ z − z ′ γ −q , γ q } ≤ C

p

|z − z ′ |,

q=0

uniformly in s, t, z, z ′ in the chosen neighborhoods. To transfer this pathwise modulus to the normalized martingale sums, cover {z : |z − xj | ≤ δ} by nested dyadic grids. On a grid with mesh of order δ2−ℓ , each adjacent increment is a martingale √ difference with predictable variance of order δ2−ℓ and absolute size of order δ2−ℓ . A martingale Bernstein inequality, followed by a union bound over the grid edges and summation over ℓ, gives

sup h∈[−M,M ]|S|k

T  1 X √ ψs,xj +hs,j /√T ,t − ψs,xj ,t s∈S, 1≤j≤k T t=1

= op (1). ∞

By the uniform representation in Step 1, the centered CDF increment differs uniformly from the 16

influence-sum increment in the preceding display by op (1). Therefore,

sup h∈[−M,M ]|S|k

      √ hs,j hs,j − F s xj + √ T F̄T,s xj + √ T T s∈S, 1≤j≤k √  − T {F̄T,s (xj ) − Fs (xj )} s∈S, 1≤j≤k

= op (1). ∞

For the population CDF increment, continuity of the densities gives, uniformly over the same neighborhoods,  sup

√

 T

h∈[−M,M ]|S|k

   hs,j − Fs (xj ) Fs xj + √ − fxS ⊙ h −→ 0. T s∈S, 1≤j≤k ∞

Applying these two bounds to the preceding decomposition yields sup h∈[−M,M ]|S|k

FT,x (h) − FT,x (0) − fxS ⊙ h ∞ = op (1).

The Gaussian limit from Step 2 now gives the stated weak convergence in the product supremum norm. The complete argument is given in Appendix B. Remark 1. One might ask whether the centered CDF process converges weakly under the Kolmogorov– Smirnov norm. Under the present assumptions, such a global process limit need not hold, because uniform tightness of the CDF fluctuations over the full threshold range is not guaranteed. We therefore formulate the result locally around finitely many thresholds, which is sufficient for the nonsmooth functionals considered below.

4.2

Bootstrap validity

∗ := F ∗ |S|k , define the stacked bootstrap local For s ∈ S, write F̄T,s η̄T (s) . For h = (hs,j )s∈S, 1≤j≤k ∈ R

CDF process by F∗T,x (h) :=



√

 T

∗ F̄T,s



hs,j xj + √ T



 − F̄T,s (xj )

. s∈S, 1≤j≤k

Given the trajectory, the conditional law of F∗T,x is generated solely by the bootstrap multipliers. Theorem 5 (Bootstrap validity for the local CDF process). Assume the conditions of Theorem 4

17

and α1 ≤ 1/2. Then, for every fixed M < ∞,   F∗T,x ⇒∗ h 7→ GSx + fxS ⊙ h

in ℓ∞ ([−M, M ]|S|k ; R|S|k ), in P-probability,

where GSx is the centered Gaussian vector identified in Theorem 4. Proof sketch. Step 1: obtain a local bootstrap influence representation. The bootstrap counterpart of Step 1 in the proof of Theorem 4 gives, for every fixed M < ∞, every s ∈ S, and every j = 1, . . . , k, √ sup

√ |z−xj |≤M/ T

1 ∗ T {F̄T,s (z) − F̄T,s (z)} − √

T X (Wt∗ − 1)ψs,z,t = op∗ (1)

T t=1

in P-probability. The local remainder bounds are the same as in the sampling representation, while the additional multiplier remainders are controlled in Appendix B. Step 2: identify the conditional limit at the fixed thresholds. Conditional on the observed trajectory, the summands are independent and centered. The martingale law of large numbers and the Markov P p ergodic theorem give T −1 Tt=1 ψtS (x)ψtS (x)T → − ΩSx . Since E∗ [(Wt∗ − 1)2 ] = 1, the left-hand side is the conditional covariance matrix of the leading multiplier sum. Boundedness of ψtS (x) and the multiplier moment condition imply the conditional Lindeberg condition. The conditional multivariate Lindeberg–Feller theorem therefore yields T

1 X ∗ √ (Wt − 1)ψtS (x) ⇒∗ GSx T t=1

in P-probability.

Evaluating the representation from Step 1 at z = xj and stacking the coordinates gives 1 F∗T,x (0) = √

T X (Wt∗ − 1)ψtS (x) + op∗ (1)

T t=1

in R|S|k ,

in P-probability, and hence F∗T,x (0) ⇒∗ GSx in R|S|k , in P-probability. Step 3: pass from the fixed thresholds to the local processes. By definition, for every h, the (s, j)-coordinate of F∗T,x (h) − F∗T,x (0) is √

       ∗ hs,j hs,j ∗ F̄T,s xj + √ − F̄T,s xj + √ − F̄T,s (xj ) − F̄T,s (xj ) T T     √ hs,j + T F̄T,s xj + √ − F̄T,s (xj ) . T

T

18

We control the centered bootstrap CDF increment in the first line and the sampling CDF increment in the second line separately. For the centered bootstrap CDF increment, Step 3 in the proof of Theorem 4 already established p ψs,z,t − ψs,z ′ ,t ≤ C |z − z ′ |, uniformly over the relevant neighborhoods. Conditional on the observed trajectory, the multipliers are independent and centered. The same dyadic-grid argument, now using the conditional Bernstein inequality, therefore gives

sup h∈[−M,M ]|S|k

T   1 X ∗ √ (Wt − 1) ψs,xj +hs,j /√T ,t − ψs,xj ,t s∈S, 1≤j≤k T t=1

= op∗ (1) ∞

in probability. By the uniform representation in Step 1, it follows that the centered bootstrap CDF increment in the first line of the decomposition is uniformly op∗ (1) in probability. For the sampling CDF increment in the second line, the uniform local expansion already established in Step 3 of Theorem 4 gives, uniformly over h ∈ [−M, M ]|S|k ,      √ hs,j T F̄T,s xj + √ − F̄T,s (xj ) = fxS ⊙ h + op (1). T s∈S, 1≤j≤k Consequently, sup h∈[−M,M ]|S|k

F∗T,x (h) − F∗T,x (0) − fxS ⊙ h ∞ = op∗ (1)

in probability. The conditional limit from Step 2 now gives the stated process convergence. The complete argument is given in Appendix B.

19

The inferential applications below require the local CDF expansion to remain valid when the local perturbation is random. The following corollary provides this random-index version of Theorem 5. Indeed, for each fixed M , the uniform expansion in that theorem may be evaluated at h = ∆∗T on the event ∥∆∗T ∥∞ ≤ M ; conditional tightness then allows M → ∞. Corollary 1 (Bootstrap expansion at random local thresholds). Under the conditions of Theorem 5, let ∆∗s,j,T = Op∗ (1) in probability for every s ∈ S and j = 1, . . . , k. Then, jointly over these states and thresholds, F∗T,x (∆∗T ) = F∗T,x (0) + fxS ⊙ ∆∗T + op∗ (1), in probability, where ∆∗T := (∆∗s,j,T )s∈S, 1≤j≤k .

4.3

Functionals characterized by CDF equations

We next consider a finite-dimensional functional whose value is characterized by CDF evaluations at parameter-dependent thresholds. Choose states s1 , . . . , sJ ∈ S. Let M : Rp × RJ → Rp and gj : Rp → R, and define H(θ) = M (θ, Fs1 (g1 (θ)), . . . , FsJ (gJ (θ))) ,
HT (θ) = M θ, F̄T,s1 (g1 (θ)), . . . , F̄T,sJ (gJ (θ)) . ∗ . Let θ be a locally identified solution of H(θ) = 0, and Define HT∗ by replacing F̄T,sj with F̄T,s 0 j

set xj = gj (θ0 ). Write Gx for the subvector of GSx corresponding to (sj , xj )Jj=1 , and Ωx for its covariance matrix. Assume that M and g1 , . . . , gJ are continuously differentiable. With the derivatives of M evaluated at (θ0 , Fs1 (x1 ), . . . , FsJ (xJ )), define  Mu = Mu1

···

MuJ



,

B = Mθ +

J X

Muj fsj (xj )∇gj (θ0 )T .

j=1

Suppose that B is nonsingular. Theorem 6 (Inference for CDF-defined functionals). Suppose that the conditions of Theorem 5 hold for the thresholds x1 , . . . , xJ . Let θ̂T be a measurable, locally consistent solution of HT (θ) = 0,

20

and let θ̂T∗ be a measurable solution of HT∗ (θ) = 0 such that θ̂T∗ − θ0 = op∗ (1) in probability. Then √ √

T (θ̂T − θ0 ) = −B −1 Mu

T (θ̂T∗ − θ̂T ) = −B −1 Mu

√

√

 T {F̄T,sj (xj ) − Fsj (xj )}

1≤j≤J

 ∗ T {F̄T,s (x ) − F̄ (x )} j T,sj j j

1≤j≤J

+ op (1) ⇒ −B −1 Mu Gx , + op∗ (1) ⇒∗ −B −1 Mu Gx .

The second convergence holds in P-probability. Proof sketch.

The chain rule gives DH(θ0 ) = B. Since B is nonsingular, there are a neighborhood

of θ0 and a constant c > 0 on which ∥H(θ)∥ ≥ c∥θ − θ0 ∥. Choose shrinking neighborhoods that contain θ̂T and θ̂T∗ with probability tending to one, as permitted by their local consistency. The fixed-threshold tightness and local stochastic equicontinuity in Theorems 4 and 5 make the sampling and bootstrap CDF errors uniformly of order T −1/2 on these neighborhoods. Because HT (θ̂T ) = 0, HT∗ (θ̂T∗ ) = 0, and M is locally Lipschitz in its CDF arguments, the local identification bound then gives θ̂T − θ0 = Op (T −1/2 ) and θ̂T∗ − θ0 = Op∗ (T −1/2 ) in probability. These rates place every gj (θ̂T ) and gj (θ̂T∗ ) in a root-T neighborhood of xj . Applying Theorem 4 to the sampling CDF evaluations, Corollary 1 to their bootstrap counterparts, and then expanding M to first order gives the two estimating equations √  √ 0 = B T (θ̂T − θ0 ) + Mu T {F̄T,sj (xj ) − Fsj (xj )} + op (1), 1≤j≤J   √ √ 0 = B T (θ̂T∗ − θ0 ) + Mu T {F̄T,sj (xj ) − Fsj (xj )} 1≤j≤J  √  ∗ + T {F̄T,sj (xj ) − F̄T,sj (xj )} + op∗ (1). 1≤j≤J

Subtracting the first equation from the second and applying B −1 gives the centered bootstrap representation in the theorem. At the fixed thresholds, Theorem 4 sends the sampling CDF-error vector to Gx , while Theorem 5 sends the bootstrap CDF-error vector conditionally to the same Gx . Applying the linear map −B −1 Mu gives the two stated limits. The sampling covariance is B −1 Mu Ωx MuT B −T , while bootstrap critical values can be computed without estimating this covariance matrix. The complete proof is given in Appendix B. Example 5 (Median absolute deviation). Fix a state s, and write Fs = Fηπ (s) . The median ms and median absolute deviation ds of the discounted return are characterized jointly by 1 Fs (ms ) = , 2

1 Fs (ms + ds ) − Fs (ms − ds ) = . 2 21

Let (m̂T,s , dˆT,s ) and (m̂∗T,s , dˆ∗T,s ) be the corresponding locally consistent solutions obtained from ∗ , respectively. To apply Theorem 6, take θ = (m, d)T , s = s = s = s, g (θ) = m, F̄T,s and F̄T,s 1 2 3 1

g2 (θ) = m + d, g3 (θ) = m − d, and M (θ, u1 , u2 , u3 ) = (u1 − 1/2, u2 − u3 − 1/2)T . The derivative matrix in that theorem becomes 

fs (ms )

0



. BMAD,s =  fs (ms + ds ) − fs (ms − ds ) fs (ms + ds ) + fs (ms − ds ) Suppose that ms − ds , ms , and ms + ds lie in (0, (1 − γ)−1 ), and that fs is continuous near these points. If fs (ms ) > 0 and fs (ms + ds ) + fs (ms − ds ) > 0, then BMAD,s is nonsingular, so Theorem 6 applies directly. It yields the following limits, where GMAD,s is obtained by applying the linear map −1 −BMAD,s Mu to the Gaussian CDF coordinates at ms , ms + ds , and ms − ds :

√

 T

m̂T,s − ms dˆT,s − ds



√

 ⇒ GMAD,s ,

 T

m̂∗T,s − m̂T,s dˆ∗T,s − dˆT,s

  ⇒∗ GMAD,s

where the second convergence holds in probability. Example 6 (Return quantiles). Fix a state s and τ ∈ (0, 1), and let qτ,s = inf{x : Fs (x) ≥ τ }. Suppose that qτ,s ∈ (0, (1 − γ)−1 ) and that fs is continuous near qτ,s , with fs (qτ,s ) > 0. Include qτ,s among the selected thresholds. ∗ (θ) = τ admit roots First consider the simple case in which the equations F̄T,s (θ) = τ and F̄T,s

near qτ,s that satisfy the local consistency conditions of Theorem 6. In that theorem, take p = J = 1, s1 = s, θ0 = qτ,s , g1 (θ) = θ, and M (θ, u) = u − τ . Then x1 = qτ,s , Mθ = 0, Mu = 1, and g1′ (θ0 ) = 1, so B = fs (qτ,s ). Thus the linear map −B −1 Mu in Theorem 6 is multiplication by −1/fs (qτ,s ), which gives the linear representations and Gaussian limits displayed below whenever exact roots are used. In general, the estimated CDFs need not attain τ exactly. Define instead the generalized-inverse estimators ∗ ∗ q̂T,τ,s = inf{x : F̄T,s (x) ≥ τ }.

q̂T,τ,s = inf{x : F̄T,s (x) ≥ τ }, Set ∆T,s =

√

T (q̂T,τ,s − qτ,s ) and ∆∗T,s =

√

∗ T (q̂T,τ,s − qτ,s ). Lemma B.18 shows that both local shifts

are tight, in the sampling and conditional senses, respectively. The uniform local-process expansion

22

in Theorem 4 and its random-index bootstrap counterpart in Corollary 1 therefore give √ √

T {F̄T,s (q̂T,τ,s ) − τ } = ∗ ∗ T {F̄T,s (q̂T,τ,s ) − τ} =

√ √

T {F̄T,s (qτ,s ) − Fs (qτ,s )} + fs (qτ,s )∆T,s + op (1), √ ∗ T {F̄T,s (qτ,s ) − Fs (qτ,s )} + T {F̄T,s (qτ,s ) − F̄T,s (qτ,s )} + fs (qτ,s )∆∗T,s + op∗ (1).

For exact roots, the left-hand sides are zero. For the generalized-inverse estimators, Lemma B.19 shows that they are op (1) and op∗ (1), respectively, in probability. Solving the first equation and subtracting it from the second gives √

T (q̂T,τ,s − qτ,s ) ⇒ −

√

Gs,qτ,s , fs (qτ,s )

The second convergence holds in P-probability.

23

∗ T (q̂T,τ,s − q̂T,τ,s ) ⇒∗ −

Gs,qτ,s . fs (qτ,s )

A

Proofs for Section 3

A.1

Proofs for Section 3.1

Separability of the Cramér space. Define J : M0 → L2 ([0, (1 − γ)−1 ]) by Jµ = Fµ . By the definition of the Cramér norm, J is a linear isometry. The Hilbert completion M is therefore isometrically isomorphic to the closure of J(M0 ) in L2 ([0, (1 − γ)−1 ]). Since L2 ([0, (1 − γ)−1 ]) is separable, this closed subspace is separable. Finally, S is finite, so the product Hilbert space H = MS is separable. For the martingale arguments below, let Ft−1 = σ(S0 , (Au , Ru , Su+1 )0≤u<t ) and Ft = Ft−1 ∨ σ(At , Rt , St+1 ). Thus Ft−1 contains the observed trajectory through St , and conditional on Ft−1 the current transition is generated from the fixed policy and MDP kernel given St . Lemma A.1 (Bellman residual and coercivity). The sequence (mt , Ft ) is a bounded H-valued martingale difference, and et and At are uniformly bounded. Moreover, A is boundedly invertible and, for some c0 > 0, ⟨h, Ah⟩H ≥ c0 ∥h∥2H ,

h ∈ H.

(10)

Proof. The Bellman fixed-point equation, conditioned on Ft−1 , gives E[mt | Ft−1 ] = 0. Since returns lie in [0, (1 − γ)−1 ] and 0 < αt ≤ 1, we have s ∥mt ∥H ≤ (1 − γ)−1/2 , For ∥h∥2µπ =

sup ∥et ∥H ≤ t

|S| , 1−γ

sup ∥At ∥ < ∞. t

2 s µπ (s) ∥h(s)∥ℓ2 , Jensen’s inequality, the affine pushforward change of variables, and

P

stationarity give ∥T π h∥2µπ ≤ γ ∥h∥2µπ .

(11)

Thus I − T π is invertible by its Neumann series, and so is A = Dµπ (I − T π ). Finally, ⟨h, Ah⟩H = ∥h∥2µπ − ⟨h, T π h⟩µπ ≥ (1 − with c0 = (1 −

√

√

γ) ∥h∥2µπ ≥ c0 ∥h∥2H ,

γ) mins µπ (s) > 0.

Lemma A.2 (Finite-state operator Poisson equation). Let B : S → L(H) be bounded and satisfy P P∞ π k s µπ (s)B(s) = 0. Then Q(s) = k=0 (P ) B(s) converges uniformly in operator norm and is the bounded solution, normalized to have stationary mean zero, of Q(s) − (P π Q)(s) = B(s). 24

Proof. Because S is finite and the chain is geometrically ergodic, (P π )k B(s) ≤ ∥B∥∞

X

(P π )k (s, u) − µπ (u) ≤ Cρk

u∈S

for some ρ < 1, uniformly in s. Thus the series converges uniformly; telescoping proves the Poisson equation. The normalization and uniqueness follow by averaging and geometric ergodicity.

A.2

Proofs for Section 3.2

For s ∈ S, define the statewise mean drift by A(s)h := E[At h | St = s],

h ∈ H.

(12)

Then A=

X

µπ (s)A(s).

s∈S

Lemma A.3 (Mean-square bound for the last iterate). There is a constant C < ∞ such that E ∥et ∥2H ≤ Cαt .

(13)

Proof. Let P π act on state-indexed operators in the usual way, and define the centered self-adjoint operator D(s) =

A(s) + A(s)∗ A + A∗ − . 2 2

By Lemma A.2, Q(s) =

∞ X

(P π )k D(s)

k=0

is uniformly bounded, self-adjoint, and solves the Poisson equation Q(s) − (P π Q)(s) = D(s). For every sufficiently large integer n, define Vn = ∥en ∥2H − 2αn+1 ⟨en , Q(Sn+1 )en ⟩H .

25

(14)

Writing CQ = sups ∥Q(s)∥, we have {1 − 2CQ αn+1 } ∥en ∥2H ≤ Vn ≤ {1 + 2CQ αn+1 } ∥en ∥2H , so Vn and ∥en ∥2H are uniformly equivalent for large n. The recursion (5), the martingale-difference property of mt , and uniform boundedness of mt , et , and At give ∥et − et−1 ∥H ≤ Cαt and E[∥et ∥2H | Ft−1 ] ≤ ∥et−1 ∥2H − 2αt ⟨et−1 , A(St )et−1 ⟩H + Cαt2 . Replacing et by et−1 inside the correction changes its conditional expectation by at most Cαt . Since E[Q(St+1 ) | Ft−1 ] = (P π Q)(St ), |E[⟨et , Q(St+1 )et ⟩H | Ft−1 ] − ⟨et−1 , (P π Q)(St )et−1 ⟩H | ≤ Cαt . Moreover, αt − αt+1 = O(αt /t) = O(αt2 ); multiplying this difference by the bounded correction contributes only O(αt2 ). Combining these displays with (14) cancels the state-dependent part of the first-order drift: E[Vt | Ft−1 ] ≤ Vt−1 − 2αt ⟨et−1 , {A(St ) + (P π Q)(St ) − Q(St )}et−1 ⟩H + Cαt2 = Vt−1 − 2αt ⟨et−1 , Aet−1 ⟩H + Cαt2 . The last equality is an equality of quadratic forms: Q − P π Q = D and D(St ) = sym A(St ) − sym A. The coercivity bound (10) and equivalence of the corrected Lyapunov function with the squared norm consequently yield constants c, C > 0 such that E[Vt | Ft−1 ] ≤ (1 − cαt )Vt−1 + Cαt2 for all sufficiently large t. Taking expectations and writing vt := EVt gives vt ≤ (1 − cαt )vt−1 + Cαt2 . Since αt−1 /αt = 1 + O(t−1 ) = 1 + o(αt ), induction in this scalar comparison recursion gives vt ≤ Cαt . The displayed equivalence of Vt and ∥et ∥2H proves (13). Lemma A.4 (Remainder bounds for Polyak–Ruppert averaging). The two remainder terms in (7) satisfy T

1 X −1 √ αt (et−1 − et ) = op (1) T t=1 26

and

T

1 X √ (A − At )et−1 = op (1). T t=1 Proof. Abel summation gives T X

αt−1 (et−1 − et ) = α1−1 e0 − αT−1 eT +

t=1

T −1 X

−1 (αt+1 − αt−1 )et .

t=1

By Lemma A.3, the normalized endpoint and sum on the right are both Op (T (κ−1)/2 ) = op (1). This proves the first assertion. Using the statewise mean operator in (12), decompose (A − At )et−1 = {A − A(St )}et−1 + {A(St ) − At }et−1 . The second term is a martingale difference, and boundedness of the sampled operators together with Lemma A.3 gives 2

T

1 X E √ {A(St ) − At }et−1 T t=1

H

T

CX ≤ αt = o(1). T t=1

For the state-selection term, Lemma A.2 gives the uniformly bounded solution R(s) =

∞ X

(P π )k {A − A(·)}(s),

A − A(s) = R(s) − (P π R)(s).

k=0

Hence A − A(St ) = R(St ) − R(St+1 ) + R(St+1 ) − E[R(St+1 ) | Ft−1 ]. After multiplication by et−1 , the second line is a martingale difference whose normalized sum converges to zero in L2 , again by Lemma A.3. Summation by parts and uniform boundedness of R bound the remaining normalized telescoping sum by C √ T

1+

T X

! ∥et − et−1 ∥H

.

t=2

The recursion (5) and uniform boundedness of et , mt , and At imply ∥et − et−1 ∥H ≤ Cαt . The last display is therefore O(T −1/2 + T 1/2−κ ) = o(1), 27

because κ > 1/2. This proves the second assertion. Lemma A.5 (Hilbert-space CLT for Bellman residuals). The Bellman residuals satisfy T

1 X √ mt ⇒ NH (0, Σ). T t=1 Proof. Put Σ(s) = E[mt ⊗ mt | St = s]. Each Σ(s) is nonnegative, and tr Σ(s) = E[∥mt ∥2H | St = s] ≤ (1 − γ)−1 . We give a finite-dimensional projection proof so that no Hilbert-valued martingale CLT is invoked without verifying its tightness condition. Let (uℓ )ℓ≥1 be an orthonormal basis of H, and let Pq be the orthogonal projection onto span{u1 , . . . , uq }. For fixed q, the predictable covariance matrix of Pq mt is a function only of St . The finite-state Markov ergodic theorem therefore gives T

1X E [Pq mt ⊗ Pq mt | Ft−1 ] −→ Pq ΣPq T t=1

in probability. Since ∥mt ∥H ≤ (1 − γ)−1/2 , the conditional Lindeberg condition is automatic. The ordinary q-dimensional martingale central limit theorem consequently yields T

1 X Pq √ mt ⇒ NPq H (0, Pq ΣPq ). T t=1 It remains to pass from fixed projections to H. Martingale orthogonality gives T

1 X E (I − Pq ) √ mt T t=1

2

T

= H

1X E ∥(I − Pq )mt ∥2H . T t=1

The Cesàro state frequencies converge to µπ , even from an arbitrary initial distribution, and hence the right-hand side converges to X

h i µπ (s)E ∥(I − Pq )mt ∥2H | St = s = tr{(I − Pq )Σ}.

s∈S

Since tr(Σ) =

X

h i µπ (s)E ∥mt ∥2H | St = s ≤ (1 − γ)−1 ,

s∈S

28

the projection-tail trace decreases to zero as q → ∞. Thus the normalized sums are asymptotically tight in H, and their every finite-dimensional projection converges to the corresponding projection of NH (0, Σ). The projection characterization of weak convergence in a separable Hilbert space now yields T

1 X √ mt ⇒ NH (0, Σ). T t=1

Proof of Theorem 1. Lemma A.4, using the stability bound in Lemma A.3, shows that both remain√ der sums in (7) are op (1) after summation and division by T . Hence T T 1 X 1 X et−1 = √ mt + op (1). A√ T t=1 T t=1

The endpoint identity T −1/2

PT

t=1 (et − et−1 ) = (eT − e0 )/

(15)

√ T = op (1) and bounded invertibility

of A give the linear representation. Combining the linear representation with Lemma A.5 gives a centered Gaussian limit with covariance A−1 Σ(A−1 )∗ , completing the proof.

A.3

Proofs for Section 3.3

Let e∗t = ηt∗ − η π and δt = e∗t − et = ηt∗ − ηt . Lemma A.6 (Mean-square bound for the bootstrap last iterate). There is a constant C < ∞ such that EE∗ ∥e∗t ∥2H ≤ Cαt ,

EE∗ ∥δt ∥2H ≤ Cαt .

(16)

almost surely.

(17)

Moreover, ∥δt − δt−1 ∥H ≤ Cαt Proof. The exact and bootstrap errors satisfy et = et−1 − αt At et−1 + αt mt ,

e∗t = e∗t−1 − αt Wt∗ At e∗t−1 + αt Wt∗ mt .

Subtracting the two recursions gives δt = δt−1 − αt Wt∗ At δt−1 + αt (Wt∗ − 1){mt − At et−1 }.

29

(18)

Because (αt ) is decreasing, α1 ≤ 1/2, and Wt∗ ∈ {0, 2}, we have 0 ≤ αt Wt∗ ≤ 1 for every t. Thus the visited-state update is a convex combination of probability measures, and ηt∗ remains a vector of probability measures. The multipliers are uniformly bounded. Let ∗ Fet−1 = σ(Ft−1 , W1∗ , . . . , Wt−1 ),

Fet = σ(Ft , W1∗ , . . . , Wt∗ ).

Conditional expectation below is taken jointly over the current transition and current multiplier. Their independence gives, actionwise for every h ∈ H, E[Wt∗ At h | Fet−1 ] = A(St )h,

E[Wt∗ mt | Fet−1 ] = 0.

Thus the multiplier leaves the first-order drift in the Lyapunov–Poisson argument unchanged; (Wt∗ )2 enters only the uniformly bounded second-order term. Let Q be the solution furnished by Lemma A.2 for D(s) =

A(s) + A(s)∗ A + A∗ − . 2 2

Uniform boundedness of Wt∗ , e∗t , mt , and At gives e∗t − e∗t−1 H ≤ Cαt and, after expanding the squared recursion and taking the joint conditional expectation, 2 E[∥e∗t ∥2H | Fet−1 ] ≤ e∗t−1 H − 2αt e∗t−1 , A(St )e∗t−1 H + Cαt2 .

The increment bound and E[Q(St+1 ) | Fet−1 ] = (P π Q)(St ) likewise give E[⟨e∗t , Q(St+1 )e∗t ⟩H | Fet−1 ] − e∗t−1 , (P π Q)(St )e∗t−1 H ≤ Cαt . Define, for all sufficiently large n, Vn∗ = ∥e∗n ∥2H − 2αn+1 ⟨e∗n , Q(Sn+1 )e∗n ⟩H . As in the sampling proof, Vn∗ is uniformly equivalent to ∥e∗n ∥2H , the step-size difference contributes

30

only O(αt2 ), and Q − P π Q = D cancels the state-dependent drift. Coercivity therefore gives
∗ E[Vt∗ | Fet−1 ] ≤ 1 − cαt Vt−1 + Cαt2 . The same scalar comparison used for Vt gives EE∗ Vt∗ ≤ Cαt and hence the first bound in (16). The second follows from ∥δt ∥2H ≤ 2 ∥e∗t ∥2H + 2 ∥et ∥2H and Lemma A.3. Finally, uniform boundedness of the two iterates, the multipliers, and the operators in (18) gives (17). Lemma A.7 (Bootstrap Polyak–Ruppert expansion). The averaged bootstrap error satisfies T T 1 X 1 X ∗ A√ δt = √ (Wt − 1)mt + op∗ (1) T t=1 T t=1

in H,

(19)

in probability. Proof. Rearranging (18) gives the bootstrap Polyak–Ruppert identity Aδt−1 = αt−1 (δt−1 − δt ) + (Wt∗ − 1)mt + (A − At )δt−1 − (Wt∗ − 1)At δt−1 − (Wt∗ − 1)At et−1 . We show that, after summation and division by

√

(20)

T , every term except the multiplier sum is

negligible. Abel summation and (16) imply T

1 X −1 √ αt (δt−1 − δt ) = op (1). T t=1 −1 − αt−1 has the same order. Indeed, the endpoint term is Op (T (κ−1)/2 ), and the sum involving αt+1

For the Markovian operator remainder, the term T

1 X √ {A(St ) − At }δt−1 T t=1 is a square-integrable martingale sum whose second moment is bounded by CT −1 For the state-selection term, Lemma A.2 gives the bounded operator R(s) =

∞ X (P π )k {A − A(·)}(s), k=0

31

P

t≤T αt = o(1).

and write A − A(St ) = R(St ) − R(St+1 ) + R(St+1 ) − E[R(St+1 ) | Ft−1 ]. The centered term yields another martingale sum with second moment at most CT −1

P

t≤T αt .

Summation by parts, uniform boundedness of R, and (17) bound the normalized telescoping term by ( CT −1/2

1+

T X

) αt

= O T −1/2 + T 1/2−κ = o(1).

t=2

Hence

T

1 X √ (A − At )δt−1 = op (1). T t=1

(21)

Independence and centering of Wt∗ − 1 make each of the last two sums in (20) a martingale sum in the enlarged filtration. Boundedness of At , (13), and (16) give

∗

EE

T

2

T

H 2

1 X ∗ √ (Wt − 1)At δt−1 T t=1

1 X ∗ EE∗ √ (Wt − 1)At et−1 T t=1

T

CX αt = o(1), ≤ T t=1 T

≤ H

CX αt = o(1). T t=1

Combining these bounds with (20) yields, under the joint law of the data and the multipliers, T T 1 X ∗ 1 X δt−1 = √ (Wt − 1)mt + op (1). A√ T t=1 T t=1

Because δ0 = 0 and δT is uniformly bounded, T

1 X δT √ (δt − δt−1 ) = √ = op (1). T t=1 T This proves (19) under the joint law. For any joint remainder RT∗ = op (1) and every ε, η > 0, E[P∗ {∥RT∗ ∥H > ε}] = EE∗ [1{∥RT∗ ∥H > ε}] −→ 0, where the expectation on the right is under the joint data–multiplier law. Markov’s inequality therefore gives P [P∗ {∥RT∗ ∥H > ε} > η] −→ 0,

32

which proves the stated op∗ (1) remainder in P-probability. Lemma A.8 (Conditional Gaussian limit of the leading multiplier sum). The leading multiplier sum satisfies T

1 X ∗ √ (Wt − 1)mt ⇒∗ NH (0, Σ) T t=1

in H, for P-almost every observed trajectory.

Proof. Put ξt∗ = Wt∗ −1. Conditional on the data, the variables T −1/2 ξt∗ mt are independent, centered H-valued random elements. For every h, g ∈ H, a scalar martingale law of large numbers followed by the Markov ergodic theorem gives T

T

t=1

t=1

1X 1X ⟨mt , h⟩H ⟨mt , g⟩H − E[⟨mt , h⟩H ⟨mt , g⟩H | Ft−1 ] −→ 0, T T 1 T

T X

E[⟨mt , h⟩H ⟨mt , g⟩H | Ft−1 ] −→ ⟨Σh, g⟩H ,

t=1

almost surely. Let (uℓ )ℓ≥1 be an orthonormal basis of H, and let Pq be the orthogonal projection onto span{u1 , . . . , uq }. Applying the preceding limits to the countable collection of basis pairs, and applying the same argument to ∥(I − Pq )mt ∥2H , shows that the following convergences hold simultaneously for every fixed q on a single event of P-probability one: T

1X Pq mt ⊗ Pq mt −→ Pq ΣPq , T

(22)

t=1

T

1X ∥(I − Pq )mt ∥2H −→ tr{(I − Pq )Σ}. T

(23)

t=1

On this event, (22) is the convergence of the conditional covariance of the projected multiplier sum. Since ξt∗ ∈ {−1, 1} and ∥mt ∥H ≤ (1 − γ)−1/2 , the conditional Lindeberg condition is zero for all sufficiently large T . The finite-dimensional Lindeberg–Feller theorem therefore gives, for every fixed q, T

1 X ∗ Pq √ ξt mt ⇒∗ NPq H (0, Pq ΣPq ). T t=1 For the projection tails, conditional independence, centering, and E∗ [(ξt∗ )2 ] = 1 give T

∗

E

1 X ∗ (I − Pq ) √ ξt mt T t=1

2

T

= H

33

1X ∥(I − Pq )mt ∥2H . T t=1

Moreover, boundedness of mt gives tr(Σ) =

X

i h µπ (s)E ∥mt ∥2H | St = s ≤ (1 − γ)−1 ,

s∈S

so tr{(I − Pq )Σ} → 0 as q → ∞. Together with (23), conditional Markov’s inequality therefore gives, on the same event, for every ε > 0, T

( lim lim sup P

1 X ∗ (I − Pq ) √ ξt m t T t=1

∗

q→∞ T →∞

) >ε

= 0.

H

The same tail trace controls the Gaussian limit. Hence the finite-dimensional conditional convergence and conditional tightness establish the asserted conditional weak convergence for every trajectory in this event of probability one. Proof of Theorem 2. Lemma A.7 and bounded invertibility of A give 1 Z∗T = A−1 √

T X

T t=1

(Wt∗ − 1)mt + op∗ (1)

in H,

in probability. Lemma A.8 and boundedness of A−1 show that the leading term converges conditionally to G for P-almost every observed trajectory. The conditional remainder above means that, for every ε, η > 0, " P P∗

(

T

1 X ∗ Z∗T − A−1 √ (Wt − 1)mt T t=1

) >ε

# > η −→ 0.

H

This conditionally negligible perturbation therefore does not alter the conditional weak limit, and Z∗T ⇒∗ G

A.4

in H, in P-probability.

Proofs for Section 3.4

Proof of Theorem 3. Regard Φ as a functional on the Cramér space, and write θ0 = η π ,

θT = η̄T .

34

Then √

T (θT − θ0 ) = ZT .

Theorem 1 implies that ZT is tight in H, and hence ∥θT − θ0 ∥H = Op (T −1/2 ). By Hadamard differentiability, √

T {Φ(η̄T ) − Φ(η π )} = Φ̇ηπ (ZT ) + op (1).

(24)

Since Φ̇ηπ is continuous and linear, Theorem 1, the continuous mapping theorem, and (24) give √

T {Φ(η̄T ) − Φ(η π )} ⇒ Φ̇ηπ (G).

For finitely many functionals, stack the maps and their derivatives and apply the same argument. For the bootstrap conclusion, write θ0 = η π , θT = η̄T , and θT∗ = η̄T∗ . The conditional weak convergence in Theorem 2 implies unconditional weak convergence of Z∗T to G. Indeed, for every bounded continuous f : H → R, p

E∗ [f (Z∗T )] → − E[f (G)] . Because these conditional expectations are bounded, the convergence also holds in L1 . Taking expectation under the data-generating law gives E[f (Z∗T )] = E{E∗ [f (Z∗T )]} −→ E[f (G)] . Thus ZT and Z∗T are tight under the joint law of the data and multipliers. Their pair and the sum ZT + Z∗T are therefore tight as well. Under the stated Hadamard differentiability tangentially to the full space H, the defining expansion is uniform over compact sets of directions. Applying that uniform expansion on compact sets which contain the two tight random directions with arbitrarily high probability gives, under the joint law, √ √

T {Φ(η̄T∗ ) − Φ(η π )} = Φ̇ηπ (ZT + Z∗T ) + op (1), T {Φ(η̄T ) − Φ(η π )} = Φ̇ηπ (ZT ) + op (1).

Subtracting and using linearity yields √

T {Φ(η̄T∗ ) − Φ(η̄T )} = Φ̇ηπ (Z∗T ) + RT∗ , 35

RT∗ = op (1)

(25)

under the joint law. For every ε, η > 0, P [P∗ (∥RT∗ ∥ > ε) > η] ≤ η −1 P(∥RT∗ ∥ > ε) −→ 0, so RT∗ = op∗ (1) in probability. The conditional continuous mapping theorem applied to the bounded linear map Φ̇ηπ , together with the conditionally negligible remainder in (25), proves the asserted conditional weak convergence in probability. For finitely many functionals, stack them into a single Euclidean-valued map and stack their derivatives. The same argument gives the joint conclusion. When d = 1 and the Gaussian limit is nondegenerate, its distribution function is continuous p

∗ and strictly increasing. The conditional weak convergence therefore implies qT,p → − qp for every

p ∈ (0, 1), where qp is the p-quantile of Φ̇ηπ (G). Combining this quantile convergence with the sampling conclusion gives i h √ ∗ ∗ −→ 1 − α. P qT,α/2 ≤ T {Φ(η̄T ) − Φ(η π )} ≤ qT,1−α/2 Rearranging the inequalities proves the stated confidence-interval coverage.

B

Proofs for Section 4

B.1

Proofs for Section 4.1

Lemma B.1 (Density bounds for the TD iterates). Every exact iterate ηt (s) has a density ft,s . If Kt = maxs ∥ft,s ∥∞ , then

Kt ≤ K0

t Y

{1 + (γ −1 − 1)αj } ≤ C exp(Ct1−κ ).

(26)

j=1

Every bootstrap iterate has a density and, almost surely under the joint data–multiplier law, ∗ max ft,s ≤ C exp(Ct1−κ ). ∞ s∈S

(27)

Consequently, the exact CDF iterates and their bootstrap counterparts are Lipschitz, with the same displayed deterministic growth bound. Proof. Extend every density by zero outside [0, (1 − γ)−1 ]. At the visited state, the density form of 36

(1) is ft,St (x) = (1 − αt )ft−1,St (x) + αt γ

−1

 ft−1,St+1

x − Rt γ

 ,

while the other statewise densities are unchanged. Hence Kt ≤ {1 + (γ −1 − 1)αt }Kt−1 . Iterating this inequality, using 1 + u ≤ eu and

Pt

1−κ , proves (26). For the bootstrap j=1 αj ≤ Ct

recursion, replace αt by αt Wt∗ . Because (αt ) is decreasing, α1 ≤ 1/2, and Wt∗ ∈ {0, 2}, we have 0 ≤ αt Wt∗ ≤ 1 for every t. The bootstrap density update is therefore a nonnegative mixture, and the same calculation proves (27). An absolutely continuous distribution has a Lipschitz CDF with Lipschitz constant bounded by the essential supremum of its density. Lemma B.2 (An interpolation inequality for CDFs). Let F and G be CDFs of laws supported on [0, (1 − γ)−1 ], and suppose that the extension of F by zero to the left of 0 and by one to the right of (1 − γ)−1 is K-Lipschitz. Then ∥G − F ∥3∞ ≤ CK,γ

Z (1−γ)−1

|G(y) − F (y)|2 dy.

(28)

0

Proof. Suppose first that G(z) − F (z) = a > 0. Since G(z) ≤ 1, Lipschitz continuity gives a ≤ 1 − F (z) ≤ K{(1 − γ)−1 − z}. Monotonicity then implies G(y) − F (y) ≥ a/2 for z ≤ y ≤ z + a/(2K), so the integral in (28) is at least a3 /(8K). If F (z) − G(z) = a > 0, the same argument applies on [z − a/(2K), z], using a ≤ F (z) ≤ Kz. Taking the supremum over z proves the claim. Lemma B.3 (Uniform CDF last-iterate bounds). Let et = ηt − η π and Et◦ = max Fet (s) ∞ . s∈S

Then 2/3

E[(Et◦ )2 ] ≤ Cαt . For the bootstrap iterates, define e∗t = ηt∗ − η π , δt = e∗t − et , Et∗,◦ = maxs Fe∗t (s)

(29)

∞

, and Dt◦ =

maxs Fδt (s) ∞ . Then   2/3 EE∗ (Et∗,◦ )2 + (Dt◦ )2 ≤ Cαt .

37

(30)

Proof. Apply Lemma B.2 statewise and use finiteness of S. Jensen’s inequality and Lemma A.3 give 4/3

2/3

E[(Et◦ )2 ] ≤ CE ∥et ∥H ≤ C{E ∥et ∥2H }2/3 ≤ Cαt . The same argument with Lemma A.6 gives the bound for Et∗,◦ ; the bound for Dt◦ follows from δt = e∗t − et and the triangle inequality. Lemma B.4 (Martingale bound on a deterministic grid). Let U be a compact interval and, for every T , let {Dt,T (z) : z ∈ U }Tt=1 be scalar martingale differences with respect to a common filtration. Suppose that, for deterministic sequences BT , ΛT ≥ 0, sup |Dt,T (z)| ≤ BT ,

Dt,T (z) − Dt,T (z ′ ) ≤ ΛT z − z ′

z∈U

almost surely for every t. Define T

1X E[Dt,T (z)2 | Ft−1 ], T z∈U

σT2 = sup

ℓT = log{2 + CU T 2 (1 + ΛT )},

t=1

where CU depends only on the length of U . If sT > 0 is deterministic and σT = Op (sT ), then   p T 1 X B T ℓT −3/2 √ √ sup Dt,T (z) = Op sT ℓT + +T . T t=1 T z∈U

(31)

The same conclusion holds conditionally in probability, with Op∗ , when the hypotheses and the predictable-variance bound hold under the conditional law while BT and ΛT remain deterministic. Proof. Cover U by a deterministic grid of mesh ρT = {T 2 (1 + ΛT )}−1 . Its cardinality is at most 1 + CU T 2 (1 + ΛT ). If z ◦ is a closest grid point to z, the off-grid interpolation error in the normalized sum is bounded by T

√ 1 X √ |Dt,T (z) − Dt,T (z ◦ )| ≤ T ΛT ρT ≤ T −3/2 . T t=1 On the event σT ≤ M sT , the predictable quadratic variation of the unnormalized sum at every grid point is at most T M 2 s2T . Freedman’s inequality at each point and a union bound over the 38

deterministic grid therefore imply, for every u ≥ 1, #   T p 1 X BT (ℓT + u) ◦ √ √ , σT ≤ M sT ≤ 2e−u . Dt,T (z ) > C M sT ℓT + u + P max z◦ T t=1 T "

Because σT = Op (sT ), first choose M large and then u large. Adding the interpolation error proves (31). For the conditional assertion, the same display holds with P∗ whenever σT ≤ M sT . The assumption σT = Op∗ (sT ) in probability means that, for every ε, η > 0, M can be chosen so that lim sup P{P∗ (σT > M sT ) > η} < ε. T →∞

The conditional Freedman display, followed by this localization and then the choices of u and M , proves the stated Op∗ bound in probability. Fix s ∈ S, x ∈ (0, (1 − γ)−1 ), and a closed neighborhood U ⊂ (0, (1 − γ)−1 ) of x. Since A = Dµπ (I − T π ), its inverse has the Neumann representation −1

A

=

∞ X

(T π )q Dµ−1 . π

q=0

For g ∈ H with bounded cumulative functions, extended by zero outside [0, (1 − γ)−1 ], this gives

F(A−1 g)(s) (z) =

∞ X

F[(T π )q Dµ−1 g](s) (z), π

z ∈ U.

(32)

q=0

Lemma B.5 (Pointwise representation of A−1 ). The series in (32) converges absolutely and uniformly on U , and F(A−1 Ag)(s) (z) = Fg(s) (z),

z ∈ U.

(33)

Proof. Start the policy trajectory at S0 = s, put

Gq =

q−1 X

γ ℓ Rℓ ,

µmin = min µπ (r), r∈S

ℓ=0

and couple Gq with the infinite return Gπ (s). Iterating the signed-measure Bellman operator and

39

then taking cumulative functions gives    z − Gq . F[(T π )q Dµ−1 g](s) (z) = Es µπ (Sq )−1 Fg(Sq ) π γq If maxr Fg(r) ∞ ≤ 1, then q −1 sup F[(T π )q Dµ−1 g](s) (z) ≤ µ−1 min sup Ps Gq ≤ z ≤ Gq + γ (1 − γ) π

z∈U

z∈U

π q −1 ≤ µ−1 ≤ Cγ q min sup Ps |G (s) − z| ≤ γ (1 − γ)

(34)

z∈U

for all sufficiently large q, by boundedness of fs on a slightly larger neighborhood of U . Scaling proves (34), hence absolute and uniform convergence. Telescoping gives

F(A−1 Ag)(s) (z) =

∞ X

F[(T π )q (I−T π )g](s) (z) = Fg(s) (z),

z ∈ U,

q=0

because the terminal term vanishes by (34). For every interval I ⊂ U , with |I| denoting its length, the same coupling yields, for all sufficiently large q,

Ps Gq ∈ I + [−γ q (1 − γ)−1 , 0] ≤ Ps Gπ (s) ∈ I + [−γ q (1 − γ)−1 , γ q (1 − γ)−1 ] ≤ C{|I| + γ q }. (35)

For q ≥ 1, write A−1 [q] g =

q−1 h X

(T π )ℓ Dµ−1 g π

i

(36)

ℓ=0

for the q-term truncation of A−1 . For h ∈ H whose cumulative functions have globally Lipschitz zero extensions, write Fh(r) (u) − Fh(r) (v) , r∈S u̸=v |u − v|

|h|Lip = max sup

∥h∥∞ = max Fh(r) ∞ . r∈S

Lemma B.6 (Lipschitz bounds for the Bellman operators). Let A(r) be the actionwise conditional mean in (12), and put R(r) =

∞ X (P π )k {A − A(·)}(r). k=0

40

For every h ∈ H with bounded, globally Lipschitz cumulative functions, |(T π )q h|Lip ≤ γ −q |h|Lip .

|At h|Lip + |A(r)h|Lip + |Ah|Lip + |R(r)h|Lip ≤ C |h|Lip ,

Moreover, if B is any difference or finite-state average of these operators, then the q-term truncation of A−1 satisfies sup F(A−1 Bh)(s) (z) ≤ Cq ∥h∥∞ ,

z∈U

F(A−1 Bh)(s)

[q]

[q]

≤ Cγ −q |h|Lip . Lip

Proof. The affine pullback of cumulative functions in At multiplies Lipschitz constants by at most γ −1 , while conditioning and finite-state averaging do not increase them beyond a fixed factor. This proves the bounds for At , A(r), A, and (T π )q . Geometric ergodicity gives ∞ X k=0

max r∈S

X

(P π )k (r, u) − µπ (u) < ∞,

u∈S

and (P π )k {A − A(·)}(r) =

X

{µπ (u) − (P π )k (r, u)}A(u),

u∈S

which proves the bound for R(r). Finally, sum the sup-norm and Lipschitz bounds over the q terms P −ℓ ≤ Cγ −q . in A−1 ℓ<q γ [q] ; Lemma B.7 (Step-size remainder at a selected threshold). With the notation of Lemma B.5, let et = ηt − η π . Then sup FA−1 √1 PT

z∈U

T

 (z) (s)

−1 t=1 αt (et−1 −et )

= op (1).

Proof. Fix s, x, and the neighborhood U from Lemma B.5. Truncate (32) at qT = ⌈c log T ⌉, where c is chosen so that γ qT = o(T −1 ). The tail estimate (34) implies, for every signed-measure perturbation h with bounded, zero-extended cumulative functions, sup F((A−1 −A−1 )h)(s) (z) ≤ Cγ qT ∥h∥∞ .

z∈U

[qT ]

Every summand in the step-size remainder is uniformly bounded in sup norm, so its normalized √ partial sum is at most C T deterministically. Consequently, the omitted contribution is bounded √ by C T γ qT = o(1), uniformly on U . For pointwise control of the truncated term, use Et◦ and the

41

bound (29) from Lemma B.3. Since T π is a Markov averaging operator on bounded perturbations, sup F(A−1 g)(s) (z) ≤ CqT ∥g∥∞ . [qT ]

z∈U

Abel summation gives the exact identity T X

αt−1 (et−1 − et ) = α1−1 e0 − αT−1 eT +

T −1 X

−1 (αt+1 − αt−1 )et .

t=1

(37)

t=1

−1 Because αt−1 = (t + t0 )κ /a ≍ tκ and αt+1 − αt−1 = O(tκ−1 ), Cauchy–Schwarz and (29) imply

α1−1 E0◦ + αT−1 ET◦ +

T −1 X

−1 (αt+1 − αt−1 )Et◦

t=1

= Op (T 2κ/3 ). 1/3

Indeed, EEt◦ ≤ Cαt , the endpoint contribution is O(T 2κ/3 ), and the sum is bounded in expectation P by C t<T t2κ/3−1 = O(T 2κ/3 ). Applying A−1 [qT ] to (37) and evaluating the resulting cumulative function at (s, z) therefore gives sup FA−1 √1 PT

z∈U

[qT ]



−1 t=1 αt (et−1 −et )

T

(s)

(z)

  = Op (log T )T 2κ/3−1/2 = op (1), where the last equality uses κ < 3/4. Lemma B.8 (Random-operator remainder at selected thresholds). Under the same conditions, sup FA−1 √1 PT

z∈U

T

t=1 (A−At )et−1



(s)

(z) = op (1).

Proof. Let qT be the truncation level used in the proof of Lemma B.7. The cumulative functions of et vanish at both endpoints and are extended by zero outside [0, (1 − γ)−1 ]. Since the exact iterates and the population return laws are absolutely continuous, Fet (r) (0) = Fet (r) ((1 − γ)−1 ) = 0. Its zero extension is consequently globally Lipschitz with the same constant as on [0, (1 − γ)−1 ].

42

This endpoint property is also preserved by the sampled operator: at z = 0 the affine argument (z − Rt )/γ is at most zero, while, because Rt ≤ 1, (1 − γ)−1 − Rt ≥ (1 − γ)−1 γ

at z = (1 − γ)−1 .

Thus every perturbation to which (T π )q is applied below has a globally Lipschitz zero extension. Lemma B.1 and Assumption 1 give, deterministically along every realized path, |et |Lip ≤ Kt + KF ≤ C exp(Ct1−κ ).

(38)

Lemma B.6 supplies the required operator bounds. In particular, the two martingale arrays in the sampling remainder are tr Dt,T (z) = F(A−1 {A(St )−At }et−1 )(s) (z), [qT ]

st Dt,T (z) = F(A−1 {R(St+1 )−(P π R)(St )}et−1 )(s) (z). [qT ]

Both are martingale differences with respect to the pre-transition filtration Ft−1 = σ{S0 , (Au , Ru , Su+1 )u<t , St }. Indeed, et−1 is Ft−1 -measurable and E[At h | Ft−1 ] = A(St )h

for every h ∈ H,

E[R(St+1 ) | Ft−1 ] = (P π R)(St ).

The truncated inverse is deterministic and linear, so applying it and evaluating its cumulative function preserves conditional centering. The preceding operator bounds show that either array, denoted generically by Dt,T , has the deterministic pathwise bounds sup |Dt,T (z)| ≤ CqT , z∈U

|Dt,T |Lip ≤ ΛT := Cγ −qT exp(CT 1−κ ).

(39)

In particular, the logarithmic grid factor in Lemma B.4 satisfies ℓT = O(T 1−κ ),

43

(40)

because qT = O(log T ). For the transition-noise component of (A − At )et−1 , the envelope after applying A−1 [qT ] and ◦ . Its largest predictable variance consequently satisfies evaluating its cumulative function is CqT Et−1

1 σT2 ≤ CqT2 T

T X ◦ (Et−1 )2 . t=1

The expectation of the right-hand side is O(qT2 T −2κ/3 ) by (29), so Markov’s inequality gives   σT = Op qT 

T 1X

T

2/3

αt

!1/2  

= Op (qT T −κ/3 ).



t=1

The same variance calculation applies to the centered Poisson martingale array. Lemma B.4, with sT = qT T −κ/3 , BT = CqT , and (40), therefore gives for either array n o Op (log T )T 1/2−5κ/6 + (log T )T 1/2−κ + T −3/2 = op (1). For completeness, put B(r) = A − A(r). The finite-state Poisson equation B = R − P π R yields B(St )et−1 = {R(St ) − R(St+1 )}et−1 + {R(St+1 ) − (P π R)(St )}et−1 . The second line is the centered Poisson martingale array already controlled above. Summation by parts makes the first line explicit: T X {R(St ) − R(St+1 )}et−1 = R(S1 )e0 − R(ST +1 )eT t=1

+

T X

R(St+1 )(et − et−1 ).

t=1

Since ∥et − et−1 ∥∞ ≤ Cαt , applying the truncated inverse, evaluating its cumulative function, and √ dividing by T bounds this term by CqT √ T

1+

T X

! αt

  = O (log T ){T −1/2 + T 1/2−κ } .

t=1

44

Consequently all the normalized endpoint, Poisson, and martingale terms are, uniformly on U , h n oi Op (log T ) T 2κ/3−1/2 + T 1/2−5κ/6 + T 1/2−κ + T −1/2 + op (1) = op (1). Every displayed power of T is negative under 3/5 < κ < 3/4. The tail of A−1 is op (1) uniformly on U by the truncation argument in Lemma B.7. Combining the tail, martingale, Poisson, and endpoint bounds proves the result. Lemma B.9 (Pointwise Polyak–Ruppert expansion). With the notation of Lemma B.5, if rT ↓ 0 is deterministic and UT = {z : |z − x| ≤ rT }, then T √  1 X T F̄T,s (z) − Fs (z) − √ F(A−1 mt )(s) (z) = op (1). T t=1 z∈UT

sup

Proof of Lemma B.9. Sum (7), divide by

√

(41)

T , apply A−1 , and evaluate the resulting cumulative

function at (s, z). The identity (33) identifies the left-hand side, while Lemmas B.7 and B.8 remove the other two terms. Thus, uniformly on UT , T T 1 X 1 X √ Fet−1 (s) (z) = √ F(A−1 mt )(s) (z) + op (1). T t=1 T t=1

√ Replacing Fet−1 (s) by Fet (s) changes the expression by {FeT (s) (z) − Fe0 (s) (z)}/ T = o(1), uniformly in z, and proves (41). Lemma B.10 (Martingale CLT for the pointwise influence vector). For s ∈ S and z ∈ (0, (1 − γ)−1 ), define ψs,z,t = F(A−1 mt )(s) (z). For the thresholds x1 , . . . , xk , let
ψtS (x) = ψs,xj ,t s∈S, 1≤j≤k . Then (ψtS (x)) is a bounded martingale-difference sequence and T

1 X S √ ψt (x) ⇒ N|S|k (0, ΩSx ), T t=1

45

where ΩSx is defined in (9). Proof. The residual mt is uniformly bounded and satisfies E[mt | Ft−1 ] = 0. Absolute and uniform convergence of the Neumann series for A−1 in Lemma B.5 therefore implies that every ψs,xj ,t is bounded and conditionally centered. Hence (ψtS (x), Ft ) is a bounded R|S|k -valued martingaledifference sequence. The conditional covariance depends on the past through the current state. The Markov ergodic theorem gives T i p X h i 1X h S E ψt (x)ψtS (x)T | Ft−1 → − µπ (s)E ψtS (x)ψtS (x)T | St = s = ΩSx . T t=1

s∈S

Boundedness makes the conditional Lindeberg condition immediate. The multivariate martingale central limit theorem gives the stated convergence. Lemma B.11 (Local stochastic equicontinuity). For each j, choose a closed neighborhood Uj ⊂ (0, (1 − γ)−1 ) of xj . Then, for every s ∈ S, j = 1, . . . , k, and ε > 0, 

 √

 lim lim sup P  sup δ↓0

T →∞

z∈Uj |z−xj |≤δ

 T {F̄T,s (z) − Fs (z)} − {F̄T,s (xj ) − Fs (xj )} > ε = 0.

Proof of Lemma B.11. Fix s and j, and abbreviate x = xj , U = Uj , and ψz,t = ψs,z,t . We first derive a pathwise modulus for the influence process. By Assumption 1, the CDFs extended by zero to the left of 0 and by one to the right of (1 − γ)−1 are globally KF -Lipschitz, and hence every realized residual path satisfies max Fmt (r) (u) − Fmt (r) (v) ≤ Km |u − v| , r∈S

Km = KF (1 + γ −1 ).

For d = |z − z ′ |, write the difference of the q-th terms in the two Neumann expansions of A−1 as ∆q,t (z, z ′ ). The affine scaling inside (T π )q gives ∆q,t (z, z ′ ) ≤ Cdγ −q . On the other hand, applying the small-ball estimate (34) separately at z and z ′ gives |∆q,t (z, z ′ )| ≤

46

Cγ q . Therefore ψz,t − ψz ′ ,t ≤ C

∞ X

√ min{dγ −q , γ q } ≤ C d

almost surely,

(42)

q=0

uniformly in t, z, z ′ ∈ U , and the value of St . In particular, i h 2 max E ψz,t − ψz ′ ,t | St = r ≤ C z − z ′ . r∈S

We now give the chaining step. On Iδ = {z ∈ U : |z − x| ≤ δ}, take nested dyadic grids with mesh dℓ ≤ 2δ2−ℓ . Each grid has at most C2ℓ adjacent increments. For every such edge (z, z ′ ), the variables ψz,t − ψz ′ ,t are martingale differences, their total predictable variance after p normalization by T −1/2 is at most Cdℓ , and their normalized absolute bound is at most C dℓ /T by (42). Consequently, for every u ≥ 1, the scalar martingale Bernstein inequality followed by a union bound over all edges and all levels gives, with probability at least 1 − Ce−u ,   T √ −ℓ/2 √ 1 X 1+ℓ+u ′ √ √ max {ψz,t − ψz ,t } ≤ C δ 2 1+ℓ+u+ edges at level ℓ T t=1 T simultaneously for every ℓ ≥ 0. Indeed, choosing the Bernstein exponent proportional to 1 + ℓ + u makes the failure probability at level ℓ at most Ce−u−cℓ , which is summable over ℓ. Since ∞ X

−ℓ/2

2

√

∞ X

√

1 + ℓ + u ≤ C 1 + u,

2−ℓ/2 (1 + ℓ + u) ≤ C(1 + u),

ℓ=0

ℓ=0

and every finite-T influence sum has continuous paths by (42), the dyadic chains converge to every z ∈ Iδ and yield  ! T √ √ 1 X 1+u {ψz,t − ψx,t } > C δ ≤ Ce−u . P sup √ 1+u+ √ T t=1 T z∈Iδ First taking T → ∞, then choosing u large and letting δ ↓ 0, gives   lim lim sup P  sup δ↓0

T →∞

z∈U |z−x|≤δ

T X



1  √ (ψz,t − ψx,t ) > ε = 0 T t=1

(43)

for every ε > 0. Combining (41), which holds for every deterministic rT ↓ 0, with (43) and using

47

the subsequence characterization of stochastic equicontinuity gives 



√   lim lim sup P  sup T {F̄T,s (z) − Fs (z)} − {F̄T,s (x) − Fs (x)} > ε = 0. δ↓0

T →∞

z∈U |z−x|≤δ

Taking the maximum over s ∈ S and j = 1, . . . , k preserves this conclusion. Proof of Theorem 4. For every s ∈ S and j = 1, . . . , k, choose the neighborhood in Lemma B.5. Lemma B.9, evaluated at z = xj , gives T

1 X S FT,x (0) = √ ψt (x) + op (1) T t=1

in R|S|k .

Lemma B.10 gives the weak convergence of the leading martingale sum to N|S|k (0, ΩSx ). Slutsky’s theorem then gives FT,x (0) ⇒ GSx . √ Lemma B.11, evaluated on |z − xj | ≤ M/ T , gives stochastic equicontinuity jointly over all s ∈ S and j = 1, . . . , k. Continuity of the densities also gives the deterministic drift uniformly over the same neighborhoods. Therefore, sup h∈[−M,M ]|S|k

FT,x (h) − FT,x (0) − fxS ⊙ h ∞ = op (1).

Combining this uniform expansion with the fixed-threshold limit proves the asserted convergence in ℓ∞ ([−M, M ]|S|k ; R|S|k ).

B.2

Proofs for Section 4.2

Lemma B.12 (Bootstrap step-size and random-operator remainders). Let et = ηt − η π and δt = ηt∗ − ηt . For every fixed s ∈ S, x ∈ (0, (1 − γ)−1 ), and regular neighborhood U , sup FA−1 √1 PT

z∈U

sup FA−1 √1 PT

z∈U

 (z) (s)

= op∗ (1),

 (z) (s)

= op∗ (1)

−1 t=1 αt (δt−1 −δt )

T

T

t=1 (A−At )δt−1

in probability.

48

Proof. Put e∗t = ηt∗ − η π , so that δt = e∗t − et , and fix s, x, and the neighborhood U . Let qT = ⌈c log T ⌉, with c chosen so that γ qT = o(T −1 ). The multiplier restriction makes the Wt∗ ’s uniformly bounded. Use the notation and uniform pointwise bounds (29)–(30) from Lemma B.3. Lemma B.1 gives the deterministic pathwise bounds |e∗t |Lip + |δt |Lip ≤ C exp(Ct1−κ ),

(44)

Lemma B.6 and the uniform bound on Wt∗ show that each transition or centered Poisson array obtained from A−1 [qT ] , with et−1 replaced by δt−1 , has envelope CqT and Lipschitz constant at most ΛT = Cγ −qT exp(CT 1−κ ). These arrays are martingale differences under the joint law with respect to ∗ Fet−1 = Ft−1 ∨ σ(W1∗ , . . . , Wt−1 ).

Consequently, the deterministic grid in Lemma B.4 has ℓT = O(T 1−κ ). The bootstrap weights and the cumulative functions of every signed-measure perturbation are √ uniformly bounded, so (34) bounds the truncation error by C T γ qT = o(1), uniformly on U . Abel summation and (30) bound the step-size term in (20) by T X

αt−1 (δt−1 − δt ) = α1−1 δ0 − αT−1 δT

t=1

+

T −1 X

−1 (αt+1 − αt−1 )δt .

t=1

After applying A−1 [qT ] , evaluating its cumulative function at (s, z), and dividing by

√

T , the same

calculation as in (37) gives n o Op (log T )T 2κ/3−1/2 = op (1). For (A − At )δt−1 , the transition-noise component is a scalar martingale sum after application of A−1 [qT ] and pointwise evaluation, and the state-selection component is handled with the finite-state Poisson

49

equation. For either resulting joint martingale array, its predictable standard deviation satisfies T

{σTδ }2 ≤ CqT2

1X ◦ 2 (Dt−1 ) . T t=1

Equation (30) and Markov’s inequality under the joint law give σTδ = Op (qT T −κ/3 ). Lemma B.4 and (44) therefore give, for either joint martingale array, n o Op (log T )T 1/2−5κ/6 + (log T )T 1/2−κ + T −3/2 = op (1). Writing again B = R − P π R, the state-selection term decomposes as T X

B(St )δt−1 =

t=1

T X

{R(St+1 ) − (P π R)(St )}δt−1

t=1

+ R(S1 )δ0 − R(ST +1 )δT +

T X

R(St+1 )(δt − δt−1 ).

t=1

The first line is the centered Poisson martingale array. The last line, ∥δt − δt−1 ∥∞ ≤ Cαt , and qT = O(log T ) contribute Op ((log T ){T −1/2 + T 1/2−κ }). Hence the entire (A − At )δt−1 remainder is uniformly op (1) under the joint law. If RT ≥ 0 denotes either joint remainder, then, for every ε, η > 0, P{P∗ (RT > ε) > η} ≤ η −1 (P ⊗ P∗ )(RT > ε) −→ 0. Thus both joint bounds are op∗ (1) in probability. Lemma B.13 (Conditional multiplier remainders). Let ξt∗ = Wt∗ − 1. Under the conditions of Lemma B.12, sup FA−1 √1 PT

 (z) (s)

= op∗ (1),

sup FA−1 √1 PT

 (z) (s)

= op∗ (1)

z∈U

z∈U

T

T

∗ t=1 ξt At δt−1

∗ t=1 ξt At et−1

in probability. Proof. Let qT = ⌈c log T ⌉ be the same truncation level as above. Conditional on the observed trajectory and the past multipliers, the arrays obtained from ξt∗ At δt−1 and ξt∗ At et−1 are centered. Lemmas B.1 and B.6 give deterministic Lipschitz bounds of the form used in Lemma B.4. Their global

50

◦ ◦ , respectively, and their conditional predictable envelopes are bounded by CqT Dt−1 and CqT Et−1

standard deviations obey T

{σT∗,δ }2 ≤ CqT2

T

1X ◦ 2 (Dt−1 ) , T

{σT∗,e }2 ≤ CqT2

t=1

1X ◦ 2 (Et−1 ) . T t=1

For the first bound, (30) gives, for every M, η > 0, T

" P P

∗

1X ◦ 2 (Dt−1 ) > M T −2κ/3 T

!

# >η ≤

t=1

C ; Mη

this is Markov’s inequality first conditionally and then under the data law. The same conclusion for the second bound follows from (29). Hence σT∗,δ + σT∗,e = Op∗ (qT T −κ/3 )

in probability.

The conditional assertion in Lemma B.4 therefore gives, for each of the two normalized suprema, n o Op∗ (log T )T 1/2−5κ/6 + (log T )T 1/2−κ + T −3/2 = op∗ (1) in probability. This proves both conditional multiplier bounds. Lemma B.14 (Pointwise bootstrap Polyak–Ruppert expansion). Let ξt∗ = Wt∗ − 1 and ψs,z,t = F(A−1 mt )(s) (z). Fix s ∈ S and x ∈ (0, (1 − γ)−1 ), let rT ↓ 0 be deterministic, and set UT = {z : |z − x| ≤ rT }. Then √ sup z∈UT

T

1 X ∗ T {Fη̄T∗ (s) (z) − F̄T,s (z)} − √ ξt ψs,z,t = op∗ (1) T t=1

(45)

in probability. Proof of Lemma B.14. Let δt = ηt∗ − ηt . Sum (20), divide by

√

T , apply A−1 , and evaluate its

cumulative function at (s, z). The identity (33) identifies the left-hand side. Lemmas B.12 and B.13

51

remove the four remainder terms, and the leading term becomes T −1/2

PT

∗ t=1 ξt ψs,z,t . Finally,

T

1 X δT √ (δt − δt−1 ) = √ = o(1) T t=1 T uniformly in the threshold z, which proves (45). Lemma B.15 (Conditional multiplier central limit theorem). With the notation of Lemma B.14, let
ψtS (x) = ψs,xj ,t s∈S, 1≤j≤k . Then

T

1 X ∗ S √ ξt ψt (x) ⇒∗ GSx T t=1 in probability. Proof of Lemma B.15. Conditional on the data, the summands ξt∗ ψtS (x) are independent and centered. The martingale law of large numbers and the Markov ergodic theorem give convergence to the covariance matrix in Lemma B.10: T

1X S p ψt (x)ψtS (x)T → − ΩSx . T t=1

Moreover, boundedness of ψtS (x) and the (2 + δ)-moment bound for ξt∗ imply the conditional Lindeberg condition. The conditional multivariate Lindeberg–Feller theorem therefore yields T

1 X ∗ S √ ξt ψt (x) ⇒∗ GSx , T t=1

GSx ∼ N|S|k (0, ΩSx ),

in probability. Lemma B.16 (Conditional stochastic equicontinuity near a selected threshold). For the neighborhoods Uj in Lemma B.11, every s ∈ S, j = 1, . . . , k, and every ε, η > 0, 



  lim lim sup P P∗  sup δ↓0

T →∞

z∈Uj |z−xj |≤δ

 √



  T {Fη̄T∗ (s) (z) − F̄T,s (z)} − {Fη̄T∗ (s) (xj ) − F̄T,s (xj )} > ε > η  = 0.

Proof of Lemma B.16. Fix s and j, and abbreviate x = xj , U = Uj , and ψz,t = ψs,z,t . Conditional

52

on the data, 2

T

1 X ∗ E∗ √ ξt ψz,t − ψz ′ ,t T t=1

T

1X 2 = ψz,t − ψz ′ ,t ≤ C z − z ′ , T t=1

where the last inequality holds pathwise by (42). The multiplier restriction makes ξt∗ uniformly bounded. Hence the same Bernstein and dyadic-union calculation as in the sampling proof gives, for every u ≥ 1, P∗

 ! T √ √ 1+u 1 X ∗ 1+u+ √ ≤ Ce−u sup √ ξt {ψz,t − ψx,t } > C δ T t=1 T z∈Iδ

for every realized data path, with deterministic constants independent of that path. Taking T → ∞, then choosing u large and letting δ ↓ 0, therefore implies, for every ε, η > 0, 



  lim lim sup P P∗  sup δ↓0

T →∞

z∈U |z−x|≤δ

  T X 1   √ ξt∗ (ψz,t − ψx,t ) > ε > η  = 0. T t=1

(46)

Combining (46) with Lemma B.14, which holds for every deterministic rT ↓ 0, gives the asserted conditional stochastic equicontinuity by the subsequence characterization. The maximum over s ∈ S and j = 1, . . . , k preserves the conclusion. Proof of Theorem 5. For every s ∈ S and j = 1, . . . , k, Lemma B.14, evaluated at z = xj , gives T √ 1 X ∗ T {Fη̄T∗ (s) (xj ) − F̄T,s (xj )} = √ ξt ψs,xj ,t + op∗ (1) T t=1

in probability. Stacking the coordinates yields √

 T {Fη̄T∗ (s) (xj ) − F̄T,s (xj )}

T

1 X ∗ S =√ ξt ψt (x) + op∗ (1) s∈S, 1≤j≤k T t=1

in R|S|k ,

in probability. Lemma B.15 gives conditional weak convergence of the leading sum to GSx . The conditional Slutsky theorem shows that the remainder does not change this limit, proving √

 T {Fη̄T∗ (s) (xj ) − F̄T,s (xj )}

in P-probability. 53

s∈S, 1≤j≤k

⇒∗ GSx

√ Lemma B.16, evaluated on |z − xj | ≤ M/ T , makes the centered bootstrap CDF fluctuation locally constant. Theorem 4 supplies the componentwise sampling drift. A data-measurable op (1) remainder is also op∗ (1) in probability. Combining these facts yields sup h∈[−M,M ]|S|k

F∗T,x (h) −

√

 T {Fη̄T∗ (s) (xj ) − F̄T,s (xj )}

s∈S, 1≤j≤k

− fxS ⊙ h

= op∗ (1)

(47)

∞

in probability. The conditional weak convergence of the fixed-threshold vector established above and the conditional Slutsky theorem prove the stated local-process convergence. Proof of Corollary 1. Fix M < ∞. On the event maxs,j ∆∗s,j,T ≤ M , substitute h = ∆∗T into (47). Conditional tightness of ∆∗T permits M → ∞, which gives the asserted expansion.

B.3

Proofs for Section 4.3

Lemma B.17 (Uniform CDF errors on shrinking parameter neighborhoods). Let rT ↓ 0 be deterministic and set BT = {θ : ∥θ − θ0 ∥ ≤ rT }. Then √ max sup

T F̄T,sj (gj (θ)) − Fsj (gj (θ)) = Op (1),

max sup

√ ∗ T F̄T,s (gj (θ)) − Fsj (gj (θ)) = Op∗ (1) j

1≤j≤J θ∈BT

and 1≤j≤J θ∈BT

in probability. Proof. Continuous differentiability of the finitely many gj ’s gives a constant Cg such that, on BT , max |gj (θ) − xj | ≤ Cg rT . j

Define √ ωT (r) = max

sup

1≤j≤J |z−xj |≤Cg r

T {F̄T,sj (z) − Fsj (z)} − {F̄T,sj (xj ) − Fsj (xj )} .

Lemma B.11 and the subsequence characterization of stochastic equicontinuity imply ωT (rT ) = op (1). The fixed-threshold conclusion of Theorem 4 therefore gives the first assertion. For the bootstrap, define ωT∗ (r) = max

√ sup

1≤j≤J |z−xj |≤Cg r

∗ ∗ T {F̄T,s (z) − F̄T,sj (z)} − {F̄T,s (xj ) − F̄T,sj (xj )} . j j

54

∗ − Fsj into its sampling and Lemma B.16 gives ωT∗ (rT ) = op∗ (1) in probability. Decomposing F̄T,s j

bootstrap parts, and using the fixed-threshold conclusions of Theorems 4 and 5, proves the second assertion. Proof of Theorem 6. The chain rule gives DH(θ0 ) = B. Since B is nonsingular, the inverse function theorem yields a neighborhood N of θ0 and a constant c > 0 such that ∥H(θ)∥ ≥ c ∥θ − θ0 ∥ ,

θ ∈ N.

(48)

Local consistency permits a deterministic sequence rT ↓ 0 such that BT = {θ : ∥θ − θ0 ∥ ≤ rT } ⊂ N contains θ̂T with probability tending to one and θ̂T∗ with conditional probability tending to one in probability. On these events, Lemma B.17, the local Lipschitz continuity of M , and the two estimating equations give c θ̂T − θ0 ≤ H(θ̂T ) − HT (θ̂T ) = Op (T −1/2 ) and c θ̂T∗ − θ0 ≤ H(θ̂T∗ ) − HT∗ (θ̂T∗ ) = Op∗ (T −1/2 ) in probability. Thus both estimators have the required root-T localization. √ Put dT = T (θ̂T − θ0 ). Continuous differentiability of gj gives √ ∆j,T :=

T {gj (θ̂T ) − xj } = ∇gj (θ0 )T dT + op (1) = Op (1).

(49)

The random-threshold expansion in Theorem 4 therefore yields o √ √ n T F̄T,sj (gj (θ̂T )) − Fsj (xj ) = T {F̄T,sj (xj ) − Fsj (xj )} + fsj (xj )∇gj (θ0 )T dT + op (1)

(50)

jointly over j = 1, . . . , J. Expand the estimating equation around (θ0 , Fs1 (x1 ), . . . , FsJ (xJ )). Equations (49)–(50) and continuous differentiability of M give √

  T M θ̂T , F̄T,s1 (g1 (θ̂T )), . . . , F̄T,sJ (gJ (θ̂T )) √  = BdT + Mu T {F̄T,sj (xj ) − Fsj (xj )} + op (1).

0=

1≤j≤J

55

(51)

Bounded invertibility of B gives √

T (θ̂T − θ0 ) = −B −1 Mu

√

 T {F̄T,sj (xj ) − Fsj (xj )}

1≤j≤J

+ op (1).

The sampling limit follows from Theorem 4 and the continuous mapping theorem. √ For the bootstrap conclusion, put d∗T = T (θ̂T∗ − θ0 ). The root-T localization established above gives d∗T = Op∗ (1) in probability, and hence ∆∗j,T :=

√

T {gj (θ̂T∗ ) − xj } = ∇gj (θ0 )T d∗T + op∗ (1) = Op∗ (1)

in probability. The random-threshold expansions in Theorem 4 and Corollary 1 give o √ √ √ n ∗ ∗ T F̄T,sj (gj (θ̂T∗ )) − Fsj (xj ) = T {F̄T,sj (xj ) − Fsj (xj )} + T {F̄T,s (xj ) − F̄T,sj (xj )} j + fsj (xj )∇gj (θ0 )T d∗T + op∗ (1)

(52)

jointly over j, in probability. Taylor expansion of the bootstrap estimating equation now gives 0 = Bd∗T + Mu



√

 T {F̄T,sj (xj ) − Fsj (xj )}

1≤j≤J

+

√





∗ T {F̄T,s (xj ) − F̄T,sj (xj )} j

1≤j≤J

+ op∗ (1) (53)

in probability. Subtracting (51) from (53), and observing that a data-measurable op (1) remainder is op∗ (1) in probability, yields √

T (θ̂T∗ − θ̂T ) = −B −1 Mu

√

 ∗ T {F̄T,s (x )} (x ) − F̄ j j T,s j j

1≤j≤J

+ op∗ (1).

Theorem 5 now gives √

T (θ̂T∗ − θ̂T ) ⇒∗ −B −1 Mu Gx

in probability. Lemma B.18 (Root-T localization of generalized quantiles). Fix a state s and τ ∈ (0, 1), and define qτ,s = inf{x : Fs (x) ≥ τ },

q̂T,τ,s = inf{x : F̄T,s (x) ≥ τ },

56

∗ ∗ q̂T,τ,s = inf{x : F̄T,s (x) ≥ τ }.

Suppose that qτ,s ∈ (0, (1 − γ)−1 ) and that fs is continuous near qτ,s , with fs (qτ,s ) > 0. Include qτ,s among the selected evaluation points. Then √

√

T (q̂T,τ,s − qτ,s ) = Op (1),

∗ T (q̂T,τ,s − qτ,s ) = Op∗ (1)

in probability.

Proof. Continuity of fs and positivity of fs (qτ,s ) imply Fs (qτ,s ) = τ and, for every sufficiently small ε > 0, Fs (qτ,s − ε) < τ < Fs (qτ,s + ε). Theorem 1 and the interpolation inequality (28) give F̄T,s − Fs ∞ = op (1). p

The strict local crossing displayed in the lemma therefore implies q̂T,τ,s → − qτ,s . The same argument, ∗ using Theorem 2 and the triangle inequality around Fs , gives q̂T,τ,s − qτ,s = op∗ (1) in probability.

We next sharpen consistency to root-T localization. For any fixed M > 0, monotonicity of F̄T,s gives n√ o n o √ P T (q̂T,τ,s − qτ,s ) > M ≤ P F̄T,s (qτ,s + M/ T ) < τ , n√ o n o √ P T (q̂T,τ,s − qτ,s ) < −M ≤ P F̄T,s (qτ,s − M/ T ) ≥ τ . Theorem 4 expands the centered quantities on the right as

√

T {F̄T,s (qτ,s ) − Fs (qτ,s )} ± fs (qτ,s )M +

op (1). Tightness of the fixed-threshold centered CDF error, followed by M → ∞, proves √ ∆T,s :=

T (q̂T,τ,s − qτ,s ) = Op (1).

∗ , together with Corollary 1 and tightness of The identical inequalities for F̄T,s

√

∗ (q )−F (q )}, T {F̄T,s τ,s s τ,s

give ∆∗T,s :=

√

∗ T (q̂T,τ,s − qτ,s ) = Op∗ (1)

in probability. Lemma B.19 (Vanishing overshoot at generalized quantiles). Under the conditions of Lemma B.18, √

√

T {F̄T,s (q̂T,τ,s ) − τ } = op (1),

57

∗ ∗ T {F̄T,s (q̂T,τ,s ) − τ } = op∗ (1)

in probability. Proof. For a function G with left limits, write JG (z) = G(z) − G(z−). Fix M < ∞ and define √ ωT,M =

sup

√ √ T {F̄T,s (qτ,s + h/ T ) − Fs (qτ,s + h/ T )} − {F̄T,s (qτ,s ) − Fs (qτ,s )} ,

|h|≤M +1

with left limits included by taking increasing sequences of h’s. The stochastic-equicontinuity bound in Theorem 4 gives ωT,M = op (1). By the defining inequalities of a generalized inverse, F̄T,s (q̂T,τ,s −) ≤ τ ≤ F̄T,s (q̂T,τ,s ). On {|∆T,s | ≤ M }, the continuity of Fs and the preceding modulus therefore give 0≤ ≤

√ √

T {F̄T,s (q̂T,τ,s ) − τ } T JF̄T,s (q̂T,τ,s ) ≤ 2ωT,M = op (1).

Letting M → ∞ proves the sampling overshoot assertion. For the bootstrap generalized inverse, define ∗ ωT,M =

√ sup |h|≤M +1

√ √ ∗ ∗ T {F̄T,s (qτ,s + h/ T ) − F̄T,s (qτ,s + h/ T )} − {F̄T,s (qτ,s ) − F̄T,s (qτ,s )} .

∗ Corollary 1 gives ωT,M = op∗ (1) in probability. On {|∆∗T,s | ≤ M },

0≤

√

∗ ∗ T {F̄T,s (q̂T,τ,s ) − τ}

√

∗ T JF̄ ∗ (q̂T,τ,s ) T,s √ √ ∗ ∗ = T JF̄ ∗ −F̄T,s (q̂T,τ,s ) + T JF̄T,s (q̂T,τ,s )

≤

T,s

∗ ≤ 2ωT,M + 2ωT,M = op∗ (1)

in probability. Letting M → ∞ proves the bootstrap overshoot assertion. √

T (q̂T,τ,s − qτ,s ). Lemmas B.18 and B.19 give ∆T,s = Op (1) and √ a negligible sampling overshoot. Theorem 4, evaluated at qτ,s + ∆T,s / T = q̂T,τ,s , therefore gives Proof of Example 6. Put ∆T,s =

√ op (1) =

T {F̄T,s (q̂T,τ,s ) − τ } =

√

T {F̄T,s (qτ,s ) − Fs (qτ,s )} + fs (qτ,s )∆T,s + op (1).

58

Solving for ∆T,s proves the sampling representation, and Theorem 4 gives its Gaussian limit. √ ∗ For the bootstrap, let ∆∗T,s = T (q̂T,τ,s −qτ,s ). Lemmas B.18 and B.19, together with Corollary 1, give √ op∗ (1) =

∗ ∗ T {F̄T,s (q̂T,τ,s ) − τ} =

√

∗ T {F̄T,s (qτ,s ) − Fs (qτ,s )} + fs (qτ,s )∆∗T,s + op∗ (1)

in probability. Subtracting the sampling expansion and using ∆∗T,s − ∆T,s =

√

∗ T (q̂T,τ,s − q̂T,τ,s )

gives the bootstrap representation. Theorem 5 gives the conditional weak limit.

References [1] M. G. Bellemare, W. Dabney, and R. Munos. A distributional perspective on reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, pages 449–458, 2017. [2] M. G. Bellemare, W. Dabney, and M. Rowland. Distributional Reinforcement Learning. MIT Press, 2023. [3] M. Böck and C. Heitzinger. Speedy categorical distributional reinforcement learning and complexity analysis. SIAM Journal on Mathematics of Data Science, 4(2):675–693, 2022. doi: 10.1137/20M1364436. [4] Y. Chandak, S. Niekum, B. da Silva, E. Learned-Miller, E. Brunskill, and P. S. Thomas. Universal off-policy evaluation. In Advances in Neural Information Processing Systems, volume 34, pages 27475–27490, 2021. [5] A. Huang, L. Leqi, Z. C. Lipton, and K. Azizzadenesheli. Off-policy risk assessment for markov decision processes. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151, pages 5022–5050, 2022. [6] K. Jin, Y. Peng, J. Yang, and Z. Zhang. Accelerated distributional temporal difference learning with linear function approximation. arXiv preprint arXiv:2511.12688, 2025.

59

[7] E. C. Kaya and A. Hashemi. A finite-iteration theory for asynchronous categorical distributional temporal-difference learning. arXiv preprint arXiv:2605.06866, 2026. [8] T. Morimura, M. Sugiyama, H. Kashima, H. Hachiya, and T. Tanaka. Nonparametric return distribution approximation for reinforcement learning. In Proceedings of the 27th International Conference on Machine Learning, pages 799–806, 2010. [9] Y. Peng, L. Zhang, and Z. Zhang. Statistical efficiency of distributional temporal difference learning. In Advances in Neural Information Processing Systems, volume 37, pages 24724–24761, 2024. doi: 10.52202/079017-0779. [10] Y. Peng, K. Jin, L. Zhang, and Z. Zhang. A finite sample analysis of distributional td learning with linear function approximation. In Advances in Neural Information Processing Systems, volume 38, 2025. [11] B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992. [12] P. Ramprasad, Y. Li, Z. Yang, Z. Wang, W. W. Sun, and G. Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. Journal of the American Statistical Association, 118(544):2901–2914, 2023. doi: 10.1080/01621459.2022.2096620. [13] M. Rowland, M. G. Bellemare, W. Dabney, R. Munos, and Y. W. Teh. An analysis of categorical distributional reinforcement learning. In Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, pages 29–37, 2018. [14] M. Rowland, R. Munos, M. G. Azar, Y. Tang, G. Ostrovski, A. Harutyunyan, K. Tuyls, M. G. Bellemare, and W. Dabney. An analysis of quantile temporal-difference learning. Journal of Machine Learning Research, 25(163):1–47, 2024. [15] M. Rowland, L. K. Wenliang, R. Munos, C. Lyle, Y. Tang, and W. Dabney. Near-minimaxoptimal distributional reinforcement learning with a generative model. In Advances in Neural Information Processing Systems, volume 37, pages 132774–132823, 2024. doi: 10.52202/ 079017-4221. [16] W. Rudin. Functional Analysis. McGraw–Hill, 2 edition, 1991.

60

[17] D. Ruppert. Efficient estimations from a slowly convergent robbins–monro process. Technical report, Cornell University, Operations Research and Industrial Engineering, 1988. [18] R. S. Sutton. Learning to predict by the methods of temporal differences. Machine Learning, 3:9–44, 1988. [19] R. Wu, M. Uehara, and W. Sun. Distributional offline policy evaluation with predictive error guarantees. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 37685–37712, 2023. [20] W. Wu, G. Li, Y. Wei, and A. Rinaldo. Statistical inference for policy evaluation with temporal difference learning. arXiv preprint arXiv:2410.16106, 2024. [21] W. Wu, Y. Wei, and A. Rinaldo. Uncertainty quantification for markov chain induced martingales with application to temporal difference learning. arXiv preprint arXiv:2502.13822, 2025. [22] M. Zeng, Y. Zhang, and X. Shao. Self-normalized inference for constant-stepsize temporaldifference learning under markovian sampling. arXiv preprint arXiv:2608.10896, 2026. [23] L. Zhang, Y. Peng, J. Liang, W. Yang, and Z. Zhang. Estimation and inference in distributional reinforcement learning. The Annals of Statistics, 53(5):1987–2011, 2025.

61

Related documents

• Amortizing intractable inference in large language models#798540
• Amortizing intractable inference in large language models#797127
• From Scores to Samples: Elastic Forcing for Autoregressive Video Generation#1144872
• Frame Differential On-Policy Self-Distillation for Video Reasoning#1143988
• Nested Inductive Bias Framework for SPD Manifold Learning#927754