mlsanityData to 7 Oct 2026

On the Existence of a Complexity in Fixed Budget Bandit Identification

arXiv 2303.09468 ↗First posted 16 Mar 2023stat.ML cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

In fixed budget bandit identification, an algorithm sequentially observes samples from several distributions up to a given final time. It then answers a query about the set of distributions. A good algorithm will have a small probability of error. While that probability decreases exponentially with the final time, the best attainable rate is not known precisely for most identification tasks. We show that if a fixed budget task admits a complexity, defined as a lower bound on the probability of error which is attained by the same algorithm on all bandit problems, then that complexity is determined by the best non-adaptive sampling procedure for that problem. We show that there is no such complexity for several fixed budget identification tasks including Bernoulli best arm identification with two arms: there is no single algorithm that attains everywhere the best possible rate.

Key facts. Cited by 19 papers in the map (data through 7 Oct 2026). Builds on 21 of its 30 references that are in the map. First posted on arXiv 16 Mar 2023.

Builds on

21 of 30 references.

References · 21

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 280
  2. 2016Optimal Best Arm Identification with Fixed Confidencecited by 233
  3. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  4. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  5. 2016An optimal algorithm for the Thresholding Bandit Problemcited by 62
  6. 2019Non-Asymptotic Pure Exploration by Solving Gamescited by 62
  7. 2019Pure Exploration with Multiple Correct Answerscited by 60
  8. 2019The True Sample Complexity of Identifying Good Armscited by 37
  9. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  10. 2017The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regimecited by 31
  11. 2021Fixed-Budget Best-Arm Identification in Structured Banditscited by 22
  12. 2022Minimax Optimal Algorithms for Fixed-Budget Best Arm Identificationcited by 20
9 more
  1. 2020Structure Adaptive Algorithms for Stochastic Banditscited by 19
  2. 2023Open Problem: Optimal Best Arm Identification with Fixed Budgetcited by 18
  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. 2018Sequential Test for the Lowest Mean: From Thompson to Murphy Samplingcited by 14
  6. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 12
  7. 2022On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Banditscited by 8
  8. 2021Problem Dependent View on Structured Thresholding Bandit Problemscited by 5
  9. 2021Online Sign Identification: Minimization of the Number of Errors in Thresholding Banditscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 8; 2025: 1; 2026: 3.

19 papers.

Sort:

  1. 2023Bandit Pareto Set Identification: the Fixed Budget Settingcited by 13
  2. 2023Best Arm Identification with Fixed Budget: A Large Deviation Perspectivecited by 12
  3. 2024Active Adaptive Experimental Design for Treatment Effect Estimation with Covariate Choicescited by 12
  4. 2024Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identificationcited by 9
  5. 2023Optimal Batched Best Arm Identificationcited by 8
  6. 2023An Anytime Algorithm for Good Arm Identificationcited by 6
  7. 2023On Universally Optimal Algorithms for A/B Testingcited by 5
  8. 2024Best Arm Identification with Minimal Regretcited by 5
  9. 2024Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Banditscited by 5
  10. 2024Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Banditscited by 4
  11. 2023Worst-Case Optimal Multi-Armed Gaussian Best Arm Identification with a Fixed Budgetcited by 3
  12. 2023Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variancescited by 3
7 more
  1. 2024Adaptive Experimental Design for Policy Learningcited by 1
  2. 2024Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identificationcited by 1
  3. 2024UCB Exploration for Fixed-Budget Bayesian Best Arm Identificationcited by 1
  4. 2025Admissibility of Completely Randomized Trials: A Large-Deviation Approachcited by 1
  5. 2026Fixed Budget is No Harder Than Fixed Confidence in Best-Arm Identification up to Logarithmic Factorscited by 0
  6. 2026varepsilon-Good Action Identification in Fixed-Budget Monte Carlo Tree Searchcited by 0
  7. 2026Fundamental Limitations of Fixed-Budget Best-Arm Identificationcited by 0