- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies stochastic -armed bandits with exactly optimal arms. It presents the minimax rate for , based on a sharper analysis of subsampling followed by MOSS and matching lower bounds up to logarithmic factors. It also extends non-adaptivity lower bounds to regimes where optimal-arm sets necessarily overlap, under specified separation and horizon conditions.
Critical strengths
-
The sharper minimax characterization can give a polynomial improvement over existing bounds when almost all arms are optimal, e.g., when . This gives upper and lower bounds that match up to logarithm factors across the full range of .
-
The non-adaptivity result for overlapping optimal-arm sets is also an interesting contribution. It shows that adaptation can remain difficult even when instances necessarily share many optimal arms, extending beyond earlier constructions that are based on disjoint optima.
Critical weaknesses
My main reservation is the precision and clarity of the main-text explanations. The non-adaptivity claim on page 6 is too broad for comparable optimal-arm counts, although the formal statements do impose separation conditions. More importantly, the overview of Theorem 6.2 treats a pull-count bound on an event as controlling the full-trajectory KL divergence; the appendix instead uses a stopped experiment. These passages make the scope and reasoning of a main contribution harder to follow than necessary.
Minor technical point: Appendix A absorbs an additive into the claimed regret bound, which tends to zero when and . This step is not justified uniformly as written. Retaining the sharper miss-probability estimate appears to repair the argument without changing the claimed rate.
Questions for authors
None
3 comments
Thank you for the response and revisions. These largely address my concerns, and I maintain my scores.
Two minor corrections remain: (i) reverse the final ceiling comparison on page 14 and retain in the subsequent bound on ; (ii) use the additive total-variation comparison from Appendix C.5 in Section 6.2 to make the constant-probability conclusion explicit
We thank the reviewer for the follow-up comments and helpful suggestions. We are glad to hear that our previous rebuttal has addressed your main concerns.
Q1: Reverse the final ceiling comparison on page 14 and retain in the subsequent bound on .
A1: Thank you for catching this remaining issue! We have revised Appendix A.1 to correct the direction of the inequalities involving the ceiling functions and consistently replaced with wherever the logarithmic factor arises from .
Q2: Use the additive total-variation comparison from Appendix C.5 in Section 6.2 to make the constant-probability conclusion explicit.
A2: Thank you for this suggestion! We have revised lines 475–483 of the manuscript to explicitly state that the change-of-measure argument relies on an additive comparison in total variation distance. We then apply Pinsker's inequality to establish a constant upper bound on the total variation distance, thereby making the constant-probability conclusion explicit.
Thank you for your supportive feedback! We answer your questions as follows.
Q1: The non-adaptivity claim on page 6 is too broad for comparable optimal-arm counts.
A1: Thank you for pointing out this issue, we have revised our paper accordingly to specify that the non-adaptivity result is only applicable when A=ω~(B).
Q2: The overview of Theorem 6.2 treats a pull-count bound on an event as controlling the full-trajectory KL divergence; the appendix instead uses a stopped experiment.
A2: We thank the reviewer for pointing out this imprecision in our proof overview. We would like to clarify the motivation for introducing the stopped experiment in Appendix C.5 and its connection to the high-level argument in Section 6.2.
At a high level, the key step in proving Theorem 6.2 is to establish a regret lower bound on the hard instance ν. To this end, we aim to show that the event E:=NU(T)≤m occurs with constant probability under Pν. Our argument proceeds in two steps. First, using the exploration constraints imposed by near-optimality on ΞK,A, we establish that Pθ(E)≥1/2 on the all-equal reference instance θ. Second, we transfer this probability lower bound from θ to ν. The key intuition is that, when Δ≍1/m, the two instances cannot be reliably distinguished before the algorithm has pulled arms in U more than m times. Consequently, the event E must also occur with constant probability under ν, so that Pν[E] is properly lower bounded. This is the central intuition conveyed by the proof overview in Section 6.2.
The formal proof in Appendix C.5 follows precisely this roadmap, with the stopped experiment providing a rigorous justification for the second step. A standard approach to establishing indistinguishability is to bound the KL divergence between the trajectory distributions induced by the two instances. However, directly bounding the KL divergence between the full-trajectory distributions Pθ and Pν does not yield the desired result. Specifically, on the event NU(T)>m, the algorithm may pull arms in U substantially more than m times. Such trajectories can contribute significantly to the full-trajectory KL divergence, preventing us from obtaining a sufficiently tight bound.
To address this issue, we introduce the stopping time τ, defined as the first time the algorithm pulls an arm in U for the (m+1)-th time, or T if no such time exists. Under this definition, the event E is measurable with respect to Fτ. Crucially, on the event NU(T)>m, the portion of the trajectory after time τ, which may contribute substantially to the full-trajectory KL divergence, is marginalized out. Consequently, the KL divergence between the restricted distributions Pθ∣Fτ and Pν∣Fτ is smaller and can be upper-bounded by the desired quantity.
We view the stopped experiment as a technical device for formalizing the intuition that the two instances remain indistinguishable as long as the algorithm has not sufficiently explored U. For this reason, we originally omitted it from the high-level proof overview. Nevertheless, we agree that the original presentation could incorrectly suggest that the pull-count bound on E directly controls the full-trajectory KL divergence. We have therefore revised Section 6.2 to explicitly distinguish the event-restricted intuition from the formal stopped-experiment argument, and clarified the motivation for introducing the stopping time in Appendix C.5.
Q3: Appendix A absorbs an additive 1/2 into the claimed regret bound, which tends to zero when A=K−1 and T=K.
A3: Thank you for catching this issue! We have fixed this issue in our revision.