Best-Arm Identification

Ask about this topic

Overview

Best-arm identification is the problem of choosing the best among several options when each evaluation is noisy, as in bandit experiments, model evaluation, or hyperparameter search. Algorithms such as successive elimination and halving, as well as Track-and-Stop, allocate samples adaptively and use confidence bounds or likelihood tests to decide what to keep and when to stop. Work considers fixed budgets or prescribed confidence levels, and extends these methods to pairwise comparisons, multiple objectives, costs, fairness constraints, and nonstationary rewards; evaluations often use synthetic Gaussian or Bernoulli bandits and real model or policy benchmarks. A central challenge is reducing evaluations by exploiting gaps, correlations, or prior information without losing reliable guarantees when assumptions fail or the best options are nearly tied.

Latest papers

CardsList

49 papers8 papers in the last four weeks, up 60% on the four weeks before. 0.0% of all new papers.

  1. Bayesian Fixed-Confidence Best-Arm Identification with Abstention

    Oct 21, 2026Yuqi Huang, Yunlong Hou, Vincent Y. F. TanBest-Arm Identification

    Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore

  2. Rethinking Successive Rejects Algorithms

    Oct 15, 2026Mohamed Khair, Junpei KomiyamaBest-Arm IdentificationMulti-Armed Bandits

    Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP

  3. When More Objectives Make Identification Easier: The Role of Preferences and Feedback

    Oct 13, 2026Bo Xue, Ji Cheng, Yuanyu Wan +1Multi-Armed BanditsBest-Arm Identification

    City University of Hong Kong · Zhejiang University

  4. Few-for-Many Best-Arm Identification in Multi-Objective Bandits

    Oct 12, 2026Bo Xue, Yilu Liu, Haodong Jing +3Multi-Armed BanditsBest-Arm Identification

    City University of Hong Kong. · Xi’an Jiaotong University. · Northwest Polytechnical University.

  5. Best Arm Identification for Bandits with Shifting Means

    Oct 7, 2026Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal +2Multi-Armed BanditsBest-Arm Identification

    CWI and Booking.com Science Park 123 1098 XG Amsterdam · CWI and University of Twente Science Park 123 1098 XG Amsterdam · Indian Institute of Science (IISc), Bengaluru CV Raman Rd, Bengaluru, Karnataka 560012, India +2

  6. Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy

    Oct 3, 2026Keqin Chen, Jie Bian, Yulian Wu +1Best-Arm IdentificationMulti-Armed Bandits

    Institute of Data Science National University of Singapore · Department of Electrical and Computer Engineering National University of Singapore · Department of Mathematics National University of Singapore

  7. Nearly Optimal Fixed-Confidence Best-Arm Identification with 1-Bit Feedback

    Oct 2, 2026Khang Luong, Dinh Thai Son, Hoang Ta +2Best-Arm IdentificationMulti-Armed Bandits

    Hanoi University of Science and Technology · Quantum AI & Cyber Security Institute, FPT Corporation

  8. Sharp Non-Asymptotic Analysis of the Penalized Challenger in ββ-EB-TCI for Bernoulli Bandits

    Oct 1, 2026Nam Nguyen, Tuan Quang DamMulti-Armed BanditsBest-Arm Identification

    Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam

  9. Quantum Monte Carlo Tree Search with Fixed Confidence

    Sep 27, 2026Mingjie Hu, Jian-Qiang Hu, Enlu ZhouMonte Carlo Tree SearchBest-Arm Identification

    School of Management, Fudan University · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

  10. Cost-Aware Best-LLM Identification using Dueling Feedback

    Sep 24, 2026Sarvesh Gharat, Nikhil Karamchandani, Jayakrishnan NairDueling BanditsBest-Arm Identification

    Centre for Machine Intelligence and Data Science (C-MInDS) Indian Institute of Technology Bombay · Department of Electrical Engineering Indian Institute of Technology Bombay

  11. Efficient Cost-Aware LLM Evaluation via Bayesian Bandit Gittins Indices

    Sep 22, 2026Qian Xie, Yueli He, Nairen CaoMulti-Armed BanditsLLM Evaluation

    Cornell University · Columbia University · New York University +1

  12. Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

    Sep 12, 2026Jiarui Yao, Jiaxi Zhao, Xiangxin ZhouBest-Arm IdentificationSample Complexity

    UIUC · NUS · Tencent Hunyuan

  13. A positive resolution of the gap-entropy conjecture

    Sep 9, 2026P. M. Aronow, Nathan Kallus, Patrick LopattoBest-Arm IdentificationInformation-Theoretic Lower Bounds

  14. The Price of Decentralization in Top-KK Arm Identification

    Aug 22, 2026Larissa Xu, Jasmine Nguyen, William ChangMulti-Armed BanditsBest-Arm Identification

    Department of Applied Mathematics, University of California, Los Angeles, USA

  15. Variance Driven Exploration: A Provable and Efficient Methodology for Pure Exploration in Highly Stochastic Environments

    Aug 22, 2026Khang Luong, Nam Nguyen, Hoang Ta +2Uncertainty-Aware ExplorationRL Exploration

    Hanoi University of Science and Technology, Hanoi, Vietnam · Quantum AI & Cyber Security Institute, FPT Corporation, Vietnam.

  16. Where Does the Union Bound Go? Best-Arm Identification and Strong FWER Control

    Aug 20, 2026Rianne de HeideBest-Arm IdentificationMulti-Armed Bandits

    Department of Applied Mathematics, University of Twente · Centrum Wiskunde & Informatica, Amsterdam

  17. Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

    Aug 15, 2026Jingxin Zhan, Yuze Han, Zhihua ZhangMulti-Armed BanditsBest-Arm Identification

    School of Mathematical Sciences, Peking University · Center for Applied Statistics and School of Statistics, Renmin University of China

  18. Dynamically Allocating Evaluation Effort for Model Ranking

    Aug 4, 2026Vilém Zouhar, Julia Kreutzer, Alon Lavie +4Model SelectionMulti-Armed Bandits

    ETH Zurich · Cohere Labs · Carnegie Mellon University +3

  19. Dominant Arm Identification with Mixing and Recycling Observed Samples

    Aug 2, 2026Jonghyun Sim, Wonyoung KimMulti-Armed BanditsBest-Arm Identification

    Chung-Ang University, Seoul, Republic of Korea.

  20. MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Bandits

    Jul 16, 2026Xin Li, Zixin ZhongMulti-Armed BanditsMechanism Design

    Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou)

  21. Fundamental Limitations of Fixed-Budget Best-Arm Identification

    Jul 13, 2026Motti GoldbergerMulti-Armed BanditsBest-Arm Identification

    Yale University

  22. Optimal Top-kk Identification from Pairwise Comparisons

    Jul 9, 2026Motti Goldberger, Nils RudiPairwise Preference LearningMulti-Armed Bandits

    Yale University, New Haven, CT, USA.

  23. Best-Arm Identification with Generative Proxy

    Jul 8, 2026Tianyi Ma, Hanzhang Qin, Ruihao Zhu +1Multi-Armed BanditsBest-Arm Identification

    School of Operations Research and Information Engineering, Cornell University · Department of Industrial Systems Engineering and Management, National University of Singapore · SC Johnson College of Business, Cornell University +1

  24. Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis

    Jul 5, 2026Harsh Shrivastava, Yuta Kawakami, Junpei Komiyama +1Multi-Armed BanditsCausal Effect Estimation

    Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, UAE · RIKEN AIP, Tokyo, Japan

  25. Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition

    Jun 28, 2026Yuqi Huang, Yunlong Hou, Vincent Y. F. TanMulti-Armed BanditsBest-Arm Identification

    Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore

  26. Ranking-and-Selection with Multiple Correct Answers and Non-Answerable Estimates

    Jun 20, 2026Qiaoqiao Wang, Wei YouBest-Arm IdentificationAdaptive Sampling

    Dept. of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology, Hong Kong, China

  27. Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

    Jun 8, 2026Vladimir Braverman, Chen Wang, Liudeng Wang +1Multi-Armed BanditsBest-Arm Identification

    Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

  28. Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity

    Jun 5, 2026Zifan Lyu, Chahine Nejma, Tobias Wegel +2Model SelectionMulti-Armed Bandits

    1ETH Zurich · 2Centrale Sup´elec · 3ENS de Cachan +1

  29. Provably Reduced Sample Cost in Prior-Guided Hyperparameter Optimization

    Jun 3, 2026Leona Hennig, Jasmin Brandt, Lukas Fehring +3Multi-Fidelity OptimizationMulti-Armed Bandits

    Institute of Artificial Intelligence Leibniz University Hanover, Germany · University of Bielefeld Bielefeld, Germany · Institute of Artificial Intelligence, Leibniz University Hanover & L3S Research Center Hanover, Germany

  30. Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits

    Jun 1, 2026Pu Wang, Yao-Xiang DingMulti-Armed BanditsBest-Arm Identification

    State Key Lab of CAD&CG, Zhejiang University