  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.
