Combinatorial Pure Exploration of Multi-Armed Bandits
We study the combinatorial pure exploration (CPE) problem in the stochastic multi-armed bandit setting, where a learner explores a set of arms with the objective of identifying the optimal member of a decision class, which is a collection of subsets of arms with certain combinatorial structures such as size-K subsets, matchings, spanning trees or paths, etc. The CPE problem represents a rich class of pure exploration tasks which covers not only many existing models but also novel cases where the object of interest has a nontrivial combinatorial structure. In this paper, we provide a series of results for the general CPE problem. We present general learning algorithms which work for all decision classes that admit offline maximization oracles in both fixed confidence and fixed budget settings. We prove problem-dependent upper bounds of our algorithms. Our analysis exploits the combinatorial structures of the decision classes and introduces a new analytic tool. We also establish a general problem-dependent lower bound for the CPE problem. Our results show that the proposed algorithms achieve the optimal sample complexity (within logarithmic factors) for many decision classes. In addition, applying our results back to the problems of top-K arms identification and multiple bandit best arms identification, we recover the best available upper bounds up to constant factors and partially resolve a conjecture on the lower bounds.
This paper is (to the best of my knowledge) the first paper that studies best 'configuration' identification (or pure-exploration) in combinatorial multi-armed bandit. Two algorithms are proposed: CLUCB in the fixed-confidence setting and CSAR in the fixed-budget setting, and a lower bound is given in the fixed-confidence setting. The algorithms generalize is a very nice and natural way the LUCB and SAR algorithm designed for K best arms (or TopK) identification. As highlighted by the authors, the main strenght of the algorithms is that they treat in a unified way every combinatorial bandit problem. Their analysis feature a complexity term H can can be particularized to each combinatorial problem and appears natural. However, the paper suffer from two shortcomings: first, there is a small error in the proof of Theorem 1 (that can be corrected, an union bound is missing) and second, it is far too long. A NIPS reviewer will clearly NOT read 40 pages... I would advise you to remove all extensions (Appendix B. Appendix C.2 and Appendix E.) and keep them for an extended paper in a journal (where they will be more likely to be really reviewed). Moreover, the references to the theory of matroids (already in the main text) are a bit difficult to get for a non-initiated reader (like myself), so you should either define matroids in the main text or not mention them. Theorem 1 is a high probabability bound on the number of samples from the arms needed to identify the best configuration in the fixed-confidence setting. Its proof consists in showing that on the event \xi on which for all t, the true means of all arms belong to their confidence interval, the algorithm outputs the right configuration and the number of sample used are upper bounded deterministically. And it is shown that the confidence intervals are chosen such that the event \xi has probability larger than 1 - \delta. This fact is actually not completely true with your choices of confidence intervals: in the display at line 706, the number of draws of arm e T_t(e) is random, so Hoeffding inequality cannot be applied directly: you should add a union bound (summing over all the possible values for T_t from 1 to t), which would lead to a log(CKt^3/\delta) -with some constant C- in your confidence interval. On the event \xi, the upper bound on the number of samples strongly relies on Lemma 10, which resorts to the width of a class \cM and to the concept of exchange class, which is particular to combinatorial problems. Finally, in the end of the proof of Theorem 1, you say that you get the upper bound "solving for T". Would it be possible that you really give an explicit upper bound on T rather than a big O?I did not read the proof of the analysis of CSAR, but I guess it uses similar tools on exchange classes pluged into the analysis of SAR (and I hope other reviewers will confirm it is right). The quality of the paper is good, it is well-structured, except for the presence of "Related works" in Section 6, which I think would be more naturally presented in the introduction. There are some weird formulations and english mistakes at some places, some of them are: l.24 "we prove problem-dependent upper bounds of our algorithm" -> for our algorithmsl.102 " a probability of error bound of the CSAR algorithm" -> an upper bound on the probability of error of the CSAR algorithml.113 "standard assumptions of the stochastic MAB" -> in the stochastic MABsecond paragraph of page 3 : you use too much "the learner" (he or him could be fine at some places)paragraph 3 of the same page: "two different stopping conditions", I would rather say "constraints" (since in the fixed-budget setting there is no stopping condition)l.137 -> we present THE CLUCB algorithml.187 -> of -> forIt is a bit difficult from the main text to really have an intuition on what the width of an exchange class represents, but I don't really know how to improve that.   There is though a small error in the proof that must be corrected