Adversarially Batched Online Learning

Mingda Qiao, Kerui WuarXiv 2026 · arXiv

TL;DR

This paper introduces a framework for adversarially batched online learning, where a learner can only update its strategy at fixed, externally imposed time intervals. The authors identify two key complexity measures—relative batch growth for stochastic bandits and the 2-norm of batch lengths for adversarial settings—that precisely characterize the "regret penalty" caused by these update constraints.

What Problem Does This Paper Address?

In standard online learning, we assume a learner can observe feedback and update its decision rule after every single round. In the real world, this is often impossible. Consider a clinical trial where data is only reviewed at specific interim dates, or a distributed system that only synchronizes logs when a communication window opens. These constraints force the learner to commit to a fixed policy for a "batch" of time.

While previous research explored "batched" learning where the learner chooses the batch sizes to save on communication, this paper tackles the adversarial setting. Here, the environment (or an adversary) dictates the update points. The core challenge is that a learner might be forced into a long "blind commitment" during a batch, potentially accruing massive regret if the environment changes or if the initial policy was suboptimal.

Methods

The authors analyze four canonical problems: Stochastic Bandits, Online Convex Optimization (OCO), Prediction with Expert Advice (the "Experts Problem"), and Adversarial Bandits.

  • For Stochastic Bandits: They propose a Successive Elimination with Merging algorithm. The "merging" step is a novel technical contribution that combines short consecutive batches to ensure the batch sequence effectively grows at a controlled rate, which is necessary to prove tight regret bounds.
  • For Adversarial Settings (OCO, Experts, Bandits): They show that classic algorithms like Online Gradient Descent (OGD), Hedge, and EXP3 can be adapted by tuning the learning rate based on the batch structure.
  • The Adaptive Doubling Trick: A standout contribution is a generic "batch-oblivious" wrapper (Algorithm 2). Standard doubling tricks (used to handle unknown horizons) fail in the batched setting because a single batch can "overshoot" a pre-set budget by an arbitrary amount. Their new trick recalibrates the learning rate based on the realized sum of squared batch lengths, allowing a learner who doesn't know the future batch schedule to perform as well as one who does.

Datasets

Not discussed in the paper. This is a theoretical work focused on proving regret bounds and designing algorithms; evaluation is performed via mathematical proof rather than empirical benchmarking on specific datasets.

Key Insights and Ideas

  • The "Blind Commitment" Ratio ($\alpha$): For stochastic bandits, the difficulty is captured by $\alpha = \max_j (b_j / t_{j-1})$, where $b_j$ is the current batch length and $t_{j-1}$ is the total time elapsed before it. If a batch is much longer than the history used to inform it, $\alpha$ is high, and the regret penalty grows.
  • The 2-Norm Characterization: For the three adversarial problems, the authors discovered that the optimal regret is tightly characterized by the 2-norm of the batch-length sequence ($\|b\|_2 = \sqrt{\sum b_j^2}$). This provides a beautiful, unified metric for how much batching hurts in non-stochastic environments.
  • Batch-Obliviousness is "Free": In adversarial settings, the authors prove that not knowing the batch structure in advance doesn't actually hurt your asymptotic regret. Their adaptive doubling trick allows a "batch-oblivious" learner to match the performance of a "batch-aware" one.
  • Naive Doubling is Dangerous: The paper includes a clever counterexample (Proposition 2) showing that a standard doubling trick can lead to linear regret (total failure) in batched settings, whereas their adaptive version succeeds.

Key Results

  • Stochastic Bandits: The authors established a gap-dependent regret bound of $O(\alpha^2 \sum \Delta_i^{-1} \log T)$ and a gap-independent bound of $\tilde{O}(\sqrt{\alpha NT})$. They also proved a lower bound of $\Omega(\alpha^{3/2} \sum \Delta_i^{-1})$, showing that a polynomial dependence on the hardness metric $\alpha$ is unavoidable.
  • Adversarial Problems: For OCO, the regret is $O(DG\|b\|_2)$. For the Experts problem, it is $O(\|b\|_2 \sqrt{\log N})$. These bounds are shown to be nearly optimal, with matching lower bounds for any fixed batch structure.
  • Unified Complexity: The results show that when batches are roughly equal in size, the regret increases by a factor of $\sqrt{T/B}$ compared to the non-batched setting.

Limitations and Future Work

  • The $\alpha$ Gap: There is still a gap between the $\alpha^{3/2}$ lower bound and the $\alpha^2$ upper bound for gap-dependent stochastic bandits. The authors suggest that their current analysis might be limited to $\alpha^{7/4}$, leaving room for a tighter characterization.
  • Broader Models: The authors suggest extending this "adversarially batched" framework to more complex models like Reinforcement Learning or Contextual Bandits, where feedback delays and update constraints are even more prevalent in practice.
  • Stricter Adversaries: While the batch structure is adversarial, the rewards in the stochastic bandit section are still assumed to be i.i.d. Exploring fully adversarial rewards with adversarial batching in the bandit setting remains a challenging frontier.

Summary updated

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.
BibTeX
@misc{qiao2026adversarially,
  author = {Mingda Qiao and Kerui Wu},
  title = {{Adversarially Batched Online Learning}},
  year = {2026},
  eprint = {2611.17500},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17500},
}
Figure