Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes elimination rules that can be easily combined with existing fixed-confidence algorithms for pure exploration, both for sampling and stopping strategies. The benefits are improved performance in the nonasymptotic regime. The authors show a result that the elimination stopping results in eliminating pieces no later than the standard LLR stopping.
strengths_and_weaknesses: Strength is that the proposed strategy leads to improved empirical performance. The weakness is that the theory does not seem to be strong, at least in the current form.

The contribution is clear, but the details can be explained better. So, I would say that clarity is below expectation. Originality, quality, and significance is all mediocre (just around the bar).

My main complaint is that there is no 'provable' improvement of the proposed methods in mathematical analysis. I do not mean the proof for 'not worse', but a proof like 'a strictly upper bound can be achieved and it can make an orderwise difference in some cases'. Empirical evaluation shows that the empirical performance improvement can be better, but in my opinion, it is rather a minor improvement.

----
(after rebuttal) I have changed the score as the authors have addressed the concern.
questions: Theorem 2.6. I understand that with elimination stopping it is never worse, but it is not clear if it makes a meaningful difference. I was not able to pin down on exactly how (9) can be strictly better than (8). I don't have a good sense on whether $H^*(\theta)$ is related to $\min_{...} H_p(\omega,\theta)$ in (9). I'd like to hear from the authors on this. Without a careful comparison, I cannot say for sure that it is meaningful. To make a stronger argument, I would find a specific instance where (8) can be orderwise larger than (9) to showcase the real difference.

The explanation of reset times in Section 3.1 was not clear at all to me. What is the role of the resetting? It would  be beneficial if we have a protocol/pseudocode description of what we expect from existing algorithms and what we do for eliminating the pieces, side by side. Also, please provide a specific example algorithm where you show how elimination pieces at sampling can be combined.

How existing elimination strategies are not easy to extend to combinatorial settings: I think Successive Accept and Reject (SAR) was applied to combinatorial pure exploration in Chen et al., Combinatorial Pure Exploration of Multi-Armed Bandits, 2014. I would be surprised if one cannot apply SE/SAR style algorithms for the problem that the authors' are concerend?

I will adjust the score based on the feedback.

minor comments

* I would have one displayed equation or table or figure that compares LLR, full elimination, selective elimination like next to each other.
* In the end of section 3.1, “the reason for having different sets of active pieces for stopping and sampling is that it allows us to derive guarantees on expected stopping times. If one is only interested in high-probability results, it is possible to use the same set for both components.” ⇒ this is not immediately clear.
* Section 3.1's description can be improved. It would also be beneficial if we have a protocol/pseudocode description of what we expect from existing algorithms and what we do for eliminating the pieces, side by side.
  * Actually, it'd be better if there is a specific example algorithm where you show how elimination pieces at sampling is applied.
* It would be great if we know what stp and smp stands for in notations.
* definition of $\tilde{\mathcal{P}}\_t^{smp}$ : for the first line, did you mean to use $\alpha_{t,\delta}$ where $t$ is actually the most recent reset time j(t)? The current definition seems like it always computes $\overline{\mathcal P}\_t(i; \alpha\_{t,\delta})$ all the time anyways.
  * I also did not understand the purpose of this the reset times. why are we doing resets? is it because we will be discarding samples?
  * for reset times, are we using just the samples from the last block of time steps to compute $\overline{\mathcal P}$ or using entire samples ?
* Line 726, an union ⇒  a union 
* Line 738, we the following ⇒ the following 


limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work bridges the gap between elimination algorithms and fully adaptive algorithms for identification problems in bandits. One the one hand, the main strength and weakness of elimination algorithms are their high computational efficiency and large sample complexities, respectively. One the other hand, fully adaptive algorithms enjoy stronger sample complexity guarantees while being computationally inefficient. In this paper are designed fully adaptive algorithms that perform elimination. These algorithms are shown to get the best of both worlds, both theoretically and empirically.

strengths_and_weaknesses: Strengths:
- The framework has a broad range of applications: it covers among others the problems of gaussian bandits, top-k, thresholding identification for linear and unstructured bandits.
- On this general setup, this work successfully tackles the problem of designing strategies that are both fully adaptive and performing elimination.
- The experiments support the theoretical claims.

Weaknesses: 
- This paper could benefit from a better presentation: 
- It would be nice to highlight a pseudo-code of the algorithm designed.
- It takes a long time to get to the main theoretical results.
- The theorems are hard to parse without examples/instantiations.

questions: - In practice how does one modify an existing algorithm (say e.g. Track-and-Stop) to incorporate any of the elimination steps suggested in this work?
- Writing the infimum LLR in closed form is very illustrative. Are there settings where the quantities in the theorems are closed form? If so, would it be possible to add some more explicit statements?
- Are there original algorithms and new elimination counterparts of these for which the computational complexity can be computed? The claimed improvement on computational complexity feels very empirical, instead of being theoretically characterized.

limitations: I did not really find a clear statement about the limitations of the work. The authors state that the potential negative societal impacts of their work is N/A. This work is mainly theoretical, but it might still be valuable to mention how bandit algorithms are applied to the world and e.g. what could go wrong if the suggested algorithms are used.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary:  The authors propose a new algorithm design principle for elimination algorithms in the fixed-confidence, best-arm-identification setting with parametric distributions that modifies the usual stopping rule of track-and-stop-style algorithms (adaptive in their terminology).

Roughly, under an assumption that the parameter space of each alternative for each arm i (i.e. the parameters that would result in any arm other than i being the best) can be decomposed into a small subset of pieces that are easy to optimize over, the authors propose elimination of individual pieces. In contrast, the typical track-and-stop algorithm will continue until all pieces except for those belonging to a single action can be eliminated. This procedure can reduce the cost of checking the stopping rule, and is shown to have the same guarantees (correctness and asymptotic efficiency).

The authors then present sampling rule that also takes into account pieces that have been eliminated and show that, under a technical assumption, the new sampling rule does not degrade the sample complexity. Improved performance in both sample complexity and time complexity is shows experimentally.


strengths_and_weaknesses: While the writing was generally high quality, I found the overall presentation confusing and the theoretical results a bit underwhelming (though I didn't read the appendix, so it is possible the technical difficulties were larger than I thought).

First, I found the main ideas difficult to understand and had to work through section 2 a few times. I think the presentation could be improved if the section was restructured to highlight a cartoon of the original track-and-stop and introduce your new ideas an modifications. It wasn't immediately clear to me if your procedure would produce an action elimination algorithm or an adaptive algorithm. Beginning with the explanation that you are in the parametric setting and are modifying track and stop would help.

I also wish that the elimination sampling algorithm was presented more clearly, perhaps with pseudo-code (at least for your favorite instantiation of an adaptive algorithm). 

It might be good to give a bit more intuition about what "adaptive sampling" and "elimination" algorithms do and their differences, especially since there are several well known algorithms (e.g. LUCB, TS variant)) that don't fit into your two classes. Specifically, I found your "repeatedly test the correctness of every answer" confusing, and it would be probably clearer to describe how elimination algorithms work in phases/epochs. I might go so far at to argue that "adaptive" is a confusing choice, as elimination algorithms also change their sampling distributions as data are collected (albeit usually through eliminating actions). Perhaps phased / non-phased would be a clearer distinction.

Another very import distinction is that "elimination algorithms" are generally non-parametric, needing only some way to get finite-sample confidence intervals on the target parameters, whereas "adaptive" methods require strong parametric assumptions.

I wish there was theory showing improvement in the sample complexity, and I wish there was a discussion about the assumptions (specifically, an argument about why they should be necessary).

Other feedback:
line 137: bad grammar

questions: Can you provide some justification for your assumptions?Are there special cases when you can provably show an improved sample complexity?
limitations: I think a closer discussion about the assumptions is needed. Societal impact was not addressed, but I don't think it's necessary.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the problem of finding (or identifying) the correct answer to a specific question in a bandit scenario. Examples are what is the arm with the highest mean (best arm identification), or which arms have a mean larger than some specific value (thresholding bandits)? For this purpose, they revisit the algorithmic approaches based on log-likelihood ratio stopping, which are theoretically quite appealing but are oftentimes computationally expensive. Roughly speaking, these approaches stop as soon as there is an answer such that the alternatives to these answers are not plausible enough (measured in terms of minimal distance of log-likelihood ratio). Under the assumption that the underlying bandit problem scenario allows a decomposition of the possible alternative sets into smaller subsets (called pieces), the authors suggest two stopping criteria that have provably a smaller stopping time than the log-likelihood approach provided all are using the same sampling strategy. These stopping criteria are combining the log-likelihood ratio stopping approach with the non-adaptive elimination-based approaches by excluding pieces as soon as these are ``redundant’’ for the decision making. The authors show that for a couple of Gaussian linear bandit problems the assumption above is satisfied and the minimizer of the log-likelihood ratio can be efficiently computed on the corresponding pieces. Moreover, a bound in expectation on the resulting stopping times are shown, when the stopping criteria are combined with an efficient sampling rule.
Inspired by the suggested stopping criteria the authors derive a sampling strategy that is specifically tailored towards an early stopping of the former. The suggested approaches are investigated in an experimental study on synthetic data.
strengths_and_weaknesses: # Strengths

## Quite interesting topic
The underlying problem setting of general identification in bandits is a relevant theoretical problem scenario covering a range of practical applications and has already been investigated by a couple of several authors. The underlying research question of whether the fully adaptive approaches can be adapted such that they are computationally more efficient such as the non-adaptive elimination strategies is of utmost relevance for practical applications. The key challenge is of course to maintain the appealing theoretical properties of the fully adaptive approaches.

## Soundness
Overall, most of the results are sound as well as their proofs. I haven’t checked all proofs in every last detail but had a thorough look at the proofs of core results, which were fine as far as I can tell.

## Quality of writing/presentation
In general, the paper is well written. Although it is a rather technical paper the notation is well thought out.

# Weaknesses

## Modest theoretical contribution
Although the paper contains a fairly extensive appendix of proofs of the theoretical results, these are largely based on prior work and no groundbreaking new ideas come in, as far as I can tell. Therefore, I think the theoretical contribution of this paper is okay, but not significant.


## Vague description of eliminating at sampling 
The part about the suggested sampling strategy can be improved regarding its clarity. To be more precise, I would have appreciated if the eliminating at sampling approach would have been presented in form of a pseudo-code instead of a rather vague verbal description.


questions: - Are there bandit settings where it is not possible to decompose the alternative set into meaningful pieces? If yes, these should be mentioned in the paper.
 
- Of course, one might ask why the full elimination approach is considered at all, if it has such a high runtime, while the sampling complexity in the experiments is not significantly different compared to the LLR approach. In this way, the authors could save some space, which could be used to discuss other relevant things, e.g., describe how to apply the methods to other bandit settings than Gaussian linear bandits.




limitations: I would have appreciated if the authors would give a remark regarding a direct comparison of the actual stopping times, i.e. in which case it is possible and in which it is not. I think only for Theorem 2.6 it is.
review_title: null

Meta-review: metareview: This paper has initially received borderline scores: the reviewers appreciated the general algorithmic framework and the high technical quality, but some of them lamented the relative weakness of the contribution (in particular the lack of hard improvements over existing results) and pointed out that the presentation could use some improvements. Some of these concerns were addressed in a revised version of the paper and a series of well-written author responses, which eventually convinced several reviewers to raise their scores.

Eventually, all reviewers agreed that the paper is acceptable for publication. The authors are encouraged to do another pass of revision when preparing the final version of the paper, and take all the reviewers' comments into account in the process.
confidence: Less certain
Decision: Accept