Summary
The paper delves into the study of the 'Explore Then Commit' (ETC) policy, where the algorithm is divided into two stages: exploration and commitment. During exploration, the algorithm is permitted to switch actions, while the commitment phase restricts the algorithm to pulling only the commit arm. The primary objective of the algorithm is to reduce the expected commit time, denoted as $T_c$, and ensure that at time $T_c$, $\hat a \neq a^*$ holds true with a probability of $O(1/T)$.
Three variations of the ETC policy are introduced in this paper: EOCP, EOCP-UG, and KL-EOCP.
For EOCP, it's structured for a known gap setting, achieving regret in the order of $2\log T/\Delta_i$. The authors assert that this outcome is asymptotically optimal. However, this claim appears to be incorrect. As per reference [On Explore-then-Commit Strategy], the asymptotic optimal regret for a known gap should be $\log T/(2\Delta_i)$. Furthermore, the authors have not discussed this setting's reference in a comprehensible manner. For instance, DETC with a known gap achieves exact asymptotic optimality.
For EOCP-UG, the authors show that it achieves asymptotic optimality with a commit time of $\log^2 T$.
As for KL-EOCP, it necessitates knowledge of certain parameters for the design of the pre-determined stopping time.
In summary, the claim that the EOCP and KL-EOCP algorithms are asymptotically optimal appears to be overstated. The upper bound for EOCP-UG and its associated lower bound is the same as DETC. As for the lower bound, the assumption seems excessively strong. The authors did not clearly indicate whether algorithms must adhere to the equation given in Line 241.
Primarily, this paper targets two-armed bandit problems, focusing on asymptotic regret. However, I am intrigued by the finite-time bound. I would appreciate an algorithm that is not only asymptotically optimal but also demonstrates a robust finite-time bound. In addition, the paper only considers a fixed horizon T setting. What about the case with an unknown $T$? From my understanding, DECT and its variant [Almost Optimal Anytime Algorithm for Batched Multi-Armed Bandits], are also suitable for an unknown T setting. Furthermore, the necessity of the assumption in Line 141 is not clearly articulated and requires clarification.
Regarding experimental results, the performance of ETC and DECT presented in this paper is inconsistent with previous papers. This discrepancy might be due to parameter adjustments in these algorithms. I would appreciate seeing empirical results with parameter tuning for both ETC and DETC.
----
# At the end of discussion phase
The authors fail to address my primary concerns. Below, I elaborate on these issues:
1. Line 174 of the manuscript asserts that in the pre-determined setting (where the gap $\Delta$ is known), $\frac{2\log T}{\Delta}$ is asymptotically optimal. This claim is misleading. Algorithm 4 in reference [21] shows that in the pre-determined setting with $T_c = \log^2 T$, there exists an algorithm with a regret of $\frac{\log T}{2\Delta}$. Moreover, the known lower bound (Theorem 6 in [20]) for known gap setting is $\frac{\log T}{2\Delta}$. Therefore, stating $ \frac{2\log T}{\Delta}$ as asymptotically optimal is an overstatement.
In their response, the authors attempt to equate the lower bound of the pre-determined setting with the lower bound of the known gap setting in the ETC strategy [20]. This comparison is problematic and has the potential to mislead other readers. Specifically, Table 1 in the authors' response erroneously claims that $4\log T/\Delta$ is the lower bound for the known gap setting, whereas this is actually the lower bound proven for the **unknown gap** setting in Theorem 4 of [20]. Additionally, they assert that $2\log T/\Delta$ is the lower bound for the known gap and pre-determined settings, which contradicts Algorithm 4 in [21] that shows regret $\frac{\log T}{2\Delta}$.
2. As I pointed out in my initial review, DECT [21] (Algorithm 5 and 2) can be directly applied to the unknown gap setting. The results for DECT in an unknown gap setting are identical to those presented in this paper.
Given the paper's significant overstatements and the paper's limited contributions, I am revising my score from 4 to 3.
Strengths
In this paper, the authors propose an algorithm called Explore Optimistically then Commit Pessimistically (EOCP) to solve the Regret Optimal Best Arm Identification (ROBAI) problem. It first uses an optimistic modified UCB algorithm to explore actions with a slightly larger exploration function , and then commits to actions according to a pessimistic LCB algorithm when the exploration ends. The main contributions include designing new stopping rules with both pre-determined stopping time (vanilla EOCP) and adaptive stopping time (the EOCP-UG variant), which provably balance the trade-off between regret minimization and optimal action identification
Rating
3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
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.