Pith. sign in

REVIEW 4 major objections 3 minor 29 references

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

T0 review · 4 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read Allowing the step-size offset to grow as log(1/δ) yields the first sub-Gaussian-tailed all-time concentration bound for contractive stochastic approximation under multiplicative noise.

desk verdict The mean-square half is a clean and useful simplification, but the advertised concentration bound is not proven as written: the event-inclusion logic in Lemmas 7–8 is inverted, and that is the load-bearing part of Theorem 2. read the letter →

arxiv 2607.17595 v1 pith:WJFGQIQX submitted 2026-07-20 cs.LG cs.SYeess.SYmath.OC

Siddharth Chandak This is my paper · ORCID
classification cs.LGcs.SYeess.SYmath.OC MSC 62L2060G4260E15
keywords stochasticapproximationmultiplicativenoiseconcentrationboundmean-squareerrorsub-GaussiantailAzuma-HoeffdingLyapunovdriftreinforcementlearning
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 gives a unified, elementary proof of both mean-square and high-probability bounds for stochastic approximation (SA) when the update map is contractive in an arbitrary norm and the noise can scale with the norm of the current iterate. The central technical move is to average the noise into an auxiliary sequence, so that the squared norm of the error satisfies a one-step Lyapunov drift inequality without any smoothing of the norm. For concentration, a probabilistic induction over 'good' events lets the author apply Azuma–Hoeffding to truncated martingale noise. The payoff is the first sub-Gaussian-tailed maximal (all-time) concentration bound for SA under multiplicative noise, at the price of a step-size offset that grows logarithmically with the confidence level. A companion impossibility result from prior work implies this δ-dependence is unavoidable.

What carries the argument

The averaged noise sequence ξ_{k+1}=(1−β_k)ξ_k+β_k M_{k+1} with auxiliary iterates z_k=x_k−ξ_k. It converts the original iteration into z_{k+1}=z_k+β_k(f(z_k)−z_k+Δ_k) with ||Δ_k||≤λ||ξ_k||, producing a one-step Lyapunov drift inequality for ||z_k−x*||^2_c directly, without constructing a Moreau envelope. The remaining bound on ||ξ_k|| is obtained by induction: deterministic in expectation for the mean-square bound, and probabilistic via 'good' events C_k and truncated noise M_{i+1}1_{C_i} for the concentration bound, which then allows Azuma–Hoeffding. The δ-dependent offset h=Ω(log(1/δ)) is what converts a Weibull tail into a sub-Gaussian tail.

What would settle it

Run TD(0) or Q-learning on a small MDP with a noise process constructed to satisfy ||M_{k+1}||^2 ≤ σ^2(1+||x_k||^2) a.s. but with a conditional variance that saturates the bound, and compare the all-time maximum of ||x_k−x*||^2 for h=c log(1/δ) versus a fixed h. If the δ-dependent h does not produce a sub-Gaussian tail (i.e., the bound's exceedance probability scales as exp(−c/δ) instead of δ), the central claim fails. Alternatively, a counterexample with a δ-independent step size achieving a sub-Gaussian tail would directly contradict the stated impossibility, but the proof invokes that impos

Watch

Extended reading notes

Core claim

Under a contractive map f with fixed point x*, iteration x_{k+1}=x_k+β_k(f(x_k)-x_k+M_{k+1}) with β_k=β/(k+h), if the martingale noise satisfies ||M_{k+1}||^2_c ≤ σ^2(1+||x_k||^2_c) almost surely, then for β≥4/(1−λ) and h=Ω(log(1/δ)) the squared error obeys ||x_k−x*||^2_c ≤ c_4 log(d(k+1)/δ)/(k+h) for all k≥0 with probability at least 1−π^2 δ/3. This is the first all-time (maximal) bound with a sub-Gaussian tail for multiplicative noise; prior work could only achieve Weibull tails, and an impossibility result shows that a sub-Gaussian tail cannot be obtained with a δ-independent step size. The same averaged-noise machinery also yields a mean-square bound O(1/(k+h)) matching the best known ra

Load-bearing premise

The proof rests on the almost-sure multiplicative noise bound ||M_{k+1}||^2_c ≤ σ^2(1+||x_k||^2_c) a.s. (Assumption 3): without it the truncated noise has no finite exponential moments and the Azuma–Hoeffding step in Lemma 9 has nothing to bite on.

Editorial extensions

If this is right

  • For ℓ∞-contractive operators such as Q-learning, the concentration bound is O(σ^2 log(d(k+1)/δ)/((1−λ)^3(k+h))), matching the mean-square rate up to the log(1/δ) factor.
  • A sub-Gaussian tail and a δ-independent step size cannot be achieved simultaneously for multiplicative noise; the paper matches prior impossibility by making h grow logarithmically with 1/δ.
  • Under additive (uniformly bounded) noise, the same proof recovers known sub-Gaussian bounds with a fixed h, showing the δ-dependence is specific to multiplicative noise.
  • The mean-square bound E[||x_k−x*||^2] ≤ c_2/(k+h) holds for arbitrary norm contractions, including the max norm used in many RL algorithms, at the same O(log d/k) rate as the Moreau-envelope method.

Reading between the lines

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

  • The same noise-averaging and probabilistic-induction template likely extends to Markovian noise and to non-expansive or two-timescale algorithms (e.g., RVI or SSP Q-learning), where unbounded iterates are the norm; the paper sketches these directions but does not prove them.
  • The δ-dependent step size can be interpreted as a burn-in phase: choosing a fixed h moves the bound's start time to k_0=Ω(log(1/δ)), so the paper's result is equivalent to a trade-off between early-time coverage and tail sharpness.
  • A concrete testable prediction: for any multiplicative-noise SA instance satisfying Assumption 3, the maximal squared error over a simulated long trajectory should show log(1/δ) scaling when h is set to c log(1/δ), and a heavier tail when h is fixed.
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

4 major / 3 minor

Summary. The paper studies stochastic approximation (SA) under arbitrary-norm contractive maps and multiplicative noise, with iterates that are not a priori bounded. The authors introduce an averaged noise sequence and auxiliary iterates to obtain a one-step Lyapunov drift inequality for the normed error without smoothing the norm, and then use inductive bounds on the averaged noise. The main advertised result is a maximal (all-time) concentration bound with sub-Gaussian tail, obtained by allowing the step-size offset h to grow logarithmically in 1/delta. The mean-square bound (Theorem 1) and the additive-noise results are also presented. The paper is clearly written and the proposed technique is elegant, but the concentration proof as written contains a systematic complement/event-direction error in Lemmas 7 and 8 and in the final step of Theorem 2.

Significance. If the concentration proof is corrected, the paper would make a substantial contribution: it removes the Moreau-envelope machinery for arbitrary-norm contractions and, more importantly, gives the first sub-Gaussian-tailed maximal concentration bound for SA under multiplicative noise, with the confidence-dependent step-size offset placed exactly outside the impossibility regime identified by Chen et al. [15]. The proof is elementary, has no fitted parameters, and supplies explicit constants; the mean-square part appears sound. However, the concentration argument as written does not establish Theorem 2, because it bounds the union of the good events rather than its complement. The errors are mechanical to repair, so I view this as a major revision rather than a rejection.

major comments (4)
  1. [Section 3.2, Lemma 7(a)] The proof derives A_k ∩ B_k ⊆ C_k and then claims, 'or equivalently, C_k ⊆ A_k ∪ B_k.' This equivalence is false: A∩B⊆C is equivalent to C^c ⊆ A^c ∪ B^c, not to C⊆A∪B. The subsequent decomposition is therefore applied to ∪(A_k∪B_k), the union of the 'good' events, whereas Theorem 2 requires a bound on ∪ C_k^c. Moreover, the first-time decomposition in Lemma 7(a) uses F_k = ∩_{i<k}(A_i∩B_i); this is the correct F_k only if the event being decomposed is ∪(A_k^c∪B_k^c), not ∪(A_k∪B_k). The proof chain from Lemma 7 to Theorem 2 therefore does not establish the theorem as written.
  2. [Section 3.2, Lemma 8(a)] The lemma states that F_k ⊆ A_k implies P(F_k ∩ A_k) = 0. If F_k ⊆ A_k, then F_k ∩ A_k = F_k, whose probability is not zero in general. What the corrected decomposition needs is P(F_k ∩ A_k^c) = 0, and this is indeed true because F_k ⊆ A_k. The statement and proof must be restated with the complement; as written, the lemma asserts a different and false identity.
  3. [Appendix B.2, Lemma 8(b)] The inequality in Lemma 8(b) has the wrong direction. B_k is defined as {||ξ_k||_c^2 ≤ v_k}, so on F_k ∩ B_k the untruncated sum is at most v_k; since the indicators 1_{C_i} are equal to 1 on F_k, the same event is contained in {||Σ tilde M_{i+1}||^2 ≤ v_k}, not in {||Σ tilde M_{i+1}||^2 > v_k}. Lemma 9 bounds the latter tail event, so it cannot be applied to F_k ∩ B_k. The event whose small probability the induction requires is F_k ∩ B_k^c, which is contained in {||Σ tilde M_{i+1}||^2 > v_k}. This is a load-bearing error in the truncation argument.
  4. [Appendix B.4, proof of Theorem 2] The final display reads P(∪_{k=0}^∞ C_k) ≤ Σ 2δ/(k+1)^2, and the theorem is then declared proved. Since C_k is the good event, the small-probability event needed is ∪_{k≥0} C_k^c. As written, the proof bounds a probability that is typically close to 1. This is the same complement error as in Lemma 7 and should be corrected throughout Section 3.2 and Appendix B: the objective is to bound P(∪ C_k^c), and the decomposition should be over F_k ∩ (A_k^c ∪ B_k^c).
minor comments (3)
  1. [Section 1.1 and Section 3.2] The text says the goal is to upper bound P(⋃ C_k); it should say P(⋃ C_k^c). This typo propagates into Lemma 7 and the proof of Theorem 2.
  2. [Appendix B.4, constants in Theorem 2] The stated theorem reads 'there exist constants c3 and c4 such that if h ≥ c3', but the proof defines c4 as a function of h and δ, with c4 = 2h||x0-x*||^2/log(d/δ) + O(1). For arbitrary h ≥ c3, no h-independent c4 can satisfy the displayed bound at k=0. The theorem should make the quantifier explicit, e.g., take h = Θ(c3) or state that c4 may depend on h and δ; the current wording is ambiguous.
  3. [Lemma 7(a), second equality] After correcting the complements, the first-time decomposition should be written as ∪_{k≥0}(A_k^c ∪ B_k^c) = ∪_{k≥0}( (∩_{i<k}(A_i∩B_i)) ∩ (A_k^c ∪ B_k^c) ). This clarifies the intended induction and makes the role of F_k transparent.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is self-contained; known self-citations are not load-bearing.

full rationale

The manuscript's derivation is a direct proof from Assumptions 1-3: Lemma 3 gives a one-step Lyapunov drift inequality for the auxiliary error ||z_k - x*||_c^2, Lemmas 4-6 bootstrap the mean-square bound by an induction on E[1 + ||x_i||_c^2], and Lemmas 7-9 combine Azuma-Hoeffding with the truncated noise M~_{i+1} = M_{i+1} 1_{C_i} to control the concentration event. No parameter is fitted to data, no empirical quantity is called a prediction, and the target bound (Theorem 2) does not enter as an assumption: the constants Gamma_3, c_3, c_4 are explicit functions of sigma, beta, lambda, the norm-equivalence constants, and the initial data, and are selected after the inequalities are proved. The delta-dependent offset h = Omega(log(1/delta)) is a disclosed design condition, and the comparison/impossibility result attributed to Chen et al. [15] is external (no author overlap) and not required for the proof. The few self-citations ([8], [10], [11]) appear only in related-work and future-direction discussion, so they are not load-bearing. If taken literally, the set inclusions in Lemmas 7-8 appear to involve complements inconsistently and may indicate a proof gap or typesetting issue; that is a correctness concern, not circularity, because it does not identify the theorem's conclusion with an assumption.

Assumptions & free parameters 1 free parameters · 5 assumptions · 3 invented entities

No data are fitted and no physical entities are postulated. The only hand-chosen quantity is the delta-dependent offset h, which is the mechanism enabling the sub-Gaussian tail. The rest of the analysis rests on stated problem assumptions and standard inequalities.

free parameters (1)
  • step-size offset h = h >= 2*beta + A*log(A*d/delta)+1, with A = 672*zeta_2*beta*sigma^2/lambda'^2
    The sub-Gaussian tail is obtained by allowing h to grow logarithmically with 1/delta. This is the paper's key design choice and is not determined by data.
assumptions (5)
  • domain assumption Assumption 1: f is a lambda-contraction in the arbitrary norm ||.||_c
    Defines the class of mappings and ensures a unique fixed point x* via the Banach fixed-point theorem.
  • domain assumption Assumptions 2 and 3: M_{k+1} is a martingale difference sequence with multiplicative second-moment or a.s. bound
    The multiplicative-noise hypothesis is the setting of the paper; the a.s. version is needed for the Azuma truncation step in the concentration proof.
  • standard math Finite-dimensional norm equivalence between ||.||_c, l2, and l_infinity
    Used in Lemma 4 and Lemma 9 to convert bounds between norms; the constants zeta_1 and zeta_2 come from this equivalence.
  • standard math Azuma-Hoeffding inequality for bounded martingale differences
    Core concentration tool in Lemma 9 after truncating the noise by the good events.
  • standard math Banach fixed-point theorem
    Assumption 1 plus completeness of R^d implies existence and uniqueness of the fixed point x* used throughout.
invented entities (3)
  • Averaged noise sequence xi_k
    purpose: Reformulate the SA iteration so a one-step Lyapunov drift inequality can be written directly on the normed error.
    A proof device defined by xi_{k+1}=(1-beta_k)xi_k+beta_k M_{k+1}; it has no external falsifiable handle.
  • Auxiliary iterates z_k = x_k - xi_k
    purpose: Carry the contraction structure of the algorithm while leaving the averaged noise to be bounded separately.
    A purely mathematical construction used in Lemma 3; not a physical or algorithmic quantity.
  • Good events C_k, A_k, B_k
    purpose: Enable probabilistic induction by controlling the iterates on the event that Azuma-Hoeffding is applied to the truncated noise.
    Threshold-based proof events defined in Section 3.2; they have no meaning outside the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach." pith.science (2026). https://pith.science/paper/WJFGQIQX

@misc{pith2026260717595,
  author       = {Pith},
  title        = {Pith review of: Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WJFGQIQX}},
  note         = {Machine review of arXiv:2607.17595}
}
abstract

We establish mean-square and concentration bounds for stochastic approximation (SA) with arbitrary norm contractive mappings, under a multiplicative noise model where the noise may scale affinely with the norm of the iterates, and the iterates are potentially unbounded. These settings arise in reinforcement learning, where operators are often contractive in the $\ell_\infty$ norm and the noise scales with the iterates. To address the arbitrary norm, earlier works replace the non-smooth squared norm with a smooth Lyapunov function constructed via the generalized Moreau envelope. For concentration analysis, these works handle multiplicative noise and unbounded iterates through a multi-stage bootstrapping argument that starts from a time-varying worst-case bound and iteratively refines it. We instead present a unified and elementary analysis that yields both bounds. Using an averaged noise sequence and corresponding auxiliary iterates, we obtain a one-step Lyapunov drift inequality for the normed error directly, without smoothing the norm or constructing an envelope. For the mean-square bound, we combine this drift inequality with an induction argument showing that the iterates remain bounded in expectation. For the concentration bound, we develop a probabilistic induction over a sequence of "good" events on which the iterates are controlled, allowing the standard Azuma-Hoeffding bound to be applied. Our approach yields the first sub-Gaussian tailed maximal (all-time) concentration bound for SA under multiplicative noise, by allowing the stepsize to depend logarithmically on the confidence level. Beyond the specific setting considered here, we discuss the generalizability of these proof techniques to other noise models and iterative algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 3 linked inside Pith

  1. [15]

    Concentration of contractive stochastic approximation: Additive and multiplicative noise

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

    2025

  2. [1]

    Learning algorithms for markov decision processes with average cost

    Abounadi, J., Bertsekas, D., Borkar, V.S., 2001. Learning algorithms for markov decision processes with average cost. SIAM Journal on Control and Optimization 40, 681–698

    2001

  3. [2]

    Concentration of general stochastic approximation under heavy-tailed markovian noise

    Agrawal, S., Maguluri, S.T., Zubeldia, M., 2026. Concentration of general stochastic approximation under heavy-tailed markovian noise. URL:https://arxiv.org/abs/2605.20999,arXiv:2605.20999

    arXiv 2026

  4. [3]

    First-Order Methods in Optimization

    Beck, A., 2017. First-Order Methods in Optimization. Society for Industrial and Applied Mathematics, Philadelphia, PA

    2017

  5. [4]

    Adaptive algorithms and stochastic approximations

    Benveniste, A., Métivier, M., Priouret, P., 2012. Adaptive algorithms and stochastic approximations. Springer Science & Business Media

    2012

  6. [5]

    A finite time analysis of temporal difference learning with linear function approximation, in: Proceedings of the 31st Conference On Learning Theory, PMLR

    Bhandari, J., Russo, D., Singal, R., 2018. A finite time analysis of temporal difference learning with linear function approximation, in: Proceedings of the 31st Conference On Learning Theory, PMLR. pp. 1691–1692

    2018

  7. [6]

    Borkar,V.,2022.StochasticApproximation:ADynamicalSystemsViewpoint:SecondEdition.TextsandReadingsinMathematics,Hindustan Book Agency

    2022

  8. [7]

    Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds

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

    2024

Show all 29 references
  1. [8]

    A concentration bound for td(0) with function approximation

    Chandak, S., Borkar, V.S., 2026. A concentration bound for td(0) with function approximation. Stochastic Systems 16, 44–60

    2026

  2. [9]

    Concentration of contractive stochastic approximation and reinforcement learning

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

    2022

  3. [10]

    Finite-timeboundsfortwo-time-scalestochasticapproximationwitharbitrarynormcontractions and markovian noise, in: 2025 IEEE 64th Conference on Decision and Control (CDC), pp

    Chandak,S.,Haque,S.U.,Bambos,N.,2025. Finite-timeboundsfortwo-time-scalestochasticapproximationwitharbitrarynormcontractions and markovian noise, in: 2025 IEEE 64th Conference on Decision and Control (CDC), pp. 6095–6101

    2025

  4. [11]

    Heavy-tailedandlong-rangedependentnoiseinstochasticapproximation:Afinite-time analysis

    Chandak,S.,Yadav,A.,Ozgur,A.,Bambos,N.,2026. Heavy-tailedandlong-rangedependentnoiseinstochasticapproximation:Afinite-time analysis. URL:https://arxiv.org/abs/2603.19648,arXiv:2603.19648

    2026

  5. [12]

    Non-asymptotic convergence of stochastic iterative algorithms: A lyapunov framework

    Chen, Z., Maguluri, S.T., 2026. Non-asymptotic convergence of stochastic iterative algorithms: A lyapunov framework. URL:https: //arxiv.org/abs/2605.31309,arXiv:2605.31309

    2026 arXiv

  6. [13]

    Finite-sampleanalysisofcontractivestochasticapproximationusingsmooth convex envelopes, in: Advances in Neural Information Processing Systems, Curran Associates, Inc

    Chen,Z.,Maguluri,S.T.,Shakkottai,S.,Shanmugam,K.,2020. Finite-sampleanalysisofcontractivestochasticapproximationusingsmooth convex envelopes, in: Advances in Neural Information Processing Systems, Curran Associates, Inc.. pp. 8223–8234

    2020

  7. [14]

    A lyapunov theory for finite-sample guarantees of markovian stochastic approximation

    Chen, Z., Maguluri, S.T., Shakkottai, S., Shanmugam, K., 2024. A lyapunov theory for finite-sample guarantees of markovian stochastic approximation. Operations Research 72, 1352–1367

    2024

  8. [16]

    Finite sample analyses for TD(0) with function approximation, in: Proceedings of the AAAI Conference on Artificial Intelligence

    Dalal, G., Szörényi, B., Thoppe, G., Mannor, S., 2018. Finite sample analyses for TD(0) with function approximation, in: Proceedings of the AAAI Conference on Artificial Intelligence

    2018

  9. [17]

    Tight high probability bounds for linear stochastic approximation with fixed stepsize, in: Advances in Neural Information Processing Systems, Curran Associates, Inc

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

    2021

  10. [18]

    Stochastic Approximation and Recursive Algorithms and Applications

    Kushner, H., Yin, G., 2013. Stochastic Approximation and Recursive Algorithms and Applications. Stochastic Modelling and Applied Probability, Springer New York

    2013

  11. [19]

    Isq-learningminimaxoptimal?atightsamplecomplexityanalysis

    Li,G.,Cai,C.,Chen,Y.,Wei,Y.,Chi,Y.,2023. Isq-learningminimaxoptimal?atightsamplecomplexityanalysis. OperationsResearch72, 222–236

    2023

  12. [20]

    Sample complexity of asynchronousQ-learning: Sharper analysisand variance reduction,in: Advances in Neural Information Processing Systems, Curran Associates, Inc

    Li, G.,Wei, Y., Chi, Y.,Gu, Y., Chen,Y., 2020. Sample complexity of asynchronousQ-learning: Sharper analysisand variance reduction,in: Advances in Neural Information Processing Systems, Curran Associates, Inc.. pp. 7031–7043

    2020

  13. [21]

    Non-asymptotic analysis of stochastic approximation algorithms for machine learning, in: Advances in Neural Information Processing Systems, Curran Associates, Inc

    Moulines, E., Bach, F., 2011. Non-asymptotic analysis of stochastic approximation algorithms for machine learning, in: Advances in Neural Information Processing Systems, Curran Associates, Inc

    2011

  14. [22]

    Robuststochasticapproximationapproachtostochasticprogramming

    Nemirovski,A.,Juditsky,A.,Lan,G.,Shapiro,A.,2009. Robuststochasticapproximationapproachtostochasticprogramming. SIAMJournal on optimization 19, 1574–1609

    2009

  15. [23]

    Time-uniform concentration bounds for iterative algorithms

    Pham, T., Rinaldo, A., Sarkar, P., 2025. Time-uniform concentration bounds for iterative algorithms. URL:https://arxiv.org/abs/ 2511.18273,arXiv:2511.18273

    2025

  16. [24]

    Almost sure convergence rates and concentration of stochastic approximation and reinforcement learning with markovian noise

    Qian, X., Xie, Z., Liu, X., Zhang, S., 2024. Almost sure convergence rates and concentration of stochastic approximation and reinforcement learning with markovian noise. URL:https://arxiv.org/abs/2411.13711,arXiv:2411.13711

    2024 arXiv

  17. [25]

    Finite-time analysis of asynchronous stochastic approximation and Q-learning, in: Proceedings of Thirty Third Conference on Learning Theory, PMLR

    Qu, G., Wierman, A., 2020. Finite-time analysis of asynchronous stochastic approximation and Q-learning, in: Proceedings of Thirty Third Conference on Learning Theory, PMLR. pp. 3185–3205

    2020

  18. [26]

    Finite-timeerrorboundsforlinearstochasticapproximationandtdlearning,in:ProceedingsoftheThirty-Second Conference on Learning Theory, PMLR

    Srikant,R.,Ying,L.,2019. Finite-timeerrorboundsforlinearstochasticapproximationandtdlearning,in:ProceedingsoftheThirty-Second Conference on Learning Theory, PMLR. pp. 2803–2830

    2019

  19. [27]

    A concentration bound for stochastic approximation via Alekseev’s formula

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

    2019

  20. [28]

    An analysis of temporal-difference learning with function approximation

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

    1997

  21. [29]

    Q-learning

    Watkins, C.J., Dayan, P., 1992. Q-learning. Machine learning 8, 279–292. Page 17 of 17

    1992

Pith tools

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