mlsanityData to 13 Oct 2026

Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits

arXiv 2402.05878 ↗First posted 8 Feb 2024stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the problem of Bayesian fixed-budget best-arm identification (BAI) in structured bandits. We propose an algorithm that uses fixed allocations based on the prior information and the structure of the environment. We provide theoretical bounds on its performance across diverse models, including the first prior-dependent upper bounds for linear and hierarchical BAI. Our key contribution is introducing new proof methods that result in tighter bounds for multi-armed BAI compared to existing methods. We extensively compare our approach to other fixed-budget BAI methods, demonstrating its consistent and robust performance in various settings. Our work improves our understanding of Bayesian fixed-budget BAI in structured bandits and highlights the effectiveness of our approach in practical scenarios.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Builds on 29 of its 51 references that are in the map. First posted on arXiv 8 Feb 2024.

Builds on

29 of 51 references.

References · 29

  1. 2016Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimizationcited by 693
  2. 2017A Tutorial on Thompson Samplingcited by 423
  3. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 281
  4. 2016Simple Bayesian Algorithms for Best Arm Identificationcited by 116
  5. 2016Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problemcited by 79
  6. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  7. 2021Meta-Thompson Samplingcited by 62
  8. 2020An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Banditscited by 45
  9. 2020Latent Bandits Revisitedcited by 43
  10. 2021Bayesian decision-making under misspecified priors with applications to meta-learningcited by 43
  11. 2021Hierarchical Bayesian Banditscited by 34
  12. 2022Top Two Algorithms Revisitedcited by 34
17 more
  1. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  2. 2021No Regrets for Learning the Prior in Banditscited by 29
  3. 2021Fixed-Budget Best-Arm Identification in Structured Banditscited by 22
  4. 2023On the Existence of a Complexity in Fixed Budget Bandit Identificationcited by 20
  5. 2022Deep Hierarchy in Banditscited by 19
  6. 2023Open Problem: Optimal Best Arm Identification with Fixed Budgetcited by 18
  7. 2017Variational inference for the multi-armed contextual banditcited by 15
  8. 2021Metalearning Linear Bandits by Prior Updatecited by 15
  9. 2022Mixed-Effect Thompson Samplingcited by 14
  10. 2022Bayesian Fixed-Budget Best-Arm Identificationcited by 13
  11. 2021Rate-optimal Bayesian Simple Regret in Best Arm Identificationcited by 11
  12. 2022Meta-Learning for Simple Regret Minimizationcited by 10
  13. 2022Multi-Task Off-Policy Learning from Bandit Feedbackcited by 9
  14. 2023VITS : Variational Inference Thompson Sampling for contextual banditscited by 6
  15. 2023On Universally Optimal Algorithms for A/B Testingcited by 6
  16. 2023Thompson Exploration with Best Challenger Rule in Best Arm Identificationcited by 4
  17. 2023Improving the Knowledge Gradient Algorithmcited by 2

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 2.

4 papers.

  1. 2024Generalized Neyman Allocation for Locally Minimax Optimal Best-Arm Identificationcited by 1
  2. 2024UCB Exploration for Fixed-Budget Bayesian Best Arm Identificationcited by 1
  3. 2026Regime-Conditioned Evaluation in Multi-Context Bayesian Optimizationcited by 0
  4. 2026Leveraging Similarities in Multi-Armed Banditscited by 0