mlsanityData to 14 Oct 2026

Fixed-Confidence Guarantees for Bayesian Best-Arm Identification

arXiv 1910.10945 ↗First posted 24 Oct 2019cs.LG stat.MLcited by 38

Not on the map. Why?

Abstract (arXiv)

We investigate and provide new insights on the sampling rule called Top-Two Thompson Sampling (TTTS). In particular, we justify its use for fixed-confidence best-arm identification. We further propose a variant of TTTS called Top-Two Transportation Cost (T3C), which disposes of the computational burden of TTTS. As our main contribution, we provide the first sample complexity analysis of TTTS and T3C when coupled with a very natural Bayesian stopping rule, for bandits with Gaussian rewards, solving one of the open questions raised by Russo (2016). We also provide new posterior convergence results for TTTS under two models that are commonly used in practice: bandits with Gaussian and Bernoulli rewards and conjugate priors.

Key facts. Cited by 38 papers in the map (data through 14 Oct 2026). First posted on arXiv 24 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 11; 2024: 5; 2025: 2; 2026: 4.

38 papers.

Sort:

  1. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  2. 2021Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedbackcited by 21
  3. 2021Policy Choice and Best Arm Identification: Asymptotic Analysis of Exploration Samplingcited by 15
  4. 2022Information-Directed Selection for Top-Two Algorithmscited by 15
  5. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 12
  6. 2021Rate-optimal Bayesian Simple Regret in Best Arm Identificationcited by 11
  7. 2022Non-Asymptotic Analysis of a UCB-based Top Two Algorithmcited by 11
  8. 2021Best-Arm Identification in Correlated Multi-Armed Banditscited by 8
  9. 2022Adaptive Experimentation in the Presence of Exogenous Nonstationary Variationcited by 8
  10. 2023Best Arm Identification with Fairness Constraints on Subpopulationscited by 8
  11. 2021A Non-asymptotic Approach to Best-Arm Identification for Gaussian Banditscited by 7
  12. 2023On the Complexity of Differentially Private Best-Arm Identification with Fixed Confidencecited by 6
26 more
  1. 2024Best-Arm Identification in Unimodal Banditscited by 6
  2. 2022Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gapcited by 4
  3. 2022Thompson Sampling for (Combinatorial) Pure Explorationcited by 4
  4. 2023Price of Safety in Linear Best Arm Identificationcited by 4
  5. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
  6. 2022SPRT-based Efficient Best Arm Identification in Stochastic Banditscited by 3
  7. 2022Best Arm Identification with Contextual Information under a Small Gapcited by 3
  8. 2023Asymptotically Optimal Fixed-Budget Best Arm Identification with Variance-Dependent Boundscited by 3
  9. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  10. 2023Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budgetcited by 3
  11. 2022Active Sampling of Multiple Sources for Sequential Estimationcited by 2
  12. 2023Best Arm Identification in Stochastic Bandits: Beyond β-optimalitycited by 2
  13. 2023Adaptive Experimentation at Scale: A Computational Framework for Flexible Batchescited by 2
  14. 2024Adaptive Experimental Design for Policy Learningcited by 2
  15. 2024Fixing the Loose Brake: Exponential-Tailed Stopping Time in Best Arm Identificationcited by 2
  16. 2022Suboptimal Performance of the Bayes Optimal Algorithm in Frequentist Best Arm Identificationcited by 1
  17. 2023Best Arm Identification in Batched Multi-armed Bandit Problemscited by 1
  18. 2024UCB Exploration for Fixed-Budget Bayesian Best Arm Identificationcited by 1
  19. 2025Pure Exploration via Frank-Wolfe Self-Playcited by 1
  20. 2025Deceptive Exploration in Multi-armed Banditscited by 1
  21. 2023Sequential Best-Arm Identification with Application to Brain-Computer Interfacecited by 0
  22. 2024Fixed Confidence Best Arm Identification in the Bayesian Settingcited by 0
  23. 2026Active Hypothesis Testing for Correlated Combinatorial Anomaly Detectioncited by 0
  24. 2026Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Banditscited by 0
  25. 2026Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identificationcited by 0
  26. 2026Sharp Non-Asymptotic Analysis of the Penalized Challenger in β-EB-TCI for Bernoulli Banditscited by 0