Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping
Huikang Liu, Zhengchao Wang, Daniel Kuhn, Wolfram Wiesemann
cs.LG · math.OC · stat.ML
Quick verdict
Exact LP for minimax one-arm Bernoulli stopping yields an index policy with 4.45√(KT)+10.75K regret; lowest estimated worst-case regret up to T=200 in tests.
Summary
The paper constructs an index policy for finite-horizon Bernoulli multi-armed bandits from minimax solutions of single-arm bandit (SAB) stopping problems. The authors show that the SAB minimax stopping problem admits an exact semi-infinite linear program over continuation probabilities (Theorem 1), with a count-state reduction (Proposition 1), the bound V_G(c) ≤ √(G/8e)+c (Proposition 2), and a finite-grid approximation whose added regret G(G+1)/(4M) is explicitly controlled (Proposition 3). Arm indices use cumulative continuation probabilities, made monotone in the known-arm reward via an envelope and capped by a reward-shortfall rule (Propositions 4–5, Lemma 1). The resulting policy achieves distribution-free regret at most 4.45√(KT)+10.75K for T ≥ 2K, matching the √(KT) minimax order; a Bernoulli randomization extends the guarantee to [0,1]-supported rewards. In experiments up to T=200, the SAB policy's single-arm worst-case regret is roughly half the best benchmark's, and the multi-arm policy beats KL-UCB, KL-UCB-Switch, MOSS, KL-MOSS, ε-TS, and Tsallis-INF across K=2,4,8, staying within 9.6–12.6% of a grid-based MAB minimax policy at K=2. Main limitations: the headline constant exceeds the best known 4; certified grid sizes appear heavier than those used experimentally; and no code availability is stated.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The single-arm minimax stopping problem admits an exact semi-infinite linear program whose optimal solution recovers a minimax stopping policy (Theorem 1), with value bounded by V_G(c) ≤ √(G/8e)+c (Proposition 2).
- An index built from cumulative continuation probabilities — monotone-adjusted via an envelope in the known-arm reward and capped by a reward-shortfall rule — yields a MAB policy with distribution-free regret at most 4.45√(KT)+10.75K for T ≥ 2K (Theorem 2).
- This bound matches the minimax-optimal √(KT) order against the 0.1365√(KT) lower bound of Cesa-Bianchi et al. (2006, Theorem 6.11), and extends to [0,1]-supported rewards via Bernoulli randomization (Remark 1).
- Numerically, the SAB-based index policy attains lower estimated worst-case regret than six benchmarks across all tested (K,T) with K ∈ {2,4,8}, T ≤ 200, and stays within 9.6–12.6% of a grid-based MAB minimax policy at K=2.
- A finite-grid implementation with quantified approximation loss (Proposition 3) suffices for the guarantee, since the analysis needs only a uniform SAB regret bound, not exact minimax policies.
Strengths
Exact, two-directional LP characterization
Theorem 1 proves the constraint array representation of stopping policies is exact, not a relaxation: any feasible array recovers a policy via (3), and any policy maps to a feasible array; attainment is established via compactness and regret continuity (Appendix A.1).
Original and clean one-arm-to-multi-arm bridge
Proposition 4's shared-threshold identity rewrites SAB regret as total probability of wrong continuation decisions; Proposition 5's monotone envelope plus reward-shortfall cap preserves bounded regret, and Lemma 1 supplies exactly the index implications used in the Section 5.3 proof.
Unusually careful constant certification
Honest, noise-free SAB benchmarking and a genuine MAB sanity check
Concrete practical implementation
Weaknesses
Theory–practice grid mismatch
Headline constant is not the best known or the best-proven one
Modest experimental scale and heuristic worst-case search
Missing motivating example
No code or solver details
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
This is a theory-driven method paper on finite-horizon Bernoulli multi-armed bandits (MAB). The authors build an index policy from minimax solutions of single-arm bandit (SAB) stopping problems: for each known-arm reward c ∈ [0,1], the SAB minimax stopping policy is characterized exactly by a semi-infinite linear program over continuation probabilities (Theorem 1), exploiting a count-state sufficiency reduction (Proposition 1, extending Bradt et al. 1956). Central claims: (i) the exact LP characterization with attainment of the optimum; (ii) an index — the largest c whose cumulative continuation probability, after a monotone envelope adjustment and a reward-shortfall cap (Propositions 4–5, Lemma 1), still exceeds a per-arm uniform threshold — yields a MAB policy with distribution-free regret ≤ 4.45√(KT)+10.75K for T ≥ 2K (Theorem 2), matching the √(KT) minimax order against the 0.1365√(KT) lower bound of Cesa-Bianchi et al. (2006); (iii) extension to [0,1]-supported rewards via Bernoulli randomization (Remark 1); (iv) empirical dominance of six benchmarks up to T=200.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the SAB-based index policy for multi-armed bandits?
Each arm is assigned an index equal to the largest known-arm reward c for which a minimax single-arm stopping policy would still keep sampling that arm given its observed history — after a monotone adjustment in c and a cap that stops arms whose cumulative reward falls short of c's benchmark by a tolerance b. Each round, the policy pulls the arm with the largest index, and an arm switches to its empirical mean once it has been pulled H=⌈T/K⌉ times.
What regret guarantee does the policy achieve?
For Bernoulli bandits with K arms and horizon T ≥ 2K, worst-case expected regret is at most 4.45√(KT)+10.75K, matching the minimax-optimal √(KT) order (the best known lower bound is 0.1365√(KT)). With alternative parameters the proof yields 1.51√(KT)+1.9K, and a deterministic threshold variant gives 6.45√(KT)+17K. A Bernoulli-randomization reduction extends the guarantee to any rewards supported on [0,1].
How does it compare to UCB or Thompson sampling?
In estimated worst-case regret up to T=200 and K=2,4,8, it beat the tested benchmarks KL-UCB, KL-UCB-Switch, MOSS, KL-MOSS, ε-TS, and Tsallis-INF — by 11.2–13.2% at K=2, up to 17.6% at K=4 and 25.0% at K=8 (T=40). At K=2 it stayed within 9.6–12.6% of a directly optimized grid-based MAB minimax policy. These are finite-horizon empirical results; the proven constant (4.45) is still larger than Tsallis-INF's best known 4.
Is code available for this paper?
No code or data availability statement appears in the provided text. However, the algorithm is fully specified (Algorithm 1 plus the finite-grid construction in Section 5.4), so the pipeline — solving the SAB linear programs on a grid and precomputing continuation tables — could in principle be reimplemented.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1–5 are available only as captions and axis labels in the extracted text; exact curves, error bars, and randomized-state patterns could not be inspected.
- The interval-evaluation certifications in Appendix A.4 (r_κ0, γ⋆, Λ0 bounds) were not independently recomputed for this review.
- The text appears essentially complete (abstract through Appendix B), but PDF extraction artifacts (broken ligatures, inline math reflow) are present throughout.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.