- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The goal is to identify the best arm at a particular time using a limited number of observations from nearby times. Each arm has its own ordered stream: pulling an arm reveals its next sample, moving farther from the target. Longer prefixes reduce sampling noise but can reverse the ordering at the target. SignCount-SH compares each pair at several dyadic prefix lengths, stops at the first decisive comparison, and uses the resulting win counts for sequential halving. The paper proves a simple-regret guarantee and a lower bound over a class defined by its resolution and ranking certificates. Experiments use a synthetic reward trajectory and NYC taxi data; the strongest taxi results come from a Bernstein variant that accounts for batch sampling variance.
Critical strengths
-
The target-time objective leads to a different statistical problem from identifying the best historical average. The multiresolution test uses this distinction directly: a prefix can preserve the sign of a gap even when it gives a poor estimate of the gap's magnitude. This is a good reason to study the setting separately from stationary BAI.
-
The ranking certificate addresses the difficult part of the elimination proof. Lemma 12 controls the good arm's score against a bad arm through comparisons with third arms, so it remains useful for a data-dependent surviving set. The hard family in Appendix C.2 then shows that a strong target-time gap can still require many samples when the remaining observations carry only a weak signal. I find this combination more persuasive than an upper bound alone.
Critical weaknesses
-
I cannot reconstruct the synthetic experiment from the specified stream lengths. Appendix D sets and , includes target time 545, and reports budgets up to . Only 96 samples per arm remain after that target. At the largest budget, Algorithm 2 requests 85, 170, and 341 additional samples from surviving arms across its three stages, for a final depth of 596. The paper does not state whether the final regime is extended, streams are resampled, or requests are capped. The choice matters because it determines which drift the algorithms encounter. This needs resolving before the reported synthetic comparison can be assessed.
-
The taxi results provide narrower evidence than the general scalar-observation model suggests. Section 4.2 reports that the Hoeffding version resolves no duels and behaves like Vanilla-SH through tie-breaking. The improved version uses known batch sizes and variance calibration, with up to 4,000 trips counted as one query. Appendix K appropriately separates identification from forecasting, but its afternoon results show almost no gain over Vanilla-SH. The method is promising in the morning regime; its advantage across observation models and drift patterns remains less clear.
Questions for authors
-
Experimental clarification: How are samples beyond time 640 generated or handled for the later synthetic targets? Is the same continuation or exhaustion rule used for every method?
-
Scope clarification: At the reported confidence level, do the experimental trajectories have finite ranking certificates? In particular, do the earlier wrong-sign exclusions in Definition 1 hold for the comparisons needed after the simulated reversals?
Response to Reviewer SEHP
1. Experimental clarification
We thank the reviewer for identifying this omission. The stated T=640 describes the nonconstant portion of the trajectory. In the experiments, we extend the final plateau unchanged.
We will state this explicitly in Appendix D.
2. Scope clarification
At (δ,σ)=(0.05,0.02), target times 1, 289, and 545 have finite ranking certificates and satisfy the earlier wrong-sign exclusions in Definition 1. Target 49 does not. In this case, for comparisons between the target-best arm 5 and arms 1 and 4, recent-prefix averages never produce a sufficiently strong correctly signed signal to exceed the conservative 3qi(δ) certificate threshold. As older observations enter, the prefix averages eventually become significantly wrong-signed. Their resolving depths, and therefore HNS(δ)(θ,0), are infinite.
Theorem 5 therefore does not cover target 49. Its success there is empirical. This is possible because Definition 1 is a sufficient certificate, not an instance-wise necessary condition. We will clarify that the experiment deliberately includes both certified and challenging uncertified trajectories.