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

Nicolas Nguyen, Imad Aouali, András György, Claire Vernade
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:379-387, 2025.

Abstract

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 lies in introducing novel proof techniques that yield tighter bounds for multi-armed BAI compared to existing approaches. Our work provides new insights into Bayesian fixed-budget BAI in structured bandits, and extensive experiments demonstrate the consistent and robust performance of our method in practice across various settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-nguyen25a, title = {Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits}, author = {Nguyen, Nicolas and Aouali, Imad and Gy{\"o}rgy, Andr{\'a}s and Vernade, Claire}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {379--387}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/nguyen25a/nguyen25a.pdf}, url = {https://proceedings.mlr.press/v258/nguyen25a.html}, abstract = {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 lies in introducing novel proof techniques that yield tighter bounds for multi-armed BAI compared to existing approaches. Our work provides new insights into Bayesian fixed-budget BAI in structured bandits, and extensive experiments demonstrate the consistent and robust performance of our method in practice across various settings.} }
Endnote
%0 Conference Paper %T Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits %A Nicolas Nguyen %A Imad Aouali %A András György %A Claire Vernade %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-nguyen25a %I PMLR %P 379--387 %U https://proceedings.mlr.press/v258/nguyen25a.html %V 258 %X 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 lies in introducing novel proof techniques that yield tighter bounds for multi-armed BAI compared to existing approaches. Our work provides new insights into Bayesian fixed-budget BAI in structured bandits, and extensive experiments demonstrate the consistent and robust performance of our method in practice across various settings.
APA
Nguyen, N., Aouali, I., György, A. & Vernade, C.. (2025). Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:379-387 Available from https://proceedings.mlr.press/v258/nguyen25a.html.

Related Material