acceptodds
Under review as a conference paper at ICLR 2027

Adversarially Batched Online Learning

Abstract

We introduce adversarially batched online learning, where the learner may update its decision rule only at a restricted set of time steps. Equivalently, the time horizon is partitioned into batches, within which the learner must use a fixed policy. We study this model for four canonical problems: stochastic bandits, online convex optimization, prediction with expert advice, and adversarial bandits. For stochastic bandits, we identify a universal complexity measure based on relative batch growth and establish both gap-dependent and gap-independent regret bounds. We show that the multiplicative penalty relative to the standard gap-dependent complexity can grow superlinearly in batch hardness. For the remaining three, we show that the optimal regret is tightly characterized by the 2-norm of the batch-length sequence. The upper bound is achieved by a batch-oblivious learner who does not know the batch structure, via a generic adaptive doubling trick tailored to this complexity measure. In contrast, the lower bound holds even for batch-aware learners.

Primary area:
learning theory
Keywords:
Online learning, multi-armed bandits

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_fXUXOpenReview ↗
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 α\alpha measuring relative batch growth and obtain regret bounds O~(α2∑i:Δi>0Δi−1)\widetilde{O}(\alpha^2 \sum_{i:\Delta_i>0}\Delta_i^{-1}) and O~(αNT)\widetilde{O}(\sqrt{\alpha NT}), alongside a worst-case lower bound Ω(α3/2∑i:Δi>0Δi−1)\Omega(\alpha^{3/2}\sum_{i:\Delta_i>0}\Delta_i^{-1}). For OCO, experts, and adversarial bandits, they establish O(DG∥b∥2)O(DG\|b\|_2), O(∥b∥2log⁡N)O(\|b\|_2\sqrt{\log N}), and O(∥b∥2Nlog⁡N)O(\|b\|_2\sqrt{N\log N}), respectively, where bb 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

We thank the reviewer for the thoughtful feedback. We will address the listed concerns below:

For stochastic bandits

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 2 and Appendix 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)S_j=\Theta(b_j/n_j) 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.\alpha(\mathcal B')\le 4\alpha(\mathcal 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.

For the other three settings

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\|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 in Proposition 2 and Appendix I, the naive doubling trick adaptation can incur Ω(T)\Omega(T) regret on an instance (where our method achieves O(T3/4)O(T^{3/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.

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!

Reviewer_T44wOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes an online learning model where an adversary partitions the time horizon into batches, and the learner is restricted to updating her action at boundaries. The authors study stochastic bandits, oco, experts and adversarial bandits.

Critical strengths
  • The paper is structured well, easy to follow and theoretical analysis is coherent.
  • For stochastic bandits, the introduces a natural complexity measure that is characterized by relative growth (compared to absolute delay).
Critical weaknesses
  • The paper presents a unified treatment of the four settings, but the new theoretical contributions seem more concentrated than the presentation suggests. Specifically 1) On OCO and Experts, the delayed feedback literature seems to recover the same bounds (as the authors themselves observe 2) On adversarial bandits, the distinction from arbitrary delay work seems to rest primarily in a strong "fixed-arm" (rather than sampling distribution) assumption. Without this, prior works in arbitrary-delay (e.g. Zimmert and Seldin AISTATS 2020) recover O(NT+∥b∥2log⁡N)O(\sqrt{NT}+\lVert\mathbf b\rVert_2\sqrt{\log N}). The paper could better motivate applications requiring realized-action freezing and clarify that the novelty in this setting arises from additional action constraint, rather than adversarially chosen timings. So, the main novelty seems to be in the relative-growth complexity measure, which is a useful extension of Gao et al, but the technique seems to be closely based on their successive elimination framework (with an additional merging step), and furthermore the gap-dependent bound is not tight.
Questions for authors
  • In the delayed feedback model, should the Schlisselberg et al baseline be O~(min⁡T,NT+bmax⁡)\widetilde O(\min{T,\sqrt{NT}+b_{\max}})? The paper's broader multiplicative-versus-additive distinction still stands.
4 comments
AuthorsOpenReview ↗

Response (1)

We thank the reviewer for the incisive feedback. We will address the listed concerns below:

Beyond extension of Gao et al.

For stochastic bandits, we agree that our 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 2 and Appendix 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)S_j=\Theta(b_j/n_j) 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.\alpha(\mathcal B')\le 4\alpha(\mathcal 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.

Connections to existing methods and the generic adaptive doubling trick

We agree that delayed-feedback results recover the OCO and experts' upper bounds, as demonstrated in Appendix H. We also give a complementary reduction to scale-free online learning covering all three non-stochastic settings in Appendix G. These reductions explain the dependence on ∥b∥2\|b\|_2 from different perspectives and, together with our lower bounds in Theorem 5, clarify how batch structure affects learning difficulty.

Beyond these reductions, one of our technical contributions 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 in Proposition 2 and Appendix I, the naive doubling trick adaptation can incur Ω(T)\Omega(T) regret on an instance (where our method achieves O(T3/4)O(T^{3/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.

AuthorsOpenReview ↗

Response (2)

realized-action freezing in adversarial bandits

We study the stricter setting for adversarial bandits where the learner commits to a single arm within a batch and learns only the losses associated with that action throughout the batch. In this model, fresh within-batch arm sampling is not permitted, and our adversarial-bandit results characterize the combined effect of externally imposed batch boundaries and this commitment constraint. Below, we provide some motivated examples that have the "fixed-arm" constraints:

  • A food delivery app's implementation assigns one algorithm variant to a region for an entire time window, rather than independently assigning a variant to every delivery.
  • A production line required to use one configuration throughout a scheduled run, with quality feedback released after the run.
  • A pricing system required to honor one posted price throughout a sales window, with sales feedback reported at its end.

In each case, randomization can select the configuration or price at the window's start, but repeatedly resampling it would violate the operational commitment.

Nevertheless, we agree that if we instead allow the usual per-round randomized action choices and reveal each round's indexed bandit feedback at the batch endpoint, the problem is a special case of delayed bandits. Specifically, setting dt=tj−td_t=t_j-t for t∈(tj−1,tj]t\in(t_{j-1},t_j] gives

Ddelay=∑tdt=12∑jbj(bj−1)=∣b∣22−T2.D_{\mathrm{delay}}=\sum_t d_t=\frac12\sum_j b_j(b_j-1)=\frac{\\|b\\|_2^2-T}{2}.

Theorem 1 of Zimmert et al. then yields

=O\\!\left(\sqrt{NT}+\\|b\\|_2\sqrt{\log N}\right),$$ without advance knowledge of the delays. We will explicitly discuss this comparison under the looser setting that has no "fixed-arm" constraint. > Schlisselberg et al.'s result We thank the reviewer for the correction. We will revise the baseline to $\tilde{O}(\min\\{ T, \sqrt{NT} + b_{\max} \\})$, and agree that our claim on the multiplicative-versus-additive distinction remains valid.

Thank you for the detailed response and clarifications. I have no further questions, and would like to maintain my current score.

Thank you for the review and response, Reviewer T44w!

Reviewer_qzrrOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This work considers online-learning problems in which updates are allowed only at externally fixed batch boundaries. It covers stochastic bandits, OCO, prediction with expert advice, and adversarial bandits. A learner may know the schedule in advance (batch-aware) or discover a boundary only when its feedback arrives (batch-oblivious).

For stochastic bandits, the paper defines the relative batch-growth parameter α=max⁡jbj/tj−1\alpha=\max_j b_j/t_{j-1}. A successive-elimination algorithm that merges short consecutive batches obtains gap-dependent regret O~(min⁡{T,α2∑i:Δi>0Δi−1})\widetilde O(\min\{T,\alpha^2\sum_{i:\Delta_i>0}\Delta_i^{-1}\}) and gap-independent regret O~(min⁡{T,αNT})\widetilde O(\min\{T,\sqrt{\alpha NT}\}). The paper gives a matching gap-independent lower bound on a family of batch structures. Its strongest gap-dependent lower bound is Ω(α3/2∑i:Δi>0Δi−1)\Omega(\alpha^{3/2}\sum_{i:\Delta_i>0}\Delta_i^{-1}).

For OCO, experts, and adversarial bandits, the upper bounds depend on ∣b∣2=(∑jbj2)1/2\\|\mathbf b\\|_2=(\sum_j b_j^2)^{1/2}. OGD, Hedge, and EXP3 give bounds of order DG∣b∣2DG\\|\mathbf b\\|_2, ∣b∣2log⁡N\\|\mathbf b\\|_2\sqrt{\log N}, and ∣b∣2Nlog⁡N\\|\mathbf b\\|_2\sqrt{N\log N}, respectively. The OCO lower bound holds for every fixed batch structure, while the experts and adversarial-bandit lower bounds are worst-case constructions over families of batch structures. An adaptive doubling procedure matches these batch-aware rates without advance knowledge of the batch lengths.

Critical strengths
  1. The paper identifies useful structure beyond the number of batches or the largest batch. In the stochastic setting, α\alpha measures the size of the next commitment relative to the amount of information already available. For example, geometrically growing batches can have α=O(1)\alpha=O(1) even when the final batch is large, while one sudden batch can make α\alpha large. For OCO, experts, and adversarial bandits, the appearance of ∣b∣2\\|\mathbf b\\|_2 follows from the squared gradient or loss ranges. So schedules with the same BB or bmax⁡b_{\max} can have different regret guarantees.

  2. The paper gives several upper and lower bounds rather than only an algorithm for one problem. The OCO result is pointwise tight for every fixed B\mathcal B. The adaptive doubling argument is also useful. It treats the batch that exceeds the current guess separately and then sums the realized squared batch lengths geometrically. Proposition 2 shows why the usual epoch schedule cannot simply be used here: a schedule with mm unit batches followed by mm batches of length mm gives the naive Hedge adaptation Ω(T)\Omega(T) regret, while Theorem 7 gives O(T3/4)O(T^{3/4}) on the same instance.

Critical weaknesses
  1. The stochastic gap-dependent result is not a tight characterization. Theorem 1 gives an α2\alpha^2 upper bound, while Theorem 4 gives an α3/2\alpha^{3/2} lower bound, leaving a gap of factor α1/2\alpha^{1/2}. Proposition 4 does not close this gap: it constructs abstract batch-length and active-set sequences for which the comparison used in the current proof loses Ω(α7/4)\Omega(\alpha^{7/4}), but it does not construct a stochastic-bandit instance that forces this loss for every algorithm.

  2. The ∣b∣2\\|\mathbf b\\|_2 lower bounds for experts and adversarial bandits have a weaker scope than the corresponding upper bounds. Theorem 5 gives upper bounds for every fixed batch structure, but the experts and adversarial-bandit lower bounds use specially balanced families. The experts proof chooses structures with bmax⁡=O(∣b∣2/log⁡N)b_{\max}=O(\\|\mathbf b\\|_2/\sqrt{\log N}) so that the batches can be divided into Ω(log⁡N)\Omega(\log N) stages, and the adversarial-bandit proof finally chooses a structure with bmax⁡=O(∣b∣2/N)b_{\max}=O(\\|\mathbf b\\|_2/\sqrt N). So the statement that the optimal regret is characterized by ∣b∣2\\|\mathbf b\\|_2 should be qualified as a worst-case statement for these two problems.

Questions for authors
  1. For experts and adversarial bandits, are the ∣b∣2log⁡N\\|\mathbf b\\|_2\sqrt{\log N} and O~(∣b∣2N)\widetilde O(\\|\mathbf b\\|_2\sqrt N) rates claimed only in the worst case over batch structures? Can comparable lower bounds be proved for every fixed B\mathcal B, or do some structures admit smaller minimax regret?

  2. Is there a realizable stochastic-bandit construction that gives an Ω(α2∑iΔi−1)\Omega(\alpha^2\sum_i\Delta_i^{-1}) lower bound, or can the upper bound be improved toward α3/2\alpha^{3/2}?

1 comment

We thank the reviewer for the incisive feedback. We will address the listed concerns below:

W1 & Q2: the gap in the dependence on α\alpha

We agree that closing the α1/2\alpha^{1/2} gap between the gap-dependent upper and lower bounds remains an open problem and have already identified this open problem in Appendix A (Discussion). Similarly, we also agree and have explicitly mentioned that Proposition 4 serves only as an abstract counterexample to demonstrate that current analysis cannot be improved to α3/2\alpha^{3/2} instead of serving as an algorithm-independent lower bound. As discussed in Appendix A, one concrete starting point for the future work is to form a realizable stochastic bandit instance from the counterexample in Proposition 4 and to generalize an algorithm-independent lower bound with a dependence of α7/4\alpha^{7/4}.

On the other hand, we note that our existing results have provided substantive guarantees with some novel analysis methods. For the gap-dependent upper bound, compared with previous work of Gao et al., we replaces the coarse worst-arm dependence N/Δmin⁡N/\Delta_{\min} by the standard UCB-type complexity ∑i:Δi>0Δi−1\sum_{i:\Delta_i > 0} \Delta_i^{-1} and generalized to any batch structure B\mathcal{B} instead of only to specially designed ones.

Such an improvement is achieved by a novel gap-dependent analysis that is substantially different from the previous work. Specifically, we introduce 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 toward proving Theorem 1. As analyzed in Lemma 2 and Appendix B.2, we decompose regret and inverse-gap complexity by elimination blocks and distinguish moderate from rapid active-set contraction. Moderate-contraction blocks admit direct comparisons, while consecutive rapid-contraction blocks require an amortized argument that charges their geometrically decaying contributions to the preceding block. The merging procedure creates the geometric-growth structure needed by this argument while ensuring α(B′)≤4α(B)+2\alpha(\mathcal B')\le 4\alpha(\mathcal B)+2.

For the lower bound, Theorem 4 uses a separate construction hiding two nearly tied arms among many arms to strengthen the linear-in-α\alpha lower bound to α3/2\alpha^{3/2}. While the precise exponent remains an open problem, this already shows that a superlinear penalty in α\alpha is unavoidable in general.

W2 & Q1: the scope of the lower bounds

We agree that, compared to the OCO's lower bound, experts and adversarial bandits have a weaker scope. However, we want to clarify that our proofs establish lower bounds for every fixed batch structure satisfying the stated mild conditions instead of only in the worst case over batch structures. More precisely, writing R∗(B)R^*(\mathcal B) for the minimax regret with the batch structure B\mathcal B fixed and known to the learner, the proofs give:

  • Experts (Appendix E.2): for every B\mathcal B satisfying bmax⁡≤c∥b∥2/log⁡Nb_{\max}\le c\|b\|_2/\sqrt{\log N}, we have R∗(B)=Ω(∥b∥2log⁡N)R^*(\mathcal B)=\Omega(\|b\|_2\sqrt{\log N});
  • Adversarial bandits (Appendix F.2): for every B\mathcal B satisfying bmax⁡≤c∥b∥2/Nb_{\max}\le c\|b\|_2/\sqrt N, we have R∗(B)=Ω(∥b∥2N)R^*(\mathcal B)=\Omega(\|b\|_2\sqrt N),

where c>0c>0 is a fixed absolute constant. These conditions cover a wide range of batch structures, and our lower bounds hold for every fixed structure within this range. The guarantee is therefore uniform over these families, rather than merely a worst-case statement obtained by selecting a particular batch structure. We nevertheless agree that the conditions cannot be omitted from a claim of matching rates for every fixed structure. We have explicitly stated these conditions in Appendices E.2 and F.2 toward proving Theorem 5. We will revise the main text accordingly to highlight our scope.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.