Verification Based Solution for Structured MAB Problems
We consider the problem of finding the best arm in a stochastic Multi-armed Bandit (MAB) game and propose a general framework based on verification that applies to multiple well-motivated generalizations of the classic MAB problem. In these generalizations, additional structure is known in advance, causing the task of verifying the optimality of a candidate to be easier than discovering the best arm. Our results are focused on the scenario where the failure probability must be very low; we essentially show that in this high confidence regime, identifying the best arm is as easy as the task of verification. We demonstrate the effectiveness of our framework by applying it, and matching or improving the state-of-the art results in the problems of: Linear bandits, Dueling bandits with the Condorcet assumption, Copeland dueling bandits, Unimodal bandits and Graphical bandits.
This paper proposes a verification-based framework for solving a range of bandit problems, including condorcet dueling bandits, copeland dueling bandits, linear bandits, unimodal bandits, and graphical bandits.  The setting considered is PAC-style guarantees for pure exploration, rather than online regret minimization.  The authors show an iterative approach whereby a verification algorithm is used to verify a proposed solution by an exploration algorithm.  Since the verification algorithm has cheaper sample complexity, one can construct a meta-algorithm that iteratively calls the two algorithms in order to achieve rigorous PAC-style sample complexity guarantees.  These guarantees are compared against existing results, and the authors demonstrate improvements in some regimes.  In general, I think the technical results are interesting and mostly sound, although I can't help but feel that the presentation could be significantly improved.  Some of the results seem a bit incomplete, although I think a more complete theoretical account is straightforward.    My larger concern is the significance of the results in the paper.  Part of this could be resolved by greater clarity in the writing.  More details are covered in the sections below.  As it stands, my review is borderline.  I can see this paper as suitable for NIPS or a bit below the accept threshold, depending on the author response.
*** Significance Part 1 *** I wonder if the authors have looked into the details of the proofs of some of the previous work.  One common trick that people do in these types of theoretical analyses is to simplify the results because one cares only about the simpler bounds that merges together a more complicated summation of terms into a single term.  For example, the result for Linear Bandits shows an improvement that could be non-existent with a more refined analysis of the result in [19].  This would be somewhat analogous to what the authors noted in footnote 3.  *** Significance Part 2 *** The authors argue that these results are meaningful improvements upon previous work.  However, it would be easier to accept this argument if the authors can construct explicit cases that satisfy the results.  For instance, I'm particularly interested in the linear case.   Numerical experiments could also help and/or complement the theoretical results.  *** Clarity *** The paper feels a bit incomplete in its writing.  For instance, Copeland dueling bandits isn't substantially discussed at all in the main paper.  And related to the above point on significance, the reader feels a bit disappointed by a lack of substantial discussion on the implications of the theoretical results.  Furthermore, the paper doesn't actually formally define any problem settings.  I realize this is very difficult due to the generality of the framework being proposed, but this lack of specificity is somehow dissatisfying.  *** Proofs *** I'm curious about the equations after Line 135. It seems like there is an extra kappa*H_explore term -- can the authors explain this?  Perhaps related to the above question, the authors never explicitly state a sample complexity of the verification oracle when the findbestarm subroutine fails.  For instance, Lemma 14 doesn't have a sample complexity guarantee.  I think this should be a straightforward fix, but the theoretical results are incomplete without them.