betaFeedback

WorksComputer Science

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.

Introduction

Online learning provides a framework for sequential decision-making in uncertain environments. In standard settings, the learner plays an action at each round and observes the associated losses, which may immediately factor into the decision in the next round. The objective is to minimize the cumulative regret, defined as the difference between the total loss of the learner and that of the best fixed action in hindsight. While this framework has been studied extensively (e.g., see [4, 15]), the assumption that the learner can freely revise its policy after every round is often violated in practice. Frequent policy updates may be infeasible due to physical, logistical, or system constraints: outcomes may only become available after a trial phase, human annotations may need to be collected and validated together, and system-level updates may require synchronization.

This work addresses Batched Online Learning, where the learner is only allowed to update their decision rules at a set of specific time points. Prior work in this domain has largely focused on scenarios where the learner designs the batch structure to optimize the trade-off between the regret and the number of batches (e.g., [9, 7]). In contrast, we investigate the Adversarially Batched setting, where the update points are imposed by an external environment (or adversary) and are immutable from the learner’s perspective. For example, a clinical trial may release cumulative outcome data only at irregular interim review dates, a crowdsourcing platform may return validated annotations only after unpredictable quality-control cycles, and a distributed system may synchronize logs or deploy updates only when communication windows become available at unpredictable times.

The core challenge in our setting is that the learner must make a commitment at the beginning of each batch that cannot be revised until the batch ends, potentially accruing significant regret if the batch is long. We study this setting under four classic online learning problems: Stochastic Bandits, Online Convex Optimization (OCO), Experts Problem, and Adversarial Bandits.

The main contributions of this work are summarized below. We formally introduce our setup in § 1.1 and state our results in § 2.

  • We formulate a model of adversarially batched online learning, where the environment specifies the time steps on which the learner is allowed to update its decision rule.

  • For stochastic bandits, we identify a universal batch-complexity measure that captures the multiplicative regret increase over the non-batched setting. We prove both gap-dependent and gap-independent regret bounds that depend on this quantity.

  • For the other three problems, we show that the optimal regret is characterized by the 2-norm of the batch length sequence by proving nearly matching upper and lower bounds. The upper bound is achieved by a batch-oblivious learner that does not know the batch structure, while the lower bound applies to batch-aware learners as well.

Problem Setup

In standard online learning settings, the learner interacts with the environment over a sequence of time steps t∈[T]:={1,2,…,T}t \in[T] := \{1,2,\ldots,T\}. At each time step, the learner makes a decision based on the feedback observed from previous rounds, receives feedback from the environment, and updates its decision rule. The goal of the learner is to minimize the cumulative regret, which quantifies the sub-optimality of its actions compared to the optimal fixed action in hindsight.

Our model: Adversarially Batched Online Learning. Departing from the standard model, we study an adversarially batched setting: the learner will receive the cumulative loss at certain update time points, where both the loss at each round and the update points are determined by the environment (adversarially). In other words, the environment segments the time horizon into BB batches, and the learner can only update its strategy at the end of each batch. We denote the set of update time steps by T={t1,t2,…,tB}\mathcal{T} = \{t_1,t_2,\ldots,t_B\}. Equivalently, the instance can be described by its batch structure B=(b1,b2,…,bB)=(t1−0,t2−t1,…,tB−tB−1)\mathcal{B} = (b_1,b_2,\ldots,b_B) = (t_1-0,t_2-t_1,\ldots,t_B-t_{B-1}).1 We will primarily use the batch structure B\mathcal{B} to specify an instance. We also write Li(j)=∑k=tj−1+1tjli(k)L_i^{(j)} = \sum_{k=t_{j-1}+1}^{t_j} l_i^{(k)} as the cumulative loss of action i∈[N]i \in[N] within batch j∈[B]j \in[B].

We further distinguish between two settings regarding the learner’s knowledge of the batch structure. In the batch-aware setting, the learner is given the entire update time set T\mathcal{T} (or equivalently the batch structure B\mathcal{B}) before the learning process begins. The learner may then leverage this information, e.g., to tune the learning rate. In contrast, in the batch-oblivious setting, the learner does not know the future update times in advance. Instead, the learner only gets notified that a batch has ended at each time step tj∈Tt_j \in\mathcal{T}, and still does not know the future update times tj+1,…,tBt_{j+1},\ldots,t_B.

We instantiate the model of adversarially batched online learning in four canonical settings: stochastic bandits, online convex optimization (OCO), experts problem, and adversarial bandits.

Stochastic Bandits. In stochastic Multi-Armed Bandits (MAB), each of the NN arms is associated with a fixed but unknown reward distribution over [0,1][0,1]. Each pull of an arm results in a reward independently sampled from that distribution. In the adversarially batched setting, the learner commits to a policy that specifies the sequence of arms to be pulled (e.g., a round-robin policy that cycles through 1, 2, . . . , NN). The learner can only update this policy at the end of each batch. Let μi\mu_i denote the mean reward of arm i∈[N]i \in[N], and suppose that the learner pulls arm it∈[N]i_t \in[N] at time tt. Then, the learner incurs a regret of Reg⁡N(T):=T⋅max⁡i∗∈[N]μi∗−∑t=1Tμit\operatorname{Reg}_{N}^{(T)} := T \cdot\max_{i^* \in[N]} \mu_{i^*} - \sum_{t=1}^{T} \mu_{i_t}.

OCO. Let K⊆Rd\mathcal{K} \subseteq\mathbb{R}^d be a nonempty compact convex action set and D:=sup⁡x,y∈K∥x−y∥2D := \sup_{x,y \in\mathcal{K}} \|x-y\|_2 be its Euclidean diameter. At every round t∈[T]t \in[T], the environment chooses a convex loss function ft:K→Rf_t:\mathcal{K} \to\mathbb{R}. We assume that ftf_t is GG-Lipschitz over K\mathcal{K}, i.e., every subgradient g∈∂ft(x)g \in\partial f_t(x) satisfies ∥g∥2≤G\|g\|_2 \le G. In the adversarially batched setting, the learner must use the same action x(j)∈Kx^{(j)} \in\mathcal{K} throughout each batch jj. At the end of each batch, the learner receives first-order feedback for the losses incurred in that batch. Let zj=∑t=tj−1+1tjgtz_j = \sum_{t=t_{j-1}+1}^{t_j} g_t denote the aggregate subgradient in batch jj where gt∈∂ft(x(j))g_t \in\partial f_t(x^{(j)}). Since each ftf_t is GG-Lipschitz, ∥zj∥2≤Gbj\|z_j\|_2 \le G b_j. The regret is measured against the best fixed action in hindsight: Reg⁡=∑j=1B∑t=tj−1+1tjft(x(j))−min⁡x∗∈K∑t=1Tft(x∗)\operatorname{Reg} = \sum_{j=1}^{B}\sum_{t=t_{j-1}+1}^{t_j} f_t(x^{(j)}) - \min_{x^* \in\mathcal{K}} \sum_{t=1}^{T} f_t(x^*).

Experts Problem. In the experts problem, the learner interacts with NN experts. At every round, the learner selects a distribution over the experts and incurs the expected loss under this distribution. The losses of all experts are then revealed to the learner. Formally, let pi(j)p_i^{(j)} denote the probability assigned to expert i∈[N]i \in[N] at batch j∈[B]j \in[B].2 The regret of the learner in the adversarially batched experts problem is then defined as the difference between the cumulative loss of the learner and that of the best fixed expert in hindsight: Reg⁡N(B)=∑j=1B∑i=1N(pi(j)Li(j))−min⁡i∗∈[N]∑j=1BLi∗(j)\operatorname{Reg}_{N}^{(B)} = \sum_{j=1}^{B}\sum_{i=1}^{N} \left(p_i^{(j)}L_i^{(j)}\right) - \min_{i^* \in[N]}\sum_{j=1}^{B}L_{i^*}^{(j)}.

Adversarial Bandits. Similar to the experts problem, an adversarial MAB instance is specified by the losses li(t)∈[0,1]l_i^{(t)} \in[0,1] of all actions (or “arms”) i∈[N]i \in[N] at all time steps t∈[T]t \in[T]. The difference is that the learner, instead of observing all losses after each round, only sees the loss of the chosen arm. Specifically, we study the stricter setting in which the learner commits to a single arm for the entire batch, and only learns the losses associated with that action throughout the batch.

We measure performance by the expected static regret, which is also known as the pseudo-regret, which compares the learner’s expected cumulative loss with the lowest expected loss over all arms in hindsight, i.e., Reg⁡N(B)=E[∑j=1B∑i=1Npi(j)Li(j)−min⁡i∗∈[N]∑j=1BLi∗(j)]\operatorname{Reg}_{N}^{(B)} = \mathbb{E}\left[\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}L_i^{(j)}-\min_{i^* \in[N]}\sum_{j=1}^{B}L_{i^*}^{(j)}\right]. All expectations in the upper bounds are over the learner’s internal randomization, and over the adversary’s initial randomization if it draws the oblivious loss table from a distribution.

Our Results

For each problem, we characterize the effect of the batch structure through matching regret bounds governed by different complexity measures.

Stochastic Bandits

Upper Bounds. Let Δi:=max⁡i∗∈[N]μi∗−μi≥0\Delta_i := \max_{i^* \in[N]} \mu_{i^*} - \mu_i \ge0 denote the gap of arm ii. The well-known Upper Confidence Bound (UCB) algorithm [2] has a gap-dependent regret bound of O((log⁡T)⋅∑i:Δi>01/Δi)O((\log T)\cdot\sum_{i:\Delta_i>0}1/\Delta_i) and a gap-independent bound of O(NTlog⁡N)O(\sqrt{NT\log N}).

For the batched setting, [9] studied an easier setting where the update points are freely chosen by the learner. They proposed an algorithm and proved regret upper bounds under specific batch structures. In particular, given the time horizon TT and the batch number BB, the batch structure bj=Θ(Tj/B)b_j = \Theta(T^{j/B}) leads to an expected regret upper bound of O(T1/Blog⁡Nlog⁡(NT)NΔmin⁡)O\left(T^{1/B}\log N\log(NT)\frac{N}{\Delta_{\min}}\right), where Δmin⁡:=min⁡i:Δi>0Δi\Delta_{\min} := \min_{i:\Delta_i>0}\Delta_i is the minimum non-zero gap.

For our adversarially batched setting, we first introduce a universal complexity measure α\alpha that captures the hardness of an arbitrary batch structure in stochastic bandits.

Definition 1. The hardness metric α\alpha of a batch structure B=(b1,b2,…,bB)\mathcal{B}=(b_1,b_2,\ldots,b_B) is

α:=max⁡jbj∑k=1j−1bk=max⁡jbjtj−1,\alpha:= \max_j \frac{b_j}{\sum_{k=1}^{j-1} b_k} = \max_j \frac{b_j}{t_{j-1}},

where, for brevity, we define t0=1t_0=1 to avoid division by zero.3

Intuitively, α\alpha captures the largest mismatch between a batch length and the evidence available before it. In batch jj, the algorithm commits to bjb_j rounds using only the previous tj−1t_{j-1} observations; hence a large ratio bj/tj−1b_j/t_{j-1} means long blind commitments given limited data, while small ratios mean information keeps pace with commitment length.

References

  1. [1]Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multi-armed bandit problem. Machine learning, 47(2):235–256, 2002. 1.3
  2. [2]Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002. 1.2.1, 1.2.2, 1.3, FDOI
  3. [3]Lilian Besson and Emilie Kaufmann. What doubling tricks can and can’t do for multi-armed bandits. arXiv preprint arXiv:1803.06971, 2018. 1.2.3arxiv.org/abs/1803.06971
  4. [4]Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006. 1, 1.2.2, 1.2.3, 1.3
  5. [5]Mingyu Chen and Xuezhou Zhang. Improved algorithms for adversarial bandits with unbounded losses. arXiv preprint arXiv:2310.01756, 2023. 1.2.2, 1.3, G.2, 10arxiv.org/abs/2310.01756
  6. [7]Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni. Regret bounds for batched bandits. In AAAI Conference on Artificial Intelligence (AAAI), pages 7340–7348, 2021. 1, 1.3arxiv.org/abs/1910.04959
  7. [8]Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. 1.2.2, 1.3, E
  8. [9]Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In Advances in Neural Information Processing Systems (NeurIPS), pages 503–513, 2019. 1, 1.2.1, 1, 1.2.1, 1.2.1, 1.2.1, 1.3, 2, 2, 3, C.1, C.1, C.1arxiv.org/abs/1904.01763
  9. [10]Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Online learning under delayed feedback. In International Conference on Machine Learning (ICML), pages 1453–1461, 2013. 1.3arxiv.org/abs/1306.0686
  10. [11]Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári. Delay-tolerant online convex optimization: Unified analysis and adaptive-gradient algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016. 1.2.2, 1.3, H, 11DOI
  11. [13]Licheng Liu and Mingda Qiao. Online prediction with limited selectivity. In Advances in Neural Information Processing Systems (NeurIPS), 2025. 1.3arxiv.org/abs/2508.09592
  12. [14]Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4–22, 1985. 1.3
  13. [15]Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. 1, 1.3
  14. [16]Nick Littlestone and Manfred K Warmuth. The weighted majority algorithm. Information and computation, 108(2):212–261, 1994. 1.3
  15. [17]Chris Mesterharm. On-line learning with delayed label feedback. In International Conference on Algorithmic Learning Theory, pages 399–413. Springer, 2005. 1.3
  16. [18]Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science, 716:50–69, 2018. 1.2.2, 1.3, G.1, 9arxiv.org/abs/1601.01974
  17. [19]Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit problems. The Annals of Statistics, 44(2):660–681, 2016. 1.3

Paper details

vlnc:W_cd6768yr
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

large language models (LLMs)

View statement
Looking for related papers…
Contents