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\} t ∈ [ T ] := { 1 , 2 , … , 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 B B B 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 = { t 1 , t 2 , … , t B } \mathcal{T} = \{t_1,t_2,\ldots,t_B\} T = { t 1 , t 2 , … , t B } . Equivalently, the instance can be described by its batch structure B = ( b 1 , b 2 , … , b B ) = ( t 1 − 0 , t 2 − t 1 , … , t B − t B − 1 ) \mathcal{B} = (b_1,b_2,\ldots,b_B) = (t_1-0,t_2-t_1,\ldots,t_B-t_{B-1}) B = ( b 1 , b 2 , … , b B ) = ( t 1 − 0 , t 2 − t 1 , … , t B − t B − 1 ) .1 We will primarily use the batch structure B \mathcal{B} B to specify an instance. We also write L i ( j ) = ∑ k = t j − 1 + 1 t j l i ( k ) L_i^{(j)} = \sum_{k=t_{j-1}+1}^{t_j} l_i^{(k)} L i ( j ) = ∑ k = t j − 1 + 1 t j l i ( k ) as the cumulative loss of action i ∈ [ N ] i \in[N] i ∈ [ N ] within batch j ∈ [ B ] j \in[B] j ∈ [ 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} T (or equivalently the batch structure B \mathcal{B} 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 t j ∈ T t_j \in\mathcal{T} t j ∈ T , and still does not know the future update times t j + 1 , … , t B t_{j+1},\ldots,t_B t j + 1 , … , 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 N N N arms is associated with a fixed but unknown reward distribution over [ 0 , 1 ] [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, . . . , N N N ). The learner can only update this policy at the end of each batch. Let μ i \mu_i μ i denote the mean reward of arm i ∈ [ N ] i \in[N] i ∈ [ N ] , and suppose that the learner pulls arm i t ∈ [ N ] i_t \in[N] i t ∈ [ N ] at time t t t . Then, the learner incurs a regret of Reg N ( T ) : = T ⋅ max i ∗ ∈ [ N ] μ i ∗ − ∑ t = 1 T μ i t \operatorname{Reg}_{N}^{(T)} := T \cdot\max_{i^* \in[N]} \mu_{i^*} - \sum_{t=1}^{T} \mu_{i_t} Reg N ( T ) := T ⋅ max i ∗ ∈ [ N ] μ i ∗ − ∑ t = 1 T μ i t .
OCO. Let K ⊆ R d \mathcal{K} \subseteq\mathbb{R}^d K ⊆ R d be a nonempty compact convex action set and D : = sup x , y ∈ K ∥ x − y ∥ 2 D := \sup_{x,y \in\mathcal{K}} \|x-y\|_2 D := sup x , y ∈ K ∥ x − y ∥ 2 be its Euclidean diameter. At every round t ∈ [ T ] t \in[T] t ∈ [ T ] , the environment chooses a convex loss function f t : K → R f_t:\mathcal{K} \to\mathbb{R} f t : K → R . We assume that f t f_t f t is G G G -Lipschitz over K \mathcal{K} K , i.e., every subgradient g ∈ ∂ f t ( x ) g \in\partial f_t(x) g ∈ ∂ f t ( x ) satisfies ∥ g ∥ 2 ≤ G \|g\|_2 \le G ∥ g ∥ 2 ≤ G . In the adversarially batched setting, the learner must use the same action x ( j ) ∈ K x^{(j)} \in\mathcal{K} x ( j ) ∈ K throughout each batch j j j . At the end of each batch, the learner receives first-order feedback for the losses incurred in that batch. Let z j = ∑ t = t j − 1 + 1 t j g t z_j = \sum_{t=t_{j-1}+1}^{t_j} g_t z j = ∑ t = t j − 1 + 1 t j g t denote the aggregate subgradient in batch j j j where g t ∈ ∂ f t ( x ( j ) ) g_t \in\partial f_t(x^{(j)}) g t ∈ ∂ f t ( x ( j ) ) . Since each f t f_t f t is G G G -Lipschitz, ∥ z j ∥ 2 ≤ G b j \|z_j\|_2 \le G b_j ∥ z j ∥ 2 ≤ G b j . The regret is measured against the best fixed action in hindsight: Reg = ∑ j = 1 B ∑ t = t j − 1 + 1 t j f t ( x ( j ) ) − min x ∗ ∈ K ∑ t = 1 T f t ( 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^*) Reg = ∑ j = 1 B ∑ t = t j − 1 + 1 t j f t ( x ( j ) ) − min x ∗ ∈ K ∑ t = 1 T f t ( x ∗ ) .
Experts Problem. In the experts problem , the learner interacts with N N N 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 p i ( j ) p_i^{(j)} p i ( j ) denote the probability assigned to expert i ∈ [ N ] i \in[N] i ∈ [ N ] at batch j ∈ [ B ] j \in[B] j ∈ [ 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 = 1 B ∑ i = 1 N ( p i ( j ) L i ( j ) ) − min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( 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)} Reg N ( B ) = ∑ j = 1 B ∑ i = 1 N ( p i ( j ) L i ( j ) ) − min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( j ) .
Adversarial Bandits. Similar to the experts problem, an adversarial MAB instance is specified by the losses l i ( t ) ∈ [ 0 , 1 ] l_i^{(t)} \in[0,1] l i ( t ) ∈ [ 0 , 1 ] of all actions (or “arms”) i ∈ [ N ] i \in[N] i ∈ [ N ] at all time steps t ∈ [ T ] t \in[T] t ∈ [ 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 = 1 B ∑ i = 1 N p i ( j ) L i ( j ) − min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( 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] Reg N ( B ) = E [ ∑ j = 1 B ∑ i = 1 N p i ( j ) L i ( j ) − min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( j ) ] . 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 Δ i := max i ∗ ∈ [ N ] μ i ∗ − μ i ≥ 0 denote the gap of arm i i i . The well-known Upper Confidence Bound (UCB) algorithm [2 ] has a gap-dependent regret bound of O ( ( log T ) ⋅ ∑ i : Δ i > 0 1 / Δ i ) O((\log T)\cdot\sum_{i:\Delta_i>0}1/\Delta_i) O (( log T ) ⋅ ∑ i : Δ i > 0 1/ Δ i ) and a gap-independent bound of O ( N T log N ) O(\sqrt{NT\log N}) O ( N T 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 T T T and the batch number B B B , the batch structure b j = Θ ( T j / B ) b_j = \Theta(T^{j/B}) b j = Θ ( T j / B ) leads to an expected regret upper bound of O ( T 1 / B log N log ( N T ) N Δ min ) O\left(T^{1/B}\log N\log(NT)\frac{N}{\Delta_{\min}}\right) O ( T 1/ B log N log ( N T ) Δ m i n N ) , where Δ min : = min i : Δ i > 0 Δ i \Delta_{\min} := \min_{i:\Delta_i>0}\Delta_i Δ m i n := min i : Δ i > 0 Δ 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 = ( b 1 , b 2 , … , b B ) \mathcal{B}=(b_1,b_2,\ldots,b_B) B = ( b 1 , b 2 , … , b B ) is
α : = max j b j ∑ k = 1 j − 1 b k = max j b j t j − 1 , \alpha:= \max_j \frac{b_j}{\sum_{k=1}^{j-1} b_k} = \max_j \frac{b_j}{t_{j-1}}, α := j max ∑ k = 1 j − 1 b k b j = j max t j − 1 b j , where, for brevity, we define t 0 = 1 t_0=1 t 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 j j j , the algorithm commits to b j b_j b j rounds using only the previous t j − 1 t_{j-1} t j − 1 observations; hence a large ratio b j / t j − 1 b_j/t_{j-1} b j / t j − 1 means long blind commitments given limited data, while small ratios mean information keeps pace with commitment length.
As a warm-up, we extend the α \alpha α -dependent regret bound of [9 ] (Remark 1) to all batch structures: in Proposition 3 (Appendix § 7 .§ 4 ), we prove an O ~ ( min { T , α N / Δ min } ) \widetilde{O}(\min\{T,\alpha N/\Delta_{\min}\}) O ( min { T , α N / Δ m i n }) regret bound for any batch structure. Our main technical contribution then goes further: we propose a successive-elimination algorithm with merging operations in § 3 , and prove both gap-dependent and gap-independent regret guarantees for adversarially batched stochastic bandits.
Theorem 1. For adversarially batched stochastic bandits with N N N arms and an arbitrary batch structure B \mathcal{B} B with hardness metric α \alpha α , there is an algorithm with a gap-dependent expected regret of
O ( min { T , α 2 log ( N T ) ∑ i : Δ i > 0 1 Δ i } ) . O\left(\min\left\{T,\alpha^2\log(NT)\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\right\}\right). O ( min { T , α 2 log ( N T ) i : Δ i > 0 ∑ Δ i 1 } ) .
Theorem 2. For adversarially batched stochastic bandits with N N N arms and an arbitrary batch structure B \mathcal{B} B with hardness metric α \alpha α , there is an algorithm with a gap-independent expected regret of
O ~ ( min { T , α T N } ) . \widetilde{O}\left(\min\left\{T,\sqrt{\alpha TN}\right\}\right). O ( min { T , α T N } ) .
Compared with [9 ] , our results apply to any batch structure B \mathcal{B} B , rather than only to specially designed ones. Our gap-dependent bound (Theorem 1) replaces the coarse worst-arm dependence N / Δ min N/\Delta_{\min} N / Δ m i n by the standard UCB-type complexity ∑ i : Δ i > 0 Δ i − 1 \sum_{i:\Delta_i>0}\Delta_i^{-1} ∑ i : Δ i > 0 Δ i − 1 , yielding an improvement of up to a factor of N N N in its dependence on the gaps. This refinement costs an additional factor of α \alpha α , but only for the gap-dependent bound. The gap-independent bound, on the other hand, has a better (square root) dependence on the batch hardness measure α \alpha α . In particular, when no batch is significantly longer than the cumulative length of the preceding batches, i.e., α = O ( 1 ) \alpha=O(1) α = O ( 1 ) , both bounds recover the standard non-batched regret rates up to polylogarithmic factors.
Lower Bounds. On the lower-bound side, we show that a polynomial dependence on α \alpha α is unavoidable. Firstly, in Appendix § 8 .§ 1 , we extend the analysis of [9 ] to establish both gap-dependent and gap-independent worst-case lower bounds.
Proposition 1. Suppose t j ∗ − 1 ≥ C N t_{j^*-1}\ge CN t j ∗ − 1 ≥ C N , where j ∗ ∈ arg max j b j / t j − 1 j^*\in\arg\max_j b_j/t_{j-1} j ∗ ∈ arg max j b j / t j − 1 and C C C is a sufficiently large constant. Then, there is a hard instance of adversarially batched stochastic bandits such that every algorithm suffers a gap-dependent regret lower bound of Ω ( α ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α ∑ i : Δ i > 0 Δ i − 1 ) .
Theorem 3. Suppose t j ∗ − 1 ≥ C 1 N t_{j^*-1}\ge C_1N t j ∗ − 1 ≥ C 1 N and t j ∗ − 1 ≥ C 2 T α t_{j^*-1}\ge C_2\frac{T}{\alpha} t j ∗ − 1 ≥ C 2 α T , where j ∗ ∈ arg max j b j / t j − 1 j^*\in\arg\max_j b_j/t_{j-1} j ∗ ∈ arg max j b j / t j − 1 and C 1 , C 2 C_1,C_2 C 1 , C 2 are sufficiently large constants. Then, there is a hard instance of adversarially batched stochastic bandits such that every algorithm suffers a gap-independent regret lower bound of Ω ( α N T ) \Omega(\sqrt{\alpha NT}) Ω ( α N T ) .
Theorem 3 gives a gap-independent lower bound that matches the upper bound in Theorem 2 up to logarithmic factors on a suitable family of hard batch structures. On the other hand, for the gap-dependent setting, Theorem 1 and Proposition 1 still leave a multiplicative gap of α \alpha α . To narrow this gap, in Appendix § 8 .§ 3 we construct a carefully designed hard instance and establish a stronger gap-dependent lower bound with an α 3 / 2 \alpha^{3/2} α 3/2 dependence.
Theorem 4. There exists a hard instance of adversarially batched stochastic bandits such that every algorithm suffers an expected cumulative regret of Ω ( α 3 / 2 ∑ i : Δ i > 0 1 Δ i ) \Omega\left(\alpha^{3/2}\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\right) Ω ( α 3/2 ∑ i : Δ i > 0 Δ i 1 ) .
Moreover, we show in Appendix § 8 .§ 4 that our gap-dependent analysis necessarily leads to an Ω ( α 7 / 4 ) \Omega(\alpha^{7/4}) Ω ( α 7/4 ) factor in the regret bound.
Convex Optimization-based Problems
Batch-Aware Setting. In Appendices § 9 .§ 1 , § 10 .§ 1 and § 11 .§ 1 , we prove the following regret upper bounds for the other three problems with convex optimization formulations under the adversarially batched model, including OCO, the experts problem (which can be formulated as an Online Linear Optimization (OLO) over the probability simplex), and the adversarial bandits (which can be formulated as an instance of bandit convex optimization). The bounds are obtained by classic algorithms: Online Gradient Descent (OGD) [Zin03], Hedge [8 , 4 ] , and EXP3 [2 ] .
Theorem 5. For any batch structure B \mathcal{B} B , the following regret guarantees hold:
In the adversarially batched OCO problem, projected OGD with learning rate η > 0 \eta> 0 η > 0 satisfies Reg ≤ D 2 2 η + η G 2 2 ∥ b ∥ 2 2 \operatorname{Reg} \leq\frac{D^2}{2\eta}+\frac{\eta G^2}{2}\|\mathbf{b}\|_2^2 Reg ≤ 2 η D 2 + 2 η G 2 ∥ b ∥ 2 2 . Setting η = D G ∥ b ∥ 2 \eta=\frac{D}{G\|\mathbf{b}\|_2} η = G ∥ b ∥ 2 D gives a regret upper bound of O ( D G ∥ b ∥ 2 ) O(DG\|\mathbf{b}\|_2) O ( D G ∥ b ∥ 2 ) .
In the adversarially batched experts problem with N N N experts, Hedge with learning rate η > 0 \eta> 0 η > 0 satisfies Reg ≤ ln N η + η 8 ∥ b ∥ 2 2 \operatorname{Reg} \leq\frac{\ln N}{\eta}+\frac{\eta}{8}\|\mathbf{b}\|_2^2 Reg ≤ η l n N + 8 η ∥ b ∥ 2 2 . Setting η = 8 ln N ∥ b ∥ 2 \eta=\frac{\sqrt{8\ln N}}{\|\mathbf{b}\|_2} η = ∥ b ∥ 2 8 l n N gives a regret upper bound of O ( min { ∥ b ∥ 2 log N , T } ) O\left(\min\{\|\mathbf{b}\|_2\sqrt{\log N},T\}\right) O ( min { ∥ b ∥ 2 log N , T } ) .
In the adversarially batched adversarial bandits problem with N N N arms, EXP3 with learning rate η > 0 \eta> 0 η > 0 satisfies Reg ≤ ln N η + η N 2 ∥ b ∥ 2 2 \operatorname{Reg} \leq\frac{\ln N}{\eta}+\frac{\eta N}{2}\|\mathbf{b}\|_2^2 Reg ≤ η l n N + 2 η N ∥ b ∥ 2 2 . Setting η = 2 ln N ∥ b ∥ 2 N \eta=\frac{\sqrt{2\ln N}}{\|\mathbf{b}\|_2\sqrt{N}} η = ∥ b ∥ 2 N 2 l n N bounds the pseudo-regret by O ( min { ∥ b ∥ 2 N log N , T } ) O\left(\min\{\|\mathbf{b}\|_2\sqrt{N\log N},T\}\right) O ( min { ∥ b ∥ 2 N log N , T } ) .
We complement the upper bounds with matching or nearly-matching worst-case lower bounds (up to logarithmic factors) in Appendices § 9 .§ 3 , § 10 .§ 3 and § 11 .§ 3 , demonstrating that the dependence on ∥ b ∥ 2 \|\mathbf{b}\|_2 ∥ b ∥ 2 is unavoidable. For OCO, the lower bound holds for every fixed batch structure, whereas for experts and adversarial bandits we establish the corresponding worst-case lower bounds under an additional mild assumption on the maximum batch length.
Theorem 6. The following lower bounds hold for adversarially batched online learning:
For every batch structure B \mathcal{B} B , every algorithm for adversarially batched OCO suffers an expected regret of Ω ( D G ∥ b ∥ 2 ) \Omega(DG\|\mathbf{b}\|_2) Ω ( D G ∥ b ∥ 2 ) .
For every N ≥ 2 N \geq2 N ≥ 2 and batch structure B \mathcal{B} B , every algorithm has a worst-case regret of Ω ( ∥ b ∥ 2 ) \Omega(\|\mathbf{b}\|_2) Ω ( ∥ b ∥ 2 ) . Moreover, assuming max i ∈ [ B ] b i ≤ O ( ∥ b ∥ 2 / log N ) \max_{i\in[B]}b_i \leq O(\|\mathbf{b}\|_2/\sqrt{\log N}) max i ∈ [ B ] b i ≤ O ( ∥ b ∥ 2 / log N ) , the regret is at least Ω ( ∥ b ∥ 2 log N ) \Omega(\|\mathbf{b}\|_2\sqrt{\log N}) Ω ( ∥ b ∥ 2 log N ) .
For every N ≥ 2 N \geq2 N ≥ 2 and batch structure B \mathcal{B} B , every algorithm has a worst-case pseudo-regret of Ω ( min { ∥ b ∥ 2 N , ∥ b ∥ 2 2 b max } ) \Omega\left(\min\left\{\|\mathbf{b}\|_2\sqrt{N},\frac{\|\mathbf{b}\|_2^2}{b_{\max}}\right\}\right) Ω ( min { ∥ b ∥ 2 N , b m a x ∥ b ∥ 2 2 } ) , where b max = max j ∈ [ B ] b j b_{\max}=\max_{j\in[B]}b_j b m a x = max j ∈ [ B ] b j . In particular, if b max ≤ O ( ∥ b ∥ 2 N ) b_{\max}\leq O(\|\mathbf{b}\|_2\sqrt{N}) b m a x ≤ O ( ∥ b ∥ 2 N ) , then the pseudo-regret is lower bounded by Ω ( ∥ b ∥ 2 N ) \Omega(\|\mathbf{b}\|_2\sqrt{N}) Ω ( ∥ b ∥ 2 N ) .
Batch-Oblivious Setting. The algorithms in Theorem 5 are batch-aware, since the optimal learning rate depends on the quantity ∥ b ∥ 2 \|\mathbf{b}\|_2 ∥ b ∥ 2 . Towards extending the upper bound to the batch-oblivious setting, we show in Appendices G and H that algorithms from scale-free and delayed-feedback online learning can be adapted. Specifically, for scale-free online learning, we treat each batch as a meta-round and deploy SOLO FTRL [18 ] for OCO and the experts problem, and UMAB-NN [5 ] for adversarial bandits, to recover the same order of upper bounds. For delayed-feedback models, we view batched feedback as a special case of delayed feedback and apply the delay-adaptive algorithms of [11 ] to OCO and the experts problem. We note that existing delayed-feedback results do not directly apply to the stricter adversarial bandits setting studied here, as they typically allow the learner to select new arms while feedback from previous rounds remains outstanding.
An Adaptive Doubling Trick
The reductions above recover batch-oblivious guarantees through existing scale-free or delay-adaptive algorithms. We additionally provide a generic conversion that preserves the choice of the base algorithm: As shown in Theorem 7, any restartable algorithm satisfying the fixed-learning-rate bound and instantaneous-regret condition, which bounds the regret incurred in any single round against any comparator by O ( A D ) O(\sqrt{AD}) O ( A D ) , can be made batch-oblivious using only learning-rate selection and restarts, with no additional logarithmic factor in its regret guarantee.
Theorem 7. Consider a base online learning algorithm A η \mathcal{A}_{\eta} A η , parametrized by a learning rate η > 0 \eta> 0 η > 0 . Suppose that there exist known quantities A , D > 0 A,D > 0 A , D > 0 , such that whenever A η \mathcal{A}_{\eta} A η is run from scratch on any batch structure B \mathcal{B} B , its regret satisfies Reg ( A η ) = O ( A η + D η ∥ b ∥ 2 2 ) \operatorname{Reg}(\mathcal{A}_{\eta}) = O\left(\frac{A}{\eta} + D\eta\lVert b\rVert_{2}^{2}\right) Reg ( A η ) = O ( η A + D η ∥ b ∥ 2 2 ) . Suppose the instantaneous regret against any comparator is at most L L L , where L = O ( A D ) L = O(\sqrt{AD}) L = O ( A D ) . Then, there exists a batch-oblivious algorithm whose regret satisfies O ( A D ∥ b ∥ 2 ) O\left(\sqrt{AD}\lVert b\rVert_{2}\right) O ( A D ∥ b ∥ 2 ) .
In particular, Theorem 7 allows OGD, Hedge, and EXP3 to retain their batch-aware rates without requiring advance knowledge of the batch structure. The main difficulty is that a batch may overshoot the current budget by an arbitrarily large amount before its length becomes known. Proposition 2 (proved in Appendix § 14 ) shows a naïve implementation of the standard doubling trick [4 , 3 ] can fail dramatically. In contrast, our analysis controls this batch separately, and the next budget is calibrated to the realized sum of squared batch lengths.
Proposition 2. There exists a family of instances of the adversarially batched experts problem on which the naïve doubling-trick adaptation of Hedge incurs an Ω ( T ) \Omega(T) Ω ( T ) regret, whereas a batch-aware algorithm can achieve an O ( T 3 / 4 ) O(T^{3/4}) O ( T 3/4 ) regret.
Related Work
Our work builds on the vast literature on online learning, including stochastic MAB [14 , 1 ] , OCO [Zin03], the experts problem [16 , 8 ] , and adversarial bandits [1 ] . We refer the reader to [4 , 15 ] for a comprehensive introduction.
Selective Prediction with Limited Selectivity. Most similar to our setup is the recent work of [13 ] , which builds on the selective prediction formulation of [Drul3, QV19] and studies a variant in which the forecaster can only initiate predictions at a prescribed subset of time steps. Their setting can be viewed as prediction-focused in the sense that restrictions are imposed on when predictions may be made, whereas we generalize this timing constraint to regret minimization in online learning, covering the stochastic bandits, OCO, the experts problem, and adversarial bandits.
Batched Bandits. The constraint of batched feedback in multi-armed bandits has garnered significant attention recently. The seminal work of [19 ] characterized the minimax regret for stochastic bandits with a limited number of batches, showing that O ( log T ) O(\log T) O ( log T ) batches are sufficient to achieve the optimal O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) regret. [9 ] extended this by analyzing the trade-off between the number of batches and regret, introducing a “grid” structure. [7 ] further improved these bounds for specific batch structures. [JTX^{+}21] studied the anytime version of batched bandits and developed algorithms that allow the learner to adaptively choose update points while approaching the minimal batch complexity. Crucially, these works generally assume the learner can design the grid (e.g., the batch structure) to minimize the regret. Our setting differs fundamentally: the batch structure is adversarial and imposed by the environment, forcing the learner to act under external constraints rather than optimizing the schedule.
Scale-Free and Loss-Adaptive Online Learning. Existing online learning frameworks can potentially be deployed in the adversarially batched model through batch-level aggregation. In this study, we show batch-oblivious reductions in the experts problem and adversarial bandits using scale-free and loss-adaptive online learning. Specifically, [18 ] developed scale-free online learning algorithms whose regret guarantees adapt to the observed magnitudes of the loss vectors. By treating each batch as a single meta-round, SOLO FTRL can be directly deployed for OCO and the experts problem while retaining the desired dependence on the realized batch lengths. For adversarial bandits, an analogous reduction uses the unbounded-loss bandit algorithm of [5 ] .
Delayed Feedback Model. Our problem is also related to online learning with delayed feedback [17 , 10 , 11 SLAM25] . For OCO and the experts problem , similar to scale-free reductions (Appendix § 12 ), we show in Appendix § 13 that delayed-feedback models can be reduced to obtain the same order of batch-oblivious regret upper bounds. In contrast, existing delayed-bandit results do not directly apply to our adversarial bandits problem, which requires the learner to commit to a single arm throughout each batch. For stochastic bandits , existing delayed-feedback results [10 SLAM25] typically incur an additive penalty on top of the standard regret, controlled by absolute delay . In the adversarially batched setting, this can be expressed as O ( min { T , ∑ i : Δ i > 0 log T Δ i + b max ∑ i : Δ i > 0 Δ i } ) \mathcal{O}\left(\min\left\{T,\sum_{i:\Delta_i>0}\frac{\log T}{\Delta_i}+b_{\max}\sum_{i:\Delta_i>0}\Delta_i\right\}\right) O ( min { T , ∑ i : Δ i > 0 Δ i l o g T + b m a x ∑ i : Δ i > 0 Δ i } ) or O ~ ( min { T , N T + N b max } ) \widetilde{\mathcal{O}}\left(\min\left\{T,\sqrt{NT}+Nb_{\max}\right\}\right) O ( min { T , N T + N b m a x } ) , where b max : = max j b j b_{\max}:=\max_j b_j b m a x := max j b j . In contrast, our analysis provides a multiplicative characterization through the relative growth measure α \alpha α . Consequently, we provide complementary bounds that can be substantially sharper whenever batch sizes are large but remain controlled relative to the accumulated history. For example, under geometrically growing batches, the maximum batch length and the number of outstanding observations can be Θ ( T ) \Theta(T) Θ ( T ) , whereas α = Θ ( 1 ) \alpha=\Theta(1) α = Θ ( 1 ) .
Stochastic Bandits
Our algorithm (Algorithm 1) builds on the Batched Successive Elimination algorithm of [9 ] , with an additional merging operation. Specifically, let γ > 0 \gamma>0 γ > 0 be a constant parameter associated with the UCB bound. Let A j A_j A j denote the set of active arms at the beginning of batch j j j and n j : = ∣ A j ∣ n_j:=|A_j| n j := ∣ A j ∣ . Then, S j : = ∑ k = 1 j b k S_j:=\sum_{k=1}^{j}b_k S j := ∑ k = 1 j b k is the total number of times arm i ∈ A j i\in A_j i ∈ A j is pulled by the end of batch j j j (i.e., at time step t j t_j t j ).4 Algorithm 1 eliminates every arm with an empirical mean that is lower, by a margin of at least γ ln ( N T ) S j \sqrt{\frac{\gamma\ln(NT)}{S_j}} S j γ l n ( N T ) , than the highest empirical mean μ ^ a ∗ \hat{\mu}_{a_*} μ ^ a ∗ .
A Gap-Dependent Upper Bound. To analyze Algorithm 1, we define j i j_i j i to be the index of the block after which arm i i i is intended to be eliminated. Recall that Δ i = max i ∗ ∈ [ N ] ∣ μ i ∗ − μ i ∣ \Delta_i=\max_{i^*\in[N]}|\mu_{i^*}-\mu_i| Δ i = max i ∗ ∈ [ N ] ∣ μ i ∗ − μ i ∣ is the gap of arm i i i . Then, j i j_i j i is formally defined as j i : = min { j ∈ [ B ] : S j ≥ 4 γ ln ( N T ) Δ i 2 } j_i:=\min\left\{j\in[B]:S_j\ge\frac{4\gamma\ln(NT)}{\Delta_i^2}\right\} j i := min { j ∈ [ B ] : S j ≥ Δ i 2 4 γ l n ( N T ) } if this set is nonempty; otherwise, we define j i = B + 1 j_i=B+1 j i = B + 1 .
Algorithm 1 Batched Arm Elimination with Merging
Require: Time horizon $T$. Number of arms $N$. Parameter $\gamma > 0$.
1: Initialize $j \leftarrow 1; A_1 \leftarrow [N]; b_j \leftarrow 0$; ▷ all arms are active
2: for $t = 1, 2, \ldots, T$ do
3: Pull the least-pulled arm in $A_j$; ▷ pull active arms in a round-robin fashion
4: $b_j \leftarrow b_j + 1$; ▷ track batch length
5: if $t$ is among the updating time steps then
6: Update the empirical mean $\hat{\mu}_a$ for each arm $a \in A_j$;
7: if $j = 1$ or $b_j \ge 2 \cdot b_{j-1}$ then ▷ the merged batch is long enough
8: $A_{j+1} \leftarrow \left\{a \in A_j : \max_{a^* \in A_j} \hat{\mu}_{a^*} - \hat{\mu}_a \le \sqrt{\frac{\gamma \log(NT)}{S_j}}\right\}$; ▷ eliminate arms
9: $j \leftarrow j + 1; b_j \leftarrow 0$;
10: end if
11: end if
12: end for
We will condition on a “good event” E g o o d \mathcal{E}^{\mathrm{good}} E good defined as follows: (1) the optimal arm i ∗ i^* i ∗ remains active throughout the algorithm; (2) every sub-optimal arm i i i with Δ i > 0 \Delta_i > 0 Δ i > 0 and j i ≤ B j_i \le B j i ≤ B is eliminated by the end of batch j i j_i j i . Lemma 1, proved in Appendix § 7 .§ 1 , upper bounds the probability that E g o o d \mathcal{E}^{\mathrm{good}} E good does not happen by 1 / T 1/T 1/ T . The contribution of this case to the expected regret is at most T ⋅ 1 T = 1 T \cdot\frac{1}{T} = 1 T ⋅ T 1 = 1 . Then, Lemma 2 upper bounds the regret assuming event E g o o d \mathcal{E}^{\mathrm{good}} E good . These two lemmas together yield Theorem 1. We provide a brief proof sketch below for Lemma 2 and defer the full proof to Appendix § 7 .§ 3 .
Lemma 1. Pr [ E g o o d ] ≥ 1 − 1 / T \Pr[\mathcal{E}^{\mathrm{good}}] \ge1 - 1/T Pr [ E good ] ≥ 1 − 1/ T .
Lemma 2. Conditioned on E g o o d \mathcal{E}^{\mathrm{good}} E good , Algorithm 1 has regret O ( α 2 log ( N T ) ∑ i : Δ i > 0 Δ i − 1 ) O\left(\alpha^2 \log(NT) \sum_{i:\Delta_i>0} \Delta_i^{-1}\right) O ( α 2 log ( N T ) ∑ i : Δ i > 0 Δ i − 1 ) .
Proof sketch of Lemma 2. Suppose that a sub-optimal arm i i i remains active at the beginning of block j j j , i.e., it has not been eliminated by the end of block j − 1 j - 1 j − 1 . By the definition of j i j_i j i and the good event, we have Δ i ≤ 4 γ ln ( N T ) S j − 1 \Delta_i \le\sqrt{\frac{4\gamma\ln(NT)}{S_{j-1}}} Δ i ≤ S j − 1 4 γ l n ( N T ) . Then, the total regret incurred by arms eliminated at the end of block j j j is at most ( n j − n j + 1 ) S j 4 γ ln ( N T ) S j − 1 (n_j - n_{j+1})S_j\sqrt{\frac{4\gamma\ln(NT)}{S_{j-1}}} ( n j − n j + 1 ) S j S j − 1 4 γ l n ( N T ) , where n j n_j n j is the number of active arms during block j j j and S j = ∑ k = 1 j b k n k S_j = \sum_{k=1}^{j} \frac{b_k}{n_k} S j = ∑ k = 1 j n k b k is the number of pulls per active arm up to the end of block j j j . Assume for simplicity that the block lengths grow geometrically except for the last one, i.e., b j ≥ 2 b j − 1 b_j \ge2b_{j-1} b j ≥ 2 b j − 1 for all j ∈ [ B − 1 ] j \in[B - 1] j ∈ [ B − 1 ] while b B ≤ 2 b B − 1 b_B \le2b_{B-1} b B ≤ 2 b B − 1 . Under this assumption, we can show that t j < 2 b j t_j < 2b_j t j < 2 b j and S j = Θ ( b j / n j ) S_j = \Theta(b_j/n_j) S j = Θ ( b j / n j ) . The total conditional regret is then bounded by O ( log ( N T ) ) O(\sqrt{\log(NT)}) O ( log ( N T ) ) times
∑ j = 1 B ( n j − n j + 1 ) b j n j n j − 1 b j − 1 . (1) \sum_{j=1}^{B}(n_j-n_{j+1})\frac{b_j}{n_j}\sqrt{\frac{n_{j-1}}{b_{j-1}}}. \tag*{(1)} j = 1 ∑ B ( n j − n j + 1 ) n j b j b j − 1 n j − 1 . (1)
On the other hand, the ∑ i : Δ i > 0 1 / Δ i \sum_{i:\Delta_i>0} 1/\Delta_i ∑ i : Δ i > 0 1/ Δ i term in the target bound is at least, up to a log ( N T ) \sqrt{\log(NT)} log ( N T ) factor,
∑ j = 1 B ( n j − n j + 1 ) b j − 1 n j − 1 . (2) \sum_{j=1}^{B}(n_j-n_{j+1})\sqrt{\frac{b_{j-1}}{n_{j-1}}}. \tag*{(2)} j = 1 ∑ B ( n j − n j + 1 ) n j − 1 b j − 1 . (2)
To bound Equation (1) by Equation (2) , we split blocks into two types. For the first type, the active set size does not shrink too quickly, i.e., n j ≥ n j − 1 / ( C α ) n_j \ge n_{j-1}/(C\alpha) n j ≥ n j − 1 / ( C α ) for a constant C C C . For each such block j j j , the bounds b j ≤ O ( α ) ⋅ b j − 1 b_j \le O(\alpha) \cdot b_{j-1} b j ≤ O ( α ) ⋅ b j − 1 and n j ≥ n j − 1 / O ( α ) n_j \ge n_{j-1}/O(\alpha) n j ≥ n j − 1 / O ( α ) directly imply that the j j j th term in (1) is at most O ( α 2 ) O(\alpha^2) O ( α 2 ) times the corresponding term in (2) . For the second type, the active set shrinks rapidly, i.e., n j < n j − 1 / ( C α ) n_j < n_{j-1}/(C\alpha) n j < n j − 1 / ( C α ) . Whenever we have consecutive blocks j 0 , j 0 + 1 , … , j 1 j_0, j_0+1,\ldots,j_1 j 0 , j 0 + 1 , … , j 1 of this type, their contribution to (1) forms a vanishing geometric series, and can be charged to the preceding block (i.e., the ( j 0 − 1 ) (j_0-1) ( j 0 − 1 ) -th term), which is then controlled by O ( α 2 ) O(\alpha^2) O ( α 2 ) times the corresponding term in (2) .
Taking both block types into account, we have ∑ j = 1 B ( n j − n j + 1 ) b j n j n j − 1 b j − 1 ≤ O ( α 2 ) ∑ j = 1 B ( n j − n j + 1 ) b j − 1 n j − 1 \sum_{j=1}^{B}(n_j-n_{j+1})\frac{b_j}{n_j}\sqrt{\frac{n_{j-1}}{b_{j-1}}}\leq O(\alpha^2)\sum_{j=1}^{B}(n_j-n_{j+1})\sqrt{\frac{b_{j-1}}{n_{j-1}}} ∑ j = 1 B ( n j − n j + 1 ) n j b j b j − 1 n j − 1 ≤ O ( α 2 ) ∑ j = 1 B ( n j − n j + 1 ) n j − 1 b j − 1 , which establishes the O ( α 2 log ( N T ) ∑ i : Δ i > 0 1 Δ i ) O\left(\alpha^2\log(NT)\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\right) O ( α 2 log ( N T ) ∑ i : Δ i > 0 Δ i 1 ) regret bound. For a general block structure, the algorithm merges consecutive blocks so that the resulting block sequence B ′ B' B ′ satisfies the above geometric-growth condition. The merging only changes the complexity measure α \alpha α by at most a constant factor, namely, α ( B ′ ) ≤ 4 α ( B ) + 2 \alpha(B')\leq4\alpha(B)+2 α ( B ′ ) ≤ 4 α ( B ) + 2 . Therefore, the same regret bound holds for the original adversarially batched instance.
An Improved Gap-dependent Lower Bound. Towards narrowing the gap between the gap-dependent upper and lower bounds, we strengthen the lower bound extended from [9 ] from Ω ( α ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α ∑ i : Δ i > 0 Δ i − 1 ) (Proposition 1) to Ω ( α 3 / 2 ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha^{3/2}\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α 3/2 ∑ i : Δ i > 0 Δ i − 1 ) (Theorem 4) by constructing a carefully designed hard instance. Specifically, we randomly hide a pair of nearly tied Bernoulli arms among N N N arms and adopt a three-batch structure of lengths ( N , N 2 , N 3 ) (N,N^2,N^3) ( N , N 2 , N 3 ) , so that with constant probability the learner allocates only O ( N ) O(N) O ( N ) samples to the two special arms before the last batch and hence cannot reliably distinguish the better one, resulting in Ω ( N 5 / 2 ) = Ω ( α 3 / 2 ∑ i : Δ i > 0 Δ i − 1 ) \Omega(N^{5/2})=\Omega\left(\alpha^{3/2}\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( N 5/2 ) = Ω ( α 3/2 ∑ i : Δ i > 0 Δ i − 1 ) . The full proof of Theorem 4 is deferred to Appendix C.2.
A Gap-Independent Upper Bound. We now prove the gap-independent regret bound of Algorithm 1 (Theorem 2) via a simple application of the Cauchy-Schwarz inequality [Sch90].
Proof of Theorem 2. For each arm i ∈ [ N ] i\in[N] i ∈ [ N ] , let τ i \tau_i τ i denote the number of blocks in which it remains active. We will condition on event E g o o d \mathcal{E}^{\mathrm{good}} E good , under which τ i ≤ j i \tau_i\leq j_i τ i ≤ j i holds for every i ∈ [ N ] i\in[N] i ∈ [ N ] . Then, arm i i i is pulled S τ i S_{\tau_i} S τ i times throughout the algorithm. By definition of the regret, we have
Reg N ( T ) = ∑ i : Δ i > 0 ( Δ i S τ i ) ⋅ S τ i ≤ ∑ i : Δ i > 0 Δ i 2 S τ i ⋅ ∑ i : Δ i > 0 S τ i ≤ ∑ i : Δ i > 0 Δ i 2 S τ i ⋅ T . \operatorname{Reg}_{N}^{(T)}=\sum_{i:\Delta_i>0}\left(\Delta_i\sqrt{S_{\tau_i}}\right)\cdot\sqrt{S_{\tau_i}}\leq\sqrt{\sum_{i:\Delta_i>0}\Delta_i^2S_{\tau_i}}\cdot\sqrt{\sum_{i:\Delta_i>0}S_{\tau_i}}\leq\sqrt{\sum_{i:\Delta_i>0}\Delta_i^2S_{\tau_i}}\cdot\sqrt{T}. Reg N ( T ) = i : Δ i > 0 ∑ ( Δ i S τ i ) ⋅ S τ i ≤ i : Δ i > 0 ∑ Δ i 2 S τ i ⋅ i : Δ i > 0 ∑ S τ i ≤ i : Δ i > 0 ∑ Δ i 2 S τ i ⋅ T .
where the second step applies the Cauchy-Schwarz inequality. Let π 1 , π 2 , … , π N ∈ [ N ] \pi_1,\pi_2,\ldots,\pi_N\in[N] π 1 , π 2 , … , π N ∈ [ N ] be a permutation of the N N N arms in the order in which they are eliminated. Formally, we break ties arbitrarily and list all arms that remain active at the end of the list. For each i ∈ [ N ] i\in[N] i ∈ [ N ] , let σ i ∈ [ N ] \sigma_i\in[N] σ i ∈ [ N ] be the index of arm i i i in permutation π \pi π . By definition, whenever arm i i i remains active in the algorithm, the number of active arms is at least N − σ i + 1 N-\sigma_i+1 N − σ i + 1 . For each arm i i i with Δ i > 0 \Delta_i>0 Δ i > 0 , we have
S τ i = ∑ k = 1 τ i b k n k ≤ ∑ k = 1 τ i − 1 b k N − σ i + 1 = t τ i N − σ i + 1 ≤ ( 1 + α ) t τ i − 1 N − σ i + 1 . S_{\tau_i}=\sum_{k=1}^{\tau_i}\frac{b_k}{n_k}\leq\frac{\sum_{k=1}^{\tau_i-1}b_k}{N-\sigma_i+1}=\frac{t_{\tau_i}}{N-\sigma_i+1}\leq\frac{(1+\alpha)t_{\tau_i-1}}{N-\sigma_i+1}. S τ i = k = 1 ∑ τ i n k b k ≤ N − σ i + 1 ∑ k = 1 τ i − 1 b k = N − σ i + 1 t τ i ≤ N − σ i + 1 ( 1 + α ) t τ i − 1 .
where the last inequality also holds for τ i = 1 \tau_i=1 τ i = 1 under the convention t 0 = 1 t_0=1 t 0 = 1 . Also note that S j ≥ ∑ k = 1 j b k / N = t j / N S_j\geq\sum_{k=1}^{j}b_k/N=t_j/N S j ≥ ∑ k = 1 j b k / N = t j / N . If τ i ≥ 2 \tau_i\geq2 τ i ≥ 2 , then τ i − 1 < j i \tau_i-1<j_i τ i − 1 < j i , so the definition of j i j_i j i gives
t τ i − 1 ≤ N S τ i − 1 < 4 γ N ln ( N T ) Δ i 2 . t_{\tau_i-1}\leq NS_{\tau_i-1}<\frac{4\gamma N\ln(NT)}{\Delta_i^2}. t τ i − 1 ≤ N S τ i − 1 < Δ i 2 4 γ N ln ( N T ) .
For τ i = 1 \tau_i = 1 τ i = 1 , the same upper bound on t τ i − 1 = t 0 = 1 t_{\tau_i-1} = t_0 = 1 t τ i − 1 = t 0 = 1 holds since Δ i ≤ 1 \Delta_i \le1 Δ i ≤ 1 and γ \gamma γ is sufficiently large. Therefore, using α ≥ 1 \alpha\ge1 α ≥ 1 , we obtain S τ i ≤ O ( α ) ⋅ N ln ( N T ) ( N − σ i + 1 ) Δ i 2 S_{\tau_i} \le O(\alpha) \cdot\frac{N\ln(NT)}{(N-\sigma_i+1)\Delta_i^2} S τ i ≤ O ( α ) ⋅ ( N − σ i + 1 ) Δ i 2 N l n ( N T ) . Consequently, on E g o o d \mathcal{E}^{\mathrm{good}} E good ,
Reg N ( T ) ≤ ∑ i : Δ i > 0 Δ i 2 S τ i ⋅ T ≤ O ( α ) ⋅ T ∑ i : Δ i > 0 N ln ( N T ) N − σ i + 1 . \operatorname{Reg}^{(T)}_N \le\sqrt{\sum_{i:\Delta_i>0}\Delta_i^2S_{\tau_i}\cdot T} \le O(\sqrt{\alpha})\cdot\sqrt{T\sum_{i:\Delta_i>0}\frac{N\ln(NT)}{N-\sigma_i+1}}. Reg N ( T ) ≤ i : Δ i > 0 ∑ Δ i 2 S τ i ⋅ T ≤ O ( α ) ⋅ T i : Δ i > 0 ∑ N − σ i + 1 N ln ( N T ) .
Finally, ∑ i : Δ i > 0 ( N − σ i + 1 ) − 1 ≤ ∑ i = 1 N 1 / i = O ( log N ) \sum_{i:\Delta_i>0}(N-\sigma_i+1)^{-1}\le\sum_{i=1}^{N}1/i=O(\log N) ∑ i : Δ i > 0 ( N − σ i + 1 ) − 1 ≤ ∑ i = 1 N 1/ i = O ( log N ) gives a bound of O ~ ( α T N ) \widetilde{O}(\sqrt{\alpha TN}) O ( α T N ) . Combining with the trivial bound T T T and O ( 1 ) O(1) O ( 1 ) regret from the complement of E g o o d \mathcal{E}^{\mathrm{good}} E good completes the proof. □
Table 2.
An Adaptive Doubling Trick
To prove Theorem 7, we introduce an adaptive doubling trick algorithm, as shown in Algorithm 2. The algorithm maintains an epoch-wise guess g ( r ) g^{(r)} g ( r ) for the sum of squared batch lengths, and runs A η \mathcal{A}_\eta A η with learning rate η ( r ) = A / ( D g ( r ) ) \eta^{(r)}=\sqrt{A/(Dg^{(r)})} η ( r ) = A / ( D g ( r ) ) . Within each epoch, it tracks the observed quantity a ( r ) = ∑ b j 2 a^{(r)}=\sum b_j^2 a ( r ) = ∑ b j 2 and starts a new epoch once a ( r ) ≥ g ( r ) a^{(r)}\ge g^{(r)} a ( r ) ≥ g ( r ) . The next guess is set to twice the realized sum in epoch r r r , i.e., g ( r + 1 ) = 2 a ( r ) g^{(r+1)}=2a^{(r)} g ( r + 1 ) = 2 a ( r ) . Thereby, the learning rate is recalibrated only when the observed batch complexity outgrows the current guess, yielding regret controlled by the realized squared-batch mass across epochs.
Proof of Theorem 7. Let R R R be the index of the last non-empty epoch, and let Reg ( r ) \operatorname{Reg}^{(r)} Reg ( r ) denote the regret incurred in epoch r ∈ { 0 , 1 , … , R } r\in\{0,1,\ldots,R\} r ∈ { 0 , 1 , … , R } . For randomized algorithms, all regret bounds below are understood in expectation. By sub-additivity of regret, it suffices to bound each Reg ( r ) \operatorname{Reg}^{(r)} Reg ( r ) separately. Let L L L denote the upper bound on instantaneous regret implied by the problem setup. Note that L = O ( A D ) L=O(\sqrt{AD}) L = O ( A D ) by the precondition of the theorem.
Regret in epoch 0. Since epoch 0 consists of a single block of length b 1 b_1 b 1 , Reg ( 0 ) ≤ L b 1 = L a ( 0 ) = O ( A D a ( 0 ) ) \operatorname{Reg}^{(0)} \le Lb_1 = L\sqrt{a^{(0)}} = O\left(\sqrt{ADa^{(0)}}\right) Reg ( 0 ) ≤ L b 1 = L a ( 0 ) = O ( A D a ( 0 ) ) . If R = 0 R = 0 R = 0 , this already proves the desired bound. Henceforth, assume R ≥ 1 R \ge1 R ≥ 1 .
Regret within epochs 1, 2, … \ldots … , R R R . Fix r ∈ [ R ] r \in[R] r ∈ [ R ] and suppose that epoch r r r spans blocks j 0 , j 0 + 1 , … , j 1 j_0, j_0 + 1, \ldots, j_1 j 0 , j 0 + 1 , … , j 1 . The regret can be decomposed into two parts: Reg ( r ) ≤ Reg g u e s s ( r ) + Reg r e m a i n ( r ) \operatorname{Reg}^{(r)} \le\operatorname{Reg}^{(r)}_{\mathrm{guess}} + \operatorname{Reg}^{(r)}_{\mathrm{remain}} Reg ( r ) ≤ Reg guess ( r ) + Reg remain ( r ) , where Reg g u e s s ( r ) \operatorname{Reg}^{(r)}_{\mathrm{guess}} Reg guess ( r ) is the regret in blocks j 0 j_0 j 0 through j 1 − 1 j_1 - 1 j 1 − 1 and Reg r e m a i n ( r ) \operatorname{Reg}^{(r)}_{\mathrm{remain}} Reg remain ( r ) is the regret within the last block j 1 j_1 j 1 . For the first part Reg g u e s s ( r ) \operatorname{Reg}^{(r)}_{\mathrm{guess}} Reg guess ( r ) , note that Algorithm 2 guarantees ∑ j = j 0 j 1 − 1 b j 2 < g ( r ) \sum_{j=j_0}^{j_1-1} b_j^2 < g^{(r)} ∑ j = j 0 j 1 − 1 b j 2 < g ( r ) ; otherwise, epoch r r r should have finished after block j 1 − 1 j_1 - 1 j 1 − 1 . Also recall that Algorithm 2 sets η ( r ) = A / ( D g ( r ) ) \eta^{(r)} = \sqrt{A/(Dg^{(r)})} η ( r ) = A / ( D g ( r ) ) . For a fixed batch structure, the epoch boundaries are deterministic. Thus, applying the regret guarantee of A η A_\eta A η to blocks j 0 j_0 j 0 through j 1 − 1 j_1 - 1 j 1 − 1 gives
Reg g u e s s ( r ) ≤ O ( A η ( r ) + D η ( r ) ∑ j = j 0 j 1 − 1 b j 2 ) ≤ O ( A η ( r ) + D η ( r ) g ( r ) ) = O ( A D g ( r ) ) . \operatorname{Reg}^{(r)}_{\mathrm{guess}} \le O\left(\frac{A}{\eta^{(r)}} + D\eta^{(r)} \sum_{j=j_0}^{j_1-1} b_j^2\right) \le O\left(\frac{A}{\eta^{(r)}} + D\eta^{(r)}g^{(r)}\right) = O\left(\sqrt{ADg^{(r)}}\right). Reg guess ( r ) ≤ O ( η ( r ) A + D η ( r ) j = j 0 ∑ j 1 − 1 b j 2 ) ≤ O ( η ( r ) A + D η ( r ) g ( r ) ) = O ( A D g ( r ) ) .
If this prefix is empty, its regret is zero, and the same bound holds. Since g ( r ) = 2 a ( r − 1 ) g^{(r)} = 2a^{(r-1)} g ( r ) = 2 a ( r − 1 ) , we have Reg g u e s s ( r ) = O ( A D a ( r − 1 ) ) \operatorname{Reg}^{(r)}_{\mathrm{guess}} = O\left(\sqrt{ADa^{(r-1)}}\right) Reg guess ( r ) = O ( A D a ( r − 1 ) ) . The second part Reg r e m a i n ( r ) \operatorname{Reg}^{(r)}_{\mathrm{remain}} Reg remain ( r ) is upper bounded by L b j 1 Lb_{j_1} L b j 1 . Since a ( r ) = ∑ j = j 0 j 1 b j 2 ≥ b j 1 2 a^{(r)} = \sum_{j=j_0}^{j_1} b_j^2 \ge b_{j_1}^2 a ( r ) = ∑ j = j 0 j 1 b j 2 ≥ b j 1 2 , we have Reg r e m a i n ( r ) ≤ L a ( r ) = O ( A D a ( r ) ) \operatorname{Reg}^{(r)}_{\mathrm{remain}} \le L\sqrt{a^{(r)}} = O\left(\sqrt{ADa^{(r)}}\right) Reg remain ( r ) ≤ L a ( r ) = O ( A D a ( r ) ) . Thus,
Reg ( r ) ≤ Reg g u e s s ( r ) + Reg r e m a i n ( r ) ≤ O ( A D a ( r − 1 ) + A D a ( r ) ) . \operatorname{Reg}^{(r)} \le\operatorname{Reg}^{(r)}_{\mathrm{guess}} + \operatorname{Reg}^{(r)}_{\mathrm{remain}} \le O\left(\sqrt{ADa^{(r-1)}} + \sqrt{ADa^{(r)}}\right). Reg ( r ) ≤ Reg guess ( r ) + Reg remain ( r ) ≤ O ( A D a ( r − 1 ) + A D a ( r ) ) .
Put everything together. We have shown that Reg ( 0 ) = O ( A D a ( 0 ) ) \operatorname{Reg}^{(0)} = O\left(\sqrt{ADa^{(0)}}\right) Reg ( 0 ) = O ( A D a ( 0 ) ) and, for each r ∈ [ R ] r \in[R] r ∈ [ R ] , Reg ( r ) ≤ O ( A D a ( r − 1 ) + A D a ( r ) ) \operatorname{Reg}^{(r)} \le O\left(\sqrt{ADa^{(r-1)}} + \sqrt{ADa^{(r)}}\right) Reg ( r ) ≤ O ( A D a ( r − 1 ) + A D a ( r ) ) . Summing over all epochs shows that the regret of Algorithm 2 is upper bounded by ∑ r = 0 R Reg ( r ) ≤ ∑ r = 0 R O ( A D a ( r ) ) ≤ ∑ r = 0 R − 1 O ( A D a ( r ) ) + O ( A D ∥ b ∥ 2 ) \sum_{r=0}^{R} \operatorname{Reg}^{(r)} \le\sum_{r=0}^{R} O\left(\sqrt{ADa^{(r)}}\right) \le\sum_{r=0}^{R-1} O\left(\sqrt{ADa^{(r)}}\right) + O\left(\sqrt{AD}\lVert b\rVert_2\right) ∑ r = 0 R Reg ( r ) ≤ ∑ r = 0 R O ( A D a ( r ) ) ≤ ∑ r = 0 R − 1 O ( A D a ( r ) ) + O ( A D ∥ b ∥ 2 ) , where the second step applies a ( R ) ≤ ∑ j = 1 B b j 2 = ∥ b ∥ 2 2 a^{(R)} \le\sum_{j=1}^{B} b_j^2 = \lVert b\rVert_2^2 a ( R ) ≤ ∑ j = 1 B b j 2 = ∥ b ∥ 2 2 . Recall that Algorithm 2 sets g ( r ) = 2 a ( r − 1 ) g^{(r)} = 2a^{(r-1)} g ( r ) = 2 a ( r − 1 ) for each epoch r ∈ [ R ] r \in[R] r ∈ [ R ] . Moreover, for every r ∈ [ R − 1 ] r \in[R-1] r ∈ [ R − 1 ] , a ( r ) ≥ g ( r ) a^{(r)} \ge g^{(r)} a ( r ) ≥ g ( r ) holds when epoch r r r ends. Thus, a ( r ) ≥ g ( r ) = 2 a ( r − 1 ) a^{(r)} \ge g^{(r)} = 2a^{(r-1)} a ( r ) ≥ g ( r ) = 2 a ( r − 1 ) , which further implies a ( r ) ≤ a ( R − 1 ) 2 R − r − 1 a^{(r)} \le\frac{a^{(R-1)}}{2^{R-r-1}} a ( r ) ≤ 2 R − r − 1 a ( R − 1 ) for every r ∈ { 0 , 1 , … , R − 1 } r \in\{0, 1, \ldots, R-1\} r ∈ { 0 , 1 , … , R − 1 } . Therefore,
∑ r = 0 R − 1 O ( A D a ( r ) ) ≤ O ( A D a ( R − 1 ) ) ∑ r = 0 R − 1 1 2 R − r − 1 ≤ O ( A D a ( R − 1 ) ) . \sum_{r=0}^{R-1} O\left(\sqrt{ADa^{(r)}}\right) \le O\left(\sqrt{ADa^{(R-1)}}\right)\sum_{r=0}^{R-1}\sqrt{\frac{1}{2^{R-r-1}}} \le O\left(\sqrt{ADa^{(R-1)}}\right). r = 0 ∑ R − 1 O ( A D a ( r ) ) ≤ O ( A D a ( R − 1 ) ) r = 0 ∑ R − 1 2 R − r − 1 1 ≤ O ( A D a ( R − 1 ) ) .
Noting O ( A D a ( R − 1 ) ) ≤ O ( A D ∥ b ∥ 2 ) O\left(\sqrt{ADa^{(R-1)}}\right) \le O\left(\sqrt{AD}\lVert b\rVert_2\right) O ( A D a ( R − 1 ) ) ≤ O ( A D ∥ b ∥ 2 ) completes the proof.
AI Use Statement
We used large language models (LLMs) to assist with writing and editing the manuscript, including improving clarity, grammar, and presentation. The authors reviewed and revised the resulting text and take full responsibility for the content of the paper.
Discussion
A natural open problem is to tighten the gap-dependent regret bounds for stochastic bandits (Theorems 1 and 4). While our analysis improved the gap-dependent lower bound from Ω ( α ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α ∑ i : Δ i > 0 Δ i − 1 ) to Ω ( α 3 2 ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha^{\frac{3}{2}}\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α 2 3 ∑ i : Δ i > 0 Δ i − 1 ) , there remains an α 1 / 2 \alpha^{1/2} α 1/2 gap between the upper and lower bounds. In Appendix § 8 .§ 4 , we show a limitation of the comparison used in our current analysis, which suggests that the current approach at best yields an O ~ ( α 7 4 ∑ i : Δ i > 0 Δ i − 1 ) \widetilde{O}\left(\alpha^{\frac{7}{4}}\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) O ( α 4 7 ∑ i : Δ i > 0 Δ i − 1 ) regret bound. Therefore, one concrete starting point is to generalize such an algorithm-dependent to an algorithm-independent lower bound of Ω ( α 7 4 ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha^{\frac{7}{4}}\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α 4 7 ∑ i : Δ i > 0 Δ i − 1 ) with a realizable stochastic bandit instance that works for any algorithm, and then see if such a lower bound can be further strengthened to an almost-matching lower bound of Ω ( α 2 ∑ i : Δ i > 0 Δ i − 1 ) \Omega\left(\alpha^2\sum_{i:\Delta_i>0}\Delta_i^{-1}\right) Ω ( α 2 ∑ i : Δ i > 0 Δ i − 1 ) .
Another interesting direction is to extend adversarially batched online learning beyond the four canonical problems considered in this work. Natural directions include reinforcement learning and other bandit models, such as contextual bandits, where feedback constraints and externally imposed update schedules also arise. The complexity measures developed here, including the 2-norm of the batch length sequence and the hardness metric α \alpha α , provide a natural starting point for understanding how adversarially chosen batch structures affect regret in these broader online learning models.
Upper Bounds for Stochastic Bandits
Proof of Lemma 1
Lemma 3 (Hoeffding’s inequality). Let X 1 , … , X τ X_1,\ldots,X_\tau X 1 , … , X τ be independent random variables such that X s ∈ [ a , b ] X_s \in[a,b] X s ∈ [ a , b ] for all s ∈ [ τ ] s \in[\tau] s ∈ [ τ ] . Let X ‾ = 1 τ ∑ s = 1 τ X s \overline{X}=\frac{1}{\tau}\sum_{s=1}^{\tau}X_s X = τ 1 ∑ s = 1 τ X s . Then, for any ϵ > 0 , \epsilon>0, ϵ > 0 ,
Pr [ ∣ X ‾ − E [ X ‾ ] ∣ ≥ ϵ ] ≤ 2 exp ( − 2 τ ϵ 2 ( b − a ) 2 ) . \Pr\left[\left|\overline{X}-\mathbb{E}[\overline{X}]\right|\ge\epsilon\right]\le2\exp\left(-\frac{2\tau\epsilon^2}{(b-a)^2}\right). Pr [ X − E [ X ] ≥ ϵ ] ≤ 2 exp ( − ( b − a ) 2 2 τ ϵ 2 ) .
We now prove Lemma 1. Recall that j i = min { j ∈ [ B ] : S j ≥ 4 γ ln ( N T ) Δ i 2 } j_i=\min\left\{j\in[B]:S_j\ge\frac{4\gamma\ln(NT)}{\Delta_i^2}\right\} j i = min { j ∈ [ B ] : S j ≥ Δ i 2 4 γ l n ( N T ) } , and the “good event” E g o o d \mathcal{E}^{\mathrm{good}} E good is defined as follows: (1) the optimal arm i ∗ i^* i ∗ remains active throughout the algorithm; (2) every sub-optimal arm i i i with Δ i > 0 \Delta_i>0 Δ i > 0 and j i ≤ B j_i\le B j i ≤ B is eliminated by the end of batch j i j_i j i .
Proof of Lemma 1. We first address integer rounding. Under the least-pulled-arm rule, the cumulative pull counts of active arms differ by at most one. Thus, within each block k k k , the number of pulls of any active arm differs from b k / n k b_k/n_k b k / n k by at most two. Summing over blocks, the actual cumulative pull count C i ( j ) C_i(j) C i ( j ) of an arm surviving through block j j j satisfies ∣ C i ( j ) − S j ∣ ≤ 2 j |C_i(j)-S_j|\le2j ∣ C i ( j ) − S j ∣ ≤ 2 j . Since merging produces O ( log T ) O(\log T) O ( log T ) blocks, choosing γ \gamma γ sufficiently large ensures C i ( j ) = Θ ( S j ) C_i(j)=\Theta(S_j) C i ( j ) = Θ ( S j ) whenever the elimination threshold is at most one; otherwise, no elimination occurs. We apply concentration inequalities to the actual integer pull counts and suppress these constant-factor rounding effects below.
Proof of lemma:stochasticcondregret
If Condition (1) fails, then μ ^ i − μ ^ i ∗ > γ ln ( N T ) S j \hat{\mu}_i-\hat{\mu}_{i^*}>\sqrt{\frac{\gamma\ln(NT)}{S_j}} μ ^ i − μ ^ i ∗ > S j γ l n ( N T ) must hold for some i ≠ i ∗ i\ne i^* i = i ∗ at the end of some batch j j j . Since the rewards are bounded in [ 0 , 1 ] [0,1] [ 0 , 1 ] , ( μ ^ i − μ ^ i ∗ ) − ( μ i − μ i ∗ ) (\hat{\mu}_i-\hat{\mu}_{i^*})-(\mu_i-\mu_{i^*}) ( μ ^ i − μ ^ i ∗ ) − ( μ i − μ i ∗ ) is an average of S j S_j S j independent random variables bounded in the length-4 interval [ − 2 , 2 ] [-2,2] [ − 2 , 2 ] . Also note that μ i − μ i ∗ ≤ 0 \mu_i-\mu_{i^*}\le0 μ i − μ i ∗ ≤ 0 by the optimality of arm i ∗ i^* i ∗ . Thus, by Lemma 3,
Pr [ μ ^ i − μ ^ i ∗ > γ ln ( N T ) S j ] ≤ Pr [ ( μ ^ i − μ ^ i ∗ ) − ( μ i − μ i ∗ ) > γ ln ( N T ) S j ] ≤ 2 exp ( − γ ln ( N T ) 16 ) = 2 ( N T ) γ / 16 . \Pr\left[\hat{\mu}_i-\hat{\mu}_{i^*}>\sqrt{\frac{\gamma\ln(NT)}{S_j}}\right]\le\Pr\left[(\hat{\mu}_i-\hat{\mu}_{i^*})-(\mu_i-\mu_{i^*})>\sqrt{\frac{\gamma\ln(NT)}{S_j}}\right]\le2\exp\left(-\frac{\gamma\ln(NT)}{16}\right)=\frac{2}{(NT)^{\gamma/16}}. Pr [ μ ^ i − μ ^ i ∗ > S j γ ln ( N T ) ] ≤ Pr [ ( μ ^ i − μ ^ i ∗ ) − ( μ i − μ i ∗ ) > S j γ ln ( N T ) ] ≤ 2 exp ( − 16 γ ln ( N T ) ) = ( N T ) γ /16 2 .
Union bounding over all possible values of i ∈ [ N ] i\in[N] i ∈ [ N ] , j ∈ [ B ] j\in[B] j ∈ [ B ] , and S j ∈ [ T ] S_j\in[T] S j ∈ [ T ] gives
Pr [ Condition (1) fails ] ≤ ∑ i = 1 N ∑ t = 1 T ∑ S j = 1 T 2 ( N T ) γ / 16 ≤ 1 2 T , \Pr[\text{Condition (1) fails}]\le\sum_{i=1}^{N}\sum_{t=1}^{T}\sum_{S_j=1}^{T}\frac{2}{(NT)^{\gamma/16}}\le\frac{1}{2T}, Pr [ Condition (1) fails ] ≤ i = 1 ∑ N t = 1 ∑ T S j = 1 ∑ T ( N T ) γ /16 2 ≤ 2 T 1 ,
where the last step holds for some sufficiently large constant γ \gamma γ .
Next, we analyze the probability that Condition (2) fails to hold. For this to happen, there must be some arm i ≠ i ∗ i\ne i^* i = i ∗ such that μ ^ i ∗ − μ ^ i ≤ γ ln ( N T ) S j i \hat{\mu}_{i^*}-\hat{\mu}_i\le\sqrt{\frac{\gamma\ln(NT)}{S_{j_i}}} μ ^ i ∗ − μ ^ i ≤ S j i γ l n ( N T ) by the end of batch j i j_i j i . By definition of j i = min { j ∈ [ B ] : S j ≥ 4 γ ln ( N T ) Δ i 2 } j_i=\min\left\{j\in[B]:S_j\ge\frac{4\gamma\ln(NT)}{\Delta_i^2}\right\} j i = min { j ∈ [ B ] : S j ≥ Δ i 2 4 γ l n ( N T ) } , we have μ i ∗ − μ i = Δ i ≥ 2 γ ln ( N T ) S j i \mu_{i^*}-\mu_i=\Delta_i\ge2\sqrt{\frac{\gamma\ln(NT)}{S_{j_i}}} μ i ∗ − μ i = Δ i ≥ 2 S j i γ l n ( N T ) . It follows that we have
( μ i ∗ − μ i ) − ( μ ^ i ∗ − μ ^ i ) ≥ Δ i − γ ln ( N T ) S j i ≥ γ ln ( N T ) S j i . (\mu_{i^*}-\mu_i)-(\hat{\mu}_{i^*}-\hat{\mu}_i)\ge\Delta_i-\sqrt{\frac{\gamma\ln(NT)}{S_{j_i}}}\ge\sqrt{\frac{\gamma\ln(NT)}{S_{j_i}}}. ( μ i ∗ − μ i ) − ( μ ^ i ∗ − μ ^ i ) ≥ Δ i − S j i γ ln ( N T ) ≥ S j i γ ln ( N T ) .
Applying Lemma 3 again upper bounds the probability for the above to hold by 2 ( N T ) γ / 16 \frac{2}{(NT)^{\gamma/16}} ( N T ) γ /16 2 . Then, union bounding over all possible values of i ∈ [ N ] i\in[N] i ∈ [ N ] , j i ∈ [ B ] j_i\in[B] j i ∈ [ B ] , and S j i ∈ [ T ] S_{j_i}\in[T] S j i ∈ [ T ] gives
Pr [ Condition (2) fails ] ≤ N T 2 ⋅ 2 ( N T ) γ / 16 ≤ 1 2 T \Pr[\text{Condition (2) fails}]\le NT^2\cdot\frac{2}{(NT)^{\gamma/16}}\le\frac{1}{2T} Pr [ Condition (2) fails ] ≤ N T 2 ⋅ ( N T ) γ /16 2 ≤ 2 T 1
for some sufficiently large constant γ \gamma γ . Combining the two probability bounds completes the proof. □ \square □
Proof of Lemma 2
Proof of Lemma 2. We first prove the upper bound under the additional assumption that
b j ≥ 2 b j − 1 , ∀ j ∈ { 2 , 3 , … , B − 1 } and b B ≤ 2 b B − 1 . (3) b_j\ge2b_{j-1},\quad\forall j\in\{2,3,\ldots,B-1\}\quad\text{and}\quad b_B\le2b_{B-1}. \tag*{(3)} b j ≥ 2 b j − 1 , ∀ j ∈ { 2 , 3 , … , B − 1 } and b B ≤ 2 b B − 1 . (3)
Later, we will show that Algorithm 1 effectively ensures such an assumption by merging the blocks.
Assuming Equation (3) , it holds for every j ∈ [ B − 1 ] j\in[B-1] j ∈ [ B − 1 ] that
t j = b j + b j − 1 + ⋯ + b 1 ≤ b j ⋅ ( 1 + 1 2 + ⋯ + 1 2 j − 1 ) < 2 b j , t_j=b_j+b_{j-1}+\cdots+b_1\le b_j\cdot\left(1+\frac{1}{2}+\cdots+\frac{1}{2^{j-1}}\right)<2b_j, t j = b j + b j − 1 + ⋯ + b 1 ≤ b j ⋅ ( 1 + 2 1 + ⋯ + 2 j − 1 1 ) < 2 b j ,
which further implies b j b j − 1 ≤ b j t j − 1 / 2 ≤ 2 α \frac{b_j}{b_{j-1}}\le\frac{b_j}{t_{j-1}/2}\le2^\alpha b j − 1 b j ≤ t j − 1 /2 b j ≤ 2 α for every j ∈ { 2 , 3 , … , B } j\in\{2,3,\ldots,B\} j ∈ { 2 , 3 , … , B } . Moreover, it holds for every j ∈ [ B − 1 ] j\in[B-1] j ∈ [ B − 1 ] that S j = Θ ( b j / n j ) S_j=\Theta(b_j/n_j) S j = Θ ( b j / n j ) , since we have
b j n j ≤ S j = ∑ k = 1 j b k n k ≤ ∑ k = 1 j b k n j = t j n j ≤ 2 b j n j . \frac{b_j}{n_j}\le S_j=\sum_{k=1}^{j}\frac{b_k}{n_k}\le\frac{\sum_{k=1}^{j}b_k}{n_j}=\frac{t_j}{n_j}\le\frac{2b_j}{n_j}. n j b j ≤ S j = k = 1 ∑ j n k b k ≤ n j ∑ k = 1 j b k = n j t j ≤ n j 2 b j .
Decomposition of the regret. At the end of each block j ∈ [ B − 1 ] j \in[B-1] j ∈ [ B − 1 ] , n j − n j + 1 n_j-n_{j+1} n j − n j + 1 sub-optimal arms are removed. Each such arm i ∈ A j ∖ A j + 1 i \in A_j \setminus A_{j+1} i ∈ A j ∖ A j + 1 was pulled S j S_j S j times and each pull caused a Δ i \Delta_i Δ i regret. We note that, under the least-pulled-arm rule, the cumulative pull counts of active arms differ by at most one. Consequently, the actual cumulative count C i ( j ) C_i(j) C i ( j ) of an arm surviving through block j j j satisfies ∣ C i ( j ) − S j ∣ ≤ 2 j \lvert C_i(j)-S_j\rvert\le2j ∣ C i ( j ) − S j ∣ ≤ 2 j . Since merging produces B = O ( log T ) B=O(\log T) B = O ( log T ) blocks, rounding affects concentration bounds only by constant factors at sample sizes where elimination can occur. Its contribution to regret therefore is O ( log T ∑ i : Δ i > 0 Δ i ) O(\log T\sum_{i:\Delta_i>0}\Delta_i) O ( log T ∑ i : Δ i > 0 Δ i ) , which is absorbed by the stated bounds.
Conditioned on event E g o o d \mathcal{E}^{\mathrm{good}} E good , every sub-optimal arm i i i is removed before or at the end of block j i j_i j i . Then, i ∈ A j i \in A_j i ∈ A j implies that
Δ i ≤ γ ln ( N T ) S j − 1 \Delta_i \le\sqrt{\frac{\gamma\ln(NT)}{S_{j-1}}} Δ i ≤ S j − 1 γ ln ( N T )
The above also holds for the last block (i.e., j = B j=B j = B ), if we define A B + 1 : = { i ∈ [ N ] : Δ i = 0 } A_{B+1}:=\{i\in[N]:\Delta_i=0\} A B + 1 := { i ∈ [ N ] : Δ i = 0 } as the set of optimal arms and n B + 1 = ∣ A B + 1 ∣ n_{B+1}=\lvert A_{B+1}\rvert n B + 1 = ∣ A B + 1 ∣ .
Summing over all B B B blocks, we obtain the following upper bound on the regret:
∑ j = 1 B ( n j − n j + 1 ) ⋅ S j ⋅ γ ln ( N T ) S j − 1 = O ( log ( N T ) ) ⋅ ∑ j = 1 B ( n j − n j + 1 ) ⋅ S j ⋅ 1 S j − 1 . \sum_{j=1}^{B}(n_j-n_{j+1})\cdot S_j\cdot\sqrt{\frac{\gamma\ln(NT)}{S_{j-1}}}
=O\left(\sqrt{\log(NT)}\right)\cdot\sum_{j=1}^{B}(n_j-n_{j+1})\cdot S_j\cdot\sqrt{\frac{1}{S_{j-1}}}. j = 1 ∑ B ( n j − n j + 1 ) ⋅ S j ⋅ S j − 1 γ ln ( N T ) = O ( log ( N T ) ) ⋅ j = 1 ∑ B ( n j − n j + 1 ) ⋅ S j ⋅ S j − 1 1 .
Recall that S j = Θ ( b j / n j ) S_j=\Theta(b_j/n_j) S j = Θ ( b j / n j ) for every j ∈ [ B − 1 ] j\in[B-1] j ∈ [ B − 1 ] . Therefore, using the shorthand
L H S j : = { ( n j − n j + 1 ) ⋅ b j n j ⋅ n j − 1 b j − 1 , j ∈ [ B − 1 ] , ( n j − n j + 1 ) ⋅ S j ⋅ n j − 1 b j − 1 , j = B , \mathrm{LHS}_j :=
\begin{cases}
(n_j-n_{j+1})\cdot\frac{b_j}{n_j}\cdot\sqrt{\frac{n_{j-1}}{b_{j-1}}}, & j\in[B-1],\\
(n_j-n_{j+1})\cdot S_j\cdot\sqrt{\frac{n_{j-1}}{b_{j-1}}}, & j=B,
\end{cases} LHS j := ⎩ ⎨ ⎧ ( n j − n j + 1 ) ⋅ n j b j ⋅ b j − 1 n j − 1 , ( n j − n j + 1 ) ⋅ S j ⋅ b j − 1 n j − 1 , j ∈ [ B − 1 ] , j = B ,
the regret is upper bounded by O ( log ( N T ) ) ⋅ ∑ j = 1 B L H S j O\left(\sqrt{\log(NT)}\right)\cdot\sum_{j=1}^{B}\mathrm{LHS}_j O ( log ( N T ) ) ⋅ ∑ j = 1 B LHS j .
Decomposition of the regret bound. Recall that our goal is to upper bound the regret by
α 2 ln ( N T ) ⋅ ∑ i : Δ i > 0 1 Δ i ≥ α 2 ln ( N T ) ∑ j = 1 B ( n j − n j + 1 ) S j − 1 γ log ( N T ) ≥ Ω ( log ( N T ) ) ⋅ α 2 ∑ j = 1 B ( n j − n j + 1 ) b j − 1 n j − 1 . \begin{aligned}
\alpha^2\ln(NT)\cdot\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}
\ge\alpha^2\ln(NT)\sum_{j=1}^{B}(n_j-n_{j+1})\sqrt{\frac{S_{j-1}}{\gamma\log(NT)}} \\
&\ge\Omega\left(\sqrt{\log(NT)}\right)\cdot\alpha^2\sum_{j=1}^{B}(n_j-n_{j+1})\sqrt{\frac{b_{j-1}}{n_{j-1}}}.
\end{aligned} α 2 ln ( N T ) ⋅ i : Δ i > 0 ∑ Δ i 1 ≥ α 2 ln ( N T ) j = 1 ∑ B ( n j − n j + 1 ) γ log ( N T ) S j − 1 ≥ Ω ( log ( N T ) ) ⋅ α 2 j = 1 ∑ B ( n j − n j + 1 ) n j − 1 b j − 1 .
Therefore, it suffices to show that ∑ j = 1 B L H S j ≤ O ( α 2 ) ⋅ ∑ j = 1 B R H S j \sum_{j=1}^{B}\mathrm{LHS}_j\le O(\alpha^2)\cdot\sum_{j=1}^{B}\mathrm{RHS}_j ∑ j = 1 B LHS j ≤ O ( α 2 ) ⋅ ∑ j = 1 B RHS j , where
R H S j : = ( n j − n j + 1 ) b j − 1 n j − 1 . \mathrm{RHS}_j := (n_j-n_{j+1})\sqrt{\frac{b_{j-1}}{n_{j-1}}}. RHS j := ( n j − n j + 1 ) n j − 1 b j − 1 .
Division of blocks. Towards proving ∑ j = 1 B L H S j ≤ O ( α 2 ) ⋅ ∑ j = 1 B R H S j \sum_{j=1}^{B}\mathrm{LHS}_j\le O(\alpha^2)\cdot\sum_{j=1}^{B}\mathrm{RHS}_j ∑ j = 1 B LHS j ≤ O ( α 2 ) ⋅ ∑ j = 1 B RHS j , we set C = 3 C=3 C = 3 and partition the blocks 1 , 2 , … , B 1,2,\ldots,B 1 , 2 , … , B into two sets:
J 1 : = { j ∈ [ B ] : n j ≥ n j − 1 C α } and J 2 : = { j ∈ [ B ] : n j < n j − 1 C α } . J_1:=\left\{j\in[B]:n_j\ge\frac{n_{j-1}}{C\alpha}\right\}
\quad\text{and}\quad
J_2:=\left\{j\in[B]:n_j<\frac{n_{j-1}}{C\alpha}\right\}. J 1 := { j ∈ [ B ] : n j ≥ C α n j − 1 } and J 2 := { j ∈ [ B ] : n j < C α n j − 1 } .
For notational convenience, we extend the initialization convention t 0 = 1 t_0=1 t 0 = 1 by setting b 0 : = 1 b_0:=1 b 0 := 1 , n 0 : = n 1 = N n_0:=n_1=N n 0 := n 1 = N , and S 0 : = b 0 / n 0 S_0:=b_0/n_0 S 0 := b 0 / n 0 . These analysis-only boundary values encode the trivial first-block bounds Δ i ≤ 1 ≤ γ log ( N T ) / S 0 \Delta_i\le1\le\sqrt{\gamma\log(NT)}/S_0 Δ i ≤ 1 ≤ γ log ( N T ) / S 0 and b 1 ≤ α b 0 b_1\le\alpha b_0 b 1 ≤ α b 0 , while ensuring the first block belongs to the J 1 J_1 J 1 .
Blocks in J 1 J_1 J 1 . For any j ∈ J 1 j \in J_1 j ∈ J 1 , the condition n j ≥ n j − 1 C α n_j \ge\frac{n_{j-1}}{C\alpha} n j ≥ C α n j − 1 together with the bound b j ≤ 2 α ⋅ b j − 1 b_j \le2\alpha\cdot b_{j-1} b j ≤ 2 α ⋅ b j − 1 gives
LHS j ≤ ( n j − n j + 1 ) ⋅ 2 α ⋅ b j − 1 n j − 1 / ( C α ) ⋅ n j − 1 b j − 1 ≤ O ( α 2 ) ⋅ RHS j , \operatorname{LHS}_j \le(n_j-n_{j+1})\cdot\frac{2\alpha\cdot b_{j-1}}{n_{j-1}/(C\alpha)}\cdot\sqrt{\frac{n_{j-1}}{b_{j-1}}} \le O(\alpha^2)\cdot\operatorname{RHS}_j, LHS j ≤ ( n j − n j + 1 ) ⋅ n j − 1 / ( C α ) 2 α ⋅ b j − 1 ⋅ b j − 1 n j − 1 ≤ O ( α 2 ) ⋅ RHS j ,
which further implies
∑ j ∈ J 1 LHS j ≤ O ( α 2 ) ⋅ ∑ j ∈ J 1 RHS j ≤ O ( α 2 ) ⋅ ∑ j = 1 B RHS j . (4) \sum_{j\in J_1}\operatorname{LHS}_j \le O(\alpha^2)\cdot\sum_{j\in J_1}\operatorname{RHS}_j \le O(\alpha^2)\cdot\sum_{j=1}^{B}\operatorname{RHS}_j. \tag*{(4)} j ∈ J 1 ∑ LHS j ≤ O ( α 2 ) ⋅ j ∈ J 1 ∑ RHS j ≤ O ( α 2 ) ⋅ j = 1 ∑ B RHS j . (4)
Blocks in J 2 J_2 J 2 . To control the contribution from J 2 J_2 J 2 , consider an index pair ( j 0 , j 1 ) (j_0,j_1) ( j 0 , j 1 ) that specify a maximal contiguous subsequence of indices in J 2 J_2 J 2 . In other words, j 0 , j 0 + 1 , … , j 1 ∈ J 2 j_0,j_0+1,\ldots,j_1\in J_2 j 0 , j 0 + 1 , … , j 1 ∈ J 2 while j 0 − 1 , j 1 + 1 ∉ J 2 j_0-1,j_1+1\notin J_2 j 0 − 1 , j 1 + 1 ∈ / J 2 . We will show that ∑ j = j 0 j 1 LHS j ≤ O ( α 2 ) ⋅ RHS j 0 − 1 \sum_{j=j_0}^{j_1}\operatorname{LHS}_j\le O(\alpha^2)\cdot\operatorname{RHS}_{j_0-1} ∑ j = j 0 j 1 LHS j ≤ O ( α 2 ) ⋅ RHS j 0 − 1 .
When j ≠ B j\ne B j = B , we have
LHS j = ( n j − n j + 1 ) ⋅ b j n j n j − 1 b j − 1 ≤ b j n j − 1 b j − 1 ≤ O ( α ) n j − 1 b j − 1 , \operatorname{LHS}_j=(n_j-n_{j+1})\cdot\frac{b_j}{n_j}\sqrt{\frac{n_{j-1}}{b_{j-1}}}\le b_j\sqrt{\frac{n_{j-1}}{b_{j-1}}}\le O(\alpha)\sqrt{n_{j-1}b_{j-1}}, LHS j = ( n j − n j + 1 ) ⋅ n j b j b j − 1 n j − 1 ≤ b j b j − 1 n j − 1 ≤ O ( α ) n j − 1 b j − 1 ,
where the last step applies b j ≤ 2 α ⋅ b j − 1 b_j\le2\alpha\cdot b_{j-1} b j ≤ 2 α ⋅ b j − 1 . For j = B j=B j = B , note that S B − 1 ≤ 2 b B − 1 / n B − 1 S_{B-1}\le2b_{B-1}/n_{B-1} S B − 1 ≤ 2 b B − 1 / n B − 1 and the assumption b B ≤ 2 b B − 1 b_B\le2b_{B-1} b B ≤ 2 b B − 1 (from Equation (3) ) together imply
S B = S B − 1 + b B n B ≤ 2 b B − 1 n B − 1 + 2 b B − 1 n B ≤ 4 b B − 1 n B . S_B=S_{B-1}+\frac{b_B}{n_B}\le\frac{2b_{B-1}}{n_{B-1}}+\frac{2b_{B-1}}{n_B}\le\frac{4b_{B-1}}{n_B}. S B = S B − 1 + n B b B ≤ n B − 1 2 b B − 1 + n B 2 b B − 1 ≤ n B 4 b B − 1 .
It follows that LHS B = ( n B − n B + 1 ) ⋅ S B n B − 1 b B − 1 ≤ 4 n B − 1 b B − 1 \operatorname{LHS}_B=(n_B-n_{B+1})\cdot S_B\sqrt{\frac{n_{B-1}}{b_{B-1}}}\le4\sqrt{n_{B-1}b_{B-1}} LHS B = ( n B − n B + 1 ) ⋅ S B b B − 1 n B − 1 ≤ 4 n B − 1 b B − 1 . Therefore, we have LHS j ≤ O ( α ) n j − 1 b j − 1 \operatorname{LHS}_j\le O(\alpha)\sqrt{n_{j-1}b_{j-1}} LHS j ≤ O ( α ) n j − 1 b j − 1 for every j ∈ { j 0 , j 0 + 1 , … , j 1 } j\in\{j_0,j_0+1,\ldots,j_1\} j ∈ { j 0 , j 0 + 1 , … , j 1 } .
Since b j ≤ 2 α ⋅ b j − 1 b_j\le2\alpha\cdot b_{j-1} b j ≤ 2 α ⋅ b j − 1 and n j < n j − 1 C α n_j<\frac{n_{j-1}}{C\alpha} n j < C α n j − 1 hold for every j ∈ { j 0 , j 0 + 1 , … , j 1 } j\in\{j_0,j_0+1,\ldots,j_1\} j ∈ { j 0 , j 0 + 1 , … , j 1 } , a simple induction gives b j − 1 ≤ ( 2 α ) j − j 0 ⋅ b j 0 − 1 b_{j-1}\le(2\alpha)^{j-j_0}\cdot b_{j_0-1} b j − 1 ≤ ( 2 α ) j − j 0 ⋅ b j 0 − 1 and n j − 1 ≤ n j 0 − 1 ( C α ) j − j 0 n_{j-1}\le\frac{n_{j_0-1}}{(C\alpha)^{j-j_0}} n j − 1 ≤ ( C α ) j − j 0 n j 0 − 1 . It follows that
∑ j = j 0 j 1 LHS j ≤ O ( α ) ⋅ ∑ j = j 0 j 1 b j − 1 n j − 1 ( LHS j ≤ O ( α ) n j − 1 b j − 1 ) ≤ O ( α ) ⋅ ∑ j = j 0 j 1 ( 2 α ) j − j 0 ⋅ b j 0 − 1 ⋅ n j 0 − 1 ( C α ) j − j 0 ≤ O ( α ) ⋅ b j 0 − 1 n j 0 − 1 ⋅ ∑ t = 0 j 1 − j 0 ( 2 / 3 ) t = O ( α ) ⋅ b j 0 − 1 n j 0 − 1 . ( C = 3 ) \begin{aligned}
\sum_{j=j_0}^{j_1}\operatorname{LHS}_j\le O(\alpha)\cdot\sum_{j=j_0}^{j_1}\sqrt{b_{j-1}n_{j-1}}
\qquad\left(\operatorname{LHS}_j\le O(\alpha)\sqrt{n_{j-1}b_{j-1}}\right) \\
&\le O(\alpha)\cdot\sum_{j=j_0}^{j_1}\sqrt{(2\alpha)^{j-j_0}\cdot b_{j_0-1}\cdot\frac{n_{j_0-1}}{(C\alpha)^{j-j_0}}} \\
&\le O(\alpha)\cdot\sqrt{b_{j_0-1}n_{j_0-1}}\cdot\sum_{t=0}^{j_1-j_0}\sqrt{(2/3)^t}=O(\alpha)\cdot\sqrt{b_{j_0-1}n_{j_0-1}}.
\qquad(C=3)
\end{aligned} j = j 0 ∑ j 1 LHS j ≤ O ( α ) ⋅ j = j 0 ∑ j 1 b j − 1 n j − 1 ( LHS j ≤ O ( α ) n j − 1 b j − 1 ) ≤ O ( α ) ⋅ j = j 0 ∑ j 1 ( 2 α ) j − j 0 ⋅ b j 0 − 1 ⋅ ( C α ) j − j 0 n j 0 − 1 ≤ O ( α ) ⋅ b j 0 − 1 n j 0 − 1 ⋅ t = 0 ∑ j 1 − j 0 ( 2/3 ) t = O ( α ) ⋅ b j 0 − 1 n j 0 − 1 . ( C = 3 )
For the RHS j 0 − 1 \operatorname{RHS}_{j_0-1} RHS j 0 − 1 term, note that the assumption j 0 ∈ J 2 j_0\in J_2 j 0 ∈ J 2 implies n j 0 < n j 0 − 1 C α n_{j_0}<\frac{n_{j_0-1}}{C\alpha} n j 0 < C α n j 0 − 1 . Moreover, since j 0 − 1 ∈ J 1 j_0-1\in J_1 j 0 − 1 ∈ J 1 , we have n j 0 − 1 ≥ n j 0 − 2 C α n_{j_0-1}\ge\frac{n_{j_0-2}}{C\alpha} n j 0 − 1 ≥ C α n j 0 − 2 and equivalently n j 0 − 2 ≤ C α ⋅ n j 0 − 1 n_{j_0-2}\le C\alpha\cdot n_{j_0-1} n j 0 − 2 ≤ C α ⋅ n j 0 − 1 . We then have
RHS j 0 − 1 = ( n j 0 − 1 − n j 0 ) b j 0 − 2 n j 0 − 2 > ( n j 0 − 1 − n j 0 − 1 C α ) b j 0 − 2 C α ⋅ n j 0 − 1 ( n j 0 < n j 0 − 1 C α and n j 0 − 2 ≤ C α ⋅ n j 0 − 1 ) ≥ Ω ( 1 ) ⋅ b j 0 − 2 n j 0 − 1 α . \begin{aligned}
\operatorname{RHS}_{j_0-1}=(n_{j_0-1}-n_{j_0})\sqrt{\frac{b_{j_0-2}}{n_{j_0-2}}} \\
&>\left(n_{j_0-1}-\frac{n_{j_0-1}}{C\alpha}\right)\sqrt{\frac{b_{j_0-2}}{C\alpha\cdot n_{j_0-1}}}
\qquad\left(n_{j_0}<\frac{n_{j_0-1}}{C\alpha}\text{ and }n_{j_0-2}\le C\alpha\cdot n_{j_0-1}\right) \\
&\ge\Omega(1)\cdot\sqrt{\frac{b_{j_0-2}n_{j_0-1}}{\alpha}}.
\end{aligned} RHS j 0 − 1 = ( n j 0 − 1 − n j 0 ) n j 0 − 2 b j 0 − 2 > ( n j 0 − 1 − C α n j 0 − 1 ) C α ⋅ n j 0 − 1 b j 0 − 2 ( n j 0 < C α n j 0 − 1 and n j 0 − 2 ≤ C α ⋅ n j 0 − 1 ) ≥ Ω ( 1 ) ⋅ α b j 0 − 2 n j 0 − 1 .
Combining the two bounds above and applying b j 0 − 1 ≤ 2 α ⋅ b j 0 − 2 b_{j_0-1} \le2\alpha\cdot b_{j_0-2} b j 0 − 1 ≤ 2 α ⋅ b j 0 − 2 , we conclude that
∑ j = j 0 j 1 L H S j ≤ O ( α ) ⋅ b j 0 − 1 n j 0 − 1 ≤ O ( α ) ⋅ α ⋅ b j 0 − 2 n j 0 − 1 ≤ O ( α 2 ) ⋅ R H S j 0 − 1 . \sum_{j=j_0}^{j_1} \mathrm{LHS}_j \le\mathcal{O}(\alpha) \cdot\sqrt{b_{j_0-1}n_{j_0-1}} \le\mathcal{O}(\alpha) \cdot\sqrt{\alpha\cdot b_{j_0-2}n_{j_0-1}} \le\mathcal{O}(\alpha^2) \cdot\mathrm{RHS}_{j_0-1}. j = j 0 ∑ j 1 LHS j ≤ O ( α ) ⋅ b j 0 − 1 n j 0 − 1 ≤ O ( α ) ⋅ α ⋅ b j 0 − 2 n j 0 − 1 ≤ O ( α 2 ) ⋅ RHS j 0 − 1 .
Summing over all contiguous intervals in J 2 J_2 J 2 (i.e., all pairs ( j 0 , j 1 ) (j_0,j_1) ( j 0 , j 1 ) ) gives
∑ j ∈ J 2 L H S j ≤ O ( α 2 ) ⋅ ∑ j = 1 B R H S j . (5) \sum_{j\in J_2} \mathrm{LHS}_j \le\mathcal{O}(\alpha^2) \cdot\sum_{j=1}^{B} \mathrm{RHS}_j. \tag*{(5)} j ∈ J 2 ∑ LHS j ≤ O ( α 2 ) ⋅ j = 1 ∑ B RHS j . (5)
Combining Equations (4) and (5) completes the proof under the assumption in Equation (3) .
General block structures. Finally, we note that Algorithm 1 effectively merges the blocks to form a new batch structure, denoted as B ′ \mathcal{B}' B ′ , that ensures b j ′ ≥ 2 b j − 1 ′ b'_j \ge2b'_{j-1} b j ′ ≥ 2 b j − 1 ′ except for the last block. Since the assumption in Equation (3) holds, our previous analysis bounds the regret by O ( [ α ( B ′ ) ] 2 log ( N T ) ∑ i : Δ i > 0 1 Δ i ) \mathcal{O}\left([\alpha(\mathcal{B}')]^2\log(NT)\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\right) O ( [ α ( B ′ ) ] 2 log ( N T ) ∑ i : Δ i > 0 Δ i 1 ) . It remains to show that the merging does not significantly increase the difficulty parameter α \alpha α of the batch structure. Concretely, we will prove α ( B ′ ) ≤ 4 α ( B ) + 2 \alpha(\mathcal{B}') \le4\alpha(\mathcal{B}) + 2 α ( B ′ ) ≤ 4 α ( B ) + 2 .
Consider an arbitrary block b j ′ b'_j b j ′ in the new batch structure B ′ \mathcal{B}' B ′ . If b j ′ b'_j b j ′ is the final incomplete merged block, we have b j ′ < 2 b j − 1 ′ ≤ 2 t j − 1 ′ b'_j < 2b'_{j-1} \le2t'_{j-1} b j ′ < 2 b j − 1 ′ ≤ 2 t j − 1 ′ . Otherwise, b j ′ b'_j b j ′ is a completed merged block, including the case where its completion coincides with the end of the horizon. In this boundary case, the final-block condition in Equation (3) is replaced by b B ≥ 2 b B − 1 b_B \ge2b_{B-1} b B ≥ 2 b B − 1 ; all merged blocks then satisfy the geometric-growth condition, so S B = Θ ( b B / n B ) S_B = \Theta(b_B/n_B) S B = Θ ( b B / n B ) and the regular-block estimates in the preceding regret analysis apply to the final block as well. For a completed merged block b j ′ b'_j b j ′ , let r r r be the index of the last original block (in B \mathcal{B} B ) that forms b j ′ b'_j b j ′ . By construction, we have b j ′ ≤ 2 b j − 1 ′ + b r b'_j \le2b'_{j-1} + b_r b j ′ ≤ 2 b j − 1 ′ + b r ; otherwise, block b j ′ b'_j b j ′ should be completed after merging block b r − 1 b_{r-1} b r − 1 . By definition, we have b r / t r − 1 ≤ α ( B ) b_r/t_{r-1} \le\alpha(\mathcal{B}) b r / t r − 1 ≤ α ( B ) . Furthermore,
t r − 1 ≤ t j − 1 ′ + 2 b j − 1 ′ = b 1 ′ + b 2 ′ + ⋯ + b j − 1 ′ + 2 b j − 1 ′ ≤ 4 b j − 1 ′ . t_{r-1} \le t'_{j-1} + 2b'_{j-1} = b'_1 + b'_2 + \cdots+ b'_{j-1} + 2b'_{j-1} \le4b'_{j-1}. t r − 1 ≤ t j − 1 ′ + 2 b j − 1 ′ = b 1 ′ + b 2 ′ + ⋯ + b j − 1 ′ + 2 b j − 1 ′ ≤ 4 b j − 1 ′ .
Then, we have
b j ′ ≤ 2 b j − 1 ′ + α ( B ) ⋅ t r − 1 ≤ 2 b j − 1 ′ + α ( B ) ⋅ 4 b j − 1 ′ ≤ ( 4 α ( B ) + 2 ) ⋅ t j − 1 ′ . b'_j \le2b'_{j-1} + \alpha(\mathcal{B}) \cdot t_{r-1} \le2b'_{j-1} + \alpha(\mathcal{B}) \cdot4b'_{j-1} \le(4\alpha(\mathcal{B})+2)\cdot t'_{j-1}. b j ′ ≤ 2 b j − 1 ′ + α ( B ) ⋅ t r − 1 ≤ 2 b j − 1 ′ + α ( B ) ⋅ 4 b j − 1 ′ ≤ ( 4 α ( B ) + 2 ) ⋅ t j − 1 ′ .
Therefore, we have α ( B ′ ) = max j b j ′ t j − 1 ′ ≤ 4 α ( B ) + 2 \alpha(\mathcal{B}') = \max_j \frac{b'_j}{t'_{j-1}} \le4\alpha(\mathcal{B})+2 α ( B ′ ) = max j t j − 1 ′ b j ′ ≤ 4 α ( B ) + 2 , which completes the proof.
Extension of Existing Bounds for Arbitrary Batch Structure
Proposition 3. For the adversarially batched stochastic bandits with N N N arms and arbitrary batch structure B \mathcal{B} B characterized by the hardness metric α \alpha α , there is an algorithm with an expected regret of
O ( α log N log ( N T ) N Δ min ) , \mathcal{O}\left(\alpha\log N\log(NT)\frac{N}{\Delta_{\min}}\right), O ( α log N log ( N T ) Δ m i n N ) , where Δ min = min i : Δ i > 0 Δ i \Delta_{\min}=\min_{i:\Delta_i>0}\Delta_i Δ m i n = min i : Δ i > 0 Δ i .
Proof. We follow the argument used in the proof of Theorem 2. Throughout the following argument, we work on the event E g o o d \mathcal{E}^{\mathrm{good}} E good . Let τ i \tau_i τ i and σ i \sigma_i σ i be defined as in that proof: τ i \tau_i τ i is the number of blocks in
which arm i i i remains active, and σ i \sigma_i σ i is its position in the elimination order, with ties broken arbitrarily and surviving arms listed last. Then τ i ≤ j i \tau_i \le j_i τ i ≤ j i , and
Reg N ( t B ) = ∑ i : Δ i > 0 Δ i ⋅ S τ i . \operatorname{Reg}_{N}(t_B)=\sum_{i:\Delta_i>0}\Delta_i\cdot S_{\tau_i}. Reg N ( t B ) = i : Δ i > 0 ∑ Δ i ⋅ S τ i .
Whenever arm i i i remains active, there are at least N − σ i + 1 N-\sigma_i+1 N − σ i + 1 active arms. Hence,
S τ i = ∑ k = 1 τ i b k n k ≤ ∑ k = 1 τ i b k N − σ i + 1 = t τ i N − σ i + 1 ≤ ( 1 + α ) t τ i − 1 N − σ i + 1 . S_{\tau_i}=\sum_{k=1}^{\tau_i}\frac{b_k}{n_k}\le\sum_{k=1}^{\tau_i}\frac{b_k}{N-\sigma_i+1}=\frac{t_{\tau_i}}{N-\sigma_i+1}\le\frac{(1+\alpha)t_{\tau_i-1}}{N-\sigma_i+1}. S τ i = k = 1 ∑ τ i n k b k ≤ k = 1 ∑ τ i N − σ i + 1 b k = N − σ i + 1 t τ i ≤ N − σ i + 1 ( 1 + α ) t τ i − 1 .
Since τ i ≤ j i \tau_i\le j_i τ i ≤ j i , the definition of j i j_i j i gives, for τ i ≥ 2 \tau_i\ge2 τ i ≥ 2 ,
t τ i − 1 N ≤ S τ i − 1 < 4 γ log ( N T ) Δ i 2 . \frac{t_{\tau_i-1}}{N}\le S_{\tau_i-1}<\frac{4\gamma\log(NT)}{\Delta_i^2}. N t τ i − 1 ≤ S τ i − 1 < Δ i 2 4 γ log ( N T ) .
Consequently,
t τ i − 1 ≤ 4 γ log ( N T ) N Δ i 2 . t_{\tau_i-1}\le\frac{4\gamma\log(NT)N}{\Delta_i^2}. t τ i − 1 ≤ Δ i 2 4 γ log ( N T ) N .
The same bound holds for τ i = 1 \tau_i=1 τ i = 1 , using t 0 = 1 t_0=1 t 0 = 1 and the choice of γ \gamma γ in Lemma 1. Moreover,
∑ i : Δ i > 0 1 N − σ i + 1 ≤ ∑ n = 1 N 1 n ≤ 1 + ln N , \sum_{i:\Delta_i>0}\frac{1}{N-\sigma_i+1}\le\sum_{n=1}^{N}\frac{1}{n}\le1+\ln N, i : Δ i > 0 ∑ N − σ i + 1 1 ≤ n = 1 ∑ N n 1 ≤ 1 + ln N ,
since ( σ i ) i ∈ [ N ] (\sigma_i)_{i\in[N]} ( σ i ) i ∈ [ N ] is a permutation of [ N ] [N] [ N ] . Combining these bounds, we have
Reg N ( t B ) = ∑ i : Δ i > 0 Δ i ⋅ S τ i ≤ ∑ i : Δ i > 0 Δ i ( 1 + α ) t τ i − 1 N − σ i + 1 ≤ ∑ i : Δ i > 0 Δ i 4 γ log ( N T ) N Δ i 2 1 + α N − σ i + 1 \begin{aligned}
\operatorname{Reg}_{N}(t_B)=\sum_{i:\Delta_i>0}\Delta_i\cdot S_{\tau_i} \\
&\le\sum_{i:\Delta_i>0}\Delta_i\frac{(1+\alpha)t_{\tau_i-1}}{N-\sigma_i+1} \\
&\le\sum_{i:\Delta_i>0}\Delta_i\frac{4\gamma\log(NT)N}{\Delta_i^2}\frac{1+\alpha}{N-\sigma_i+1}
\end{aligned} Reg N ( t B ) = i : Δ i > 0 ∑ Δ i ⋅ S τ i ≤ i : Δ i > 0 ∑ Δ i N − σ i + 1 ( 1 + α ) t τ i − 1 ≤ i : Δ i > 0 ∑ Δ i Δ i 2 4 γ log ( N T ) N N − σ i + 1 1 + α
≤ 4 γ ( 1 + α ) ( 1 + ln N ) log ( N T ) N Δ min . \le4\gamma(1+\alpha)(1+\ln N)\log(NT)\frac{N}{\Delta_{\min}}. ≤ 4 γ ( 1 + α ) ( 1 + ln N ) log ( N T ) Δ m i n N .
By Lemma 1, Pr [ E g o o d ] ≥ 1 − 1 / T \Pr[E^{\mathrm{good}}]\ge1-1/T Pr [ E good ] ≥ 1 − 1/ T . Since the regret is at most T = t B T=t_B T = t B , the contribution of bad events to the expected regret is at most 1 1 1 . Using α ≥ 1 \alpha\ge1 α ≥ 1 and N ≥ 2 N\ge2 N ≥ 2 , we obtain
E [ Reg N ( t B ) ] ≤ 4 γ ( 1 + α ) ( 1 + ln N ) log ( N T ) N Δ min + 1 = O ( α log N log ( N T ) N Δ min ) , \mathbb{E}\left[\operatorname{Reg}_{N}(t_B)\right]\le4\gamma(1+\alpha)(1+\ln N)\log(NT)\frac{N}{\Delta_{\min}}+1=O\left(\alpha\log N\log(NT)\frac{N}{\Delta_{\min}}\right), E [ Reg N ( t B ) ] ≤ 4 γ ( 1 + α ) ( 1 + ln N ) log ( N T ) Δ m i n N + 1 = O ( α log N log ( N T ) Δ m i n N ) ,
which completes the proof.
Lower Bounds for Stochastic Bandits
Lower Bounds Extended from [9 ]
Gap-Dependent Lower Bound. We first give a bounded-reward analogue of [9 Lemma 2] . The proof follows the same multiple-hypothesis testing argument, but uses Bernoulli reward distributions instead of Gaussian ones.
Lemma 4. For every N ≥ 2 N \ge2 N ≥ 2 and every 0 < Δ ≤ 1 / 8 0 < \Delta\le1/8 0 < Δ ≤ 1/8 , and every batched policy, there exists an N N N -armed stochastic bandit instance with Bernoulli rewards, with all means in [ 0 , 1 ] [0,1] [ 0 , 1 ] and all nonzero gaps belonging to { Δ , 2 Δ } \{\Delta,2\Delta\} { Δ , 2Δ } , such that every batched policy satisfies
E [ Reg ] ≥ Δ 4 ∑ j = 1 B b j exp ( − C 0 ⋅ t j − 1 Δ 2 N − 1 ) , \mathbb{E}[\operatorname{Reg}] \ge\frac{\Delta}{4} \sum_{j=1}^{B} b_j \exp\left(-C_0 \cdot\frac{t_{j-1}\Delta^2}{N-1}\right), E [ Reg ] ≥ 4 Δ j = 1 ∑ B b j exp ( − C 0 ⋅ N − 1 t j − 1 Δ 2 ) , where C 0 > 0 C_0 > 0 C 0 > 0 is a universal numerical constant.
Proof. Fix Δ ≤ 1 / 8 \Delta\le1/8 Δ ≤ 1/8 . We construct N N N candidate bandit instances P 1 , … , P N P_1,\ldots,P_N P 1 , … , P N . Under P 1 P_1 P 1 , the arm reward distributions are
P 1 = Bern ( 1 2 + Δ ) ⊗ Bern ( 1 2 ) ⊗ ( N − 1 ) . P_1 = \operatorname{Bern}\left(\frac{1}{2}+\Delta\right) \otimes\operatorname{Bern}\left(\frac{1}{2}\right)^{\otimes(N-1)}. P 1 = Bern ( 2 1 + Δ ) ⊗ Bern ( 2 1 ) ⊗ ( N − 1 ) . For every i ∈ { 2 , … , N } i \in\{2,\ldots,N\} i ∈ { 2 , … , N } , define
P i = Bern ( 1 2 + Δ ) ⊗ Bern ( 1 2 ) ⊗ ⋯ ⊗ Bern ( 1 2 + 2 Δ ) ⊗ ⋯ ⊗ Bern ( 1 2 ) , P_i = \operatorname{Bern}\left(\frac{1}{2}+\Delta\right) \otimes\operatorname{Bern}\left(\frac{1}{2}\right) \otimes\cdots\otimes\operatorname{Bern}\left(\frac{1}{2}+2\Delta\right) \otimes\cdots\otimes\operatorname{Bern}\left(\frac{1}{2}\right), P i = Bern ( 2 1 + Δ ) ⊗ Bern ( 2 1 ) ⊗ ⋯ ⊗ Bern ( 2 1 + 2Δ ) ⊗ ⋯ ⊗ Bern ( 2 1 ) , where the i i i -th arm has a mean of 1 / 2 + 2 Δ 1/2 + 2\Delta 1/2 + 2Δ . As Δ ≤ 1 / 8 \Delta\le1/8 Δ ≤ 1/8 ,
1 / 2 ≤ 1 / 2 + Δ ≤ 1 / 2 + 2 Δ ≤ 3 / 4 , 1/2 \le1/2+\Delta\le1/2+2\Delta\le3/4, 1/2 ≤ 1/2 + Δ ≤ 1/2 + 2Δ ≤ 3/4 , so every reward distribution is supported on { 0 , 1 } \{0,1\} { 0 , 1 } and has mean in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Moreover, under P 1 P_1 P 1 , arm 1 is optimal, and every other arm has gap exactly Δ \Delta Δ . Under P i P_i P i for each i ≥ 2 i \ge2 i ≥ 2 , arm i i i is optimal; arm 1 has gap Δ \Delta Δ , while every arm k ∉ { 1 , i } k \notin\{1,i\} k ∈ / { 1 , i } has gap 2 Δ 2\Delta 2Δ . Hence every nonzero gap belongs to { Δ , 2 Δ } \{\Delta,2\Delta\} { Δ , 2Δ } , and in particular is at most 2 Δ ≤ 1 / 4 2\Delta\le1/4 2Δ ≤ 1/4 .
For a round t t t belonging to batch j j j , let P i t P_i^t P i t denote the distribution, under instance P i P_i P i , of all information available to the learner when the action at time t t t is selected. Since no feedback from the current batch is available before the batch ends, P i t P_i^t P i t depends only on observations from the first j − 1 j-1 j − 1 batches. Every incorrect arm choice incurs instantaneous regret of at least Δ \Delta Δ under each P i P_i P i . Therefore,
sup i ∈ [ N ] E i [ Reg ] ≥ 1 N ∑ i = 1 N E i [ Reg ] ≥ Δ ∑ t = 1 T 1 N ∑ i = 1 N P i t ( i t ≠ i ) . \sup_{i \in[N]} \mathbb{E}_i[\operatorname{Reg}] \ge\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}_i[\operatorname{Reg}] \ge\Delta\sum_{t=1}^{T} \frac{1}{N}\sum_{i=1}^{N} P_i^t(i_t \ne i). i ∈ [ N ] sup E i [ Reg ] ≥ N 1 i = 1 ∑ N E i [ Reg ] ≥ Δ t = 1 ∑ T N 1 i = 1 ∑ N P i t ( i t = i ) . We apply the same multiple-hypothesis testing inequality used in [9 ] with the star tree having edges ( 1 , 2 ) , ( 1 , 3 ) , … , ( 1 , N ) (1,2),(1,3),\ldots,(1,N) ( 1 , 2 ) , ( 1 , 3 ) , … , ( 1 , N ) . For every t t t ,
1 N ∑ i = 1 N P i t ( i t ≠ i ) ≥ 1 2 N ∑ i = 2 N exp ( − D K L ( P 1 t ∥ P i t ) ) . \frac{1}{N}\sum_{i=1}^{N} P_i^t(i_t \ne i) \ge\frac{1}{2N}\sum_{i=2}^{N} \exp\left(-D_{\mathrm{KL}}(P_1^t\Vert P_i^t)\right). N 1 i = 1 ∑ N P i t ( i t = i ) ≥ 2 N 1 i = 2 ∑ N exp ( − D KL ( P 1 t ∥ P i t ) ) . The instances P 1 P_1 P 1 and P i P_i P i differ only in the reward distribution of arm i i i : under P 1 P_1 P 1 it is Bern ( 1 / 2 ) \operatorname{Bern}(1/2) Bern ( 1/2 ) , whereas under P i P_i P i it is Bern ( 1 / 2 + 2 Δ ) \operatorname{Bern}(1/2+2\Delta) Bern ( 1/2 + 2Δ ) . Hence, the standard KL chain rule for bandit observations gives
D K L ( P 1 t ∥ P i t ) = E 1 [ t i ] d Δ , (6) D_{\mathrm{KL}}(P_1^t\Vert P_i^t) = \mathbb{E}_1[t_i]d_\Delta, \tag*{(6)} D KL ( P 1 t ∥ P i t ) = E 1 [ t i ] d Δ , (6) where t i t_i t i is the number of times arm i i i has been pulled before the current batch and
d Δ = D K L ( Bern ( 1 / 2 ) ∥ Bern ( 1 / 2 + 2 Δ ) ) d_\Delta= D_{\mathrm{KL}}\left(\operatorname{Bern}(1/2)\Vert\operatorname{Bern}(1/2+2\Delta)\right) d Δ = D KL ( Bern ( 1/2 ) ∥ Bern ( 1/2 + 2Δ ) ) = 1 2 log 1 / 2 1 / 2 + 2 Δ + 1 2 log 1 / 2 1 / 2 − 2 Δ = \frac{1}{2}\log\frac{1/2}{1/2+2\Delta}+\frac{1}{2}\log\frac{1/2}{1/2-2\Delta} = 2 1 log 1/2 + 2Δ 1/2 + 2 1 log 1/2 − 2Δ 1/2 = − 1 2 log ( 1 − 16 Δ 2 ) . = -\frac{1}{2}\log(1-16\Delta^2). = − 2 1 log ( 1 − 16 Δ 2 ) .
Since Δ ≤ 1 / 8 \Delta\le1/8 Δ ≤ 1/8 , we have 16 Δ 2 ≤ 1 / 4 16\Delta^2 \le1/4 16 Δ 2 ≤ 1/4 . Using
− log ( 1 − x ) ≤ x 1 − x , -\log(1-x) \le\frac{x}{1-x}, − log ( 1 − x ) ≤ 1 − x x ,
where 0 ≤ x < 1 0 \le x < 1 0 ≤ x < 1 , we obtain
d Δ ≤ 1 2 16 Δ 2 1 − 16 Δ 2 ≤ C 0 Δ 2 . d_{\Delta} \le\frac{1}{2}\frac{16\Delta^2}{1-16\Delta^2} \le C_0\Delta^2. d Δ ≤ 2 1 1 − 16 Δ 2 16 Δ 2 ≤ C 0 Δ 2 .
For t t t in batch j j j , all observations available to the learner come from the first t j − 1 t_{j-1} t j − 1 rounds. Consequently,
∑ i = 2 N E 1 [ t i ] ≤ t j − 1 . \sum_{i=2}^{N}\mathbb{E}_1[t_i] \le t_{j-1}. i = 2 ∑ N E 1 [ t i ] ≤ t j − 1 .
Together, by Jensen’s inequality, we have
1 N ∑ i = 1 N P i t ( i ≠ i ) ≥ 1 2 N ∑ i = 2 N exp ( − d Δ E 1 [ t i ] ) ≥ N − 1 2 N exp ( − d Δ N − 1 ∑ i = 2 N E 1 [ t i ] ) ≥ 1 4 exp ( − C 0 t j − 1 Δ 2 N − 1 ) . \begin{aligned}
\frac{1}{N}\sum_{i=1}^{N}P_i^t(i\ne i) \ge\frac{1}{2N}\sum_{i=2}^{N}\exp(-d_{\Delta}\mathbb{E}_1[t_i]) \\
&\ge\frac{N-1}{2N}\exp\left(-\frac{d_{\Delta}}{N-1}\sum_{i=2}^{N}\mathbb{E}_1[t_i]\right) \\
&\ge\frac{1}{4}\exp\left(-C_0\frac{t_{j-1}\Delta^2}{N-1}\right).
\end{aligned} N 1 i = 1 ∑ N P i t ( i = i ) ≥ 2 N 1 i = 2 ∑ N exp ( − d Δ E 1 [ t i ]) ≥ 2 N N − 1 exp ( − N − 1 d Δ i = 2 ∑ N E 1 [ t i ] ) ≥ 4 1 exp ( − C 0 N − 1 t j − 1 Δ 2 ) .
Summing over all b j b_j b j rounds in batch j j j gives
sup i ∈ [ N ] E i [ Reg ] ≥ Δ 4 ∑ j = 1 B b j exp ( − C 0 t j − 1 Δ 2 N − 1 ) , \sup_{i\in[N]}\mathbb{E}_i[\operatorname{Reg}] \ge\frac{\Delta}{4}\sum_{j=1}^{B}b_j\exp\left(-C_0\frac{t_{j-1}\Delta^2}{N-1}\right), i ∈ [ N ] sup E i [ Reg ] ≥ 4 Δ j = 1 ∑ B b j exp ( − C 0 N − 1 t j − 1 Δ 2 ) ,
which marks the end of the proof. □
Now we are ready to prove Proposition 1.
Proof of Proposition 1. We consider a broad family of hard instances that satisfy t j ∗ − 1 ≥ C N t_{j^*-1} \ge CN t j ∗ − 1 ≥ C N . Taking advantage of Lemma 4, we have
Δ ⋅ E [ Reg N ( B ) ] ≥ Δ 2 ⋅ ∑ j = 1 B t j − t j − 1 4 exp ( − C 0 t j − 1 Δ 2 N − 1 ) = Δ 2 ⋅ ∑ j = 1 B b j 4 exp ( − C 0 t j − 1 Δ 2 N − 1 ) ≥ Δ 2 ⋅ b j ∗ 4 exp ( − C 0 t j ∗ − 1 Δ 2 N − 1 ) , \begin{aligned}
\Delta\cdot\mathbb{E}\left[\operatorname{Reg}^{(B)}_N\right]\ge\Delta^2\cdot\sum_{j=1}^{B}\frac{t_j-t_{j-1}}{4}\exp\left(-\frac{C_0t_{j-1}\Delta^2}{N-1}\right) \\
&=\Delta^2\cdot\sum_{j=1}^{B}\frac{b_j}{4}\exp\left(-\frac{C_0t_{j-1}\Delta^2}{N-1}\right) \\
&\ge\Delta^2\cdot\frac{b_{j^*}}{4}\exp\left(-\frac{C_0t_{j^*-1}\Delta^2}{N-1}\right),
\end{aligned} Δ ⋅ E [ Reg N ( B ) ] ≥ Δ 2 ⋅ j = 1 ∑ B 4 t j − t j − 1 exp ( − N − 1 C 0 t j − 1 Δ 2 ) = Δ 2 ⋅ j = 1 ∑ B 4 b j exp ( − N − 1 C 0 t j − 1 Δ 2 ) ≥ Δ 2 ⋅ 4 b j ∗ exp ( − N − 1 C 0 t j ∗ − 1 Δ 2 ) ,
where we set j ∗ j^* j ∗ to be the block index chosen by α \alpha α , i.e., α = max j b j t j − 1 = b j ∗ t j ∗ − 1 \alpha=\max_j\frac{b_j}{t_{j-1}}=\frac{b_{j^*}}{t_{j^*-1}} α = max j t j − 1 b j = t j ∗ − 1 b j ∗ . Next, we consider a case where every sub-optimal arm has the smallest gap Δ = Δ i : i ≠ i ∗ = N − 1 C 0 t j ∗ − 1 \Delta= \Delta_{i:i\ne i^*} = \sqrt{\frac{N-1}{C_0t_{j^*-1}}} Δ = Δ i : i = i ∗ = C 0 t j ∗ − 1 N − 1 , which leads to
Δ ⋅ E [ Reg N ( B ) ] ≥ Δ 2 ⋅ b j ∗ 4 exp ( − C 0 t j ∗ − 1 Δ 2 N − 1 ) ≥ N − 1 t j ∗ − 1 b j ∗ 4 exp ( − C 0 t j ∗ − 1 N − 1 N − 1 t j ∗ − 1 ) = Ω ( 1 ) ⋅ b j ∗ t j ∗ − 1 N = Ω ( 1 ) ⋅ α N . \begin{aligned}
\Delta\cdot\mathbb{E}\left[\operatorname{Reg}^{(B)}_N\right] \ge\Delta^2 \cdot\frac{b_{j^*}}{4}\exp\left(-\frac{C_0t_{j^*-1}\Delta^2}{N-1}\right) \\
&\ge\frac{N-1}{t_{j^*-1}}\frac{b_{j^*}}{4}\exp\left(-\frac{C_0t_{j^*-1}}{N-1}\frac{N-1}{t_{j^*-1}}\right) \\
&= \Omega(1)\cdot\frac{b_{j^*}}{t_{j^*-1}}N = \Omega(1)\cdot\alpha N.
\end{aligned} Δ ⋅ E [ Reg N ( B ) ] ≥ Δ 2 ⋅ 4 b j ∗ exp ( − N − 1 C 0 t j ∗ − 1 Δ 2 ) ≥ t j ∗ − 1 N − 1 4 b j ∗ exp ( − N − 1 C 0 t j ∗ − 1 t j ∗ − 1 N − 1 ) = Ω ( 1 ) ⋅ t j ∗ − 1 b j ∗ N = Ω ( 1 ) ⋅ α N .
We note that, based on the hard instance construction (t j ∗ − 1 ≥ C N t_{j^*-1} \ge CN t j ∗ − 1 ≥ C N ), Δ = N − 1 C 0 t j ∗ − 1 ≤ 1 / 8 \Delta= \sqrt{\frac{N-1}{C_0t_{j^*-1}}} \le1/8 Δ = C 0 t j ∗ − 1 N − 1 ≤ 1/8 is a valid bounded-reward gap. Finally, we have
Δ ⋅ E [ Reg N ( B ) ] ≥ Ω ( 1 ) ⋅ N α ⟺ E [ Reg N ( B ) ] ≥ Ω ( 1 ) ⋅ α N Δ = Ω ( α ∑ i ≠ i ∗ Δ i − 1 ) . \Delta\cdot\mathbb{E}\left[\operatorname{Reg}^{(B)}_N\right] \ge\Omega(1)\cdot N\alpha\Longleftrightarrow\mathbb{E}\left[\operatorname{Reg}^{(B)}_N\right] \ge\Omega(1)\cdot\alpha\frac{N}{\Delta} = \Omega\left(\alpha\sum_{i\ne i^*}\Delta_i^{-1}\right). Δ ⋅ E [ Reg N ( B ) ] ≥ Ω ( 1 ) ⋅ N α ⟺ E [ Reg N ( B ) ] ≥ Ω ( 1 ) ⋅ α Δ N = Ω α i = i ∗ ∑ Δ i − 1 .
which completes the proof.
Gap-Independent Lower Bound. Similar to the proof of Proposition 1, we consider a family of hard instances that satisfy t j ∗ − 1 ≥ C N t_{j^*-1} \ge CN t j ∗ − 1 ≥ C N and t j ∗ − 1 ≥ Ω ( T / α ) t_{j^*-1} \ge\Omega(T/\alpha) t j ∗ − 1 ≥ Ω ( T / α ) , where, intuitively speaking, the second part asks that the hard instance’s largest relative batch must occur late enough. Based on the proof of Proposition 1, we have
E [ Reg N ( B ) ] ≥ Δ ⋅ ∑ j = 1 B t j − t j − 1 4 exp ( − C 0 t j − 1 Δ 2 N − 1 ) = Δ ⋅ ∑ j = 1 B b j 4 exp ( − C 0 t j − 1 Δ 2 N − 1 ) ≥ Δ 4 b j ∗ exp ( − C 0 t j ∗ − 1 Δ 2 N − 1 ) = e − 1 4 C 0 b j ∗ N − 1 t j ∗ − 1 . \begin{aligned}
\mathbb{E}\left[\operatorname{Reg}^{(B)}_N\right] \ge\Delta\cdot\sum_{j=1}^{B}\frac{t_j-t_{j-1}}{4}\exp\left(-\frac{C_0t_{j-1}\Delta^2}{N-1}\right) \\
&= \Delta\cdot\sum_{j=1}^{B}\frac{b_j}{4}\exp\left(-\frac{C_0t_{j-1}\Delta^2}{N-1}\right) \\
&\ge\frac{\Delta}{4}b_{j^*}\exp\left(-\frac{C_0t_{j^*-1}\Delta^2}{N-1}\right) \\
&= \frac{e^{-1}}{4\sqrt{C_0}}b_{j^*}\sqrt{\frac{N-1}{t_{j^*-1}}}.
\end{aligned} E [ Reg N ( B ) ] ≥ Δ ⋅ j = 1 ∑ B 4 t j − t j − 1 exp ( − N − 1 C 0 t j − 1 Δ 2 ) = Δ ⋅ j = 1 ∑ B 4 b j exp ( − N − 1 C 0 t j − 1 Δ 2 ) ≥ 4 Δ b j ∗ exp ( − N − 1 C 0 t j ∗ − 1 Δ 2 ) = 4 C 0 e − 1 b j ∗ t j ∗ − 1 N − 1 .
Recall b j ∗ = Θ ( α t j ∗ − 1 ) b_{j^*} = \Theta(\alpha t_{j^*-1}) b j ∗ = Θ ( α t j ∗ − 1 ) and the condition of t j ∗ − 1 = Ω ( T α ) t_{j^*-1} = \Omega\left(\frac{T}{\alpha}\right) t j ∗ − 1 = Ω ( α T ) , we have
E [ Reg N ( B ) ] ≥ Ω ( 1 ) ⋅ α N t j ∗ − 1 ≥ Ω ( 1 ) ⋅ α N T . \mathbb{E}\left[\operatorname{Reg}^{(B)}_N\right] \ge\Omega(1)\cdot\alpha\sqrt{Nt_{j^*-1}} \ge\Omega(1)\cdot\sqrt{\alpha NT}. E [ Reg N ( B ) ] ≥ Ω ( 1 ) ⋅ α N t j ∗ − 1 ≥ Ω ( 1 ) ⋅ α N T .
An Improved Gap-Dependent Lower Bound
Proof. Set δ = 1 16 N \delta= \frac{1}{16\sqrt{N}} δ = 16 N 1 . For every unordered pair { u , v } ⊆ [ N ] \{u,v\}\subseteq[N] { u , v } ⊆ [ N ] , define two instances ν u , v + \nu^+_{u,v} ν u , v + and ν u , v − \nu^-_{u,v} ν u , v − . Under ν u , v + \nu^+_{u,v} ν u , v + ,
μ u = 1 2 + δ 2 , μ v = 1 2 − δ 2 , \mu_u=\frac{1}{2}+\frac{\delta}{2},\quad\mu_v=\frac{1}{2}-\frac{\delta}{2}, μ u = 2 1 + 2 δ , μ v = 2 1 − 2 δ ,
while every arm i ∉ { u , v } i\notin\{u,v\} i ∈ / { u , v } has deterministic reward 0 0 0 . Under ν u , v − \nu^-_{u,v} ν u , v − , the means of u u u and v v v are exchanged, i.e.,
μ u = 1 2 − δ 2 , μ v = 1 2 + δ 2 , \mu_u=\frac{1}{2}-\frac{\delta}{2},\quad\mu_v=\frac{1}{2}+\frac{\delta}{2}, μ u = 2 1 − 2 δ , μ v = 2 1 + 2 δ ,
The two special arms have Bernoulli rewards.
Our hard distribution samples { U , V } ∼ Unif ( ( [ N ] 2 ) ) \{U,V\} \sim\operatorname{Unif}\left(\binom{[N]}{2}\right) { U , V } ∼ Unif ( ( 2 [ N ] ) ) , and independently samples S ∈ { + , − } S \in\{+,-\} S ∈ { + , − } uniformly. The resulting instance is ν U , V S \nu_{U,V}^{S} ν U , V S . The batch structure is set to be B = { N , N 2 , N 3 } \mathcal{B}=\{N,N^{2},N^{3}\} B = { N , N 2 , N 3 } , which gives α = max { N , N 2 N , N 3 N + N 2 } = Θ ( N ) \alpha=\max\left\{N,\frac{N^{2}}{N},\frac{N^{3}}{N+N^{2}}\right\}=\Theta(N) α = max { N , N N 2 , N + N 2 N 3 } = Θ ( N ) . We first focus on the deterministic algorithm and extend to the randomized algorithm at the end.
The First Batch. Recall that the first batch has N N N rounds without any prior feedback. Let m i m_i m i be the number of times that arm i i i has been pulled in the first batch; then ∑ i = 1 N m i = N \sum_{i=1}^{N}m_i=N ∑ i = 1 N m i = N . Define the set of arms that are not heavily sampled (less than 3 times) in the first batch as L = { i ∈ [ N ] : m i ≤ 2 } \mathcal{L}=\{i\in[N]:m_i\le2\} L = { i ∈ [ N ] : m i ≤ 2 } . Since every arm outside L \mathcal{L} L is pulled at least three times, we have
3 ( N − ∣ L ∣ ) ≤ ∑ i = 1 N m i = N 3(N-|\mathcal{L}|)\le\sum_{i=1}^{N}m_i=N 3 ( N − ∣ L ∣ ) ≤ i = 1 ∑ N m i = N
and hence ∣ L ∣ ≥ 2 N 3 |\mathcal{L}|\ge\frac{2N}{3} ∣ L ∣ ≥ 3 2 N . Let E E E be the event that all rewards received in the first batch are 0, and define F = E ∩ { U , V ∈ L } F=E\cap\{U,V\in\mathcal{L}\} F = E ∩ { U , V ∈ L } . Recall that μ i ≤ 1 2 + δ 2 < 1 2 + 1 4 = 3 4 \mu_i\le\frac{1}{2}+\frac{\delta}{2}<\frac{1}{2}+\frac{1}{4}=\frac{3}{4} μ i ≤ 2 1 + 2 δ < 2 1 + 4 1 = 4 3 as δ = 1 16 N < 1 / 2 \delta=\frac{1}{16\sqrt{N}}<1/2 δ = 16 N 1 < 1/2 . For any u , v ∈ L u,v\in\mathcal{L} u , v ∈ L and either S = + S=+ S = + or S = − S=- S = − , both special arms have means smaller than 3 / 4 3/4 3/4 . Therefore,
Pr [ r i = 0 ∣ i ∈ { u , v } ] ≥ 1 4 \Pr[r_i=0\mid i\in\{u,v\}]\ge\frac{1}{4} Pr [ r i = 0 ∣ i ∈ { u , v }] ≥ 4 1
Moreover, m u + m v ≤ 4 m_u+m_v\le4 m u + m v ≤ 4 . Thus,
Pr [ E ∣ U = u , V = v , S ] ≥ 4 − ( m u + m v ) ≥ 4 − 4 = Ω ( 1 ) . \Pr[E\mid U=u,V=v,S]\ge4^{-(m_u+m_v)}\ge4^{-4}=\Omega(1). Pr [ E ∣ U = u , V = v , S ] ≥ 4 − ( m u + m v ) ≥ 4 − 4 = Ω ( 1 ) .
Consequently,
Pr [ F ] = Pr [ U , V ∈ L ] ⋅ Pr [ E ∣ U , V ∈ L ] ≥ ( ∣ L ∣ 2 ) ( N 2 ) 4 − 4 = Ω ( 1 ) . \Pr[F]=\Pr[U,V\in\mathcal{L}]\cdot\Pr[E\mid U,V\in\mathcal{L}]
\ge\frac{\binom{|\mathcal{L}|}{2}}{\binom{N}{2}}4^{-4}=\Omega(1). Pr [ F ] = Pr [ U , V ∈ L ] ⋅ Pr [ E ∣ U , V ∈ L ] ≥ ( 2 N ) ( 2 ∣ L ∣ ) 4 − 4 = Ω ( 1 ) .
The Second Batch. Conditioned on event E E E , the learner observes the same all-zero history regardless of the underlying pair and sign. Let q i q_i q i be the number of pulls of arm i i i in the second batch. Since the algorithm is deterministic, ∑ i = 1 N q i = N 2 \sum_{i=1}^{N}q_i=N^2 ∑ i = 1 N q i = N 2 , and the values q 1 , … , q N q_1,\ldots,q_N q 1 , … , q N are fixed conditioned on E E E . For u , v ∈ L u,v\in\mathcal{L} u , v ∈ L , we denote p u , v = Pr [ E ∣ U = u , V = v ] p_{u,v}=\Pr[E\mid U=u,V=v] p u , v = Pr [ E ∣ U = u , V = v ] , where the probability averages over the random sign S S S . By the argument above, p u , v ≥ 4 − 4 p_{u,v}\ge4^{-4} p u , v ≥ 4 − 4 . We check the expected sample complexity of special arms in the second batch conditioning on F F F :
E [ q U + q V ∣ F ] = ∑ u < v ; u , v ∈ L p u , v ⋅ ( q u + q v ) ∑ u < v ; u , v ∈ L p u , v ≤ ∑ u < v ; u , v ∈ L ( q u + q v ) ∑ u < v ; u , v ∈ L p u , v \mathbb{E}[q_U+q_V\mid F]
=\frac{\sum_{u<v;\,u,v\in\mathcal{L}}p_{u,v}\cdot(q_u+q_v)}
{\sum_{u<v;\,u,v\in\mathcal{L}}p_{u,v}}
\le\frac{\sum_{u<v;\,u,v\in\mathcal{L}}(q_u+q_v)}
{\sum_{u<v;\,u,v\in\mathcal{L}}p_{u,v}} E [ q U + q V ∣ F ] = ∑ u < v ; u , v ∈ L p u , v ∑ u < v ; u , v ∈ L p u , v ⋅ ( q u + q v ) ≤ ∑ u < v ; u , v ∈ L p u , v ∑ u < v ; u , v ∈ L ( q u + q v )
as p u , v ≤ 1 p_{u,v}\le1 p u , v ≤ 1 . Moreover, recall that p u , v ≥ 4 − 4 p_{u,v}\ge4^{-4} p u , v ≥ 4 − 4 and note that every q i q_i q i will appear in ( q u + q v ) (q_u+q_v) ( q u + q v ) with a total number of ∣ L ∣ − 1 |\mathcal{L}|-1 ∣ L ∣ − 1 times. Thus,
∑ u < v ; u , v ∈ L ( q u + q v ) ∑ u < v ; u , v ∈ L p u , v ≤ ( ∣ L ∣ − 1 ) ∑ i ∈ L q i 4 − 4 ( ∣ L ∣ 2 ) ≤ ( ∣ L ∣ − 1 ) N 2 4 − 4 ( ∣ L ∣ 2 ) = O ( N ) , \frac{\sum_{u<v;\,u,v\in\mathcal{L}}(q_u+q_v)}
{\sum_{u<v;\,u,v\in\mathcal{L}}p_{u,v}}
\le\frac{(|\mathcal{L}|-1)\sum_{i\in\mathcal{L}}q_i}
{4^{-4}\binom{|\mathcal{L}|}{2}}
\le\frac{(|\mathcal{L}|-1)N^2}
{4^{-4}\binom{|\mathcal{L}|}{2}}
=O(N), ∑ u < v ; u , v ∈ L p u , v ∑ u < v ; u , v ∈ L ( q u + q v ) ≤ 4 − 4 ( 2 ∣ L ∣ ) ( ∣ L ∣ − 1 ) ∑ i ∈ L q i ≤ 4 − 4 ( 2 ∣ L ∣ ) ( ∣ L ∣ − 1 ) N 2 = O ( N ) ,
where the last step follows from ∣ L ∣ = Ω ( N ) |\mathcal{L}|=\Omega(N) ∣ L ∣ = Ω ( N ) .
The Third Batch. Next, conditioned on event F F F , we fix one ( u , v ) (u,v) ( u , v ) pair with u , v ∈ L u,v \in\mathcal{L} u , v ∈ L form a binary hypothesis testing:
H + : μ u = 1 2 + δ 2 ; μ v = 1 2 − δ 2 , H_{+}: \mu_u = \frac{1}{2}+\frac{\delta}{2};\ \mu_v = \frac{1}{2}-\frac{\delta}{2}, H + : μ u = 2 1 + 2 δ ; μ v = 2 1 − 2 δ ,
and
H − : μ u = 1 2 − δ 2 ; μ v = 1 2 + δ 2 . H_{-}: \mu_u = \frac{1}{2}-\frac{\delta}{2};\ \mu_v = \frac{1}{2}+\frac{\delta}{2}. H − : μ u = 2 1 − 2 δ ; μ v = 2 1 + 2 δ .
We first note that conditioning on the first-batch event E E E does not make the two hypotheses equally likely in general. Nevertheless, since u , v ∈ L u,v \in\mathcal{L} u , v ∈ L , their posterior probabilities remain bounded away from zero. Indeed,
Pr [ E ∣ U = u , V = v , S = + ] Pr [ E ∣ U = u , V = v , S = − ] = ( 1 − δ 2 ) m u ( 1 + δ 2 ) m v ( 1 + δ 2 ) m u ( 1 − δ 2 ) m v = ( 1 − δ 1 + δ ) m u − m v . \frac{\Pr[E \mid U=u,V=v,S=+]}{\Pr[E \mid U=u,V=v,S=-]}=\frac{\left(\frac{1-\delta}{2}\right)^{m_u}\left(\frac{1+\delta}{2}\right)^{m_v}}{\left(\frac{1+\delta}{2}\right)^{m_u}\left(\frac{1-\delta}{2}\right)^{m_v}}=\left(\frac{1-\delta}{1+\delta}\right)^{m_u-m_v}. Pr [ E ∣ U = u , V = v , S = − ] Pr [ E ∣ U = u , V = v , S = + ] = ( 2 1 + δ ) m u ( 2 1 − δ ) m v ( 2 1 − δ ) m u ( 2 1 + δ ) m v = ( 1 + δ 1 − δ ) m u − m v .
Since m u , m v ≤ 2 m_u,m_v \le2 m u , m v ≤ 2 and δ ≤ 1 / 16 \delta\le1/16 δ ≤ 1/16 , this likelihood ratio is bounded above and below by universal constants. In other words, there exists a universal constant c 0 > 0 c_0 > 0 c 0 > 0 such that
Pr [ S = + ∣ E , U = u , V = v ] ≥ c 0 , Pr [ S = − ∣ E , U = u , V = v ] ≥ c 0 . \Pr[S=+ \mid E,U=u,V=v] \ge c_0,\quad\Pr[S=- \mid E,U=u,V=v] \ge c_0. Pr [ S = + ∣ E , U = u , V = v ] ≥ c 0 , Pr [ S = − ∣ E , U = u , V = v ] ≥ c 0 .
Let P + P_+ P + and P − P_- P − denote the distribution of the second-batch observations under H + H_+ H + and H − H_- H − conditioned on the first-batch history E E E . Since the second-batch allocation is fixed to be q 1 , … , q N q_1,\ldots,q_N q 1 , … , q N , the KL divergence between the distributions induced by the two hypotheses can be formulated as
D K L ( P + ∥ P − ) = q u ⋅ kl ( 1 + δ 2 , 1 − δ 2 ) + q v ⋅ kl ( 1 − δ 2 , 1 + δ 2 ) , D_{\mathrm{KL}}(P_+ \mathbin{\|} P_-) = q_u \cdot\operatorname{kl}\left(\frac{1+\delta}{2},\frac{1-\delta}{2}\right)+q_v \cdot\operatorname{kl}\left(\frac{1-\delta}{2},\frac{1+\delta}{2}\right), D KL ( P + ∥ P − ) = q u ⋅ kl ( 2 1 + δ , 2 1 − δ ) + q v ⋅ kl ( 2 1 − δ , 2 1 + δ ) ,
where kl ( p ∥ q ) \operatorname{kl}(p\|q) kl ( p ∥ q ) denotes the binary relative entropy. It is easy to see that
kl ( 1 + δ 2 , 1 − δ 2 ) = kl ( 1 − δ 2 , 1 + δ 2 ) = δ log 1 + δ 1 − δ ≤ δ ⋅ 4 δ = 4 δ 2 . \operatorname{kl}\left(\frac{1+\delta}{2},\frac{1-\delta}{2}\right)=\operatorname{kl}\left(\frac{1-\delta}{2},\frac{1+\delta}{2}\right)=\delta\log\frac{1+\delta}{1-\delta}\le\delta\cdot4\delta=4\delta^2. kl ( 2 1 + δ , 2 1 − δ ) = kl ( 2 1 − δ , 2 1 + δ ) = δ log 1 − δ 1 + δ ≤ δ ⋅ 4 δ = 4 δ 2 .
Thus, D K L ( P + ∥ P − ) ≤ 4 δ 2 ( q u + q v ) D_{\mathrm{KL}}(P_+ \mathbin{\|} P_-) \le4\delta^2(q_u+q_v) D KL ( P + ∥ P − ) ≤ 4 δ 2 ( q u + q v ) . Let X i X_i X i denote the number of times that arm i i i is pulled in the third batch. Since the learner cannot update its policy inside the third batch, the vector X 1 , … , X N X_1,\ldots,X_N X 1 , … , X N denote the number of times that arm i i i is pulled in the third batch. Since the learner cannot update its policy inside the third batch, the vector ( X 1 , … , X N ) (X_1,\ldots,X_N) ( X 1 , … , X N ) is determined by the observations available at the end of the second batch. Define the binary test
ϕ = { + , X u ≥ X v , − , X u < X v . \phi=
\begin{cases}
+, & X_u \ge X_v,\\
-, & X_u < X_v.
\end{cases} ϕ = { + , − , X u ≥ X v , X u < X v .
By the Bretagnolle-Huber inequality, we have
Pr + [ ϕ = − ] + Pr − [ ϕ = + ] ≥ 1 2 e − 4 δ 2 ( q u + q v ) . \Pr_+[\phi=-]+\Pr_-[\phi=+]\ge\frac{1}{2}e^{-4\delta^2(q_u+q_v)}. + Pr [ ϕ = − ] + − Pr [ ϕ = + ] ≥ 2 1 e − 4 δ 2 ( q u + q v ) .
Under such false events where suboptimal arms that have a gap of at least δ \delta δ have been pulled at least b 3 / 2 b_3/2 b 3 /2 times, the regret is at least N 3 δ 2 \frac{N^3\delta}{2} 2 N 3 δ . Let π + = Pr [ S = + ∣ E , U = u , V = v ] \pi_+ = \Pr[S=+ \mid E,U=u,V=v] π + = Pr [ S = + ∣ E , U = u , V = v ] and π − = Pr [ S = − ∣ E , U = u , V = v ] \pi_- = \Pr[S=- \mid E,U=u,V=v] π − = Pr [ S = − ∣ E , U = u , V = v ] . Since π + , π − ≥ c 0 \pi_+,\pi_- \ge c_0 π + , π − ≥ c 0 , we have
E [ R 3 ∣ F , U = u , V = v ] ≥ N 3 δ 2 ( π + Pr + [ ϕ = − ] + π − Pr − [ ϕ = + ] ) ≥ c 0 N 3 δ 4 exp ( − 4 δ 2 ( q u + q v ) ) . \begin{aligned}
\mathbb{E}[R_3 \mid F,U=u,V=v] \ge\frac{N^3\delta}{2}\left(\pi_+\Pr_+[\phi=-]+\pi_-\Pr_-[\phi=+]\right) \\
&\ge\frac{c_0N^3\delta}{4}\exp(-4\delta^2(q_u+q_v)).
\end{aligned} E [ R 3 ∣ F , U = u , V = v ] ≥ 2 N 3 δ ( π + + Pr [ ϕ = − ] + π − − Pr [ ϕ = + ] ) ≥ 4 c 0 N 3 δ exp ( − 4 δ 2 ( q u + q v )) .
Taking expectation over ( U , V ) (U,V) ( U , V ) conditioned on F F F and using Jensen’s inequality gives
E [ R 3 ∣ F ] ≥ c 0 N 3 δ 4 E [ exp ( − 4 δ 2 ( q U + q V ) ) ∣ F ] ≥ c 0 N 3 δ 4 exp ( − 4 δ 2 E [ ( q U + q V ) ∣ F ] ) \begin{aligned}
\mathbb{E}[R_3\mid F] \ge\frac{c_0N^3\delta}{4}\mathbb{E}[\exp(-4\delta^2(q_U+q_V))\mid F] \\
&\ge\frac{c_0N^3\delta}{4}\exp\left(-4\delta^2\mathbb{E}[(q_U+q_V)\mid F]\right)
\end{aligned} E [ R 3 ∣ F ] ≥ 4 c 0 N 3 δ E [ exp ( − 4 δ 2 ( q U + q V )) ∣ F ] ≥ 4 c 0 N 3 δ exp ( − 4 δ 2 E [( q U + q V ) ∣ F ] )
Recall that E [ q U + q V ∣ F ] = O ( N ) \mathbb{E}[q_U+q_V\mid F]=O(N) E [ q U + q V ∣ F ] = O ( N ) and δ = 1 16 N \delta=\frac{1}{16\sqrt{N}} δ = 16 N 1 . Therefore, δ 2 E [ ( q U + q V ) ∣ F ] = O ( 1 ) \delta^2\mathbb{E}[(q_U+q_V)\mid F]=O(1) δ 2 E [( q U + q V ) ∣ F ] = O ( 1 ) , and
E [ R 3 ∣ F ] = Ω ( N 3 1 N ) = Ω ( N 5 2 ) . \mathbb{E}[R_3\mid F]=\Omega\left(N^3\frac{1}{\sqrt{N}}\right)=\Omega\left(N^{\frac{5}{2}}\right). E [ R 3 ∣ F ] = Ω ( N 3 N 1 ) = Ω ( N 2 5 ) .
Finally, recall that Pr [ F ] = Ω ( 1 ) \Pr[F]=\Omega(1) Pr [ F ] = Ω ( 1 ) , we have
E [ Reg ] ≥ Pr [ F ] E [ R 3 ∣ F ] = Ω ( N 5 / 2 ) = Ω ( α 3 2 ∑ i : Δ i > 0 Δ i − 1 ) , \mathbb{E}[\operatorname{Reg}]\ge\Pr[F]\mathbb{E}[R_3\mid F]=\Omega(N^{5/2})=\Omega\left(\alpha^{\frac{3}{2}}\sum_{i:\Delta_i>0}\Delta_i^{-1}\right), E [ Reg ] ≥ Pr [ F ] E [ R 3 ∣ F ] = Ω ( N 5/2 ) = Ω ( α 2 3 i : Δ i > 0 ∑ Δ i − 1 ) ,
where the last step follows the fact that one special arm has a gap δ \delta δ in every instance in support of the hard distribution, while the remaining N − 2 N-2 N − 2 non-special arms have gaps that are bounded by universal constants, which gives ∑ i : Δ i > 0 1 Δ i = 1 δ + Θ ( N ) = Θ ( N ) \sum_{i:\Delta_i>0}\frac{1}{\Delta_i}=\frac{1}{\delta}+\Theta(N)=\Theta(N) ∑ i : Δ i > 0 Δ i 1 = δ 1 + Θ ( N ) = Θ ( N ) .
Randomized Algorithms. Let one randomized algorithm A A A ’s internal randomness be w w w . Fixing w w w makes the randomized algorithm a deterministic algorithm, denoted as A w A_w A w , where we have shown that for any deterministic algorithm, there exists a worst instance from a hard prior Π \Pi Π that makes E ν ∼ Π [ Reg ] = Ω ( N 5 / 2 ) \mathbb{E}_{\nu\sim\Pi}[\operatorname{Reg}]=\Omega(N^{5/2}) E ν ∼ Π [ Reg ] = Ω ( N 5/2 ) . Therefore,
E w E ν [ Reg ] = E ν E w [ Reg ] = Ω ( N 5 / 2 ) = Ω ( α 3 2 ∑ i : Δ i > 0 1 Δ i ) . \mathbb{E}_w\mathbb{E}_\nu[\operatorname{Reg}]=\mathbb{E}_\nu\mathbb{E}_w[\operatorname{Reg}]=\Omega(N^{5/2})=\Omega\left(\alpha^{\frac{3}{2}}\sum_{i:\Delta_i>0}\frac{1}{\Delta_i}\right). E w E ν [ Reg ] = E ν E w [ Reg ] = Ω ( N 5/2 ) = Ω ( α 2 3 i : Δ i > 0 ∑ Δ i 1 ) .
which completes the proof.
An Abstract Counterexample of the Current Gap-Dependent Analysis
We examine the comparison step used in the analysis of Algorithm 1. Specifically, we construct an abstract instance with sequences of batch lengths and active-set sizes for which this comparison requires a factor of Ω ( α 7 / 4 ) \Omega(\alpha^{7/4}) Ω ( α 7/4 ) .
Proposition 4. There exists a family of abstract sequences ( b j ) j = 1 B (b_j)_{j=1}^{B} ( b j ) j = 1 B and non-increasing positive integers ( n j ) j = 1 B + 1 (n_j)_{j=1}^{B+1} ( n j ) j = 1 B + 1 such that, writing
S j : = ∑ k = 1 j b k n k , L H S j : = ( n j − n j + 1 ) S j S j − 1 , R H S j : = ( n j − n j + 1 ) S j − 1 ( j = 2 , … , B ) , S_j:=\sum_{k=1}^{j}\frac{b_k}{n_k},\qquad\mathrm{LHS}_j:=(n_j-n_{j+1})\frac{S_j}{\sqrt{S_{j-1}}},\qquad\mathrm{RHS}_j:=(n_j-n_{j+1})\sqrt{S_{j-1}}\quad(j=2,\ldots,B), S j := k = 1 ∑ j n k b k , LHS j := ( n j − n j + 1 ) S j − 1 S j , RHS j := ( n j − n j + 1 ) S j − 1 ( j = 2 , … , B ) , we have
∑ j = 2 B L H S j ∑ j = 2 B R H S j = Θ ( α 7 / 4 ) , \frac{\sum_{j=2}^{B}\mathrm{LHS}_j}{\sum_{j=2}^{B}\mathrm{RHS}_j}=\Theta(\alpha^{7/4}), ∑ j = 2 B RHS j ∑ j = 2 B LHS j = Θ ( α 7/4 ) , where α \alpha α is the hardness metric of ( b j ) j = 1 B (b_j)_{j=1}^{B} ( b j ) j = 1 B .
Proof. Let N N N range over eighth powers of integers, and consider a game of five batches with lengths b j = N 1 2 b_j = N^{\frac{1}{2}} b j = N 2 1 , i.e., b 1 = N 1 2 b_1 = N^{\frac{1}{2}} b 1 = N 2 1 , b 2 = N b_2 = N b 2 = N , b 3 = N 3 2 b_3 = N^{\frac{3}{2}} b 3 = N 2 3 , b 4 = N 2 b_4 = N^2 b 4 = N 2 , b 5 = N 5 2 b_5 = N^{\frac{5}{2}} b 5 = N 2 5 . By definition, we have α = max j b j t j − 1 = Θ ( N 1 / 2 ) \alpha= \max_j \frac{b_j}{t_{j-1}} = \Theta(N^{1/2}) α = max j t j − 1 b j = Θ ( N 1/2 ) . Choose the abstract active-set size as
n 1 = n 2 = n 3 = N , n 4 = N 3 4 , n 5 = N 3 8 , n 6 = 1. n_1 = n_2 = n_3 = N, n_4 = N^{\frac{3}{4}}, n_5 = N^{\frac{3}{8}}, n_6 = 1. n 1 = n 2 = n 3 = N , n 4 = N 4 3 , n 5 = N 8 3 , n 6 = 1.
For j < 3 j < 3 j < 3 , it is easy to see that L H S j = R H S j = 0 \mathrm{LHS}_j = \mathrm{RHS}_j = 0 LHS j = RHS j = 0 as n j − n j + 1 = 0 n_j - n_{j+1} = 0 n j − n j + 1 = 0 . Moreover, we have S 2 = N 1 / 2 N + N N = Θ ( N / N ) = Θ ( 1 ) S_2 = \frac{N^{1/2}}{N} + \frac{N}{N} = \Theta(N/N) = \Theta(1) S 2 = N N 1/2 + N N = Θ ( N / N ) = Θ ( 1 ) . Similarly, we have S 3 = Θ ( N 3 / 2 / N ) = Θ ( N 1 / 2 ) S_3 = \Theta(N^{3/2}/N) = \Theta(N^{1/2}) S 3 = Θ ( N 3/2 / N ) = Θ ( N 1/2 ) , S 4 = Θ ( N 5 / 4 ) S_4 = \Theta(N^{5/4}) S 4 = Θ ( N 5/4 ) , and S 5 = Θ ( N 17 / 8 ) S_5 = \Theta(N^{17/8}) S 5 = Θ ( N 17/8 ) . Plugging the above into ∑ j L H S j \sum_j \mathrm{LHS}_j ∑ j LHS j and ∑ j R H S j \sum_j \mathrm{RHS}_j ∑ j RHS j gives
∑ j = 1 B L H S j = Θ ( 1 ) ⋅ ( N 3 / 2 + N 7 / 4 + N 15 / 8 ) = Θ ( N 15 / 8 ) . \sum_{j=1}^{B} \mathrm{LHS}_j = \Theta(1) \cdot\left(N^{3/2} + N^{7/4} + N^{15/8}\right) = \Theta\left(N^{15/8}\right). j = 1 ∑ B LHS j = Θ ( 1 ) ⋅ ( N 3/2 + N 7/4 + N 15/8 ) = Θ ( N 15/8 ) .
and
∑ j = 1 B R H S j = Θ ( 1 ) ⋅ ( N + N + N ) = Θ ( N ) . \sum_{j=1}^{B} \mathrm{RHS}_j = \Theta(1) \cdot(N + N + N) = \Theta(N). j = 1 ∑ B RHS j = Θ ( 1 ) ⋅ ( N + N + N ) = Θ ( N ) .
Therefore, we have ∑ j L H S j / ∑ j R H S j = N 15 / 8 / N = N 7 / 8 = α 7 / 4 \sum_j \mathrm{LHS}_j/\sum_j \mathrm{RHS}_j = N^{15/8}/N = N^{7/8} = \alpha^{7/4} ∑ j LHS j / ∑ j RHS j = N 15/8 / N = N 7/8 = α 7/4 . Thus, no uniform comparison of these two sums over such abstract sequences can have a multiplicative factor o ( α 7 / 4 ) o(\alpha^{7/4}) o ( α 7/4 ) .
Online Convex Optimization
Online Gradient Descent (OGD) is a classical algorithm for online convex optimization. In the adversarially batched setting, the same algorithm applies, with the only change being that the update is performed once per batch using the aggregate subgradient. Specifically, starting from an arbitrary x ( 1 ) ∈ K x^{(1)} \in\mathcal{K} x ( 1 ) ∈ K , at the end of batch j j j the learner performs the update
x ( j + 1 ) = Π K ( x ( j ) − η z j ) , x^{(j+1)} = \Pi_{\mathcal{K}}\left(x^{(j)} - \eta z_j\right), x ( j + 1 ) = Π K ( x ( j ) − η z j ) ,
where Π K ( y ) = arg min x ∈ K ∥ x − y ∥ 2 \Pi_{\mathcal{K}}(y) = \arg\min_{x \in\mathcal{K}} \|x-y\|_2 Π K ( y ) = arg min x ∈ K ∥ x − y ∥ 2 is Euclidean projection onto K \mathcal{K} K , and η \eta η is the learning rate.
Upper Bound.
Proof of Theorem 5 (Point 1). Fix x ∗ ∈ K x^* \in\mathcal{K} x ∗ ∈ K . For each batch j j j , we define the aggregate loss function F j ( x ) = ∑ t = t j − 1 + 1 t j f t ( x ) F_j(x) = \sum_{t=t_{j-1}+1}^{t_j} f_t(x) F j ( x ) = ∑ t = t j − 1 + 1 t j f t ( x ) . Recall that z j = ∑ t = t j − 1 + 1 t j g t z_j = \sum_{t=t_{j-1}+1}^{t_j} g_t z j = ∑ t = t j − 1 + 1 t j g t . As the sum of convex functions is convex, z j ∈ ∂ F j ( x ( j ) ) z_j \in\partial F_j\left(x^{(j)}\right) z j ∈ ∂ F j ( x ( j ) ) , which implies
F j ( x ( j ) ) − F j ( x ∗ ) ≤ ⟨ z j , x ( j ) − x ∗ ⟩ . F_j\left(x^{(j)}\right) - F_j(x^*) \le\left\langle z_j, x^{(j)} - x^* \right\rangle. F j ( x ( j ) ) − F j ( x ∗ ) ≤ ⟨ z j , x ( j ) − x ∗ ⟩ .
Therefore,
∑ j = 1 B ( F j ( x ( j ) ) − F j ( x ∗ ) ) ≤ ∑ j = 1 B ⟨ z j , x ( j ) − x ∗ ⟩ . \sum_{j=1}^{B} \left(F_j\left(x^{(j)}\right) - F_j(x^*)\right) \le\sum_{j=1}^{B} \left\langle z_j, x^{(j)} - x^* \right\rangle. j = 1 ∑ B ( F j ( x ( j ) ) − F j ( x ∗ ) ) ≤ j = 1 ∑ B ⟨ z j , x ( j ) − x ∗ ⟩ .
It remains to bound the right-hand side using the standard projected OGD argument. By the non-expansiveness of Euclidean projection, and since x ∗ ∈ K x^* \in\mathcal{K} x ∗ ∈ K , Π K ( x ∗ ) = x ∗ \Pi_{\mathcal{K}}(x^*) = x^* Π K ( x ∗ ) = x ∗ , so
∥ x ( j + 1 ) − x ∗ ∥ 2 2 ≤ ∥ Π K ( x ( j ) − η z j ) − Π K ( x ∗ ) ∥ 2 2 . \left\|x^{(j+1)} - x^*\right\|_2^2 \le\left\|\Pi_{\mathcal{K}}\left(x^{(j)} - \eta z_j\right) - \Pi_{\mathcal{K}}(x^*)\right\|_2^2. x ( j + 1 ) − x ∗ 2 2 ≤ Π K ( x ( j ) − η z j ) − Π K ( x ∗ ) 2 2 .
Expanding the square gives
∥ x ( j + 1 ) − x ∗ ∥ 2 2 ≤ ∥ x ( j ) − x ∗ ∥ 2 2 − 2 η ⟨ z j , x ( j ) − x ∗ ⟩ + η 2 ∥ z j ∥ 2 2 \left\|x^{(j+1)}-x^*\right\|_2^2 \le\left\|x^{(j)}-x^*\right\|_2^2 - 2\eta\left\langle z_j,x^{(j)}-x^*\right\rangle+ \eta^2\left\|z_j\right\|_2^2 x ( j + 1 ) − x ∗ 2 2 ≤ x ( j ) − x ∗ 2 2 − 2 η ⟨ z j , x ( j ) − x ∗ ⟩ + η 2 ∥ z j ∥ 2 2
⟺ ⟨ z j , x ( j ) − x ∗ ⟩ ≤ ∥ x ( j ) − x ∗ ∥ 2 2 − ∥ x ( j + 1 ) − x ∗ ∥ 2 2 2 η + η 2 ∥ z j ∥ 2 2 . \Longleftrightarrow\left\langle z_j,x^{(j)}-x^*\right\rangle\le\frac{\left\|x^{(j)}-x^*\right\|_2^2-\left\|x^{(j+1)}-x^*\right\|_2^2}{2\eta}+\frac{\eta}{2}\left\|z_j\right\|_2^2. ⟺ ⟨ z j , x ( j ) − x ∗ ⟩ ≤ 2 η x ( j ) − x ∗ 2 2 − x ( j + 1 ) − x ∗ 2 2 + 2 η ∥ z j ∥ 2 2 .
Summing over j = 1 , … , B j=1,\ldots,B j = 1 , … , B gives
∑ j = 1 B ⟨ z j , x ( j ) − x ∗ ⟩ ≤ ∥ x ( 1 ) − x ∗ ∥ 2 2 − ∥ x ( B ) − x ∗ ∥ 2 2 2 η + η 2 ∥ z j ∥ 2 2 . \sum_{j=1}^{B}\left\langle z_j,x^{(j)}-x^*\right\rangle\le\frac{\left\|x^{(1)}-x^*\right\|_2^2-\left\|x^{(B)}-x^*\right\|_2^2}{2\eta}+\frac{\eta}{2}\left\|z_j\right\|_2^2. j = 1 ∑ B ⟨ z j , x ( j ) − x ∗ ⟩ ≤ 2 η x ( 1 ) − x ∗ 2 2 − x ( B ) − x ∗ 2 2 + 2 η ∥ z j ∥ 2 2 .
As ∥ x ( 1 ) − x ∗ ∥ 2 ≤ D \left\|x^{(1)}-x^*\right\|_2\le D x ( 1 ) − x ∗ 2 ≤ D , we have
∑ j = 1 B ⟨ z j , x ( j ) − x ∗ ⟩ ≤ D 2 2 η + η 2 ∑ j = 1 B ∥ z j ∥ 2 2 ≤ D 2 2 η + η G 2 2 ∥ b ∥ 2 2 , \sum_{j=1}^{B}\left\langle z_j,x^{(j)}-x^*\right\rangle\le\frac{D^2}{2\eta}+\frac{\eta}{2}\sum_{j=1}^{B}\left\|z_j\right\|_2^2\le\frac{D^2}{2\eta}+\frac{\eta G^2}{2}\left\|b\right\|_2^2, j = 1 ∑ B ⟨ z j , x ( j ) − x ∗ ⟩ ≤ 2 η D 2 + 2 η j = 1 ∑ B ∥ z j ∥ 2 2 ≤ 2 η D 2 + 2 η G 2 ∥ b ∥ 2 2 ,
which completes the proof.
Lower Bound
We further show that the dependence on D D D , G G G and ∥ b ∥ 2 \left\|b\right\|_2 ∥ b ∥ 2 is unavoidable. It suffices to consider linear losses, which form a subclass of convex losses.
Proof of Theorem 6 (Point 1). Choose x + , x − ∈ K x^+,x^-\in\mathcal{K} x + , x − ∈ K such that ∥ x + − x − ∥ 2 = D \left\|x^+-x^-\right\|_2=D ∥ x + − x − ∥ 2 = D and define u = x + − x − D u=\frac{x^+-x^-}{D} u = D x + − x − . For every batch j j j , independently sample a Rademacher random variable Z j ∈ { − 1 , + 1 } Z_j\in\{-1,+1\} Z j ∈ { − 1 , + 1 } and let the environment use the linear loss
f t ( x ) = G Z j ⟨ u , x ⟩ f_t(x)=GZ_j\langle u,x\rangle f t ( x ) = G Z j ⟨ u , x ⟩
throughout batch j j j . Since the learner chooses x ( j ) x^{(j)} x ( j ) before observing Z j Z_j Z j ,
E [ G b j Z j ⟨ u , x ( j ) ⟩ ∣ Z 1 , … , Z j − 1 ] = 0. \mathbb{E}\left[G b_j Z_j\langle u,x^{(j)}\rangle\mid Z_1,\ldots,Z_{j-1}\right]=0. E [ G b j Z j ⟨ u , x ( j ) ⟩ ∣ Z 1 , … , Z j − 1 ] = 0.
Hence the learner’s expected cumulative loss is 0.
For the best fixed decision term, since the width of K \mathcal{K} K in direction u u u is D D D , max x ∈ K ⟨ u , x ⟩ − min x ∈ K ⟨ u , x ⟩ = D \max_{x\in\mathcal{K}}\langle u,x\rangle-\min_{x\in\mathcal{K}}\langle u,x\rangle=D max x ∈ K ⟨ u , x ⟩ − min x ∈ K ⟨ u , x ⟩ = D . By symmetry of S S S ,
E [ min x ∈ K ⟨ u , x ⟩ ∑ j = 1 B b j Z j ] = − D G 2 E [ ∣ ∑ j = 1 B b j Z j ∣ ] , \mathbb{E}\left[\min_{x\in\mathcal{K}}\langle u,x\rangle\sum_{j=1}^{B}b_jZ_j\right]=-\frac{DG}{2}\mathbb{E}\left[\left|\sum_{j=1}^{B}b_jZ_j\right|\right], E [ x ∈ K min ⟨ u , x ⟩ j = 1 ∑ B b j Z j ] = − 2 D G E [ j = 1 ∑ B b j Z j ] ,
which indicates that
E [ Reg ] = 0 − ( − D G 2 E [ ∣ ∑ j = 1 B b j Z j ∣ ] ) = D G 2 E [ ∣ ∑ j = 1 B b j Z j ∣ ] . \mathbb{E}[\operatorname{Reg}]=0-\left(-\frac{DG}{2}\mathbb{E}\left[\left|\sum_{j=1}^{B}b_jZ_j\right|\right]\right)=\frac{DG}{2}\mathbb{E}\left[\left|\sum_{j=1}^{B}b_jZ_j\right|\right]. E [ Reg ] = 0 − ( − 2 D G E [ j = 1 ∑ B b j Z j ] ) = 2 D G E [ j = 1 ∑ B b j Z j ] .
Applying the Khintchine inequality (Lemma 7) with p = 1 p=1 p = 1 gives a regret lower bound of Ω ( D G ∑ j = 1 B b j 2 ) = Ω ( D G ∥ b ∥ 2 ) \Omega\left(DG\sqrt{\sum_{j=1}^{B}b_j^2}\right)=\Omega(DG\left\|b\right\|_2) Ω ( D G ∑ j = 1 B b j 2 ) = Ω ( D G ∥ b ∥ 2 ) and completes the proof.
Experts Problem
Hedge5 [8 ] is a classical algorithm for the experts problem. In the non-batched setting, the algorithm maintains a positive weight w i ( t ) w_i^{(t)} w i ( t ) for each expert i ∈ [ N ] i \in[N] i ∈ [ N ] at each round t ∈ [ T ] t \in[T] t ∈ [ T ] . The learner then samples an expert according to the probability distribution p i ( t ) = w i ( t ) ∑ j = 1 N w j ( t ) p_i^{(t)} = \frac{w_i^{(t)}}{\sum_{j=1}^{N} w_j^{(t)}} p i ( t ) = ∑ j = 1 N w j ( t ) w i ( t ) induced by the weights. After observing the losses, the algorithm updates the weights by assigning smaller weights to experts that incur larger losses with a learning rate η > 0 \eta> 0 η > 0 :
w i ( t + 1 ) = w i ( t ) exp ( − η ℓ i ( t ) ) . w_i^{(t+1)} = w_i^{(t)} \exp(-\eta\ell_i^{(t)}). w i ( t + 1 ) = w i ( t ) exp ( − η ℓ i ( t ) ) .
In the adversarially batched setting, the same idea applies, where updates are performed using the cumulative loss observed for each batch. Note that the weights must remain constant within each batch, i.e., w i ( t j − 1 + 1 ) = ⋯ = w i ( t j ) w_i^{(t_{j-1}+1)} = \cdots= w_i^{(t_j)} w i ( t j − 1 + 1 ) = ⋯ = w i ( t j ) . Thus, we re-define the notation w i ( j ) w_i^{(j)} w i ( j ) as the weight for expert i i i at the beginning of batch j j j in the rest of the paper, and write p i ( j ) p_i^{(j)} p i ( j ) for the associated probability accordingly. A pseudo-code is provided in Algorithm 3.
Table 3.
Upper Bound
We show that Hedge naturally adapts to the adversarially batched experts setting. The only change from the standard algorithm is that the multiplicative update is applied once per batch, using the cumulative loss L i ( j ) : = ∑ t = t j − 1 + 1 t j ℓ i ( t ) ∈ [ 0 , b j ] L_i^{(j)} := \sum_{t=t_{j-1}+1}^{t_j} \ell_i^{(t)} \in[0,b_j] L i ( j ) := ∑ t = t j − 1 + 1 t j ℓ i ( t ) ∈ [ 0 , b j ] . Thus, within each batch, the distribution remains fixed, and after observing the cumulative batch losses, the weights are updated as w i ( j + 1 ) = w i ( j ) exp ( − η L i ( j ) ) w_i^{(j+1)} = w_i^{(j)} \exp(-\eta L_i^{(j)}) w i ( j + 1 ) = w i ( j ) exp ( − η L i ( j ) ) . The second point of the proof of Theorem 5 then follows from a simple modification to the standard Hedge analysis.
Lemma 5 (Hoeffding’s Lemma). Let X X X be a real-valued random variable supported on an interval [ a , b ] [a,b] [ a , b ] . Then for any η ∈ R \eta\in\mathbb{R} η ∈ R ,
ln E [ e − η X ] ≤ − η E [ X ] + η 2 ( b − a ) 2 8 . \ln\mathbb{E}\left[e^{-\eta X}\right] \leq-\eta\mathbb{E}[X] + \frac{\eta^2(b-a)^2}{8}. ln E [ e − η X ] ≤ − η E [ X ] + 8 η 2 ( b − a ) 2 .
Proof of Theorem 5 (Point 2). Let Z j : = ∑ i = 1 N w i ( j ) Z_j := \sum_{i=1}^{N} w_i^{(j)} Z j := ∑ i = 1 N w i ( j ) be the total weight of all N N N experts at block j j j , which makes p i ( j ) = w i ( j ) Z j p_i^{(j)} = \frac{w_i^{(j)}}{Z_j} p i ( j ) = Z j w i ( j ) . We conduct the proof by bounding ln Z B + 1 \ln Z_{B+1} ln Z B + 1 and recover the inequality in the regret formula. Recall that in the Hedge algorithm, the weight of each expert i i i is updated according to w i ( j + 1 ) = w i ( j ) ⋅ e − η L i ( j ) w_i^{(j+1)} = w_i^{(j)} \cdot e^{-\eta L_i^{(j)}} w i ( j + 1 ) = w i ( j ) ⋅ e − η L i ( j ) . It follows that w i ( B + 1 ) = exp ( − η ∑ j = 1 B L i ( j ) ) w_i^{(B+1)} = \exp\left(-\eta\sum_{j=1}^{B} L_i^{(j)}\right) w i ( B + 1 ) = exp ( − η ∑ j = 1 B L i ( j ) ) , which can be used to lower bound ln Z B \ln Z_B ln Z B as follows:
ln Z B + 1 = ln ( ∑ i = 1 N exp ( − η ∑ j = 1 B L i ( j ) ) ) ≥ max i ∈ [ N ] − η ∑ j = 1 B L i ( j ) = − η min i ∈ [ N ] ∑ j = 1 B L i ( j ) . \ln Z_{B+1} = \ln\left(\sum_{i=1}^{N} \exp\left(-\eta\sum_{j=1}^{B} L_i^{(j)}\right)\right) \geq\max_{i \in[N]} -\eta\sum_{j=1}^{B} L_i^{(j)} = -\eta\min_{i \in[N]} \sum_{j=1}^{B} L_i^{(j)}. ln Z B + 1 = ln ( i = 1 ∑ N exp ( − η j = 1 ∑ B L i ( j ) ) ) ≥ i ∈ [ N ] max − η j = 1 ∑ B L i ( j ) = − η i ∈ [ N ] min j = 1 ∑ B L i ( j ) .
For the lower bound, we first bound the ratio Z j + 1 Z j \frac{Z_{j+1}}{Z_j} Z j Z j + 1 using Lemma 5. As p i ( j ) = w i ( j ) Z j p_i^{(j)} = \frac{w_i^{(j)}}{Z_j} p i ( j ) = Z j w i ( j ) , we have
ln Z j + 1 Z j = ln ∑ i = 1 N ( w i ( j ) Z j ⋅ exp ( − η L i ( j ) ) ) = ln E i [ exp ( − η L i ( j ) ) ] . \ln\frac{Z_{j+1}}{Z_j} = \ln\sum_{i=1}^{N} \left(\frac{w_i^{(j)}}{Z_j} \cdot\exp\left(-\eta L_i^{(j)}\right)\right) = \ln\mathbb{E}_i\left[\exp\left(-\eta L_i^{(j)}\right)\right]. ln Z j Z j + 1 = ln i = 1 ∑ N ( Z j w i ( j ) ⋅ exp ( − η L i ( j ) ) ) = ln E i [ exp ( − η L i ( j ) ) ] .
Applying Lemma 5 to L i ( j ) = ∑ k = t j − 1 + 1 t j l i ( k ) ∈ [ 0 , b j ] L_i^{(j)} = \sum_{k=t_{j-1}+1}^{t_j} l_i^{(k)} \in[0,b_j] L i ( j ) = ∑ k = t j − 1 + 1 t j l i ( k ) ∈ [ 0 , b j ] and summing over all batches gives
∑ j = 1 B ln Z j + 1 Z j ≤ ∑ j = 1 B ( − η ⋅ E [ L ( j ) ] + η 2 b j 2 8 ) = − η ∑ j = 1 B E [ L ( j ) ] + η 2 8 ∑ j = 1 B b j 2 . \sum_{j=1}^{B} \ln\frac{Z_{j+1}}{Z_j} \leq\sum_{j=1}^{B} \left(-\eta\cdot\mathbb{E}\left[L^{(j)}\right] + \frac{\eta^2 b_j^2}{8}\right) = -\eta\sum_{j=1}^{B} \mathbb{E}\left[L^{(j)}\right] + \frac{\eta^2}{8} \sum_{j=1}^{B} b_j^2. j = 1 ∑ B ln Z j Z j + 1 ≤ j = 1 ∑ B ( − η ⋅ E [ L ( j ) ] + 8 η 2 b j 2 ) = − η j = 1 ∑ B E [ L ( j ) ] + 8 η 2 j = 1 ∑ B b j 2 .
Since the left-hand side above is equal to ln Z B + 1 − ln Z 1 = ln Z B + 1 − ln N \ln Z_{B+1} - \ln Z_1 = \ln Z_{B+1} - \ln N ln Z B + 1 − ln Z 1 = ln Z B + 1 − ln N by telescoping,
ln Z B + 1 ≤ ln N − η ∑ j = 1 B E [ L ( j ) ] + η 2 8 ∑ j = 1 B b j 2 . \ln Z_{B+1} \leq\ln N - \eta\sum_{j=1}^{B} \mathbb{E}\left[L^{(j)}\right] + \frac{\eta^2}{8} \sum_{j=1}^{B} b_j^2. ln Z B + 1 ≤ ln N − η j = 1 ∑ B E [ L ( j ) ] + 8 η 2 j = 1 ∑ B b j 2 .
Combining the above with the lower bound gives
− η min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( j ) ≤ ln N − η ∑ j = 1 B E [ L ( j ) ] + η 2 8 ∑ j = 1 B b j 2 , -\eta\min_{i^* \in[N]} \sum_{j=1}^{B} L_{i^*}^{(j)} \leq\ln N - \eta\sum_{j=1}^{B} \mathbb{E}\left[L^{(j)}\right] + \frac{\eta^2}{8} \sum_{j=1}^{B} b_j^2, − η i ∗ ∈ [ N ] min j = 1 ∑ B L i ∗ ( j ) ≤ ln N − η j = 1 ∑ B E [ L ( j ) ] + 8 η 2 j = 1 ∑ B b j 2 ,
which implies the regret bound
∑ j = 1 B E [ L ( j ) ] − min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( j ) ≤ ln N η + η 8 ∑ j = 1 B b j 2 . \sum_{j=1}^{B} \mathbb{E}\left[L^{(j)}\right] - \min_{i^* \in[N]} \sum_{j=1}^{B} L_{i^*}^{(j)} \leq\frac{\ln N}{\eta} + \frac{\eta}{8} \sum_{j=1}^{B} b_j^2. j = 1 ∑ B E [ L ( j ) ] − i ∗ ∈ [ N ] min j = 1 ∑ B L i ∗ ( j ) ≤ η ln N + 8 η j = 1 ∑ B b j 2 .
Setting η = 8 ln N ∑ j = 1 B b j 2 \eta= \sqrt{\frac{8 \ln N}{\sum_{j=1}^{B} b_j^2}} η = ∑ j = 1 B b j 2 8 l n N gives a regret bound of O ( ∥ b ∥ 2 log N ) O(\lVert b\rVert_2 \sqrt{\log N}) O (∥ b ∥ 2 log N ) . This completes the proof, since the regret is always trivially bounded by T T T .
Lower Bound
Towards proving the second point of Theorem 6, we first prove a lower bound for any arbitrary batch structure, and then construct a broad family of hard instances that gives a matching worst-case lower bound. Specifically, we first prove Lemma 6, which gives an Ω ( ∥ b ∥ 2 ) \Omega(\lVert b\rVert_2) Ω (∥ b ∥ 2 ) regret lower bound for the N = 2 N = 2 N = 2 case. Then, we prove the second point of Theorem 6 by bootstrapping from Lemma 6 via dividing the N N N -expert instance into ≈ log 2 N \approx\log_2 N ≈ log 2 N independent two-expert instances.
Lemma 6. For the adversarially batched expert problem with N = 2 N = 2 N = 2 experts and batch structure B = ( b 1 , b 2 , … , b B ) \mathcal{B} = (b_1, b_2, \ldots, b_B) B = ( b 1 , b 2 , … , b B ) , the minimax regret is at least Ω ( ∥ b ∥ 2 ) \Omega(\lVert b\rVert_2) Ω (∥ b ∥ 2 ) .
We prove Lemma 6 using a standard construction, in which the losses are from independent coin flips, and the Khintchine inequality (Lemma 7).
Lemma 7 (Khintchine inequality). Let { Z i } i = 1 N \{Z_i\}_{i=1}^{N} { Z i } i = 1 N be i.i.d. random variables with Pr [ Z i = + 1 ] = Pr [ Z i = − 1 ] = 1 / 2 \Pr[Z_i = +1] = \Pr[Z_i = -1] = 1/2 Pr [ Z i = + 1 ] = Pr [ Z i = − 1 ] = 1/2 for each i ∈ [ N ] i \in[N] i ∈ [ N ] . Let 0 < p < ∞ 0 < p < \infty 0 < p < ∞ and let x 1 , … , x i ∈ C x_1, \ldots, x_i \in\mathbb{C} x 1 , … , x i ∈ C . Then
A p ( ∑ i = 1 N ∣ x i ∣ 2 ) 1 2 ≤ ( E [ ∣ ∑ i = 1 N x i Z i ∣ p ] ) 1 p ≤ B p ( ∑ i = 1 N ∣ x i ∣ 2 ) 1 2 A_p \left(\sum_{i=1}^{N} |x_i|^2\right)^{\frac{1}{2}} \le\left(\mathbb{E}\left[\left|\sum_{i=1}^{N} x_i Z_i\right|^p\right]\right)^{\frac{1}{p}} \le B_p \left(\sum_{i=1}^{N} |x_i|^2\right)^{\frac{1}{2}} A p ( i = 1 ∑ N ∣ x i ∣ 2 ) 2 1 ≤ ( E [ i = 1 ∑ N x i Z i p ] ) p 1 ≤ B p ( i = 1 ∑ N ∣ x i ∣ 2 ) 2 1 for some constants A p , B p > 0 A_p, B_p > 0 A p , B p > 0 .
Proof of Lemma 6. Consider two experts who play opposite actions at random within each batch. Let X 1 , X 2 , … , X B X_1, X_2, \ldots, X_B X 1 , X 2 , … , X B be independent random variables that follow Bern ( 1 / 2 ) \operatorname{Bern}(1/2) Bern ( 1/2 ) . The losses are specified by L 1 ( j ) = b j ⋅ X j L_1^{(j)} = b_j \cdot X_j L 1 ( j ) = b j ⋅ X j and L 2 ( j ) = b j ⋅ ( 1 − X j ) L_2^{(j)} = b_j \cdot(1-X_j) L 2 ( j ) = b j ⋅ ( 1 − X j ) for each j ∈ [ B ] j \in[B] j ∈ [ B ] , and we write L ( j ) = ( L 1 ( j ) , L 2 ( j ) ) L^{(j)} = (L_1^{(j)}, L_2^{(j)}) L ( j ) = ( L 1 ( j ) , L 2 ( j ) ) as the (two-dimensional) loss vector. Over the randomness in the losses (i.e., in X X X ), the expectation of the regret is given by
E X [ ∑ j = 1 B ⟨ p ( j ) , L ( j ) ⟩ ] − E X [ min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( j ) ] . \mathbb{E}_{X}\left[\sum_{j=1}^{B} \langle p^{(j)}, L^{(j)}\rangle\right] - \mathbb{E}_{X}\left[\min_{i^* \in[N]} \sum_{j=1}^{B} L_{i^*}^{(j)}\right]. E X [ j = 1 ∑ B ⟨ p ( j ) , L ( j ) ⟩ ] − E X [ i ∗ ∈ [ N ] min j = 1 ∑ B L i ∗ ( j ) ] .
For the first term, note that p ( j ) p^{(j)} p ( j ) only depends on X 1 , X 2 , … , X j − 1 X_1, X_2, \ldots, X_{j-1} X 1 , X 2 , … , X j − 1 . Thus, X j X_j X j still follows Bern ( 1 / 2 ) \operatorname{Bern}(1/2) Bern ( 1/2 ) conditioned on p ( j ) p^{(j)} p ( j ) . It follows that E X [ ⟨ p ( j ) , L ( j ) ⟩ ] = b j / 2 \mathbb{E}_{X}[\langle p^{(j)}, L^{(j)}\rangle] = b_j/2 E X [⟨ p ( j ) , L ( j ) ⟩] = b j /2 . For the second term, we have
E X [ min i ∗ ∈ [ N ] ∑ j = 1 B L i ∗ ( j ) ] = E X [ min { ∑ j = 1 B b j ⋅ X j , ∑ j = 1 B b j ⋅ ( 1 − X j ) } ] . \mathbb{E}_{X}\left[\min_{i^* \in[N]} \sum_{j=1}^{B} L_{i^*}^{(j)}\right] = \mathbb{E}_{X}\left[\min\left\{\sum_{j=1}^{B} b_j \cdot X_j, \sum_{j=1}^{B} b_j \cdot(1-X_j)\right\}\right]. E X [ i ∗ ∈ [ N ] min j = 1 ∑ B L i ∗ ( j ) ] = E X [ min { j = 1 ∑ B b j ⋅ X j , j = 1 ∑ B b j ⋅ ( 1 − X j ) } ] .
Therefore, we can re-write the expected regret as
∑ j = 1 B b j 2 − E X [ min { ∑ j = 1 B b j ⋅ X j , ∑ j = 1 B b j ⋅ ( 1 − X j ) } ] = E X [ max { ∑ j = 1 B b j ⋅ ( 1 / 2 − X j ) , ∑ j = 1 B b j ⋅ ( X j − 1 / 2 ) } ] = E X [ ∣ ∑ j = 1 B b j ⋅ ( X j − 1 / 2 ) ∣ ] = 1 2 E Z [ ∣ ∑ j = 1 B b j Z j ∣ ] , \begin{aligned}
\sum_{j=1}^{B} \frac{b_j}{2} - \mathbb{E}_{X}\left[\min\left\{\sum_{j=1}^{B} b_j \cdot X_j, \sum_{j=1}^{B} b_j \cdot(1-X_j)\right\}\right] \\
&= \mathbb{E}_{X}\left[\max\left\{\sum_{j=1}^{B} b_j \cdot(1/2-X_j), \sum_{j=1}^{B} b_j \cdot(X_j-1/2)\right\}\right] \\
&= \mathbb{E}_{X}\left[\left|\sum_{j=1}^{B} b_j \cdot(X_j-1/2)\right|\right] = \frac{1}{2}\mathbb{E}_{Z}\left[\left|\sum_{j=1}^{B} b_j Z_j\right|\right],
\end{aligned} j = 1 ∑ B 2 b j − E X [ min { j = 1 ∑ B b j ⋅ X j , j = 1 ∑ B b j ⋅ ( 1 − X j ) } ] = E X [ max { j = 1 ∑ B b j ⋅ ( 1/2 − X j ) , j = 1 ∑ B b j ⋅ ( X j − 1/2 ) } ] = E X [ j = 1 ∑ B b j ⋅ ( X j − 1/2 ) ] = 2 1 E Z [ j = 1 ∑ B b j Z j ] ,
where Z 1 , Z 2 , … , Z B Z_1, Z_2, \ldots, Z_B Z 1 , Z 2 , … , Z B denote independent Rademacher random variables (i.e., Pr [ Z j = + 1 ] = Pr [ Z j = − 1 ] = 1 / 2 \Pr[Z_j = +1] = \Pr[Z_j = -1] = 1/2 Pr [ Z j = + 1 ] = Pr [ Z j = − 1 ] = 1/2 ) in the last step. Applying Lemma 7 with p = 1 p = 1 p = 1 gives a regret lower bound of A 1 2 ⋅ ∑ j = 1 B b j 2 = Ω ( ∥ b ∥ 2 ) \frac{A_1}{2} \cdot\sqrt{\sum_{j=1}^{B} b_j^2} = \Omega(\lVert b\rVert_2) 2 A 1 ⋅ ∑ j = 1 B b j 2 = Ω (∥ b ∥ 2 ) and completes the proof. □ \square □
Lemma 6 gives the lower bound of the adversarially batched expert problem under the N = 2 N = 2 N = 2 case. To handle the general-N N N case, the intuition is to partition the B B B blocks into ≈ log 2 N \approx\log_2 N ≈ log 2 N independent stages, such that the block sequence of each stage has a 2-norm of ≈ ∥ b ∥ 2 / log N \approx\lVert b\rVert_2/\sqrt{\log N} ≈ ∥ b ∥ 2 / log N . For each stage, we design only two different losses, so each stage can be viewed as an independent 2-expert problem. We then apply Lemma 6 to lower bound the regret within each stage, and argue that these regrets are additive. We start by proving the lemma below, which states that under the worst-case construction that satisfies max j ∈ [ B ] b j ≤ O ( ∥ b ∥ 2 / log N ) \max_{j\in[B]} b_j \le O(\lVert b\rVert_2/\sqrt{\log N}) max j ∈ [ B ] b j ≤ O (∥ b ∥ 2 / log N ) , we can partition the game into Ω ( log N ) \Omega(\log N) Ω ( log N ) stages. This, in turn, gives an Ω ( ∥ b ∥ 2 / log N ) \Omega(\lVert b\rVert_2/\log N) Ω (∥ b ∥ 2 / log N ) worst-case lower bound.
Lemma 8. Suppose that b 1 , b 2 , … , b B > 0 b_1,b_2,\ldots,b_B>0 b 1 , b 2 , … , b B > 0 and max j ∈ [ B ] b j ≤ c ⋅ ∥ b ∥ 2 log 2 N \max_{j\in[B]} b_j \le c\cdot\frac{\lVert b\rVert_2}{\sqrt{\log_2 N}} max j ∈ [ B ] b j ≤ c ⋅ l o g 2 N ∥ b ∥ 2 for some c > 0 c>0 c > 0 . Then, there exists S ≥ ⌊ log 2 N 1 + c 2 ⌋ S\ge\left\lfloor\frac{\log_2 N}{1+c^2}\right\rfloor S ≥ ⌊ 1 + c 2 l o g 2 N ⌋ and a partition { G 1 , G 2 , … , G S } \{G_1,G_2,\ldots,G_S\} { G 1 , G 2 , … , G S } of [ B ] [B] [ B ] such that, for each s ∈ [ S ] s\in[S] s ∈ [ S ] ,
∑ j ∈ G s b j 2 ≥ ∥ b ∥ 2 log 2 N . \sqrt{\sum_{j\in G_s}b_j^2}\ge\frac{\lVert b\rVert_2}{\sqrt{\log_2 N}}. j ∈ G s ∑ b j 2 ≥ log 2 N ∥ b ∥ 2 . Moreover, each partition G s G_s G s consists of contiguous integers, i.e., G s = { j 0 , j 0 + 1 , … , j 1 } G_s=\{j_0,j_0+1,\ldots,j_1\} G s = { j 0 , j 0 + 1 , … , j 1 } , for some integers j 0 ≤ j 1 j_0\le j_1 j 0 ≤ j 1 .
Proof. We construct the partition by greedily forming minimal segments, so that the sum of squared entries within each segment is ≥ M : = ∥ b ∥ 2 2 / ( log 2 N ) \ge M:=\lVert b\rVert_2^2/(\log_2 N) ≥ M := ∥ b ∥ 2 2 / ( log 2 N ) . Formally, we start with t 0 = 0 t_0=0 t 0 = 0 . For each s = 1 , 2 , … s=1,2,\ldots s = 1 , 2 , … , we define t s t_s t s to be the smallest index that satisfies
∑ j = t s − 1 + 1 t s b j 2 ≥ M . \sum_{j=t_{s-1}+1}^{t_s}b_j^2\ge M. j = t s − 1 + 1 ∑ t s b j 2 ≥ M .
If such an index exists, we must have ∑ j = t s − 1 + 1 t s − 1 b j 2 < M \sum_{j=t_{s-1}+1}^{t_s-1}b_j^2<M ∑ j = t s − 1 + 1 t s − 1 b j 2 < M . If no valid t s t_s t s exists, we set S = s − 1 S=s-1 S = s − 1 and reset t S t_S t S to B B B . The resulting partition is then given by G s = { t s − 1 + 1 , t s − 1 + 2 , … , t s } G_s=\{t_{s-1}+1,t_{s-1}+2,\ldots,t_s\} G s = { t s − 1 + 1 , t s − 1 + 2 , … , t s } for each s ∈ [ S ] s\in[S] s ∈ [ S ] . By construction, each s ∈ [ S ] s\in[S] s ∈ [ S ] satisfies the desired inequality
∑ j ∈ G s b j 2 ≥ M = ∥ b ∥ 2 log 2 N . \sqrt{\sum_{j\in G_s}b_j^2}\ge\sqrt{M}=\frac{\lVert b\rVert_2}{\sqrt{\log_2 N}}. j ∈ G s ∑ b j 2 ≥ M = log 2 N ∥ b ∥ 2 .
It remains to lower bound S S S , the number of segments. Note that for each s ∈ [ S − 1 ] s\in[S-1] s ∈ [ S − 1 ] , we have
∑ j ∈ G s b j 2 = ∑ j = t s − 1 + 1 t s − 1 b j 2 + b t s 2 ≤ M + ( c ⋅ ∥ b ∥ 2 log 2 N ) 2 = ( 1 + c 2 ) ⋅ ∥ b ∥ 2 2 log 2 N . \sum_{j\in G_s}b_j^2=\sum_{j=t_{s-1}+1}^{t_s-1}b_j^2+b_{t_s}^2\le M+\left(c\cdot\frac{\lVert b\rVert_2}{\sqrt{\log_2 N}}\right)^2=(1+c^2)\cdot\frac{\lVert b\rVert_2^2}{\log_2 N}. j ∈ G s ∑ b j 2 = j = t s − 1 + 1 ∑ t s − 1 b j 2 + b t s 2 ≤ M + ( c ⋅ log 2 N ∥ b ∥ 2 ) 2 = ( 1 + c 2 ) ⋅ log 2 N ∥ b ∥ 2 2 .
Furthermore, we must have ∑ j ∈ G S b j 2 < 2 ⋅ ( 1 + c 2 ) ⋅ ∥ b ∥ 2 2 log 2 N \sum_{j\in G_S}b_j^2<2\cdot(1+c^2)\cdot\frac{\lVert b\rVert_2^2}{\log_2 N} ∑ j ∈ G S b j 2 < 2 ⋅ ( 1 + c 2 ) ⋅ l o g 2 N ∥ b ∥ 2 2 ; otherwise, we should have formed at least two segments from blocks t S − 1 + 1 t_{S-1}+1 t S − 1 + 1 through B B B . Therefore, we have
∥ b ∥ 2 2 = ∑ s = 1 S ∑ j ∈ G s b j 2 < ( S + 1 ) ⋅ ( 1 + c 2 ) ⋅ ∥ b ∥ 2 2 log 2 N . \lVert b\rVert_2^2=\sum_{s=1}^{S}\sum_{j\in G_s}b_j^2<(S+1)\cdot(1+c^2)\cdot\frac{\lVert b\rVert_2^2}{\log_2 N}. ∥ b ∥ 2 2 = s = 1 ∑ S j ∈ G s ∑ b j 2 < ( S + 1 ) ⋅ ( 1 + c 2 ) ⋅ log 2 N ∥ b ∥ 2 2 .
This gives S > log 2 N 1 + c 2 − 1 S>\frac{\log_2 N}{1+c^2}-1 S > 1 + c 2 l o g 2 N − 1 and thus S ≥ ⌊ log 2 N 1 + c 2 ⌋ S\ge\left\lfloor\frac{\log_2 N}{1+c^2}\right\rfloor S ≥ ⌊ 1 + c 2 l o g 2 N ⌋ .
Now we are ready to prove the second point of Theorem 6.
Proof of Theorem 6 (Point 2). We apply Lemma 8 to partition the block representation B = ( b 1 , … , b B ) \mathcal{B} = (b_1,\ldots,b_B) B = ( b 1 , … , b B ) of the family of hard instances that satisfies max j ∈ [ B ] b j ≤ O ( ∥ b ∥ 2 / log N ) \max_{j\in[B]} b_j \le O(\lVert b\rVert_2/\sqrt{\log N}) max j ∈ [ B ] b j ≤ O (∥ b ∥ 2 / log N ) into S ≥ Ω ( log N ) S \ge\Omega(\log N) S ≥ Ω ( log N ) contiguous stages G 1 , G 2 , … , G S G_1,G_2,\ldots,G_S G 1 , G 2 , … , G S . Each G s = { t s − 1 + 1 , t s − 1 + 2 , … , t s } G_s = \{t_{s-1}+1,t_{s-1}+2,\ldots,t_s\} G s = { t s − 1 + 1 , t s − 1 + 2 , … , t s } denotes the indices of the blocks within stage s s s , and the number of time steps in stage s s s is T s = ∑ j ∈ G s b j T_s = \sum_{j\in G_s} b_j T s = ∑ j ∈ G s b j .
For each stage s ∈ [ S ] s \in[S] s ∈ [ S ] , we independently apply Lemma 6 to construct two random loss sequences
( ℓ 0 ( t s − 1 + 1 ) , ℓ 0 ( t s − 1 + 2 ) , … , ℓ 0 ( t s ) ) and ( ℓ 1 ( t s − 1 + 1 ) , ℓ 1 ( t s − 1 + 2 ) , … , ℓ 1 ( t s ) ) , \left(\ell_0^{(t_{s-1}+1)},\ell_0^{(t_{s-1}+2)},\ldots,\ell_0^{(t_s)}\right) \quad\text{and}\quad\left(\ell_1^{(t_{s-1}+1)},\ell_1^{(t_{s-1}+2)},\ldots,\ell_1^{(t_s)}\right), ( ℓ 0 ( t s − 1 + 1 ) , ℓ 0 ( t s − 1 + 2 ) , … , ℓ 0 ( t s ) ) and ( ℓ 1 ( t s − 1 + 1 ) , ℓ 1 ( t s − 1 + 2 ) , … , ℓ 1 ( t s ) ) ,
where ℓ i ( j ) \ell_i^{(j)} ℓ i ( j ) denotes the total loss of expert i ∈ { 0 , 1 } i \in\{0,1\} i ∈ { 0 , 1 } within batch j ∈ G s j \in G_s j ∈ G s .
Without loss of generality, we assume that there are exactly N = 2 S N = 2^S N = 2 S experts. For clarity, we label the experts using length-S S S binary strings in { 0 , 1 } S \{0,1\}^S { 0 , 1 } S , i.e., each expert is labeled with S S S bits i 1 , i 2 , … , i S i_1,i_2,\ldots,i_S i 1 , i 2 , … , i S . Then, the losses in the original instance are defined as
L i 1 , i 2 , … , i S ( j ) : = ℓ i s ( j ) , L_{i_1,i_2,\ldots,i_S}^{(j)} := \ell_{i_s}^{(j)}, L i 1 , i 2 , … , i S ( j ) := ℓ i s ( j ) ,
where s ∈ [ S ] s \in[S] s ∈ [ S ] is the unique index such that j ∈ G s j \in G_s j ∈ G s . In other words, the expert labeled i = ( i 1 , i 2 , … , i S ) i = (i_1,i_2,\ldots,i_S) i = ( i 1 , i 2 , … , i S ) incurs the same loss as “expert i s i_s i s ” does within stage s s s .
Now, suppose that the learner incurs a loss of L ^ ( j ) \widehat{L}^{(j)} L ( j ) within each block j ∈ [ B ] j \in[B] j ∈ [ B ] . Then, the regret of the learner is given by
∑ j = 1 B L ^ ( j ) − min i ∈ { 0 , 1 } S ∑ j = 1 B L i ( j ) = ∑ s = 1 S ∑ j ∈ G s L ^ ( j ) − ∑ s = 1 S min i s ∈ { 0 , 1 } ∑ j ∈ G s ℓ i s ( j ) = ∑ s = 1 S [ ∑ j ∈ G s L ^ ( j ) − min i s ∈ { 0 , 1 } ∑ j ∈ G s ℓ i s ( j ) ] . \begin{aligned}
\sum_{j=1}^{B} \widehat{L}^{(j)}-\min_{i\in\{0,1\}^{S}}\sum_{j=1}^{B}L_i^{(j)}
=\sum_{s=1}^{S}\sum_{j\in G_s}\widehat{L}^{(j)}-\sum_{s=1}^{S}\min_{i_s\in\{0,1\}}\sum_{j\in G_s}\ell_{i_s}^{(j)} \\
&=\sum_{s=1}^{S}\left[\sum_{j\in G_s}\widehat{L}^{(j)}-\min_{i_s\in\{0,1\}}\sum_{j\in G_s}\ell_{i_s}^{(j)}\right].
\end{aligned} j = 1 ∑ B L ( j ) − i ∈ { 0 , 1 } S min j = 1 ∑ B L i ( j ) = s = 1 ∑ S j ∈ G s ∑ L ( j ) − s = 1 ∑ S i s ∈ { 0 , 1 } min j ∈ G s ∑ ℓ i s ( j ) = s = 1 ∑ S j ∈ G s ∑ L ( j ) − i s ∈ { 0 , 1 } min j ∈ G s ∑ ℓ i s ( j ) .
Note that ∑ j ∈ G s L ^ ( j ) − min i s ∈ { 0 , 1 } ∑ j ∈ G s ℓ i s ( j ) \sum_{j\in G_s}\widehat{L}^{(j)}-\min_{i_s\in\{0,1\}}\sum_{j\in G_s}\ell_{i_s}^{(j)} ∑ j ∈ G s L ( j ) − min i s ∈ { 0 , 1 } ∑ j ∈ G s ℓ i s ( j ) is exactly the learner’s regret within stage s s s . Since we constructed the losses using Lemma 6, the regret within each stage s s s is at least Ω ( ∑ j ∈ G s b j 2 ) \Omega\left(\sqrt{\sum_{j\in G_s} b_j^2}\right) Ω ( ∑ j ∈ G s b j 2 ) , which is in turn lower bounded by Ω ( ∥ b ∥ 2 log N ) \Omega\left(\frac{\lVert b\rVert_2}{\sqrt{\log N}}\right) Ω ( l o g N ∥ b ∥ 2 ) by our construction of the partition from Lemma 8 . Finally, since Lemma 8 guarantees S ≥ Ω ( log N ) S \ge\Omega(\log N) S ≥ Ω ( log N ) , the regret is lower bounded by Ω ( ∥ b ∥ 2 log N ) \Omega(\lVert b\rVert_2\sqrt{\log N}) Ω (∥ b ∥ 2 log N ) , which marks the end of the proof.
Adversarial Bandits
Recall that in the adversarial bandits setting, the player only observes the loss of the chosen arm l i t ( t ) l_{i_t}^{(t)} l i t ( t ) at each round t ∈ [ T ] t \in[T] t ∈ [ T ] . The EXP3 algorithm of Auer, Cesa-Bianchi, Freund, and Schapire [2 ] uses l ~ ( t ) = ( 0 , … , l i t ( t ) p i t ( t ) , … , 0 ) \widetilde{l}^{(t)} = \left(0,\ldots,\frac{l_{i_t}^{(t)}}{p_{i_t}^{(t)}},\ldots,0\right) l ( t ) = ( 0 , … , p i t ( t ) l i t ( t ) , … , 0 ) as an estimator for the actual loss vector l ( t ) l^{(t)} l ( t ) . This estimator is unbiased since, for each coordinate i ∈ [ N ] i \in[N] i ∈ [ N ] ,
E i t ∼ p ( t ) [ l ~ i ( t ) ] = Pr i t ∼ p ( t ) [ i t = i ] ⋅ l i t ( t ) p i t ( t ) + Pr i t ∼ p ( t ) [ i t ≠ i ] ⋅ 0 = l i ( t ) . \mathbb{E}_{i_t\sim p^{(t)}}\left[\widetilde{l}_i^{(t)}\right]
=\Pr_{i_t\sim p^{(t)}}[i_t=i]\cdot\frac{l_{i_t}^{(t)}}{p_{i_t}^{(t)}}+\Pr_{i_t\sim p^{(t)}}[i_t\ne i]\cdot0=l_i^{(t)}. E i t ∼ p ( t ) [ l i ( t ) ] = i t ∼ p ( t ) Pr [ i t = i ] ⋅ p i t ( t ) l i t ( t ) + i t ∼ p ( t ) Pr [ i t = i ] ⋅ 0 = l i ( t ) .
In the adversarially batched setting, we update the weights according to
w i ( j + 1 ) = w i ( j ) exp ( − η L ~ i ( j ) ) , w_i^{(j+1)}=w_i^{(j)}\exp\left(-\eta\widetilde{L}_i^{(j)}\right), w i ( j + 1 ) = w i ( j ) exp ( − η L i ( j ) ) ,
where L ~ i ( j ) = ∑ t = t j − 1 + 1 t j l i ( t ) \widetilde{L}^{(j)}_i=\sum_{t=t_{j-1}+1}^{t_j}l_i^{(t)} L i ( j ) = ∑ t = t j − 1 + 1 t j l i ( t ) . The weights then determine the probability of pulling each arm via p i ( j + 1 ) = w i ( j + 1 ) ∑ n ∈ [ N ] w n ( j + 1 ) p_i^{(j+1)}=\frac{w_i^{(j+1)}}{\sum_{n\in[N]}w_n^{(j+1)}} p i ( j + 1 ) = ∑ n ∈ [ N ] w n ( j + 1 ) w i ( j + 1 ) . A detailed pseudo-code is provided in Algorithm 4.
Algorithm 4 EXP3 in the Adversarially Batched Bandits Setting
Initialize: w i ( 1 ) ← 1 ∀ i ∈ [ N ] w_i^{(1)}\leftarrow1\ \forall i\in[N] w i ( 1 ) ← 1 ∀ i ∈ [ N ] , p ( 1 ) ← w i ( 1 ) ∑ k = 1 N w k ( 1 ) ∀ i ∈ [ N ] p^{(1)}\leftarrow\frac{w_i^{(1)}}{\sum_{k=1}^{N}w_k^{(1)}}\ \forall i\in[N] p ( 1 ) ← ∑ k = 1 N w k ( 1 ) w i ( 1 ) ∀ i ∈ [ N ] , and j ← 1 j\leftarrow1 j ← 1
Sample arm i j ∼ p ( j ) i_j\sim p^{(j)} i j ∼ p ( j )
for t = 1 , … , T t=1,\ldots,T t = 1 , … , T do
p i ( j ) ← w i ( j ) ∑ k = 1 N w k ( j ) ∀ i ∈ [ N ] p_i^{(j)}\leftarrow\frac{w_i^{(j)}}{\sum_{k=1}^{N}w_k^{(j)}}\ \forall i\in[N] p i ( j ) ← ∑ k = 1 N w k ( j ) w i ( j ) ∀ i ∈ [ N ]
if bandit feedback for the current block is revealed to the player then
t j ← t t_j\leftarrow t t j ← t
Observe block loss of the played arm: L i j ( j ) L_{i_j}^{(j)} L i j ( j )
Form importance-weighted loss estimates: L ^ i ( j ) ← L i ( j ) p i ( j ) 1 { i = i j } \widehat{L}_i^{(j)}\leftarrow\frac{L_i^{(j)}}{p_{i}^{(j)}}\mathbf{1}\{i=i_j\} L i ( j ) ← p i ( j ) L i ( j ) 1 { i = i j }
Update weights: w i ( j + 1 ) ← w i ( j ) exp ( − η L ^ i ( j ) ) ∀ i ∈ [ N ] w_i^{(j+1)}\leftarrow w_i^{(j)}\exp\left(-\eta\widehat{L}_i^{(j)}\right)\quad\forall i\in[N] w i ( j + 1 ) ← w i ( j ) exp ( − η L i ( j ) ) ∀ i ∈ [ N ]
j ← j + 1 j\leftarrow j+1 j ← j + 1
Sample arm i j ∼ p ( j ) i_j\sim p^{(j)} i j ∼ p ( j )
end if
end for
Upper Bound
Proof of Theorem 5 (Point 3). Let Z j : = ∑ i = 1 N w i ( j ) Z_j:=\sum_{i=1}^{N}w_i^{(j)} Z j := ∑ i = 1 N w i ( j ) to be the total weight of all N N N experts at block j j j , and then bound ln Z B + 1 \ln Z_{B+1} ln Z B + 1 on both directions.
Fix an arm i ∗ ∈ [ N ] i^*\in[N] i ∗ ∈ [ N ] . To lower bound ln Z B + 1 \ln Z_{B+1} ln Z B + 1 , we note
ln Z B + 1 = ln ( ∑ i = 1 N exp ( − η ∑ j = 1 B L ~ i ( j ) ) ) ≥ − η ∑ j = 1 B L ~ i ∗ ( j ) . \ln Z_{B+1}=\ln\left(\sum_{i=1}^{N}\exp\left(-\eta\sum_{j=1}^{B}\widetilde{L}_i^{(j)}\right)\right)\geq-\eta\sum_{j=1}^{B}\widetilde{L}_{i^*}^{(j)}. ln Z B + 1 = ln ( i = 1 ∑ N exp ( − η j = 1 ∑ B L i ( j ) ) ) ≥ − η j = 1 ∑ B L i ∗ ( j ) .
For the upper bound, recall that p i ( j ) = w i ( j ) ∑ n = 1 N w n ( j ) p_i^{(j)}=\frac{w_i^{(j)}}{\sum_{n=1}^{N}w_n^{(j)}} p i ( j ) = ∑ n = 1 N w n ( j ) w i ( j ) . Then,
Z j + 1 Z j = ∑ i = 1 N w i ( j ) Z j exp ( − η L ~ i ( j ) ) = ∑ i = 1 N p i ( j ) exp ( − η L ~ i ( j ) ) . \frac{Z_{j+1}}{Z_j}=\sum_{i=1}^{N}\frac{w_i^{(j)}}{Z_j}\exp\left(-\eta\widetilde{L}_i^{(j)}\right)=\sum_{i=1}^{N}p_i^{(j)}\exp\left(-\eta\widetilde{L}_i^{(j)}\right). Z j Z j + 1 = i = 1 ∑ N Z j w i ( j ) exp ( − η L i ( j ) ) = i = 1 ∑ N p i ( j ) exp ( − η L i ( j ) ) .
Applying the inequality e − x ≤ 1 − x + x 2 2 e^{-x}\leq1-x+\frac{x^2}{2} e − x ≤ 1 − x + 2 x 2 for x ≥ 0 x\geq0 x ≥ 0 , we obtain
Z j + 1 Z j ≤ ∑ i = 1 N p i ( j ) [ 1 − η L ~ i ( j ) + η 2 2 ( L ~ i ( j ) ) 2 ] = 1 − η ∑ i = 1 N p i ( j ) L ~ i ( j ) + η 2 2 ∑ i = 1 N p i ( j ) ( L ~ i ( j ) ) 2 . \begin{aligned}
\frac{Z_{j+1}}{Z_j}\leq\sum_{i=1}^{N}p_i^{(j)}\left[1-\eta\widetilde{L}_i^{(j)}+\frac{\eta^2}{2}\left(\widetilde{L}_i^{(j)}\right)^2\right] \\
&=1-\eta\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}+\frac{\eta^2}{2}\sum_{i=1}^{N}p_i^{(j)}\left(\widetilde{L}_i^{(j)}\right)^2.
\end{aligned} Z j Z j + 1 ≤ i = 1 ∑ N p i ( j ) [ 1 − η L i ( j ) + 2 η 2 ( L i ( j ) ) 2 ] = 1 − η i = 1 ∑ N p i ( j ) L i ( j ) + 2 η 2 i = 1 ∑ N p i ( j ) ( L i ( j ) ) 2 .
Taking the logarithm and summing over all blocks leads to
ln Z B + 1 − ln Z 1 ≤ ∑ j = 1 B ln ( 1 − η ∑ i = 1 N p i ( j ) L ~ i ( j ) + η 2 2 ∑ i = 1 N p i ( j ) ( L ~ i ( j ) ) 2 ) . \ln Z_{B+1} - \ln Z_1 \le\sum_{j=1}^{B} \ln\left(1-\eta\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}+\frac{\eta^2}{2}\sum_{i=1}^{N}p_i^{(j)}\left(\widetilde{L}_i^{(j)}\right)^2\right). ln Z B + 1 − ln Z 1 ≤ j = 1 ∑ B ln ( 1 − η i = 1 ∑ N p i ( j ) L i ( j ) + 2 η 2 i = 1 ∑ N p i ( j ) ( L i ( j ) ) 2 ) .
Applying ln ( 1 + x ) ≤ x \ln(1+x)\le x ln ( 1 + x ) ≤ x and noting Z 1 = N Z_1=N Z 1 = N gives
ln Z B + 1 ≤ ln N − η ∑ j = 1 B ∑ i = 1 N p i ( j ) L ~ i ( j ) + η 2 2 ∑ j = 1 B ∑ i = 1 N p i ( j ) ( L ~ i ( j ) ) 2 . \ln Z_{B+1}\le\ln N-\eta\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}+\frac{\eta^2}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\left(\widetilde{L}_i^{(j)}\right)^2. ln Z B + 1 ≤ ln N − η j = 1 ∑ B i = 1 ∑ N p i ( j ) L i ( j ) + 2 η 2 j = 1 ∑ B i = 1 ∑ N p i ( j ) ( L i ( j ) ) 2 .
Combining the above with the lower bound ln Z B + 1 ≥ − η ⋅ ∑ j = 1 B L ~ i ∗ ( j ) \ln Z_{B+1}\ge-\eta\cdot\sum_{j=1}^{B}\widetilde{L}_{i^*}^{(j)} ln Z B + 1 ≥ − η ⋅ ∑ j = 1 B L i ∗ ( j ) gives
η ( ∑ j = 1 B ∑ i = 1 N p i ( j ) L ~ i ( j ) − ∑ j = 1 B L ~ i ∗ ( j ) ) ≤ ln N + η 2 2 ∑ j = 1 B ∑ i = 1 N p i ( j ) ( L ~ i ( j ) ) 2 . \eta\left(\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}-\sum_{j=1}^{B}\widetilde{L}_{i^*}^{(j)}\right)\le\ln N+\frac{\eta^2}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\left(\widetilde{L}_i^{(j)}\right)^2. η ( j = 1 ∑ B i = 1 ∑ N p i ( j ) L i ( j ) − j = 1 ∑ B L i ∗ ( j ) ) ≤ ln N + 2 η 2 j = 1 ∑ B i = 1 ∑ N p i ( j ) ( L i ( j ) ) 2 .
Equivalently,
∑ j = 1 B ∑ i = 1 N p i ( j ) L ~ i ( j ) − ∑ j = 1 B L ~ i ∗ ( j ) ≤ ln N η + η 2 ∑ j = 1 B ∑ i = 1 N p i ( j ) ( L ~ i ( j ) ) 2 . \sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}-\sum_{j=1}^{B}\widetilde{L}_{i^*}^{(j)}\le\frac{\ln N}{\eta}+\frac{\eta}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\left(\widetilde{L}_i^{(j)}\right)^2. j = 1 ∑ B i = 1 ∑ N p i ( j ) L i ( j ) − j = 1 ∑ B L i ∗ ( j ) ≤ η ln N + 2 η j = 1 ∑ B i = 1 ∑ N p i ( j ) ( L i ( j ) ) 2 .
Recall that p ( j ) p^{(j)} p ( j ) is itself a random variable and directly affects L ~ ( j ) \widetilde{L}^{(j)} L ( j ) . Given the definition of pseudo-regret, we check the expectation of ∑ j = 1 B ∑ i = 1 N p i ( j ) L ~ i ( j ) − ∑ j = 1 B L ~ i ∗ ( j ) \sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}-\sum_{j=1}^{B}\widetilde{L}_{i^*}^{(j)} ∑ j = 1 B ∑ i = 1 N p i ( j ) L i ( j ) − ∑ j = 1 B L i ∗ ( j ) . Specifically,
E p ( j ) [ ∑ j = 1 B ∑ i = 1 N p i ( j ) L ~ i ( j ) − ∑ j = 1 B L ~ i ∗ ( j ) ] = ∑ j = 1 B ∑ i = 1 N p i ( j ) E p ( j ) [ L ~ i ( j ) ] − ∑ j = 1 B E p ( j ) [ L ~ i ∗ ( j ) ] = ∑ j = 1 B ∑ i = 1 N p i ( j ) L i ( j ) − ∑ j = 1 B L i ∗ ( j ) . \begin{aligned}
\mathbb{E}_{p^{(j)}}\left[\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\widetilde{L}_i^{(j)}-\sum_{j=1}^{B}\widetilde{L}_{i^*}^{(j)}\right]=\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\mathbb{E}_{p^{(j)}}\left[\widetilde{L}_i^{(j)}\right]-\sum_{j=1}^{B}\mathbb{E}_{p^{(j)}}\left[\widetilde{L}_{i^*}^{(j)}\right] \\
&=\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}L_i^{(j)}-\sum_{j=1}^{B}L_{i^*}^{(j)}.
\end{aligned} E p ( j ) [ j = 1 ∑ B i = 1 ∑ N p i ( j ) L i ( j ) − j = 1 ∑ B L i ∗ ( j ) ] = j = 1 ∑ B i = 1 ∑ N p i ( j ) E p ( j ) [ L i ( j ) ] − j = 1 ∑ B E p ( j ) [ L i ∗ ( j ) ] = j = 1 ∑ B i = 1 ∑ N p i ( j ) L i ( j ) − j = 1 ∑ B L i ∗ ( j ) .
Taking the result back to the LHS of the inequality leads to
∑ j = 1 B ∑ i = 1 N p i ( j ) L i ( j ) − ∑ j = 1 B L i ∗ ( j ) ≤ E p ( j ) [ ln N η + η 2 ∑ j = 1 B ∑ i = 1 N p i ( j ) ( L ~ i ( j ) ) 2 ] = ln N η + η 2 ∑ j = 1 B ∑ i = 1 N p i ( j ) ⋅ E p ( j ) [ ( L ~ i ( j ) ) 2 ] = ln N η + η 2 ∑ j = 1 B ∑ i = 1 N p i ( j ) ⋅ p i ( j ) ⋅ ( L i ( j ) p i ( j ) ) 2 = ln N η + η 2 ∑ j = 1 B ∑ i = 1 N ( L i ( j ) ) 2 ≤ ln N η + η N 2 ∑ j = 1 B b j 2 ( L ~ i ( j ) ∈ [ 0 , b i ] ) \begin{aligned}
\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}L_i^{(j)}-\sum_{j=1}^{B}L_{i^*}^{(j)}
\le\mathbb{E}_{p^{(j)}}\left[\frac{\ln N}{\eta}+\frac{\eta}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\left(\widetilde{L}_i^{(j)}\right)^2\right] \\
&=\frac{\ln N}{\eta}+\frac{\eta}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\cdot\mathbb{E}_{p^{(j)}}\left[\left(\widetilde{L}_i^{(j)}\right)^2\right] \\
&=\frac{\ln N}{\eta}+\frac{\eta}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}p_i^{(j)}\cdot p_i^{(j)}\cdot\left(\frac{L_i^{(j)}}{p_i^{(j)}}\right)^2 \\
&=\frac{\ln N}{\eta}+\frac{\eta}{2}\sum_{j=1}^{B}\sum_{i=1}^{N}\left(L_i^{(j)}\right)^2 \\
&\le\frac{\ln N}{\eta}+\frac{\eta N}{2}\sum_{j=1}^{B}b_j^2
\qquad\left(\widetilde{L}_i^{(j)}\in[0,b_i]\right)
\end{aligned} j = 1 ∑ B i = 1 ∑ N p i ( j ) L i ( j ) − j = 1 ∑ B L i ∗ ( j ) ≤ E p ( j ) [ η ln N + 2 η j = 1 ∑ B i = 1 ∑ N p i ( j ) ( L i ( j ) ) 2 ] = η ln N + 2 η j = 1 ∑ B i = 1 ∑ N p i ( j ) ⋅ E p ( j ) [ ( L i ( j ) ) 2 ] = η ln N + 2 η j = 1 ∑ B i = 1 ∑ N p i ( j ) ⋅ p i ( j ) ⋅ ( p i ( j ) L i ( j ) ) 2 = η ln N + 2 η j = 1 ∑ B i = 1 ∑ N ( L i ( j ) ) 2 ≤ η ln N + 2 η N j = 1 ∑ B b j 2 ( L i ( j ) ∈ [ 0 , b i ] )
Setting η = 2 ln N ∥ b ∥ 2 N \eta=\frac{\sqrt{2\ln N}}{\lVert b\rVert_2\sqrt{N}} η = ∥ b ∥ 2 N 2 l n N bounds the pseudo-regret by ∥ b ∥ 2 ⋅ 2 N ln N = O ( ∥ b ∥ 2 ⋅ N log N ) \lVert b\rVert_2\cdot\sqrt{2N\ln N}=\mathcal{O}(\lVert b\rVert_2\cdot\sqrt{N\log N}) ∥ b ∥ 2 ⋅ 2 N ln N = O (∥ b ∥ 2 ⋅ N log N ) . □
Lower Bound
Similar to the second point of the proof of Theorem 6, we first prove a lower bound for any arbitrary batch structure B \mathcal{B} B , then construct a family of hard instances that gives a tight worst-case lower bound.
Proof of Theorem 6 (Point 3). Recall the notation that b max = max j ∈ [ B ] b j b_{\max} = \max_{j \in[B]} b_j b m a x = max j ∈ [ B ] b j .
Let K = min { N , max { 2 , ∥ b ∥ 2 2 b max 2 } } K = \min\left\{N, \max\left\{2, \frac{\lVert b\rVert_2^2}{b_{\max}^2}\right\}\right\} K = min { N , max { 2 , b m a x 2 ∥ b ∥ 2 2 } } . As ∥ b ∥ 2 2 ≥ b max 2 \lVert b\rVert_2^2 \ge b_{\max}^2 ∥ b ∥ 2 2 ≥ b m a x 2 and N ≥ 2 N \ge2 N ≥ 2 , we have
K ≥ 2 ; K ≤ 2 ∥ b ∥ 2 2 / b max 2 . K \ge2;\quad K \le2\lVert b\rVert_2^2/b_{\max}^2. K ≥ 2 ; K ≤ 2 ∥ b ∥ 2 2 / b m a x 2 .
We construct K K K hard environments, indexed by θ ∈ [ K ] \theta\in[K] θ ∈ [ K ] . Fixing a sufficiently small absolute constant γ = 1 / 16 \gamma= 1/16 γ = 1/16 , we define δ j = γ K b j ∥ b ∥ 2 \delta_j = \gamma\frac{\sqrt{K}b_j}{\lVert b\rVert_2} δ j = γ ∥ b ∥ 2 K b j for j ∈ [ B ] j \in[B] j ∈ [ B ] . It is easy to see that
δ j ≤ γ K b max ∥ b ∥ 2 ≤ γ 2 < 1 4 . \delta_j \le\gamma\frac{\sqrt{K}b_{\max}}{\lVert b\rVert_2} \le\gamma\sqrt{2} < \frac{1}{4}. δ j ≤ γ ∥ b ∥ 2 K b m a x ≤ γ 2 < 4 1 .
For every θ ∈ [ K ] \theta\in[K] θ ∈ [ K ] , we define an oblivious randomized environment P θ P_\theta P θ as follows. For every batch j ∈ [ B ] j \in[B] j ∈ [ B ] and arm i ∈ [ N ] i \in[N] i ∈ [ N ] , independently sample
X j , i ∼ { Bernoulli ( 1 2 − δ j ) , i = θ , Bernoulli ( 1 2 ) , i ≠ θ . X_{j,i} \sim
\begin{cases}
\operatorname{Bernoulli}\left(\frac{1}{2}-\delta_j\right), & i=\theta,\\
\operatorname{Bernoulli}\left(\frac{1}{2}\right), & i\ne\theta.
\end{cases} X j , i ∼ { Bernoulli ( 2 1 − δ j ) , Bernoulli ( 2 1 ) , i = θ , i = θ .
Within batch j j j , set the loss of arm i i i to be constant across all b j b_j b j rounds, i.e., l i ( t ) = X j , i l_i^{(t)} = X_{j,i} l i ( t ) = X j , i , t = t j − 1 + 1 , … , t j t = t_{j-1}+1,\ldots,t_j t = t j − 1 + 1 , … , t j . Thus the cumulative loss of arm i i i in batch j j j is L i ( j ) = b j X j , i L_i^{(j)} = b_jX_{j,i} L i ( j ) = b j X j , i . Since the environment is oblivious and the random variables associated with batch j j j are independent of the history before batch j j j , under P θ P_\theta P θ we have
E θ [ L i j ( j ) ] = Pr θ [ i j = θ ] b j ( 1 2 − δ j ) + Pr θ [ i j ≠ θ ] b j 2 = b j 2 − b j δ j Pr θ [ i j = θ ] , \mathbb{E}_\theta\left[L_{i_j}^{(j)}\right] = \Pr_\theta[i_j=\theta]b_j\left(\frac{1}{2}-\delta_j\right) + \Pr_\theta[i_j\ne\theta]\frac{b_j}{2} = \frac{b_j}{2} - b_j\delta_j\Pr_\theta[i_j=\theta], E θ [ L i j ( j ) ] = θ Pr [ i j = θ ] b j ( 2 1 − δ j ) + θ Pr [ i j = θ ] 2 b j = 2 b j − b j δ j θ Pr [ i j = θ ] ,
where, recall that i j i_j i j is the arm selected by the learner in batch j j j . On the other hand,
E θ [ L θ ( j ) ] = b j ( 1 2 − δ j ) , \mathbb{E}_\theta\left[L_\theta^{(j)}\right] = b_j\left(\frac{1}{2}-\delta_j\right), E θ [ L θ ( j ) ] = b j ( 2 1 − δ j ) ,
while every arm i ≠ θ i \ne\theta i = θ has expected loss b j / 2 b_j/2 b j /2 . Therefore, the pseudo-regret under P θ P_\theta P θ is
Reg θ = ∑ j = 1 B ( b j 2 − b j δ j Pr θ [ i j = θ ] ) − ∑ j = 1 B b j ( 1 2 − δ j ) = ∑ j = 1 B b j δ j ( 1 − Pr θ [ i j = θ ] ) = ∑ j = 1 B b j δ j − ∑ j = 1 B b j δ j Pr θ [ i j = θ ] . \begin{aligned}
\operatorname{Reg}_\theta= \sum_{j=1}^{B}\left(\frac{b_j}{2} - b_j\delta_j\Pr_\theta[i_j=\theta]\right) - \sum_{j=1}^{B}b_j\left(\frac{1}{2}-\delta_j\right) \\
&= \sum_{j=1}^{B}b_j\delta_j\left(1-\Pr_\theta[i_j=\theta]\right) \\
&= \sum_{j=1}^{B}b_j\delta_j - \sum_{j=1}^{B}b_j\delta_j\Pr_\theta[i_j=\theta].
\end{aligned} Reg θ = j = 1 ∑ B ( 2 b j − b j δ j θ Pr [ i j = θ ] ) − j = 1 ∑ B b j ( 2 1 − δ j ) = j = 1 ∑ B b j δ j ( 1 − θ Pr [ i j = θ ] ) = j = 1 ∑ B b j δ j − j = 1 ∑ B b j δ j θ Pr [ i j = θ ] .
For the first term, we have
∑ j = 1 B b j δ j = γ K ∥ b ∥ 2 ∑ j = 1 B b j 2 = γ K ∥ b ∥ 2 . \sum_{j=1}^{B}b_j\delta_j = \frac{\gamma\sqrt{K}}{\lVert b\rVert_2}\sum_{j=1}^{B}b_j^2 = \gamma\sqrt{K}\lVert b\rVert_2. j = 1 ∑ B b j δ j = ∥ b ∥ 2 γ K j = 1 ∑ B b j 2 = γ K ∥ b ∥ 2 .
Now we show that, for at least one θ ∈ [ K ] \theta\in[K] θ ∈ [ K ] , the learner selects arm θ \theta θ incorrectly on a constant fraction of this weighted mass. Define the null environment P 0 P_0 P 0 , under which X j , i ∼ Bern ( 1 / 2 ) X_{j,i} \sim\operatorname{Bern}(1/2) X j , i ∼ Bern ( 1/2 ) independently for every j ∈ [ B ] j \in[B] j ∈ [ B ] and i ∈ [ N ] i \in[N] i ∈ [ N ] . We compare P 0 P_0 P 0 and P θ P_\theta P θ . Since the learner uses the same decision rule under P 0 P_0 P 0 and P θ P_\theta P θ , the only difference between the two transcript distributions occurs in batches in which arm θ \theta θ is selected. By the chain rule for KL divergence,
D K L ( P 0 ∥ P θ ) = ∑ j = 1 B Pr 0 [ i j = θ ] kl ( 1 / 2 ∥ 1 / 2 − δ j ) . D_{\mathrm{KL}}(P_0\|P_\theta)=\sum_{j=1}^{B}\Pr_0[i_j=\theta]\operatorname{kl}(1/2\|1/2-\delta_j). D KL ( P 0 ∥ P θ ) = j = 1 ∑ B 0 Pr [ i j = θ ] kl ( 1/2∥1/2 − δ j ) .
where kl ( p ∥ q ) \operatorname{kl}(p\|q) kl ( p ∥ q ) denotes the binary relative entropy. For 0 ≤ δ j ≤ 1 / 4 0\leq\delta_j\leq1/4 0 ≤ δ j ≤ 1/4 ,
kl ( 1 / 2 ∥ 1 / 2 − δ ) = − 1 2 log ( 1 − 4 δ 2 ) ≤ 8 3 δ j 2 . \operatorname{kl}(1/2\|1/2-\delta)=-\frac{1}{2}\log(1-4\delta^2)\leq\frac{8}{3}\delta_j^2. kl ( 1/2∥1/2 − δ ) = − 2 1 log ( 1 − 4 δ 2 ) ≤ 3 8 δ j 2 .
Hence, D K L ( P 0 ∥ P θ ) ≤ 8 3 ∑ j = 1 B Pr 0 [ i j = θ ] δ j 2 D_{\mathrm{KL}}(P_0\|P_\theta)\leq\frac{8}{3}\sum_{j=1}^{B}\Pr_0[i_j=\theta]\delta_j^2 D KL ( P 0 ∥ P θ ) ≤ 3 8 ∑ j = 1 B Pr 0 [ i j = θ ] δ j 2 . By Pinsker’s inequality, for every j ∈ [ B ] j\in[B] j ∈ [ B ] ,
Pr θ [ i j = θ ] ≤ Pr 0 [ i j = θ ] + 1 2 D K L ( P 0 ∥ P θ ) . \Pr_\theta[i_j=\theta]\leq\Pr_0[i_j=\theta]+\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P_0\|P_\theta)}. θ Pr [ i j = θ ] ≤ 0 Pr [ i j = θ ] + 2 1 D KL ( P 0 ∥ P θ ) .
Taking this back, we have
Reg ‾ θ ≥ γ K ∥ b ∥ 2 − ∑ j = 1 B b j δ j Pr 0 [ i j = θ ] − γ K ∥ b ∥ 2 1 2 D K L ( P 0 ∥ P θ ) . \overline{\operatorname{Reg}}_\theta\geq\gamma\sqrt{K}\|b\|_2-\sum_{j=1}^{B}b_j\delta_j\Pr_0[i_j=\theta]-\gamma\sqrt{K}\|b\|_2\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P_0\|P_\theta)}. Reg θ ≥ γ K ∥ b ∥ 2 − j = 1 ∑ B b j δ j 0 Pr [ i j = θ ] − γ K ∥ b ∥ 2 2 1 D KL ( P 0 ∥ P θ ) .
Now we average the above inequality over θ ∈ [ K ] \theta\in[K] θ ∈ [ K ] . As the learner selects at most one arm in each batch, ∑ θ = 1 K Pr 0 [ i j = θ ] ≤ 1 \sum_{\theta=1}^{K}\Pr_0[i_j=\theta]\leq1 ∑ θ = 1 K Pr 0 [ i j = θ ] ≤ 1 , thus
1 K ∑ θ = 1 K ∑ j = 1 B b j δ j Pr 0 [ i j = θ ] ≤ ∑ j = 1 B b j δ j K = γ K ∥ b ∥ 2 K . \frac{1}{K}\sum_{\theta=1}^{K}\sum_{j=1}^{B}b_j\delta_j\Pr_0[i_j=\theta]\leq\frac{\sum_{j=1}^{B}b_j\delta_j}{K}=\frac{\gamma\sqrt{K}\|b\|_2}{K}. K 1 θ = 1 ∑ K j = 1 ∑ B b j δ j 0 Pr [ i j = θ ] ≤ K ∑ j = 1 B b j δ j = K γ K ∥ b ∥ 2 .
For the last term, the Cauchy-Schwarz inequality gives
1 K ∑ θ = 1 K 1 2 D K L ( P 0 ∥ P θ ) ≤ 1 K ∑ θ = 1 K 1 2 D K L ( P 0 ∥ P θ ) ≤ 1 K ∑ θ = 1 K 1 2 ∑ j = 1 B Pr 0 [ i j = θ ] 8 3 δ j 2 = 4 3 K ∑ j = 1 B δ j 2 ∑ θ = 1 K Pr 0 [ i j = θ ] ≤ 4 3 K ∑ j = 1 B δ j 2 . \begin{aligned}
\frac{1}{K}\sum_{\theta=1}^{K}\sqrt{\frac{1}{2}D_{\mathrm{KL}}(P_0\|P_\theta)}
\leq\sqrt{\frac{1}{K}\sum_{\theta=1}^{K}\frac{1}{2}D_{\mathrm{KL}}(P_0\|P_\theta)} \\
&\leq\sqrt{\frac{1}{K}\sum_{\theta=1}^{K}\frac{1}{2}\sum_{j=1}^{B}\Pr_0[i_j=\theta]\frac{8}{3}\delta_j^2} \\
&=\sqrt{\frac{4}{3K}\sum_{j=1}^{B}\delta_j^2\sum_{\theta=1}^{K}\Pr_0[i_j=\theta]} \\
&\leq\sqrt{\frac{4}{3K}\sum_{j=1}^{B}\delta_j^2}.
\end{aligned} K 1 θ = 1 ∑ K 2 1 D KL ( P 0 ∥ P θ ) ≤ K 1 θ = 1 ∑ K 2 1 D KL ( P 0 ∥ P θ ) ≤ K 1 θ = 1 ∑ K 2 1 j = 1 ∑ B 0 Pr [ i j = θ ] 3 8 δ j 2 = 3 K 4 j = 1 ∑ B δ j 2 θ = 1 ∑ K 0 Pr [ i j = θ ] ≤ 3 K 4 j = 1 ∑ B δ j 2 .
Substituting δ j \delta_j δ j , we have
4 3 K ∑ j = 1 B δ j 2 = 4 3 K γ 2 K ∑ j = 1 B b j 2 ∥ b ∥ 2 2 = 2 γ 3 . \sqrt{\frac{4}{3K}\sum_{j=1}^{B}\delta_j^2}
=\sqrt{\frac{4}{3K}\gamma^2K\frac{\sum_{j=1}^{B}b_j^2}{\|b\|_2^2}}
=\frac{2\gamma}{\sqrt{3}}. 3 K 4 j = 1 ∑ B δ j 2 = 3 K 4 γ 2 K ∥ b ∥ 2 2 ∑ j = 1 B b j 2 = 3 2 γ .
Combining together,
1 K ∑ θ = 1 K Reg ‾ θ ≥ 1 K ∑ θ = 1 K γ K ∥ b ∥ 2 − γ K ∥ b ∥ 2 K − γ K ∥ b ∥ 2 2 γ 3 = γ K ∥ b ∥ 2 ( 1 − 1 K − 2 γ 3 ) . \begin{aligned}
\frac{1}{K}\sum_{\theta=1}^{K}\overline{\operatorname{Reg}}_{\theta} \ge\frac{1}{K}\sum_{\theta=1}^{K}\gamma\sqrt{K}\lVert b\rVert_{2}-\frac{\gamma\sqrt{K}\lVert b\rVert_{2}}{K}-\gamma\sqrt{K}\lVert b\rVert_{2}\frac{2\gamma}{3} \\
&= \gamma\sqrt{K}\lVert b\rVert_{2}\left(1-\frac{1}{K}-\frac{2\gamma}{\sqrt{3}}\right).
\end{aligned} K 1 θ = 1 ∑ K Reg θ ≥ K 1 θ = 1 ∑ K γ K ∥ b ∥ 2 − K γ K ∥ b ∥ 2 − γ K ∥ b ∥ 2 3 2 γ = γ K ∥ b ∥ 2 ( 1 − K 1 − 3 2 γ ) .
As K ≥ 2 K \ge2 K ≥ 2 and γ = 1 / 16 \gamma= 1/16 γ = 1/16 , it is easy to see that 1 K ∑ θ = 1 K Reg ‾ θ = Ω ( K ∥ b ∥ 2 2 ) \frac{1}{K}\sum_{\theta=1}^{K}\overline{\operatorname{Reg}}_{\theta} = \Omega(\sqrt{K\lVert b\rVert_{2}^{2}}) K 1 ∑ θ = 1 K Reg θ = Ω ( K ∥ b ∥ 2 2 ) . From the definition of K K K ,
K ≥ 1 2 min { N , ∥ b ∥ 2 2 b max 2 } . K \ge\frac{1}{2}\min\left\{N,\frac{\lVert b\rVert_{2}^{2}}{b_{\max}^{2}}\right\}. K ≥ 2 1 min { N , b m a x 2 ∥ b ∥ 2 2 } .
Therefore,
K ∥ b ∥ 2 2 = Ω ( ∥ b ∥ 2 2 min { N , ∥ b ∥ 2 2 / b max 2 } ) = Ω ( min { ∥ b ∥ 2 N , ∥ b ∥ 2 2 b max } ) . \sqrt{K\lVert b\rVert_{2}^{2}} = \Omega\left(\sqrt{\lVert b\rVert_{2}^{2}\min\left\{N,\lVert b\rVert_{2}^{2}/b_{\max}^{2}\right\}}\right) = \Omega\left(\min\left\{\lVert b\rVert_{2}\sqrt{N},\frac{\lVert b\rVert_{2}^{2}}{b_{\max}}\right\}\right). K ∥ b ∥ 2 2 = Ω ( ∥ b ∥ 2 2 min { N , ∥ b ∥ 2 2 / b m a x 2 } ) = Ω ( min { ∥ b ∥ 2 N , b m a x ∥ b ∥ 2 2 } ) .
Finally, we consider a hard instance where b max ≤ O ( ∥ b ∥ 2 / N ) b_{\max} \le\mathcal{O}(\lVert b\rVert_{2}/\sqrt{N}) b m a x ≤ O (∥ b ∥ 2 / N ) . Under the min operation above, this hard instance yields a worst-case lower bound of Ω ( ∥ b ∥ 2 N ) \Omega\left(\lVert b\rVert_{2}\sqrt{N}\right) Ω ( ∥ b ∥ 2 N ) , which ends the proof. □ \square □
Reduction from Scale-Free Online Learning
We perform the reduction by treating each batch as a single meta-round. In batch j j j , the learner uses the decision produced by the online algorithm throughout I j = { t j − 1 + 1 , … , t j } I_j = \{t_{j-1}+1,\ldots,t_j\} I j = { t j − 1 + 1 , … , t j } , and feeds the aggregate loss over the batch back to the algorithm at time t j t_j t j .
OCO and Experts
We use the algorithm, namely, SOLO FTRL, and theorems proposed in [18 ] .
Lemma 9 (Corollary 1 of [18 ] ). Let K \mathcal{K} K be a nonempty bounded closed convex set equipped with a norm ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ , and let ψ : K → R + \psi:\mathcal{K}\to\mathbb{R}_{+} ψ : K → R + be lower semicontinuous and 1-strongly convex with respect to ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ . Define S = sup x ∈ K ψ ( x ) S=\sup_{x\in\mathcal{K}}\psi(x) S = sup x ∈ K ψ ( x ) . Then SOLO FTRL with regularizer
R ( w ) = 2.75 sup v ∈ K f ( v ) f ( w ) R(w)=\frac{\sqrt{2.75}}{\sqrt{\sup_{v\in\mathcal{K}}f(v)}}f(w) R ( w ) = sup v ∈ K f ( v ) 2.75 f ( w ) satisfies
Reg ≤ 13.3 sup v ∈ K f ( v ) ∑ j = 1 B ∥ z j ∥ ∗ 2 \operatorname{Reg}\le13.3\sqrt{\sup_{v\in\mathcal{K}}f(v)\sum_{j=1}^{B}\lVert z_j\rVert_{*}^{2}} Reg ≤ 13.3 v ∈ K sup f ( v ) j = 1 ∑ B ∥ z j ∥ ∗ 2 for any sequence of loss vector z 1 , … , z B z_1,\ldots,z_B z 1 , … , z B , where ∥ ⋅ ∥ ∗ \lVert\cdot\rVert_{*} ∥ ⋅ ∥ ∗ is the dual norm.
OCO. Let x ( j ) ∈ K x^{(j)}\in\mathcal{K} x ( j ) ∈ K denote the action selected at meta-round j j j and played throughout batch j j j , i.e., x ( t ) = x ( j ) x^{(t)}=x^{(j)} x ( t ) = x ( j ) for every t ∈ I j t\in I_j t ∈ I j . For each t ∈ I j t\in I_j t ∈ I j , recall g t ∈ ∂ f t ( x ( j ) ) g_t\in\partial f_t(x^{(j)}) g t ∈ ∂ f t ( x ( j ) ) is a subgradient at the decision used in batch j j j , and z j = ∑ t ∈ I j g t z_j=\sum_{t\in I_j}g_t z j = ∑ t ∈ I j g t . For every u ∈ K u\in\mathcal{K} u ∈ K , convexity gives
∑ t = 1 T ( f t ( x ( t ) ) − f t ( u ) ) ≤ ∑ j = 1 B ⟨ z j , x ( j ) − u ⟩ . \sum_{t=1}^{T}\left(f_t\left(x^{(t)}\right)-f_t(u)\right)\le\sum_{j=1}^{B}\langle z_j,x^{(j)}-u\rangle. t = 1 ∑ T ( f t ( x ( t ) ) − f t ( u ) ) ≤ j = 1 ∑ B ⟨ z j , x ( j ) − u ⟩ .
Thus, the batched OCO problem is reduced to OLO on the meta-losses z j z_j z j . Applying Lemma 9 gives
Reg ≤ C D 2 2 ∑ j = 1 B ∥ z j ∥ 2 2 = O ( D G ∑ j = 1 B b j 2 ) . \operatorname{Reg} \le C\sqrt{\frac{D^2}{2}\sum_{j=1}^{B}\lVert z_j\rVert_2^2}=O\left(DG\sqrt{\sum_{j=1}^{B}b_j^2}\right). Reg ≤ C 2 D 2 j = 1 ∑ B ∥ z j ∥ 2 2 = O D G j = 1 ∑ B b j 2 .
Experts Problem. Let l t ∈ [ 0 , 1 ] N l_t \in[0,1]^N l t ∈ [ 0 , 1 ] N be the expert-loss vector at round t t t , and let z j = ∑ t ∈ I j l t z_j=\sum_{t\in I_j}l_t z j = ∑ t ∈ I j l t . Then ∥ z j ∥ ∞ ≤ b j \lVert z_j\rVert_\infty\le b_j ∥ z j ∥ ∞ ≤ b j , and the regret in the batched experts problem is the OLO regret
Reg = ∑ j = 1 B ⟨ p j , z j ⟩ − min p ∈ Δ N ∑ j = 1 B ⟨ p , z j ⟩ . \operatorname{Reg}=\sum_{j=1}^{B}\langle p_j,z_j\rangle-\min_{p\in\Delta_N}\sum_{j=1}^{B}\langle p,z_j\rangle. Reg = j = 1 ∑ B ⟨ p j , z j ⟩ − p ∈ Δ N min j = 1 ∑ B ⟨ p , z j ⟩ .
Equip Δ N \Delta_N Δ N with the l 1 l_1 l 1 -norm and take
f ( p ) = ∑ i = 1 N p i log p i + log N . f(p)=\sum_{i=1}^{N}p_i\log p_i+\log N. f ( p ) = i = 1 ∑ N p i log p i + log N .
By Pinsker’s inequality, f f f is 1-strongly convex with respect to ∥ ⋅ ∥ 1 \lVert\cdot\rVert_1 ∥ ⋅ ∥ 1 , and sup p ∈ Δ N f ( p ) = log N \sup_{p\in\Delta_N}f(p)=\log N sup p ∈ Δ N f ( p ) = log N . Since the dual norm of l 1 l_1 l 1 is l ∞ l_\infty l ∞ , Lemma 9 gives
Reg ≤ C log N ∑ j = 1 B ∥ z j ∥ ∞ 2 ≤ O ( ∥ b ∥ 2 log N ) . \operatorname{Reg}\le C\sqrt{\log N\sum_{j=1}^{B}\lVert z_j\rVert_\infty^2}\le O\left(\lVert b\rVert_2\sqrt{\log N}\right). Reg ≤ C log N j = 1 ∑ B ∥ z j ∥ ∞ 2 ≤ O ( ∥ b ∥ 2 log N ) .
Adversarial Bandits
We use UMAB-NN proposed in [5 ] , as well as its theorem guarantees.
Lemma 10 (Theorem 1 of [5 ] ). Consider the oblivious adversarial bandit problem with N N N arms and nonnegative loss vectors z 1 , … , z B ∈ R + N z_1,\ldots,z_B\in\mathbb{R}_+^N z 1 , … , z B ∈ R + N . The UMAB-NN algorithm satisfies
E [ Reg ] = O ~ ( N ∑ j = 1 B ∥ z j ∥ ∞ 2 ) . \mathbb{E}[\operatorname{Reg}]=\widetilde{O}\left(\sqrt{N\sum_{j=1}^{B}\lVert z_j\rVert_\infty^2}\right). E [ Reg ] = O N j = 1 ∑ B ∥ z j ∥ ∞ 2 . At the beginning of batch j j j , the bandit algorithm samples an arm i j i_j i j , which is played throughout I j I_j I j . At the end of the batch, the learner observes z ~ j , i j \widetilde z_j,i_j z j , i j , the aggregate loss of the selected arm. Since l t ∈ [ 0 , 1 ] N l_t\in[0,1]^N l t ∈ [ 0 , 1 ] N , it is easy to see that z j ∈ R + N z_j\in\mathbb{R}_+^N z j ∈ R + N and ∥ z j ∥ ∞ ≤ b j \lVert z_j\rVert_\infty\le b_j ∥ z j ∥ ∞ ≤ b j . Applying Lemma 10 gives
E [ Reg ] = O ~ ( N ∥ b ∥ 2 ) . \mathbb{E}[\operatorname{Reg}]=\widetilde{O}\left(\sqrt{N}\lVert b\rVert_2\right). E [ Reg ] = O ( N ∥ b ∥ 2 ) .
Reduction from Delayed-Feedback Models
Similar to Appendix § 12 , we show that existing delayed-feedback results also recover the same order of upper bounds for the OCO and the experts problem. The reduction is conducted by viewing the feedback generated at each round of a batch as being delayed until the end of that batch. Specifically, for every t ∈ I j t\in I_j t ∈ I j , we view the feedback generated at round t t t as being delayed until the end of batch j j j , and define τ t = t j − t \tau_t=t_j-t τ t = t j − t . We use the delayed FTRL-PROX analysis of [11 ] . The following lemma is a specialization of their Theorem 4 to linear losses.
Lemma 11 (Specialization of Theorem 4 of [11 ] ). Let K \mathcal{K} K be a nonempty closed convex set equipped with a norm ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ , and let ψ : K → R + \psi:\mathcal{K}\to\mathbb{R}_{+} ψ : K → R + be 1 1 1 -strongly convex with respect to ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ . Define S = sup x ∈ K ψ ( x ) S=\sup_{x\in\mathcal{K}}\psi(x) S = sup x ∈ K ψ ( x ) . Consider delayed online linear optimization with loss vectors g 1 , … , g T g_1,\ldots,g_T g 1 , … , g T satisfying ∥ g t ∥ ∗ ≤ G \|g_t\|_{*}\le G ∥ g t ∥ ∗ ≤ G . Let τ ~ s \widetilde{\tau}_s τ s denote the update delay of the s s s -th feedback processed by the SOLID reduction of [11 ] . For any non-increasing sequence η 1 , … , η T > 0 \eta_1,\ldots,\eta_T>0 η 1 , … , η T > 0 , FTRL-PROX with cumulative regularizer r 0 : s ( x ) = ψ ( x ) η s r_{0:s}(x)=\frac{\psi(x)}{\eta_s} r 0 : s ( x ) = η s ψ ( x ) satisfies
Reg ≤ S η T + G 2 2 ∑ s = 1 T η s ( 1 + 2 τ ~ s ) . \operatorname{Reg}\leq\frac{S}{\eta_T}+\frac{G^2}{2}\sum_{s=1}^{T}\eta_s(1+2\widetilde{\tau}_s). Reg ≤ η T S + 2 G 2 s = 1 ∑ T η s ( 1 + 2 τ s ) . Moreover, ∑ s = 1 T τ ~ s = ∑ t = 1 T τ t \sum_{s=1}^{T}\widetilde{\tau}_s=\sum_{t=1}^{T}\tau_t ∑ s = 1 T τ s = ∑ t = 1 T τ t .
Let a s = 1 + 2 τ ~ s a_s=1+2\widetilde{\tau}_s a s = 1 + 2 τ s , A s = ∑ r = 1 s a r A_s=\sum_{r=1}^{s}a_r A s = ∑ r = 1 s a r . Setting η s = S G A s \eta_s=\frac{\sqrt{S}}{G\sqrt{A_s}} η s = G A s S is batch-oblivious, since A s A_s A s depends only on feedback already received. Using ∑ s = 1 T a s / A s ≤ 2 A T \sum_{s=1}^{T}a_s/\sqrt{A_s}\leq2\sqrt{A_T} ∑ s = 1 T a s / A s ≤ 2 A T , Lemma 11 gives Reg ≤ 2 G S A T \operatorname{Reg}\leq2G\sqrt{SA_T} Reg ≤ 2 G S A T . For our batched feedback pattern,
∑ t = 1 T τ t = ∑ j = 1 B ∑ t = t j − 1 + 1 t j ( t j − t ) = 1 2 ∑ j = 1 B b j ( b j − 1 ) . \sum_{t=1}^{T}\tau_t=\sum_{j=1}^{B}\sum_{t=t_{j-1}+1}^{t_j}(t_j-t)=\frac{1}{2}\sum_{j=1}^{B}b_j(b_j-1). t = 1 ∑ T τ t = j = 1 ∑ B t = t j − 1 + 1 ∑ t j ( t j − t ) = 2 1 j = 1 ∑ B b j ( b j − 1 ) .
Therefore,
A T = T + 2 ∑ t = 1 T τ t = ∑ j = 1 B b j 2 = ∥ b ∥ 2 2 . A_T=T+2\sum_{t=1}^{T}\tau_t=\sum_{j=1}^{B}b_j^2=\|b\|_2^2. A T = T + 2 t = 1 ∑ T τ t = j = 1 ∑ B b j 2 = ∥ b ∥ 2 2 .
OCO. Recall that g t ∈ ∂ f t ( x ( j ) ) g_t\in\partial f_t(x^{(j)}) g t ∈ ∂ f t ( x ( j ) ) for every t ∈ I j t\in I_j t ∈ I j , and let z j = ∑ t ∈ I j g t z_j=\sum_{t\in I_j}g_t z j = ∑ t ∈ I j g t . If only the aggregate first-order feedback z j z_j z j is returned at the end of batch j j j , we may equivalently feed the delayed algorithm b j b_j b j copies of g ˉ j = z j b j \bar g_j=\frac{z_j}{b_j} g ˉ j = b j z j , all arriving at time t j t_j t j . Since ∥ z j ∥ 2 ≤ G b j \|z_j\|_2\leq Gb_j ∥ z j ∥ 2 ≤ G b j , we have ∥ g ˉ j ∥ 2 ≤ G \|\bar g_j\|_2\leq G ∥ g ˉ j ∥ 2 ≤ G . Moreover, for every u ∈ K u\in\mathcal{K} u ∈ K , convexity gives
∑ t = 1 T ( f t ( x ( t ) ) − f t ( u ) ) ≤ ∑ j = 1 B ⟨ z j , x ( j ) − u ⟩ = ∑ j = 1 B ∑ t ∈ I j ⟨ g ˉ j , x ( j ) − u ⟩ . \sum_{t=1}^{T}\left(f_t(x^{(t)})-f_t(u)\right)\leq\sum_{j=1}^{B}\langle z_j,x^{(j)}-u\rangle=\sum_{j=1}^{B}\sum_{t\in I_j}\langle\bar g_j,x^{(j)}-u\rangle. t = 1 ∑ T ( f t ( x ( t ) ) − f t ( u ) ) ≤ j = 1 ∑ B ⟨ z j , x ( j ) − u ⟩ = j = 1 ∑ B t ∈ I j ∑ ⟨ g ˉ j , x ( j ) − u ⟩ .
Thus, the batched OCO regret is upper bounded by the regret of the corresponding delayed OLO instance. Equip K \mathcal{K} K with the Euclidean norm and take, for any fixed x 0 ∈ K x_0\in\mathcal{K} x 0 ∈ K ,
ψ ( x ) = 1 2 ∥ x − x 0 ∥ 2 2 . \psi(x)=\frac{1}{2}\|x-x_0\|_2^2. ψ ( x ) = 2 1 ∥ x − x 0 ∥ 2 2 .
Then ψ \psi ψ is 1 1 1 -strongly convex and S ≤ D 2 2 S\leq\frac{D^2}{2} S ≤ 2 D 2 . Applying Lemma 11 and A T = ∥ b ∥ 2 2 A_T=\|b\|_2^2 A T = ∥ b ∥ 2 2 gives
Reg ≤ 2 G D 2 2 ∥ b ∥ 2 2 = O ( D G ∥ b ∥ 2 ) . \operatorname{Reg}\leq2G\sqrt{\frac{D^2}{2}\|b\|_2^2}=O(DG\|b\|_2). Reg ≤ 2 G 2 D 2 ∥ b ∥ 2 2 = O ( D G ∥ b ∥ 2 ) .
Experts Problem. Let z ˉ j = ∑ t ∈ I j l t \bar z_j=\sum_{t\in I_j}l_t z ˉ j = ∑ t ∈ I j l t be the aggregate expert-loss vector in batch j j j . As above, at time t j t_j t j we may feed the delayed algorithm b j b_j b j copies of l ˉ j = z ˉ j b j \bar l_j=\frac{\bar z_j}{b_j} l ˉ j = b j z ˉ j . Since l t ∈ [ 0 , 1 ] N l_t\in[0,1]^N l t ∈ [ 0 , 1 ] N , we have l ˉ j ∈ [ 0 , 1 ] N \bar l_j\in[0,1]^N l ˉ j ∈ [ 0 , 1 ] N and ∥ l ˉ j ∥ ∞ ≤ 1 \|\bar l_j\|_\infty\leq1 ∥ l ˉ j ∥ ∞ ≤ 1 . This transformation preserves the regret:
Reg = ∑ j = 1 B ⟨ p j , z j ⟩ − min p ∈ Δ N ∑ j = 1 B ⟨ p , z j ⟩ = ∑ j = 1 B ∑ t ∈ I j ⟨ p j , l ˉ j ⟩ − min p ∈ Δ N ∑ j = 1 B ∑ t ∈ I j ⟨ p , l ˉ j ⟩ . \operatorname{Reg}=\sum_{j=1}^{B}\langle p_j,z_j\rangle-\min_{p\in\Delta_N}\sum_{j=1}^{B}\langle p,z_j\rangle=\sum_{j=1}^{B}\sum_{t\in I_j}\langle p_j,\bar l_j\rangle-\min_{p\in\Delta_N}\sum_{j=1}^{B}\sum_{t\in I_j}\langle p,\bar l_j\rangle. Reg = j = 1 ∑ B ⟨ p j , z j ⟩ − p ∈ Δ N min j = 1 ∑ B ⟨ p , z j ⟩ = j = 1 ∑ B t ∈ I j ∑ ⟨ p j , l ˉ j ⟩ − p ∈ Δ N min j = 1 ∑ B t ∈ I j ∑ ⟨ p , l ˉ j ⟩ .
Equip Δ N \Delta_N Δ N with the l 1 l_1 l 1 -norm and take
ψ ( p ) = ∑ i = 1 N p i log p i + log N . \psi(p)=\sum_{i=1}^{N}p_i\log p_i+\log N. ψ ( p ) = i = 1 ∑ N p i log p i + log N .
By Pinsker’s inequality, ψ \psi ψ is 1-strongly convex with respect to ∥ ⋅ ∥ 1 \lVert\cdot\rVert_1 ∥ ⋅ ∥ 1 , and
sup p ∈ Δ N ψ ( p ) = log N . \sup_{p\in\Delta_N}\psi(p)=\log N. p ∈ Δ N sup ψ ( p ) = log N .
Since the dual norm of l 1 l_1 l 1 is l ∞ l_\infty l ∞ , applying Lemma 11 with G = 1 G=1 G = 1 gives
Reg ≤ 2 log N ∥ b ∥ 2 = O ( ∥ b ∥ 2 log N ) . \operatorname{Reg}\leq2\sqrt{\log N}\lVert b\rVert_2=O\left(\lVert b\rVert_2\sqrt{\log N}\right). Reg ≤ 2 log N ∥ b ∥ 2 = O ( ∥ b ∥ 2 log N ) .
Naive Doubling Trick
As Intuitively shown in Table 1 , for each doubling epoch r r r , Algorithm 5 predicts the sum of squared known batch to be the actual sum of squared batch in epoch r r r , i.e., ∑ j = 1 2 r − 1 b j 2 = ∑ j = 2 r − 1 + 1 2 r b j 2 \sum_{j=1}^{2^{r-1}}b_j^2=\sum_{j=2^{r-1}+1}^{2^r}b_j^2 ∑ j = 1 2 r − 1 b j 2 = ∑ j = 2 r − 1 + 1 2 r b j 2 .
Table 1. Comparison of guessed and actual parameters across epochs.
Algorithm 5 Naive Doubling Trick under Adversarial Batched Setting
Play the uniform distribution until the first block ends (i.e., at time b 1 b_1 b 1 );
r ← 1 r\leftarrow1 r ← 1 ; ▷ start epoch 1
while 2 r ≤ B 2^r\leq B 2 r ≤ B do
g ( r ) ← ∑ j = 1 2 r − 1 b j 2 g^{(r)}\leftarrow\sum_{j=1}^{2^{r-1}}b_j^2 g ( r ) ← ∑ j = 1 2 r − 1 b j 2 ; ▷ guess squared 2-norm in epoch r r r
η ( r ) ← 8 ln N g ( r ) \eta^{(r)}\leftarrow\sqrt{\frac{8\ln N}{g^{(r)}}} η ( r ) ← g ( r ) 8 l n N ; ▷ set learning rate
Run Hedge on blocks 2 r − 1 + 1 , … , 2 r 2^{r-1}+1,\ldots,2^r 2 r − 1 + 1 , … , 2 r with learning rate η ( r ) \eta^{(r)} η ( r ) ;
r ← r + 1 r\leftarrow r+1 r ← r + 1 ; ▷ start a new epoch
end while
Example 1. Let m ≥ 2 m\geq2 m ≥ 2 be an integer power of 2. Consider a batch structure with B = 2 m B=2m B = 2 m batches:
b 1 = ⋯ = b m = 1 , b m + 1 = ⋯ = b 2 m = m , b_1=\cdots=b_m=1,\quad b_{m+1}=\cdots=b_{2m}=m, b 1 = ⋯ = b m = 1 , b m + 1 = ⋯ = b 2 m = m ,
and note that ∥ b ∥ 2 = m 3 + m = Θ ( m 3 / 2 ) \lVert b\rVert_2=\sqrt{m^3+m}=\Theta(m^{3/2}) ∥ b ∥ 2 = m 3 + m = Θ ( m 3/2 ) .
Consider an instance with N = 2 N=2 N = 2 experts. For simplicity, let both experts’ per-round losses to 0 in small blocks (b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m ) so that the first half of the game only serves to fool the naive algorithm. For the remaining m m m blocks, the losses alternate between the two experts. Specifically, for each k = 1 , 2 , … , m k=1,2,\ldots,m k = 1 , 2 , … , m , block j = m + k j=m+k j = m + k satisfies
( L 1 ( m + k ) , L 2 ( m + k ) ) = { ( 0 , m ) , if k is odd , ( m , 0 ) , if k is even . \left(L_1^{(m+k)},L_2^{(m+k)}\right)=
\begin{cases}
(0,m), & \text{if } k \text{ is odd},\\
(m,0), & \text{if } k \text{ is even}.
\end{cases} ( L 1 ( m + k ) , L 2 ( m + k ) ) = { ( 0 , m ) , ( m , 0 ) , if k is odd , if k is even .
Proof. of Proposition 2. Let R R R be the index of the last epoch in Algorithm 5. We argue that by the construction of Example 1, the actual number of blocks a a a in epoch R R R is exactly the second half of the blocks, i.e., a ( R ) = ∑ j = m + 1 m 2 m 2 = m 3 a^{(R)}=\sum_{j=m+1}^{m^2}m^2=m^3 a ( R ) = ∑ j = m + 1 m 2 m 2 = m 3 . On the other hand, Algorithm 5 guesses the number of blocks in the last epoch to be g ( R ) = ∑ j = 1 m 1 2 = m g^{(R)}=\sum_{j=1}^{m}1^2=m g ( R ) = ∑ j = 1 m 1 2 = m , which largely deviates from a ( R ) a^{(R)} a ( R ) . The corresponding learning rate for epoch R R R is then set to η ( R ) = 8 ln 2 m \eta^{(R)}=\sqrt{\frac{8\ln2}{m}} η ( R ) = m 8 l n 2 . In the following, we omit the superscript and write η \eta η for the learning rate in the last epoch for simplicity.
Since both actions have zero losses in the first m m m blocks, we have w 1 ( m + 1 ) = w 2 ( m + 1 ) = 1 w_1^{(m+1)}=w_2^{(m+1)}=1 w 1 ( m + 1 ) = w 2 ( m + 1 ) = 1 at the beginning of block m + 1 m+1 m + 1 . Since ( L 1 ( m + 1 ) , L 2 ( m + 1 ) ) = ( 0 , m ) \left(L_1^{(m+1)},L_2^{(m+1)}\right)=(0,m) ( L 1 ( m + 1 ) , L 2 ( m + 1 ) ) = ( 0 , m ) , Algorithm 5 incurs a loss of m 2 \frac{m}{2} 2 m , and updates the weights to w 1 ( m + 2 ) = e − η ⋅ 0 = 1 w_1^{(m+2)}=e^{-\eta\cdot0}=1 w 1 ( m + 2 ) = e − η ⋅ 0 = 1 and w 2 ( m + 2 ) = e − η ⋅ m = e − β w_2^{(m+2)}=e^{-\eta\cdot m}=e^{-\beta} w 2 ( m + 2 ) = e − η ⋅ m = e − β , where we use the shorthand β : = m ⋅ η = 8 m ln 2 \beta:=m\cdot\eta=\sqrt{8m\ln2} β := m ⋅ η = 8 m ln 2 .
Then, in block m + 2 m+2 m + 2 , the algorithm puts a much higher probability (of p 1 ( m + 2 ) = 1 1 + e − β p_1^{(m+2)}=\frac{1}{1+e^{-\beta}} p 1 ( m + 2 ) = 1 + e − β 1 ) on expert 1, and incurs a loss of m 1 + e − β \frac{m}{1+e^{-\beta}} 1 + e − β m . After that, the weights of the two experts are equal (w 1 ( m + 3 ) = w 2 ( m + 3 ) = e − β w_1^{(m+3)}=w_2^{(m+3)}=e^{-\beta} w 1 ( m + 3 ) = w 2 ( m + 3 ) = e − β ), so the next block m + 3 m+3 m + 3 is identical to block m + 1 m+1 m + 1 .
Repeating this pattern, there are m 2 \frac{m}{2} 2 m blocks (namely, blocks m + 1 , m + 3 , … m+1,m+3,\ldots m + 1 , m + 3 , … ) on which Algorithm 5 incurs a loss of m 2 \frac{m}{2} 2 m . On each of the remaining m 2 \frac{m}{2} 2 m blocks, the loss is m 1 + e − β \frac{m}{1+e^{-\beta}} 1 + e − β m . Note that either experts has a total loss of m 2 ⋅ m = m 2 / 2 \frac{m}{2}\cdot m=m^2/2 2 m ⋅ m = m 2 /2 over the entire horizon. Therefore, the regret is given by
m 2 ⋅ m 2 + m 2 ⋅ m 1 + e − β − m 2 2 = C m 2 = Ω ( m 2 ) , \frac{m}{2}\cdot\frac{m}{2}+\frac{m}{2}\cdot\frac{m}{1+e^{-\beta}}-\frac{m^2}{2}=Cm^2=\Omega(m^2), 2 m ⋅ 2 m + 2 m ⋅ 1 + e − β m − 2 m 2 = C m 2 = Ω ( m 2 ) ,
where C = 1 4 ⋅ 1 − e − β 1 + e − β = 1 4 ⋅ 1 − e − 8 m ln 2 1 + e − 8 m ln 2 = Ω ( 1 ) C=\frac{1}{4}\cdot\frac{1-e^{-\beta}}{1+e^{-\beta}}=\frac{1}{4}\cdot\frac{1-e^{-\sqrt{8m\ln2}}}{1+e^{-\sqrt{8m\ln2}}}=\Omega(1) C = 4 1 ⋅ 1 + e − β 1 − e − β = 4 1 ⋅ 1 + e − 8 m l n 2 1 − e − 8 m l n 2 = Ω ( 1 ) for all sufficiently large m m m .
On the other hand, the desired regret bound from Theorem 5 is
O ( ∥ b ∥ 2 log N ) = O ( m 3 / 2 ) O(\lVert b\rVert_2\sqrt{\log N})=O(m^{3/2}) O (∥ b ∥ 2 log N ) = O ( m 3/2 )
on this instance. This completes the proof. □
Adaptive Doubling Trick Sidesteps the Hard Instance
We further instantiate Theorem 7 on the hard instance from Example 1, showing that the adaptive doubling trick avoids the linear-regret failure mode of the naive doubling trick.
Corollary 1. For the adversarially batched experts instance constructed in Example 1, the naive doubling-trick adaptation of Hedge incurs expected regret Ω ( T ) \Omega(T) Ω ( T ) , whereas the adaptive doubling trick described in Algorithm 2 achieves a regret of O ( T 3 / 4 ) O(T^{3/4}) O ( T 3/4 ) .
Proof. We consider the case of Example 1, where Proposition 2 has shown that the naive doubling trick has a regret of Ω ( T ) \Omega(T) Ω ( T ) . Applying Theorem 7, we have
Reg N B = O ( ∥ b ∥ 2 log N ) = O ( m ⋅ m 2 log 2 ) = O ( m 3 / 2 ) . \operatorname{Reg}^{B}_{N}=O\left(\lVert b\rVert_2\sqrt{\log N}\right)=O\left(\sqrt{m\cdot m^2\log2}\right)=O\left(m^{3/2}\right). Reg N B = O ( ∥ b ∥ 2 log N ) = O ( m ⋅ m 2 log 2 ) = O ( m 3/2 ) .
Taking T ≍ m 2 T\asymp m^2 T ≍ m 2 back into the equation completes the proof. □