mlsanityData to 7 Oct 2026

Top Two Algorithms Revisited

arXiv 2206.05979 ↗First posted 13 Jun 2022stat.ML cs.LGcited by 34

Not on the map. Why?

Abstract (arXiv)

Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models (Russo, 2016), for parametric families of arms. They select the next arm to sample from by randomizing among two candidate arms, a leader and a challenger. Despite their good empirical performance, theoretical guarantees for fixed-confidence best arm identification have only been obtained when the arms are Gaussian with known variances. In this paper, we provide a general analysis of Top Two methods, which identifies desirable properties of the leader, the challenger, and the (possibly non-parametric) distributions of the arms. As a result, we obtain theoretically supported Top Two algorithms for best arm identification with bounded distributions. Our proof method demonstrates in particular that the sampling step used to select the leader inherited from Thompson sampling can be replaced by other choices, like selecting the empirical best arm.

Key facts. Cited by 34 papers in the map (data through 7 Oct 2026). Builds on 17 of its 46 references that are in the map. First posted on arXiv 13 Jun 2022.

Builds on

17 of 46 references.

References · 17

  1. 2013lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Banditscited by 148
  2. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  3. 2018Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervalscited by 76
  4. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  5. 2019Pure Exploration with Multiple Correct Answerscited by 60
  6. 2017Improving the Expected Improvement Algorithmcited by 54
  7. 2020Review on Ranking and Selection: A New Perspectivecited by 28
  8. 2017A minimax and asymptotically optimal algorithm for stochastic banditscited by 27
  9. 2020Optimal Thompson Sampling strategies for support-aware CVaR banditscited by 26
  10. 2021Regret Minimization in Heavy-Tailed Banditscited by 24
  11. 2018KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpointscited by 20
  12. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 19
5 more
  1. 2020Optimal Best-Arm Identification Methods for Tail-Risk Measurescited by 17
  2. 2021A/B/n Testing with Control in the Presence of Subpopulationscited by 17
  3. 2014On the Complexity of A/B Testingcited by 14
  4. 2021From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Banditscited by 4
  5. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 10; 2024: 6; 2025: 9; 2026: 3.

34 papers.

Sort:

  1. 2022Dealing with Unknown Variances in Best-Arm Identificationcited by 13
  2. 2023Adaptive Algorithms for Relaxed Pareto Set Identificationcited by 13
  3. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 12
  4. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  5. 2024Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identificationcited by 9
  6. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  7. 2023Optimal Batched Best Arm Identificationcited by 8
  8. 2023Neural Exploitation and Exploration of Contextual Banditscited by 7
  9. 2023Optimal Best-Arm Identification in Bandits with Access to Offline Datacited by 6
  10. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
  11. 2024Best-Arm Identification in Unimodal Banditscited by 6
  12. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
22 more
  1. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  2. 2022SPRT-based Efficient Best Arm Identification in Stochastic Banditscited by 3
  3. 2022Best Arm Identification with Contextual Information under a Small Gapcited by 3
  4. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  5. 2024Preference-based Pure Explorationcited by 3
  6. 2025Risk-sensitive Bandits: Arm Mixture Optimality and Regret-efficient Algorithmscited by 3
  7. 2023Best Arm Identification in Stochastic Bandits: Beyond β-optimalitycited by 2
  8. 2024Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identificationcited by 2
  9. 2025FraPPE: Fast and Efficient Preference-based Pure Explorationcited by 2
  10. 2025Balancing Performance and Costs in Best Arm Identificationcited by 1
  11. 2025Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validationcited by 1
  12. 2025Fixed-Confidence Multiple Change Point Identification under Bandit Feedbackcited by 1
  13. 2025Pure Exploration via Frank-Wolfe Self-Playcited by 1
  14. 2023Best arm identification in rare eventscited by 0
  15. 2023Sequential Best-Arm Identification with Application to Brain-Computer Interfacecited by 0
  16. 2024Fixed Confidence Best Arm Identification in the Bayesian Settingcited by 0
  17. 2025Identifying the Best Transition Lawcited by 0
  18. 2025Pure Exploration with Infinite Answerscited by 0
  19. 2025Non-Asymptotic Analysis of (Sticky) Track-and-Stopcited by 0
  20. 2026Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identificationcited by 0
  21. 2026ICMAPE: In-Context Multiagent Pure Explorationcited by 0
  22. 2026Sharp Non-Asymptotic Analysis of the Penalized Challenger in β-EB-TCI for Bernoulli Banditscited by 0