A Fast Algorithm for PAC Combinatorial Pure Exploration
  We consider the problem of Combinatorial Pure Exploration (CPE), which deals
with finding a combinatorial set or arms with a high reward, when the rewards
of individual arms are unknown in advance and must be estimated using arm
pulls. Previous algorithms for this problem, while obtaining sample complexity
reductions in many cases, are highly computationally intensive, thus making
them impractical even for mildly large problems. In this work, we propose a new
CPE algorithm in the PAC setting, which is computationally light weight, and so
can easily be applied to problems with tens of thousands of arms. This is
achieved since the proposed algorithm requires a very small number of
combinatorial oracle calls. The algorithm is based on successive acceptance of
arms, along with elimination which is based on the combinatorial structure of
the problem. We provide sample complexity guarantees for our algorithm, and
demonstrate in experiments its usefulness on large problems, whereas previous
algorithms are impractical to run on problems of even a few dozen arms. The
code for the algorithms and experiments is provided at
https://github.com/noabdavid/csale.
