cs.LGNov 12, 2026

Adversarially Batched Online Learning

Authors: Mingda Qiao, Kerui Wu

Organizations: University of Massachusetts Amherst

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.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Batched Kernelized Bandits: Refinements and Extensions

    Mar 13, 2026Chenkai Ma, Keqin Chen, Jonathan ScarlettBlack-Box OptimizationMulti-Armed Bandits

  2. Offline-to-Online Learning in Linear Bandits

    Jun 3, 2026Kushagra Chandak, Toshinori Kitamura, Xiaoqi TanMulti-Armed BanditsContextual Bandits

  3. Strongly Adaptive Online Learning Achieves Uniform Discounted Regret

    Oct 29, 2026Sifan Yang, Wenhao Yang, Lijun ZhangOnline Convex Optimization