{"id":"ed607fee-ddd1-46d6-80a1-2ed3f1b509fa","arxiv_id":"2501.19254","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Unmodified linear Q-learning converges in L2 to a bounded set at a polynomial or exponential rate under an epsilon-softmax behavior policy with adaptive temperature.","lead":"This paper proves that the weights of unmodified linear Q-learning stay bounded in expectation and reach a bounded set at a quantified rate, when exploration uses an epsilon-softmax policy with adaptive temperature. The result extends Meyn (2024) from almost-sure boundedness to explicit L2 convergence rates and also yields a new rate for tabular Q-learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's drift inequality requires full-column-rank features; this condition is absent, and rank-deficient features make the stated bounded-set conclusion false.","rationale":"The reader's weakest assumption is exactly the missing full-column-rank condition, and my read agrees. I checked the chain of dependence: Theorem 1 uses Lemma 7, which uses Lemma 16, whose beta formula contains lambda_min(X^T D_mu_w X); a positive beta requires X^T D_mu_w X to be uniformly positive definite. Neither Assumption 3.1 nor LR supplies this, and Table 1 even claims no restrictive feature assumptions. The invariant-null-space argument shows this is not merely a proof gap: for rank-deficient X, the null-space component of the weights is never updated, so no universal bounded-set constant independent of w0 can exist. This is a genuine counterexample to the theorem as stated, not just a missing proof detail, and it fully supports the reader's CONDITIONAL verdict: add full-column-rank (equivalently, uniform positive definiteness of X^T D_mu_w X) to Theorem 1 and adjust Table 1 accordingly. The rest of the analysis appears sound conditional on that fix, and the general SA theorem and the pseudo-contraction lemma for tabular Q-learning are not affected by this concern. Minor issue worth fixing: Theorem 1 part (2) states epsilon_alpha in (0,1), while Assumption LR requires (0.5,1]; Appendix C.4 also treats the full (0,1) range, so this appears to be a typo but should be corrected. The Baird experiments are illustrative rather than decisive.","tokens_in":19,"tokens_out":5052,"duration_ms":112976,"concrete_test":"Analytical counterexample: take |S|=1, |A|=2, gamma=0.99, zero rewards, epsilon=0.1, and features x(s,a)=(1,0) for both actions, so X has rank 1. Initialize w0=(0,M) with M large. The second feature is identically zero, so the update alpha_t delta_t x(s,a) has zero second coordinate and w_{t,2}=M for every t; Xw_t also has no dependence on M. Hence E||w_t||^2 >= M^2 for all t. Compute the claimed constant B_{1,3} from Appendix C.4 for this instance: since the raw-data constants are independent of w0 and lambda_min(X^T D X)=0, the beta step cannot produce a positive drift coefficient, so B_{1,3} is independent of M. Taking M^2 > B_{1,3} violates Theorem 1 at every sufficiently large t. This is a direct algebraic verification and needs no simulation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 hinges on Lemma 7, whose proof invokes Lemma 16 to assert w^T A(w) w <= -beta||w||^2 for ||w||>=1. The beta formula contains lambda_min(X^T D_mu_w X); for beta>0 one needs X^T D_mu_w X to be uniformly positive definite, i.e., X must have full column rank. Assumptions 3.1 and LR never state this, and Table 1 explicitly claims the Theorem 1 row uses no restrictive feature assumptions. If X is rank deficient, take w in null(X). Then Xw=0, so the behavior policy mu_w is the uniform epsilon-softmax policy independent of w, the greedy feature value is 0, and A(w)w = X^T D_mu_w (gamma P_pi_w - I) X w = 0. The null-space component of w is invariant under the update because delta_t x(s,a) is orthogonal to null(X). Hence E||w_t||^2 >= ||w_0^null||^2 for all t, while the right-hand side of Theorem 1 tends to B_{1,3}, which is independent of w0. Choosing ||w_0^null||^2 > B_{1,3} makes the theorem's inequality false. Thus, as stated, Theorem 1 is false: the missing full-column-rank assumption must be added (and Table 1's 'no restrictive feature assumptions' claim modified), or the conclusion must be weakened to depend on the null-space component.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":76,"tokens_out":18761,"duration_ms":278085,"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":[{"comment":"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.","section":"Appendix C, Lemma 16; Theorem 1; Table 1"},{"comment":"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).","section":"Appendix C, Lemma 16 and Lemma 7"}],"minor_comments":[{"comment":"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":"Section 3, Theorem 1 statement"},{"comment":"The sentence 'Most of the proofs here are similar to Section 5.3' should refer to Section 5.2, not Section 5.3.","section":"Section 5.3, first paragraph of the proof of Theorem 2"},{"comment":"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'.","section":"Appendix C.4, proof of Theorem 1"},{"comment":"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":"Throughout the paper"},{"comment":"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.","section":"Section 6, Experiments"}],"recommendation":"major_revision","confidential_remarks":"The missing full-column-rank condition is a genuine correctness bug in the main theorem, not a presentation issue, and the stress-test concern lands. However, the fix is local and within the manuscript's scope: add the rank/uniform-positive-definiteness condition and adjust Table 1, or weaken the conclusion to track the invariant null component. The tabular result and the general SA theorem appear independent and sound, so I would not reject. Please ensure the authors treat the rank issue as a load-bearing theorem-statement change, not a cosmetic caveat."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nCredit 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.\n\nSoft 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.\n\nThe 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.","headline":"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.","tokens_in":31570,"tokens_out":2434,"would_cite":false,"duration_ms":22723,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["linear Q-learning","L2 convergence","bounded set","stochastic approximation","Markovian noise","epsilon-softmax behavior policy","tabular Q-learning","weighted Bellman operator"],"falsifier":"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.","tokens_in":30408,"feed_emoji":"📉","tokens_out":10125,"duration_ms":94280,"temperature":0.7,"pith_summary":"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.","feed_headline":"Linear Q-learning provably converges in L2 to a bounded set","feed_subtitle":"Expected weight squares decay at polynomial or exponential rates under softmax exploration, with no algorithm tweaks.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the drift inequality $w^\\top A(w)w \\le -\\beta\\|w\\|_2^2$ and the epsilon-softmax adaptive-temperature behavior policy that make the expected update Lipschitz.","marker":"Meyn (2024)"},{"why":"Provides the uniform mixing and mixing-time lemmas used to control the time-inhomogeneous Markovian noise in the stochastic-approximation theorem.","marker":"Zhang et al. (2022)"},{"why":"Introduces the auxiliary Markov chain construction used to bound the delayed noise term in the proof of the general stochastic-approximation result.","marker":"Zou et al. (2019)"},{"why":"Supplies the Moreau envelope and Lyapunov arguments used to handle the nonsmooth infinity norm in the tabular Q-learning analysis.","marker":"Chen et al. (2021)"},{"why":"Provides the discrete Gronwall inequality used to telescope the recursive bounds into explicit convergence rates.","marker":"Borkar (2009)"},{"why":"Provides the smooth-function equivalences used to convert squared norms into Lyapunov functions in the stochastic-approximation proof.","marker":"Beck (2017)"}],"fun_headline_variants":["Linear Q-learning converges in L2 without algorithm tweaks","First L2 convergence rate for linear Q-learning","Unmodified linear Q-learning: L2 rate to a bounded set","Linear Q-learning: L2 convergence without Bellman completeness","Softmax exploration suffices for L2 convergence in Q-learning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Linear Q-learning converges in L2 without algorithm tweaks","First L2 convergence rate for linear Q-learning","Unmodified linear Q-learning: L2 rate to a bounded set","Linear Q-learning: L2 convergence without Bellman completeness","Softmax exploration suffices for L2 convergence in Q-learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001064,"raw_usage":{"total_tokens":4517,"prompt_tokens":1057,"completion_tokens":3460,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":673,"completion_tokens_details":{"reasoning_tokens":3378}},"tokens_in":673,"tokens_out":3460,"duration_ms":21196,"temperature":1.0,"reasoning_tokens":3378,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T20:48:44.785646+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"The projected bellman equation in reinforcement learning","cited_arxiv_id":null,"evidence_quote":"Supplies the drift inequality $w^\\top A(w)w \\le -\\beta\\|w\\|_2^2$ and the epsilon-softmax adaptive-temperature behavior policy that make the expected update Lipschitz."},{"cited_title":"Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch","cited_arxiv_id":null,"evidence_quote":"Provides the uniform mixing and mixing-time lemmas used to control the time-inhomogeneous Markovian noise in the stochastic-approximation theorem."},{"cited_title":"Finite-sample analysis for SARSA with linear function approximation","cited_arxiv_id":null,"evidence_quote":"Introduces the auxiliary Markov chain construction used to bound the delayed noise term in the proof of the general stochastic-approximation result."},{"cited_title":"T., Shakkottai, S., and Shanmugam, K","cited_arxiv_id":null,"evidence_quote":"Supplies the Moreau envelope and Lyapunov arguments used to handle the nonsmooth infinity norm in the tabular Q-learning analysis."},{"cited_title":"Stochastic approximation: a dynamical systems viewpoint","cited_arxiv_id":null,"evidence_quote":"Provides the discrete Gronwall inequality used to telescope the recursive bounds into explicit convergence rates."}],"review_version":1}