{"id":"2f89710b-9729-4221-b9df-75d798bc3ee0","arxiv_id":"2505.21796","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A black-box theorem shows that if un-averaged SA iterates concentrate, then Polyak-averaged iterates concentrate at the optimal 1/k rate, with applications to reinforcement learning algorithms.","lead":"This paper proves a general theorem that converts high-probability error bounds for un-averaged stochastic approximation iterates into sharp bounds for Polyak-Ruppert averaged iterates. It applies the framework to TD-learning, Q-learning, and off-policy TD, though several 'first' claims conflict with prior work.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 4.1 uses an un-averaged bound at i=k+1 that the theorem's hypothesis does not provide; the statement needs an off-by-one fix or a strengthened assumption.","rationale":"The reader's weakest assumption was Assumption 4.3 (subgaussianity at the fixed point), which is a scope condition rather than a defect in the main theorem's internal logic. My concern is different and, in my view, more directly load-bearing for the central claim: the proof of Theorem 4.1 requires a high-probability concentration event for the un-averaged iterate at time k+1, but the theorem's hypothesis only supplies such an event for times up to k. This appears in the definition of E_{k+1} and in the control of the telescoping term T2. Because the theorem is the paper's main contribution, a proof gap at this exact point matters more than the tightness-example algebra that the reader also flagged. The gap is likely fixable by shifting the horizon by one or by an alternative decomposition, so it does not warrant rejection; it does require a correction to the statement or the proof. I therefore keep the reader's CONDITIONAL verdict rather than moving to ACCEPT or REJECT. I also note that Proposition 4.2's stated inequality appears algebraically inconsistent, but that issue affects the 'tightness' claim and is secondary to the main theorem's proof gap.","tokens_in":37988,"tokens_out":24638,"duration_ms":255397,"concrete_test":"Re-derive the proof of Theorem 4.1 using only the stated event E_k(δ) with the hypothesis for i≤k. Isolate the display where the telescoping sum Σ_{i=k0}^{k}(x_{i+1}−x_i)/α_i is introduced and check whether the bound can be closed without a high-probability estimate on x_{k+1}. If it cannot, amend the theorem to assume the un-averaged bound for all i≤k+1, replace every occurrence of f(δ/2,k) in the bound by f(δ/2,k+1), and re-verify the proof. As a numerical sanity check, set k=1, f(δ,1)=1, f(δ,2)=M for large M; if the original statement's bound is claimed without M, the proof must fail at the step involving x_2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 4.1 in Appendix B.1 is built on the event E_k(δ) := {∥x_i−x*∥²_c ≤ α_i f(δ,k) for all 0≤i≤k}, which is exactly what the theorem's hypothesis supplies. However, after Eq. (B.4) every tail bound is written for ∥˜y_k∥²_c 1_{E_{k+1}}, and the argument repeatedly uses bounds that only make sense on E_{k+1}. In the control of T2, the telescoping identity introduces x_{k+1}, and the proof uses ∥x_{k+1}−x*∥²_c ≤ α_k f(δ,k); in T3 it states “∥x_i−x*∥²_c ≤ α_i f(δ,k) in E_{k+1}.” But E_{k+1} is defined with f(δ,k+1), and the theorem's assumption does not cover i=k+1 at all. Even if one redefines E_{k+1} with f(δ,k), the event {∥x_{k+1}−x*∥²_c ≤ α_{k+1}f(δ,k)} is not guaranteed by the hypothesis. Thus the claimed probability P(E_{k+1}) ≥ 1−δ′ is not justified, and the final union bound yielding 1−δ does not follow as written. The fix is straightforward — either strengthen the hypothesis to hold for all i≤k+1, in which case the bound must be stated with f(δ/2,k+1) instead of f(δ/2,k), or find a telescoping decomposition that avoids x_{k+1}. Since the theorem is the paper's central contribution, this gap is load-bearing even though it is likely repairable.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a black-box theorem that converts high-probability bounds on un-averaged stochastic approximation iterates into high-probability bounds on Polyak-Ruppert averaged iterates. Theorem 4.1 claims that if, for each delta', the un-averaged iterates satisfy ||x_i - x*||_c^2 <= alpha_i f_xi(delta', k) for all i <= k with probability at least 1 - delta', then the averaged iterate y_k satisfies a bound whose leading term is O((log(1/delta) + d) sigma^2/(k+1)) plus higher-order terms. The paper applies this result to contractive SA, tabular TD(n), Q-learning, and off-policy TD with linear function approximation, and also claims a tightness example and an impossibility result for multiplicative noise.","tokens_in":38282,"tokens_out":14469,"duration_ms":151452,"significance":"If correct, the main theorem is a genuinely useful modular reduction: it lets existing concentration results for raw SA be lifted to averaged iterates at the parametric rate, and the applications to TD-learning and Q-learning would provide new finite-time distributional bounds. The paper is also honest about a proof artifact in Section 4.1 and about the heavy-tailed behavior under multiplicative noise, which is formalized in Theorem 5.3. However, two load-bearing issues need to be resolved: the proof of Theorem 4.1 uses an off-by-one event that is not supplied by the theorem's hypothesis, and the tightness example in Appendix B.4 contains a scaling error. These issues do not appear to be fatal, but they must be repaired before the advertised claims are established.","major_comments":[{"comment":"The proof of Theorem 4.1 has an off-by-one gap in its use of events. It defines E_k(delta) using the bound ||x_i - x*||_c^2 <= alpha_i f(delta, k) for 0 <= i <= k, which is exactly what the theorem's hypothesis supplies. From Eq. (B.5) onward, however, all bounds on ||tilde y_k||_c^2 are taken on the event 1_{E_{k+1}}, and E_{k+1} is never explicitly defined. In controlling T2, the telescoping identity introduces x_{k+1} and step (c) uses ||x_{k+1} - x*||_c^2 <= alpha_k f(delta, k); in controlling T3 the text states that ||x_i - x*||_c^2 <= alpha_i f(delta, k) on E_{k+1}. But the theorem's hypothesis only covers indices 0 <= i <= k, and if E_{k+1} is interpreted with the same definition at k+1, it would involve f(delta, k+1), not f(delta, k). Consequently the claimed bound P(E_{k+1}) >= 1 - delta' is not justified, and the final union bound yielding probability at least 1 - delta does not follow as written. The gap is likely repairable by strengthening the hypothesis to hold for all i <= k+1 and restating the input bound with f(delta/2, k+1), or by designing a telescoping decomposition that avoids x_{k+1}; as it stands, this is a load-bearing defect in the central theorem.","section":"Appendix B.1, Theorem 4.1"},{"comment":"The tightness example contains an algebraic scaling error. With x_0 = 0, one has (k+1)||y_k||^2 = ||sum_{i=1}^k w_i||^2/(k+1), but the proof replaces this by ||sum_{i=1}^k w_i||^2 and then compares sqrt{k sigma_bar^2 log(1/delta)} with ||sum_i w_i||. The final computation concludes P(chi_2^2 <= 2 log(1/delta)) = 1 - delta, which is a statement about the norm of the summed noise, not about ||y_k|| at the scaling claimed in the proposition. The proposition statement itself also has a dimension mismatch: sigma_bar sqrt{k log(1/delta)} has the units of a norm, while it is added to ||x_0||^2, a squared norm. Because this example is the basis for the paper's claim that Theorem 4.1 is tight up to a universal constant, the tightness claim is not established by the argument as written. A corrected example may well salvage the qualitative conclusion, but it needs to be restated and re-proved with the correct (k+1) scaling and with care about the dimension term in the leading bound.","section":"Appendix B.4, Proposition 4.2"}],"minor_comments":[{"comment":"In the displayed formula for epsilon_bar(k, delta/2), the function f is evaluated as f(delta, k_0(delta/2, k) - 1), while all other terms in the theorem use f(delta/2, k). This is inconsistent with the union-bound language in the proof and should be corrected to f(delta/2, ...) unless there is a deliberate reason for the asymmetry.","section":"Theorem 4.1 statement"},{"comment":"The event E_{k+1} is used repeatedly from Eq. (B.5) onward but is never defined; the text only defines E_k(delta). The proof also refers to the event E_{k0} without definition. These should be made explicit so the reader can check whether the event indices and the f arguments are nested consistently.","section":"Appendix B.1"},{"comment":"The proposition states the probability of the displayed event is at most 1 - delta, while the proof concludes equality. If the intended claim is a lower-tail statement showing that the error can be as large as the leading term, the direction of the inequality and the event should be stated carefully to distinguish high-probability upper bounds from lower-tail statements.","section":"Appendix B.4"},{"comment":"In the proof of Theorem 5.2, the constants beta_2 and beta_4 are used in an inconsistent way: Eq. (B.9) introduces beta_2, while the supermartingale display subsequently uses both beta_2 and beta_4. The notation should be unified so the dependency of the final bound on these constants is clear.","section":"Appendix B.6"}],"recommendation":"major_revision","confidential_remarks":"The paper's reliance on [14] is appropriate: [14] is a published external result used only to supply the un-averaged input bounds, and no constants are fitted to make the theorem true. The main concern is the off-by-one gap in the central proof and the flawed tightness example; both are consequential but appear repairable within the manuscript's scope. I do not see a circularity problem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. Theorem 4.1 is a real contribution: a black-box reduction from un-averaged high-probability bounds to averaged ones at the optimal O(1/k) rate, and it does not appear in the cited literature. But the proof as written has a gap: it needs a concentration bound for x_{k+1} that the theorem's hypothesis does not supply, because E_{k+1} includes i=k+1 while the assumption only covers i≤k. The stress-test note is right that the fix is straightforward—apply the hypothesis with k+1 and f(δ,k+1)—but as written the claimed probability does not follow. This is load-bearing, not a cosmetic typo.\n\nThe structure is good. The split-early/late argument, the martingale concentration under Assumption 4.3, and the applications to TD, Q-learning, and off-policy TD are concrete. The second author's [14] is cited appropriately as input, and the paper is honest that multiplicative noise gives only polynomial tails. The new off-policy TD bound looks genuinely new; averaged Q-learning concentration results already exist (e.g., [27,29]), so the novelty claims should be toned down.\n\nSoft spots beyond the main gap: Proposition 4.2 has a factor-of-two scaling error in the chi-square calculation and a stray ||x0||^2 term in the statement, so the claim that the leading term is tight up to a universal constant is not justified as written. The subgaussianity of Jacobian noise in Assumption 4.3 is strong, but it is stated clearly and the authors are candid about what happens when it fails. Lemma 4.1 is a nice sanity-check result showing the tail can be kept at f(δ) at the cost of rate.\n\nThe paper is for SA and RL theory readers. It deserves a serious referee, but the referee should send it back for a corrected proof of Theorem 4.1, a rewritten tightness example, and reined-in novelty claims. I'd send it out: the framework is worth one round of revision.","headline":"A genuinely useful modular theorem for Polyak-averaged SA bounds, but the main proof has an off-by-one gap and the tightness example has scaling errors.","tokens_in":38865,"tokens_out":3982,"would_cite":false,"duration_ms":39365,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","60E15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A general theorem converts raw-iterate concentration bounds into Polyak-averaged bounds at the optimal $O(1/k)$ rate.","keywords":["stochastic approximation","Polyak-Ruppert averaging","high-probability bounds","concentration inequalities","temporal difference learning","Q-learning","contractive operators","subgaussian noise"],"falsifier":"Run the paper's own tightness example—constant step size, $F(x,w)=w$, and subgaussian noise in even dimension—and measure the limiting tail of $\\sqrt{k}\\|y_k-x^*\\|_2$. If the upper tail constant exceeds the $2\\sqrt{6}$ factor allowed by the theorem, the universal constant in Theorem 4.1 is not correct; alternatively, a contractive SA satisfying Assumptions 4.2–4.3 whose averaged error decays slower than $1/k$ for fixed $\\delta$ would refute the claimed rate.","tokens_in":37733,"feed_emoji":"📊","tokens_out":8209,"duration_ms":79393,"temperature":0.7,"pith_summary":"Polyak–Ruppert averaging is known to give stochastic approximation algorithms their optimal asymptotic variance, but finite-time high-probability guarantees for the averaged iterates have lagged behind. This paper proves a transfer theorem: if the raw iterates $x_i$ come with any high-probability bound of the form $\\|x_i-x^*\\|^2_c \\le \\alpha_i f_\\xi(\\delta',k)$ for all $i\\le k$, then the averaged iterates $y_k$ satisfy $\\|y_k-x^*\\|^2_c \\le (c\\log(1/\\delta)+d)\\bar\\sigma^2/(k+1)$ plus higher-order terms, with probability at least $1-\\delta$. The bound is tight up to a universal constant for a constructed example, and it applies to contractive stochastic approximation, temporal-difference learning, and Q-learning, giving what the paper reports as the first full-distribution concentration bounds for averaged Q-learning and off-policy TD-learning.","feed_headline":"Averaged stochastic approximation gets a universal concentration theorem","feed_subtitle":"Any high-probability bound on raw iterates lifts to Polyak averages at the optimal 1/k rate.","key_machinery":"The proof splits the averaged error into an early part $\\bar y_k$ (iterates before the recursion enters the local smoothness radius $R$) and a late part $\\tilde y_k$, then writes $(J\\bar F(x^*)-I)\\tilde y_k$ as four terms: a subgaussian sum of the operator noise at the fixed point, a telescoping step-size term, a remainder controlled by the local pseudo-smoothness constant $N$, and a martingale term driven by Jacobian noise. Chernoff-type exponential concentration on the subgaussian terms produces the $\\log(1/\\delta)/(k+1)$ leading term, while the Moreau-envelope assumption (Assumption 4.1) is used to keep the squared norm smooth when the natural norm is not.","core_discovery":"The paper's central claim is a modular transfer theorem for Polyak–Ruppert averaging. For any stochastic approximation recursion of the form $x_{k+1}=(1-\\alpha_k)x_k+\\alpha_k F(x_k,w_{k+1})$ whose raw iterates satisfy a high-probability bound $\\|x_i-x^*\\|^2_c \\le \\alpha_i f_\\xi(\\delta',k)$ for all $0\\le i\\le k$ with probability at least $1-\\delta'$, the averaged iterates $y_k=\\frac{1}{k+1}\\sum_{i=0}^k x_i$ satisfy, with probability at least $1-\\delta$, $\\|y_k-x^*\\|^2_c \\le (c\\log(1/\\delta)+d)\\bar\\sigma^2/(k+1)$ plus higher-order terms, where $\\bar\\sigma^2$ is a subgaussian variance proxy of the noise at the fixed point and $c$ is a universal constant. The authors construct an example showing the leading term is tight up to a constant multiplicative factor, and they apply the mechanism to contractive SA, TD-learning, Q-learning, and off-policy TD with linear function approximation.","pith_inferences":["Because Theorem 4.1 is black-box in the un-averaged bound, the real bottleneck for heavy-tailed or Markovian settings is the raw-iterate concentration result; better raw bounds would lift to averaged bounds without reworking the averaging argument.","Since the theorem bounds the whole distribution of the error with a step size independent of $\\delta$, it could support data-dependent confidence intervals for averaged reinforcement-learning estimators, not just single-point tail statements.","The multiplicative-noise impossibility result suggests that for off-policy TD with function approximation, practitioners should expect polynomial tails unless extra structure beyond the standard assumptions is exploited; tightening the $1/\\sqrt{\\delta}$ factor would require sharper un-averaged bounds, a direction the paper names explicitly.","A natural test is whether the same transfer mechanism holds for tail-averaged rather than Polyak-averaged iterates, or for Markovian noise where the un-averaged bounds are less mature; the paper does not analyze these, but its assumptions are stated in a way that might accommodate them."],"forward_implications":["For contractive stochastic approximation with additive subgaussian noise, the averaged error has a $\\log(1/\\delta)/(k+1)$ tail, so the step size need no longer depend on the target confidence $\\delta$.","Averaged TD-learning and Q-learning inherit whole-distribution concentration bounds with $1/k$ leading terms; the paper identifies these as the first such bounds for averaged Q-learning and off-policy TD.","Under multiplicative noise, no sub-Weibull concentration bound is possible for averaged iterates, so the polynomial $1/\\sqrt{\\delta}$ tail derived in the paper is the natural shape rather than a proof artifact.","The framework turns any future improvement in un-averaged SA bounds into an immediate improvement of the averaged bound, because the theorem accepts the raw-iterate bound as a black-box input.","Step-size exponent can be tuned: $\\xi=1/2$ is best for linear operators with non-additive noise and $\\xi=2/3$ for nonlinear operators, controlling the higher-order terms."],"supporting_citations":[{"why":"supplies the un-averaged concentration bounds for contractive SA with additive and multiplicative noise that Theorem 5.1 plugs into the transfer theorem.","marker":"[14]"},{"why":"provides the fourth-moment supermartingale machinery and un-averaged bounds for multiplicative noise used in Theorem 5.2.","marker":"[31]"},{"why":"introduces Polyak–Ruppert averaging and its optimal asymptotic variance, the phenomenon the paper makes non-asymptotic.","marker":"[33]"},{"why":"introduces the smooth Moreau-envelope norm used in Assumption 4.1 and in the contractive-SA applications.","marker":"[12]"},{"why":"establishes finite-time high-probability bounds for averaged linear SA, the setting the paper's general theorem subsumes and extends.","marker":"[17]"},{"why":"gives the statistical analysis of averaged Q-learning that the paper's Q-learning concentration result complements with full-distribution bounds.","marker":"[29]"}],"fun_headline_variants":["Polyak averaging gets a universal high-probability bound theorem","One theorem to lift raw SA bounds to optimal Polyak averages","Polyak-averaged SA: sharp high-probability tails from raw iterates","Rate-optimal concentration for averaged SA via a single lemma","New theorem: Polyak averaging turns SA bounds into optimal tails"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The clean $\\log(1/\\delta)/(k+1)$ leading term rests on Assumption 4.3, which requires the operator noise and the Jacobian noise at the fixed point $x^*$ to be subgaussian; when that fails, as in the paper's multiplicative-noise application, the averaged-error tail is only polynomially bounded in $1/\\delta$.","fun_headline_variants_meta":{"raw":{"variants":["Polyak averaging gets a universal high-probability bound theorem","One theorem to lift raw SA bounds to optimal Polyak averages","Polyak-averaged SA: sharp high-probability tails from raw iterates","Rate-optimal concentration for averaged SA via a single lemma","New theorem: Polyak averaging turns SA bounds into optimal tails"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000752,"raw_usage":{"total_tokens":3336,"prompt_tokens":923,"completion_tokens":2413,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":539,"completion_tokens_details":{"reasoning_tokens":2323}},"tokens_in":539,"tokens_out":2413,"duration_ms":16830,"temperature":1.0,"reasoning_tokens":2323,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:23:18.622365+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's own tightness example—constant step size, $F(x,w)=w$, and subgaussian noise in even dimension—and measure the limiting tail of $\\sqrt{k}\\|y_k-x^*\\|_2$. If the upper tail constant exceeds the $2\\sqrt{6}$ factor allowed by the theorem, the universal constant in Theorem 4.1 is not correct; alternatively, a contractive SA satisfying Assumptions 4.2–4.3 whose averaged error decays slower than $1/k$ for fixed $\\delta$ would refute the claimed rate.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the un-averaged concentration bounds for contractive SA with additive and multiplicative noise that Theorem 5.1 plugs into the transfer theorem."},{"cited_title":"Moulines and F","cited_arxiv_id":null,"evidence_quote":"provides the fourth-moment supermartingale machinery and un-averaged bounds for multiplicative noise used in Theorem 5.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces Polyak–Ruppert averaging and its optimal asymptotic variance, the phenomenon the paper makes non-asymptotic."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"introduces the smooth Moreau-envelope norm used in Assumption 4.1 and in the contractive-SA applications."},{"cited_title":"Durmus, E","cited_arxiv_id":null,"evidence_quote":"establishes finite-time high-probability bounds for averaged linear SA, the setting the paper's general theorem subsumes and extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the statistical analysis of averaged Q-learning that the paper's Q-learning concentration result complements with full-distribution bounds."}],"review_version":1}