Pure Exploration in Infinitely-Armed Bandit Models with Fixed-Confidence
We consider the problem of near-optimal arm identification in the fixed confidence setting of the infinitely armed bandit problem when nothing is known about the arm reservoir distribution. We (1) introduce a PAC-like framework within which to derive and cast results; (2) derive a sample complexity lower bound for near-optimal arm identification; (3) propose an algorithm that identifies a nearly-optimal arm with high probability and derive an upper bound on its sample complexity which is within a log factor of our lower bound; and (4) discuss whether our log^2(1/delta) dependence is inescapable for "two-phase" (select arms first, identify the best later) algorithms in the infinite setting. This work permits the application of bandit models to a broader class of problems where fewer assumptions hold.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Pure Exploration in Asynchronous Federated Bandits
We study the federated pure exploration problem of multi-armed bandits and linear bandits, where $M$ agents cooperatively identify the best arm via communicating with the central server. To enhance the robustness against…
Multi-Armed BanditsPure exploration in multi-armed bandits with low rank structure using oblivious sampler
In this paper, we consider the low rank structure of the reward sequence of the pure exploration problems. Firstly, we propose the separated setting in pure exploration problem, where the exploration strategy cannot rece…
Multi-Armed BanditsAsymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits
We study pure exploration with infinitely many bandit arms generated \iid from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability $1-\delta$, wi…
Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits
We study pure exploration with infinitely many bandit arms generated i.i.d. from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability $1-\delta$, …
Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
We study the real-valued combinatorial pure exploration of the multi-armed bandit in the fixed-budget setting. We first introduce the Combinatorial Successive Asign (CSA) algorithm, which is the first algorithm that can …