{"id":"081eec0f-a87d-4479-bb6d-7825516ce3e1","arxiv_id":"2608.01069","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper derives sharp asymptotic formulas for post-bandit sample-mean bias under UCB-type index algorithms, showing that for non-unique optimal arms the standardized bias decays only as 1/sqrt(log T) for UCB1.","lead":"This paper proves exact leading-order formulas for how much bandit algorithms like UCB1 bias the average rewards they collect for downstream statistical tests. It shows the bias shrinks very slowly, as one over the square root of log time, which matters for anyone using bandit-collected data for inference.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 15's optimal-arm tracking bound is internally inconsistent: the threshold d needed for o(T/f_T) cannot satisfy Lemma 14's lower bound, so Condition 3(5) for |O|>=2 is unproven.","rationale":"The reader identified Condition 3, especially equation (5), as the weakest load-bearing premise. I agree with that assessment, and I found a more specific internal problem within the paper's own verification of Condition 3 for UCB1 in the multiple-optimal-arms case. The proof of Lemma 15 claims that the complement of the event Upsilon directly yields the desired o(T/f_T) bound, but the only tail bound available (Lemma 14) requires a threshold d that is omega(T/f_T), making the claimed direct bound impossible. This is not merely a missing verification for a general abstract class: it affects the concrete UCB1 theorem when |O| >= 2, which is one of the headline results. The issue is a proof gap rather than a demonstrated falsehood; the bias formula for optimal arms with multiple optima may still be correct, and a simulation can indicate whether the underlying scaling is true. I did not choose the omitted sub-Gaussian assumption as the primary concern because it is a condition-statement mismatch that is straightforwardly repaired by adding sub-Gaussianity to Theorem 1; the Lemma 15 gap is a substantive obstacle in the proof of the main UCB1 result. The verdict remains CONDITIONAL: the paper's central claims are plausible and partially supported, but this specific step must be fixed or replaced before the multiple-optimal-arm results can be considered proven.","tokens_in":23731,"tokens_out":38389,"duration_ms":317099,"concrete_test":"Simulate UCB1 (rho = 2, Gaussian or Bernoulli rewards) with K = 2, mu_1 = mu_2 = 0, sigma_i^2 = 1, and no suboptimal arms, for T in {1e4, 1e5, 1e6}. At each T, compute the fluid solution n_{i,T} and the empirical fluid solution tilde n_{i,T} from (2)-(3), and estimate ||N_1(T) - tilde n_{1,T}||_p for a fixed p > 1 (e.g. p = 2) over at least 1000 seeds. Plot ||N_1 - tilde n_1||_p * f_T / T as a function of T. If this ratio does not converge to 0, Condition 3(5) fails for optimal arms and the multiple-optimal-arm bias formula is not supported. If it does converge to 0, the claim may still be true, but the written proof of Lemma 15 needs repair because its decomposition cannot deliver that rate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 15 aims to verify Condition 3(5), i.e. f_T ||(N_i - tilde n_i)/n_i||_p = o(1), for optimal arms i when m=|O|>=2. Since n_i ~ T, this requires ||N_i - tilde n_i||_p = o(T/f_T). The proof splits the Lp norm into the event Upsilon = {|N_i - tilde n_i| > d}, its complement, and the complement of U_g ∩ B_kappa ∩ W_eta^c. On Upsilon^c it asserts 'the desired bound |N_i - tilde n_i| = o(T/f_T) holds directly,' which is only true if d = o(T/f_T). However, the tail bound applied on Upsilon (Lemma 14, used with g = T/sqrt(f_T) per the proof) is conditioned on d >= sqrt(n_i) g/f_T + T/(2 f_T^2). With n_i ~ T this lower bound is T^{3/2}/f_T^{3/2} + T/(2 f_T^2) = omega(T/f_T). No d can be simultaneously o(T/f_T) and satisfy that lower bound. Consequently the residual term (10) in Lemma 4 is not controlled for optimal arms in the multiple-optima case, and Theorem 2's |O|>=2 statement (and Theorem 1 as applied to optimal arms) lacks a demonstrated verification of the key stability condition.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the bias of post-bandit sample means and Z-statistics under index-based bandit algorithms. It introduces the effective exploration rate Γ and a two-stage (fluid and empirical-fluid) approximation of pull counts. The main theorem states that under Conditions 1–3, Γ_{a,T}/√n_{a,T} E[\\bar X_a(N_a(T))−μ_a] → −2(1 − 1_{a∈O}/|O|)σ_a² and Γ_{a,T}E[Z_{a,T}] → −(1 − 1_{a∈O}/|O|)σ_a. For generalized UCB, Γ=f_T, so for UCB1 the standardized bias of every non-unique-optimal arm decays as 1/√log T. The paper also derives a regret-bias trade-off from these rates.","tokens_in":24125,"tokens_out":14697,"duration_ms":132666,"significance":"If the proof of the UCB verification were complete, this would be a substantial contribution: it gives the first sharp leading-order bias formula for a canonical stable algorithm, identifies an interpretable algorithm-dependent quantity (effective exploration rate), and makes a concrete falsifiable prediction (1/√log T bias decay for UCB1). The empirical fluid approximation is a promising technique. The paper is also honest in presenting Condition 3 as a verification condition rather than as a derived property. However, the current manuscript does not fully support the multiple-optima case, and the conditional nature of Theorem 1 limits the generality of the 'stable index algorithms' claim to families for which Condition 3 can actually be verified.","major_comments":[{"comment":"The verification of Condition 3(5) for optimal arms when |O|≥2 is not established. In Lemma 15 the L_p norm of N_i(T)−\\tilde n_{i,T} is split using the event Υ_i^c, and on Υ_i^c the proof asserts that the desired bound |N_i(T)−\\tilde n_{i,T}|=o(T/f_T) holds directly. This is true only if the threshold d defining Υ_i satisfies d=o(T/f_T). But Lemma 14, as invoked in the same proof with g=T/√f_T, is stated only for d ≥ √n_{i,T}g/f_T + T/(2f_T²). Since n_{i,T}≍T for i∈O and f_T=√(ρ log T) for UCB1, this lower bound is ≍ T^{3/2}/f_T^{3/2} + T/(2f_T²), which is ω(T/f_T) and in fact ω(T) for large T. Thus no threshold can simultaneously be o(T/f_T) and satisfy Lemma 14's hypothesis; the 'middle range' of deviations, where T/f_T < |N_i(T)−\\tilde n_{i,T}| ≪ T^{3/2}/f_T^{3/2}, is not controlled by any argument in the manuscript. Consequently Condition 3(5) is not demonstrated for optimal arms in the multiple-optima case, and the proofs of Theorem 2 for |O|≥2 and of Theorem 1 as applied to optimal arms with |O|≥2 are incomplete as written.","section":"Appendix C.1, Lemma 15 (with Lemma 14)"}],"minor_comments":[{"comment":"The proof of Lemma 1 is omitted. Since the fluid and empirical-fluid approximations are the foundation of the main theorem, the authors should supply the existence/uniqueness argument or a precise reference.","section":"Section 3.1, Lemma 1"},{"comment":"In the proof of Lemma 2, the function is written as Γ_q(k) in one place but defined as Λ_q(k) in the lemma statement; please correct the notation.","section":"Proof of Lemma 2"},{"comment":"The statement of Lemma 14 is typeset ambiguously: the conditions on d and g run together with the event {|N_i(T)−\\tilde n_{i,T}|>d}. Please reformat so that the quantifiers and constraints are unambiguous.","section":"Appendix C.1, Lemma 14 statement"},{"comment":"The sharper bound for the Z-statistic of the unique optimal arm is stated without proof ('the proof for the Z-statistic bias is similar and we omit'). Since this is a claimed sharper result, the argument should be included or at least sketched.","section":"Proof of Theorem 2, |O|=1 case"},{"comment":"The in-text citation '(Halder et al., Sengupta et al. (2026))' is malformed and does not match the reference list; please fix it.","section":"Section 1.2, related work"}],"recommendation":"major_revision","confidential_remarks":"The multiple-optima verification gap in Lemma 15 is localized but load-bearing: it affects the central UCB claim for all optimal arms when |O|≥2, not a peripheral result. I recommend major revision rather than rejection because the conditional theorem and the single-optimum/suboptimal-arm parts appear sound, and the gap may be repairable with a sharper tracking argument. The authors should either provide a correct verification of Condition 3(5) for optimal arms under UCB1/Poly-UCB or explicitly restrict the statements and abstract accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the main idea is good: an empirical fluid approximation that tracks pull counts of index algorithms, used to derive the leading-order bias of post-bandit sample means and Z-statistics. Second, the proof of the paper's headline multiple-optima result does not hold up as written. The stress-test note is correct: Lemma 15's verification of Condition 3(5) for optimal arms when |O|>=2 is internally inconsistent. To make the Lp norm on the good event negligible you need d = o(T/f_T), but the tail bound from Lemma 14, applied with g = T/sqrt(f_T), requires d >= sqrt(n_i,T) g/f_T + T/(2 f_T^2), which is omega(T/f_T). No choice of d works, so the proof of Lemma 15 does not verify the key stability condition for the multiple-optima case, and Theorem 2's |O|>=2 statement is unproven.\n\nWhat the paper does well: the empirical fluid approximation is a real addition, and the sharp 1/sqrt(log T) rate for UCB1 is new if it holds. The regret-bias trade-off (Corollary 1) is a clean observation. The UCB1 verification for suboptimal arms (Lemma 12) is substantial and may survive. The general theorem is honest about being conditional on Condition 3, and the prior literature is cited accurately.\n\nBeyond the stress-test: Lemma 1's proof is omitted, which is annoying but minor. Condition 3 as stated omits the sub-Gaussian assumption used throughout the proofs; that is a real gap between assumptions and proofs. The Poly-UCB section is a sketch. But the central problem is the multiple-optima case, where the authors emphasize the qualitative distinction, and that case is not established.\n\nThis paper is for anyone working on inference after adaptive experiments, especially practitioners who want to know how much bias UCB leaves. It deserves a serious referee because the core idea is valuable and the flaw may be repairable. My recommendation would be major revision: ask for a correct verification of Condition 3 for optimal arms, or a revised theorem that only claims the suboptimal-arm result.","headline":"Sharp new bias formula with a nice fluid tool, but the multiple-optima proof has a gap that needs fixing before the headline claim is credible.","tokens_in":24562,"tokens_out":5385,"would_cite":false,"duration_ms":43137,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","62L12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stable index bandit algorithms such as UCB1 carry a precisely quantified bias in post-hoc sample means: for every arm that is not uniquely optimal, the standardized bias decays at the slow rate $1/\\sqrt{\\log T}$, with the constant set by…","keywords":["post-bandit inference","adaptive sampling bias","multi-armed bandits","UCB1","index algorithms","effective exploration rate","empirical fluid approximation","regret-bias trade-off"],"falsifier":"Simulate a three-arm bandit with two optimal arms (mean 0) and one suboptimal arm, all with variance $\\sigma^2=1$, under UCB1 at $T=10^6$; the paper predicts $f_T\\,\\mathbb{E}[Z_{a,T}]\\to -1/2$ for each optimal arm and $-1$ for the suboptimal arm, and $\\frac{f_T}{\\sqrt{n_{a,T}}}\\mathbb{E}[\\bar X_a(N_a(T))-\\mu_a]\\to-1$ for the suboptimal arm. If the products converge instead to zero, or to constants that depend on the exploration constant $\\rho$, the leading-order covariance claim in Lemma 3 is wrong; equivalently, verifying that $\\mathbb{E}[Z_{a,T}]\\sqrt{\\mathrm{Reg}_T}$ takes the same constant under $f_t=\\sqrt{2\\log t}$ and $f_t=t^{1/4}$ would confirm the regret-bias trade-off.","tokens_in":23546,"feed_emoji":"🎰","tokens_out":10678,"duration_ms":81083,"temperature":0.7,"pith_summary":"Adaptive sampling by bandit algorithms systematically shifts sample means away from the truth, and this paper tries to prove that the shift has a sharp leading-order formula rather than just a generic bound. The claim is that for stable index algorithms such as UCB1, the standardized bias of any arm that is not the uniquely optimal one is asymptotically $-1/\\Gamma_{a,T}$ times the arm's standard deviation, where $\\Gamma_{a,T}$ is the index function's effective exploration rate. Specializing to UCB1 gives $\\Gamma_{a,T}=f_T\\asymp\\sqrt{\\log T}$, so the bias decays at the slow rate $1/\\sqrt{\\log T}$; the paper also shows the unique optimal arm's bias is polynomially smaller. A reader should care because the rate is slow enough that naive confidence intervals and tests built from bandit-collected data stay distorted even at large horizons, and because the same formula forces a regret-bias trade-off: more exploration reduces bias but increases regret.","feed_headline":"Adaptive sampling bias under UCB1 decays at only 1/sqrt(log T)","feed_subtitle":"Low-regret exploration and unbiased downstream inference pull in opposite directions.","key_machinery":"The load-bearing object is the effective exploration rate $$\\Gamma_t(x,n):=-2\\,$n^{{3/2}}$\\,\\frac{\\partial_n I_t(x,n)}{\\partial_x I_t(x,n)},$$ which the paper interprets as how many additional pulls of an arm offset a one-standard-error perturbation of its sample mean while keeping the index unchanged; large $\\Gamma$ means the algorithm barely reacts to noise, hence less bias. The second engine is the empirical fluid approximation $\\tilde n_t$, defined by solving the index-equalization equations with the population means replaced by sample means evaluated at the deterministic fluid counts $n_t$; unlike the deterministic fluid $n_t$, it retains the coupling between pull counts and reward fluctuations, and Lemma 3 shows that the covariance $(\\tilde n_{a,T}-n_{a,T})(\\bar X_a(n_{a,T})-\\mu_a)$ supplies exactly the leading term of the bias. Around the two approximations, the proof uses the covariance identity of Lemma 2, $\\mathbb{E}[\\bar X_a(N_{a,T})-\\mu_a]=-q^{-1}\\mathbb{E}[(N_{a,T}-q)(\\bar X_a(N_{a,T})-\\mu_a)]$ for any deterministic $q$, and Lemma 4's residual bounds to kill everything not of leading order.","core_discovery":"The paper's central result, Theorem 1, states that under its regularity and stability conditions, for every arm $a$, the standardized sample-mean bias and the expected $Z$-statistic obey $$\\frac{\\Gamma_{a,T}}{\\sqrt{n_{a,T}}}\\,\\mathbb{E}\\big[\\bar X_a(N_a(T))-\\mu_a\\big]\\;\\to\\;-2\\left(1-\\frac{\\mathbf 1_{a\\in O}}{|O|}\\right)\\$sigma_a^{2}$,\\qquad \\Gamma_{a,T}\\,\\mathbb{E}[Z_{a,T}]\\;\\to\\;-\\left(1-\\frac{\\mathbf 1_{a\\in O}}{|O|}\\right)\\sigma_a,$$ where $O$ is the set of optimal arms and $\\Gamma_{a,T}$ is the effective exploration rate of the index function. For generalized UCB indices $I_t(x,n)=x+f_t/\\sqrt n$, $\\Gamma_{a,T}=f_T$, so the expected $Z$-statistic of every arm that is not the unique optimal arm is of order $-1/f_T$; with $f_T=\\sqrt{\\rho\\log T}$ this is the slow $1/\\sqrt{\\log T}$ decay, while the unique optimal arm's bias is only $O(f_T/T)$ or smaller. The negative sign reproduces the known downward bias of adaptively collected means, and the prefactor $(1-\\mathbf 1_{a\\in O}/|O|)$ is zero for the unique optimal arm, full for every suboptimal arm, and intermediate when several arms tie for the top, reflecting the extra selection bias caused by the algorithm oscillating among indistinguishable optimal arms.","pith_inferences":["(Editorial inference) The prefactor $(1-\\mathbf 1_{a\\in O}/|O|)$ predicts a numerically testable symmetry: simulating an $m$-arm bandit with all arms tied at the same mean should reproduce the factor $1-1/m$ on every arm, and the same simulation could check whether one arm's bias in a tie equals the bias it would carry as the unique suboptimal arm in a two-arm problem.","(Editorial inference) Because $\\Gamma$ is a local derivative of the index function, the same definition could assign an effective exploration rate to non-index policies by measuring how many pulls a one-standard-error reward shift displaces; if the logic carries, Thompson sampling and $\\epsilon$-greedy would get concrete bias orders instead of only stability-or-instability labels.","(Editorial inference) The formula suggests a plug-in debiasing recipe, subtracting $(1-\\mathbf 1_{a\\in O}/|O|)\\sigma_a/f_T$ from the $Z$-statistic with estimated $\\sigma_a$, whose residual error should be $o(1/f_T)$; a finite-sample experiment comparing coverage before and after this correction would test both the leading constant and the rate."],"forward_implications":["Under UCB1, the standardized bias of any arm that is not the unique optimal arm decays only as $1/\\sqrt{\\log T}$, so at any realistic horizon the distortion remains comparable to the standard error and shifts naive hypothesis tests built from bandit-collected data.","Bias and regret obey a fixed trade-off: within the generalized UCB family, $\\mathbb{E}[Z_{a,T}]\\cdot\\sqrt{\\mathrm{Reg}_T}\\to\\kappa_a$ with $\\kappa_a$ independent of the algorithm, so an algorithm cannot reduce its bias without paying more regret, and vice versa.","The unique optimal arm is qualitatively different: its expected $Z$-statistic bias is $O(f_T/T)$, polynomially small, whereas any arm sharing the top with another optimal arm carries the full $-1/f_T$ bias because the algorithm's oscillation among optimal arms amplifies selection bias.","For arms with the same mean, the higher-variance arm gets the larger bias and more distorted $Z$-statistic, since the formula's strength is proportional to $\\sigma_a$ (and $\\sigma_a^2$ for the sample mean), a concrete prediction of Theorem 2."],"supporting_citations":[{"why":"Documents that arm-specific sample means from adaptive experiments are systematically biased downward, the phenomenon this paper sharpens into a leading-order formula.","marker":"Nie et al. (2018)"},{"why":"Introduces UCB1, the canonical index algorithm whose $f_t=\\sqrt{2\\log t}$ exploration produces the paper's headline $1/\\sqrt{\\log T}$ bias rate.","marker":"Auer et al. (2002)"},{"why":"Gives the asymptotic lower bound forcing suboptimal arms' pull counts to grow, which Condition 2 mirrors in the fluid scaling.","marker":"Lai and Robbins (1985)"},{"why":"Provides the stability condition $(N_a(T)-n_{a,T})/n_{a,T}\\to 0$ in $L^p$ that Condition 3 strengthens with faster concentration around the empirical fluid counts.","marker":"Praharaj and Khamaru (2025)"},{"why":"Supplies the precise regret and adaptive-inference analysis of UCB that the sharp bias characterization builds on as its benchmark.","marker":"Han et al. (2024)"},{"why":"The prior sharp inference study for the UCB algorithm that this paper's leading-order bias formula refines.","marker":"Khamaru and Zhang (2024)"},{"why":"The standard reference fixing the definition of regret used in the regret-bias trade-off corollary.","marker":"Lattimore and Szepesvári (2020)"}],"fun_headline_variants":["UCB1 bias: 1/sqrt(log T) for suboptimal arms","Suboptimal arm bias under UCB1: 1/sqrt(log T)","Bias under UCB1: 1/sqrt(log T) unless arm is unique best","Effective exploration rate sets bias: 1/sqrt(log T) for UCB1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The headline formula rests on Condition 3's concentration-rate assumptions, that the scaled gap $\\Gamma_{a,T}(N_a(T)-\\tilde n_{a,T})/n_{a,T}$ tends to zero in $L^p$ and that the sample mean evaluated at the random stop is within $o(1/\\sqrt{n_{a,T}})$ of its fluid-time value, which the paper verifies for UCB1 and Poly-UCB but simply posits for the general index-algorithm statement of Theorem 1; the paper also states without proof (Lemma 1) that the fluid and empirical-fluid allocations exist and are unique.","fun_headline_variants_meta":{"raw":{"variants":["UCB1 bias: 1/sqrt(log T) for suboptimal arms","Suboptimal arm bias under UCB1: 1/sqrt(log T)","Bias under UCB1: 1/sqrt(log T) unless arm is unique best","Effective exploration rate sets bias: 1/sqrt(log T) for UCB1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001578,"raw_usage":{"total_tokens":6344,"prompt_tokens":1038,"completion_tokens":5306,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":5216}},"tokens_in":654,"tokens_out":5306,"duration_ms":35095,"temperature":1.0,"reasoning_tokens":5216,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:13:49.472075+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate a three-arm bandit with two optimal arms (mean 0) and one suboptimal arm, all with variance $\\sigma^2=1$, under UCB1 at $T=10^6$; the paper predicts $f_T\\,\\mathbb{E}[Z_{a,T}]\\to -1/2$ for each optimal arm and $-1$ for the suboptimal arm, and $\\frac{f_T}{\\sqrt{n_{a,T}}}\\mathbb{E}[\\bar X_a(N_a(T))-\\mu_a]\\to-1$ for the suboptimal arm. If the products converge instead to zero, or to constants that depend on the exploration constant $\\rho$, the leading-order covariance claim in Lemma 3 is wrong; equivalently, verifying that $\\mathbb{E}[Z_{a,T}]\\sqrt{\\mathrm{Reg}_T}$ takes the same constant under $f_t=\\sqrt{2\\log t}$ and $f_t=t^{1/4}$ would confirm the regret-bias trade-off.","supporting_citations":[],"review_version":1}