- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
The paper proposes TABLE, a metric-aware best-arm identification algorithm that exploits the Lipschitz structure of the reward function to reduce sampling effort. It groups arms into nodes, selects representative exemplars, and combines posterior-guided exploration, balanced sampling, confidence-based block elimination, and adaptive node splitting. The theoretical analysis establishes safe elimination of the node containing the optimal arm under a simultaneous confidence event and provides a finite-horizon exact-identification bound under additional structural and trajectory conditions. However, the validation of the overall identification guarantee remains incomplete, as the probability of failure of the required progress and terminal conditions is not generally bounded, limiting the strength of the unconditional guarantee.
Critical strengths
-
The paper develops a principled approach to best-arm identification that leverages Lipschitz continuity and representative arms to eliminate entire groups of arms rather than evaluating each arm independently. This is a meaningful contribution because it exploits the metric structure of the problem to potentially improve sampling efficiency.
-
The theoretical analysis separates safe block elimination (Prop 4) from exact identification and explicitly states the additional structural and trajectory conditions required for the latter. This transparency strengthens the analysis by avoiding overstated claims and clarifying the limitations of the proposed guarantees.
Critical weaknesses
As stated before, my major concern is that the misidentification bound depends on an additional trajectory event C_T, whose failure probability is not bounded under general conditions. Although the paper establishes safe block elimination, it does not demonstrate that the required progress and terminal conditions hold with high probability under the proposed algorithm. This limits the strength of the main theoretical guarantee.
Questions for authors
-
What is the practical value of the finite-horizon certificate when the probability of satisfying its additional conditions is unknown?
-
What happens when the optimal node survives but repeatedly fails the splitting eligibility conditions? I ask this because I have a confusion about the relation of the two events: (1) the event that optimal group is never eliminated and (2) the optimal arm is recommended.
-
If a simpler confidence-radius condition is sufficient for correct arm identification once the optimal arm is a surviving exemplar, why does Theorem 5 require the stronger gap condition involving the additional geometric term?
-
A minor question out of curiosity: What happens to the guarantee in the limiting case where all arms must be represented individually?
Response to the Review by Reviewer 3RE5
CW1
The distinction between block-certification validity and adaptive-trajectory guarantees is central to our theoretical contribution and is explicitly acknowledged in the paper. What we prove is under valid confidence intervals and Lipschitz continuity, TABLE establishes LCSu≤μ⋆(u)≤UCSu, ensuring that the optimal block is preserved on the confidence event, without requiring exhaustive arm-level sampling.`
We explicitly state Pr(a^T=a⋆)≤δ+Pr(CTc), rather than claiming an unconditional identification guarantee. Bounding Pr(CTc) requires additional assumptions on optimal-arm representation, split activation, adaptive allocation, and terminal sampling.
We strengthened the experiments with execution diagnostics covering refinement, elimination, persistent representation, ladder balance, and terminal sampling (In appendix). These results provide additional insight into TABLE's actual trajectories, although they do not establish bound on CT. We acknowledge that controlling the trajectory-failure probability would strengthen the identification theorem. However, this is a limitation explicitly identified by the paper, not a flaw in the block-certification result it proves. We respectfully ask that the established theoretical contribution be assessed within its stated scope.
Q1) The practical value of finite-horizon certificate is that it establishes precisely when exemplar-based block elimination can guarantee correct identification without exhaustively sampling every arm.
Q2) Survival of the optimal block and recommendation of the optimal arm are distinct guarantees.
Q3) Theorem 5 and Appendix B.4 establish two different guarantees, which explains the difference in their gap conditions.
The distinction is fundamental: certifying an entire block requires controlling geometric approximation error; selecting the best among sufficiently sampled surviving exemplars does not. The stronger condition in Theorem 5 is required for its stronger block-elimination conclusion, not because exact recommendation inherently requires the additional geometric term.
Q4) When every arm is individually represented, TABLE's guarantee reduces to the standard arm-level confidence-based identification setting.
1) Geometric approximation disappears. If every arm is an exemplar, the covering error is zero. Consequently, the block confidence scores reduce toLCSu=maxa∈C(u)(μa−ra),UCSu=maxa∈C(u)(μa+ra).2) Safe elimination remains valid. Under simultaneous confidence coverage, the optimal block is still preserved. No Lipschitz approximation is needed, since every arm is directly observed.3) Identification requires only statistical precision. Once all surviving arms are sufficiently sampled, the recommendation-only conditionΔmin>2rT(δ)suffices for exact identification on the confidence event.In limiting case, TABLE naturally recovers arm-level confidence-based identification.