Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling

This paper develops inferential methods for constant-stepsize temporal-difference (TD) learning under Markovian sampling, addressing two key challenges: serial dependence in the data and the stepsize-dependent stationary target.

The paper establishes a functional central limit theorem (FCLT) for fixed-stepsize linear TD, where the covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error. It then derives a joint functional limit for parallel Richardson–Romberg (RR) recursions driven by the same trajectory. A Brownian-bridge self-normalizer yields asymptotically pivotal confidence regions for prespecified state-value contrasts without estimating the long-run covariance or selecting a bandwidth or batch length. For such a contrast, the procedure admits a one-pass implementation whose memory does not grow with the trajectory length.

At a fixed stepsize, the inferential center is the RR stationary target. The paper also studies horizon-indexed designs in which the stepsize remains constant within each run and decreases across longer horizons. Under an explicit RR-dependent rate window, the residual RR target shift, multiplicative remainder, and initialization effect are negligible at the root-n scale, yielding inference for the projected Bellman solution.

The paper makes three contributions:

• (C1) Fixed-stepsize path theory for linear TD under Markov sampling, with block-forgetting and pullback results constructing the stationary recursion (Theorems 1 and 2), and an augmented-chain decomposition yielding its FCLT (Proposition 3; Theorem 4).

• (C2) Self-normalized inference for same-trajectory RR recursions, with a joint FCLT preserving cross-level dependence and a Brownian-bridge self-normalizer yielding confidence regions for the RR stationary target without long-run covariance estimation or bandwidth/batch-length selection. For a prespecified contrast, the computation is online and one-pass, with memory independent of the trajectory length (Theorem 5; Corollary 6).

• (C3) A horizon-indexed regime in which the leading stochastic input becomes additive and the residual RR target shift is negligible at the root-n scale, yielding self-normalized inference for the projected Bellman solution over an explicit RR-dependent exponent window (Theorem 7 and Corollary 8).

The paper's organizing decomposition is:

ϑ̄n − θ∗ = ϑ̄n − θRR,α + θRR,α − θ∗,

where the first term is sampling fluctuation around the RR stationary target, and the second is the residual RR target shift.

Key theoretical results include:

• Theorem 1 (Lyapunov block contraction): For every fixed p > 2, the problem-dependent threshold αstab,p > 0 and constants cp, Cp can be chosen so that for every 0 < α ≤ αstab,p, t ≥ 0, starting state Y0 = y, and deterministic u ∈ Rd, Ey ∥Πα1:t u∥p ≤ Cp e−cp αt ∥u∥p. This shows the recursion forgets its initial iterate on the time scale α−1 without requiring one-step contraction.

• Theorem 2 (Pullback stationary TD solution): The pullback limit exists in Lp, is independent of deterministic x, and generates a stationary solution with finite pth moment.

• Theorem 4 (Fixed-α TD FCLT): n−1/2 Σ⌊nr⌋t=1 (θtα,◦ − θα) ⇒ omega1/2α Wd(r) in D([0,1], Rd), where Wd is a standard d-dimensional Brownian motion. The limit is centered at θα, not at θ∗.

• Theorem 5 (RR-FCLT): The stacked stationary process converges to a Brownian motion with a positive-semidefinite long-run covariance matrix omegaΘ,α, and the weighted combination converges with covariance omegaϑ,α:= BRR omegaΘ,α B⊤RR.

• Corollary 6 (Self-normalized inference): The statistic TnSN ⇒ Wq(1)⊤ [∫01 W̄q(r)W̄q(r)⊤ dr]−1 Wq(1), a pivotal limit not involving the covariance.

• Theorem 7 (Horizon-indexed RR-FCLT for θ∗): Under Assumption 4(i)–(iii), the stationary triangular-array process satisfies n−1/2 Σ⌊nr⌋t=1 (ϑ◦t,n − θ∗) ⇒ omega1/20 Wd(r), with the limiting driving process reducing to additive Markov noise ξt = bt − At θ∗.

• Corollary 8 (Self-normalized inference for θ∗): The same Brownian functional applies, giving confidence regions with asymptotic coverage 1 − η for Rθ∗.

The horizon-indexed rate conditions require:

• αn ↓ 0 and αn ≤ αadm,p,qRR for all sufficiently large n;

• n1−2/p αn → ∞;

• √n αnqRR+1 → 0;

• √αn n → ∞ (for deterministic starts).

When αn = n−ν, the rate window is 1/ 2(qRR+1) < ν < min(1/2, 1 − 2/p). For first-order RR (qRR = 1), the lower endpoint is 1/4.

The online implementation (Algorithm 1) maintains O(Ld + qd + q2) persistent storage for a dense contrast, with O(qd) cost for computing Rϑt and O(q2) per step for updating the self-normalizer.

Experiments on FrozenLake and random Garnet MDPs examine stationary-target coverage, RR target correction, sensitivity to mixing, batch-rule sensitivity, horizon-indexed inference, and online computation. Key findings include:

• RR–SN attains near-nominal stationary-target coverage across the evaluated Garnet designs (0.927 to 0.963), whereas smaller-stepsize, higher-dimensional FrozenLake cells remain under-covered and stabilize more slowly.

• Slower mixing is associated primarily with wider intervals and slower finite-horizon coverage stabilization.

• The first-order RR combination reduces the mean absolute target shift from approximately 1.75 × 10−2 to 4.9 × 10−4, about a 36-fold reduction in the evaluated Garnet designs, while leaving average interval length essentially unchanged.

• The horizon-indexed diagnostics are consistent with the predicted directions of the sufficient remainder scales over the evaluated horizon grid, including the RR/No-RR slope reversal at the interior rate ν = 1/3.

• At ν = 1/3, a warm start gives RR–SN coverage about 0.94 with average length about 0.11, whereas zero initialization gives coverage 1.000 with average length about 1.69 (conservative transient widening).

Improvements to AI Systems:

1. Robust Reinforcement Learning Inference Without Hyperparameter Tuning

• AI systems using TD learning (e.g., value-based RL agents) can now produce statistically valid confidence regions for value estimates under Markovian sampling, without requiring manual selection of bandwidth, batch length, or long-run covariance estimators. This eliminates a major source of user error and computational overhead in policy evaluation.

2. One-Pass, Memory-Efficient Online Uncertainty Quantification

• The self-normalized inference procedure (Algorithm 1) enables real-time, streaming confidence intervals for state-value contrasts with O(Ld + qd + q2) memory (independent of trajectory length). This allows AI systems deployed in long-horizon or infinite-horizon settings (e.g., robotics, recommendation systems) to continuously monitor estimation uncertainty without storing historical data.

3. Accurate Inference for the True Bellman Solution (Not Just Stepsize-Dependent Targets)

• The horizon-indexed design (Theorem 7) provides a principled way to shrink stepsizes across runs, ensuring that confidence regions target the projected Bellman solution θ* rather than the biased stationary target θRR,α. This corrects a systematic bias in fixed-stepsize TD inference, improving the reliability of AI systems that rely on value estimates for decision-making.

4. Automatic Bias Correction via Richardson–Romberg Extrapolation

• The first-order RR combination reduces the target shift by 36× (from 1.75×10−2 to 4.9×10−4) with negligible change in interval width. AI systems can adopt this as a default bias-correction layer in TD learning, improving accuracy of value estimates in off-policy or high-variance environments without extra tuning.

5. Theoretical Guarantees for Finite-Sample Mixing Sensitivity

• The Lyapunov block contraction (Theorem 1) and pullback stationarity (Theorem 2) provide explicit mixing-time bounds (on the α−1 scale) without requiring one-step contraction. AI systems can use these bounds to automatically detect when a given stepsize or environment mixing rate will lead to unreliable inference, triggering adaptive stepsize reduction or data collection strategies.

6. Horizon-Indexed Rate Scheduling for Valid Root-n Inference

• The explicit rate window (e.g., ν ∈ (1/4, 1/2) for first-order RR) gives AI systems a principled schedule for decreasing stepsizes across runs, ensuring that the residual target shift and initialization effects vanish at the root-n scale. This enables valid confidence intervals for the Bellman solution in practice, even with finite horizons.

7. Improved Exploration and Safe Decision-Making

• With reliable confidence regions for value contrasts, AI systems can implement risk-aware policies (e.g., upper-confidence-bound exploration, safe RL) that explicitly account for estimation uncertainty. The method’s coverage guarantees (near-nominal 0.94–0.96 in experiments) support deployment in safety-critical applications like autonomous navigation or clinical decision support.

8. Scalable Inference for High-Dimensional State Spaces

• The method’s memory and computational complexity scale linearly with state dimension d (for dense contrasts), making it feasible for AI systems with large state spaces (e.g., image-based RL) where full covariance estimation would be intractable.

What the Improved AI System Can Do:

• Provide real-time, statistically valid confidence intervals for value estimates in RL agents, with no user-selected tuning parameters.

• Automatically correct stepsize-induced bias to target the true Bellman solution.

• Operate in streaming, memory-constrained environments (e.g., edge devices, long-running simulations).

• Detect and adapt to slow-mixing environments via theoretical mixing-time bounds.

• Make safer, uncertainty-aware decisions in sequential decision-making tasks.