{"id":"f595a9d2-3d1e-4db7-aae2-58516573880f","arxiv_id":"2505.20017","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A delayed UCB algorithm for linear bandits with sub-Gaussian but temporally dependent noise achieves sublinear regret that nearly recovers i.i.d. rates when dependence decays geometrically.","lead":"This paper designs a linear bandit algorithm that keeps working when the observation noise is correlated over time, as long as the correlation fades. It proves regret guarantees that, for exponentially fading noise, nearly match the standard independent-noise results.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Confidence-sequence constants in Lemma 1 do not match its proof; the radius is understated, but the claimed regret rates survive after replacing (B+1) by 2B+1.","rationale":"The reader's stated weakest assumption is the oblivious decision-set requirement, which is a transparent scope limitation and not the source of the most immediate correctness risk. The reader's rationale does flag the mismatch between Lemma 1, Theorem 1, and Appendix A.2; I agree that this is the concrete flaw that should be fixed. I differ in emphasis: I consider the constant mismatch, not the oblivious-adversary assumption, to be the single most load-bearing concern, because it affects the written validity of the confidence sequence that all regret bounds rely on. The concern is non-fatal: the correct constant changes the radius by a factor of about two, and the resulting regret rates for geometrically and algebraically mixing noise retain the same leading orders. Therefore the appropriate verdict remains conditional acceptance, pending the correction of these constants. No experiments or code are needed to settle the issue; a careful re-derivation of Lemma 1 and Corollary 1 suffices.","tokens_in":15717,"tokens_out":33388,"duration_ms":371950,"concrete_test":"Restart the derivation of Corollary 1 from the proof's constant: set the squared radius to dp log((B+1)^2 e max(dp,t+d)/(dp)) + 4λB^2 + 4(2B+1)tφ_d + 4d log(d/δ) (or the analogous corrected value), then re-derive Theorem 2 with this β_t. If the leading terms in Corollary 2 remain O(τ p√T log^2 T + τ log T √(pT log T)) up to constants, the paper's central rate claim is confirmed; if the T-dependence changes, the central claim fails. This is a purely algebraic check of the proof chain in Appendix A.2 and Section 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing technical defect is the constant in the confidence sequence. In the proof of Lemma 1 (Appendix A.2), the supermartingale is M_k^(i)=exp(S_k^(i)-(k-1)(2B+1)φ_d), and the key step shows E[exp(D_t-(2B+1)φ_d)|F_{t-d}]≤1, using |λ_t(θ)|≤2B+1 for θ∈B(B+1). Summing the d blocks therefore gives S_t≤(2B+1)t φ_d + d log(d/δ). Lemma 1 as stated has t φ_d B, and Proposition 1, Theorem 1, and Corollary 1 build the confidence radius with t φ_d(B+1). For B>0 this is strictly smaller than the proof allows, so the stated 1-δ coverage of the ellipsoids is not established as written. This is an internal inconsistency in the proof, not a disagreement with existing consensus. It is load-bearing because every regret bound in Section 5 inherits the validity of these confidence sets. That said, the defect is confined to constants: replacing (B+1) by (2B+1) in the radius, and adjusting β_t^2 accordingly, leaves the order of Corollary 2 unchanged, since for d=τ log(BCT/p) the affected term φ_d=p/(BT) contributes at most O(p√(τT log T)), which is already present in the stated rate. The main limitation of oblivious decision sets is disclosed by the authors and is therefore a scope restriction rather than a correctness flaw in the stated claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies stochastic linear bandits with sub-Gaussian but non-independent observation noise, formalized through a new 'mixing sub-Gaussianity' assumption (Assumption 1) in which conditional means and conditional sub-Gaussian tails are controlled by a decaying sequence of mixing coefficients. The authors construct anytime-valid confidence sequences by combining an online-to-confidence-set conversion with a delayed-feedback variant of the underlying online learning game, using a blocking argument to control the dependence across rounds. These confidence sets are used in a UCB algorithm, Mixing-LinUCB (Algorithm 1), that deliberately bases its decisions on confidence sets lagged by d rounds. The main results are a worst-case regret bound (Theorem 2) and a gap-dependent regret bound (Theorem 3) expressed in terms of the mixing coefficients, with corollaries for geometric and algebraic mixing. For geometric mixing and an appropriately chosen delay, the paper claims regret of order O(τ p sqrt(T) log^2 T + τ log T sqrt(pT log T)), which it presents as recovering standard i.i.d. rates up to a factor of the mixing time.","tokens_in":16042,"tokens_out":19169,"duration_ms":197241,"significance":"If the technical gaps are repaired, this is a meaningful extension of linear bandit theory to dependent noise. The paper's key contribution is a natural and well-motivated combination of delayed-feedback online-to-confidence-set conversion with the classical blocking technique for mixing processes, and it makes the dependence of regret on the mixing coefficients explicit. The paper is transparent about its assumptions: known mixing coefficients, oblivious decision sets, and a horizon-dependent choice of delay. It provides detailed proofs and precisely stated constants, and the geometric-mixing corollary gives the right target behavior, namely i.i.d. rates up to logarithmic factors and the mixing time. These strengths make the paper a solid candidate for publication once the load-bearing technical issues are addressed.","major_comments":[{"comment":"The confidence radius stated in Lemma 1 is not supported by its proof. The proof defines M_k^(i) = exp(S_k^(i) - (k-1)(2B+1)φ_d) and establishes S_k^(i) ≤ k(2B+1)φ_d + log(d/δ) for each block, which after the union bound gives Σ_{s=1}^t D_s ≤ t(2B+1)φ_d + d log(d/δ). Lemma 1 as stated has t φ_d B, and Theorem 1, Proposition 1, and Corollary 1 build the confidence radius with the mixing term t φ_d (B+1). For B > 0 this is strictly smaller than the constant (2B+1)φ_d required by the proof, so the claimed 1-δ coverage of the confidence sets is not established as written. Because every regret bound in Section 5 inherits the validity of these confidence sets, this is a load-bearing internal inconsistency. The defect is confined to constants: replacing (B+1) by (2B+1) in the radius and adjusting β_t^2 accordingly leaves the order of all corollaries unchanged, since the affected term contributes at most O(p sqrt(τ T log T)) in the geometric-mixing case.","section":"Section 4.2, Lemma 1 and Appendix A.2"},{"comment":"The sublinear regret guarantees are fixed-horizon rather than anytime. For a fixed delay d, Theorem 2 holds for all T > d but the bound is linear in T; the sublinear rates in Corollaries 2-4 are obtained only by choosing d as a function of the target horizon T, e.g., d = τ log(BCT/p) for geometric mixing. This means the algorithm must know T (or an upper bound on it) to achieve the advertised rates, a point that is acknowledged in Section 6 but not reflected in the abstract or the introductory statement that the bounds 'recover the standard rates.' The authors suggest a time-varying delay could fix this, but they do not provide the analysis. The paper should either supply such an analysis or explicitly qualify the main claims as fixed-horizon guarantees.","section":"Section 5, Theorem 2 and Corollaries 2-4"}],"minor_comments":[{"comment":"The displayed coverage guarantee reads P(θ⋆ ∈ C_t, ∀t ≥ 1) ≤ 1 − δ; the inequality must be ≥ 1 − δ. As written, the statement asserts the opposite of the intended high-probability coverage.","section":"Theorem 1, Section 4.2"},{"comment":"The definition of V_t has typographical errors: the sum is over s but the term is written X_t X_t^⊤, and the identity matrix is written I_d instead of I_p. It should read V_t = Σ_{s=1}^t X_s X_s^⊤ + λ I_p.","section":"Proposition 1, Section 3"},{"comment":"The regret formula contains a stray 't' in the summation: Reg(T) = t∑_{t=1} sup ... should be Reg(T) = Σ_{s=1}^T sup ... .","section":"Section 2, regret definition"},{"comment":"The protocol states that at round s the environment reveals Y_{s-d+1} to the learner, while the loss L_s(Q_s) used in the analysis is evaluated with Y_s. This is legitimate because Q_s is chosen before Y_s is revealed, but the text should explicitly distinguish the information available to the learner for prediction from the loss used by the analyst, otherwise the reader may mistakenly think the learner observes the current reward.","section":"Section 4.2, delayed game protocol"}],"recommendation":"major_revision","confidential_remarks":"The constant mismatch in Lemma 1 is the main obstacle; I believe it is repairable without changing the rates. The horizon-dependent choice of d should be more prominently qualified. The paper is within scope, the techniques are sound in outline, and the authors are honest about the main limitations."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper deserves a serious referee, but only after the authors fix a constant error in the confidence sequence. The setting is new: linear bandits with sub-Gaussian, mixing noise rather than the usual i.i.d. or conditionally centered noise. The algorithm, Mixing-LinUCB, uses a delayed online-to-confidence-set conversion plus blocking, and the paper gives worst-case and gap-dependent regret bounds that recover standard rates up to the mixing time for geometrically mixing noise. That's a meaningful extension, not a revolution.\n\nThe core technical contribution is a confidence sequence for mixing sub-Gaussian noise. The structure is sound and the exposition is honest: the authors clearly flag that the mixing coefficients are assumed known, that the delay d must depend on the horizon T, and that the decision sets must be oblivious. They also include full proofs. That honesty is a real plus.\n\nThe soft spot is in Lemma 1. The lemma states P(sum D_t <= t phi_d B + d log(d/delta)), but the proof in Appendix A.2 constructs a supermartingale with exponent (2B+1) phi_d, using |lambda_t(theta)| <= 2B+1. The union bound over d blocks gives (2B+1) t phi_d, not t phi_d B. Theorem 1 and the subsequent beta_t^2 use t phi_d (B+1), which is also smaller than what the proof allows. So as written, the 1-delta coverage isn't established. This is load-bearing, since every regret bound inherits the confidence sets. That said, it's a constant-factor bug: replace (B+1) by (2B+1) in the radius and the order of all the corollaries stands. The geometric mixing rate tau p sqrt(T) log^2 T still holds because the extra term is absorbed.\n\nMinor: Theorem 1's statement has P(theta* in C_t, for all t) <= 1-delta, which should be >=. Probably a typo.\n\nThe citation pattern looks fair: they build on their own previous work (delayed online-to-PAC) and cite the relevant bandit and mixing literature. No fitted parameters or circular claims.\n\nBottom line: the paper is a legit contribution with a correctable technical defect. I'd send it to review with a strong request to fix the constant and align Lemma 1, Theorem 1, and Corollary 1. After that, it's a solid paper.","headline":"A real new setting and sound proof structure, but a constant mismatch in the confidence sequence that must be fixed before acceptance.","tokens_in":16552,"tokens_out":2223,"would_cite":true,"duration_ms":22458,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that optimism-based linear bandits remain provably sound under temporally correlated, mixing noise, with regret matching the i.i.d. benchmark up to a mixing-time factor for geometric decay.","keywords":["linear bandits","non-i.i.d. noise","mixing sub-Gaussian noise","regret bounds","confidence sequences","online-to-confidence-set conversion","delayed feedback","Mixing-LinUCB"],"falsifier":"A concrete check that would settle the central claim is to run Mixing-LinUCB on a one-dimensional problem with AR(1) noise $\\varepsilon_t = \\rho \\varepsilon_{t-1} + \\eta_t$, choose $d \\approx -1/\\log \\rho$, and compare the empirical regret with the Theorem 2 bound. To test the obliviousness premise, let the decision set at round t depend on $\\varepsilon_{t-1}$ and record how often $\\theta^\\star$ lies in $C_t$; the paper's proof requires coverage with probability at least $1-\\delta$ and predicts this adaptive choice can break it even though the noise still satisfies Assumption 1.","tokens_in":15536,"feed_emoji":"🎰","tokens_out":9958,"duration_ms":89936,"temperature":0.7,"pith_summary":"The paper relaxes the standard i.i.d. assumption on the observation noise in linear stochastic bandits, allowing noise terms that are sub-Gaussian but correlated, with dependence that decays over time. It constructs anytime-valid confidence sets by splitting the rounds into d interleaved subsequences, running an online prediction game with delayed feedback on each, and applying a per-block martingale inequality. These confidence sets feed an optimistic arm-selection rule, Mixing-LinUCB, whose regret is bounded in terms of the mixing coefficients. For geometrically mixing noise, the bound recovers the standard i.i.d. rate up to a factor of the mixing time and logarithmic factors, which matters because realistic noise in applications such as ad selection is temporally correlated.","feed_headline":"Dependent noise tamed: linear bandits match clean-noise rates","feed_subtitle":"A delayed UCB algorithm stays sound when noise is correlated but its influence fades","key_machinery":"The central object is a delayed online-to-confidence-set conversion. The abstract sequential probability assignment game is played by d independent exponentially weighted average forecasters, each active on a different residue class of rounds modulo d, and the reward feedback is delayed by d rounds; the joint forecaster's regret is bounded by summing the individual regrets. Concentration is handled by blocking: each residue class is a subsequence on which $\\exp(S_k^{(i)} - (k-1)(2B+1)\\varphi_d)$ is a non-negative supermartingale, so Ville's inequality plus a union bound gives the anytime-valid inequality in Lemma 1. A delayed version of the elliptical potential lemma, Lemma 3, controls the sum of norm terms that appear when bounding regret from the confidence ellipsoids.","core_discovery":"On the paper's own terms, the discovery is that the optimistic linear-bandit strategy remains sound when the noise is only mixing sub-Gaussian rather than conditionally independent. Under Assumption 1, the ellipsoidal confidence sets centered at the regularized least-squares estimator are anytime valid, provided the agent plays with a delay d: at round t it chooses the arm maximizing the upper confidence bound computed from data up to t-d. Theorem 2 gives a high-probability regret bound of order $2dB + \\sqrt{8dpT \\max(B^2, \\beta_T^2) \\log(1 + B^2T/(dp))}$; with geometric mixing and $d = \\lceil \\tau \\log(BCT/p) \\rceil$, Corollary 2 states the regret is $O(\\tau p \\sqrt{T} \\log^2 T + \\tau \\log T \\sqrt{pT \\log T})$, matching the i.i.d. benchmark up to the mixing time $\\tau$ and logarithmic factors. For algebraically mixing noise, the regret is sublinear when the decay exponent $r > 1$ and approaches standard rates as $r \\to \\infty$.","pith_inferences":["The same delayed-block construction should transfer to other optimistic bandit algorithms (generalized linear, kernel, or even nonlinear) as long as the noise satisfies an analogous mixing-sub-Gaussian condition, because the confidence-sequence argument is decoupled from the linear reward model.","A time-varying delay that grows slowly with t should remove the need to know the horizon T and yield fully anytime regret bounds; the paper mentions this route but leaves the details open.","The restriction to oblivious decision sets means the algorithm is safe when contexts are precommitted or based on stale data, but not when they react to recent outcomes; relaxing that would require a different concentration argument.","Since the algebraic-mixing bound is trivial for $r \\le 1$, the practical gains concentrate on noise whose dependence decays faster than $1/t$, such as ARMA or Markov chains with finite mixing time."],"forward_implications":["Under geometric mixing, the regret bound is $O(\\tau p \\sqrt{T} \\log^2 T + \\tau \\log T \\sqrt{pT \\log T})$, so the cost of dependence is essentially the mixing time $\\tau$ times log factors.","For algebraically mixing noise with exponent $r>1$, the algorithm achieves sublinear regret, and the bound converges to the i.i.d. rate as $r$ grows.","With a positive minimum gap $\\Delta$, the bound becomes roughly $O((dp/\\Delta) \\max(B^2, \\beta_T^2) \\log(1 + B^2T/(dp)))$, giving near-logarithmic regret in $T$ for suitable $d$.","For any fixed delay $d$ that does not grow with $T$, the worst-case bound is linear in $T$, so the delay has to track the horizon or the decay rate of the noise dependence."],"supporting_citations":[{"why":"Supplies the online-to-confidence-set conversion scheme and the EWA regret bound that the delayed construction starts from.","marker":"Clerico et al. (2025)"},{"why":"Introduces the delayed-feedback online-to-PAC conversion for mixing data that motivates the delayed game and blockwise martingale argument.","marker":"Abélès et al. (2025)"},{"why":"Provides the blocking technique used to turn weak dependence into per-block concentration.","marker":"Yu (1994)"},{"why":"Gives the optimistic linear-UCB template and the elliptical potential lemma that the regret analysis adapts to delayed updates.","marker":"Abbasi-Yadkori et al. (2011)"},{"why":"Is the standard reference for linear bandit confidence sets and regret analysis that sets the i.i.d. baseline being recovered.","marker":"Lattimore and Szepesvári (2020)"},{"why":"Supports splitting rounds into d interleaved subsequences to bound the regret of the delayed joint forecaster.","marker":"Weinberger and Ordentlich (2002)"},{"why":"Is cited for the definition and properties of mixing conditions that connect phi-mixing to the paper's Assumption 1.","marker":"Bradley (2005)"},{"why":"Supplies the no-hypercompression inequality behind the supermartingale interpretation of the online-to-confidence-set conversion.","marker":"Grünwald (2007)"}],"fun_headline_variants":["Delayed UCB tames dependent noise in linear bandits","Mixing noise no match: linear bandits hit i.i.d. rates","Linear bandits survive correlated noise with delay","Dependent noise solved: linear bandits match clean rates","Delayed optimism beats non-i.i.d. noise in bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The decision sets must be chosen obliviously, before any noise is observed, so the arm at round t can depend only on information at least d rounds old; if an adaptive adversary picks decision sets using recent noise, the per-block supermartingale argument in Lemma 1 stops working.","fun_headline_variants_meta":{"raw":{"variants":["Delayed UCB tames dependent noise in linear bandits","Mixing noise no match: linear bandits hit i.i.d. rates","Linear bandits survive correlated noise with delay","Dependent noise solved: linear bandits match clean rates","Delayed optimism beats non-i.i.d. noise in bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000181,"raw_usage":{"total_tokens":1285,"prompt_tokens":898,"completion_tokens":387,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":514,"completion_tokens_details":{"reasoning_tokens":302}},"tokens_in":514,"tokens_out":387,"duration_ms":62870,"temperature":1.0,"reasoning_tokens":302,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:01:32.298473+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check that would settle the central claim is to run Mixing-LinUCB on a one-dimensional problem with AR(1) noise $\\varepsilon_t = \\rho \\varepsilon_{t-1} + \\eta_t$, choose $d \\approx -1/\\log \\rho$, and compare the empirical regret with the Theorem 2 bound. To test the obliviousness premise, let the decision set at round t depend on $\\varepsilon_{t-1}$ and record how often $\\theta^\\star$ lies in $C_t$; the paper's proof requires coverage with probability at least $1-\\delta$ and predicts this adaptive choice can break it even though the noise still satisfies Assumption 1.","supporting_citations":[],"review_version":1}