Pith. sign in

REVIEW 2 major objections 4 minor 49 references

A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A general theorem converts raw-iterate concentration bounds into Polyak-averaged bounds at the optimal $O(1/k)$ rate.

desk verdict A genuinely useful modular theorem for Polyak-averaged SA bounds, but the main proof has an off-by-one gap and the tightness example has scaling errors. read the letter →

arxiv 2505.21796 v1 pith:5FOJLLMD submitted 2025-05-27 stat.ML cs.LGmath.PR

Sajad Khodadadian , Martin Zubeldia This is my paper
classification stat.MLcs.LGmath.PR MSC 62L2060E15
keywords stochasticapproximationPolyak-Ruppertaveraginghigh-probabilityboundsconcentrationinequalitiestemporaldifferencelearningQ-learningcontractiveoperatorssubgaussiannoise
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

Polyak–Ruppert averaging is known to give stochastic approximation algorithms their optimal asymptotic variance, but finite-time high-probability guarantees for the averaged iterates have lagged behind. This paper proves a transfer theorem: if the raw iterates $x_i$ come with any high-probability bound of the form $\|x_i-x^*\|^2_c \le \alpha_i f_\xi(\delta',k)$ for all $i\le k$, then the averaged iterates $y_k$ satisfy $\|y_k-x^*\|^2_c \le (c\log(1/\delta)+d)\bar\sigma^2/(k+1)$ plus higher-order terms, with probability at least $1-\delta$. The bound is tight up to a universal constant for a constructed example, and it applies to contractive stochastic approximation, temporal-difference learning, and Q-learning, giving what the paper reports as the first full-distribution concentration bounds for averaged Q-learning and off-policy TD-learning.

What carries the argument

The proof splits the averaged error into an early part $\bar y_k$ (iterates before the recursion enters the local smoothness radius $R$) and a late part $\tilde y_k$, then writes $(J\bar F(x^*)-I)\tilde y_k$ as four terms: a subgaussian sum of the operator noise at the fixed point, a telescoping step-size term, a remainder controlled by the local pseudo-smoothness constant $N$, and a martingale term driven by Jacobian noise. Chernoff-type exponential concentration on the subgaussian terms produces the $\log(1/\delta)/(k+1)$ leading term, while the Moreau-envelope assumption (Assumption 4.1) is used to keep the squared norm smooth when the natural norm is not.

What would settle it

Run the paper's own tightness example—constant step size, $F(x,w)=w$, and subgaussian noise in even dimension—and measure the limiting tail of $\sqrt{k}\|y_k-x^*\|_2$. If the upper tail constant exceeds the $2\sqrt{6}$ factor allowed by the theorem, the universal constant in Theorem 4.1 is not correct; alternatively, a contractive SA satisfying Assumptions 4.2–4.3 whose averaged error decays slower than $1/k$ for fixed $\delta$ would refute the claimed rate.

Watch

Extended reading notes

Core claim

The paper's central claim is a modular transfer theorem for Polyak–Ruppert averaging. For any stochastic approximation recursion of the form $x_{k+1}=(1-\alpha_k)x_k+\alpha_k F(x_k,w_{k+1})$ whose raw iterates satisfy a high-probability bound $\|x_i-x^*\|^2_c \le \alpha_i f_\xi(\delta',k)$ for all $0\le i\le k$ with probability at least $1-\delta'$, the averaged iterates $y_k=\frac{1}{k+1}\sum_{i=0}^k x_i$ satisfy, with probability at least $1-\delta$, $\|y_k-x^*\|^2_c \le (c\log(1/\delta)+d)\bar\sigma^2/(k+1)$ plus higher-order terms, where $\bar\sigma^2$ is a subgaussian variance proxy of the noise at the fixed point and $c$ is a universal constant. The authors construct an example showing the leading term is tight up to a constant multiplicative factor, and they apply the mechanism to contractive SA, TD-learning, Q-learning, and off-policy TD with linear function approximation.

Load-bearing premise

The clean $\log(1/\delta)/(k+1)$ leading term rests on Assumption 4.3, which requires the operator noise and the Jacobian noise at the fixed point $x^*$ to be subgaussian; when that fails, as in the paper's multiplicative-noise application, the averaged-error tail is only polynomially bounded in $1/\delta$.

Editorial extensions

If this is right

  • For contractive stochastic approximation with additive subgaussian noise, the averaged error has a $\log(1/\delta)/(k+1)$ tail, so the step size need no longer depend on the target confidence $\delta$.
  • Averaged TD-learning and Q-learning inherit whole-distribution concentration bounds with $1/k$ leading terms; the paper identifies these as the first such bounds for averaged Q-learning and off-policy TD.
  • Under multiplicative noise, no sub-Weibull concentration bound is possible for averaged iterates, so the polynomial $1/\sqrt{\delta}$ tail derived in the paper is the natural shape rather than a proof artifact.
  • The framework turns any future improvement in un-averaged SA bounds into an immediate improvement of the averaged bound, because the theorem accepts the raw-iterate bound as a black-box input.
  • Step-size exponent can be tuned: $\xi=1/2$ is best for linear operators with non-additive noise and $\xi=2/3$ for nonlinear operators, controlling the higher-order terms.

Reading between the lines

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

  • Because Theorem 4.1 is black-box in the un-averaged bound, the real bottleneck for heavy-tailed or Markovian settings is the raw-iterate concentration result; better raw bounds would lift to averaged bounds without reworking the averaging argument.
  • Since the theorem bounds the whole distribution of the error with a step size independent of $\delta$, it could support data-dependent confidence intervals for averaged reinforcement-learning estimators, not just single-point tail statements.
  • The multiplicative-noise impossibility result suggests that for off-policy TD with function approximation, practitioners should expect polynomial tails unless extra structure beyond the standard assumptions is exploited; tightening the $1/\sqrt{\delta}$ factor would require sharper un-averaged bounds, a direction the paper names explicitly.
  • A natural test is whether the same transfer mechanism holds for tail-averaged rather than Polyak-averaged iterates, or for Markovian noise where the un-averaged bounds are less mature; the paper does not analyze these, but its assumptions are stated in a way that might accommodate them.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper develops a black-box theorem that converts high-probability bounds on un-averaged stochastic approximation iterates into high-probability bounds on Polyak-Ruppert averaged iterates. Theorem 4.1 claims that if, for each delta', the un-averaged iterates satisfy ||x_i - x*||_c^2 <= alpha_i f_xi(delta', k) for all i <= k with probability at least 1 - delta', then the averaged iterate y_k satisfies a bound whose leading term is O((log(1/delta) + d) sigma^2/(k+1)) plus higher-order terms. The paper applies this result to contractive SA, tabular TD(n), Q-learning, and off-policy TD with linear function approximation, and also claims a tightness example and an impossibility result for multiplicative noise.

Significance. If correct, the main theorem is a genuinely useful modular reduction: it lets existing concentration results for raw SA be lifted to averaged iterates at the parametric rate, and the applications to TD-learning and Q-learning would provide new finite-time distributional bounds. The paper is also honest about a proof artifact in Section 4.1 and about the heavy-tailed behavior under multiplicative noise, which is formalized in Theorem 5.3. However, two load-bearing issues need to be resolved: the proof of Theorem 4.1 uses an off-by-one event that is not supplied by the theorem's hypothesis, and the tightness example in Appendix B.4 contains a scaling error. These issues do not appear to be fatal, but they must be repaired before the advertised claims are established.

major comments (2)
  1. [Appendix B.1, Theorem 4.1] The proof of Theorem 4.1 has an off-by-one gap in its use of events. It defines E_k(delta) using the bound ||x_i - x*||_c^2 <= alpha_i f(delta, k) for 0 <= i <= k, which is exactly what the theorem's hypothesis supplies. From Eq. (B.5) onward, however, all bounds on ||tilde y_k||_c^2 are taken on the event 1_{E_{k+1}}, and E_{k+1} is never explicitly defined. In controlling T2, the telescoping identity introduces x_{k+1} and step (c) uses ||x_{k+1} - x*||_c^2 <= alpha_k f(delta, k); in controlling T3 the text states that ||x_i - x*||_c^2 <= alpha_i f(delta, k) on E_{k+1}. But the theorem's hypothesis only covers indices 0 <= i <= k, and if E_{k+1} is interpreted with the same definition at k+1, it would involve f(delta, k+1), not f(delta, k). Consequently the claimed bound P(E_{k+1}) >= 1 - delta' is not justified, and the final union bound yielding probability at least 1 - delta does not follow as written. The gap is likely repairable by strengthening the hypothesis to hold for all i <= k+1 and restating the input bound with f(delta/2, k+1), or by designing a telescoping decomposition that avoids x_{k+1}; as it stands, this is a load-bearing defect in the central theorem.
  2. [Appendix B.4, Proposition 4.2] The tightness example contains an algebraic scaling error. With x_0 = 0, one has (k+1)||y_k||^2 = ||sum_{i=1}^k w_i||^2/(k+1), but the proof replaces this by ||sum_{i=1}^k w_i||^2 and then compares sqrt{k sigma_bar^2 log(1/delta)} with ||sum_i w_i||. The final computation concludes P(chi_2^2 <= 2 log(1/delta)) = 1 - delta, which is a statement about the norm of the summed noise, not about ||y_k|| at the scaling claimed in the proposition. The proposition statement itself also has a dimension mismatch: sigma_bar sqrt{k log(1/delta)} has the units of a norm, while it is added to ||x_0||^2, a squared norm. Because this example is the basis for the paper's claim that Theorem 4.1 is tight up to a universal constant, the tightness claim is not established by the argument as written. A corrected example may well salvage the qualitative conclusion, but it needs to be restated and re-proved with the correct (k+1) scaling and with care about the dimension term in the leading bound.
minor comments (4)
  1. [Theorem 4.1 statement] In the displayed formula for epsilon_bar(k, delta/2), the function f is evaluated as f(delta, k_0(delta/2, k) - 1), while all other terms in the theorem use f(delta/2, k). This is inconsistent with the union-bound language in the proof and should be corrected to f(delta/2, ...) unless there is a deliberate reason for the asymmetry.
  2. [Appendix B.1] The event E_{k+1} is used repeatedly from Eq. (B.5) onward but is never defined; the text only defines E_k(delta). The proof also refers to the event E_{k0} without definition. These should be made explicit so the reader can check whether the event indices and the f arguments are nested consistently.
  3. [Appendix B.4] The proposition states the probability of the displayed event is at most 1 - delta, while the proof concludes equality. If the intended claim is a lower-tail statement showing that the error can be as large as the leading term, the direction of the inequality and the event should be stated carefully to distinguish high-probability upper bounds from lower-tail statements.
  4. [Appendix B.6] In the proof of Theorem 5.2, the constants beta_2 and beta_4 are used in an inconsistent way: Eq. (B.9) introduces beta_2, while the supermartingale display subsequently uses both beta_2 and beta_4. The notation should be unified so the dependency of the final bound on these constants is clear.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 4.1 is a modular reduction from un-averaged to averaged bounds; the averaging theorem does not assume its own conclusion, and the cited un-averaged bounds are external published results.

full rationale

Theorem 4.1 takes as input a high-probability bound on the individual iterates and produces a bound on the Polyak average; the output is a different quantity, the averaged iterate, and it is not used to define or justify the input. The proof decomposes the average into early and late blocks, bounds each block using the assumed per-iterate bound together with Assumptions 4.1-4.3, and assembles the tail via subgaussian martingale arguments; no parameter is fitted to the target averaged bound. The applications call [14], which is coauthored by Zubeldia, for un-averaged bounds, and [31] for multiplicative-noise moment bounds, but these are published external results and provide only the stated inputs of the reduction; the paper does not invoke a uniqueness theorem or an ansatz from the authors' prior work to forbid alternatives. The tightness example is a constructive lower bound, not a fitted prediction. A separate off-by-one and event-consistency issue in the proof of Theorem 4.1, involving E_{k+1} and the un-averaged bound at i = k+1, is a correctness concern rather than a circularity concern, because it does not make the theorem's conclusion an input by construction. Overall, the derivation chain is self-contained modulo externally supplied un-averaged bounds, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No data-fitting parameters are introduced; the constants alpha, h, and xi are algorithmic hyperparameters rather than free parameters in the fitting sense. The paper introduces no new entities such as particles or forces. The analysis relies on the standard probability and SA assumptions listed in the axioms.

assumptions (5)
  • domain assumption Assumption 4.1: the squared norm ||.||_c^2 is M-smooth with respect to ||.||_c.
    Used in equation (B.4) to obtain the quadratic inequality needed for the Chernoff argument. The paper claims this is without loss of generality via Moreau envelopes, but the theorem states it as an explicit assumption.
  • domain assumption Assumption 4.2(ii): J\bar F(x*) - I is invertible, giving nu > 0.
    Needed to convert concentration of a linearized sum into concentration of the averaged error. Contractive operators satisfy this by Lemma C.3.
  • domain assumption Assumption 4.3: the operator noise and the Jacobian noise at the fixed point x* are subgaussian.
    Yields the O(log(1/delta)/(k+1)) leading term. For multiplicative noise the paper replaces this with fourth-moment assumptions in Theorem 5.2 and obtains only polynomial 1/delta dependence.
  • domain assumption Existence of a high-probability bound f_xi(delta, k) for all un-averaged iterates, as assumed in Theorem 4.1.
    This is the black-box input of the meta-theorem. The paper does not prove it in general; for contractive SA it imports [14, Theorem 2.4].
  • domain assumption Assumptions 5.1 and 5.2 or 5.3 for the applications: contraction of \bar F and either additive subgaussian noise or multiplicative noise with bounded fourth moments.
    These restrict the operator class and noise structure so that the un-averaged bounds used in the applications are available.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging." pith.science (2026). https://pith.science/paper/5FOJLLMD

@misc{pith2026250521796,
  author       = {Pith},
  title        = {Pith review of: A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5FOJLLMD}},
  note         = {Machine review of arXiv:2505.21796}
}
read the original abstract

Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

49 extracted references · 40 canonical work pages

  1. [14]

    Z. Chen, S. T. Maguluri, and M. Zubeldia. Concentration of contractive stochastic approximation: Additive and multiplicative noise. The Annals of Applied Probability, 35, 2025

    work page 2025

  2. [1]

    Bach and E

    F. Bach and E. Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n). In Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS) , page 773–781, 2013

    work page 2013

  3. [2]

    A. Beck. First-order methods in optimization. SIAM, 2017

    work page 2017

  4. [3]

    C. L. Beck and R. Srikant. Error bounds for constant step-size Q-learning. Systems & Control Letters , 61(12):1203–1208, 2012

    work page 2012

  5. [4]

    Bertsekas and J

    D. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996

    1996

  6. [5]

    D. P. Bertsekas, D. P. Bertsekas, D. P. Bertsekas, and D. P. Bertsekas.Dynamic programming and optimal control, volume 2. Athena scientific, 1995

    work page 1995

  7. [6]

    Bhandari, D

    J. Bhandari, D. Russo, and R. Singal. A finite-time analysis of temporal-difference learning with linear function approximation. Operations Research, 69(3):950–973, 2021

    work page 2021

  8. [7]

    S. Chandak. O(1/k) Finite-Time Bound for Non-Linear Two-Time-Scale Stochastic Approximation. arXiv preprint arXiv:2504.19375, 2024

    arXiv 2024

Show all 49 references
  1. [8]

    Chandak and V

    S. Chandak and V . S. Borkar. A Concentration Bound for TD(0) with Function Approximation. arXiv preprint arXiv:2312.10424, 2023

    2023

  2. [9]

    Chandak, V

    S. Chandak, V . S. Borkar, and P. R. Dodhia. Concentration of Contractive Stochastic Approximation and Rein- forcement Learning. Stochastic Systems, 12(4):411–430, 2022

    2022

  3. [10]

    Chandak, S

    S. Chandak, S. U. Haque, and N. Bambos. Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise. arXiv preprint arXiv:2503.18391, 2025

    2025

  4. [11]

    Z. Chen, S. Khodadadian, and S. T. Maguluri. Finite-Sample Analysis of Off-Policy Natural Actor–Critic With Linear Function Approximation. IEEE Control Systems Letters, 6:2611–2616, 2022

    2022

  5. [12]

    Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. Advances in Neural Information Processing Systems, 33:8223– 8234, 2020

    2020

  6. [13]

    Z. Chen, S. T. Maguluri, S. Shakkottai, and K. Shanmugam. A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Research, 71(1):147–164, 2023

    2023

  7. [15]

    Dalal, B

    G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor. Finite sample analyses for TD(0) with function approximation. In Proc. AAAI, volume 32, 2018

    2018

  8. [16]

    Dalal, G

    G. Dalal, G. Thoppe, B. Szörényi, and S. Mannor. Finite sample analysis of two-time-scale stochastic approxima- tion with applications to reinforcement learning. In Proceedings of the Conference on Learning Theory (COLT), pages 1199–1233, 2018

    2018

  9. [17]

    Durmus, E

    A. Durmus, E. Moulines, A. Naumov, and S. Samsonov. Finite-time high-probability bounds for Polyak–Ruppert averaged iterates of linear stochastic approximation.Mathematics of Operations Research, 49(1):454–478, 2024

    2024

  10. [18]

    Durmus, E

    A. Durmus, E. Moulines, A. Naumov, S. Samsonov, K. Scaman, and H.-T. Wai. Tight high probability bounds for linear stochastic approximation with fixed stepsize. Advances in Neural Information Processing Systems , 34:30063–30074, 2021

    2021

  11. [19]

    Even-Dar and Y

    E. Even-Dar and Y . Mansour. Learning rates for Q-learning. Journal of Machine Learning Research , 5:1–25, 2003. 11

    2003

  12. [20]

    D. A. Freedman. On tail probabilities for Martingales. The Annals of Probability, pages 100–118, 1975

    1975

  13. [21]

    Harold, G

    J. Harold, G. Kushner, and G. Yin. Stochastic approximation and recursive algorithm and applications. Applica- tion of Mathematics, 35(10), 1997

    1997

  14. [22]

    Hoeffding

    W. Hoeffding. Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding, pages 409–426. Springer, 1994

    1994

  15. [23]

    S. T. Kong, S. Zeng, T. T. Doan, and R. Srikant. Nonasymptotic CLT and Error Bounds for Two-Time-Scale Stochastic Approximation. arXiv preprint arXiv:2502.09884, 2024

    2024

  16. [24]

    Lakshminarayanan and C

    C. Lakshminarayanan and C. Szepesvári. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In Proc. AISTATS, pages 1347–1355, 2018

    2018

  17. [25]

    C. K. Lauand and S. Meyn. Bias in stochastic approximation cannot be eliminated with averaging. InProceedings of the Annual Allerton Conference on Communication, Control, and Computing, pages 1–4, 2022

    2022

  18. [26]

    G. Li, C. Cai, Y . Chen, Y . Gu, Y . Wei, and Y . Chi. Tightening the dependence on horizon in the sample com- plexity of Q-learning. In Proceedings of the Conference on Learning Theory (COLT), 2021. Extended version: arXiv:2102.06548

    2021 arXiv

  19. [27]

    G. Li, C. Cai, Y . Chen, Y . Wei, and Y . Chi. Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis. Operations Research, 72(1):222–236, 2024

    2024

  20. [28]

    G. Li, Y . Wei, Y . Chi, Y . Gu, and Y . Chen. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. IEEE Transactions on Information Theory, 68(1):448–473, 2022

    2022

  21. [29]

    X. Li, W. Yang, J. Liang, Z. Zhang, and M. I. Jordan. A Statistical Analysis of Polyak-Ruppert Averaged Q- Learning. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS) , volume 206, pages 2207–2261, 2023

    2023

  22. [30]

    W. Mou, C. J. Li, M. J. Wainwright, P. L. Bartlett, and M. I. Jordan. On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration. In Proceedings of the Conference on Learning Theory (COLT), pages 2947–2997, 2020

    2020

  23. [31]

    Moulines and F

    E. Moulines and F. Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. Advances in neural information processing systems, 24, 2011

    2011

  24. [32]

    Nemirovski, A

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4):1574–1609, 2009

    2009

  25. [33]

    B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging.SIAM journal on control and optimization, 30(4):838–855, 1992

    1992

  26. [34]

    Qu and A

    G. Qu and A. Wierman. Finite-time analysis of asynchronous stochastic approximation and Q-learning. In Proceedings of the Conference on Learning Theory (COLT), pages 3185–3205, 2020

    2020

  27. [35]

    Robbins and S

    H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics , pages 400–407, 1951

    1951

  28. [36]

    D. Ruppert. Efficient estimations from a slowly convergent Robbins-Monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988

    1988

  29. [37]

    Samsonov, E

    S. Samsonov, E. Moulines, Q.-M. Shao, Z.-S. Zhang, and A. Naumov. Gaussian Approximation and Multiplier Bootstrap for Polyak–Ruppert Averaged Linear SA with Applications to TD Learning. In Advances in Neural Information Processing Systems, 2024

    2024

  30. [38]

    Samsonov, D

    S. Samsonov, D. Tiapkin, A. Naumov, and E. Moulines. Finite-sample analysis of the temporal difference learning. In Proceedings of the Conference on Learning Theory (COLT), 2024. 12

    2024

  31. [39]

    Samsonov, D

    S. Samsonov, D. Tiapkin, A. Naumov, and E. Moulines. Improved High-Probability Bounds for the TD Learning Algorithm via Exponential Stability. In Proceedings of the Conference on Learning Theory (COLT) . PMLR, 2024

    2024

  32. [40]

    Shalev-Shwartz et al

    S. Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends® in Machine Learning, 4(2):107–194, 2012

    2012

  33. [41]

    R. Srikant. Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning. arXiv preprint arXiv:2401.15719, 2024

    2024

  34. [42]

    Srikant and L

    R. Srikant and L. Ying. Finite-time error bounds for linear stochastic approximation and TD learning. In Proceedings of the Conference on Learning Theory (COLT), pages 2803–2830. PMLR, 2019

    2019

  35. [43]

    R. S. Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3:9–44, 1988

    1988

  36. [44]

    Thoppe and V

    G. Thoppe and V . S. Borkar. A concentration bound for stochastic approximation via Alekseev’s formula. Stochastic Systems, 9(1):1–26, 2019

    2019

  37. [45]

    Tsitsiklis and B

    J. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674–690, 1997

    1997

  38. [46]

    M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint . Cambridge University Press, 2019

    2019

  39. [47]

    C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8:279–292, 1992

    1992

  40. [48]

    E. Xia, K. Khamaru, M. Wainwright, and M. Jordan. Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning. IEEE Transactions on Information Theory, page 1, 2024

    2024

  41. [49]

    exp   6λk (k + 1)2 kX i=k0 (F (x∗, wi+1) − x∗) 2 c .1 Ek+1   #   1/4 | {z } T1 .   E

    Y . Zhang and Q. Xie. Constant stepsize Q-learning: Distributional convergence, bias and extrapolation. Rein- forcement Learning Journal, 3:1168–1210, 2024. 13 Appendices A Analysis of the case study in Section 5 The generalized Moreau envelope norm ∥ · ∥m was introduced in [1...

    2024

Pith tools

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