- Rating
- 4
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies fixed-confidence best-arm identification when a joint action's reward is a sum of local factors and each factor reward is observed separately. It starts from the known characteristic-time optimization and represents feasible sampling allocations through junction-tree marginals. A second dynamic program keeps cumulative reward gaps, allowing the optimization to retain each competitor's own gap. This gives an exact conic formulation whose size depends on graph width and gap-state width, together with a quantized approximation for real-valued means. JT Track-and-Stop uses these allocations and a conservative stopping statistic to attain the asymptotic sample-complexity lower bound. Experiments check the optimization against exhaustive solutions and compare sampling efficiency and target-solver runtime on synthetic instances.
Critical strengths
-
The paper addresses the computational obstacle in the known lower bound. Junction-tree consistency handles feasible allocations, but the more interesting step is the signed gap-state recursion: ordinary max-sum cannot optimize the ratio involving a competitor's squared gap. Theorem 5 turns this recursion into an explicit conic program while allowing correlated sampling allocations. This improves on the restriction used by Vannella et al. [1]. The comparisons with exhaustive optimization across 70 instances in Appendix F.2 help verify that the formulation was implemented correctly.
-
Quantization is carried through to the stopping rule, rather than used only to produce sampling targets. Proposition 6 controls the offline approximation error; the online grid can shrink without knowing the true minimum gap; and Equation (3) accounts for rounding before declaring a winner. These details matter for the claim of -correct, asymptotically optimal identification.
[1] Filippo Vannella, Alexandre Proutiere, and Jaeseong Jeong. Best Arm Identification in Multi-Agent Multi-Armed Bandits. International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research 202:34875–34907, 2023.
Critical weaknesses
-
The experimental stopping rule is insufficiently documented. Section 7 says the methods share a stopping calibration, but does not identify the implemented threshold, grid constant, or solver tolerances. Equation (63) specifies a theoretical boundary; it is unclear whether that boundary produced Figure 2. Appendix F promises calibration, confidence-level, and quantization results, but the supplied PDF ends after F.2 without them. Since the reported advantage is measured in stopping times, empirical error rates and the actual stopping rule are essential to interpreting the comparison.
-
The large-instance result demonstrates one allocation solve, rather than the complete identification procedure. The 48-agent binary chain is impressive as an optimization example, but the main online comparisons use five agents and the additional online examples reach six or seven. Figure 2(b) reports target-solver time, while the online figures report samples. There is no corresponding comparison of total time spent constructing targets, solving them, and checking stopping. The paper acknowledges that gap-state width can be large; I therefore see strong evidence for the representation, with less evidence for its practical advantage in large online problems.
Questions for authors
-
Experimental clarification: Which stopping threshold, quantization constant, and numerical tolerances produced Figure 2? Was Equation (63) used? What error rates were observed, and how were runs that reached a time or sample cap handled?
-
Implementation clarification: Does Figure 2(b) include construction of gap supports and the conic program? Are total online runtimes available for the same instances used in the sample comparisons? Please also clarify whether the experimental sections announced in Appendix F were omitted from this version.
Thank you for the thorough and positive review. We address your experimental and implementation questions below.
Q1 - Experimental clarification. We agree that some of the experimental details were not sufficiently documented in the original submission. We have now clarified the stopping rule, quantization schedule, numerical settings, and empirical error rates. In particular, our experiments use the practical stopping threshold β(t,δ)=log[(1+log(max2,t))/δ], a well-established choice in BAI experiments (see Kaufmann and Koolen, 2021, Sec. 5.1; Wang et al., 2021, Sec. 5.2). We use the same threshold and exact empirical GLR stopping test across all methods to ensure a fair comparison of their sampling efficiency. Regarding empirical correctness, all 1,020 recorded runs underlying Fig. 2(c–e) stopped correctly without reaching their sample caps. We further conducted 1,200 additional calibration trials across four gap and confidence settings, observing zero errors and zero capped runs. These results, together with the corresponding confidence bounds and complete experimental settings, are reported in App. F.
Q2 - Implementation and runtime clarification. We agree that the computational scope of the original experiments deserved a clearer explanation. The exact SOCP formulation of Theorem 5 provides a convex characterization of the characteristic-time problem and allows us to explicitly quantify its variables and constraints. For numerical efficiency, our experiments instead use an LP-based implementation. We have clarified this distinction and documented the numerical settings in Section 6 and Appendix F. The revised manuscript additionally reports online runtimes for the original sample-complexity comparisons and the new large-scale experiments discussed in our response to Reviewer qD7v (Q1). Finally, we thank the reviewer for identifying the incomplete Appendix F. We have restored and updated the missing experimental sections, including numerical validation, sensitivity analyses, and stopping-rule calibration.