{"id":"5916943f-6409-40ef-8168-040c01076e80","arxiv_id":"2506.13390","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new design and a sharper analysis of orthogonalized regression yield optimal regret, logarithmic regret under gaps, and the first PAC and best-arm identification guarantees for semiparametric bandits.","lead":"This paper gives the first near-optimal bandit algorithm for rewards made of a linear model plus an unpredictable per-round shift, matching the best known rate for ordinary linear bandits. It also provides the first guarantees for finding the best arm and for certifying any recommended arm in this setting.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6 proof has an invalid phase-count step: Lemma 14 and D.2 replace Σ 2^ℓ by d² L_T and then substitute L_T for 2^{L_T}; the headline √dT regret bound is not derived as written.","rationale":"I agree with the reader's overall CONDITIONAL assessment but locate the load-bearing weakness differently. The reader's weakest_assumption is the arm-invariance of the shift ν_t; that is a real modeling boundary, but within the paper's stated model the centering argument is internally consistent. The more direct threat to the central claim is the phase-count algebra in the proof of Theorem 6. Lemma 14's bound and the subsequent substitution in D.2 are not valid as written: one factor is 2^{L_T}, not L_T, and the proof swaps the two. This is exactly the kind of omitted or incorrect derivation that must be fixed before the √dT regret bound can be considered established. The fix appears straightforward — use the direct sum Σ_ℓ d/ε_ℓ and Lemma 15 — so I do not move the verdict to reject or unverdict; the paper should remain conditionally accepted pending a corrected proof. I mark agreement as partial because the reader did flag 'phase-count algebra' among minor issues but did not treat it as the weakest assumption, whereas I see it as the primary load-bearing concern.","tokens_in":28272,"tokens_out":27848,"duration_ms":273504,"concrete_test":"Re-derive the phase-elimination regret bound in Appendix D directly: under event E_T, Reg(T) ≤ C Σ_{ℓ=1}^{L_T} [d log(dKℓ/(δε_ℓ))/ε_ℓ + d^{3/2} log(dKℓ/δ)] with ε_ℓ = 2^{-ℓ}. Bound Σ_ℓ 1/ε_ℓ ≤ 2·2^{L_T}, combine with Lemma 15's 2^{L_T} ≤ c√(T/(d log(dK/δ))), and verify that the resulting expression contains the three displayed terms of Theorem 6. If the direct sum yields √(dT log K) plus the d^{3/2} log² term, the theorem is salvageable with a corrected proof; if not, the claimed √dT rate is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on the proof of Theorem 6 in Appendix D, and that proof contains an algebraic transition that does not go through. Lemma 14 first obtains Reg(T) ≲ Σ_{ℓ=1}^{L_T} d log(...)/ε_ℓ + d^{3/2} log(...) with ε_ℓ = 2^{-ℓ}. The next step in the proof replaces the sum Σ_ℓ 1/ε_ℓ = O(2^{L_T}) by d² L_T (log + L_T), which is not an upper bound when 2^{L_T} is larger than d L_T. Then, in the displayed calculation of D.2, the proof writes d² L_T as d√(T/(d log(dK/δ))), invoking Lemma 15. But Lemma 15 bounds 2^{L_T}, not L_T; it gives L_T ≤ (1/2) log(T/(d log(dK/δ))). Taken literally, Lemma 14 plus Lemma 15 would produce a bound of order d² log(T/d) + d^{3/2} log²(T/d), not √(dT) log K. The √dT rate is recoverable by bounding the direct sum Σ_ℓ d/ε_ℓ ≤ d·2^{L_T} and then applying Lemma 15, but that corrected argument is not what the paper presents. Since Theorem 6 is the paper's headline claim, the missing derivation is a load-bearing weak point in the submission as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies a finite-armed semiparametric bandit model in which the reward of arm i at time t is x_i^T θ* + ν_t + η_t, with ν_t an H_{t-1}-measurable bounded shift common to all arms. The authors introduce an experimental-design procedure (DEO) for orthogonalized regression: put mass 1/2 on an anchor arm and use a G-optimal design on the differences x_i - x_1. They prove a design-cost bound of O(√d) (Theorem 3) and a non-asymptotic estimation error bound whose leading term is √L/√t (Theorem 4), avoiding the previous Cauchy–Schwarz-based bounds. These ingredients are used to give pure-exploration PAC/BAI guarantees and a phase-elimination algorithm SBE with claimed instance-independent regret eO(√dT logK) (Theorem 6), gap-dependent logarithmic regret (Theorem 7), and simultaneous PAC and BAI guarantees (Theorem 8). The appendix contains detailed proofs, including a martingale-based error decomposition for the estimation error.","tokens_in":28589,"tokens_out":14506,"duration_ms":137658,"significance":"If the results hold, this is a substantial advance: it would give the first √d-rate regret bound for semiparametric bandits, matching the finite-armed linear bandit lower bound up to logarithmic factors, and it would be the first work to bring experimental design, PAC, and best-arm-identification guarantees to this model. The DEO design itself is simple and computationally efficient, requiring only O(log T) design computations, and the estimation analysis in Theorem 4 is a genuine improvement over the Cauchy–Schwarz-based arguments used in prior work. The paper is also careful about the dependence on K and about the non-convexity introduced by centering. However, the proof of the headline regret bound contains a specific algebraic gap in the phase-counting step, which directly affects Theorem 6 and also propagates to Theorem 7; the result is likely repairable, but the current text does not derive the claimed rate.","major_comments":[{"comment":"The phase-counting step in Lemma 14 is invalid. The proof passes from Σ_{ℓ=1}^{L_T} (d log(dKL_T/δ) + dℓ)/ε_ℓ to d²L_T(log(dKL_T/δ)+L_T). Since ε_ℓ = 2^{-ℓ}, the left-hand side contains a geometric sum of order d 2^{L_T}, while the right-hand side replaces 2^{L_T} by dL_T; for L_T modestly large, 2^{L_T} is not bounded by dL_T, and no prior argument establishes such a bound. The subsequent display in D.2 compounds this by substituting √(T/(d log(dK/δ))) for L_T 'by Lemma 15', but Lemma 15 bounds 2^{L_T}, not L_T. Thus the claimed √(dT) regret bound is not derived as written. The gap appears fixable: one can bound the direct sums Σ_ℓ d/ε_ℓ and Σ_ℓ dℓ/ε_ℓ by d·2^{L_T} and d·L_T·2^{L_T}, respectively, and then apply Lemma 15; I recommend rewriting Lemma 14 and D.2 along these lines. After such a repair, the displayed d^{3/2} log(dKT/δ) log(T/d) term in Theorem 6 is not eO(√dT logK) for T comparable to d under the paper's convention that eO hides only logarithmic factors of d and T, so the theorem should either state the required regime or be presented in the min(eO(√dT logK), eO(d√T)) form already discussed in the paper.","section":"Appendix D.1–D.2 (Lemma 14 and proof of Theorem 6)"},{"comment":"The same erroneous replacement appears in the gap-dependent proof. In D.3, the sum Σ_{ℓ=1}^{L⋆} d log(...)/ε_ℓ is again replaced by d²L⋆ log(...), and then d²L⋆ is subsequently replaced by d/Δ⋆ to obtain the final (d/Δ⋆ + d^{3/2})log rate. Neither replacement is justified: the first equates a geometric sum of size 2^{L⋆} ≍ 1/Δ⋆ with L⋆, and the second requires dL⋆ ≍ 1/Δ⋆, which is not true for the definition L⋆ = ⌈log₂(1/Δ⋆)⌉+1 in general. Since Theorem 7 is one of the paper's advertised contributions, this proof step also needs to be corrected.","section":"Appendix D.3 (proof of Theorem 7)"}],"minor_comments":[{"comment":"The abstract states the minimax regret as eO(√dT), but §1.3 defines eO as hiding only log factors of d and T and not logK, and the introduction and Theorem 6 state eO(√dT logK); the abstract should be made consistent with the convention.","section":"Abstract and §1.3"},{"comment":"The displayed bound says τ(ε,δ) ≥ C₂(...), but the proof derives an upper bound on the number of samples needed; the inequality should be τ(ε,δ) ≤ C₂(...).","section":"Corollary 5"},{"comment":"The bound on ‖Σ_s e_s q_s‖₂ is imported from Lemma 10 of Kim et al. (2021) without stating the lemma; since this is one of the few non-standard ingredients in the proof of Theorem 4, please reproduce its statement or give a self-contained proof so the appendix is complete.","section":"Appendix B, Step 3-2"},{"comment":"The notation for the min of the two sample complexities mixes constants C₂, C₃, and C₄ without a clear definition; the displayed formula in Appendix E and the proof in F.4 should use consistent labels.","section":"Appendix H and Theorem 18"},{"comment":"There are several typos: 'Compuational Effeiciency' and 'poicy' in Appendix H, and the figure captions mention a 'cosine' shift although the text defines only sine and log shifts; these should be corrected.","section":"Appendix H and figure captions"}],"recommendation":"major_revision","confidential_remarks":"The gap in the proof of Theorem 6 is substantial enough that the paper should not be accepted in its current form, but I believe it is fixable by the direct geometric-sum argument, so rejection is not warranted. The authors should also verify whether the final d^{3/2} term is genuinely dominated under their stated eO convention, and should state the exact form of the Ge et al. (2023) lower bound used in Theorem 4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Top line: this is a serious paper with a real advance, but the proof of the headline theorem has a gap that needs to be fixed before the result is claimed.\n\nThe genuine novelty is the DEO design: shifting features by x_1 and running G-optimal design on the differences reduces the non-convex orthogonalized-regression design problem to a classical one, and Theorem 3 gives the √d bound. Theorem 4's decorrelation argument is the technical heart and is a real improvement over the Cauchy–Schwarz analysis used by all prior work. The PAC and BAI corollaries are new for this model, and the paper is honest about the BAI sample complexity not being instance-optimal. The appendix proofs are detailed and, apart from the issue below, structurally sound.\n\nThe problem is in the proof of Theorem 6. Lemma 14 derives a bound with a sum over phases of d/ε_ℓ, which is O(d·2^{L_T}). The proof then replaces that sum by d²L_T, and in D.2 substitutes L_T with the Lemma 15 bound on 2^{L_T}. That substitution is not valid; Lemma 15 says 2^{L_T} ≲ sqrt(T/(d log)), not L_T. Taken literally, Lemma 14 plus Lemma 15 gives d² log(T/d), not √(dT). The claimed rate is recoverable: bound Σ d/ε_ℓ directly by d·2^{L_T} and apply Lemma 15. But as written, the step does not go through. Since Theorem 6 is the paper's headline contribution, this is not a cosmetic typo. The fix is short, and the result is likely correct, but the authors need to redo that part of the proof.\n\nMinor things: the abstract drops the log K factor from the minimax rate (their eO convention explicitly does not hide log K), and Corollary 5 writes τ ≥ ... where it should be τ ≤ ... .\n\nThe model assumption that ν_t is a single scalar affecting all arms in a round is explicit and standard in the semiparametric bandit literature. It is a scope limitation—arm-specific shifts would break the centering—but not an unstated one.\n\nWho this is for: bandit theorists, especially anyone working on orthogonalized regression or design-based methods for structured bandits. It deserves a serious referee: the ideas are good, the writing is clear, and the gap is fixable. I would send it out and require the proof correction before acceptance.","headline":"A genuine advance in semiparametric bandits, but the proof of the headline √dT regret bound has an invalid phase-count step that needs fixing.","tokens_in":29130,"tokens_out":3932,"would_cite":true,"duration_ms":33707,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62K05","62L05","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the unknown common shift in a semiparametric bandit can be handled at no asymptotic cost: the regret matches the linear-bandit minimax rate $\\tilde O(\\sqrt{dT}\\log K)$, with PAC and best-arm guarantees as a byproduct.","keywords":["semiparametric bandits","orthogonalized regression","G-optimal design","regret minimization","best-arm identification","PAC bounds","phase elimination","adversarial shift"],"falsifier":"Take the lower-bound instance from Step 5 of Theorem 4: fix any design $p$, set $\\nu_s=-\\bar{x}_p^\\top\\theta^\\star$ (a legal common shift), and take Gaussian noise, so the reward becomes the linear model $(x_{a_s}-\\bar{x}_p)^\\top\\theta^\\star+\\eta_s$. Compute the minimax error $\\inf_{\\hat\\theta}\\sup_{\\theta}|(x_i-x_1)^\\top(\\hat\\theta-\\theta^\\star)|$ over $t$ samples: the paper's Theorem 4 predicts a rate $\\Theta(\\sqrt{d}/\\sqrt{t})$; if the true rate is $\\Theta(d/\\sqrt{t})$, the claimed optimal $\\sqrt d$ dependence is wrong.","tokens_in":28079,"feed_emoji":"🎰","tokens_out":16036,"duration_ms":136864,"temperature":0.7,"pith_summary":"The paper studies finite-armed bandits where each arm has a feature vector $x_i$, the expected reward is $x_i^\\top \\theta^\\star$ plus an unknown shift $\\nu_t$ that can change adversarially every round, and the shift is common to all arms in that round. It aims to establish that this shift costs nothing asymptotically: a phase-elimination algorithm called SBE achieves cumulative regret $\\tilde O(\\sqrt{dT}\\log K)$, matching the minimax lower bound for purely linear bandits even though the model is strictly larger. This is the first $\\sqrt d$-rate regret bound for semiparametric bandits, and SBE also returns a PAC learner and a best-arm identifier while running, and gives logarithmic regret when the optimal arm has a positive suboptimality gap, for instance $\\tilde O(d\\log K/\\Delta_\\star)$. The reason this is worth caring about is practical: time-varying baselines, trends, and external interference appear in recommendation and clinical settings, and earlier algorithms paid extra factors of $d$.","feed_headline":"Bandit method matches optimal regret rate despite hidden shifts","feed_subtitle":"First semiparametric bandit algorithm that also gives PAC and best-arm guarantees.","key_machinery":"The load-bearing mechanism is orthogonalized ridge regression on centered features, together with a two-part design trick. The estimator regresses rewards on $\\tilde x_{a_s}=x_{a_s}-\\mathbb E[x_{a_s}\\mid \\mathcal H_{s-1}]$, so the unknown shift $\\nu_s$ is absorbed into a martingale difference and cancels in arm comparisons. The DEO design solves the non-convex design problem implicitly: it places half the probability mass on an anchor arm $x_1$ and runs the standard linear G-optimal design on the difference vectors $\\{x_i-x_1\\}$ with the remaining mass. The identity $\\Sigma_p=\\sum_{i<j}p_ip_j(x_i-x_j)(x_i-x_j)^\\top$ shows the resulting covariance is at least a quarter of the linear design's second moment, giving $\\|x_i-x_1\\|_{\\Sigma_{deo}^{-1}}\\le 2\\sqrt d$. The sharp statistical rate comes from a decoupling step in Theorem 4: the inverse covariance matrix is separated from the martingale of centered features, so the error is controlled by $\\sqrt L/\\sqrt t$ rather than by Cauchy-Schwarz's $d/\\sqrt t$.","core_discovery":"The central claim is that the unknown shift $\\nu_t$ can be handled without sacrificing the optimal dimension dependence. Because $\\nu_t$ is assumed common to all arms in a round, the difference between two arms' expected rewards is $(x_i-x_j)^\\top\\theta^\\star$; the algorithm never needs to estimate $\\nu_t$ itself. Orthogonalized regression centers each sampled feature by its conditional mean, $\\tilde x_{a_s}=x_{a_s}-\\mathbb E[x_{a_s}\\mid \\mathcal H_{s-1}]$, which turns $\\nu_s$ into a martingale term rather than a bias. The paper proves an estimation-error bound for this estimator, $|z^\\top(\\hat\\theta_t-\\theta^\\star)|=O(\\sqrt{L\\log(t/\\delta)}/\\sqrt t + \\sqrt{LM}\\log(d/\\delta)/t)$ with $L=\\|z\\|_{\\Sigma_p^{-1}}^2$ and $M=\\max_i\\|x_i-\\bar x_p\\|_{\\Sigma_p^{-1}}^2$, attaining the $\\sqrt d/\\sqrt t$ rate. Combined with the DEO design, whose covariance satisfies $\\Sigma_{deo}\\succeq \\tfrac14 \\Sigma_{opt,1}$ so that $\\|x_i-x_1\\|_{\\Sigma_{deo}^{-1}}\\le 2\\sqrt d$, this yields SBE's $\\tilde O(\\sqrt{dT}\\log K)$ regret, gap-dependent logarithmic regret, and the first PAC and best-arm identification guarantees for semiparametric bandits.","pith_inferences":["Inference: The common-shift assumption is the true boundary of the result; if $\\nu_t$ were arm-specific, the cancellation $(x_i-x_1)^\\top\\hat\\theta_t$ would fail and regret would plausibly degrade to linear. A testable variant is to add arm-dependent offsets and measure how the regret scales.","Inference: DEO is a generic reduction: any G-optimal design for linear bandits on the difference vectors, mixed with half the mass on an anchor arm, yields a semiparametric design with only a constant-factor loss. This may simplify future algorithms for other semiparametric objectives.","Inference: The decoupling technique used to prove Theorem 4, separating the random inverse covariance from the centered-feature martingale, is transferable to other estimation problems with non-anticipatory shifts, such as offline policy evaluation.","Inference: The MAB application suggests a broader recipe for non-stationary rewards: model the shared time-varying baseline nonparametrically and compare arms through differences, rather than modeling each arm's absolute reward."],"forward_implications":["The common adversarial shift is asymptotically free: SBE's regret has the same order, up to logarithms, as the minimax lower bound for finite-armed linear bandits.","A single algorithm simultaneously minimizes regret, satisfies an $(\\epsilon,\\delta)$-PAC guarantee with sample complexity $\\tilde O(d\\log K/\\epsilon^2)$, and identifies the best arm in $\\tilde O(d\\log K/\\Delta_\\star^2)$ pulls.","When the best arm is separated by a gap $\\Delta_\\star$, regret becomes logarithmic, of order $\\tilde O(d\\log K/\\Delta_\\star)$; exploration effectively stops once the gap is certified.","Applied to $K$ unstructured arms with common time-varying shifts, the method yields $\\tilde O(\\sqrt{KT})$ regret, matching the multi-armed bandit rate.","The sharp non-asymptotic analysis of orthogonalized regression, which removes the $\\sqrt d$ factor that Cauchy-Schwarz arguments leave in the error rate, is a reusable statistical result independent of the bandit framing."],"supporting_citations":[{"why":"Introduced the action-centered model with a baseline shift, the setting this paper generalizes.","marker":"Greenewald et al. (2017)"},{"why":"Supplies the orthogonalized ridge estimator and a $\\tilde O(d\\sqrt T)$ bound that SBE improves; the baseline to beat.","marker":"Krishnamurthy et al. (2018)"},{"why":"Thompson-sampling method with $\\tilde O(d^{3/2}\\sqrt T)$ regret, another prior bound the new result improves.","marker":"Kim and Paik (2019)"},{"why":"Computationally efficient $\\tilde O(d\\sqrt T)$ algorithm; comparison baseline.","marker":"Chowdhury et al. (2023)"},{"why":"Provides the G-optimal design and phase-elimination template plus the finite-armed linear lower bound that sets the target $\\tilde O(\\sqrt{dT}\\log K)$.","marker":"Lattimore and Szepesvári (2019)"},{"why":"Establishes the $\\tilde O(\\sqrt{dT}\\log K)$ lower bound for finite-armed linear bandits that the paper's guarantee matches.","marker":"Li et al. (2019)"},{"why":"Gives G-optimal design for best-arm identification in linear bandits and the sample-complexity rates the paper matches.","marker":"Soare et al. (2014)"},{"why":"Provides the dimension-free martingale concentration inequality used in the decorrelation step of the sharp estimation bound.","marker":"Kim et al. (2021)"}],"fun_headline_variants":["First semiparametric bandit with all key guarantees","Hidden shifts no obstacle for optimal bandit regret","Orthogonalized regression yields optimal semiparametric bandit regret","Optimal regret, PAC, and best-arm for shifted bandits","Experimental design overcomes shift bias in bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires the unknown shift to be a single value shared by all arms in each round and fixed before the arm is chosen, so that comparing arms cancels it.","fun_headline_variants_meta":{"raw":{"variants":["First semiparametric bandit with all key guarantees","Hidden shifts no obstacle for optimal bandit regret","Orthogonalized regression yields optimal semiparametric bandit regret","Optimal regret, PAC, and best-arm for shifted bandits","Experimental design overcomes shift bias in bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000737,"raw_usage":{"total_tokens":3313,"prompt_tokens":984,"completion_tokens":2329,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":2248}},"tokens_in":600,"tokens_out":2329,"duration_ms":20716,"temperature":1.0,"reasoning_tokens":2248,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:06:09.828971+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the lower-bound instance from Step 5 of Theorem 4: fix any design $p$, set $\\nu_s=-\\bar{x}_p^\\top\\theta^\\star$ (a legal common shift), and take Gaussian noise, so the reward becomes the linear model $(x_{a_s}-\\bar{x}_p)^\\top\\theta^\\star+\\eta_s$. Compute the minimax error $\\inf_{\\hat\\theta}\\sup_{\\theta}|(x_i-x_1)^\\top(\\hat\\theta-\\theta^\\star)|$ over $t$ samples: the paper's Theorem 4 predicts a rate $\\Theta(\\sqrt{d}/\\sqrt{t})$; if the true rate is $\\Theta(d/\\sqrt{t})$, the claimed optimal $\\sqrt d$ dependence is wrong.","supporting_citations":[{"cited_title":"(2018) and semiparametric-TS of Kim and Paik (2019)","cited_arxiv_id":null,"evidence_quote":"Supplies the orthogonalized ridge estimator and a $\\tilde O(d\\sqrt T)$ bound that SBE improves; the baseline to beat."},{"cited_title":"(2021)), we aim to bound∥Pt s=1esqs∥2","cited_arxiv_id":null,"evidence_quote":"Provides the dimension-free martingale concentration inequality used in the decorrelation step of the sharp estimation bound."}],"review_version":2}