Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set

Shangtong Zhang; Xinyu Liu; Zixuan Xie

REVIEW 2 major objections 5 minor 51 references

Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set

T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper proves that unmodified linear Q-learning converges in mean square to a bounded set, with explicit polynomial or exponential rates, under an epsilon-softmax behavior policy with adaptive temperature.

desk verdict The main theorem is false as stated without a full-column-rank condition on the features; fix that and this is a solid contribution with a reusable SA theorem. read the letter →

arxiv 2501.19254 v4 pith:Y4HIXO76 submitted 2025-01-31 cs.LG cs.AIstat.ML

Xinyu Liu , Zixuan Xie , Shangtong Zhang This is my paper · ORCID

classification cs.LGcs.AIstat.ML MSC 62L2068Q3268T05

keywords linearQ-learningL2convergenceboundedsetstochasticapproximationMarkoviannoiseepsilon-softmaxbehaviorpolicytabularweightedBellmanoperator

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 aims to prove that linear Q-learning, in its unmodified form with no target network, projection, experience replay, or regularization, does not diverge in a quantitative sense: the expected squared weight norm decays to a bounded set at an explicit rate. It establishes the first L2 convergence rates for unmodified linear Q-learning, polynomial for learning-rate exponent 1 and exponential for exponents between 1/2 and 1. The only behavioral requirement is an epsilon-softmax exploration policy with an adaptive temperature, and the analysis avoids Bellman completeness and near-optimality assumptions on the behavior policy. The same stochastic-approximation machinery yields a first L2 convergence rate for tabular Q-learning with an epsilon-softmax behavior policy, converging to the optimal action-value function itself.

What carries the argument

The load-bearing object is a general stochastic-approximation theorem for updates $w_{t+1} = w_t + \alpha_t H(w_t, Y_{t+1})$ driven by a time-inhomogeneous Markov chain whose transition kernel $P_w$ changes on the same timescale as the weights. The theorem establishes a recursive bound $\mathbb{E}[L(w_{t+1})] \le (1+f(t))\mathbb{E}[L(w_t)] + \alpha_t \mathbb{E}[\langle \nabla L(w_t), h(w_t)\rangle] + f(t)$ with $f(t) = O(\ln^2(t+t_0)/(t+t_0)^{2\epsilon_\alpha})$, using uniform mixing, a delay by the mixing time $\tau_{\alpha_t}$, and an auxiliary Markov chain to control the noise. For linear Q-learning the critical drift bound is that for large adaptive-temperature constant $\kappa_0$ and small $\epsilon$, $w^\top A(w)w \le -\beta\|w\|_2^2$ for $\|w\|_2 \ge 1$, where $A(w) = X^\top D_{\mu_w}(\gamma P_{\pi_w} - I)X$; this turns the recursion into a contraction outside a ball. For tabular Q-learning the key new object is the weighted Bellman optimality operator $T'q = D_{\mu_q}(Tq - q) + q$, which is not a contraction but is shown to be a pseudo-contraction in the infinity norm, with modulus $1 - (1-\gamma)\inf_{q,s,a} d_{\mu_q}(s,a)$.

What would settle it

Take a small MDP and a feature matrix with duplicate columns so $X$ is rank deficient, then run unmodified linear Q-learning with the epsilon-softmax adaptive-temperature policy; the component of $w$ orthogonal to the feature span is invariant, so $\mathbb{E}[\|w_t\|_2^2]$ cannot settle into a set with radius independent of $\|w_0\|$. A direct check is to evaluate $\lambda_{\min}(X^\top D_{\mu_w} X)$ along the trajectory; if it approaches zero, the uniform drift constant $\beta$ cannot exist.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central claim is that the unmodified linear Q-learning iterates $\{w_t\}$ satisfy $\mathbb{E}[\|w_t\|_2^2] \le B_{1,1}(t+t_0)^{-B_{1,2}\alpha}\|w_0\|_2^2 + B_{1,3}$ when $\alpha_t = \alpha/(t+t_0)$, and $\mathbb{E}[\|w_t\|_2^2] \le B_{1,4}\exp(-B_{1,5}(t+t_0)^{1-\epsilon_\alpha})\|w_0\|_2^2 + B_{1,6}$ when $\alpha_t = \alpha/(t+t_0)^{\epsilon_\alpha}$ with $\epsilon_\alpha \in (0.5, 1)$. That is, the squared weight norm converges in expectation to a bounded set, not to a point. The same general stochastic-approximation result gives an $L^2$ convergence rate for tabular Q-learning with an $\epsilon$-softmax behavior policy, and there the iterates converge to the optimal action-value function $q_*$ itself. The authors emphasize that no algorithm modification, Bellman completeness assumption, or near-optimality assumption is used; the only algorithm-level requirement is the exploratory softmax policy with adaptive temperature.

Load-bearing premise

The proof requires the weighted feature matrix $X^\top D_{\mu_w} X$ to be uniformly positive definite for large weights, i.e. the feature matrix $X$ must have full column rank; the paper never states this rank condition, despite claiming no restrictive feature assumptions.

Editorial extensions

If this is right

Unmodified linear Q-learning, as run with softmax exploration and adaptive temperature, does not diverge in mean square; $\mathbb{E}[\|w_t\|_2^2]$ is eventually bounded by a constant depending only on the MDP, the features, the reward, and the discount factor.
Choosing a learning-rate exponent $\epsilon_\alpha \in (0.5, 1)$ instead of $\epsilon_\alpha = 1$ upgrades the rate to the bounded set from polynomial to exponential.
Tabular Q-learning with an $\epsilon$-softmax behavior policy converges in $L^2$ to $q_*$ without count-based learning rates, matching a form practitioners actually run.
The general stochastic-approximation theorem applies to any single-timescale update driven by fast-changing Markovian noise with Lipschitz transition kernels, making it a reusable tool beyond Q-learning.
No Bellman completeness or near-optimality assumption is needed; the only behavioral condition is $\epsilon > 0$ combined with the adaptive temperature.

Reading between the lines

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

The stated independence from feature assumptions is best read as conditional on the feature matrix having full column rank; if $X$ is rank deficient, the drift inequality cannot hold uniformly and no bounded-set radius independent of the initial weight can exist.
Because the proof is built on a recursive drift inequality rather than ODE asymptotics, almost-sure and high-probability analogues of the $L^2$ rate should follow from the same machinery; the paper lists these as future directions.
The tabular result's pseudo-contraction modulus degrades as the state-action grid grows, since $\inf_{q,s,a} d_{\mu_q}(s,a)$ shrinks; the rate constants should be interpreted with the size of the MDP in mind.

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

Short version: the paper delivers a genuinely new L2 convergence-rate result for unmodified linear Q-learning, plus a single-timescale stochastic approximation theorem that should be reusable. But Theorem 1 as stated is false: Lemma 16 needs X^T D_mu_w X to be uniformly positive definite, which is equivalent to X having full column rank. That condition is never stated, and Table 1 explicitly claims no restrictive feature assumptions. I checked the stress-test and it holds: if w lies in the null space of X, the behavior policy is a fixed uniform epsilon-softmax policy, the linear part of the drift vanishes, the null-space component of the weights is invariant, and no bound independent of w0 can hold. So the missing assumption is load-bearing, not cosmetic. This is fixable: add the full-rank assumption and adjust Table 1, or weaken the conclusion to depend on the initial null-space component.

Credit where due: the paper is the first to give an L2 rate to a bounded set for unmodified linear Q-learning under an epsilon-softmax policy with adaptive temperature, extending Meyn's almost-sure boundedness. The general SA result (Theorem 3) with fast-changing Markovian transition functions and no projection is proved in detail in the appendix; the auxiliary-chain coupling and the mixing-time decomposition look sound. The tabular result with the pseudo-contraction property of the weighted Bellman operator (Lemma 8) is also clean and new, and Lemma 5 on the Lipschitz property of the adaptive-temperature policy is a nice piece of work.

Soft spots beyond the rank condition: there is a minor range inconsistency in Theorem 1—case 2 says epsilon_alpha in (0,1), while the abstract and Theorem 2 say (0.5,1); the proof actually needs the lower bound. Experiments are minimal (Baird only) and no code is provided, but for a theory paper that is acceptable. The dependency on Lemma 16 from Meyn is cited properly, but the paper should state the full condition explicitly rather than hiding it in the beta formula.

The core technical machinery is worth engaging with, and the flaw is an unstated assumption rather than a broken proof. I would send this to peer review, asking the authors to state the full-rank condition and reconcile the claims in Table 1. After that, the main results are likely correct and citable.

Referee Report

2 major / 5 minor

Summary. The paper proves mean-square (L2) convergence rates for unmodified linear Q-learning with an epsilon-softmax behavior policy and adaptive temperature: weights converge in expectation to a bounded set at a polynomial or exponential rate (Theorem 1). It also proves a corresponding rate for tabular Q-learning with an epsilon-softmax policy, via a pseudo-contraction property of a weighted Bellman optimality operator (Theorem 2). The technical core is a general stochastic-approximation theorem for single-timescale Markovian noise (Theorem 3), with detailed appendix proofs. The linear case relies on a drift inequality whose positive drift coefficient comes from Lemma 16, reproduced from Meyn (2024).

Significance. If the rank issue identified below is fixed, the paper would make a substantial contribution: it provides the first L2 convergence rate for the original, unmodified linear Q-learning algorithm under an epsilon-softmax exploration policy, without target networks, replay, projection, regularization, Bellman completeness, or near-optimality assumptions. The general SA result in Theorem 3 is potentially reusable, and the tabular result (Theorem 2) is independent of the linear-feature issue and appears sound. The appendix is detailed and the rate expressions are explicit. However, the central theorem is currently false as stated because a full-column-rank condition on the feature matrix is missing.

major comments (2)

[Appendix C, Lemma 16; Theorem 1; Table 1] The proof of Theorem 1 depends on Lemma 7, whose drift inequality uses w^T A(w) w <= -beta ||w||_2^2 with beta > 0. In Lemma 16, beta is proportional to lambda_min(X^T D_mu_w X), and this quantity is positive uniformly in w only if X has full column rank (with epsilon > 0 and Assumption 3.1). The full-column-rank condition is never stated in Assumptions 3.1/LR or in Theorem 1, and Table 1 explicitly claims that the Theorem 1 row uses no restrictive feature assumptions. This is not a mere proof gap: if w0 is chosen in null(X) with large norm, then X w0 = 0, so the behavior policy mu_w0 is uniform and the greedy feature value is 0. Every subsequent update increment is a multiple of x(S_t,A_t), which lies in range(X^T), orthogonal to null(X); hence the null-space component of w_t is invariant. Therefore E[||w_t||_2^2] >= ||w0^null||_2^2 for all t, while the right-hand side of Theorem 1 tends to B1,3, which is independent of w0. Choosing ||w0^null||_2^2 > B1,3 makes the stated inequality false. The theorem must add an explicit full-column-rank assumption (or an equivalent uniform positive-definiteness condition), and Table 1 must be revised; alternatively, the conclusion must include the invariant null component as part of the limiting bound.
[Appendix C, Lemma 16 and Lemma 7] Even after adding full column rank, the paper should justify that the beta in Lemma 16 is a single constant independent of w. As reproduced, the displayed beta contains lambda_min(X^T D_mu_w X) and lambda_max(X^T D_mu_w X), both of which depend on w through D_mu_w, while Lemma 7 and the proof of Theorem 1 require a fixed beta > 0 for all w with ||w||_2 >= 1. The needed statement is that inf_{w: ||w||_2 >= 1} lambda_min(X^T D_mu_w X) > 0, which does follow from full column rank, epsilon > 0, and Assumption 3.1, but it is not stated or proved. This uniform lower bound is load-bearing for the drift inequality and should be stated explicitly rather than left implicit in the citation to Meyn (2024).

minor comments (5)

[Section 3, Theorem 1 statement] Case (2) of Theorem 1 says 'When epsilon_alpha in (0,1)', while Assumption LR restricts epsilon_alpha to (0.5,1]; the statement should consistently say (0.5,1) (or explicitly explain why the wider range is intended).
[Section 5.3, first paragraph of the proof of Theorem 2] The sentence 'Most of the proofs here are similar to Section 5.3' should refer to Section 5.2, not Section 5.3.
[Appendix C.4, proof of Theorem 1] The phrase 'using x + y >= sqrt(xy)' has the inequality direction reversed for the intended Young-type bound; it should be '2 sqrt(xy) <= x + y'.
[Throughout the paper] There are several typographical errors, including 'behaivor' (Sections 2, 4, and Table 1), 'intead' (Section 4), 'supercede' (Section 4), 'funciton' (Section 5.2), and 'prodecure' (Section 5.2); a copyedit pass is needed.
[Section 6, Experiments] The experiments use a constant learning rate alpha = 0.1, which is outside Assumption LR's decaying learning rates; Figure 1 is therefore only an illustration of boundedness, not a verification of the stated rates, and this should be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the L2 bounds follow from a proved stochastic-approximation recursion plus external drift lemmas; the self-citations used are technical Markov-chain facts, not the target result.

full rationale

The paper's derivation chain is not circular. Theorem 1 is obtained by combining (i) the general stochastic-approximation inequality in Theorem 3, which is proved in Section 5.1 and the appendix using only stated assumptions on H, P_w, and the learning rate; and (ii) the drift bound in Lemma 7, which is proved in Section C.3. The only imported drift ingredient is Lemma 16, quoted from Meyn (2024); this is an external citation, not a self-citation, and Lemma 16 does not assert the conclusion of Theorem 1. The tabular result Theorem 2 similarly rests on Lemma 8, whose pseudo-contraction proof is given in Section D.1, and on Theorem 3. No parameter is fitted to data and then renamed as a prediction; the experimental section is illustrative and not used to derive the claimed rates. The paper does cite prior work by overlapping authors, notably Lemma 1 of Zhang et al. (2022) for uniform geometric mixing under Assumption A1 and Lemma 9 of Zhang et al. (2021) for Lipschitz continuity of stationary distributions; however, these are standard finite-state Markov-chain regularity facts, they are not equivalent to the Q-learning bounded-set conclusion, and the central drift argument comes from Meyn (2024) rather than from a self-citation chain. The skeptic's concern about the missing full-column-rank condition in Lemma 16 is a correctness risk about whether beta can be positive, not a circularity: the lemma is imported, not derived from the theorem it supports, and the paper's assumptions do not define the conclusion into existence. Therefore the appropriate circularity score is 0.

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

The central claim rests on standard MDP and stochastic approximation assumptions, plus the imported Meyn drift lemma that implicitly requires full column rank of the feature matrix. The softmax parameters epsilon, kappa0, t0, and alpha are algorithm hyperparameters chosen to satisfy the theorem's conditions, not fitted to data.

free parameters (4)

epsilon = sufficiently small, epsilon < (1-gamma)^2/((1-gamma)^2+gamma^2)
Exploration parameter in the softmax behavior policy; chosen by hand and required small by Lemma 16 to make the drift negative.
kappa0 = sufficiently large
Temperature scale in the adaptive softmax policy; needed large by Lemma 16 to ensure negative drift for large weights.
t0 = sufficiently large
Offset in the learning rate schedule; must be large enough for the mixing-time bounds in Lemma 17.
alpha = positive constant
Learning rate scale; appears in the rate exponent and is set by the user, not fitted to data.

assumptions (5)

domain assumption Assumption 3.1: the Markov chain induced by a uniformly random behavior policy is irreducible and aperiodic
Ensures uniform ergodicity of all induced chains in Assumption A1; needed for the mixing bounds.
domain assumption Assumption LR: learning rate alpha_t = alpha/(t+t0)^epsilon_alpha with epsilon_alpha in (0.5, 1]
Defines the step-size family used in the rates.
domain assumption Lemma 16 (Lemma A.9 of Meyn 2024): for sufficiently large kappa0 and small epsilon, w^T A(w)w <= -beta ||w||^2 for ||w|| >= 1
Borrowed without proof; requires full-column-rank feature matrix, which is not stated.
ad hoc to paper X has full column rank (implicit)
Needed for lambda_min(X^T D_mu_w X) > 0; without it the drift lemma fails and the theorem is false.
standard math Assumptions A1, A2, A3/A3' in Theorem 3
Technical conditions of the general SA theorem; verified for the two algorithms in Sections 5.2 and 5.3.

invented entities (1)

Weighted Bellman optimality operator T'
purpose: Defined as T'q = D_mu_q (Tq - q) + q to capture the expected update of tabular Q-learning; shown to be a pseudo-contraction in Lemma 8.
A mathematical construction for the proof, not an empirical entity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set." pith.science (2026). https://pith.science/paper/Y4HIXO76

@misc{pith2026250119254,
  author       = {Pith},
  title        = {Pith review of: Linear $Q$-Learning Does Not Diverge in $L^2$: Convergence Rates to a Bounded Set},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y4HIXO76}},
  note         = {Machine review of arXiv:2501.19254}
}

abstract

$Q$-learning is one of the most fundamental reinforcement learning algorithms. It is widely believed that $Q$-learning with linear function approximation (i.e., linear $Q$-learning) suffers from possible divergence until the recent work Meyn (2024) which establishes the ultimate almost sure boundedness of the iterates of linear $Q$-learning. Building on this success, this paper further establishes the first $L^2$ convergence rate of linear $Q$-learning iterates (to a bounded set). Similar to Meyn (2024), we do not make any modification to the original linear $Q$-learning algorithm, do not make any Bellman completeness assumption, and do not make any near-optimality assumption on the behavior policy. All we need is an $\epsilon$-softmax behavior policy with an adaptive temperature. The key to our analysis is the general result of stochastic approximations under Markovian noise with fast-changing transition functions. As a side product, we also use this general result to establish the $L^2$ convergence rate of tabular $Q$-learning with an $\epsilon$-softmax behavior policy, for which we rely on a novel pseudo-contraction property of the weighted Bellman optimality operator.

Figures

Figures reproduced from arXiv: 2501.19254 by the authors.

**Figure 1.** Convergence of (linear Q-learning) with γ = 0.99, α = 0.1. The graph shows the evolution of ∥wt∥ 2 2 over time steps, demonstrating stable convergence behavior. The blue line represents the average of the squared L 2 norm of weights over 10 independent runs, and the shaded area indicates the range between minimum and maximum values [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗

**Figure 2.** shows the evolution of weight norms ∥wt∥ 2 2 for all four algorithms. While all methods eventually maintain bounded weights, our unmodified approach achieves comparable performance without the computational overhead or hyperparameter tuning required by the other methods. 0 200 400 600 800 1000 1200 1400 Time Step 0.000 0.005 0.010 0.015 0.020 0.025 0.030 0.035 wt 2 2 Target Network Weight Projection Ridge Regulariza… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 48 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

Baird, L. C. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the International Conference on Machine Learning, 1995

work page 1995
[3]

First-order methods in optimization

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

2017
[4]

A Markovian decision process

Bellman, R. A Markovian decision process. Journal of mathematics and mechanics, 1957

work page 1957
[5]

Adaptive Algorithms and Stochastic Approximations

Benveniste, A., M \' e tivier, M., and Priouret, P. Adaptive Algorithms and Stochastic Approximations. Springer, 1990

work page 1990
[6]

Stochastic approximation: a dynamical systems viewpoint

Borkar, V. Stochastic approximation: a dynamical systems viewpoint. Springer, 2009

work page 2009
[7]

The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning

Borkar, V., Chen, S., Devraj, A., Kontoyiannis, I., and Meyn, S. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applied Probability, 2025

work page 2025
[8]

D., and Wang, Z

Cai, Q., Yang, Z., Lee, J. D., and Wang, Z. Neural Temporal Difference and Q Learning provably converge to global optima. Mathematics of Operations Research, 2023

work page 2023

Show all 51 references

[9]

S., and Santos, P

Carvalho, D., Melo, F. S., and Santos, P. A new convergent variant of Q-learning with linear function approximation. In Advances in Neural Information Processing Systems, 2020

2020
[10]

and Zhao, L

Chen, X. and Zhao, L. Finite-time analysis of single-timescale actor-critic. In Advances in Neural Information Processing Systems, 2023

2023
[11]

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

Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. A Lyapunov theory for finite-sample guarantees of asynchronous Q-learning and TD-learning variants. ArXiv Preprint, 2021

2021
[12]

T., Maguluri, S

Chen, Z., Zhang, S., Doan, T. T., Maguluri, S. T., and Clarke, J.-P. Performance of Q-learning with linear function approximation: Stability and finite time analysis. Automatica, 2022

2022
[13]

P., and Maguluri, S

Chen, Z., Clarke, J. P., and Maguluri, S. T. Target network and truncation overcome the deadly triad in Q -Learning . SIAM Journal on Mathematics of Data Science, 2023

2023
[14]

T., and Zubeldia, M

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

2025
[15]

Devraj, A. M. and Meyn, S. P. Q-learning with uniformly bounded variance. IEEE Transactions on Automatic Control, 2022

2022
[16]

Learning rates for Q-learning

Even-Dar, E., Mansour, Y., and Bartlett, P. Learning rates for Q-learning . Journal of Machine Learning Research, 2003

2003
[17]

A theoretical analysis of deep Q-Learning

Fan, J., Wang, Z., Xie, Y., and Yang, Z. A theoretical analysis of deep Q-Learning . In Proceedings of the Annual Conference on Learning for Dynamics and Control, 2020

2020
[18]

and Thoppe, G

Gopalan, A. and Thoppe, G. Approximate Q-learning and SARSA(0) under the -greedy policy: a differential inclusion analysis. ArXiv Preprint, 2022

2022
[19]

Boundedness of iterates in Q-learning

Gosavi, A. Boundedness of iterates in Q-learning . Systems & Control Letters, 2006

2006
[20]

and Donghwan, L

Han-Dong, L. and Donghwan, L. Regularized Q-learning . In Advances in Neural Information Processing Systems, 2024

2024
[21]

Convergence of stochastic iterative dynamic programming algorithms

Jaakkola, T., Jordan, M., and Singh, S. Convergence of stochastic iterative dynamic programming algorithms. In Advances in Neural Information Processing Systems, 1993

1993
[22]

Exponential hardness of reinforcement learning with linear function approximation

Kane, D., Liu, S., Lovett, S., Mahajan, G., Szepesv \'a ri, C., and Weisz, G. Exponential hardness of reinforcement learning with linear function approximation. In Proceedings of the Annual Conference on Learning Theory, 2023

2023
[23]

Konda, V. R. Actor-Critic Algorithms. PhD thesis, Massachusetts Institute of Technology, 2002

2002
[24]

Konda, V. R. and Tsitsiklis, J. N. Actor-critic algorithms. In Advances in Neural Information Processing Systems, 1999

1999
[25]

and Yin, G

Kushner, H. and Yin, G. G. Stochastic approximation and recursive algorithms and applications. Springer Science & Business Media, 2003

2003
[26]

and He, N

Lee, D. and He, N. A unified switching system perspective and convergence analysis of Q-Learning algorithms. In Advances in Neural Information Processing Systems, 2020

2020
[27]

Is Q-learning minimax optimal? a tight sample complexity analysis

Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. Is Q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 2024

2024
[28]

Lin, L. J. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 1992

1992
[29]

Littman, M. L. and Szepesv \'a ri, C. A generalized reinforcement-learning model: Convergence and applications. In Proceedings of the International Conference on Machine Learning, 1996

1996
[30]

The ODE method for stochastic approximation and reinforcement learning with markovian noise

Liu, S., Chen, S., and Zhang, S. The ODE method for stochastic approximation and reinforcement learning with markovian noise. Journal of Machine Learning Research, 2025

2025
[31]

and Tsitsiklis, J

Marbach, P. and Tsitsiklis, J. N. Simulation-based optimization of markov reward processes. IEEE Transactions on Automatic Control , 2001

2001
[32]

S., Meyn, S

Melo, F. S., Meyn, S. P., and Ribeiro, M. I. An analysis of reinforcement learning with function approximation. In Proceedings of the International Conference on Machine Learning, 2008

2008
[33]

The projected bellman equation in reinforcement learning

Meyn, S. The projected bellman equation in reinforcement learning. IEEE Transactions on Automatic Control, 2024

2024
[34]

A., Veness, J., Bellemare, M

Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M. A., Fidjeland, A., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. Human-level cont...

2015
[35]

and Gharesifard, B

Olshevsky, A. and Gharesifard, B. A small gain analysis of single timescale actor critic. SIAM Journal on Control and Optimization, 2023

2023
[36]

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

Qian, X., Xie, Z., Liu, X., and Zhang, S. Almost sure convergence rates and concentration of stochastic approximation and reinforcement learning with markovian noise. ArXiv Preprint, 2024

2024
[37]

Rummery, G. A. and Niranjan, M. On-line Q-learning using connectionist systems. University of Cambridge, Department of Engineering Cambridge, UK, 1994

1994
[38]

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

2018
[39]

The asymptotic convergence-rate of Q-learning

Szepesv \'a ri, C. The asymptotic convergence-rate of Q-learning . In Advances in Neural Information Processing Systems, 1997

1997
[40]

Tsitsiklis, J. N. Asynchronous stochastic approximation and Q-learning . Machine learning, 1994

1994
[41]

Watkins, C. J. and Dayan, P. Q-learning. Machine Learning, 1992

1992
[42]

Watkins, C. J. C. H. Learning from delayed rewards. PhD thesis, King's College, Cambridge, 1989

1989
[43]

A finite-time analysis of two time-scale actor-critic methods

Wu, Y., Zhang, W., Xu, P., and Gu, Q. A finite-time analysis of two time-scale actor-critic methods. In Advances in Neural Information Processing Systems, 2020

2020
[44]

and Gu, Q

Xu, P. and Gu, Q. A finite-time analysis of Q-Learning with neural network function approximation. In Proceedings of the International Conference on Machine Learning, 2020

2020
[45]

Provably convergent two-timescale off-policy actor-critic with function approximation

Zhang, S., Liu, B., Yao, H., and Whiteson, S. Provably convergent two-timescale off-policy actor-critic with function approximation. In Proceedings of the International Conference on Machine Learning, 2020

2020
[46]

Breaking the deadly triad with a target network

Zhang, S., Yao, H., and Whiteson, S. Breaking the deadly triad with a target network. In Proceedings of the International Conference on Machine Learning, 2021

2021
[47]

Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch

Zhang, S., Tachet, R., and Laroche, R. Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch. Journal of Machine Learning Research, 2022

2022
[48]

T., and Laroche, R

Zhang, S., Des Combes, R. T., and Laroche, R. On the convergence of SARSA with linear function approximation. In Proceedings of International Conference on Machine Learning, 2023 a

2023
[49]

On the convergence and sample complexity analysis of deep q-networks with -greedy exploration

Zhang, S., Li, H., Wang, M., Liu, M., Chen, P.-Y., Lu, S., Liu, S., Murugesan, K., and Chaudhury, S. On the convergence and sample complexity analysis of deep q-networks with -greedy exploration. In Advances in Neural Information Processing Systems, 2023 b

2023
[50]

and Xie, Q

Zhang, Y. and Xie, Q. Constant stepsize Q-learning : Distributional convergence, bias and extrapolation. ArXiv Preprint, 2024

2024
[51]

Finite-sample analysis for SARSA with linear function approximation

Zou, S., Xu, T., and Liang, Y. Finite-sample analysis for SARSA with linear function approximation. In Advances in Neural Information Processing Systems, 2019

2019

Pith tools

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

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

Baird, L. C. Residual algorithms: Reinforcement learning with function approximation. In Proceedings of the International Conference on Machine Learning, 1995

work page 1995

[3] [3]

First-order methods in optimization

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

2017

[4] [4]

A Markovian decision process

Bellman, R. A Markovian decision process. Journal of mathematics and mechanics, 1957

work page 1957

[5] [5]

Adaptive Algorithms and Stochastic Approximations

Benveniste, A., M \' e tivier, M., and Priouret, P. Adaptive Algorithms and Stochastic Approximations. Springer, 1990

work page 1990

[6] [6]

Stochastic approximation: a dynamical systems viewpoint

Borkar, V. Stochastic approximation: a dynamical systems viewpoint. Springer, 2009

work page 2009

[7] [7]

The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning

Borkar, V., Chen, S., Devraj, A., Kontoyiannis, I., and Meyn, S. The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning. The Annals of Applied Probability, 2025

work page 2025

[8] [8]

D., and Wang, Z

Cai, Q., Yang, Z., Lee, J. D., and Wang, Z. Neural Temporal Difference and Q Learning provably converge to global optima. Mathematics of Operations Research, 2023

work page 2023