mlsanityData to 7 Oct 2026

Non-Asymptotic Analysis of a UCB-based Top Two Algorithm

arXiv 2210.05431 ↗First posted 11 Oct 2022stat.ML cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

A Top Two sampling rule for bandit identification is a method which selects the next arm to sample from among two candidate arms, a leader and a challenger. Due to their simplicity and good empirical performance, they have received increased attention in recent years. However, for fixed-confidence best arm identification, theoretical guarantees for Top Two methods have only been obtained in the asymptotic regime, when the error level vanishes. In this paper, we derive the first non-asymptotic upper bound on the expected sample complexity of a Top Two algorithm, which holds for any error level. Our analysis highlights sufficient properties for a regret minimization algorithm to be used as leader. These properties are satisfied by the UCB algorithm, and our proposed UCB-based Top Two algorithm simultaneously enjoys non-asymptotic guarantees and competitive empirical performance.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 23 of its 53 references that are in the map. First posted on arXiv 11 Oct 2022.

Builds on

23 of 53 references.

References · 23

  1. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  2. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  3. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  4. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  5. 2016An optimal algorithm for the Thresholding Bandit Problemcited by 62
  6. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  7. 2017Improving the Expected Improvement Algorithmcited by 54
  8. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  9. 2019Fixed-Confidence Guarantees for Bayesian Best-Arm Identificationcited by 38
  10. 2022Top Two Algorithms Revisitedcited by 34
  11. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
  12. 2016Towards Instance Optimal Bounds for Best Arm Identificationcited by 30
11 more
  1. 2017Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selectioncited by 28
  2. 2020Review on Ranking and Selection: A New Perspectivecited by 28
  3. 2021Regret Minimization in Heavy-Tailed Banditscited by 24
  4. 2020Structure Adaptive Algorithms for Stochastic Banditscited by 19
  5. 2021Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Samplingcited by 15
  6. 2022Information-Directed Selection for Top-Two Algorithmscited by 15
  7. 2014On the Complexity of A/B Testingcited by 14
  8. 2022Dealing with Unknown Variances in Best-Arm Identificationcited by 13
  9. 2021A Non-asymptotic Approach to Best-Arm Identification for Gaussian Banditscited by 7
  10. 2022On the complexity of All varepsilon-Best Arms Identificationcited by 6
  11. 2022SPRT-based Efficient Best Arm Identification in Stochastic Banditscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 3; 2025: 1; 2026: 2.

11 papers.

  1. 2023Optimal Batched Best Arm Identificationcited by 8
  2. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  3. 2024Best-Arm Identification in Unimodal Banditscited by 6
  4. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
  5. 2023An varepsilon-Best-Arm Identification Algorithm for Fixed-Confidence and Beyondcited by 3
  6. 2023Best Arm Identification in Stochastic Bandits: Beyond β-optimalitycited by 2
  7. 2024Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identificationcited by 2
  8. 2024Fixed Confidence Best Arm Identification in the Bayesian Settingcited by 0
  9. 2025Non-Asymptotic Analysis of (Sticky) Track-and-Stopcited by 0
  10. 2026Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identificationcited by 0
  11. 2026Sharp Non-Asymptotic Analysis of the Penalized Challenger in β-EB-TCI for Bernoulli Banditscited by 0