Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a new framework for structured (and unstructured) pure exploration problems. They propose a new algorithm based on modified FW where the motivation comes from the BC algorithm from the TaS paper that can be interpreted as an FW step. They show the asymptotic optimality of the algorithm and provide a finite-time analysis. The empirical results on various bandit problems show the superiority of the proposed framework.
 
main_review: high originality, mediocre quality (see my comments on experiments below), clarity is good, and the significance is above bar.

* The main contribution is very clear: they provide a new framework and recipe for solving generic pure exploration problems. I think the authors did a nice job of interpreting best challenger from Garivier & Kauffman as a frank-wolfe step and find a way to do it right.
* I feel the experiments are quite biased in that the baseline methods are missing a few popular algorithms including RAGE, LinGapE, and ALBA.  For the unstructured problem, lil ucb and LUCB are missing. Thus, I am not  convinced about its performance. 
* I was excited to read the abstract that we take only one step in each iteration since that would mean the computational complexity is much improved. However, it seems to require solving the linear program. Could the authors discuss the time complexity of the algorithm? For pure exploration problems, It seems to be worse than TaS.
* Please add a discussion on the significance of Theorem 2 in the main content of the paper. I guess the first term looks fine, but how should readers take \Psi() and T_{\epsilon,L}? Does the authors think the exponential dependence on K should be improvable? 

minor points
* L136: "close the boundary" => close to the boundeary?
* L151-152: "the optimism-in-front-of-uncertainty ": I've seen it called 'optimism in the face of uncertainty' more frequently.
* L680: did you mean [21] rather than [29] here? there are other places like L698.
* Okay, I am struggling with finding the precise definition of $\Lambda$​. So, $\Lambda$​ is the set of possible instances for which there is only a unique best arm? Then, it is not a convex set? I ask this to understand the if statement in Algorithm 1 that has $\hat \mu(t-1) \not \in \Lambda$​​ . I could guess but I would appreciate if the definition of $\Lambda$ is more explicit.
* Assumption 3: is \forall symbol missing in front of $\pi \in \mathcal{S}_{i^*(\mu)}$?
* L290: con() was defined as con{}.

----
(after rebuttal)
I am mostly satisfied with the rebuttal. I now remember that lil'ucb was evaluated in "Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting" and was empirically shown to be worse than LUCB in practical regimes anyways. But it would be great to have that remark in the final version.

For Assumption 3, I understand it now. I rephrase and expand the sentence to make it easier to read. 
limitations_and_societal_impact: I don't see a negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the pure exploration problem for stochastic bandits. In particular, the authors focus on the fixed-confidence setting. The main contributions of the paper are the following:

- First, the authors propose a variant of the BC algorithm by Garivier and Kaufmann, 2016, where the sampling rule is based on a Frank-Wolfe-type algorithm adapted to non-smooth functions. 
- Second, the authors show that the proposed algorithm is asymptotically optimal (in the sense that it matches the lower bound derived by Garivier and Kaufmann, 2016). 
- Experimental illustration is given on various scenarios including both structured (like linear BAI and BAI for Lipschitz bandits) and unstructured BAI. All the experiments are against several existing baselines (though probably better to add some more past and recent baselines as mentioned in the 'Limitations and Societal Impact' section).

main_review: Clarity: The paper is well written and the delivered message is clear. 

Quality: I did not check the all the proofs in detail (54 pages is quite long honestly), but they seem to be sound in general. Proof-related questions are listed in the 'Limitations And Societal Impact' section. 

Originality and significance: This paper proposed a variant of BC with a modified FW (adapted to non-smooth functions) that achieves the asymptotic optimality in a wide range of pure exploration scenarios. For me it is an interesting result and valuable contribution to the BAI community (at least for fixed-confidence BAI), since it has a wide range of practical usage thanks to FW and in the mean while avoids the $\beta$-tuning issue for top-two algorithms. The technical novelty is also generally sound (please see below for some technical comments).

Some technique-related comments:
- Line 240: What if $N_k(t) = 0$?
- Line 990: How do we know that $\pi = \hat{\mu}^{t-1}\in \Lambda$?
- Line 1012: $\mu$ needs to be in $\Lambda$ right?
- Proposition 3: $F$ is Lipschitz with respect to which norm?
- Line 1171: Are you sure about the last inequality $||z-x||_{\infty}^2$?
- Line 1252: $z_k(t)$ -> $z_k(s)$.
- Line 1277: It seems that $\Psi$ is exponential in the number of arms $K$? Could it be a problem when dealing with many arms?

Overall, I vote for accept for this paper. Please see the next section for major questions and minor comments.

limitations_and_societal_impact: Societal Impact: not applicable

Major questions:
- I think it could be helpful to compare the time complexity of the FW update against its counterpart in other algorithms (for example, you can compare the average execution time of different sampling rules), as in my opinion this is one important reason why we are interested in FW here. 
- I am quite curious about the forced exploration phase, do you think it is possible to get rid of it?

Minor comments:
- What is LT-H?
- It would probably be better to include LinGapE (Xu et al., 2018) and RAGE (Fiez et al., 2019) as well in the experiments for linear BAI.
- Probably better to also include top two algorithms (Russo, 2016; Qin et al., 2019; Shang et al., 2020) in the experiments (in particular for unstructured bandits).
- It would probably be better to place the acronyms (like T-D, D-C, etc) directly into the plot captions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies pure exploration in the fixed confidence setting for generic stochastic bandits. They develop a new algorithm based on Frank-Wolfe, give conditions under which it matches the lower bound (asymptotically as delta goes to 0), and empirically evaluate it. 
main_review: The paper argues that most prior work solves the optimization problem (1) at each round, which can be computationally expensive. To address this, they give an algorithm that just takes one step of Frank-Wolfe at each round instead.

I found the assumptions 2 and 3 difficult to interpret. I think it would be useful to give more explanation in the main text on when these conditions hold, especially assumption 2. Given that prior work (e.g., [9]) has already solved this problem in such a generic setting, it would be useful to understand how restrictive assumption 2 is to compare to prior work. Are these assumptions strong enough to make the sample complexity result substantially weaker than prior work? Or are these assumptions relatively benign?

The authors say in lines 100-106 that the work of [29] is quite similar to the current work, except that LMA does worse empirically. Is this the only advantage of the current paper, superior empirical performance? I think it is important to distinguish the current paper from prior work more clearly so that the contribution is clear.

The authors write in line 56 that inner optimization problem in (1) can be hard. This was a bit unclear to me. Do they mean it is NP-hard or just intensive? Could examples be provided?

Building on this, if the main advantage of the current work is being computationally lightweight, it would be useful to demonstrate this in experiments or examples of settings that are difficult for prior algorithms. Are there settings where the proposed algorithm does well, but existing algorithms do not scale to them? Essentially, are there problems that the current algorithm solves, but prior algorithms do not?


After the rebuttal: thank you for the helpful clarification. I increased my score.

limitations_and_societal_impact: I forsee no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the best arm identification problem in the fixed confidence setting. Frank Wolfe algorithm is employed to solve the minimax problem for the optimal arm allocation. They establish the asymptotic optimality of their methods in a wide class of pure exploration settings. The sample complexity is empirically confirmed in the numerical simulations.
main_review: Concern on the originality :
The lower bound of MAB pure exploration is proved in  [21], and most existing papers solve a lower bound optimization which is introduced in equation (1) at each round t. Such algorithms achieves the asymptotically optimal, but solving (1) at every round is  computationally inefficient.
In this paper, instead of solving (1) in each round as in [21], they propose an online iterative method to converge the optimal allocation of arm pulls \omega^*.
This concept is already discussed in the work of [39], which performs an online lazy mirror ascent to solve a lower bound optimization (1). Their method can avoid computing (1) at every round since it is sufficient to compute at each steps only a subgradient to maximize the concave but not smooth objective function over the simplex.

The addition by this paper is to connect FW-algorithms with pure exploration problems for solving non-smooth functions. There is a surprising work of [42] that can be applied to solving non-smooth objective functions; this enables us to leverage the analysis of the Frank-Wolfe algorithm in pure exploration bandit problems.

To sum-up, it is not so clear that this paper’s contribution is significant. The drawback of the computational issue of [21] is already discussed in [39]. Best Challenger type algorithm is also not new, which was already introduced in [21].  Analysis for  non-smooth objective function by FW-algorithms is given by [42]. This paper combines those existing work’s ideas but it is not really clear which part is the novel developed and what is the difficulty to  leverage them. 

[21] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Proc. of COLT, 2016.

[39] Pierre Ménard. Gradient ascent for active exploration in bandit problems. arXiv, 2019.

[42] Sathya N Ravi, Maxwell D Collins, and Vikas Singh. A deterministic nonsmooth frank wolfe algorithm with coreset guarantees. Informs Journal on Optimization, 2019.

============
Thank you for your feedback,  my concern is clearly addressed by author's response.

limitations_and_societal_impact: This paper is well-written and self-contained. However, it would be great if the authors clarify the main challenges in more detail.
review_title: null

Meta-review: This paper has initially received mixed reviews, with some reviewers expressing concerns about the significance of the contribution. These concerns were sufficiently addressed by the authors' response, and, after a short discussion, all reviewers agreed that the paper is strong enough for publication at the conference. I concur with this assessment and recommend that this paper be accepted.
Decision: Accept (Poster)