Pith. sign in

REVIEW 3 minor 1 cited by

Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework

T0 review · 0 major / 3 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Generalized Moreau envelopes serve as universal Lyapunov functions for finite-time analysis of stochastic approximation algorithms.

desk verdict This is a straightforward survey that unifies existing Lyapunov tools for stochastic approximation but adds no new theorems or derivations. read the letter →

arxiv 2605.31309 v1 pith:TFBKX346 submitted 2026-05-29 cs.LG math.PRstat.ML

Zaiwei Chen , Siva Theja Maguluri This is my paper · ORCID
classification cs.LGmath.PRstat.ML
keywords stochasticapproximationLyapunovfunctionsfinite-timeanalysisMoreauenvelopesreinforcementlearningQ-learningtemporaldifference
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

The paper surveys Lyapunov techniques for proving non-asymptotic convergence of stochastic iterative algorithms that solve fixed-point equations using noisy oracles. It demonstrates that generalized Moreau envelopes function as Lyapunov functions no matter which norm makes the operator contractive, and this yields mean-square error bounds. The same construction covers stochastic gradient descent, linear stochastic approximation, Q-learning, and temporal-difference learning. The survey also sketches how the approach extends to Markovian noise, seminorm contractive operators, dissipative operators, and high-probability statements.

What carries the argument

generalized Moreau envelopes used as Lyapunov functions that certify contraction of the mean-field operator under additive noise

What would settle it

An explicit counter-example in which the operator fails to be contractive in every norm yet mean-square convergence still holds, or in which the operator is contractive but the Moreau-envelope Lyapunov function fails to decrease.

Watch

Extended reading notes

Core claim

Generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm, and yield mean-square convergence guarantees for stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning.

Load-bearing premise

The fixed-point operator is contractive with respect to some norm and the noise is independent and identically distributed.

Editorial extensions

If this is right

  • Mean-square convergence rates follow directly for stochastic gradient descent on strongly convex problems.
  • The same rates apply to linear stochastic approximation and to value-based methods including Q-learning and TD learning.
  • The framework extends to Markovian noise and to operators that are contractive only in a seminorm.
  • High-probability bounds can be obtained by the same Lyapunov construction.

Reading between the lines

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

  • The universal character of the envelopes may simplify the derivation of rates for new variants of stochastic approximation that have not yet been analyzed.
  • The connection to dissipative operators suggests the technique could reach certain non-contractive but stable dynamical systems.
  • The open problems listed at the end indicate that high-probability and almost-sure statements remain less developed than mean-square ones.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 3 minor

Summary. The manuscript surveys Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms (stochastic approximation or SA) for solving fixed-point equations ¯{F}(x)=x accessed via noisy oracles. It focuses on the standard setting where ¯{F} is contractive w.r.t. some norm and noise is i.i.d., demonstrating that generalized Moreau envelopes serve as universal Lyapunov functions yielding mean-square convergence. Applications to stochastic gradient descent, linear SA, Q-learning, and temporal-difference learning are discussed, along with extensions to Markovian noise, seminorm-contractive operators, dissipative operators, high-probability bounds, and open problems. The aim is a unified, self-contained roadmap for such analyses, especially in reinforcement learning.

Significance. If the presented framework holds, the survey would be significant for providing a unified view of finite-time analysis techniques using generalized Moreau envelopes as Lyapunov functions across different norms and algorithms. This could facilitate the application of these methods in optimization and RL by offering a consistent approach rather than algorithm-specific analyses. The paper's structure as a survey that builds on existing literature while aiming for self-containment is a positive aspect.

minor comments (3)
  1. Abstract: The term 'generalized Moreau envelopes' is introduced without a brief definition or pointer to its construction; adding one sentence would improve accessibility.
  2. Introduction (first paragraph of survey description): The claim that the framework 'yields mean-square convergence guarantees' for the listed algorithms should include a forward reference to the specific section where the rates or conditions are stated, even if drawn from prior work.
  3. Notation throughout: Ensure consistent use of the bar on F and the distinction between the contractive operator and its noisy version; minor inconsistencies here could confuse readers following the Lyapunov construction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report does not raise any specific major comments.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: survey of prior techniques

full rationale

The paper is explicitly framed as a survey that unifies existing Lyapunov techniques for stochastic approximation under contractive operators. The central claim—that generalized Moreau envelopes serve as universal Lyapunov functions for mean-square convergence in the standard i.i.d. noise setting—restates and organizes results from the literature rather than deriving new predictions from parameters fitted inside this manuscript. No equations reduce a claimed result to a self-defined fit, no load-bearing uniqueness theorem is imported solely via self-citation, and the applications to SGD, linear SA, Q-learning, and TD learning are standard fixed-point reformulations. The derivation chain is therefore self-contained against external benchmarks and receives the default non-circularity finding.

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

This is a survey paper; the ledger records the domain assumptions stated in the abstract for the standard setting. No new free parameters or invented entities are introduced by the survey itself.

assumptions (2)
  • domain assumption The operator ar{F} is contractive with respect to some norm
    Stated explicitly as the standard setting in the abstract.
  • domain assumption Noise is i.i.d.
    Stated explicitly for the standard setting in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework." pith.science (2026). https://pith.science/paper/TFBKX346

@misc{pith2026260531309,
  author       = {Pith},
  title        = {Pith review of: Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Framework},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TFBKX346}},
  note         = {Machine review of arXiv:2605.31309}
}
abstract

We survey Lyapunov-based techniques for the finite-time analysis of stochastic iterative algorithms, also known as stochastic approximation (SA) algorithms, for solving fixed-point equations $\bar{F}(x)=x$, where the operator $\bar{F}(\cdot)$ can only be accessed through a noisy oracle. We first focus on the standard setting in which $\bar{F}(\cdot)$ is contractive with respect to some norm and the noise is i.i.d., and explain how generalized Moreau envelopes serve as universal Lyapunov functions, regardless of the underlying norm. We then show how this framework yields mean-square convergence guarantees and applies to stochastic gradient descent, linear SA, and value-based reinforcement learning algorithms such as Q-learning and temporal-difference learning. Finally, we discuss extensions to Markovian noise, seminorm-contractive operators, dissipative operators, and high-probability bounds, and conclude with open problems. The goal is to present a unified and self-contained roadmap for the finite-time analysis of SA and its applications, especially in reinforcement learning.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach

    cs.LG 2026-07 accept novelty 6.0 of 10

    A unified, elementary analysis gives O(1/k) mean-square and sub-Gaussian maximal concentration bounds for contractive stochastic approximation under multiplicative noise with unbounded iterates.

Reference graph

Works this paper leans on

126 extracted references · 14 canonical work pages · cited by 1 Pith paper

  1. [1]

    P., and Borkar, V

    Abounadi, J., Bertsekas, D. P., and Borkar, V. (2002). Stochastic approximation for nonexpan- sive maps: Application to q-learning algorithms.SIAM Journal on Control and Optimization, 41(1):1–22

    2002

  2. [2]

    M., Crump, T., and Far, B

    Afsar, M. M., Crump, T., and Far, B. (2022). Reinforcement learning based recommender systems: A survey.ACM Computing Surveys, 55(7):1–38

    2022

  3. [3]

    Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

    Agrawal, S., Maguluri, S. T., and Zubeldia, M. (2026). Concentration of general stochastic approximation under heavy-tailed Markovian noise.Preprint Arxiv: 2605.20999

    work page Pith review arXiv 2026

  4. [4]

    Baird, L. (1995). Residual algorithms: Reinforcement learning with function approximation. In Machine learning proceedings 1995, pages 30–37. Elsevier

    1995

  5. [5]

    Banach, S. (1922). Sur les op´ erations dans les ensembles abstraits et leur application aux ´ equations int´ egrales.Fund. math, 3(1):133–181

    1922

  6. [6]

    and Gupta, A

    Bansal, N. and Gupta, A. (2019). Potential-function proofs for gradient methods.Theory of Computing, 15(1):1–32. 27

    2019

  7. [7]

    and Laraki, R

    Baudin, L. and Laraki, R. (2022). Fictitious play and best-response dynamics in identical interest and zero-sum stochastic games. InInternational Conference on Machine Learning, pages 1664–1690. PMLR

    2022

  8. [8]

    (2017).First-Order Methods in Optimization

    Beck, A. (2017).First-Order Methods in Optimization. SIAM

    2017

Show all 126 references
  1. [9]

    Bellman, R. (1957). Dynamic programming.Press Princeton, New Jersey, 39

    1957

  2. [10]

    Bena¨ ım, M., Hofbauer, J., and Sorin, S. (2005). Stochastic approximations and differential inclusions.SIAM Journal on Control and Optimization, 44(1):328–348

    2005

  3. [11]

    Bena¨ ım, M., Hofbauer, J., and Sorin, S. (2006). Stochastic approximations and differential inclusions, part ii: Applications.Mathematics of Operations Research, 31(4):673–695

    2006

  4. [12]

    (2012).Adaptive Algorithms and Stochastic Approximations, volume 22

    Benveniste, A., M´ etivier, M., and Priouret, P. (2012).Adaptive Algorithms and Stochastic Approximations, volume 22. Springer Science & Business Media

    2012

  5. [13]

    Bertsekas, D. P. and Tsitsiklis, J. N. (1996).Neuro-Dynamic Programming. Athena Scientific

    1996

  6. [14]

    and Zhang, S

    Blaser, E. and Zhang, S. (2026). Asymptotic and finite sample analysis of nonexpansive stochastic approximations with markovian noise. InProceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 19764–19772

    2026

  7. [15]

    Border, K. C. (1985).Fixed-Point Theorems with Applications to Economics and Game Theory. Cambridge university press

    1985

  8. [16]

    Borkar, V., Chen, S., Devraj, A., Kontoyiannis, I., and Meyn, S. (2025). The ode method for asymptotic statistics in stochastic approximation and reinforcement learning.The Annals of Applied Probability, 35(2):936–982

    2025

  9. [17]

    Borkar, V. S. (2009).Stochastic Approximation: A Dynamical Systems Viewpoint, volume 48. Springer

    2009

  10. [18]

    Borkar, V. S. (2021). A concentration bound for contractive stochastic approximation.Systems & Control Letters, 153:104947

    2021

  11. [19]

    Borkar, V. S. and Meyn, S. P. (2000). The ODE method for convergence of stochastic approx- imation and reinforcement learning.SIAM Journal on Control and Optimization, 38(2):447–469

    2000

  12. [20]

    E., and Nocedal, J

    Bottou, L., Curtis, F. E., and Nocedal, J. (2018). Optimization methods for large-scale machine learning.Siam Review, 60(2):223–311

    2018

  13. [21]

    and Cominetti, R

    Bravo, M. and Cominetti, R. (2024). Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds.SIAM Journal on Control and Optimization, 62(1):191–219

    2024

  14. [22]

    C., Gerencs´ er, B., Gerencs´ er, L., and R´ asonyi, M

    Car` e, A., Cs´ aji, B. C., Gerencs´ er, B., Gerencs´ er, L., and R´ asonyi, M. (2026). Stochastic approximation in a markovian framework revisited: Lipschitz continuity of the poisson equation. Mathematics of Control, Signals, and Systems, pages 1–43

    2026

  15. [23]

    S., and Dodhia, P

    Chandak, S., Borkar, V. S., and Dodhia, P. (2022). Concentration of contractive stochastic approximation and reinforcement learning.Stochastic Systems, 12(4):411–430. 28

    2022

  16. [24]

    U., and Bambos, N

    Chandak, S., Haque, S. U., and Bambos, N. (2025). Finite-time bounds for two-time-scale stochastic approximation with arbitrary norm contractions and markovian noise. In2025 IEEE 64th Conference on Decision and Control (CDC), pages 6095–6101. IEEE

    2025

  17. [25]

    Chen, Z., Clarke, J.-P., and Maguluri, S. T. (2023). Target network and truncation overcome the deadly triad in q-learning.SIAM Journal on Mathematics of Data Science, 5(4):1078–1101

    2023

  18. [26]

    T., Shakkottai, S., and Shanmugam, K

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

    2020

  19. [27]

    T., Shakkottai, S., and Shanmugam, K

    Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2021). Finite-sample analysis of off-policy td-learning via generalized bellman operators.Advances in Neural Information Processing Systems, 34:21440–21452

    2021

  20. [28]

    T., Shakkottai, S., and Shanmugam, K

    Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2024). A Lyapunov the- ory for finite-sample guarantees of Markovian stochastic approximation.Operations Research, 72(4):1352–1367

    2024

  21. [29]

    T., and Zubeldia, M

    Chen, Z., Maguluri, S. T., and Zubeldia, M. (2025a). Concentration of contractive stochastic approximation: Additive and multiplicative noise.The Annals of Applied Probability, 35(2):1298– 1352

  22. [30]

    T., Clarke, J.-P., and Maguluri, S

    Chen, Z., Zhang, S., Doan, T. T., Clarke, J.-P., and Maguluri, S. T. (2022). Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning.Au- tomatica, 146:110623

    2022

  23. [31]

    U., and Maguluri, S

    Chen, Z., Zhang, S., Zhang, Z., Haque, S. U., and Maguluri, S. T. (2025b). A non-asymptotic theory of seminorm lyapunov stability: From deterministic to stochastic iterative algorithms. Preprint Arxiv:2502.14208

  24. [32]

    Chung, K. L. (1954). On a stochastic approximation method.The Annals of Mathematical Statistics, pages 463–483

    1954

  25. [33]

    Cutler, J., Diaz, M., and Drusvyatskiy, D. (2024). Stochastic approximation with decision- dependent distributions: Asymptotic normality and optimality.Journal of Machine Learning Research, 25(90):1–49

    2024

  26. [34]

    Dalal, G., Thoppe, G., Sz¨ or´ enyi, B., and Mannor, S. (2018). Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. InConference On Learning Theory, pages 1199–1233. PMLR

    2018

  27. [35]

    Davis, D., Drusvyatskiy, D., and Jiang, L. (2024). Asymptotic normality and optimality in nonsmooth stochastic approximation.The Annals of Statistics, 52(4):1485–1508

    2024

  28. [36]

    Deb, R., Ganesh, S., and Bhatnagar, S. (2025). Multi-timescale stochastic approximation: Stability and convergence.Preprint Arxiv:2112.03515. 29

    2025

  29. [37]

    Doan, T. T. (2021). Finite-time analysis and restarting scheme for linear two-time-scale stochastic approximation.SIAM Journal on Control and Optimization, 59(4):2798–2819

    2021

  30. [38]

    Doan, T. T. (2022a). Finite-time analysis of markov gradient descent.IEEE Transactions on Automatic Control, 68(4):2140–2153

  31. [39]

    Doan, T. T. (2022b). Nonlinear two-time-scale stochastic approximation: Convergence and finite-time performance.IEEE Transactions on Automatic Control, 68(8):4695–4705

  32. [40]

    (2018).Markov Chains, volume 4

    Douc, R., Moulines, E., Priouret, P., and Soulier, P. (2018).Markov Chains, volume 4. Springer

    2018

  33. [41]

    C., Agarwal, A., Johansson, M., and Jordan, M

    Duchi, J. C., Agarwal, A., Johansson, M., and Jordan, M. I. (2012). Ergodic mirror descent. SIAM Journal on Optimization, 22(4):1549–1578

    2012

  34. [42]

    Durmus, A., Moulines, E., Naumov, A., and Samsonov, S. (2025). Finite-time high-probability bounds for polyak–ruppert averaged iterates of linear stochastic approximation.Mathematics of Operations Research, 50(2):935–964

    2025

  35. [43]

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

    2021

  36. [44]

    (2019).Probability: Theory and Examples, volume 49

    Durrett, R. (2019).Probability: Theory and Examples, volume 49. Cambridge university press

    2019

  37. [45]

    Espeholt, L., Soyer, H., Munos, R., Simonyan, K., Mnih, V., Ward, T., Doron, Y., Firoiu, V., Harley, T., Dunning, I., et al. (2018). Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. InInternational Conference on Machine Learning, pages...

    2018

  38. [46]

    and Mansour, Y

    Even-Dar, E. and Mansour, Y. (2003). Learning rates forQ-learning.Journal of Machine Learning Research, 5(Dec):1–25

    2003

  39. [47]

    Fabian, V. (1968). On asymptotic normality in stochastic approximation.The Annals of Mathematical Statistics, pages 1327–1332

    1968

  40. [48]

    Fort, G. (2015). Central limit theorems for stochastic approximation with controlled markov chain dynamics.ESAIM: Probability and Statistics, 19:60–80

    2015

  41. [49]

    Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. (2013). Minimax pac bounds on the sample complexity of reinforcement learning with a generative model.Machine learning, 91(3):325–349

    2013

  42. [50]

    Glynn, P. W. and Iglehart, D. L. (1989). Importance sampling for stochastic simulations. Management science, 35(11):1367–1392

    1989

  43. [51]

    and Thoppe, G

    Gopalan, A. and Thoppe, G. (2023). Demystifying approximate reinforcement learning with ϵ-greedy exploration: A differential inclusion view

    2023

  44. [52]

    Gosavi, A. (2006). Boundedness of iterates inQ-learning.Systems & control letters, 55(4):347– 349. 30

    2006

  45. [53]

    and Nemirovski, A

    Guzm´ an, C. and Nemirovski, A. (2015). On lower complexity bounds for large-scale smooth convex optimization.Journal of Complexity, 31(1):1–14

    2015

  46. [54]

    Haddad, W. M. and Chellaboina, V. (2011).Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach. Princeton University Press

    2011

  47. [55]

    Haque, S. U. and Maguluri, S. T. (2025). Stochastic approximation with unbounded markovian noise: A general-purpose theorem. InProceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 ofProceedings of Machine Learning Research, pag...

    2025

  48. [56]

    G., Stepleton, T., and Munos, R

    Harutyunyan, A., Bellemare, M. G., Stepleton, T., and Munos, R. (2016). Q(λ) with off- policy corrections. InInternational Conference on Algorithmic Learning Theory, pages 305–320. Springer

    2016

  49. [57]

    Harvey, N. J. A., Liaw, C., and Randhawa, S. (2019). Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent.Preprint Arxiv:1909.00843

    2019

  50. [58]

    and Kale, S

    Hazan, E. and Kale, S. (2014). Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization.Journal of Machine Learning Research, 15:2489–2512

    2014

  51. [59]

    and Sandholm, W

    Hofbauer, J. and Sandholm, W. H. (2002). On the global convergence of stochastic fictitious play.Econometrica, 70(6):2265–2294

    2002

  52. [60]

    M., and Jordan, M

    Jin, C., Netrapalli, P., Ge, R., Kakade, S. M., and Jordan, M. I. (2019). A short note on concentration inequalities for random vectors with subgaussian norm.Preprint arXiv:1902.03736

    2019 arXiv

  53. [61]

    Kaledin, M., Moulines, E., Naumov, A., Tadic, V., and Wai, H.-T. (2020). Finite time anal- ysis of linear two-timescale stochastic approximation with markovian noise. InConference on Learning Theory, pages 2144–2203. PMLR

    2020

  54. [62]

    Khalil, H. K. and Grizzle, J. W. (2002).Nonlinear Systems, volume 3. Prentice hall Upper Saddle River, NJ

    2002

  55. [63]

    Khodadadian, S., Sharma, P., Joshi, G., and Maguluri, S. T. (2022). Federated reinforcement learning: Linear speedup under markovian sampling. InProceedings of the 39th International Conference on Machine Learning, volume 162 ofProceedings of Machine Learning Research, pages 1...

    2022

  56. [64]

    Konda, V. R. and Tsitsiklis, J. N. (2000). Actor-critic algorithms. InAdvances in neural information processing systems, pages 1008–1014. Citeseer

    2000

  57. [65]

    Konda, V. R. and Tsitsiklis, J. N. (2004). Convergence rate of linear two-time-scale stochastic approximation.The Annals of Applied Probability, 14(2):796–819

    2004

  58. [66]

    Kushner, H. J. and Clark, D. S. (2012).Stochastic Approximation Methods for Constrained and Unconstrained Systems, volume 26. Springer Science & Business Media

    2012

  59. [67]

    and Lefschetz, S

    La Salle, J. and Lefschetz, S. (2012).Stability by Liapunov’s Direct Method with Applications, volume 4. Elsevier. 31

    2012

  60. [68]

    and Szepesv´ ari, C

    Lakshminarayanan, C. and Szepesv´ ari, C. (2018). Linear stochastic approximation: How far does constant step-size and iterate averaging go? InProceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, volume 84 ofProceedings of Machine...

    2018

  61. [69]

    (2020).First-Order and Stochastic Optimization Methods for Machine Learning

    Lan, G. (2020).First-Order and Stochastic Optimization Methods for Machine Learning. Springer

    2020

  62. [70]

    Lauand, C. K. and Meyn, S. (2024). Revisiting step-size assumptions in stochastic approxi- mation.Preprint Arxiv:2405.17834

    2024

  63. [71]

    Levin, D. A. and Peres, Y. (2017).Markov Chains and Mixing Times, volume 107. American Mathematical Soc

    2017

  64. [72]

    Levine, S., Finn, C., Darrell, T., and Abbeel, P. (2016). End-to-end training of deep visuomotor policies.Journal of Machine Learning Research, 17(39):1–40

    2016

  65. [73]

    Li, G., Cai, C., Chen, Y., Gu, Y., Wei, Y., and Chi, Y. (2021). Tightening the dependence on horizon in the sample complexity of q-learning. InProceedings of the 38th International Conference on Machine Learning, volume 139 ofProceedings of Machine Learning Research, pages 629...

    2021

  66. [74]

    Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. (2024a). Is q-learning minimax optimal? a tight sample complexity analysis.Operations Research, 72(1):222–236

  67. [75]

    Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020a). Breaking the sample size barrier in model-based reinforcement learning with a generative model.Advances in neural information processing systems, 33

  68. [76]

    Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020b). Sample complexity of asynchronous q- learning: Sharper analysis and variance reduction. InAdvances in Neural Information Processing Systems, volume 33, pages 7031–7043. Curran Associates, Inc

  69. [77]

    Li, G., Wu, W., Chi, Y., Ma, C., Rinaldo, A., and Wei, Y. (2024b). High-probability sample complexities for policy evaluation with linear function approximation.IEEE Transactions on Information Theory, 70(8):5969–5999

  70. [78]

    Li, Y., Lan, G., and Zhao, T. (2022). First-order policy optimization for robust markov decision process.Preprint Arxiv:2209.10579

    2022

  71. [79]

    Liu, X., Xie, Z., and Zhang, S. (2025). Linear q-learning does not diverge inl 2: Convergence rates to a bounded set. InProceedings of the 42nd International Conference on Machine Learning, volume 267 ofProceedings of Machine Learning Research, pages 39871–39897. PMLR

    2025

  72. [80]

    Ljung, L. (1977). Analysis of recursive stochastic algorithms.IEEE transactions on automatic control, 22(4):551–575

    1977

  73. [81]

    Lou, Z., Zhu, W., and Wu, W. B. (2022). Beyond sub-gaussian noises: Sharp concentration analysis for stochastic gradient descent.Journal of Machine Learning Research. 32

    2022

  74. [82]

    Mertikopoulos, P., Hsieh, Y.-P., and Cevher, V. (2024). A unified stochastic approximation framework for learning in games.Mathematical Programming, 203:559–609

    2024

  75. [83]

    A., Veness, J., Bellemare, M

    Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015). Human-level control through deep reinforcement learning.nature, 518(7540):529–533

    2015

  76. [84]

    J., Wainwright, M

    Mou, W., Li, C. J., Wainwright, M. J., Bartlett, P. L., and Jordan, M. I. (2020). On lin- ear stochastic approximation: Fine-grained polyak-ruppert and non-asymptotic concentration. InProceedings of Thirty Third Conference on Learning Theory, volume 125 ofProceedings of Machin...

    2020

  77. [85]

    and Bach, F

    Moulines, E. and Bach, F. (2011). Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning.Advances in neural information processing systems, 24:451–459

    2011

  78. [86]

    Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. G. (2016). Safe and efficient off-policy reinforcement learning. InProceedings of the 30th International Conference on Neural Information Processing Systems, pages 1054–1062

    2016

  79. [87]

    and Chen, Z

    Nanda, P. and Chen, Z. (2025). A minimal-assumption analysis of q-learning with time-varying policies.Preprint Arxiv:2510.16132

    2025 arXiv

  80. [88]

    Nguyen, Q. D. T., Nguyen, D. A., Nguyen, H. H., and Maguluri, S. T. (2026). Almost sure convergence of nonlinear stochastic approximation: An interplay of noise and step size.Preprint Arxiv:2602.10580

    2026

  81. [89]

    Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. (2022). Training language models to follow instructions with human feedback.Advances in neural information processing systems, 35:27730–27744

    2022

  82. [90]

    Patil, G., L.A., P., Nagaraj, D., and Precup, D. (2023). Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, v...

    2023

  83. [91]

    Pham, T., Rinaldo, A., and Sarkar, P. (2025). Time-uniform concentration bounds for iterative algorithms.Preprint Arxiv:2511.18273

    2025

  84. [92]

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

    1992

  85. [93]

    A., Korda, N., and Munos, R

    Prashanth, L. A., Korda, N., and Munos, R. (2021). Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling.Machine Learning, 110:559–618

    2021

  86. [94]

    S., and Singh, S

    Precup, D., Sutton, R. S., and Singh, S. P. (2000). Eligibility traces for off-policy policy evaluation. InProceedings of the Seventeenth International Conference on Machine Learning, pages 759–766. 33

    2000

  87. [95]

    Puterman, M. L. (2014).Markov Decision Processes: Discrete Stochastic Dynamic Program- ming. John Wiley & Sons

    2014

  88. [96]

    Qian, X., Xie, Z., Liu, X., and Zhang, S. (2024). Almost sure convergence rates and concen- tration of stochastic approximation and reinforcement learning with markovian noise.Preprint Arxiv:2411.13711

    2024

  89. [97]

    and Wierman, A

    Qu, G. and Wierman, A. (2020). Finite-time analysis of asynchronous stochastic approximation and q-learning. InConference on Learning Theory, pages 3185–3205. PMLR

    2020

  90. [98]

    Rakhlin, A., Shamir, O., and Sridharan, K. (2012). Making gradient descent optimal for strongly convex stochastic optimization. InInternational Conference on Machine Learning

    2012

  91. [99]

    and Monro, S

    Robbins, H. and Monro, S. (1951). A stochastic approximation method.The Annals of Mathematical Statistics, pages 400–407

    1951

  92. [100]

    Ruppert, D. (1988). Efficient estimations from a slowly convergent robbins-monro process. Technical Report 781, Cornell University, School of Operations Research and Industrial Engi- neering. Revised December 1988

    1988

  93. [101]

    Ryu, E. K. and Boyd, S. (2016). Primer on monotone operator methods.Appl. Comput. Math, 15(1):3–43

    2016

  94. [102]

    Sacks, J. (1958). Asymptotic distribution of stochastic approximation procedures.The Annals of Mathematical Statistics, 29(2):373–405

    1958

  95. [103]

    Samsonov, S., Tiapkin, D., Naumov, A., and Moulines, E. (2024). Improved high-probability bounds for the temporal difference learning algorithm via exponential stability. InProceedings of Thirty Seventh Conference on Learning Theory, volume 247 ofProceedings of Machine Learnin...

    2024

  96. [104]

    O., Parise, F., and Ozdaglar, A

    Sayin, M. O., Parise, F., and Ozdaglar, A. (2022). Fictitious play in zero-sum stochastic games.SIAM Journal on Control and Optimization, 60(4):2095–2114

    2022

  97. [105]

    Schweitzer, P. J. (1971). Iterative solution of the functional equations of undiscounted Markov renewal programming.Journal of Mathematical Analysis and Applications, 34(3):495–501

    1971

  98. [106]

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

    2012

  99. [107]

    J., Guez, A., Sifre, L., Van Den Driessche, G., Schrit- twieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al

    Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrit- twieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of go with deep neural networks and tree search.nature, 529(7587):484

    2016

  100. [108]

    Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017). Mastering the game of go without human knowledge. Nature, 550(7676):354. 34

    2017

  101. [109]

    S., and Bambos, N

    Singh, R., Chandak, S., Moulines, E., Borkar, V. S., and Bambos, N. (2026). Regret and sample complexity of online q-learning via concentration of stochastic approximation with time- inhomogeneous markov chains.Preprint Arxiv:2602.16274

    2026 arXiv

  102. [110]

    and Ying, L

    Srikant, R. and Ying, L. (2019). Finite-time error bounds for linear stochastic approximation and td-learning. InConference on Learning Theory, pages 2803–2830

    2019

  103. [111]

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

    1988

  104. [112]

    Sutton, R. S. (1999). Open theoretical questions in reinforcement learning. InEuropean Conference on Computational Learning Theory, pages 11–17. Springer

    1999

  105. [113]

    Sutton, R. S. and Barto, A. G. (2018).Reinforcement Learning: An Introduction. MIT press

    2018

  106. [114]

    Telgarsky, M. (2022). Stochastic linear optimization never overfits with quadratically-bounded losses on general data. InConference on Learning Theory, pages 5453–5488. PMLR

    2022

  107. [115]

    and Borkar, V

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

    2019

  108. [116]

    Vapnik, V. N. (1999). An overview of statistical learning theory.IEEE transactions on neural networks, 10(5):988–999

    1999

  109. [117]

    (2018).High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47

    Vershynin, R. (2018).High-Dimensional Probability: An Introduction with Applications in Data Science, volume 47. Cambridge university press

    2018

  110. [118]

    Wainwright, M. J. (2019a).High-Dimensional Statistics: A Non-Asymptotic Viewpoint, vol- ume 48. Cambridge university press

  111. [119]

    Wainwright, M. J. (2019b). Stochastic approximation with cone-contractive operators: Sharp ℓ∞-bounds for q-learning. Technical Report arXiv:1905.06265, University of California, Berkeley

    1905 arXiv

  112. [120]

    Wang, S., Si, N., Blanchet, J., and Zhou, Z. (2023). A finite sample complexity bound for distributionally robust q-learning. InProceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 ofProceedings of Machine Learning Research, pa...

    2023

  113. [121]

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

    1992

  114. [122]

    and Guo, X

    Xu, D. and Guo, X. (2013). Fixed point analytical method for nonlinear differential equations. Journal of Computational and Nonlinear Dynamics, 8(1)

    2013

  115. [123]

    Xu, Y., Mondal, W., and Aggarwal, V. (2026). Finite-sample analysis of policy evaluation for robust average reward reinforcement learning.Advances in Neural Information Processing Systems, 38:151870–151915

    2026

  116. [124]

    and Doan, T

    Zeng, S. and Doan, T. T. (2024). Accelerated multi-time-scale stochastic approximation: Optimal complexity and applications in reinforcement learning and multi-agent games.Preprint Arxiv:2409.07767. 35

    2024

  117. [125]

    L., Chen, Y., and Xie, Q

    Zhang, Y., Huo, D. L., Chen, Y., and Xie, Q. (2024). Prelimit coupling and steady-state convergence of constant-stepsize nonsmooth contractive sa.SIGMETRICS Perform. Eval. Rev., 52(1):35–36

    2024

  118. [126]

    and Xie, Q

    Zhang, Y. and Xie, Q. (2024). Constant stepsize q-learning: Distributional convergence, bias and extrapolation.Reinforcement Learning Journal, 3:1168–1210. 36 Appendices A Proof of All Technical Results in Section 2 A.1 Proof of Proposition 2.1 (1) It is clear from the definit...

    2024

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.