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 asymptotic complexity in the so-called fixed-confidence setting has been completely characterized in Garivier and Kaufmann (2016) and Chernoff (1959), while little is known about the asymptotic complexity in its "dual" setting called fixed-budget setting. This note discusses the open problems and conjectures about the instance-dependent asymptotic complexity in the fixed-budget setting.
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 …
Locally Optimal Fixed-Budget Best Arm Identification in Two-Armed Gaussian Bandits with Unknown Variances
We address the problem of best arm identification (BAI) with a fixed budget for two-armed Gaussian bandits. In BAI, given multiple arms, we aim to find the best arm, an arm with the highest expected reward, through an ad…
Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits
We study the problem of best arm identification in linear bandits in the fixed-budget setting. By leveraging properties of the G-optimal design and incorporating it into the arm allocation rule, we design a parameter-fre…
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