{"id":"56f43c80-11fe-4abf-8831-8ecaa08a2633","arxiv_id":"2412.02251","paper_version":3,"verdict":"UNVERDICTED","confidence":"HIGH","novelty_score":1.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A statistical survey of multi-armed, contextual, and continuum-armed bandits that restates known minimax and regret results, adds an alternative UCB proof, and reports small simulation comparisons.","lead":"This paper is a review of stochastic bandit algorithms, presented from a statistics perspective. It restates known regret bounds using concentration inequalities and compares UCB, Thompson sampling, and related methods in simulations.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The alternative proof of Theorem 5 in Appendix B uses an unjustified bad-event bound, so the paper's strongest concrete UCB regret claim is not established as written.","rationale":"The reader's verdict is UNVERDICTED because this is a review article, not a new-research preprint, and the reader identifies the known-variance-proxy assumption as the weakest assumption. My stress-test found a different, more concrete weakness: the alternative proof of the paper's strongest concrete claim, Theorem 5, contains an invalid bad-event bound. The known-proxy issue is explicitly acknowledged by the paper in Section 6.4 and is standard in the bandit literature; it does not undermine the survey's internal consistency. The Appendix B proof gap, by contrast, is internal: it claims to derive the regret bound via the statistical-learning decomposition but mishandles the optimism term on the bad event. This does not change the review-level classification, since the theorem is cited from a standard reference and the survey's pedagogical contribution does not hinge on the novel proof being fully rigorous. If the paper were assessed as a research contribution, this flaw would make the proof conditional on a fix; as a review, UNVERDICTED remains appropriate. The concrete test would settle whether the proof can be repaired with a standard time-uniform concentration argument.","tokens_in":46593,"tokens_out":14671,"duration_ms":153744,"concrete_test":"Reproduce the proof of Appendix B for a two-armed Gaussian bandit with μ1 = μ2 = 0, δ = 1/T^2, and rewards N(0,1). Compute analytically or by Monte Carlo (T = 10^4, 10^5) the quantity E[1_{G^c} Σ_{t=1}^T (μ* − UCB_*(t−1,δ))]. If this quantity grows like √(log T) while 4|μ*|T^2 K δ = 0, the displayed bad-event bound is false. Then check whether replacing the union bound over T events with a union bound over pull counts (e.g., weights 1/s^2) yields the claimed O(K + √(KT log T)) regret; if yes, the flaw is confined to the proof's presentation, not the theorem's truth.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's strongest concrete claim is the UCB regret bound of Theorem 5, with the alternative proof in Appendix B advertised as the main pedagogical support. That proof has a serious gap. Lemma 7 gives Reg_T ≤ E[Σ (μ* − UCB_*(t−1,δ) + UCB_{A_t}(t−1,δ) − μ_{A_t})]. The proof then drops the term μ* − UCB_* unconditionally, although it is non-positive only on the good event G (equation A3). On the bad event G^c, whose probability is at most 2TKδ = 2K/T when δ = 1/T^2, the contribution E[1_{G^c} Σ (μ* − UCB_*)] is not bounded by 2|μ*| T P(G^c) as the displayed inequality claims. For Gaussian rewards with μ* = 0, the conditional excess of −μ̂* given a threshold violation at s = 1 is of order √(2 log(1/δ)) = 2√(log T), and this event persists over many rounds, so the bad-event contribution is Θ(√(log T)), not O(1) or O(2|μ*|T P(G^c)). Thus the final bound 4|μ*|K + 12√(log T)√(KT) does not follow from the written argument. The theorem itself is standard (Theorem 7.2 of Lattimore–Szepesvári), so the survey's overall classification is not overturned, but the 'alternative proof' does not deliver the advertised support. A correct proof would require a time-uniform confidence sequence or a union bound over pull counts with decaying weights to make the bad-event contribution negligible.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript is a survey of stochastic bandit problems (finite-armed, contextual, and continuum-armed) viewed through the lens of non-asymptotic statistics. It introduces concentration inequalities for sub-Gaussian and sub-exponential rewards, reviews ETC, UCB, MOSS, Thompson sampling, MOTS, LinUCB, LinTS, GP-UCB, and GP-TS, and discusses connections to functional data analysis and recent topics such as unknown variance proxies. A central feature is an 'alternative proof' of the UCB regret bound based on an excess-risk decomposition from statistical learning theory, presented in Appendix B.","tokens_in":46994,"tokens_out":16793,"duration_ms":157259,"significance":"If correct, the survey would provide a compact bridge between bandit theory and statistical learning theory, with a coherent narrative that many bandit guarantees reduce to concentration inequalities and risk decompositions. The paper is strongest as a compilation: it gathers standard algorithms and bounds, attributes them clearly, and includes simulations that illustrate qualitative differences among algorithms. It also honestly acknowledges the known-variance-proxy limitation in Section 6.4. However, the advertised alternative UCB proof in Appendix B contains a load-bearing gap, and the sub-exponential example in Section 2.2 contains a false inequality. These issues prevent the present version from fully delivering its methodological message, although the standard results quoted are mostly correct.","major_comments":[{"comment":"The alternative proof of Theorem 5 drops the term μ* − UCB*(t−1,δ) from Lemma 7 unconditionally. This term is non-positive only on the good event G; on G^c it can be positive and of order sqrt(2 log(1/δ)) even when μ* = 0, and it can persist over many rounds. The displayed bound E{1_{G^c} Σ (UCB_{A_t} − μ_{A_t})} ≤ 2|μ*| T P(G^c) is also invalid, since UCB_{A_t} − μ_{A_t} is not bounded by 2|μ*| on G^c. The martingale-difference term in the preceding display is not handled correctly either: the expectation of an adaptively weighted sum is not bounded by max_t E[Y_{A_t}(τ) − μ_{A_t}]. As a result, the claimed regret bound 4|μ*|K + 12 sqrt(log T) sqrt(KT) does not follow from the written argument. Since this proof is advertised in Section 3.2 as the main pedagogical support for the UCB analysis, it needs to be repaired or replaced; the theorem itself is standard and Appendix A provides a valid proof.","section":"Appendix B, Eqs. (A3)–(A4)"}],"minor_comments":[{"comment":"Example 9 asserts e^{-sμ}(1−sμ)^{-1} ≤ e^{s^2 μ^2/2} for |s| ≤ (2μ)^{-1}, but this is false: at s = 0.4/μ the left-hand side is approximately 1.117 and the right-hand side approximately 1.083. The centered exponential is indeed sub-exponential, but the displayed inequality and the implied parameterization (μ, 2μ) should be corrected.","section":"Section 2.2, Example 9"},{"comment":"In the display after Eq. (A3), the quantity S_{k*} should be S_{A_t}: the confidence radius for the selected arm A_t depends on the number of pulls of that arm, not on the number of pulls of the optimal arm.","section":"Appendix B"},{"comment":"Theorems 5 and 7 assume a known variance proxy (usually 1), while Section 6.4 discusses the unknown-proxy problem only later; adding a forward reference in Section 3.2 would make the scope of the main bounds clearer to readers.","section":"Sections 3.2 and 6.4"},{"comment":"The phrase '∑_{i=1}^n X_{ij} i.i.d.∼ N(0, nσ^2)' should read '∑_{i=1}^n X_{ij} ∼ N(0, nσ^2)', since the sum is a single random variable rather than an i.i.d. collection.","section":"Section 2.1, Example 4"},{"comment":"There are minor typos, e.g., 'genalization' in Section 6.1 should be 'generalization', and the caption of Figure 5 has 'Culumative' instead of 'Cumulative'.","section":"Various"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to be a preprint with a journal-style header, possibly intended for a survey journal. The main concern is the Appendix B proof, which should be corrected or explicitly marked as a heuristic; the standard Appendix A proof of Theorem 5 is sound. The self-citations are used as related work and do not raise concerns. The paper's broad scope and statistical organizing principle are potentially valuable, but the current technical gaps should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a survey, and its only original piece — the alternative UCB proof in Appendix B — has a real gap. The rest of the survey is a reasonably competent, if selective, tour of bandits through a statistical lens. It could be useful to statisticians entering the area, but the advertised proof doesn't deliver.\n\nWhat's new: the paper is explicitly a review. Its original contribution is the excess-risk decomposition for UCB regret (Lemma 7 and Appendix B), plus a discussion of parallels between SCAB and functional data analysis (Section 5.5). The FDA connection is a nice observation, and the survey's selection of recent statistics literature — JASA, AoS, JRSS-B papers on contextual bandits, unknown variance proxies, and causal bandits — is genuinely useful. The organization around concentration inequalities, non-asymptotic CIs, and minimax rates is coherent.\n\nWhere it's soft: The alternative proof. Lemma 7 gives a regret bound involving μ*−UCB_*(t−1). That term is non-positive only on the good event G. On G^c, the proof drops it and bounds the rest by 2|μ*| T P(G^c), but the missing term is not negligible. For Gaussian rewards with μ*=0, the conditional excess given a threshold violation is ~√(log T), and it persists over many rounds, so the bad-event contribution is Θ(√(log T)), not O(1). The displayed final bound doesn't follow from the written argument. There's also a typo: in (A4), S_{k*} should be S_{A_t}. These are fixable, but they need to be fixed.\n\nOther soft spots are minor: Example 9 claims e^{-sμ}(1−sμ)^{-1} ≤ e^{s^2 μ^2/2} for |s|≤(2μ)^{-1}, which fails at s=0.4/μ; and the simulations are illustrative only — no error bars, and MOTS is run with α=1.5 despite Theorem 9 requiring α≥4, which the authors admit.\n\nWho it's for: statisticians who want a compact overview of bandit algorithms with a focus on concentration and non-asymptotic inference, and who are prepared to look up the original results. The survey is not a research contribution, but it's not a hack job either. With a corrected proof, it would be a useful tutorial. As it stands, the broken proof undermines the paper's main pedagogical claim.\n\nRecommendation: I'd send this to peer review rather than desk-reject — it's a serious survey with a real, fixable flaw. The referee should demand a repaired Appendix B and a corrected Example 9 before acceptance. I wouldn't cite it in its current form.","headline":"A useful but flawed survey: the alternative UCB proof in Appendix B has a load-bearing gap, so the paper's one original contribution is not established as written.","tokens_in":47531,"tokens_out":4138,"would_cite":false,"duration_ms":39982,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68T05","62E17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that stochastic bandit theory is best read as non-asymptotic statistical inference, where concentration inequalities yield the confidence intervals, regret decompositions, and minimax benchmarks that organize multi-armed…","keywords":["stochastic multi-armed bandits","continuum-armed bandits","sub-Gaussian concentration inequalities","regret bounds","minimax rates","contextual bandits","exploration-exploitation trade-off","functional data analysis"],"falsifier":"Fix a K-armed bandit with near-equal means (small gaps $\\Delta_k$) and rewards drawn from a mixture such as $0.4\\,N(0,1) + 0.6\\,N(0,9)$, so the true sub-Gaussian proxy exceeds 1; run Algorithm 3 with proxy 1 for $T=10^4$ and compare the observed cumulative regret to $3\\sum_k \\Delta_k + 8\\sqrt{TK\\log T}$, since a violation at the claimed confidence level would show that the known-proxy assumption is carrying the central theorem.","tokens_in":1891,"feed_emoji":"🎰","tokens_out":3058,"duration_ms":97755,"temperature":0.7,"pith_summary":"The authors are trying to establish that the theory of stochastic bandits is essentially non-asymptotic statistics: the same toolbox of concentration inequalities, confidence intervals, regret decompositions, and minimax lower bounds explains the guarantees of UCB, MOSS, posterior sampling, and continuum-armed bandits. They make the point by re-deriving the UCB regret bound through an excess-risk-style decomposition rather than the standard proof, and by presenting the sequential decision problem as one of estimating unknown reward distributions under adaptive sampling. A sympathetic reader would take away that bandit guarantees are consequences of tail bounds applied to adaptively collected samples, and that minimax rates separate what is algorithm-specific from what is inherent in the problem. The review itself flags the main caveat: most bounds assume the reward noise is sub-Gaussian with a known variance proxy, usually set to one.","feed_headline":"Bandit regret reduces to concentration inequalities","feed_subtitle":"UCB, MOSS, and continuum-bandit guarantees come from one non-asymptotic statistical toolbox.","key_machinery":"The object that carries the argument is the regret-decomposition identity for optimistic algorithms: for UCB, $\\mathrm{Reg}_T(\\pi, v) \\le \\mathbb{E}\\sum_{t=1}^T [\\mu^* - \\mathrm{UCB}_*(t-1,\\delta) + \\mathrm{UCB}_{A_t}(t-1,\\delta) - \\mu_{A_t}]$, where the selected arm maximizes the index so the optimal arm's index term contributes a negative concentration error. This reduces regret to the sum of concentration errors of the chosen and optimal arms; feeding in a sub-Gaussian tail bound plus a union bound yields the $O(K + \\sqrt{KT\\log T})$ rate. The companion structural objects are the minimax lower bound constructed from Gaussian instances, which fixes the $\\sqrt{KT}$ benchmark, and the information gain $\\gamma_T$, which quantifies the effective dimensionality a GP-UCB learner must explore over a continuous action space.","core_discovery":"On the paper's own terms, the central discovery is that the many bandit settings share a single statistical skeleton: every algorithm's exploration is a confidence interval, every regret bound is a concentration calculation, and optimality is judged by minimax rate. The review demonstrates this by reproving the UCB regret theorem—for subG(1) rewards with $\\delta = 1/T^2$, $\\mathrm{Reg}_T(\\pi, v) \\le 3\\sum_k \\Delta_k + 8\\sqrt{TK\\log T}$, with an alternative proof giving $\\mathrm{Reg}_T \\le 4|\\mu^*|K + 12\\sqrt{\\log T}\\sqrt{KT}$—through a regret decomposition that mirrors excess risk in statistical learning. It then applies the same reading to linear contextual bandits, where LinUCB and linear Thompson sampling attain $\\widetilde{O}(d\\sqrt{T})$ regret independent of the number of arms, and to continuum-armed bandits, where the GP-UCB regret is controlled by the maximum information gain $\\gamma_T$. The review also connects continuum-armed bandits to functional data analysis, treating the unknown reward as a function to be estimated over a continuous domain.","pith_inferences":["Read as a template, the regret-decomposition lemma likely extends to optimistic algorithms beyond UCB: LinUCB and GP-UCB can be viewed as the same concentration-error-plus-estimation-error split with different confidence radii, though the review does not state this unification explicitly.","The advertised connection between continuum-armed bandits and functional data analysis suggests transfers the authors leave implicit, such as using functional principal components or basis smoothing inside a continuum bandit when the reward function has low-rank structure, which could reduce the effective action dimension.","The simulations in the unknown-variance-proxy section hint at a practical rule the paper does not state: when the variance proxy is unknown, estimating the sub-Gaussian norm online and plugging it into the confidence radius can outperform both asymptotic variance estimators and wrongly applied bounded-reward concentration bounds; this could be tested systematically across reward families.","If the statistical reading is correct, then designing a new bandit algorithm reduces to finding the tightest valid concentration inequality for the reward family, meaning any new tail bound would directly yield a new UCB-style algorithm with a corresponding regret bound."],"forward_implications":["UCB with subG(1) rewards has problem-independent regret $O(\\sqrt{TK\\log T})$, and the gap to the $\\sqrt{KT}$ minimax lower bound is closed by MOSS and the minimax-optimal Thompson-sampling variant MOTS.","Contextual linear bandits, both LinUCB and linear Thompson sampling, achieve regret $\\widetilde{O}(d\\sqrt{T})$ independent of the number of arms, so shared features pay off whenever the feature dimension is manageable.","For continuum-armed bandits with a Gaussian-process prior, the cumulative regret is bounded by $\\sqrt{C_1 T \\beta_T \\gamma_T}$, where $\\gamma_T$ is the maximum information gain, which gives sublinear regret for common kernels.","The causal treatment-effect problem can be modeled as a two-armed bandit, yielding non-asymptotic confidence intervals for the treatment effect when the potential outcomes are sub-Gaussian.","The doubling trick converts the horizon-dependent algorithms described in the review into anytime algorithms without changing their regret rates."],"supporting_citations":[{"why":"Supplies the framework of regret and environment classes, Theorem 5's UCB bound with its standard proof, and the minimax lower bound that the review recasts.","marker":"[21]"},{"why":"Provides Hoeffding's inequality, the prototype bounded-variable tail bound whose sub-Gaussian analogue drives the paper's confidence intervals.","marker":"[45]"},{"why":"Supplies the sub-Gaussian and sub-exponential concentration results and moment characterizations used throughout Section 2 and the later regret proofs.","marker":"[47]"},{"why":"Introduces MOSS, the minimax optimal strategy that closes the gap between UCB's logarithmic factor and the $\\sqrt{KT}$ lower bound.","marker":"[70]"},{"why":"Supplies MOTS and Theorem 9, the minimax-optimal Thompson-sampling variant based on truncation.","marker":"[73]"},{"why":"Introduces the LinUCB algorithm with disjoint linear models used for K-armed contextual bandits.","marker":"[74]"},{"why":"Supplies Theorem 11, the linear Thompson-sampling regret bound for contextual bandits.","marker":"[77]"},{"why":"Provides Lemmas 8 and 9 and Theorem 10, giving the confidence-set analysis and $\\widetilde{O}(d\\sqrt{T})$ regret bound for the general LinUCB algorithm.","marker":"[75]"},{"why":"Introduces GP-UCB and the information-gain regret bounds for continuum-armed bandits, stated as Theorems 12 and 13.","marker":"[81]"},{"why":"Supports Section 6.4 on estimating the sub-Gaussian variance proxy when it is unknown.","marker":"[34]"}],"fun_headline_variants":["Bandit regret is just concentration math","Every bandit algorithm is a confidence interval","From UCB to GP-UCB: one statistical proof","Regret bounds via one non-asymptotic toolbox","Bandits and functional data share a skeleton"],"cache_read_input_tokens":49536,"weakest_assumption_plain":"The main theorems assume the reward noise has a known sub-Gaussian variance proxy, normally set to 1, together with a known horizon $T$ and confidence level $\\delta$; if that proxy is unknown, misspecified, or the noise is heavy-tailed, the concentration bound in display (19) and Theorem 5 do not hold.","fun_headline_variants_meta":{"raw":{"variants":["Bandit regret is just concentration math","Every bandit algorithm is a confidence interval","From UCB to GP-UCB: one statistical proof","Regret bounds via one non-asymptotic toolbox","Bandits and functional data share a skeleton"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000179,"raw_usage":{"total_tokens":1280,"prompt_tokens":906,"completion_tokens":374,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":303}},"tokens_in":522,"tokens_out":374,"duration_ms":4048,"temperature":1.0,"reasoning_tokens":303,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:41:33.788719+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a K-armed bandit with near-equal means (small gaps $\\Delta_k$) and rewards drawn from a mixture such as $0.4\\,N(0,1) + 0.6\\,N(0,9)$, so the true sub-Gaussian proxy exceeds 1; run Algorithm 3 with proxy 1 for $T=10^4$ and compare the observed cumulative regret to $3\\sum_k \\Delta_k + 8\\sqrt{TK\\log T}$, since a violation at the claimed confidence level would show that the known-proxy assumption is carrying the central theorem.","supporting_citations":[{"cited_title":"Tight non-asymptotic inference via sub-Gaussian intrinsic moment norm","cited_arxiv_id":null,"evidence_quote":"Supports Section 6.4 on estimating the sub-Gaussian variance proxy when it is unknown."}],"review_version":1}