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 a single 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.

翻译：在固定预算土匪识别中,一种算法按顺序观察从几个分布到某个最后时间的样本,然后回答关于分配组合的询问。好的算法将产生很小的误差概率。虽然这一概率随着最后时间指数下降,但对于大多数识别任务来说,最佳可达到的速率并不准确。我们表明,如果固定预算任务承认一个复杂程度,即对所有土匪问题的单一算法所达到的误差概率的下限较低,那么复杂性则由该问题的最佳非适应性抽样程序决定。我们表明,包括伯努利最佳武器识别和两只武器在内的若干固定预算识别任务并不复杂:没有一个单一算法能够达到任何地方最佳的速率。</s>