Max-Quantile Grouped Infinite-Arm Bandits
This addresses a theoretical bandit problem for researchers in sequential decision-making, but appears incremental as it extends existing grouped bandit frameworks to infinite arms with quantile objectives.
The paper tackles the problem of identifying which group of infinitely many arms has the highest (1-α)-quantile in its reservoir distribution, using minimal total arm pulls. The result is a two-step algorithm with characterized instance-dependent and worst-case regret, including a matching lower bound for the worst-case.
In this paper, we consider a bandit problem in which there are a number of groups each consisting of infinitely many arms. Whenever a new arm is requested from a given group, its mean reward is drawn from an unknown reservoir distribution (different for each group), and the uncertainty in the arm's mean reward can only be reduced via subsequent pulls of the arm. The goal is to identify the infinite-arm group whose reservoir distribution has the highest $(1-α)$-quantile (e.g., median if $α= \frac{1}{2}$), using as few total arm pulls as possible. We introduce a two-step algorithm that first requests a fixed number of arms from each group and then runs a finite-arm grouped max-quantile bandit algorithm. We characterize both the instance-dependent and worst-case regret, and provide a matching lower bound for the latter, while discussing various strengths, weaknesses, algorithmic improvements, and potential lower bounds associated with our instance-dependent upper bounds.