On the Existence of a Complexity in Fixed Budget Bandit Identification

Rémy Degenne
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1131-1154, 2023.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-degenne23a, title = {On the Existence of a Complexity in Fixed Budget Bandit Identification}, author = {Degenne, R{\'e}my}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {1131--1154}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/degenne23a/degenne23a.pdf}, url = {https://proceedings.mlr.press/v195/degenne23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T On the Existence of a Complexity in Fixed Budget Bandit Identification %A Rémy Degenne %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-degenne23a %I PMLR %P 1131--1154 %U https://proceedings.mlr.press/v195/degenne23a.html %V 195 %X 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.
APA
Degenne, R.. (2023). On the Existence of a Complexity in Fixed Budget Bandit Identification. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:1131-1154 Available from https://proceedings.mlr.press/v195/degenne23a.html.

Related Material