- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
the paper studies the problem on identifying the best limiting loss, or say in a different way, identifying the best learning / optimization process that can lead to smallest loss in the end. specifically, the core interest is not on proposing new algorithms, but for the specific model, what the price gap we need to pay when we dont know the amplitude. the discussion covers three cases, single arm, two arms and more than two arms, with different results.
Critical strengths
the paper comes with very strong theoretic contribution on the problem of best asymptote identification, where the amplitude is unknown. as a major contribution it quantifies the cost of the unknown quantity and show that the cost is likely necessary as well, in different cases. the cost itself looks reasonable and good addition to existing works. additionally, the paper is structured in a stepwise way from one arm to two arms then multi arms, which helps a bit to get some general idea quickly despite it being very theoretical paper.
Critical weaknesses
frankly it is very hard at least for me to read with such heavily loaded notations. And many of the notations seem to be unnecessarily complicated i believe. for example, R^{pi_T,B}_{T,M}(c;r) in line 229, with 6 arguments essentially in the formula, and bottom T can be totally removed as there is already a T. also there are many notations undefined or used before defined, such as big C in the abstraction, tho this one isnt difficult to guess what it means, but there is also small c in the abstraction. overall, the notation issues have made the paper hard in reading with many cognitive efforts on digesting the meanings.
Questions for authors
to the best of my knowledge, coming from more adaptive bandit algorithm design background, it seems to be a classic result that in the two arms setting, equally sampling is nearly optimal or say in a different way, adaptivity doesn't help gain much further, while in multi-armed settings (K>2), adaptivity does make a difference. this seems to be in analogy to one of the messages this paper delivers. I first wonder if the authors can clarify if this statement is true, and if true, can the authors make this connection clear / strong with the results of this paper? especially what this paper presents beyond that?
Simplifying the error notation and defining c and C
Equation (14) now uses RT(π,M). This is the smallest worst-case error attainable by a final recommendation after sampling according to policy π, over the stated parameter window of radius M. The exponent r, rescaled gap c, budget multiplier C, and amplitude interval are fixed in that section and are suppressed in the notation. The policy symbol π denotes the sequence of rules used at different budgets, so T appears only once in RT(π,M) as the budget index.
Before the equation, Section 5 defines CT as the maximum total number of updates and c/T as the minimum separation between the limiting losses under comparison. It explains why this separation is comparable to the uncertainty in the estimated difference. Neither c nor C appears in the revised abstract. The abstract and introduction define a training run, observed loss, and limiting loss before introducing the mathematical notation.
Is the two-arm versus multi-arm distinction classical, and what is added here?
Yes, for two stationary Gaussian arms with equal known variance, balanced sampling attains the optimal fixed-budget error exponent. With unequal known variances, the allocation attaining this exponent assigns updates in proportion to the standard deviations (Kaufmann, Cappé and Garivier, 2016). Revealing the transient amplitudes in our model recovers the equal-variance stationary comparison because the remaining improvement can then be subtracted from every loss. Section 2 makes this connection explicit.
Our additional result concerns the exact nonzero limiting error for increasingly close limits when the amplitudes are unknown. The variance ratio for fitting rather than knowing the amplitude is κ(r)=(1−r)2/r2 for 0<r<1/2 and one for r≥1/2. Theorem 2 proves that this is also the exact limiting budget ratio after optimizing over allocation and stopping under the stated total budget cap. The proof must account for the dependence of the final sample counts on earlier noise. Section 5 bounds the information about which limit is smaller in the observations collected by an adaptive policy. Equal sampling and least squares attain the bound.
For more than two arms, Section 6 makes the adaptive advantage precise on a restricted class. The number of arms K is fixed, only one competitor can have a limit close to the best arm’s, and all other limits exceed both by a fixed margin. An initial screening stage identifies the pair with probability tending to one while using a fraction of the budget that tends to zero. Almost all remaining updates go to that pair. For a schedule fixed in advance, the competitive pair might consist of the two least-sampled arms, which together receive at most 2/K of the budget. On this class, screening saves a factor K/2 in first-order budget over the optimal deterministic allocation. The cost κ(r) of estimating each amplitude persists.
The optimal unrestricted adaptive allocation with several simultaneously close competitors remains open.