Best-of-K Bandits
This addresses a combinatorial bandit problem relevant for optimization and decision-making under uncertainty, with incremental contributions to understanding subset selection in bandit settings.
The paper tackles the Best-of-K Bandit problem, where a player selects subsets to maximize expected reward by observing only the maximum reward in each subset, and presents distribution-dependent lower bounds showing that exhaustive search may be necessary in worst-case scenarios, but also provides an algorithm for independent arms that mitigates information occlusion issues.
This paper studies the Best-of-K Bandit game: At each time the player chooses a subset S among all N-choose-K possible options and observes reward max(X(i) : i in S) where X is a random vector drawn from a joint distribution. The objective is to identify the subset that achieves the highest expected reward with high probability using as few queries as possible. We present distribution-dependent lower bounds based on a particular construction which force a learner to consider all N-choose-K subsets, and match naive extensions of known upper bounds in the bandit setting obtained by treating each subset as a separate arm. Nevertheless, we present evidence that exhaustive search may be avoided for certain, favorable distributions because the influence of high-order order correlations may be dominated by lower order statistics. Finally, we present an algorithm and analysis for independent arms, which mitigates the surprising non-trivial information occlusion that occurs due to only observing the max in the subset. This may inform strategies for more general dependent measures, and we complement these result with independent-arm lower bounds.