Top-two algorithms are simple and effective for fixed-confidence best-arm identification, but their sharp non-asymptotic behavior is still not well understood. We study this problem for Bernoulli bandits through β-EB-TCI, the empirical-best top-two rule of Jourdan et al., whose challenger is chosen using a Bernoulli transportation cost with a logarithmic count penalty. We prove that, after the empirical leader has become the true best arm and its sampling fraction stays close to β, the stopping time is Tβ⋆(μ)log(1/δ) up to lower-order concentration terms. We also show that, in this regime, every challenger is sampled linearly often. Thus, for the original algorithm without forced exploration, the main remaining difficulty is to control when the empirical leader becomes permanently correct. These results imply a non-asymptotic high-probability bound for all Bernoulli instances with a unique best arm. If the algorithm satisfies a finite-mean sufficient-exploration condition, the bound further yields the sharp expected sample complexity. In particular, this gives the sharp expectation result for the unguarded Bernoulli rule when all arm means are pairwise distinct, using the sufficient-exploration result of Jourdan et al. Finally, if we add a mild forced-exploration rule that contributes only O(Kt) pulls up to time t, we obtain a self-contained expected sample-complexity theorem for any number of arms under the unique-best-arm assumption. We also identify a limitation of proof strategies that try to handle equal suboptimal means through a single index-comparison argument.
Figures & tables
Figure 1 : Agreement between observed stopping times and the predictor at β=0.5 . Shaded bands are bootstrap percentile 95% confidence intervals for the empirical mean over 200 replications per point. The dashed curve is the threshold-crossing predictor tpred .
Figure 2 : Main experimental diagnostics. Left: empirical mean stopping time versus the threshold-crossing predictor over the complete evaluation grid for the guarded and unguarded algorithms. Right: β -sensitivity on cluster-close5 and tie-close4 with δ=10−6 .
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Experiment
Grid
Runs
Main evaluation
3 instances ×3 values of β×5 values of δ×2 variants ×200 reps
18,000
β -sweep
2 instances ×7 values of β×200 reps
2,800
Stress survival
2 penalized variants ×600 reps
1,200
Penalty ablation
1 unpenalized variant ×500 reps
500
Guard overhead
K∈{4,8,12,16} with reps 200,200,100,50
550
Appendix
Table 1: Experiment grids. The three main evaluation instances are sep5 , cluster-close5 , and tie-close4 . The evaluation confidence levels are 10−4,10−5,10−6,10−7,10−8 .
Variant
Settings
Median ARE
Mean ARE
Max ARE
Guarded penalized
45
1.39%
1.53%
3.86%
Unguarded penalized
45
1.60%
1.66%
4.20%
Appendix
Table 2: Absolute relative error between empirical mean stopping time and tpred over the complete evaluation grid. No penalized evaluation setting hits the simulation cap or yields a Monte Carlo misidentification.
Variant
Reps
Mean
Median
95 th percentile
Unguarded penalized
600
105,593
104,918
134,140
Guarded penalized
600
104,022
103,743
130,792
Unpenalized ablation
500
188,036
108,036
700,000
Appendix
Table 3: Stress-test stopping-time summaries on tie-close4 with β=0.5 and δ=10−8 . The unpenalized ablation hits the 700,000 -round cap in 12.8% of runs.
Instance
K
Reps
Mean τδ
Mean Gtot/τδ
95 th perc. Gtot/Kτδ
equal-close4
4
200
92,922
0.0058%
1.80%
equal-close8
8
200
196,872
0.0065%
1.80%
equal-close12
12
100
301,114
0.0069%
1.89%
equal-close16
16
50
417,489
0.0062%
1.41%
Appendix
Table 4: Guard overhead on the equal-close family with β=0.5 and δ=10−6 . The mean guard-round fraction is shown as a percentage.
Instance
β
Mean τδ
tpred
Relative error
cluster-close5
0.2
34,151
33,901
0.74%
cluster-close5
0.3
28,757
29,267
−1.74%
cluster-close5
0.4
29,141
29,001
0.48%
cluster-close5
0.5
31,390
31,334
0.18%
cluster-close5
0.6
36,063
36,505
−1.21%
cluster-close5
0.7
45,304
46,458
−2.48%
Appendix
Table 5: β -sensitivity with δ=10−6 , the guarded penalized rule, and 200 replications per point.
Instance
Method
β or α⋆
Reps
Mean τδ
SE
95 th perc.
cluster-close5
Guarded EB-TCI
0.400
200
29,141
401
38,530
cluster-close5
Idealized allocation tracking
0.357
200
34,808
411
43,978
tie-close4
Guarded EB-TCI
0.400
200
85,348
1,107
111,139
tie-close4
Idealized allocation tracking
0.367
200
102,085
1,373
132,011
Appendix
Table 6: Idealized population-allocation reference at δ=10−6 . The population-benchmark rows use the population-optimal Bernoulli allocation and the same GLR threshold as the EB-TCI experiments. No run in this table hits the cap or yields a Monte Carlo misidentification.
Figure 3 : Exploration guard diagnostics. Left: empirical survival curves on tie-close4 with β=0.5 and δ=10−8 , using 600 replications per penalized variant. Right: normalized guard overhead on the equal-close family with K∈{4,8,12,16} and δ=10−6 .
Figure 4 : Additional diagnostics. Left: the unpenalized challenger removes logNt,j but leaves the stopping rule and all other details unchanged. Right: final sampling fractions for the guarded rule with β=0.5 and δ=10−8 , compared with the optimal population weights.
Bandit algorithms generate data for downstream inference, but adaptive sampling biases post-bandit sample means. We analyze this bias for stable index algorithms, including UCB1 and its generalizations, and derive sharp leading-order expressions for the sample-mean bias and expected Z-statistic, in bandit experiments of fixed horizon T. Our characterization reveals the algorithmic origin of bias through a key index-function-dependent quantity, which we term effective exploration rate. For example, under UCB1, the effective exploration rate is of order logT, and the standardized bias of any arm (that is not uniquely optimal) decays at the extremely slow rate 1/logT. We also show how the choice of the index function affects both regret and bias, which reveals a regret-bias trade-off: more exploratory algorithm reduces bias but increases regret. We further show how bias most severely distorts confidence intervals and hypothesis tests when the tested arm is one of the tied-optimal arms. Our sharp characterization for bias uses a novel empirical fluid approximation of the algorithm's sampling dynamics, which may be of independent interest.
Lisu Wang, Yilun Chen, Jiaqi Lu
School of Data Science, The Chinese University of Hong Kong, Shenzhen · School of Management and Economics, The Chinese University of Hong Kong, Shenzhen
We consider Bayesian bandit models and prove that Thompson sampling makes at most twice the expected number of mistakes (selections of a suboptimal arm) as any other policy. Our analysis applies as long as the latent arm processes are independent and each arm evolves only when played. For stochastic bandits with best arm defined via mean reward, this confirms a conjecture of Guha and Munagala from 2014, where the factor 2 is already best possible. The result holds under any nonincreasing sequence of round weights, including fixed horizon and geometric discounting.
We study N-armed stochastic dueling bandits under the Condorcet-winner assumption, where three widely adopted objectives are considered: best-arm identification (BAI), weak regret, and strong regret. We propose Tree-Guided Identify-Then-Exploit (TG-ITE), the first unified framework to tackle all these objectives to our knowledge. Without requiring stronger assumptions, we propose a shared tree-guided identification approach to find a high-confidence incumbent within O(N) comparisons. We further propose varied exploitation strategies to utilize this warm-start stage to optimize the specific objectives at hand. This methodology enables our approach to (1) achieve O(N) sample complexity in BAI without commonly adopted stronger assumptions; (2) build the first winner-stays-style algorithm to achieve O(N) weak regret; (3) enjoy the same O(NlogT) guarantee as specialized strong-regret approaches; (4) realize the joint optimization of BAI and weak regret with O(N) guarantees for both, eliminating the sub-optimal gap of O(logN) in the existing approach. Our results provide evidence that the trade-off between BAI and regret minimization is relatively benign in dueling bandits.