Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the problem of best arm identification in the fixed budget setting. The authors introduce a notion of global optimality specific to a prescribed complexity measure $H$. They establish a characterization of the optimal rate fo such notion via the rate $R^{go}$ (see Theorem 1) and provide Algorithm 1, which samples by tracking an $\epsilon$ solution of the optimal allocation that achieves $R^{go}$. While algorithm 1 remains infeasible since it requires accesss to unavailable information, the authors propose weakened characterizations of the optimal rate $R^{go}$ via the rates $R^{go}_B, R^{go}_\infty$ (See Theorem 2). These new rates take into account the fact that an algorithm throughout its learning may not have information about future empirical mean estimates of the arms. Then the authors provide Algorithm 2 (Delayed Optimal Tracking) which enjoys a guarantee that matches the lower bound of Theorem 2 (see Theorem 5 and Theorem 7). The proposed algorithms so far do require solving a nontrivial optimization problem. To remedy this, the authors propose an approach that uses a neural network to learning the optimal solution of such optimization problems, and provide along with that numerical experiments to consolidate their approach.

strengths_and_weaknesses: Strengths


- This paper is well written paper with solid theoretical results, good literature review, and a clear presentation. This makes the paper easy to follow even though it is quite technical.
- The problem considered by this work lacks considerable understanding in the literature and as highlighted by the authors remains poorly understood. Therefore, the theoretical results of this paper, especially the characterisations of the lower bound in section 2 (Theorem 1 and 2) appear to be worthwhile contributions in my opinion that further our understanding in the fixed budget setting.
- It is really appreciated that that the authors did not stop at providing a perhaps theoretically good, but computationally infeasible algorithm. Instead the authors proposed a neural networked based learner to remedy this challenged and accompanied that with numerical experiments.


Weaknesses

- I am not fully convinced about the discussion in section 1.1. (lines 42-51) that one has to choose a complexity $H(\cdot)$ to characterize optimality in the fixed budget setting. I do not have an answer but at the same time this opens the question of how one should choose the the complexity measure $H(\cdot)$ which I think the author could clarify further. Is there a better complexity measure? are they even comparable in some sense?
-  Another weakness of the current work is that the proposed algorithms whether they rely on neural networks or not remain largely impractical (the authors also highlighted this).


questions: 
- How could one choose the complexity measure? The authors claim that one cannot obtain an instance specific lower bound as in fixed confidence setting, which I am not convinced of. However, if this is the case, does this suggest some sort of trade-off when choosing what complexity measure to focus on? Could the authors comment on this?
- By now we do have practical algorithm for the fixed confidence setting. Is there a big gain from tracking an allocation determined from solving the fixed budget lower bound instead of the fixed confidence lower bound? In Kaufmann et al. it has been shown that in the two armed bandit for the class of gaussian distributions the complexity measures that arise from both problems are the same, so perhaps there is no gain, and one could simply track allocations from the fixed confidence setting. Could the authors comment on this?
- As far as I understand the results are only valid when $\mathcal{Q}$ is restricted to the class of Gaussian distributions or Bernoulli distributions but not both at the same time. Could the author comment on this?

limitations: I think the authors have properly addressed the limitations of their work both theoretically and practically. The work remains theoretical at large, so I don't see any potential negative societal impact or ethical issue that apply.
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: It is known that the probability of error in identifying a best arm in a fixed-budget $T$ is bounded by $\exp(-RT/H)$ where $H$ is a complexity term and $R$ quantifies the rate of decay as $T \rightarrow \infty$. This paper describes methods to possibly attain the best possible rate for the hardest instance in a given class, i.e., minimax optimal rate, which is called $R^{go}$. First a lower bound $R^{go}_B \leq R^{go}$ is described, next an algorithm with error rate $O(R^{go}_B - \epsilon)$ is described. Nevertheless, this algorithm assumes an $\epsilon$-optimal solution to an intractable sup-inf optimization and thus cannot be implemented. Consequently, a heuristic $R^{go}$-tracking algorithm using neural network (TNN) is described and compared to other methods in experiments.
strengths_and_weaknesses: Obtaining good bounds on the optimal minimax rate has not been considered a lot in the existing literature, possibly because it is a hard resource allocation problem. Viewed in this light, the problem is similar to dynamic programming. However the rate $R$ is defined when the budget $T \rightarrow \infty$, and this brings it closer to prior work in best arm identification. Overall, the task considered in this paper is novel. 

The claims made in the paper seem to be technically well-supported. However the same cannot be said about the remarks. For eg, remark 1 says $R^{go}$ may be 0. But shouldn't the choice of $\mathbf{Q}$ ensure at least one of the divergence terms is positive, and thus the outer sup over $\mathbf{r}$ would make the objective positive? Remark 2 mentions that a $P$ may be in $\mathcal{P}\setminus \mathcal{Q}$ without discussing the possible zero denominator in the KL divergence. Remark 3 mentions no algorithm can be better than DOT but I think the statement is only true for algorithms that are restricted to operate in a batched manner with equal-sized batches. 

These comments are to the best of my understanding and I may have missed something as I felt the paper was generally quite hard to read. I do not understand the description in the introduction and section 1.1 about fixed budget BAI being impossible in an instance-wise optimal manner. For eg, the probability of error of successive rejects algorithm is at most $\exp(-T/(\log(K)H))$ which is optimal in order as described by Carpentier and Locatelli (2016). At some places, notation could be recapped to aid readability. For eg, in Theorem 2, it could be recapped that the domain of each $\mathbf{r}_i$ is all possible collections $(\mathbf{Q}_1, ..., \mathbf{Q}_i)$ to emphasize the batched nature of algorithms to which the lower bound applies. In the proof of Lemma 10 it will be better to describe the proof for the base case. The proof of Theorem 2 could be made easier to read by adding more explanations for the notation. It is not clear to me what $\mathbf{r}_1(\mathbf{Q}^1; \pi, \epsilon)$ means.

While the paper tries to address a hard problem, I believe some of the arguments need to be made more readable and explained bette for it to have a much higher impact. 
questions: * Algorithm 2 describes one of the key contributions by introducing the "stored" queue of means but I'm unable to fully understand. In Algorithm 2 pseudocode the input is assumed to be an oracle that can solve for $\mathbf{r}^{B,*}$. From eq (3) the input to this optimization is the $\mathbf{P}$ and $\mathbf{Q}^B$ that attain the inf. 

But in line 5 the allocation $\mathbf{r}^*_{b-K}$ is computed. How this step can be realized without knowing all the elements of $\mathbf{Q}^B$ which include $(\mathbf{Q}'_{b-K+1}, .. , \mathbf{Q}'_B)$ is unclear. 

* It seems when $B=1$ the quantity $R^{go} = R^{go}_B$ and for $B > 1, R^{go}_B < R^{go}$. Then why are we interested in $R^{go}_\infty$, in the sense that it is going farther from the true oracle rate? Possible related, why is eq (21) true?

* How sensitive is the choice of $N^{true}$ and $N^{emp}$ for the performance of TNN algorithm?
limitations: None noted
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper characterizes the optimal rate of error in the fixed budget best arm identification setting. It introduces two tracking algorithms as an endeavor for achieving the best error rate; the first algorithm is not practical but it theoretically achieves the optimal rate. The second algorithm solves a simpler optimization problem but it is computationally expensive. 
strengths_and_weaknesses: **Strengths*
1. The problem considers an important open question in the BAI literature, namley FB BAI.
2. The proposed algorithms seem to achieve the oracle rate in the experiments.


**Major comments**
1. The positioning of the paper seems inadequate. Carpentier and Locatelli (2016) already discussed the optimal rate for FB BAI problems. It could improve the paper to discuss how the work is different than theirs. Line 55 seems to only mention the fact that the constants in Carpentier and Locatelli (2016) are loose. How does your bound $R^{\text{go}}_{...}$ compare to theirs as it does not have a closed form?
2. The difference between FC and FB settings is an essential motivating point for designing FB BAI algorithms as there are already several near-optimal FC BAI algorithms in the literature. However, the discussion starting at Line 32 (and Appendix D) does not convey the message and needs clarifications. For instance, what is "instant-wise optimal"? Following up, how did you get the expression after Line 422?
3. A concrete example for Remark 1 could explain what "reasonably" mean therein.
4. Remark 2, Line 167: Why does $R(\pi)$ become zero otherwise?
5. How can we let $B\to\infty$ while it seems $B$ is the integer number of batches which needs to be $B\leq T$ ?
6. I could not understand the crux of Algorithm 2. Why is this algorithm called "delayed" ?

**Minor comments**
1. Submiting the code could improve the reproducibility of the results.
2. Lin 159: It seems like $r^*(Q...$ should be used instead of $r(Q...$
3. Line 197: Do you have the analysis showing that ignoring the last rounds does not hurt the results?
4. Line 204: what does "open $n_{b,i}$"  means?
5. Line 222: Is it $B \mathbb{N}$ instead of $b\in \mathbb{N}$ ?

questions: 1. Considering the similarity of your results to the one in Kaufmann et al. (2016) ($\sup \inf \left(H(P)\sum r D(Q \| P) ... \right)$ is first introduced in there), how is your analysis are different than them?
2. How do your bounds compare to Carpentier and Locatelli (2016)? (See Major comment 1)

Please also see the "Major comments" section above.
limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies best arm identification (BAI) under fixed budget. Two rates (of lower bounds) $R^{\text{go}}$ and $R^{\text{go}}_\infty$ are derived, where a matching algorithm for $R^{\text{}go}_\infty$ is proposed despite computationally not trackable. Then a heuristic approach is proposed to empirically match $R^{\text{go}}$.
strengths_and_weaknesses: (+) This work studies lower bounds on relatively less studied BAI with fixed budget. Since there are not many works in this area, these results are useful and can guide the design of new algorithms.

(+) A lower bound matching algorithm for $R^{\text{}go}_\infty$ is proposed. Though still can be improved by reducing computationally overhead, it is still inspiring for the problem at hand.

(-) Successive halving (SH) is not included in numerical tests.
questions: See weakness.
limitations: This work is most on maths and algorithm perspective, its social impact depends on the application of the proposed approach, which goes beyond the scope of current paper.
review_title: null

Meta-review: metareview: This paper had very mixed pre-rebuttal scores, fairly detailed reviews, and significant author/reviewer interaction.  Following all of this, the reviewers are now generally positive, with several of the initial concerns being resolved.  One of the scores remains below the threshold, due to certain claims and statements being too vague, and insufficient distinction between fixed confidence and fixed budget.  However, another reviewer responded by noting that the distinction is generally clear from existing works (e.g., [a]).  

Since this remaining concern does not appear to be a deal-breaker, I believe that acceptance is the correct decision.  However, the authors should very carefully modify the paper according to the reviewer feedback, and be extra careful of unclear statements such as those pointed out by Reviewer BbC9.

[a] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. JMLR, 2016.
confidence: Less certain
Decision: Accept