Research map / Bandits and online learning / Multi-armed bandits

Sharp Non-Asymptotic Analysis of the Penalized Challenger in $\beta$-EB-TCI for Bernoulli Bandits

NeurIPS 2026 · Bandits and online learning › Multi-armed bandits · approach: Fixed-confidence versus fixed-budget identification

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes the logarithmically penalized challenger of Bernoulli beta-EB-TCI top-two best-arm identification, proving a sharp T_beta*(mu) log(1/delta) stopping bound in a stabilized regime and expected sample complexity via an exploration guard.

Problem

Non-asymptotic, sharp fixed-confidence sample complexity of top-two algorithms (beta-EB-TCI) for best-arm identification in Bernoulli bandits, where termination and entry into a stabilized regime must be controlled.

Approach

Combines a discrete penalized population allocation benchmark and a time-uniform empirical-to-population pairwise Bernoulli GLR bound to show that once the true best arm is a stable leader with sampling fraction near beta, stopping time has leading term T_beta*(mu) log(1/delta); an O(sqrt(Kt)) exploration guard makes the expected bound hold for any number of arms.

Key results

• Empirical mean stopping times match the threshold-crossing predictor with mean absolute relative error 1.53% (guarded) and 1.66% (unguarded) across grid settings; no wrong recommendations in 18,000 penalized runs.
• On tie-close4 with beta=0.5 and delta=1e-8, guard reduces median stopping time from 104,918 to 103,743; largest guarded pull fraction is 0.0069%.
• Removing the log count penalty raises mean stopping time from 105,593 to 188,036 with 12.8% of runs hitting the cap.

Surprising findings

• Removing the logarithmic count penalty substantially worsens performance on the equal-mean stress test (mean stopping time 105,593 to 188,036; 12.8% of runs hit cap).
• A single pointwise penalized-index comparison cannot by itself give a tail bound strong enough for finite expected stabilization time with tied suboptimal means.

Limitations

• Expected sample-complexity bound for the unguarded rule with tied suboptimal means remains unresolved; pairwise-distinct corollary relies on a prior tie-breaking convention.
• Analysis restricted to Bernoulli rewards with fixed beta; no online beta adaptation.
• Lower-order constants not optimized and no matching non-asymptotic lower bound claimed.

Experimental setup

Benchmarks: simulated Bernoulli bandit instances (sep5, cluster-close5, tie-close4)

Metrics: stopping time relative error vs predictor wrong recommendation rate guard overhead fraction

Baselines: Track-and-Stop unpenalized top-two variant idealized globally optimal allocation reference

Builds on: Jourdan et al. 2022 EB-TCI Track-and-Stop Garivier and Kaufmann 2016 characteristic time Gaussian TTUCB

Closest papers by meaning

• Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification? (NeurIPS 2026 · similarity 0.89)
• On Universally Optimal Algorithms for A/B Testing (ICML 2024 · similarity 0.89)
• Near Optimal Non-asymptotic Sample Complexity of 1-Identification (ICML 2025 · similarity 0.89)
• Optimal Top-Two Method for Best Arm Identification and Fluid Analysis (NeurIPS 2024 · similarity 0.88)
• Fixed Confidence Best Arm Identification in the Bayesian Setting (NeurIPS 2024 · similarity 0.88)
• Balancing Performance and Costs in Best Arm Identification (NeurIPS 2025 · similarity 0.87)