Non-Asymptotic Analysis of a UCB-based Top Two Algorithm

Summary

In this paper, the authors proposed a new UCB-based Top-Two algorithm (TTUCB) for the best-arm identification problem (BAI) and derived a non-asymptotic upper bound on the expected sample complexity holding for any instance having a unique best arm. The authors also demonstrated that the TTUCB algorithm achieves competitive empirical performance compared to other algorithms, including some existing Top-Two methods.

Strengths

There have been some existing works that proposed top-two algorithms and analyzed the expected sample complexity for vanishing error level $\delta$, i.e., $\delta \to 0$ (asymptotic upper bound). However, this work proposed a new top-two algorithm (TTUCB) and provided a non-asymptotic upper bound on the sample complexity, i.e., a bound that holds for any error level $\delta$. The main (and new) contribution of this paper is to provide analytical techniques to obtain a non-asymptotic bound for the expected sample complexity for the TTUCB.

Weaknesses

However, this paper contains quite many weaknesses as follows. + The tightness of this bound is not verified in this paper, especially for non-vanishing $\delta$. + The obtained non-asymptotic upper bound in Theorem 2.4. does not match the lower bound (Lemma 1.1) as $\delta \to 0$, which shows that the non-asymptotic upper bound is not tight enough at small $\delta$. Note that Theorem 2.3 shows that TTUCB is $\beta$-optimal as $\delta \to 0$. + In the moderate regime $(\delta=0.1)$, the experiment (see Fig. 1) shows that the TTUCB algorithm can be better or worse than other existing ones. For example, in Fig. 1a, TTUCB looks worse than T3C although it is better than the others. Hence, it seems to me that although other existing algorithms are developed for $\delta \to 0$, they can be better than your algorithm (i.e., TTUCB) as moderate $\delta$.

Questions

+ Why don't you compare the performance of TTUCB with the non-asymptotic upper bound in Theorem 2.4 to check whether this bound is tight or not at different values of $\delta$? + From my second comment in the Originality section, what is the motivation for developing TTUCB for non-vanishing $\delta$? Why don't we perform non-asymptotic analysis for the existing top-two algorithms? Did you mean that you would like to develop a new top-two algorithm (more specifically, TTUCB) such that the non-asymptotic analysis for the upper bound can be performed easier than the others? + What is the main challenge when changing an asymptotic upper bound to a non-asymptotic one? More specifically, why is Theorem 2.3 optimal, but Theorem 2.4 not optimal as $\delta \to 0$?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

This is a theoretical work. The authors already finished the checklist as well as stated the limitations of theorems and results.

Summary

This paper presents a non-asymptotic upper bound on the expected sample complexity of a TT sampling rule-based algorithm for any error level. Numerical results also verify the performance of TTUCB. This is nice work

Strengths

1. The paper is well-written and organized. The insights behind the main results are well-presented. 2. The tracking rule is simple and easy to implement. 3. I appreciate that the authors include several simulations.

Weaknesses

One weakness is that there is still room for further improvement in the bound.

Questions

1. Any comments on how to choose the function $g_u(n)$? Are there any required properties? 2. Can you provide any suggestions on how to choose $\beta$ in practice?"

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Yes

Summary

The main objective of the paper is to establish the first non-asymptotic bound on the expected sample complexity for a Top two sampling policy in the context of best arm identification. To achieve this, the paper introduces a novel algorithm called TTUCB, which is proven to be $\beta$-optimal in asymptotic scenarios and also satisfies a non-asymptotic upper bound. This upper bound is compared with the existing upper bounds of established non-Top two algorithms. The paper supports its claims with synthetic simulation experiments. One notable contribution of the paper is the development of a generic framework that enables regret minimization algorithms to effectively tackle the best arm identification problem while providing optimal guarantees. Additionally, the paper offers guidelines on how other regret minimization algorithms can be adapted to choose a leader at each round. Overall, the paper provides significant insights into the problem of best-arm identification and presents a promising algorithmic solution along with empirical evidence to support its efficacy.

Strengths

The paper demonstrates exceptional writing, with clear claims and well-defined objectives. It successfully fills a significant gap in the literature by addressing the challenge of providing non-asymptotic guarantees for Top-two algorithms, resulting in original and valuable contributions to the broader bandit literature. The problem formulation is thoroughly justified, establishing a solid foundation for the subsequent theoretical results. The discussions on the theoretical guarantees of the proposed TTUCB algorithm are insightful and comprehensive, effectively identifying areas for potential improvement. Additionally, the paper highlights the low computational complexity of the approach, enhancing its practical applicability. The upper bounds achieved by the proposed algorithm are comparable to those of well-established methods in the field, as discussed aptly within the paper. By providing relevant comparisons, the paper strengthens the credibility and applicability of its results. Furthermore, the paper successfully contextualizes its work within the broader scope of the bandit literature, illustrating the connections between the theoretical analysis and the use of regret-minimizing algorithms in the best arm identification problem. This contextualization is particularly valuable as it addresses a scenario that differs from the traditional exploitation-exploration trade-off associated with regret minimization. Overall, the paper stands out for its clarity, strong theoretical discussions, well-justified approach, and relevant connections, making it a valuable contribution to the field of bandit problems.

Weaknesses

One potential weakness is the tightness of the upper bound provided in the paper. The proposed upper bound incorporates various parameters and constants. While there is a comparison with the upper bounds of other algorithms, it remains uncertain whether this upper bound represents the best achievable result for TTUCB or Top-two algorithms in general. Further exploration into the tightness of the upper bound would contribute to a more comprehensive understanding of the algorithm's performance. Another concern is the exclusive use of synthetic data in the experimental setup, without considering real-world datasets. It would be beneficial to address the potential challenges and limitations of applying the proposed approach to real-world datasets. Discussing any potential issues related to data collection, noise, or other factors specific to real-world settings would enhance the paper's practical applicability and broaden its impact.

Questions

1) Could you provide more details on the challenges encountered within the proof technique that led to the decision of adopting a tracking approach instead of randomization in TTUCB? It would be helpful to understand the specific difficulties that arose and how they influenced this decision. 2) Additionally, has there been any simulation-based evidence to demonstrate the comparative performance of TTUCB using tracking versus a randomization-based approach? It would be valuable to assess the effectiveness of TTUCB in comparison to algorithms utilizing random

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors talk about the limitations and places of potential improvement of the work. Societal impact is not discussed.

Summary

The authors consider the problem of best-arm identification in the unstructured multi-armed bandit problem. More precisely, they study the problem in the fixed-budget setting in the moderate confidence regime. They propose a top two algorithm based on UCB which they call TTUCB and establish that the algorithm is asymptotically $\beta$-optimal. Here, by $\beta$-optimal, the authors mean that the algorithm samples sub-optimal arms optimally under the constraint that the best arm is sampled a proportion of times that is fixed at $\beta$. More importantly, they also provide a non-asymptotic guarantee for their algorithm that is valide for all confidence levels. The authors complement their theoretical findings with empirical results.

Strengths

- Overall, the paper is well written and easy to follow. The related work is well discussed and the proofs appear to be sound to the best of my knowledge. - The non-asymptotic study of best arm identification in the fixed confidence setting is a fascinating problem and remains largely unexplored. The authors provide a non-trivial contribution to this problem by shedding some insight into the non-asymptotic behaviour of a UCB-based TOP TWO algorithm. - The proposed algorithm TTUCB seems to enjoy the best non-asymptotic guarantee up to universal constants universal constants.

Weaknesses

- The theoretical results are limited to the case of Gaussian arms with known variances. Moreover, The authors only provide a algorithm that is asymptotically $\beta$-optimal but not asymptotically optimal. This is somewhat unsatisfactory! - The authors address the non-asymptotic behaviour of best-arm identification but do not provide any non-asymptotic lower bound. As such it is unclear to me what is the best non-asymptotic bound. In fact, when the authors compare the different bounds, I believe they should also clarify (in the table) that TTUCB has an additional linear dependence on the number of arms $K$ at the finite confidence behaviour. - The authors could provide experiments which exhibit more the finite confidence behaviour of their algorithm in contrast with other algorithms. For instance, experiments that show how the sample complexity varies as $\delta$ varies.

Questions

- In Lemma 3.1, the definition of $D_0$ is not given which, according to Appendix D.2, is equal to $(1+\varepsilon^2)/\beta^2$. My first comment is that this needs to be precised in the statement of Lemma 3.1. Secondly, if you were to adaptively seek to achieve the optimal allocation with $\beta^\star$, then $D_0$ is not anymore a universal constant and might depend in a non-trivial way on the problem instance $\mu$, in which case, your proof might not work to obtain a non-asymptotic guarantee. Would this be a limitation of your proof techniques when trying to attain the optimal constant $T_\star$? I am not sure using IDS might work either. Can you comment on this? - The result of Lemma 3.1, appear to be very specific to the Gaussian case, can the author comment on how can this generalize to the general case? - The authors mention that $ T_{1/2}^\star(\mu)\le 2T^\star(\mu)$ in the worst case, can you comment on how tight is this bound? Also according to your experiment it seems TTUCB outperform asymptotically optimal algorithms like track-and-stop and FWS. Does this mean that in the experiment you considered, $T_{1/2}^\star(\mu)$ and $T^\star(\mu)$ are roughly the same? Can you run your experiments on a more challenging example where $T_{1/2}^\star(\mu)\approx 2 T^\star(\mu)$? - In the experiments section, the authors present plots in a scenario where $\delta=0.1$. Why is this value of $\delta$ considered to be in the moderate regime? Is there a clear definition if what we refer to as moderate regime? shouldn't this depend on the number of arms $K$?

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

I believe the authors have discussed the limitations of their work accordingly.

Thanks for your response.

Thanks for addressing my questions and confirming my understanding of your results. I have now revised the score I gave from 6 to 7. Regarding the moderate regime definition, it would be nice to provide further discussion and intuition on this in your paper. At an intuitive level, it seems to me that if $K$ is too large, than the limit that defines the moderate regime (whatever that is) becomes smaller. For the new numerical results you provided, $K = 35$, which to my intuition means that $\delta = 0,001$ is still considered within the moderate confidence regime. This would explain why TTUCB is performing better than track-and-stop. It would be interesting to find a regime of $K$ and $\delta$ where track-and-stop outperforms your algorithm TTUCB, if it's at all possible. This would mean, at least experimentally, that an algorithm that is both asymptotically optimal and enjoys a non-trivial non-asymptotic guarantess is still an open question. I would be happy to hear your thoughts on this.