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

• URL: http://arxiv.org/abs/2608.10896v1
• Date: Tue, 11 Aug 2026 13:19:28 GMT
• Title: Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling
• Abstract summary: Constant-stepsize temporal-difference (TD) learning is attractive for policy evaluation, but inference from a single Markov trajectory must account for serial dependence and a stepsize-dependent stationary target.<n>We establish a functional central limit theorem whose covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error.<n>Experiments on FrozenLake and Garnet illustrate stationary-target coverage, RR target correction, and the finite-sample behavior of the horizon-indexed design.
• Score: 9.271408028342496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Constant-stepsize temporal-difference (TD) learning is attractive for policy evaluation, but inference from a single Markov trajectory must account for serial dependence and a stepsize-dependent stationary target. For fixed-stepsize linear TD, we establish a functional central limit theorem whose covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error. We then derive 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. We also study 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. Experiments on FrozenLake and Garnet illustrate stationary-target coverage, RR target correction, and the finite-sample behavior of the horizon-indexed design.

Related papers

• LC-GRPO: Bridging Train-Inference Gap for Flow-Based GRPO with Langevin Correction [59.32834240526981]
  Flow-based generative models are typically sampled by solving a deterministic ordinary differential equation (ODE)<n>Existing GRPO methods for flow models replace the Euler-time ODE with aotropic differential equation (SDE) during training.<n>We introduce LC-GRPO, a flow-based GRPO framework with Langevin correction targeting the marginal distribution at the resulting timestep.
  arXiv  Detail & Related papers  (2026-08-06T04:47:57Z)
• Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping [56.14767235650558]
  Looped Transformers, which repeatedly apply a shared transformer block, are an architecturally natural fit for variable-length computation tasks.<n>We trace this variance to the spurious correlation in simple algorithmic tasks between sequence length and number of loops.<n>Our work suggests that "when to stop" should be treated as a training design choice, not merely an inference-time-allocation rule.
  arXiv  Detail & Related papers  (2026-06-29T08:58:09Z)
• A Doeblin-Anchored Contrastive Chart for Learning Markov Transition Kernels [1.2691047660244335]
  This paper introduces a statistical-to-dynamical coordinate framework for learning transition kernels from contrastive objectives.<n>We prove that the anchored contrastive risk identifies the anchored transition density and calibrates excess risk to density error.
  arXiv  Detail & Related papers  (2026-06-01T13:26:44Z)
• DISA: Offline Importance Sampling for Distribution-Matching LLM-RL [56.9445657766829]
  We introduce DISA, which moves this calibration problem outside the RL loop.<n> DISA draws proposal trajectories offline, estimates the partition function via importance sampling, and freezes the resulting partition-function estimate.<n>On two open-weight backbones across six math and three code benchmarks, DISA matches or exceeds the online-coupled distribution-matching baseline Flow.
  arXiv  Detail & Related papers  (2026-05-17T07:14:44Z)
• Recovering Physical Dynamics from Discrete Observations via Intrinsic Differential Consistency [12.266189649117003]
  We replace local supervision with a global structural constraint.<n>We train a time-conditioned secant velocity field whose deviation from this property serves two purposes.<n>As a training regularizer, it confines the hypothesis space to flows that compose consistently across temporal scales.
  arXiv  Detail & Related papers  (2026-05-08T20:24:32Z)
• Intentional Updates for Streaming Reinforcement Learning [17.262453188534526]
  In gradient-based learning, a step size chosen in parameter units does not produce a predictable per-step change in function output.<n>We propose intentional updates: first specify the intended outcome of an update and then solve for the step size that approximately achieves it.
  arXiv  Detail & Related papers  (2026-04-21T03:33:40Z)
• BASIS: Balanced Activation Sketching with Invariant Scalars for "Ghost Backpropagation" [0.0]
  Activation memory required for exact backpropagation scales linearly with network depth, context length, and feature dimensionality.<n>In this paper, we introduce an efficient backpropagation algorithm that fully decouples activation memory from the batch and sequence dimensions.
  arXiv  Detail & Related papers  (2026-03-05T20:38:25Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Sparse Randomized Shortest Paths Routing with Tsallis Divergence Regularization [0.0]
  This work elaborates on the problem of designing optimal routing policies for reaching a target node t from a source note s on a weighted directed graph G. Experimental comparisons on node clustering and semi-supervised classification tasks show that the derived dissimilarity measures based on expected routing costs provide state-of-the-art results.
  arXiv  Detail & Related papers  (2020-07-01T12:22:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.