{"id":"3f189df3-4ae9-4014-a9b6-74d4b80a4658","arxiv_id":"2607.23432","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"RAEC’s predetermined reserved exploration achieves matching minimax regret for post-commitment reward-shift bandits across short-experiment, balanced, and short-commitment regimes.","lead":"The paper gives tight regret rates for experiments that must later lock in one option after rewards change. It shows a simple pre-reserved exploration budget is enough, and more adaptive allocation does not improve the leading rate.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"No significant objection identified. The minimax characterization (Thm 3.1 ↔ Thm 5.2) is internally consistent in all three regimes; the only thin spot in the evidence chain is that the numerics run a constant-modified RAEC, not the algorithm as stated.","rationale":"The reader's verdict (ACCEPT) and weakest-assumption identification are both sound. The central claim — RAEC's predetermined reservation attains the minimax rate in all three (N, T) regimes, so adaptive allocation cannot improve the leading rate — rests on (a) Prop 4.1 → Thm 3.1 region algebra and (b) the Thm 5.2 lower bound; I re-worked both at the level of detail given and found them internally consistent, including the boundary conditions where the unified min/max rate switches regimes and the absorption of all failure-probability terms. The identifiability of post-shift means (§2.1) is indeed the most consequential premise: everything else is conditional on it. But it is explicit, standard for this model class, and the paper itself states the impossibility result without it, so it functions as a declared modeling choice rather than a soft spot in the argument. The two extensions are coherent: the perturbed-affine analysis (Thm C.1) and the ROSCOC bound (Thm 6.1) both reduce to the baseline rates at the right parameter settings, and the portfolio tightness argument via restriction to E_coord with linear g is a valid reduction. The residual weakness is evidentiary rather than logical: no released code, and the numerics modify the algorithm's constants and normalize the theory curve to the last data point, so they support slope agreement for a constant-rescaled RAEC. That warrants the proposed replication but does not move the verdict. Correctness risk stays at the human-checked-proof level the reader assigned; I see no basis to adjust ACCEPT in either direction.","tokens_in":43260,"tokens_out":14098,"duration_ms":404284,"concrete_test":"Re-run the §7.1 balanced-regime panel (N = ⌊T/4⌋, K = 4, hard instance with Δ_g = 0.3(K/(T−N))^{1/3}, T up to 2×10^4) using RAEC exactly as specified in Algorithm 1 with ε from Thm 3.1 — no (1/10)m_{g,ℓ} scaling. Check (i) Stage-I feasibility K·m_{g,L} ≤ N holds at each T, and (ii) the log-log regret slope over the seven horizons. If exact-RAEC's fitted slope deviates materially from 2/3 or feasibility fails at small T, the empirical support for the tight-rate claim is doing less work than §7.1 suggests. Independently, hand-verify the exponent step exp(−E_I[T_{j†}]·D(0,2δ_g)) with E_I[T_{j†}] ≤ E_I[T_B]/(K/2−1) in the balanced-instance lower bound of Thm 5.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I stress-tested the load-bearing chain behind the headline claim (predetermined reservation is minimax rate-optimal) and could not make a concern land. (1) Upper bound: Proposition 4.1's instance-dependent bound converts to the three regimes in Thm 3.1; I re-checked the Region II group-splitting algebra (groups 1a/1b/2 thresholds and the condition (T−N) ≥ K^{1/4}N^{3/4}·log^{3/4}/log^{1/2} used to absorb the group-1b sum) and the Region I feasibility floor ε = 4√(K log(T−N)/N), which indeed gives K·m_{g,L} ≤ N/4. The failure-probability terms (K log N/N, KN log(1/ε)/(T−N)², K log(1/ε)/(T−N)) are genuinely absorbed by the displayed rates given the third component of ε. (2) Lower bound: the two-instance Bretagnolle–Huber argument in Thm 5.2 holds for all policies (no consistency restriction needed); the exponent bookkeeping E_I[T_{i†}] ≤ E_I[T_A]/(K/2−1), E_I[T_{j†}] ≤ E_I[T_B]/(K/2−1) with D ≍ δ² is standard, and each of the three (δ_f, δ_g) choices reproduces the corresponding regime rate; the unified min/max expression algebraically reduces to √(K(T−N)²/N), K^{1/3}(T−N)^{2/3}, √(KN) in Regions I/II/III respectively, matching the upper bound up to logs. (3) The identifiability premise the reader flagged (outcomes scorable under both f and g, or paired independent signals, §2.1) is stated explicitly and paired with an impossibility statement without it; it is a modeling assumption, not a hidden step. Sanity checks (g≡0 recovering Õ(√(KN)), f≡0 recovering Õ(√(K/N)) simple regret) go through. The one place the evidence is thinner than presented: §7's experiments implement RAEC with Stage-I counts scaled by 1/10–1/25 and pin the theory curve to the final empirical point, so they corroborate slopes of a modified algorithm rather than testing RAEC as written — a corroboration gap, not a claim-breaking flaw.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper studies a two-phase stochastic bandit problem: an experiment phase of exogenous length N with reward function f, followed by a commitment phase of length T−N in which a single arm must be played under a different (but known) reward function g. The authors propose RAEC, a phased arm-elimination algorithm that reserves a predetermined number of epochs (parameterized by ε) for learning the g-optimal arm and spends the remainder on f-regret minimization. They prove an instance-dependent upper bound (Prop. 4.1) and derive regret rates in three regimes (Thm 3.1): Õ(√(KT²/N)) for short experiment, Õ(K^{1/3}(T−N)^{2/3}) in the balanced regime, and Õ(√(KT)) for short commitment. A minimax lower bound based on a two-instance Bretagnolle–Huber argument over an independent-coordinate Bernoulli subclass matches these rates for all policies (Thm 5.2), and an instance-dependent lower bound for consistent policies is also given (Thm 5.1). Two extensions treat a perturbed-affine shift structure (where ranking changes, not magnitudes, drive regret) and a concave portfolio commitment model solved by ROSCOC with a matching rate via reduction. Numerical experiments illustrate the predicted scaling and gains over UCB baselines.","tokens_in":43803,"tokens_out":7389,"duration_ms":53261,"significance":"If the results hold — and I found no reason to doubt them — the paper delivers a complete minimax characterization of an operationally motivated two-phase experimentation problem. The balanced-regime rate K^{1/3}(T−N)^{2/3} is, to my knowledge, new, and the paper proves (not just conjectures) that predetermined reservation is rate-optimal, a clean and somewhat counterintuitive message. Strengths worth naming: matching upper and lower bounds in all three regimes; a lower bound that holds for all policies; an explicit, honestly stated identifiability premise paired with an impossibility statement; a portfolio extension whose tightness is obtained by reduction rather than ignored; and sanity checks (g≡0, f≡0) recovering classical rates. The numerical section is weaker than the theory but supportive. The paper is well-situated relative to Bui et al. (2011) and Qin and Russo (2024).","major_comments":[{"comment":"§7.1–7.3: In four of five schedules in §7.1, and throughout §7.2–7.3, the experiments run constant-modified variants of the stated algorithms (Stage-I targets (1/10)m_{g,ℓ} or (1/25)m_{g,ℓ}, Stage-II targets (1/10)m_{f,ℓ}, Stage-I length 0.3τ), while the abstract claims the proposed algorithms achieve the predicted regret. Constant factors do not affect log-log slopes, so the scaling conclusions are defensible, but the abstract-level claim is not literally tested. Please either (i) add at least one regime with the unmodified Algorithm 1, or (ii) state precisely why the rescaling preserves the elimination invariants of Lemmas 4.2–4.4 (it does, since only concentration constants change, but this should be argued), and soften the abstract claim accordingly. Relatedly, the validation in Fig. 4 is a slope check with seven horizon points and a theory curve normalized through the last point; re","section":"§7, Numerical Experiments"}],"minor_comments":[{"comment":"The Region II/III boundary is stated three different ways: §1.1 uses (T−N) ≥ K^{1/4}T^{3/4}/(log(T−N))^{1/2}; the Figure 3 caption uses (T−N) ≥ K^{1/4}N^{3/4}; the Appendix proof of Thm 3.1 uses (T−N) ≥ K^{1/4}N^{3/4}log(N)^{3/4}/log(T−N)^{1/2}. These agree up to logs when N~T, but since Table 1 and Figure 2 are the headline summary, please state one consistent boundary (with logs) and use it everywhere.","section":"§1.1 / Fig. 3 / App. A"},{"comment":"ε as defined in Thm 3.1 (first component 4√(K log(T−N)/N), third √(KT log T/(T−N)²)) differs in constants and log arguments from the per-region values quoted in the §3.2 bullets (e.g., ε=√(K log T/N) in Region I). Please reconcile, and note explicitly that Lemma 4.4 step (b) requires 2ε ≤ ∆_{g,j} ≤ 1, i.e., ε ≤ 1/2, with ε ≥ 1 handled separately as in the Region III discussion.","section":"Thm 3.1 and §3.2"},{"comment":"Thm 5.1 lower-bounds only experiment-phase regret (REG ≥ REG_exp), so the commitment-phase term (T−N)·max_{∆_{g,i}<2ε}∆_{g,i} in Prop. 4.1 has no matching instance-dependent lower bound, and arms in S_g\\S_f never appear. The minimax characterization is unaffected, but since Prop. 4.1 is advertised as a stronger result, a remark on whether the instance-dependent upper bound is tight (or where the slack lies) would help.","section":"Thm 5.1 / Prop. 4.1"},{"comment":"The permutation-symmetry requirement (REG_com invariant under arm permutations) restricts the policy class but does not appear to be used in the proofs of Thm 5.1 or 5.2 (the two-instance construction holds for all policies). If it is unused, please remove it or indicate where it is needed, since it weakens the stated lower bound.","section":"Definition 5.1"},{"comment":"Typos/formatting: reference list has 'Seebastian Bubeck' (should be Sébastian); 'defition' in App. C.1; stray period in §7.3 'g(o) = −20·(o−c)ᵀA(o−c). where the target vector'; spacing artifacts throughout ('priv acy-level', 'a platform-wide'). The standing assumption N ≥ cT^a is used before it is stated in §2; consider moving it into the model definition. Figure 4's caption should state the number of replications per point (1500) rather than only in the text.","section":"Global"}],"recommendation":"minor_revision","confidential_remarks":"Positioning relative to Bui et al. (2011) and Qin and Russo (2024) is clearly delineated in §1.2, and the EC'26 one-page abstract is disclosed. The two-phase exogenous-budget model with a reward shift appears genuinely distinct from the soft-commitment literature. The paper is long but the appendix proofs are readable. My only caution to the editor: the experimental section, while honest about its constant modifications, does not literally test the stated algorithms; if the journal weighs empirical validation heavily, the authors should be asked to either run unmodified RAEC or clearly qualify the claim in the abstract."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The load-bearing claim holds: with exogenous experiment budget N and a general post-commitment reward map, RAEC’s fixed reservation parameter ε delivers matching upper and lower bounds across the short-experiment, balanced, and short-commitment regimes—roughly Õ(√(KT²/N)), Õ(K^{1/3}(T−N)^{2/3}), and Õ(√(KT)). That is the real contribution. Predetermined effort for the commitment objective is already minimax-rate optimal; learning the instance to adapt the split does not improve the leading term.\n\nWhat is new relative to committing bandits and best-of-both-worlds work is the general (not just scaled) reward shift, the full regime map with matching lower bounds, the ranking-change structural corollary (D matters more than M), and ROSCOC’s clean trick of committing to the empirical distribution of the reserved OCO path. The proof architecture is standard and internally consistent: phased elimination + Azuma for the instance-dependent bound, then the usual group-splitting conversion to minimax; lower bounds via consistent-policy KL plus a two-instance Bretagnolle–Huber construction on a fixed Bernoulli coordinate subclass. Sanity checks (g≡0 recovers ordinary bandit rates; f≡0 recovers simple-regret rates) go through. The identifiability premise—outcomes scorable under both f and g, or paired independent signals—is stated explicitly with the matching impossibility remark; it is a modeling choice, not a hidden step.\n\nSoft spots are minor and proportional. Numerics use constant-scaled Stage-I pull counts (1/10–1/25, 0.3τ) and pin the theory curve to the last empirical point, so they corroborate slopes of a modified algorithm rather than RAEC as written—a corroboration gap, not a claim break. No code release. Finite-sample multipliers and hard-instance gap prefactors are free parameters, as usual. None of that touches the theory.\n\nThis is for people who care about adaptive experimentation under announced policy shifts, platform A/B with a hard rollout date, or the theory of explore-then-commit with reward change. It deserves a serious referee. I would engage with it and expect to cite the regime table.","headline":"Tight three-regime minimax for exogenous-N bandits with post-commitment reward shift; predetermined reservation is rate-optimal, and the proofs check out.","tokens_in":45151,"tokens_out":551,"would_cite":true,"duration_ms":11758,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Reserving a fixed share of an experiment to learn the post-shift best option is rate-optimal for short-term vs long-term regret.","keywords":["multi-armed bandits","adaptive experimentation","post-commitment reward shift","regret minimization","best-arm identification","explore-then-commit","concave bandits","portfolio commitment"],"falsifier":"Find any algorithm whose worst-case regret grows strictly slower than the three-regime rates in Table 1 (for example o(K^{1/3}(T−N)^{2/3}) in the balanced regime), or show that those rates fail on the hard Bernoulli constructions used for the lower bound when dual reward observation is available.","tokens_in":44677,"feed_emoji":"⚖️","tokens_out":959,"duration_ms":21865,"temperature":0.7,"pith_summary":"When a decision-maker can try many options for a fixed experiment window and must then lock in one option whose payoffs may change after a known shift, short-run winners need not be long-run winners. This paper shows that a simple rule—pre-reserve a fixed slice of the experiment to eliminate bad post-shift options, then use the rest to control ordinary short-run regret—matches the best possible regret rates in every regime of experiment length versus commitment length. Matching lower bounds prove that smarter, adaptive reallocation of that reserved effort cannot improve the leading rate. Structural knowledge helps only when it identifies ranking changes, not mere scale shifts; the same reserved-effort idea extends to concave portfolio commitment. The result gives a quantitative rule of thumb for how much short-term pain is necessary for long-term gain under an anticipated environment change.","feed_headline":"Fixed experiment reservation matches best possible regret","feed_subtitle":"When payoffs shift after a known commit date, pre-allocating exploration is rate-optimal across all regimes.","key_machinery":"RAEC (Reserved Arm Eliminations for Commitment): a phased elimination algorithm that spends a predetermined number of epochs eliminating arms under the post-commitment reward g, then uses remaining experiment rounds to eliminate under the short-run reward f, and finally commits uniformly at random among arms that survive the g-stage.","core_discovery":"Across all regimes of experiment budget N and horizon T, the RAEC algorithm with a predetermined reservation accuracy ε attains regret upper bounds that match the minimax lower bounds up to logs: on the order of √(KT²/N) when the experiment is short, K^{1/3}(T−N)^{2/3} in the balanced regime, and √(KT) when commitment is short. Predetermined reservation is therefore minimax rate-optimal; adaptive effort allocation based on the learned instance cannot improve the leading rate.","pith_inferences":["The same predetermined-reservation template may apply to other two-horizon problems with a known switch date, such as staged regulatory rollouts or capacity-constrained manufacturing transitions.","If the commitment date N is unknown in advance, the paper’s own open question suggests the rates may degrade unless a robust online estimate of remaining horizon is available.","Platforms running GDPR-style grace periods could treat the Lagrangian weight on long-run compliance as the effective (T−N)/N ratio and set the reservation parameter from the balanced-regime formula."],"forward_implications":["Practitioners can pre-commit a fixed exploration budget for the post-shift objective without losing asymptotic optimality.","When experiment time is scarce relative to commitment, nearly all of N should go to pure exploration of the post-shift best arm.","Knowing only a ranking-preserving scale factor between pre- and post-shift rewards restores near-standard bandit rates; ranking-changing noise does not.","For concave commitment payoffs, converting the reserved exploration path into an empirical portfolio (ROSCOC) matches the same leading rates as single-arm commitment.","The cost of an anticipated reward shift is intrinsic: regret is strictly larger than ordinary √(KT) over wide ranges of N."],"fun_headline_variants":["RAEC reservation hits minimax regret in every N-T regime","Fixed explore share matches lower bounds for post-commit reward shifts","Predetermined reserve is rate-optimal; instance-adaptive effort gains nothing","Short-run vs commit tradeoff: tight √(KT²/N) to K^{1/3}(T−N)^{2/3} rates","Reserve-then-commit RAEC matches best possible regret after payoff shifts"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"During the experiment the learner must observe outcomes that can be scored under both the pre-shift and post-shift reward maps; without that link, post-shift quality is unidentified and sublinear commitment regret is impossible in general.","fun_headline_variants_meta":{"raw":{"variants":["RAEC reservation hits minimax regret in every N-T regime","Fixed explore share matches lower bounds for post-commit reward shifts","Predetermined reserve is rate-optimal; instance-adaptive effort gains nothing","Short-run vs commit tradeoff: tight √(KT²/N) to K^{1/3}(T−N)^{2/3} rates","Reserve-then-commit RAEC matches best possible regret after payoff shifts"]},"model":"grok-4.5","effort":"low","cost_usd":0.002192,"raw_usage":{"total_tokens":967,"prompt_tokens":848,"num_sources_used":0,"completion_tokens":99,"cost_in_usd_ticks":21924000,"prompt_tokens_details":{"text_tokens":848,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":20,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":848,"tokens_out":99,"duration_ms":3018,"temperature":1.0,"reasoning_tokens":20,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T22:10:46.888662+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Find any algorithm whose worst-case regret grows strictly slower than the three-regime rates in Table 1 (for example o(K^{1/3}(T−N)^{2/3}) in the balanced regime), or show that those rates fail on the hard Bernoulli constructions used for the lower bound when dual reward observation is available.","supporting_citations":[],"review_version":1}