Best 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 propose a unifying approach that leads to a meta-algorithm called unified gap-based exploration (UGapE), with a common structure and similar theoretical analysis for these two settings. We prove a performance bound for the two versions of the algorithm showing that the two problems are characterized by the same notion of complexity. We also show how the UGapE algorithm as well as its theoretical analysis can be extended to take into account the variance of the arms and to multiple bandits. Finally, we evaluate the performance of UGapE and compare it with a number of existing fixed budget and fixed confidence algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 …
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…
Tight (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 …
Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits
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. …
Fixed-Budget Best-Arm Identification in Structured Bandits
Best-arm identification (BAI) in a fixed-budget setting is a bandit problem where the learning agent maximizes the probability of identifying the optimal (best) arm after a fixed number of observations. Most works on thi…
Multi-Armed Bandits