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

Min Zeng; Xiaofeng Shao; Yichen Zhang

REVIEW 4 major objections 5 minor 16 references

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

T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Fixed-stepsize TD learning under Markovian sampling admits asymptotically pivotal confidence regions for prespecified state-value contrasts without estimating the long-run covariance, via a Brownian-bridge self-normalizer.

desk verdict Solid, genuinely new inference recipe for constant-stepsize TD—but the load-bearing Poisson-equation proof is only in an unavailable appendix, so treat the FCLTs as conditional. read the letter →

arxiv 2608.10896 v1 pith:HOMMGM5O submitted 2026-08-11 stat.ML cs.LG

Min Zeng , Yichen Zhang , Xiaofeng Shao This is my paper · ORCID

classification stat.MLcs.LG MSC 62L2060F1762F25

keywords temporal-differencelearningself-normalizationMarkoviansamplingconstantstepsizefunctionalcentrallimittheoremRichardson–RombergextrapolationBrownianbridgepolicyevaluation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Constant-stepsize temporal-difference (TD) learning is a streaming method for policy evaluation, but the usual asymptotic theory has not delivered confidence statements from a single Markov trajectory without long-run covariance estimation. This paper tries to prove that, for linear TD with a fixed stepsize, a Brownian-bridge self-normalizer built from the observed partial-sum path makes inference pivotal: for any prespecified linear contrast of state values, the statistic converges to a universal Brownian functional, with no long-run covariance estimator, bandwidth, or batch-length selector. At a fixed stepsize the inferential center is the Richardson–Romberg stationary target $\theta_{RR,\alpha}$ rather than the projected Bellman solution $\theta_*$; a separate horizon-indexed design, with stepsize constant within each run and decreasing across runs, shifts the center to $\theta_*$ under explicit rate conditions. A sympathetic reader cares because one-pass, memory-bounded confidence regions would make streaming policy evaluation practical without fragile tuning.

What carries the argument

The load-bearing object is the Brownian-bridge self-normalizer $\hat V^{SN}_n = n^{-2}\sum_{s=1}^n (S_s - s\bar\vartheta_n)(S_s - s\bar\vartheta_n)^\top$: it is the sample analogue of the integrated squared Brownian bridge, and because the unknown long-run covariance $\Omega$ multiplies both the endpoint and the bridge in the weak limit, it cancels from $T^{SN}_n = n(R\bar\vartheta_n - c)^\top (R\hat V^{SN}_n R^\top)^{-1}(R\bar\vartheta_n - c)$. The proof chain that carries the claim is a sequence of reductions: Theorem 1's Lyapunov block contraction shows exponential forgetting uniform in the chain's starting state; Theorem 2's pullback stationary solution supplies the exact stationary law and the innovation $\phi^\alpha_t = \xi_t - \tilde A_t h^\alpha_{t-1} - \bar A \bar h^\alpha$; the augmented-chain Poisson equation (Proposition 3) splits that innovation into a martingale difference plus a telescoping remainder that determines $\Omega_\alpha$; and the horizon-indexed reduction (36) shows that inside the Assumption 4 rate window the RR partial sums converge to $\bar A^{-1}$ times the additive Markov-noise partial sums. Proposition 10 then transfers any such FCLT to the same pivotal quadratic form without estimating the covariance.

What would settle it

Numerically evaluate the uniform block-contraction inequality (11) on a slow-mixing finite-state Markov chain across many starting states $y$ and admissible stepsizes $\alpha$; if any pair violates the stated exponential decay, the stationary-recursion construction and therefore the self-normalized coverage claim collapse.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is a distributional limit theorem plus a cancellation device. For a fixed stepsize $\alpha$, the centered partial sums of the stationary TD recursion converge to the Brownian motion limit $n^{-1/2}\sum_{t=1}^{\lfloor nr \rfloor}(\theta^{\alpha,\circ}_t - \theta^\alpha) \Rightarrow \Omega_\alpha^{1/2} W_d(r)$, where the innovation process $\phi^\alpha_t = \xi_t - \tilde A_t h^\alpha_{t-1} - \bar A \bar h^\alpha$ keeps the multiplicative term induced by the random TD matrix in the first-order path law. For $L$ Richardson–Romberg recursions driven by the same trajectory, the joint partial-sum process converges with cross-level covariance blocks, and the Brownian-bridge self-normalizer $\hat V^{SN}_n$ cancels the unknown covariance in the quadratic form, giving the pivotal law $W_q(1)^\top [\int \bar W_q \bar W_q^\top]^{-1} W_q(1)$. The paper claims this yields asymptotically valid confidence regions for $R\theta_{RR,\alpha}$ at fixed stepsize and, under the horizon-indexed rate conditions in Assumption 4, for $R\theta_*$ as the residual RR target shift, multiplicative remainder, and initialization effect become root-$n$ negligible.

Load-bearing premise

Everything rests on the claim that the TD recursion forgets its starting point exponentially fast, uniformly over every starting state of the Markov chain and every small fixed stepsize; if that claim fails, the stationary solution and all downstream confidence regions collapse.

Editorial extensions

If this is right

At a fixed stepsize, confidence regions for the RR stationary target $R\theta_{RR,\alpha}$ have asymptotic coverage $1-\eta$ with no long-run covariance estimator, bandwidth, or batch-length selection.
The same Brownian-bridge critical values cover the projected Bellman solution $R\theta_*$ under the horizon-indexed rate window $\alpha_n = n^{-\nu}$ with $1/(2(q_{RR}+1)) < \nu < \min\{1/2, 1-2/p\}$.
The one-pass recursion keeps memory independent of the trajectory length, with $O(Ld+qd+q^2)$ persistent storage for a dense contrast and a reported $0.180$ MB online state at $d=10$, $n=10^6$.
First-order RR with nodes $(1,2)$ and weights $(2,-1)$ cuts the target shift from roughly $1.75\times 10^{-2}$ to $4.9\times 10^{-4}$ in the evaluated Garnet designs, with interval length essentially unchanged.
In the horizon-indexed regime the leading stochastic term is additive Markov noise $\xi_t = b_t - A_t\theta_*$, so the long-run covariance reduces to $\bar{A}^{-1}\Sigma_\xi \bar{A}^{-\top}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the same Brownian-bridge transfer should apply to any constant-stepsize stochastic-approximation recursion with a Hurwitz mean matrix and a stationary pullback solution, making the method a template for linear LSA inference rather than a TD-specific device.
The paper fixes the contrast $R$ before the run; tracking several contrasts simultaneously would amount to keeping one self-normalizer per contrast, though simultaneous coverage would need a stronger argument than pointwise asymptotic pivotality.
The lower endpoint of the rate window pushes toward higher RR cancellation order to reach $\theta_*$ at practical horizons, but larger signed weights may inflate finite-sample variance; the experiments' pattern of slower stabilization in smaller-stepsize, higher-dimensional cells suggests the practical window may be narrower than the sufficient proof window.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. First, the paper gives a genuinely new recipe: constant-stepsize linear TD under Markov sampling, with Richardson–Romberg recursions sharing one trajectory, and a Brownian-bridge self-normalizer that yields pivotal confidence regions without estimating the long-run covariance. Second, the main inference results are conditional on a block of technical proofs—Theorem 1's Lyapunov block contraction, Proposition 3's Poisson equation for the augmented chain, and the central reduction (36)—all deferred to Online Appendix 1, which is not in the distributed text. I cannot check those steps, and neither can a referee. The visible part of the argument, especially the self-normalization transfer in Appendix B, is standard and correct.

What is new and good: the separation between the fixed-stepsize stationary target and the projected Bellman solution is clean, and the horizon-indexed rate window is explicit. The one-pass algorithm with memory independent of the horizon is a real practical win. The experiments are unusually honest: they report the FrozenLake small-stepsize undercoverage, label the horizon extension as post-hoc sensitivity analysis, and share code and data. The pilot selection of the batch-mean rule is disclosed. Credit where due.

Soft spots, in proportion. The missing appendix is the main one. The augmented chain Z_t^α has an unbounded second coordinate that forgets at rate cα; uniform geometric ergodicity of the data chain does not automatically transfer, so Proposition 3 is genuinely load-bearing. If that Lyapunov bound fails at the stated uniformity, the FCLTs and the pivotal inference all collapse. This is missing support, not an observed contradiction, but it is exactly the step that should be in the main text or a reliably available supplement. The horizon-indexed theory inherits the issue through the unproven reduction (36). Minor: the deterministic-start rate condition (31), α_n√n → ∞, makes the exponent window tighter than the stationary version, but the paper states this clearly.

Who this is for: researchers doing statistical inference for reinforcement learning, especially those wanting tuning-free confidence regions from one pass of TD. The full proof of the main theorem is not in the submitted packet, which makes the verdict conditional, but this is a condition, not a fatal flaw.

Recommendation: yes, send it to peer review, but get the online appendix into the referees' hands first. If Theorem 1 and Proposition 3 check out, this is a strong paper.

Referee Report

4 major / 5 minor

Summary. The paper develops asymptotic inference for constant-stepsize linear temporal-difference learning under Markovian sampling. It constructs a stationary fixed-stepsize recursion, proves a fixed-stepsize functional central limit theorem whose covariance retains the multiplicative TD noise, derives a joint FCLT for parallel Richardson–Romberg recursions sharing one trajectory, and shows that a Brownian-bridge self-normalizer yields asymptotically pivotal confidence regions for prespecified contrasts without estimating the long-run covariance or choosing a bandwidth or batch length. A horizon-indexed regime, with stepsize constant within each run and decreasing across runs, is proposed for inference on the projected Bellman solution. The main theoretical results in Sections 4 and 6 rest on stability and Poisson-equation arguments whose proofs are deferred to Online Appendix 1, which is not part of the distributed text; the visible Appendix B gives a complete proof of the self-normalization transfer.

Significance. If the deferred proofs are correct, the paper makes a substantial contribution: it provides a one-pass, memory-bounded confidence-region method for constant-stepsize TD that avoids the notoriously difficult long-run covariance estimation step, and it clarifies that the inferential center is the RR stationary target at fixed stepsize and the projected Bellman solution only under the separate horizon-indexed rate conditions. The visible part of the paper is strong: Lemma 9 and Proposition 10 are proved carefully, the related-work table is informative, the numerical section reports honest finite-sample diagnostics including under-coverage and initialization sensitivity, and a reproducibility repository is provided. The main weakness is verifiability: Theorem 1, Proposition 3, and the horizon-indexed reduction (36) are load-bearing and are not proved in the reviewed text. I found no circularity in the target definition: the paper explicitly defines θ_RR,α as the stationary mean of the RR recursion and claims coverage for that object at fixed stepsize, while using external bias bounds and rate conditions to move to θ_* in the horizon-indexed regime.

major comments (4)

[§1.2, §4.1, §6.2] The load-bearing technical inputs—Theorem 1's uniform block-contraction bound (11), Proposition 3's Poisson solution (15)–(17), and the horizon-indexed reduction (36)—are proved only in Online Appendix 1, which is not distributed with the reviewed text. I was able to verify Appendix B, Lemma 9, and Proposition 10, but not the stability and Poisson-equation steps on which Theorems 4, 5, 7 and their corollaries depend. Theorem 1's uniformity in the starting state y and in α is used to construct the stationary recursion and to transfer limits from stationary starts to fixed deterministic initializations; Proposition 3 supplies the covariance formula (18); and (36) is the step that makes the multiplicative component and the TD boundary negligible in the horizon-indexed regime. This is a missing-support issue for the central claim, not a presentation detail.
[§4.2, Proposition 3] Proposition 3 asserts an L2 solution Vα to Vα − PαVα = φα for the augmented chain Z_t^α = (Y_t, h_{t−1}^α), where h^α is unbounded and forgets at rate cα. Uniform geometric ergodicity of Y_t alone does not imply the Poisson equation for the product chain, so the finite-memory approximation and projective summability argument must be supplied. Since equation (17), the martingale-difference covariance (18), and the fixed-stepsize FCLT all pass through this proposition, the current text cannot support Theorem 4 without that argument.
[§6.2, Eq. (36)] The central reduction (36) is asserted with proof deferred to Online Appendix 1. It is exactly the statement that the centered multiplicative component ζ^RR_{t,n}, the TD boundary term, and the residual RR target shift are uniformly o_p(√n), and it identifies the limiting additive covariance Ω0 in (34). The rate assumptions in Assumption 4(i)–(iii) do not by themselves visibly deliver the displayed uniform-in-r Lp statement; the proof must show the projective maximal controls. Without this reduction, Theorem 7 and Corollary 8 are unsupported.
[§4.3, Eq. (21)] The RR bias bound (21), which is essential for the horizon-indexed inference for θ*, is imported from Huo et al. [2026] and translated in Online Appendix 1. The main text gives no statement of the bias expansion's order, the dependence of its remainder constant on the fixed cancellation order, or the exact stepsize threshold under which it holds. Since the fixed-stepsize results do not need (21) but Corollary 8 does, the paper should either state the expansion in the main text with its constants and thresholds or include the proof in the distributed version.

minor comments (5)

[§4.2, Eq. (13)] The claim E[φ_t^α] = 0 is correct but deserves a one-line derivation using stationarity of the TD recursion and E[b_t] = Aθ*; as written the reader must reconstruct the algebra.
[§6.3 and Table 5] The rate window is stated with strict inequalities, but Table 5 labels ν = 1/2 as the 'upper boundary' even though Assumption 4(iv) requires α_n√n → ∞; the table should state explicitly that ν = 1/2 is outside the admissible regime.
[§7.1] The FrozenLake reset convention—after a terminal transition the process resets to the designated start state while the terminal feature remains in the TD update—needs a formal description of the induced transition kernel to justify treating the resulting sequence as a stationary Markov chain for the asymptotic analysis.
[§4.3, Theorem 5] The sentence 'Both convergences above remain valid pointwise...' is ambiguous: if it means finite-dimensional convergence only, that is weaker than what Corollary 6 needs, and if it means weak convergence in D, the word 'pointwise' is misleading. The statement should be clarified.
[§5] The one-pass implementation is clearly explained, but the paper does not report the simulated Brownian critical values κ_{q,1−η} used in the experiments; including a small table or the simulation code in the main text or Online Appendix 2 would make the procedure fully reproducible from the paper alone.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reduction: the self-normalized inference transfer is proved in-paper, and the only significant concern is deferred proof support, not circularity.

full rationale

The paper's fixed-stepsize target theta_RR,alpha is a population parameter (the stationary mean of the RR recursion) rather than a fitted quantity; Corollaries 6 and 8 obtain pivotal limits by applying an in-paper transfer theorem (Proposition 10) to FCLTs, with the covariance factor canceled algebraically in the quadratic form, not by estimating it from the same data. The horizon-indexed inference for theta* does not fit the target to the data: it requires the external RR bias bound (21) plus explicit rate conditions (Assumption 4), and the target theta* is defined independently through the projected Bellman equation. No equation in the submitted text is equivalent to its own input by construction, and no fitted parameter is renamed as a prediction. The Shao 2010 citation for Brownian-bridge self-normalization is a non-load-bearing attribution because Proposition 10 and Lemma 9 provide a self-contained proof. The main verifiability concern is that Theorem 1's uniform Lyapunov bound, Proposition 3's augmented-chain Poisson equation, and the central reduction (36) are asserted to be proved in Online Appendix 1, which is absent from the distributed text; that is an omitted-proof support gap, not a circularity. There is no observed circular step, so the score is 0.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

No new physical or model-level entity is introduced; the augmented chain Z_t = (Y_t, h^alpha_{t-1}) is a proof device, not a postulate. The user-selected stepsizes and RR weights are hyperparameters rather than fitted constants. The proof thresholds (alpha_stab,p, alpha_fix,p, etc.) are sufficient constants constructed from the problem instance and are not tuned to simulated data.

free parameters (3)

base stepsize alpha
User-chosen learning-rate scale; in experiments alpha ranges over {0.005, 0.01, 0.02, 0.04, 0.06} for FrozenLake and {0.005, ..., 0.04} for Garnet. It is not fitted to data, but the result depends on it.
RR design (a_l, w_l) = (1,2) with weights (2,-1) in experiments
First-order Richardson-Romberg design chosen by the user; the theory allows any design satisfying the cancellation equations (8). Not fitted.
horizon-indexed exponent nu = 0.2, 1/4, 1/3, 1/2, 0.6 in diagnostics
User-specified rate alpha_n = 0.4 n^{-nu}; the rate window 1/(2(qRR+1)) < nu < min{1/2, 1-2/p} is a sufficient theoretical condition, not a fitted parameter.

assumptions (6)

domain assumption Assumption 1: stationary, irreducible, aperiodic Markov chain that is uniformly geometrically ergodic, with bounded maps A and B.
Used throughout Theorems 1 to 8 as the sampling and boundedness backbone. Standard in Markovian LSA analyses.
domain assumption Assumption 2: mean update matrix A-bar is positive stable.
Guarantees the projected Bellman solution theta* is well defined; for on-policy TD it follows from nonsingularity of the feature covariance.
domain assumption Assumption 3: every recursion stepsize lies below the problem-dependent stability threshold alpha_stab,p.
Used to enter the block-contraction regime and construct the stationary recursion in the fixed-stepsize analysis.
domain assumption Assumption 4: horizon-indexed rate conditions on alpha_n (n^{1-2/p} alpha_n -> infinity, sqrt(n) alpha_n^{qRR+1} -> 0, alpha_n sqrt(n) -> infinity).
Define the window in which the RR target shift, multiplicative remainder, and initialization effect are negligible at the root-n scale, yielding the theta* limit.
standard math Finite-order stationary-bias expansion of Huo et al. [2024, 2026] (bound (21)).
Imported external theorem: a fixed RR design of cancellation order qRR satisfies ||theta_RR,alpha - theta*|| <= C_RR alpha^{qRR+1}. Used in the horizon-indexed argument.
standard math Classical Poisson-equation solution for bounded additive Markov noise xi_t.
Used in Section 6.2 to define V_xi and the limiting covariance Omega_0 under the horizon-indexed design.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling." pith.science (2026). https://pith.science/paper/HOMMGM5O

@misc{pith2026260810896,
  author       = {Pith},
  title        = {Pith review of: Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HOMMGM5O}},
  note         = {Machine review of arXiv:2608.10896}
}

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.

Figures

Figures reproduced from arXiv: 2608.10896 by the authors.

**Figure 2.** the average RR–SN interval is approximately five times longer under slow mixing, while [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗

**Figure 2.** Coverage of each method’s stationary target (top) and average 95% confidence-interval [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗

Figures from the paper (3 more)

**Figure 3.** Figure 3: FrozenLake coverage of each method’s stationary target (top) and average 95% confidence [PITH_FULL_IMAGE:figures/full_fig_p020_3.png]

**Figure 4.** Figure 4: Garnet target shift from Rθ∗ for RR–SN and No-RR SN. The top row reports the mean absolute target shift, and the bottom row divides each replication-level target shift by its interval half-width before averaging. The columns correspond to d = 5 and d = 10. Solid lines …

**Figure 5.** Figure 5: Direct-Rθ∗ coverage (left) and average interval length (right) for RR–SN at ν = 1/3, comparing zero initialization with the reference independent-chain 200,000-step TD warm start. The evaluation trajectory begins from a separate stationary state and is shared by the tw…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 10 canonical work pages

[2026]

Revisiting the Constant Stepsize Stochastic Approximation with Decision-Dependent Markovian Noise

URLhttps://doi. org/10.48550/arXiv.2604.13378. Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie. Effectiveness of constant stepsize in Markovian LSA and statistical inference.Proceedings of the AAAI Conference on Artificial Intelligence, 38 (18):20447–20455,

work page Pith review arXiv doi:10.48550/arxiv.2604.13378
[4]

Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie

doi: 10.1609/aaai.v38i18.30028. Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in Markovian linear stochastic approximation with constant step sizes.Mathematics of Operations Research,

work page doi:10.1609/aaai.v38i18.30028
[5]

Nicholas M

doi: 10.1287/moor.2024.0471. Nicholas M. Kiefer, Timothy J. Vogelsang, and Helle Bunzel. Simple robust testing of regression hypotheses.Econometrica, 68(3):695–714,

work page arXiv 2024
[7]

Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin

URLhttps://doi.org/10.48550/arXiv.2405.17834. Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin. Fast and robust online inference with stochastic gradient descent via random scaling.Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):7381–7389,

arXiv doi:10.48550/arxiv.2405.17834
[9]

Jiaqi Li, Zhipeng Lou, Stefan Richter, and Wei Biao Wu

doi: 10.1609/aaai.v40i43.40994. Jiaqi Li, Zhipeng Lou, Stefan Richter, and Wei Biao Wu. The stochastic gradient descent from a nonlinear time series perspective,

work page doi:10.1609/aaai.v40i43.40994
[13]

Xiaofeng Shao

doi: 10.52202/085713-5807. Xiaofeng Shao. A self-normalized approach to confidence interval construction in time series.Journal of the Royal Statistical Society: Series B, 72(3):343–366,

work page doi:10.52202/085713-5807
[1988]

Richard S

doi: 10.1007/BF00115009. Richard S. Sutton and Andrew G. Barto.Reinforcement learning: An introduction. MIT Press, Cambridge, Massachusetts, second edition,

doi:10.1007/bf00115009
[1997]

Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo

doi: 10.1109/9.580874. Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo. Statistical inference for policy evaluation with temporal-difference learning, 2026a. URLhttps://doi.org/10.48550/arXiv.2410.16106. 28 Weichen Wu, Yuting Wei, and Alessandro Rinaldo. Uncertainty quantification for Markov chain induced martingales with application to temporal-di...

arXiv doi:10.48550/arxiv.2410.16106

Show all 16 references

[2000]

Caio Kalil Lauand and Sean Meyn

doi: 10.1111/1468-0262.00128. Caio Kalil Lauand and Sean Meyn. Revisiting step-size assumptions in stochastic approximation,
[2010]

doi: 10.1111/j.1467-9868.2009. 00737.x. R. Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learning. InProceedings of the 32nd Conference on Learning Theory, volume 99 ofProceedings of Machine Learning Research, pages 2803–2830,

2009
[2020]

Wenlong Mou, Ashwin Pananjady, Martin J

URLhttps://proceedings.mlr.press/ v125/mou20a.html. Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright, and Peter L. Bartlett. Optimal and instance-dependent guarantees for Markovian linear stochastic approximation. InProceedings of the 35th Conference on Learning Theory, vol...
[2021]

Christoph Dann, Gerhard Neumann, and Jan Peters

doi: 10.1287/opre.2020.2024. Christoph Dann, Gerhard Neumann, and Jan Peters. Policy evaluation with temporal differences: A survey and comparison.Journal of Machine Learning Research, 15(24):809–883,

2020
[2022]

27 Ilya Levin, Alexey Naumov, and Sergey Samsonov

doi: 10.1609/aaai.v36i7.20701. 27 Ilya Levin, Alexey Naumov, and Sergey Samsonov. High-order error bounds for Markovian LSA with Richardson–Romberg extrapolation.Proceedings of the AAAI Conference on Artificial Intelligence, 40(43):36696–36704,

doi
[2023]

URL https://doi.org/10.48550/arXiv.2302. 07690. Wenlong Mou, Chris Junchi Li, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan. On linear stochastic approximation: Fine-grained Polyak–Ruppert and non-asymptotic concentra- tion. InProceedings of the 33rd Conferenc...

doi
[2024]

Jalaj Bhandari, Daniel Russo, and Raghav Singal

doi: 10.52202/079017-4379. Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite-time analysis of temporal-difference learning with linear function approximation.Operations Research, 69(3):950–973,

doi
[2025]

Xiang Li, Jiadong Liang, and Zhihua Zhang

doi: 10.52202/085713-3171. Xiang Li, Jiadong Liang, and Zhihua Zhang. Online statistical inference for nonlinear stochastic approximation with Markovian data,

doi

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [2026]

Revisiting the Constant Stepsize Stochastic Approximation with Decision-Dependent Markovian Noise

URLhttps://doi. org/10.48550/arXiv.2604.13378. Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie. Effectiveness of constant stepsize in Markovian LSA and statistical inference.Proceedings of the AAAI Conference on Artificial Intelligence, 38 (18):20447–20455,

work page Pith review arXiv doi:10.48550/arxiv.2604.13378

[2] [4]

Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie

doi: 10.1609/aaai.v38i18.30028. Dongyan Lucy Huo, Yudong Chen, and Qiaomin Xie. Bias and extrapolation in Markovian linear stochastic approximation with constant step sizes.Mathematics of Operations Research,

work page doi:10.1609/aaai.v38i18.30028

[3] [5]

Nicholas M

doi: 10.1287/moor.2024.0471. Nicholas M. Kiefer, Timothy J. Vogelsang, and Helle Bunzel. Simple robust testing of regression hypotheses.Econometrica, 68(3):695–714,

work page arXiv 2024

[4] [7]

Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin

URLhttps://doi.org/10.48550/arXiv.2405.17834. Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin. Fast and robust online inference with stochastic gradient descent via random scaling.Proceedings of the AAAI Conference on Artificial Intelligence, 36(7):7381–7389,

arXiv doi:10.48550/arxiv.2405.17834

[5] [9]

Jiaqi Li, Zhipeng Lou, Stefan Richter, and Wei Biao Wu

doi: 10.1609/aaai.v40i43.40994. Jiaqi Li, Zhipeng Lou, Stefan Richter, and Wei Biao Wu. The stochastic gradient descent from a nonlinear time series perspective,

work page doi:10.1609/aaai.v40i43.40994

[6] [13]

Xiaofeng Shao

doi: 10.52202/085713-5807. Xiaofeng Shao. A self-normalized approach to confidence interval construction in time series.Journal of the Royal Statistical Society: Series B, 72(3):343–366,

work page doi:10.52202/085713-5807

[7] [1988]

Richard S

doi: 10.1007/BF00115009. Richard S. Sutton and Andrew G. Barto.Reinforcement learning: An introduction. MIT Press, Cambridge, Massachusetts, second edition,

doi:10.1007/bf00115009

[8] [1997]

Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo

doi: 10.1109/9.580874. Weichen Wu, Gen Li, Yuting Wei, and Alessandro Rinaldo. Statistical inference for policy evaluation with temporal-difference learning, 2026a. URLhttps://doi.org/10.48550/arXiv.2410.16106. 28 Weichen Wu, Yuting Wei, and Alessandro Rinaldo. Uncertainty quantification for Markov chain induced martingales with application to temporal-di...

arXiv doi:10.48550/arxiv.2410.16106