- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors study online learning with adversarially imposed batch schedules. For stochastic bandits, they introduce a parameter measuring relative batch growth and obtain regret bounds and , alongside a worst-case lower bound . For OCO, experts, and adversarial bandits, they establish , , and , respectively, where denotes the vector of batch lengths. They then develop an adaptive doubling trick achieving these latter guarantees without knowing future batch lengths.
Critical strengths
I find the problem studied in the paper very interesting and well motivated. In particular, allowing an adversary to choose the batch structure is a natural way to capture situations in which the learner cannot control when it can update its policy.
Furthermore, I also find the theoretical analysis quite comprehensive. The authors study several canonical online learning settings and provide both upper and lower regret bounds, giving a detailed picture of how the batch structure affects the difficulty of learning across these different problems.
Critical weaknesses
The main weakness is that the extent of the technical novelty is not entirely clear to me. The stochastic bandit algorithm builds on Gao et al. with an additional merging step, while the upper bounds for the other settings largely rely on standard methods with adapted learning rates. While these adaptations may require nontrivial analysis, I think the authors should explain more clearly which parts of the algorithms and proofs introduce new ideas beyond the formulation of the problem.
I also believe that the presentation could be improved. I understand that the paper covers several settings and many results, but the order in which they are presented makes it difficult to follow the transitions between settings.
Questions for authors
Could you better elaborate on the technical novelty?
3 comments
I would like to thank the Authors for the responses. I will keep my current score.
Thank you for the review and response, Reviewer fXUX!
We thank the reviewer for the thoughtful feedback. We will address the listed concerns below:
We agree that our stochastic-bandit algorithm shares the successive-elimination framework of Gao et al. However, we argue that our gap-dependent guarantee is established through a substantially different proof strategy that goes beyond a straightforward extension of their analysis.
More specifically, our gap-dependent analysis introduces two coupled nontrivial ideas: a decomposition and amortized charging argument based on active-set contraction, and an online merging procedure that creates the structure needed by this argument while preserving batch hardness. These novel analysis methods yield an upper bound (
Theorem 1) with finer dependence on individual arm gaps for arbitrary batch structures. Below, we explain in more detail the technical obstacle that prevents a direct extension of Gao et al.’s analysis and how our new analysis methods overcome it.1. The obstacle is the interaction between batch growth and active-set contraction. Gao et al.'s analysis controls arm pulls through elimination order and properties of their chosen grids. In our analysis, controlling batch growth alone is insufficient: when many arms are eliminated simultaneously, the surviving arms receive a much larger share of the next batch. Consequently, the cumulative samples per surviving arm can increase sharply even when the batch length grows moderately. This prevents a direct block-by-block comparison between regret and the corresponding inverse-gap complexity.
2. Our decomposition resolves this obstacle through amortized charging. In
Lemma 2andAppendix B.2, we group arms by their elimination blocks and decompose both the regret and the target inverse-gap complexity along these groups. We then partition blocks according to whether the active-set size contracts moderately or rapidly. For moderate contraction, we can compare the corresponding terms directly. For rapid contraction, we consider maximal consecutive runs of such blocks: their regret contributions admit geometrically decaying bounds, allowing the entire run to be charged to the preceding block.With this distinction between local control and amortized control across blocks, our method handles abrupt changes in the sampling allocation.
3. Merging makes this argument applicable to arbitrary batch structures. The algorithm merges consecutive batches online until their combined length is at least twice that of the preceding merged block. This geometric growth ensures that cumulative samples per active arm satisfy Sj=Θ(bj/nj) for completed merged blocks, providing the structural relation used in the decomposition and charging argument. We separately handle the final incomplete block and prove α(B′)≤4α(B)+2. Thus, the merging procedure establishes a controlled reduction from arbitrary imposed batch structures to ones that support our proof, using only the update times observed so far.
We agree that the batch-aware upper bounds use standard algorithms. We also provide two complementary connections that recover batch-oblivious guarantees: a reduction to scale-free online learning for all three settings (
Appendix G), and a reduction to delayed-feedback learning for OCO and experts (Appendix H). Both explain the emergence of ∥b∥2 in the regret bounds. Together with our lower bounds (Theorem 6), these connections help characterize the effect of batch structure on learning difficulty.Beyond these reductions, our technical contribution lies in proposing a generic adaptive doubling trick to obtain batch-oblivious guarantees for any restartable base algorithm satisfying the conditions of
Theorem 7. This requires nontrivial algorithm design and analysis: as shown inProposition 2andAppendix I, the naive doubling trick adaptation can incur Ω(T) regret on an instance (where our method achieves O(T3/4)). The challenge is that the number of batches does not control their accumulated squared lengths, so the learning rate chosen from past observations can become severely miscalibrated. Moreover, a single batch can overshoot the current budget by an arbitrarily large amount before feedback arrives. To address this, our method restarts when the observed sum of squared batch lengths reaches the current budget and sets the next budget to twice the realized sum. Our proof separately controls the blocks preceding the last batch of each epoch using the base algorithm's guarantee, and the last batch using the instantaneous-regret bound.As a result, as shown in
Theorem 7, this yields a generic conversion that preserves the base algorithm and its batch-aware regret rate without requiring advance knowledge of the batch structure.