PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Inference in Distributional Temporal-Difference Learning

Yang Peng, Liangyu Zhang

arXiv:2608.14408v1stat.MLcs.LG

TL;DR

Policy evaluation requires inference on return-distribution features beyond expected returns, but online methods from a single trajectory need theoretical guarantees. This paper develops nonparametric distributional TD inference and proves Gaussian and bootstrap limits for smooth functionals, alongside local CDF theory for nonsmooth targets.

  • Problem

    Online inference for return-distribution functionals from a single Markov trajectory remains underdeveloped despite policy-relevant differences in variability, downside risk, and adverse-outcome probabilities.

  • Method

    The paper uses nonparametric distributional temporal-difference learning, analyzing smooth functionals and local CDF behavior near finitely many thresholds.

  • Results

    The averaged estimator and its conditional bootstrap difference converge weakly to the same Gaussian limit, while local CDF expansions yield sampling and bootstrap limits for nonsmooth targets.

  • Takeaways & Limitations

    The theory supports online bootstrap inference for return-distribution functionals, including smooth targets and nonsmooth functionals defined by CDF equations.

  • Takeaways & Limitations

    The main-text analysis assumes rewards are bounded and normalized, so discounted returns lie in a bounded interval.

Abstract

from arXiv · show

We study online statistical inference for functionals of the return distribution under a fixed 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

The paper develops online inference for statistical functionals of return distributions estimated by nonparametric distributional TD from a single Markov trajectory. It establishes Gaussian and bootstrap limits for smooth functionals and local CDF theories for nonsmooth functionals defined by CDF equations.

  • 1 Introduction: Policies with similar expected returns can differ substantially in variability, downside risk, and adverse-outcome probabilities, motivating functionals beyond the mean.These features are described by statistical functionals of the return distribution.
  • 1 Introduction: The paper studies online inference for return-distribution functionals using nonparametric distributional TD from a single Markov trajectory.The targets include variance, CVaR, expected shortfall, expectiles, quantiles, and parameters defined by CDF equations.
  • 1 Introduction: For the Polyak–Ruppert average, the root-T estimation error converges weakly to a centered Gaussian random element in Cramér space.The multiplier bootstrap applies the same recursion with the step size multiplied by an independent multiplier.
  • 1 Introduction: Conditionally on the observed trajectory, the root-T difference between bootstrap and original averages converges weakly to the same Gaussian limit, supporting inference for smooth functionals.The results apply to functionals such as variance, CVaR, expected shortfall, and expectiles.
  • 1 Introduction: For nonsmooth functionals characterized by CDF equations, the paper establishes sampling and bootstrap local CDF expansions over T^-1/2-neighborhoods of relevant thresholds.These expansions yield corresponding sampling and bootstrap limits for targets including return quantiles.

2 Preliminaries

The paper studies a fixed-policy discounted tabular MDP with bounded rewards and return distributions represented as the unique fixed point of a Bellman operator. It estimates this distribution nonparametrically from a single trajectory using distributional TD, Polyak–Ruppert averaging, and bootstrap iterates.

  • Model and assumptions: The setting is a discounted tabular MDP with finite state and action spaces, fixed policy π, and an irreducible, aperiodic induced Markov chain.The chain is geometrically ergodic and has a unique stationary distribution with positive mass on every state.
  • Model and assumptions: Rewards satisfy 0 ≤ R_t ≤ 1 almost surely, so every discounted return lies in [0, (1 − γ)^−1], without requiring finite reward support.Conditional reward distributions may be discrete, continuous, or mixed.
  • Return distributions: For policy π, η^π is the vector of state-conditional discounted return distributions, with CDFs F_s and value function V^π given by the first moments.The paper targets the full return-distribution vector rather than only its expected values.
  • Return distributions: The distributional Bellman operator maps each state distribution to the expected discounted reward-shifted successor distribution, and η^π is its unique fixed point.The operator is a √γ-contraction in the supremum Cramér metric.
  • Bootstrap procedure: Bootstrap replicates reuse each observed transition while multiplying the distributional TD step size by independent bootstrap weights, with inference conditioned on the observed trajectory.Under the conditional law, the trajectory is fixed and only the bootstrap randomness varies.

3 Inference for smooth functionals

This section develops asymptotic theory for the Polyak–Ruppert averaged distributional TD estimator in Cramér space and applies it to inference for smooth functionals. It uses a zero-mass signed-measure formulation, establishes Gaussian and bootstrap limits, and transfers them to several smooth functionals.

  • Cramér-space formulation: The analysis represents distributional TD errors as zero-mass signed measures in Cramér space and derives the recursion for Polyak–Ruppert averaging.The framework uses finite signed measures supported on [0, (1 −γ)−1] with total mass zero, equipped with the Cramér inner product.
  • Asymptotic theory: The Polyak–Ruppert averaged estimator admits an asymptotic linear representation and converges to a Gaussian limit.The estimator is analyzed in the Hilbert completion of the zero-mass signed-measure space.
  • Bootstrap inference: The online multiplier bootstrap consistently reproduces the Gaussian limit of the averaged estimator.This establishes the basis for conditional bootstrap inference from the observed trajectory.
  • Smooth functionals: The functional delta method transfers the Gaussian and bootstrap limits to inference for means, variances, CVaR, expected shortfall, and expectiles.These are the smooth statistical functionals covered in the section.

Appendix A. We let T π and T π

Appendix A derives an asymptotic linear representation for the Polyak–Ruppert average and proves its centered Gaussian limit in Cramér space. It also establishes conditional bootstrap validity and transfers the limit to smooth functionals of the return distribution.

  • Asymptotic distribution: The Polyak–Ruppert average admits an asymptotic linear representation, with the remaining recursion terms asymptotically negligible.The proof obtains this representation by summing the error recursion, controlling endpoint and remainder terms, and applying A^-1.
  • Asymptotic distribution: The normalized estimation error converges weakly in H to a centered Gaussian random element G with covariance operator A^-1Σ(A^-1)*.The Gaussian limit follows from a Hilbert-space martingale central limit theorem applied to the leading martingale-difference term.
  • Bootstrap validity: The online multiplier bootstrap conditionally reproduces the same Gaussian limit G for the normalized bootstrap error, assuming α1 ≤ 1/2.The conditional convergence holds in P-probability and is established through finite-dimensional conditional limits, tail control, and a negligible remainder.
  • Inference for smooth functionals: Hadamard-differentiable functionals of the return distribution inherit Gaussian sampling and bootstrap limits through their continuous linear derivative.The result applies to smooth functionals in the Cramér geometry, including mean, variance, CVaR, expected shortfall, and expectiles.

4 Inference for nonsmooth functionals

This section develops local asymptotic theory for estimated return CDFs around finitely many thresholds and establishes bootstrap validity for these local processes. The results support inference for nonsmooth CDF-defined functionals, including return quantiles.

  • Local return-CDF asymptotics: Local CDF processes over T^-1/2-neighborhoods of finitely many thresholds converge weakly to Gaussian processes with deterministic linear drift.Theorem 4 establishes this convergence when 3/5 < κ < 3/4, in the product supremum norm.
  • Motivation: The local analysis addresses quantiles because their first-order expansions require CDF errors at unknown thresholds, where point evaluation is discontinuous in the Cramér norm.This extends inference beyond the smooth-functional theory of Section 3.
  • Bootstrap validity: The bootstrap local CDF process converges conditionally to the same centered Gaussian limit as the original local process.The bootstrap result is established under the conditions of Theorem 4 and Theorem 5.
  • CDF-defined functionals: A random-index bootstrap expansion preserves local validity at perturbations that are Op*(1), enabling inference for finite-dimensional functionals characterized by CDF equations.The resulting framework includes return quantiles among the nonsmooth statistical functionals considered.

A Proofs for Section 3 · A.1 Proofs for Section 3.1

The proofs establish the separable Hilbert-space framework, martingale structure, operator coercivity, and Poisson-equation tools underpinning Section 3. They rely on finite-state geometric ergodicity and the fixed-policy MDP transition structure.

  • A.1 Proofs for Section 3.1: The Cramér space is separable because its CDF embedding is an isometry into a closed subspace of separable L2, and the finite-state product space remains separable.The embedding maps measures to CDFs on [0, (1 −γ)−1].
  • A.1 Proofs for Section 3.1: The filtration is defined so that Ft−1 contains the trajectory through St, while the current transition is generated conditionally from the fixed policy and MDP kernel.This filtration supports the martingale arguments used in the proofs.
  • A.1 Proofs for Section 3.1: The Bellman residual sequence is a bounded H-valued martingale difference, with et and At uniformly bounded and A boundedly invertible.The martingale-difference property follows by conditioning the Bellman fixed-point equation on Ft−1.
  • A.1 Proofs for Section 3.1: The operator A is invertible because I − Tπ admits a Neumann-series inverse, yielding coercivity with c0 = (1 −√γ) mins µπ(s) > 0.The argument uses bounded returns, the step-size restriction, Jensen’s inequality, and an affine pushforward change of variables.
  • A.1 Proofs for Section 3.1: For bounded operator-valued B on the finite state space, the operator Poisson equation has a bounded stationary-mean-zero solution.The solution is constructed through a uniformly convergent series under geometric ergodicity.
  • A.1 Proofs for Section 3.1: Finite-state geometric ergodicity ensures uniform convergence of the Poisson-series representation, while telescoping verifies the equation.The normalization and uniqueness follow by averaging and geometric ergodicity.

A.2 Proofs for Section 3.2

The proofs establish mean-square stability, negligible Polyak–Ruppert remainder terms, and a Hilbert-space central limit theorem for Bellman residuals, yielding Theorem 1’s centered Gaussian limit.

  • Stability and averaging: Lemma A.3 proves a last-iterate mean-square bound of order O(α_t) using a corrected Lyapunov recursion and coercivity.The expectation recursion is v_t ≤ (1 − cα_t)v_{t−1} + Cα_t^2, which implies v_t ≤ Cα_t.
  • Stability and averaging: Lemma A.4 shows that both remainder terms in the Polyak–Ruppert representation are o_p(1) after normalization.The first follows from endpoint and sum bounds of O_p(T^(κ−1)/2) = o_p(1), while the second uses martingale differences and telescoping bounds.
  • Bellman-residual CLT: Lemma A.5 proves a Hilbert-space CLT for normalized Bellman residuals through finite-dimensional projections, automatic conditional Lindeberg control, and tightness.Projection-tail trace convergence establishes tightness in H, and every finite-dimensional projection converges to the corresponding projection of N_H(0, Σ).
  • Theorem 1: Combining the linear representation with Lemmas A.4–A.5 proves Theorem 1’s centered Gaussian limit with covariance A^−1Σ(A^−1)∗.The remainder sums are o_p(1) after normalization, and the residual CLT supplies the Gaussian limit.

A.3 Proofs for Section 3.3

The proofs establish mean-square control and a Polyak–Ruppert expansion for the bootstrap estimator. A conditional Gaussian limit for the leading multiplier sum then yields the bootstrap weak convergence in Theorem 2.

  • Bootstrap last iterate: Lemma A.6 bounds the bootstrap last-iterate error using a Lyapunov–Poisson argument whose first-order drift is unchanged by the multiplier.The multiplier enters only a uniformly bounded second-order term, while coercivity controls the resulting recursion.
  • Bootstrap Polyak–Ruppert expansion: Lemma A.7 decomposes the averaged bootstrap error into a leading multiplier sum plus a remainder that is op∗(1) in P-probability.Endpoint, step-size, operator, state-selection, telescoping, and martingale terms are shown negligible through summation and moment bounds.
  • Conditional Gaussian limit: Lemma A.8 proves conditional weak convergence of the leading multiplier sum to a Gaussian limit using covariance convergence, Lindeberg–Feller, and conditional tightness.Projection tails vanish through trace control, establishing convergence for almost every observed trajectory.
  • Theorem 2: Theorem 2 follows because bounded invertibility transfers the expansion to the averaged estimator, while the conditionally negligible remainder preserves the Gaussian limit.The resulting convergence is T ⇒∗G in H, in P-probability.

A.4 Proofs for Section 3.4 · B Proofs for Section 4

The proofs establish asymptotic inference for smooth functionals by combining Hadamard differentiability with Gaussian convergence, and extend the argument to bootstrap and joint-functional conclusions. They also derive confidence-interval coverage from bootstrap quantile convergence.

  • A.4 Proofs for Section 3.4: Theorem 1 yields tightness of Z_T in H and the rate ||θ_T − θ_0||_H = O_p(T^-1/2).This rate supports the subsequent functional expansion.
  • A.4 Proofs for Section 3.4: Continuity and linearity of the derivative, together with Theorem 1 and the continuous mapping theorem, establish the functional limit.Subtracting the expansions uses linearity and a conditionally negligible remainder.
  • A.4 Proofs for Section 3.4: For finitely many functionals, stacking the maps and derivatives yields the corresponding joint conclusion.The same construction produces a single Euclidean-valued map for the joint analysis.
  • A.4 Proofs for Section 3.4: The bootstrap proof obtains conditional weak convergence in probability and unconditional weak convergence of Z_T* to G.The unconditional result follows from bounded conditional expectations and convergence in L1.
  • A.4 Proofs for Section 3.4: Hadamard differentiability tangentially to H provides a uniform expansion over compact sets of directions.The proof applies this expansion to tight random directions with arbitrarily high probability.
  • A.4 Proofs for Section 3.4: When d = 1 and the Gaussian limit is nondegenerate, bootstrap quantile convergence combined with sampling convergence proves the stated confidence-interval coverage.The argument uses continuity and strict increase of the Gaussian limit distribution function.

B.1 Proofs for Section 4.1

The proofs establish density and Lipschitz regularity for exact and bootstrap TD iterates, then control interpolation, operator, martingale, and remainder terms needed for the pointwise Polyak–Ruppert expansion.

  • Density and CDF regularity: Exact and bootstrap TD iterates have densities, implying Lipschitz CDFs with a common deterministic growth bound.The bootstrap statement holds almost surely under the joint data–multiplier law.
  • CDF interpolation: An interpolation inequality converts sup-norm CDF discrepancies into integrated squared discrepancies for supported CDFs with Lipschitz extensions.The proof uses monotonicity and local intervals where the CDF gap remains at least half its value.
  • Martingale control: A deterministic-grid martingale bound provides uniform control over compact threshold neighborhoods, with a conditional analogue in probability.The argument combines grid discretization, interpolation, Freedman’s inequality, and a union bound.
  • Operator bounds: Bellman, conditional, averaging, and truncated operators preserve bounded Lipschitz cumulative functions under explicit operator bounds.Affine pullbacks multiply Lipschitz constants by at most γ^-1, while conditioning and finite-state averaging add only fixed factors; (Tπ)^q contributes γ^-q.
  • Polyak–Ruppert expansion: These bounds yield the pointwise Polyak–Ruppert expansion under a vanishing neighborhood radius rT.Lemma B.9 states the expansion after summing the recursion and removing the step-size remainders.

B.2 Proofs for Section 4.2

The proofs establish negligible bootstrap remainders and derive a uniform pointwise expansion near thresholds. Conditional multiplier central limit and stochastic equicontinuity arguments then yield the bootstrap local-process convergence used in Theorem 5.

  • Bootstrap remainder bounds: The deterministic grid has size ℓ_T = O(T^(1−κ)), controlling the uniform approximation over threshold neighborhoods.This follows from the martingale-array envelope and Lipschitz bounds used in Lemma B.4.
  • Bootstrap remainder bounds: Both joint bootstrap remainder bounds are op*(1) in probability under the joint law.The (A − A_t)δ_{t−1} remainder contributes O_p((log T){T^−1/2 + T^(1/2−κ)}), while q_T = O(log T).
  • Pointwise bootstrap expansion: Lemma B.14 gives a pointwise bootstrap Polyak–Ruppert expansion uniformly over thresholds z in shrinking neighborhoods U_T.The four remainder terms are removed, leaving a leading T^−1/2 partial-sum term.
  • Conditional limit theory: The conditional multiplier central limit theorem yields convergence of the centered bootstrap leading sum to the covariance limit from Lemma B.10.Conditional independence, centering, covariance convergence, and the Lindeberg condition support the multivariate Lindeberg–Feller argument.
  • Conditional limit theory: Conditional stochastic equicontinuity holds around selected thresholds, and combining it with Lemmas B.14–B.15 proves the stated local-process convergence.The conclusion remains valid after taking the maximum over all states s and thresholds j.

B.3 Proofs for Section 4.3

The proofs establish uniform CDF control on shrinking neighborhoods, root-T localization for estimating-equation solutions and generalized quantiles, and sampling and bootstrap representations with Gaussian limits. They also show that generalized-quantile overshoots vanish under continuity and positive-density conditions.

  • Uniform CDF control: Uniform CDF errors on shrinking parameter neighborhoods follow from stochastic equicontinuity and fixed-threshold results for the sampling and bootstrap estimators.Continuous differentiability controls neighborhood variation, while Lemma B.11 and Theorems 4–5 supply the required fixed-threshold conclusions.
  • Theorem 6: Both sampling and bootstrap estimating-equation solutions achieve the required root-T localization by local consistency, local Lipschitz continuity, and bounded invertibility.The inverse function theorem provides a neighborhood around θ0, and Taylor expansions of the estimating equations yield the localization and subsequent representations.
  • Generalized quantiles: Generalized quantile estimators are root-T localized when the target quantile is an included evaluation point and the return density is continuous and positive there.The assumptions require qτ,s ∈ (0, (1 −γ)−1), continuity of fs near qτ,s, and fs(qτ,s) > 0.
  • Generalized quantiles: Under the generalized-quantile conditions, sampling and bootstrap overshoots vanish, enabling quantile representations and their respective Gaussian and conditional weak limits.The argument combines monotonicity, stochastic equicontinuity, negligible overshoots, and Theorems 4–5.
Loading 2608.14408v1…