Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies multi-armed bandits when there are a large number of arms, but when a constant
fraction of the arms are optimal. The paper studies methods for cumulative regret in the fixed
horizon setting and best arm identfication (BAI) in the fixed budget setting. In the former, they
describe an UCB-style algorithm which knows this constant fraction (p*) and bound its regret; they
complement this with a lower bound and an impossibility result which states that p* is necessary. In
the latter, the describe a successsive halving style algorithm and show that it nearly matches a
lower bound.

While I do have some reservations about the set up and the motivation, my overall perspective is
quite positive. The main results (theorems 1, 2, 4, 5) build on known techniques, but there is
also a reasonable amount of new ideas. While I did not have time to check the proofs, the proof
intuitions make sense and the results are believable. The paper is also well-written.

main_review: - In my opinion, the main shortcoming of the paper is that the setting lacks practical motivation.
  This, in and of itself is not a problem (e.g. K-armed bandits are rarely used in their simplest
  form in practice, but the intuitions and proof ideas have been used to study richer feedback
  models, such as linear, X-armed, and GP bandits which are used in practice). Unfortunately, I
  don't see a natural extension of this setting to richer feedback models. It would be helpful, if
  the authors can discuss how their setting and ideas can be enhanced in future work which might
  consider more practical settings, either using such richer feedback models or otherwise. 
    - The motivating example the authors use in lines 30-33 is that there might be many arms in
      image classification, personalized medicine, or hyperparameter tuning. But the arms in these
      applications can be featurized, and the usual approach for tackling such a large number of
      arms is to use a richer feedback model so that the regret bounds scale with the complexity
      of the model and not the number of arms. It is also unreasonable to assume that a constant
      fraction of arms in these applications will be exactly optimal (usually there will be several
      good arms, but their means may not be the same), let alone that p* will be known ahead
      of time.

- Please comment on extending Algorithm 1 to the any-time setting? It appears that sampling of the
  initial pool can be handled by slowly admitting more arms after several rounds, but I am not sure
  if the confidence intervals would still work. 

- The UCB used by the authors in (2) is reminiscent of the UCB used in the following paper and is
  probably worth citing.
    Jamieson et al, "lil’ UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits"

- Can you explain the proof intuition in Theorem 3?

- Have you explored other conditions, besides the constant p* fraction, under which Algorithm 2 (or
  any other sensible algorithm) will return a ``good'' arm?
    - For instance, there are several arms, but you only need to find an \epsilon optimal arm or
      an arm whose mean is in some top percentile. 

- The successive halving strategy that the authors have used for the BAI setting was first
  introduced by Karnin et al, "Almost Optimal Exploration in Multi-Armed Bandits" and should be
  cited.


-------------------------------

Post-rebuttal: Based on the authors' reply, I have increased my score to 8. While I am less convinced about the practical motivation given by the authors and the results for the cumulative regret problem, I think the results for BAI are potentially interesting and the abstraction could be useful for some follow up work. While the proofs fundamentally build on well-known techniques, they also use some new ideas.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers infinitely many armed bandit problems where the significant portion is optimal. In particular, p* fraction of the arms are optimal. 
This paper considered two objectives (total reward optimization and best arm identification). For the first objective, the paper proposes a version of UCB algorithm with a slightly smaller confidence bound (sampling UCB, alg 1) that matches lower bound up to O(log(1/Delta)), whereas for the second objective the paper proposes a version of elimination (Elimination, alg 2) that matches lower bound up to O(log Delta^{-2}).

This paper is mainly theoretical and the assumption of many optimal arms is more restrictive than the existing literature of many-armed bandit problem (without empirical justification). I think the algorithms proposed in this paper is novel and the paper is marginally above the acceptance threshold as it is of theoretical interest of the readers. Having derived corresponding lower bounds based on change-of-measure discussion is also nice.
There can be some space for improvement on the structure of the paper. It spends 5+2/3 pages before the main results. As a result, results of the simulation are not presented during the main paper.

After the discussion period:
I would not change my rating strongly (will keep WA). I think the paper is above the threshold.


main_review: * Major comments:

** Total reward maximization

Sampling UCB (Algorithm 1) first draws C log T/p* arms and apply a version of UCB algorithm with slightly smaller confidence bound (sqrt(log Ni/Ni)). Such a confidence bound sometimes yields UCB value of U_i(t) < \mu_i. However, given there are p* fraction of arms, there is at least one optimal arm with U_i(t) >= \mu_i. This trick reduces an O(log T) factor compared with standard UCB.
- Can you briefly discuss where the log(1/Delta) gap between upper and lower bounds? The lower bound looks reasonable given it took log T/Delta**2 to identify the optimality of arm and 1/p rate of finding the optimal arm.

** Best-arm identification
Elimination (Algorithm 2) first draws T/2 arms and then at each epoch it discards the lower half of them and adds some new arms of the same order. The algorithm is aimed to draw some optimal arm tilde(O)(pDelta^2T) times and adopts a polynomially decreasing size of epochs. The algorithm is different from successive rejection and is interesting.

** Comparison with other algorithms 
Can you compare the results here with similar work? For example, what kind of bounds can we obtain when we apply [39]?

** Simulation results:
It would be great if you briefly discuss the other algorithms in simulations. 

* Minor comments:

- The paper may rename algorithm 2 as it not only eliminates some of the arms but also adds new ones at each epoch.
- Can you motivate the problem setting (a many-armed bandit with p* fraction of optimal arms)? 
- Some of the equations referred in the main papers only appear in the supplemenatry materials. For example, Eq. (3).
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors consider the stochastic bandit setting considering a possibly infinite number of arms. They call p* the fraction of optimal arms and investigate both the cumulative regret minimization and the best-arm identification problems. For both problems they provide a lower bound and a solution matching the upper bound (up to log factors).
main_review: Authors consider the stochastic bandit setting considering a possibly infinite number of arms. They call p* the fraction of optimal arms and investigate both the cumulative regret minimization and the best-arm identification problems.

If compared to existing works, they consider a more general setting and the obtained results are stronger than the ones obtained in the existing simpler frameworks.

For the first problem they provide a lower bound argument and an algorithm matching the bound up to multiplicative log factor of order 1/\Delta. The algorithm requires the knowledge of p* as input parameter, this seems to be a limitation, however authors shown that knowing such a parameter is strongly necessary.

Similarly, for the best-arm identification setting they provide a lower bound and an upper bound to the probability of choosing a suboptimal arm. The upper-bound matches the lower one up to a log factor in the exponential. The proposed algorithm does not require the knowedge of p* as it was for the regret-minimization solution.

I would like to know which challenges/technical difficulties have been solved in the proofs if compared to existing works.
Secondly, I wonder if there are connections with the combinatorial bandit problem.
limitations_and_societal_impact: See above.
review_title: null

Meta-review: All reviewers are positive about this paper. The reviewers agree that the paper shows interesting new ideas in the results (especially ones for best arm identification). The reviewers also raise concerns about practical motivations and the presentation structure of the paper. I think the paper can benefit from improving in these directions.
Decision: Accept (Poster)