On the Existence of a Complexity in Fixed Budget Bandit Identification
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal Best Arm Identification in Two-Armed Bandits with a Fixed Budget under a Small Gap
We consider fixed-budget best-arm identification in two-armed Gaussian bandit problems. One of the longstanding open questions is the existence of an optimal strategy under which the probability of misidentification matc…
Causal InferenceTight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
We consider the problem of \textit{best arm identification} with a \textit{fixed budget $T$}, in the $K$-armed stochastic bandit setting, with arms distribution defined on $[0,1]$. We prove that any bandit strategy, for …
Open Problem: Optimal Best Arm Identification with Fixed Budget
Best arm identification or pure exploration problems have received much attention in the COLT community since Bubeck et al. (2009) and Audibert et al. (2010). For any bandit instance with a unique best arm, its asymptoti…
On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now we…
LEMMABest Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence
We study the problem of identifying the best arm(s) in the stochastic multi-armed bandit setting. This problem has been studied in the literature from two different perspectives: fixed budget and fixed confidence. We pro…