{"id":"9de892e8-50fb-491b-a26f-34a3a47da9d4","arxiv_id":"2508.05570","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"For linear stochastic approximation under Markovian noise, Richardson-Romberg extrapolation cancels the linear bias and achieves the asymptotically optimal covariance.","lead":"This paper derives new error bounds for a stochastic approximation algorithm with constant step size and Richardson-Romberg extrapolation. The authors show the extrapolated estimator's leading error matches the optimal achievable variance.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Bias linearity remainder must be uniform in n; otherwise RR cancellation and optimal-variance claim fail.","rationale":"The reader's weakest assumption correctly points to the smoothness of the bias and the ergodicity of the Markov chain. I sharpen this to the specific remainder term in the bias expansion: the RR construction cancels only the first-order term, so the O(α^2) remainder must be uniformly small in n and must not amplify with the mixing time. This is a concrete, load-bearing condition that the full proof must establish. Since only the abstract and first page are available, I cannot determine whether the paper already proves this bound. Therefore the appropriate verdict remains UNVERDICTED, and my concern does not change the reader's verdict. The proposed analytical check of the remainder term would settle the issue if applied to the full manuscript.","tokens_in":1970,"tokens_out":12252,"duration_ms":138699,"concrete_test":"In the full proof, locate the bias-expansion theorem (the result establishing b_n(α) = α c + O(α^2)) and isolate the remainder R_n(α) = E[\\bar θ_n^{(α)} - θ*] - α c. Then verify analytically that sup_{n ≥ n0} |R_n(α)| = O(α^2) as α → 0, with the constant independent of n and of α, and compute the RR-combined remainder 2R_n(α) - R_n(2α). If this combined term is not O(α^2) uniformly, the extrapolation does not cancel the bias to the required order and the claim that the leading error term matches the optimal covariance is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the Richardson-Romberg estimator \\bar θ_n^{(α,RR)} cancels the leading O(α) bias and has a leading error term matching the optimal covariance of averaged LSA. This requires the bias b_n(α) = E[\\bar θ_n^{(α)}] - θ* to satisfy b_n(α) = α c + r_n(α) with r_n(α) = O(α^2) uniformly in the averaging horizon n and in the step size α. The 'linearization technique' mentioned in the abstract must establish such a remainder bound. If the remainder instead has the form α^2 n d or α^2 τ_mix d, where τ_mix is the mixing time of the Markov chain, then the extrapolated bias 2b_n(α) - b_n(2α) is O(α^2 n) or O(α^2 τ_mix), which can dominate the n^{-1/2} variance term. In that case the leading error term would no longer align with the asymptotically optimal covariance matrix. The abstract does not state the conditions under which r_n(α) is uniformly O(α^2), so this is the load-bearing regularity assumption on which the main result depends.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This manuscript studies constant-step-size linear stochastic approximation (LSA) with Polyak–Ruppert (PR) averaging under Markovian noise. The authors propose a 'linearization' decomposition of the bias E[\\barθ_n^{(α)}] − θ⋆, and claim that the leading-order bias is linear in α and hence cannot be eliminated by PR averaging. They then apply Richardson–Romberg (RR) extrapolation, \\barθ_n^{(α,RR)} = 2\\barθ_n^{(α)} − \\barθ_n^{(2α)}, and claim high-order moment bounds whose leading error term aligns with the asymptotically optimal covariance matrix of vanilla averaged LSA iterates. The visible text consists of the abstract and the first section of the introduction; no theorem statements, assumptions, or proofs are included in the provided material.","tokens_in":2288,"tokens_out":4159,"duration_ms":42130,"significance":"If the claimed bounds are correct, the paper would supply a rigorous non-asymptotic optimality justification for RR extrapolation in LSA, complementing recent work by Huo et al., Dieuleveut et al., and others. The combination of leading-bias cancellation with variance optimality would be practically valuable for reinforcement learning and stochastic optimization. The topic is timely and the main statement is crisp. However, because the visible portion contains no derivations, I cannot assess the novelty or correctness; the significance is conditional on the full proofs delivering the advertised uniformity conditions and the stated covariance alignment.","major_comments":[{"comment":"The central cancellation claim requires the bias b_n(α) = E[\\barθ_n^{(α)}] − θ⋆ to satisfy b_n(α) = α c + r_n(α) with r_n(α) = O(α^2) uniformly in the averaging horizon n. The abstract announces a 'linearization technique' but gives no remainder estimate. If the remainder is only O(α^2 n) or O(α^2 τ_mix), then the RR estimator's bias 2b_n(α) − b_n(2α) can dominate the n^{-1/2} stochastic term, and the optimal-variance claim would fail. The manuscript needs an explicit theorem stating the uniform remainder bound and the assumptions (ergodicity, moments of A(Z_k), b(Z_k), α-range, burn-in n0) under which it holds. This is the load-bearing point on which the main result depends.","section":"Section 1, Eq. (2) and Abstract"},{"comment":"The visible text contains no formal statement of the main results. The abstract promises high-order moment bounds for \\barθ_n^{(α,RR)} and alignment with the asymptotically optimal covariance, but the definitions of 'high-order', the norm (E||·||^p)^{1/p}, and the optimal covariance matrix are not given. Without the theorem statements and proofs, the central claims are unverifiable. At minimum, the authors should state the main theorems in the introduction or an early section and indicate which existing results are invoked.","section":"Section 1 (no theorem statements)"},{"comment":"The RR estimator couples the two step-size processes by using the same Markov chain {Z_k}. The visible text does not indicate how this coupling is controlled in the high-order moment analysis. A bound on E||\\barθ_n^{(α,RR)} − θ⋆||^p involves cross-moments between θ^{(α)} and θ^{(2α)}; the claimed leading covariance alignment requires a precise joint expansion. The paper should state the joint weak/strong approximation used and compare the resulting covariance with the vanilla averaged LSA covariance.","section":"Section 1, Eq. (2)"}],"minor_comments":[{"comment":"The notation \\barθ_n^{(α,RR)} is introduced only in the body; define it in the abstract or at first use.","section":"Abstract"},{"comment":"Several citations appear (Huo et al. 2024; Lauand and Meyn 2022a; Dieuleveut, Durmus, and Bach 2020; etc.) but the bibliography is not visible in the provided text; ensure all cited works are included and correctly described.","section":"Introduction, references"},{"comment":"The phrase 'is linear in α and is of order O(α)' is slightly imprecise: a function can be O(α) without being linear. Clarify that linearity refers to the leading term, as used by the RR construction.","section":"Introduction"}],"recommendation":"uncertain","confidential_remarks":"The provided manuscript excerpt contains only the abstract and first page; I cannot verify the central theorems. The uniformity-in-n concern about the bias remainder raised in the stress-test note is legitimate and should be probed when the full text is available. I recommend requesting the complete manuscript before making a final decision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a serious theory paper. The core idea—linearize the bias of constant-step-size LSA, show the leading term is O(alpha), then use Richardson-Romberg to cancel it and recover the optimal covariance of the averaged iterates—is exactly the right question to ask, and as far as I can tell from the abstract and introduction it has not been answered cleanly before. The paper earns credit for going beyond the existing non-asymptotic bounds on RR-LSA and targeting the optimality of the leading error term.\n\nWhat looks good: the problem framing is clear, the relationship to Huo et al., Durmus et al., and Lauand and Meyn is sensible, and the proposed linearization-based decomposition is a natural way to expose the bias structure. The claim that PR averaging cannot eliminate the linear bias is consistent with the Markov-noise literature. If the proof of the high-order moment bounds goes through, this would be a solid step forward.\n\nThe soft spot, and it is a load-bearing one: the abstract does not state the conditions under which the bias expansion is uniform. Richardson-Romberg cancellation works only if the remainder r_n(alpha) in b_n(alpha) = alpha c + r_n(alpha) is O(alpha^2) uniformly in n and in alpha. If the remainder instead behaves like alpha^2 n or alpha^2 tau_mix, then the extrapolated bias 2b_n(alpha) - b_n(2alpha) is no longer negligible next to the n^{-1/2} variance term, and the optimal-covariance claim fails. The stress-test note is right to flag this, and I don't see it resolved in the visible text. That doesn't mean the paper is wrong—the full proof may handle it—but it is the first thing I would look for.\n\nMinor: only the first page is available to me, so I can't comment on the actual derivations. The citation pattern looks normal from the visible text.\n\nBottom line: yes, this deserves a serious referee. A careful reviewer with stochastic-approximation and Markov-chain expertise should be asked to verify the uniformity condition and the high-order moment bounds. I wouldn't cite it yet, but I'd bring it to the reading group.","headline":"Plausible and useful claim on RR extrapolation for Markovian LSA, but the key uniformity condition on the bias remainder is not visible in the available text and must be checked before the main result can be trusted.","tokens_in":2638,"tokens_out":2350,"would_cite":false,"duration_ms":25060,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L20","60J05","65B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Richardson-Romberg extrapolation cancels the linear step-size bias of averaged linear stochastic approximation under Markov noise, and the corrected estimator attains the optimal error covariance.","keywords":["linear stochastic approximation","Polyak-Ruppert averaging","constant step size","Markovian noise","Richardson-Romberg extrapolation","bias decomposition","high-order error bounds"],"falsifier":"Run constant-step-size averaged LSA on a simple two-state Markov chain with a known linear system, estimate the bias at several step sizes $\\alpha$, and check whether the bias is actually linear in $\\alpha$. If the bias deviates from linearity in a regime where the chain is only geometrically ergodic or moments are heavy-tailed, the Richardson-Romberg combination would not cancel the leading bias and the error covariance would not match the optimal one.","tokens_in":1942,"feed_emoji":"🎯","tokens_out":5331,"duration_ms":47428,"temperature":0.7,"pith_summary":"This paper studies linear stochastic approximation (LSA) with constant step size and Polyak-Ruppert averaging under Markovian noise. It shows that the averaged estimator has a bias whose leading term is linear in the step size and cannot be eliminated by averaging alone. The authors then apply Richardson-Romberg extrapolation, which combines runs at step sizes alpha and 2alpha carrying the same noise sequence, and prove that this cancels the leading bias term. They derive high-order moment bounds for the extrapolated estimator and show that its leading error term matches the asymptotically optimal covariance matrix of the vanilla averaged iterates. The result matters because constant-step-size SA is common in practice, and the linear bias has been a known obstacle to fast convergence.","feed_headline":"Step-size bias vanishes under Richardson-Romberg averaging","feed_subtitle":"Averaged LSA with Markov noise keeps an O(alpha) bias; extrapolation removes it while keeping optimal variance.","key_machinery":"The load-bearing object is a novel bias decomposition based on linearizing the LSA update around the solution $\\theta_\\star$. This linearization separates the effects of the step size, the Markov chain dynamics, and the noise, and exposes the leading-order bias as a linear function of $\\alpha$. The Richardson-Romberg extrapolation then uses the same noise realization at two step sizes, $\\alpha$ and $2\\alpha$, so that the linear-in-$\\alpha$ term cancels in the combination $2\\bar{\\theta}_n^{(\\alpha)} - \\bar{\\theta}_n^{(2\\alpha)}$.","core_discovery":"The central discovery is a quantitative decomposition of the bias of Polyak-Ruppert averaged LSA iterates under Markovian noise. The paper proves that, for constant step size $\\alpha$, the bias is dominated by a term linear in $\\alpha$, and it identifies this term explicitly through a linearization technique. Building on this decomposition, the Richardson-Romberg extrapolation estimator, defined as $2\\bar{\\theta}_n^{(\\alpha)} - \\bar{\\theta}_n^{(2\\alpha)}$, cancels the leading bias. The paper establishes high-order moment bounds for the extrapolated estimator and shows that its leading error covariance coincides with the asymptotically optimal covariance matrix of the vanilla averaged LSA estimator","pith_inferences":["The linearization technique likely extends to nonlinear stochastic approximation with smooth updates, where the bias may also be linear in the step size to leading order; the paper only treats the linear case, so this is a natural next step.","In practice, the RR estimator requires running two coupled chains with the same noise; the coupling may reduce the effective sample size relative to two independent runs, and the finite-sample variance gain over simply decreasing $\\alpha$ deserves empirical testing.","A testable extension is to combine $\\alpha$ and $m\\alpha$ for integers $m\\ge 2$: under stronger bias regularity this should cancel higher-order terms as well, at the cost of more coupled chains.","The decomposition's dependence on the Markov chain's mixing properties suggests that the optimal-covariance alignment may degrade for slowly mixing chains, which could be checked numerically on a two-state Markov chain."],"forward_implications":["Constant-step-size LSA with Polyak-Ruppert averaging can achieve bias of order $O(\\alpha^2)$ after Richardson-Romberg extrapolation, improving the error rate without shrinking the step size.","The high-order moment bounds imply that the extrapolated estimator is as stable as the vanilla average, so the bias correction does not amplify tail risk or the number of required moments.","The leading error term of the RR estimator matches the optimal covariance of the vanilla average, meaning the correction is obtained without an asymptotic variance penalty.","The linearization-based bias decomposition may extend to other linear stochastic approximation variants, providing a general recipe for removing first-order bias.","With two coupled chains at step sizes $\\alpha$ and $2\\alpha$, the method is practical whenever the vanilla averaged estimator is computable, and the analysis gives explicit high-order guarantees that were previously missing."],"supporting_citations":[{"why":"Supplies the earlier result that the bias of averaged LSA is linear in $\\alpha$ and the Richardson-Romberg extrapolation construction for LSA; the present paper extends it to high-order moment bounds and covariance alignment.","marker":"Huo, Chen, and Xie 2023a"},{"why":"Establishes the asymptotic normality and optimal covariance of Polyak-Ruppert averaged stochastic approximation; serves as the benchmark for the optimal-variance claim.","marker":"Polyak and Juditsky 1992"},{"why":"Introduces the averaging technique whose bias is the object of study.","marker":"Ruppert 1988"},{"why":"Analyzes constant-step-size LSA with Markovian noise and identifies sources of the bias on which the linearization technique builds.","marker":"Lauand and Meyn 2022a"},{"why":"Shows geometric forgetting and bias structure for constant-step-size SA/SGD, motivating the step-size dependence the paper exploits.","marker":"Dieuleveut, Durmus, and Bach 2020"}],"fun_headline_variants":["Richardson-Romberg cancels leading bias in averaged LSA","Extrapolation removes step-size bias, keeps optimal variance","Markov LSA bias linear in alpha, RR removes it","Averaged LSA bias removed by Richardson-Romberg trick"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The chain $\\{Z_k\\}$ must be sufficiently mixing (uniformly ergodic with bounded moments) and the bias must be smooth enough in the step size that the linear approximation and the two-term Taylor-type expansion are valid; if the bias is not linear in $\\alpha$ or the chain is not ergodic, the cancellation can fail.","fun_headline_variants_meta":{"raw":{"variants":["Richardson-Romberg cancels leading bias in averaged LSA","Extrapolation removes step-size bias, keeps optimal variance","Markov LSA bias linear in alpha, RR removes it","Averaged LSA bias removed by Richardson-Romberg trick"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1288,"prompt_tokens":661,"completion_tokens":627,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":405,"completion_tokens_details":{"reasoning_tokens":564}},"tokens_in":405,"tokens_out":627,"duration_ms":6415,"temperature":1.0,"reasoning_tokens":564,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:12:55.369926+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run constant-step-size averaged LSA on a simple two-state Markov chain with a known linear system, estimate the bias at several step sizes $\\alpha$, and check whether the bias is actually linear in $\\alpha$. If the bias deviates from linearity in a regime where the chain is only geometrically ergodic or moments are heavy-tailed, the Richardson-Romberg combination would not cancel the leading bias and the error covariance would not match the optimal one.","supporting_citations":[],"review_version":1}