On Optimal Robustness to Adversarial Corruption in Online Decision Problems
Year: 2022

Abstract:
This paper considers two fundamental sequential decision-making problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus on stochastic regimes in which an adversary may corrupt losses, and we investigate what level of robustness can be achieved against adversarial corruption. The main contribution of this paper is to show that optimal robustness can be expressed by a square-root dependency on the amount of corruption. More precisely, we show that two classes of algorithms, anytime Hedge with decreasing learning rate and algorithms with second-order regret bounds, achieve O( logN ∆ + √ C logN ∆ )-regret, where N,∆, and C represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide a matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi-armed bandit problem, we also provide a nearly-tight lower bound up to a logarithmic factor.

text: algorithms with second-order regret bounds, achieve O( logN∆ + √ C logN ∆ )-regret, where N,∆, and C represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide a matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi-armed bandit problem, we also provide a nearly-tight lower bound up to a logarithmic factor.

heading: 1 Introduction
text: In this work, we consider two fundamental sequential decision-making problems, the problem of prediction with expert advice (expert problem) and the multi-armed bandit (MAB) problem. In both, a player chooses probability vectors pt over a given action set [N ] = {1, 2, . . . , N} in a sequential manner. More precisely, in each round t, a player chooses a probability vector pt ∈ [0, 1]N over the action set, and then an environment chooses a loss vector `t ∈ [0, 1]N . The player chooses pt, and then observes `t in the expert problem. In the MAB problem, the player picks action it ∈ [N ] following pt and then observes `tit . The goal of the player is to minimize the (pseudo-) regret R̄T defined as
RTi∗ = T∑ t=1 `>t pt − T∑ t=1 `ti∗ , R̄Ti∗ = E [RTi∗ ] , R̄T = max i∗∈[N ] R̄Ti∗ . (1)
For such decision-making problems, two main types of environments have been studied: stochastic environments and adversarial environments. In stochastic environments, the loss vectors are assumed to follow an unknown distribution, i.i.d. for all rounds. It is known that the difficulty of the problems can be characterized by the suboptimality gap parameter ∆ > 0, which denotes the minimum gap between the expected losses for the optimal action and for suboptimal actions. Given the parameter ∆, mini-max optimal regret bounds can be expressed as Θ( logN∆ ) in the expert problem [Degenne and Perchet, 2016, Mourtada and Gaïffas, 2019] and Θ(N log T∆ ) in the MAB problem [Auer et al., 2002a, Lai and Robbins, 1985, Lai, 1987]. In contrast to the stochastic model, the adversarial model does not assume any generative models for loss vectors, but the loss at each round may behave adversarially depending on the choices of the player up until that round. The mini-max optimal regret bounds for the adversarial model are Θ( √ T logN) in the expert problem [Cesa-Bianchi and Lugosi, 2006,
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Freund and Schapire, 1997] and Θ( √ TN) in the MAB problem [Audibert and Bubeck, 2009, Auer et al., 2002b].
As can be seen in the regret bounds, achievable performance differs greatly between the stochastic and adversarial regimes, which implies that the choice of models and algorithms will matter in many practical applications. One promising solution to this challenge is to develop best-of-both-worlds (BOBW) algorithms, which perform (nearly) optimally in both stochastic and adversarial regimes. For the expert problem, Gaillard et al. [2014] provide an algorithm with a BOBW property, and Mourtada and Gaïffas [2019] have shown that the well-known Hedge algorithm with decreasing learning rate (decreasing Hedge) enjoys a BOBW property as well. For the MAB problem, the Tsallis-INF algorithm by Zimmert and Seldin [2021] has a BOBW property, i.e., achieves O(N log T∆ )-regret in the stochastic regime and O( √ NT )-regret in the adversarial regime. One limitation of BOBW guarantees is, however, that they do not necessarily provide nontrivial regret bounds for a situation in which the stochastic and the adversarial regimes are mixed, i.e., an intermediate situation.
To overcome this BOBW-property limitation, our work focuses on an intermediate (and comprehensive) regime between the stochastic and adversarial settings. More specifically, we consider the adversarial regime with a self-bounding constraint introduced by Zimmert and Seldin [2021]. As shown by them, this regime includes the stochastic regime with adversarial corruption [Lykouris et al., 2018, Amir et al., 2020] as a special case in which an adversary modifies the i.i.d. losses to the extent that the total amount of changes does not exceed C, which is an unknown parameter referred to as the corruption level. For expert problems in the stochastic regime with adversarial corruption, Amir et al. [2020] have shown that the decreasing Hedge algorithm achieves O( logN∆ +C)-regret. For the MAB problem, Zimmert and Seldin [2021] have shown that Tsallis-INF
achieves O(N log T∆ + √ CN log T ∆ )-regret in adversarial regimes with self-bounding constraints. To
be more precise, they have proved a regret upper bound of O( ∑ i6=i∗ log T ∆i + √ C ∑ i6=i∗ log T ∆i
), where i∗ ∈ [N ] is the optimal action and ∆i represents the suboptimality gap for each action i ∈ [N ] \ {i∗}. Ito [2021b] has shown that similar regret bounds hold even when there are multiple optimal actions, i.e., even if the number of actions i with ∆i = 0 is greater than 1. In such cases, the terms of ∑ i 6=i∗ 1/∆i in regret bounds are replaced with ∑ i:∆i>0 1 ∆i
. In addition to this, Masoudian and Seldin [2021] have improved the analysis to obtain a refined regret
bound ofO ((∑ i6=i∗ 1 ∆i ) log+ ( (N−1)T ( ∑
i6=i∗ 1 ∆i )2
) + √ C (∑
i 6=i∗ 1
∆i
) log+ ( (N−1)T C ∑
i6=i∗ 1
∆i
)) , where
log+(x) = max {1, log x}. The contributions of this work are summarized in Table 1, alongside previously reported results. As shown in Theorems 3 and 4, this paper provides an improved regret upper bound of O( logN∆ +√
C logN ∆ ) for the expert problem in the adversarial regime with self-bounding constraints. This regret upper bound is tight up to a constant factor. In fact, we provide a matching lower bound in
Theorem 5. In addition to this, we show an Ω(N∆ + √ CN ∆ )-lower bound for MAB, which implies that
1Note that Amir et al. [2020] adopt a different definition of regret than in this paper. Details and notes for comparison are discussed in Remark 1.
Tsallis-INF by Zimmert and Seldin [2021] achieves a nearly optimal regret bound up to an O(log T ) factor in the adversarial regime with self-bounding constraints.
The regret bounds in Theorems 3 and 4 are smaller than the regret bound shown by Amir et al. [2020] for the stochastic regime with adversarial corruption, especially when C = Ω( logN∆ ), and they can be applied to more general problem settings in the adversarial regime with self-bounding constraints. Note here that this study and their study consider slightly different definitions of regret. More precisely, they define regret using losses without corruption, while this study uses losses after corruption to define regret. In practice, appropriate definitions would vary depending on individual situations. For example, if each expert’s prediction is itself corrupted, the latter definition is suitable. In contrast, if only the observation of the player is corrupted, the former definition seems appropriate. However, even after taking this difference in definitions into account, we can see that the regret bound in our work is, in a sense, stronger than theirs, as is discussed in Remark 1 of this paper. In particular,
we would like to emphasize that the new bound of O( logN∆ + √ C logN ∆ ) provides the first theoretical evidence implying that the corresponding algorithms are more robust against adversarial corruption than the naive Follow-the-Leader algorithm. Note also that the regret bound by Amir et al. [2020] is tight as long as the former regret definition is used.
This work shows the tight regret upper bounds for two types of known algorithms. The first, (Theorem 3), is the decreasing Hedge algorithm, which has been analyzed by Amir et al. [2020] and Mourtada and Gaïffas [2019] as well. The second (Theorem 4) represents algorithms with second-order regret bounds [Cesa-Bianchi et al., 2007, Gaillard et al., 2014, Hazan and Kale, 2010, Steinhardt and Liang, 2014, Luo and Schapire, 2015]. It is worth mentioning that Gaillard et al. [2014] have shown that a kind of second-order regret bounds impliesO( logN∆ )-regret in the stochastic regime. Theorem 4 in this work extends their analysis to a broader setting of the adversarial regime with self-bounding constraints. In the proof of Theorems 3 and 4, we follow a proof technique given by Zimmert and Seldin [2021] to exploit self-bounding constraints.
To show regret lower bounds in Theorems 5 and 6, we construct specific environments with corruption that provide insight into effective attacks which would make learning fail. Our approach to corruption is to modify the losses so that the optimality gaps decrease. This approach achieves a mini-max lower bound in the expert problem (Theorem 5) and a nearly-tight lower bound in MAB up to a logarithmic factor in T (Theorem 6). We conjecture that there is room for improvement in this lower bound for MAB under assumptions regarding consistent policies [Lai and Robbins, 1985], and that the upper bound by Zimmert and Seldin [2021] is tight up to a constant factor.

heading: 2 Related work
text: In the context of the expert problem, studies on stochastic settings seem to be more limited than those on adversarial settings. De Rooij et al. [2014] have focused on the fact that the Follow-theLeader (FTL) algorithm works well for a stochastic setting, and they have provided an algorithm that combines FTL and Hedge algorithms to achieve the best of both worlds. Gaillard et al. [2014] have provided an algorithm with a second-order regret bound depending on VTi∗ = ∑T t=1(` > t pt−`ti∗)2 in place of T and have shown that such an algorithm achieves O( logN∆ )-regret in the stochastic regime. Mourtada and Gaïffas [2019] have shown that a simpler Hedge algorithm with decreasing learning
rates of ηt = Θ( √ logN t ) enjoys a tight regret bound in the stochastic regime as well. This simple decreasing Hedge algorithm has been shown by Amir et al. [2020] to achieve O( logN∆ +C)-regret in the stochastic regime with adversarial corruption. For online linear optimization, a generalization of the expert problem, Huang et al. [2016] have shown that FTL achieves smaller regret in the stochastic setting and provides best-of-both-worlds algorithms via techniques reported by Sani et al. [2014].
For MAB, there are a number of studies on best-of-both-worlds algorithms [Bubeck and Slivkins, 2012, Zimmert and Seldin, 2021, Seldin and Slivkins, 2014, Seldin and Lugosi, 2017, Pogodin and Lattimore, 2020, Auer and Chiang, 2016, Wei and Luo, 2018, Zimmert et al., 2019, Lee et al., 2021, Ito, 2021b]. Among these, studies by Wei and Luo [2018], Zimmert and Seldin [2021], Zimmert et al. [2019] are closely related to this work. In their studies, gap-dependent regret bounds in the stochastic regime are derived via {pt}-dependent regret bounds in the adversarial regime, similarly to that seen in this work and in previous studies by Gaillard et al. [2014], Amir et al. [2020].
Studies on online optimization algorithms robust against adversarial corruption have been extended to a variety of models, including those for the multi-armed bandit [Lykouris et al., 2018, Gupta et al., 2019, Zimmert and Seldin, 2021, Hajiesmaili et al., 2020], Gaussian process bandits [Bogunovic et al., 2020], Markov decision processes [Lykouris et al., 2021, Chen et al., 2021, Jin et al., 2021], the problem of prediction with expert advice [Amir et al., 2020], online linear optimization [Li et al., 2019], and linear bandits [Bogunovic et al., 2021, Lee et al., 2021]. Literature can also be found regarding effective attacks on bandit algorithms [Jun et al., 2018, Liu and Shroff, 2019].
As summarized by Hajiesmaili et al. [2020], there can be found studies on two different models of adversarial corruption: the oblivious corruption model and the targeted corruption model. In the former (e.g., in studies by Lykouris et al. [2018], Gupta et al. [2019], Bogunovic et al. [2020]), the attacker may corrupt the losses `t after observing (`t, pt) without knowing the chosen action it while, in the latter (e.g., in studies by Jun et al. [2018], Hajiesmaili et al. [2020], Liu and Shroff [2019], Bogunovic et al. [2021], Ito [2021a], Erez and Koren [2021]), the attacker can choose corruption depending on (`t, pt, it). We discuss differences between these models in Section 3. This work mainly focuses on the oblivious corruption model for MAB problems. It is worth mentioning that Tsallis-INF [Zimmert and Seldin, 2021] works well in the oblivious corruption models, as is shown in Table 1, as well as achieving best-of-both-worlds.

heading: 3 Problem setting
text: A player is givenN , the number of actions. In each round t = 1, 2, . . . the player chooses a probability vector pt = (pt1, pt2, . . . , ptN )> ∈ {p ∈ [0, 1]N | ‖p‖1 = 1}, and then the environment chooses a loss vector `t = (`t1, `t2, . . . , `tN )> ∈ [0, 1]N . In the expert problem, the player can observe all entries of `t after outputting pt. By way of contrast, in the MAB problem, the player picks it w.r.t. pt, i.e., chooses it so that Prob[it = i|pt] = pti, and then observes `tit . The performance of the player is measured by means of the regret defined in (1).
Note that in MAB problems we have
E [ T∑ t=1 (`tit − `ti∗) ] = E [ T∑ t=1 ( `>t pt − `ti∗ )] = R̄Ti∗ (2)
under the assumption that `t is independent of it, given pt.
This paper focuses on environments in the following regime: Definition 1 (Adversarial regime with a self-bounding constraint [Zimmert and Seldin, 2021]). We say that the environment is in an adversarial regime with a (i∗,∆, C, T ) self-bounding constraint if
R̄Ti∗ = E [ T∑ t=1 (`>t pt − `ti∗) ] ≥ ∆ ·E [ T∑ t=1 (1− pti∗) ] − C (3)
holds for any algorithms, where ∆ ∈ [0, 1] and C ≥ 0.
In this paper, we deal with the situation in which the player is not given parameters (i∗,∆, C, T ).
The regime defined in Definition 1 includes the following examples: Example 1 (Stochastic regime). Suppose `t ∈ [0, 1]N follows an unknown distribution D over i.i.d. for t ∈ {1, 2, . . .}. Denote µ = E`∼D[`], and let i∗ ∈ arg mini∈[N ] µi and ∆ = mini∈[N ]\{i∗}(µi − µi∗). The environment is then in the adversarial regime with a self-bounding constraint (3) with C = 0. Note here that ∆ > 0 implies that the optimal action is unique, i.e., µi > mi∗ holds for any action i ∈ [N ] \ {i∗}. Example 2 (Adversarial regime). If we set ∆ = 1 and C = 2T , for any i∗ ∈ [N ] and for any algorithms, arbitrary loss sequences {`t}Tt=1 ⊆ [0, 1]N satisfy (3). This means that the (purely) adversarial environment will be in the adversarial regime with a (i∗, 1, 2T, T ) self-bounding constraint for any i∗ ∈ [N ] and T . Example 3 (Stochastic regime with adversarial corruption). Suppose `t ∈ [0, 1]N is given as follows: (i) a temporary loss `′t ∈ [0, 1]N is generated from an unknown distribution D (i.i.d. for t) and (ii) an adversary corrupts `′t after observing pt to determine `t subject to the constraint of
∑T t=1 ‖E[`t] − E[`′t]‖∞ ≤ C. As shown in [Zimmert and Seldin, 2021], this regime satisfies (3), i.e., is a special case of the adversarial regime with a self-bounding constraint. Remark 1. For the stochastic regime with adversarial corruption, different notions of regret can be found in the literature. An alternative to the definition in (1) is regret w.r.t. losses without corruption, i.e., R′Ti∗ = ∑T t=1 ( `′>t pt − `′ti∗ ) , (R̄′Ti∗ , and R̄ ′ T can also be defined in a similar way). In general, which metric will be appropriate depends on the situation in which the algorithm is applied. For example, in the case of prediction with expert advice, if each expert’s prediction is itself corrupted, the player’s performance should be evaluated in terms of the regret R̄T , as the consequential prediction performance is determined by the losses `t after corruption, not by `′t. In contrast, if only the observation of the player is corrupted, the performance should be evaluated in terms of R̄′T .
We can easily see that |R̄′Ti∗ − R̄Ti∗ | ≤ 2C. Amir et al. [2020] have shown a regret bound of R̄′T = O
( logN ∆ + C ) , which immediately implies R̄T = O ( logN ∆ + C ) . Similarly, a regret bound
of R̄T = O ( logN ∆ + √ C logN ∆ ) immediately implies R̄′T = O ( logN ∆ + C ) . In fact, from the
AM-DM inequality, we have
logN
∆ +
√ C logN
∆ ≤ logN ∆ + 1 2
( C + logN
∆
) = O ( C + logN
∆
) .
Note here that the former bound of R̄T = O ( logN ∆ + √ C logN ∆ ) is properly stronger than the latter
of R̄′T = O ( logN ∆ + C ) , as the latter does not necessarily imply the former.
Remark 2. In MAB, a targeted corruption model has been considered to be a variant of the model in Example 3. In this model, the adversary corrupts the losses after observing it. In this case, the loss `t after corruption and it are dependent given pt, and hence (2) does not always hold.

heading: 4 Regret upper bound

heading: 4.1 Known regret bounds for adversarial regimes by hedge algorithms
text: The Hedge algorithm [Freund and Schapire, 1997] (also called the multiplicative weight update [Arora et al., 2012] or the weighted majority forecaster [Littlestone and Warmuth, 1994]) is known to be a mini-max optimal algorithm for the expert problem. In the Hedge algorithm, the probability vector pt is defined as follows:
wti = exp ( − ηt t−1∑ j=1 `ji ) , pt = wt ‖wt‖1 , (4)
where ηt > 0 are learning rate parameters. If pt is given by (4), the regret is bounded as follows: Lemma 1. If {pt}Tt=1 is given by (4) with decreasing learning rates (i.e., ηt ≥ ηt+1 for all t), for any {`t}Tt=1 and i∗ ∈ [N ], the regret is bounded as
RTi∗ ≤ logN
η1 + T∑ t=1
( 1
ηt N∑ i=1 ptig (ηt(−`ti + αt)) + ( 1 ηt+1 − 1 ηt ) H(pt+1) ) , (5)
for any {αt}Tt=1 ⊆ R, where g and H are defined as
g(x) = exp(x)− x− 1, H(p) = N∑ i=1 pi log 1 pi . (6)
From this lemma, using g(x) ≈ x2/2 and H(p) ≤ logN , we obtain the following regret bounds for adversarial settings: Theorem 1 (Theorem 2.3 in [Cesa-Bianchi and Lugosi, 2006]). If pt is given by (4) with ηt =√
8 logN t , for any T , i ∗ ∈ [N ] and {`t}Tt=1 ⊆ [0, 1]N , the regret is bounded as RTi∗ ≤ √ 2T logN + logN/8. (7)
Hedge algorithms with decreasing learning rates ηt = Θ( √ logN t ), as in Theorem 1, are referred to as decreasing Hedge, e.g., in [Mourtada and Gaïffas, 2019]. Such algorithms are shown by Mourtada
and Gaïffas [2019] to achieve O( √
logN ∆ )-regret in stochastic regimes, and are also shown, by Amir et al. [2020], to achieve O( √
logN ∆ + C)-regret in stochastic regimes with adversarial corruption.
Besides such worst-case regret bounds as found in Theorem 1, a variety of data-dependent regret bounds have also been developed (see, e.g., [Steinhardt and Liang, 2014]). One remarkable example is that of the second-order bounds by Cesa-Bianchi et al. [2007], which depend on parameters VT defined as follows:
vt = N∑ i=1 pti(`ti − `>t pt)2, VT = T∑ t=1 vt (8)
A regret bound depending on VT rather than T can be achieved wih the following adaptive learning rates:
Theorem 2 (Theorem 5 in [Cesa-Bianchi et al., 2007]). If pt is given by (4) with, ηt =
min { 1, √ 2( √
2−1) logN (e−2)Vt−1
} , the regret is bounded as
RTi∗ ≤ 4 √ VT logN + 2 logN + 1/2 (9)
for any T , i∗ and {`t}Tt=1 ⊆ [0, 1]N .
As VT ≤ T follows from the definition (8), the regret bound in (2) includes the worst-case regret bound of RTi∗ = O( √ T logN). Further, as shown in Corollary 3 of [Cesa-Bianchi et al., 2007], the bound in Theorem 2 implies RTi∗ = O( √ LTi∗ (T−LTi∗ ) T logN), where LTi∗ = ∑T t=1 `ti∗ . This means that the regret will be improved if the cumulative loss LTi∗ for optimal action i∗ is small or is close to T .

heading: 4.2 Refined regret bound for decreasing Hedge
text: This subsection shows that the algorithm described in Theorem 1 enjoys the following regret bound as well:
Theorem 3. If pt is given by (4) with ηt = √ 8 logN t , we have
R̄Ti∗ ≤ 100 logN
∆ + 10
√ C logN
∆ (10)
under the assumption that (3) holds.
Proof. Using the fact that g(x) ≤ (e−1)x 2
2 for x ≤ 1 andH(p) ≤ (1−pi∗)(1+logN−log(1−pi∗)), from Lemma 1, we obtain
RTi∗ ≤ 9 logN + 1
4 √ logN T∑ t=1 1− pti∗√ t ( 12 logN + log
1
1− pti∗
) . (11)
A proof for (11) can be found in the appendix. From (3) and (11), for any λ > 0, we have
R̄Ti∗ = (1 + λ)R̄Ti∗ − λR̄Ti∗
≤ E [ (1 + λ) ( 9 logN +
1
4 √ logN T∑ t=1 1− pti∗√ t ( 12 logN + log
1
1− pti∗
)) − λ ( ∆
T∑ t=1 (1− pti∗)− C
)]
≤ 9(1 + λ) logN + λC + 1 + λ 4 √ logN E [ T∑ t=1 1− pti∗√ t ( 12 logN − 4λ∆ √ t logN 1 + λ − log(1− pti∗) )] .
To bound the values of the expectation, we use the following inequality T∑ t=1 xt√ t ( a− b √ t− log xt ) ≤ 2a 2 + 1 b + b (12)
which holds for any a, b > 0, T and {xt}Tt=1 ⊆ (0, 1). A proof of (12) is given in the appendix. Combining the above two displayed inequalities with a = 12 logN and b = 4λ∆ √ logN
1+λ , we obtain
R̄Ti∗ ≤ 9(1 + λ) logN + λC + 1 + λ
4 √ logN
( (2(12 logN)2 + 1)
1 + λ
4λ∆ √ logN +
4λ∆ √ logN
1 + λ ) = 9(1 + λ) logN + λC + (1 + λ)2 λ∆ logN · ( 18(logN)2 + 1 16 ) + ∆
≤ 9 logN + ∆ + 38 logN ∆ + λ
( 9 logN + C + 19 logN
∆
) + 1
λ
19 logN
∆ .
By choosing λ = √
( 19 logN∆ )/(9 logN + C + 19 logN ∆ ), we obtain
R̄Ti∗ ≤ 9 logN + ∆ + 38 logN
∆ + 2
√( 9 logN + C + 19 logN
∆
) 19 logN
∆
≤ 9 logN + ∆ + 38 logN ∆ + 2
√ 532 ( logN
∆
)2 + 19C logN
∆
≤ 9 logN + ∆ + (38 + 2 √ 532) logN ∆ + 2 √ 19
√ C logN
∆ ≤ 100 logN ∆ + 10
√ C logN
∆
where the third inequality follows from √ x+ y ≤ √ x+ √ y for x, y ≥ 0. Combining Theorems 1 and 3, we can see that the decreasing Hedge with ηt = √ 8 logN t achieves
R̄Ti∗ = O(min{ logN∆ + √ C logN ∆ , √ T logN}) in the adversarial regive with self-bounding constraints. This bound will be shown to be tight up to a constant factor in Section 5.

heading: 4.3 Refined regret bound for adaptive Hedge
text: In this subsection, we show that a second-order regret bound as seen in Theorem 2 implies tight gap-dependent regret bounds in the adversarial regime with a self-bounding constraint.
We start from the observation that vt defined in (8) satisfies vt ≤ (1− pti∗) for any i∗. In fact, we have vt ≤ ∑N i=1 pti(`ti − α)2 for any α ∈ R as the right-hand side is minimized when α = `>t pt, from which it follows that
vt ≤ N∑ i=1 pti(`ti − `ti∗)2 = ∑ i∈[N ]\{i∗} pti(`ti − `ti∗)2 ≤ ∑ i∈[N ]\{i∗} pti = 1− pti∗ . (13)
Hence, the regret bound in Theorem 2 implies
RTi∗ ≤ 4 √√√√logN T∑ t=1 (1− pti∗) + 2 logN + 1 2 . (14)
Such a regret bound depending on ∑T t=1(1− pti∗) leads to a tight gap-dependent regret bound, as shown in the following theorem: Theorem 4. Suppose that the regret is bounded as
RTi∗ ≤ √√√√A T∑ t=1 (1− pti∗) +B. (15)
Then, under the condition of (3), the pseudo-regret is bounded as
R̄Ti∗ ≤ A
∆ +B +
√ A(B + C)
∆ . (16)
Proof. From (15) and (3), for any λ > 0 we have
R̄Ti∗ = (1 + λ)R̄Ti∗ − λR̄Ti∗
≤ E (1 + λ)  √√√√A T∑
t=1
(1− pti∗) +B − λ(∆ T∑ t=1 (1− pti∗)− C ) ≤ A(1 + λ) 2
4λ∆ + (1 + λ)B + λC =
A
2∆ +B +
1
λ
A
4∆ + λ
( A
4∆ +B + C
) ,
where the second inequality follows from a √ x− bx = −b( √ x− a2b ) 2 + a 2 4b ≤ a2
4b for a > 0, b ∈ R and x ≥ 0. By choosing λ = √ ( A4∆ )/( 1 4∆ +B + C) we obtain
R̄Ti∗ ≤ A
2∆ +B + 2
√ A 4∆ · ( A 4∆ +B + C ) = A 2∆ +B + √( A 2∆ )2 + A(B + C) ∆
≤ A 2∆ +B + A 2∆ +
√ A(B + C)
∆ = A ∆ +B +
√ A(B + C)
∆ ,
where the second inequality follows from √ x+ y ≤ √ x+ √ y for x, y ≥ 0.
Combining this theorem and (14), we obtain the following regret bound for the algorithm described in Theorem 2:
Corollary 1. If pt is chosen by (4) with ηt = min{1, √ 2( √
2−1) logN (e−2)Vt−1 }, under the condition of (3), the pseudo regret is bounded as R̄Ti∗ ≤ 16 logN∆ + 4 √ (3 logN+C) logN ∆ + 3 logN .
Theorem 4 can be applied to algorithms other than the one in Theorem 2. One example is an algorithm by Gaillard et al. [2014]. In Corollary 8 of their paper, a regret bound of RTi∗ ≤ C1 √ logN ∑ t=1(` > t pt − `ti∗)2 + C2 is provided. Then, as it holds that (`>t pt − `ti∗)2 ≤ 1− pti∗ , we have (15) with appropriate A and B, and, consequently, we obtain the regret bound given in (16).

heading: 5 Regret lower bound
text: This section provides (nearly) tight lower bounds for the expert problem and the MAB problem in the adversarial regime with a self-bounding constraint. Let us begin by describing the statement for the expert problem: Theorem 5. For any ∆ ∈ (0, 1/4), N ≥ 4, T ≥ 4 logN , C ≥ 0, and for any algorithm for the expert problem, there exists an environment in the adversarial regime with a (i∗,∆, N,C, T ) self-bounding constraint for which the pseudo-regret is at least
R̄Ti∗ = Ω
( min { logN
∆ +
√ C logN
∆ , √ T logN }) . (17)
To show this lower bound, we define a distribution D∆,i∗ over {0, 1}N for ∆ ∈ (0, 1/4) and i∗ ∈ [N ], as follows: if ` ∼ D∆,i∗ , `i∗ follows a Bernoulli distribution of parameter 1/2−∆, i.e., Prob[`i∗ = 1] = 1/2−∆ and Prob[`i∗ = 0] = 1/2 + ∆, and `i follows a Bernoulli distribution of parameter 1/2 for i ∈ [N ] \ i∗, independently. We then can employ the following lemma: Lemma 2 (Proposition 2 in [Mourtada and Gaïffas, 2019]). For any algorithm and for any ∆ ∈ (0, 1/4), N ≥ 4 and T ≥ logN∆2 , there exists i ∗ such that R̄Ti∗ ≥ logN256∆ holds for (`t) T t=1 ∼ DT∆,i∗ .
Using this lower bound, we can show Theorem 5. Proof of Theorem 5. We show lower bounds for the following four cases: (i) If T ≤ logN∆2 , R̄Ti∗ = Ω( √ T logN). (ii) If C∆ ≤ logN ∆2 ≤ T , R̄Ti∗ = Ω( logN ∆ ). (iii) If logN ∆2 ≤ C ∆ ≤ T ,
R̄Ti∗ = Ω( √ C logN ∆ ). (iv) If logN ∆2 ≤ T ≤ C ∆ , R̄Ti∗ = Ω( √ T logN). Combining all four cases of (i)–(iv), we obtain (17).
(i) Suppose T < logN∆2 . Set ∆ ′ = √ logN T . We then have T = logN ∆′2 and ∆ < ∆
′ ≤ 1/4. If `t ∼ D∆′,i∗ for all t ∈ [T ], the environment is then in an adversarial regime with a (i∗,∆, N,C, T ) self-bounding constraint for any C ≥ 0, and the regret is bounded as R̄Ti∗ ≥ logN256∆′ = Ω( √ T logN) from Lemma 2.
(ii) Suppose C∆ ≤ logN ∆2 ≤ T . If `t ∼ D∆,i∗ for all t ∈ [T ], the regret is bounded as R̄Ti∗ ≥ logN 256∆ for some i∗ from Lemma 2. The environment is then in an adversarial regime with a (i∗,∆, N,C, T ) self-bounding for any C ≥ 0.
(iii) Suppose logN∆2 ≤ C ∆ ≤ T . Define ∆
′ = √
∆ logN C ≤ ∆. We then have logN ∆′ = √ C logN∆ .
Let T ′ = d logN∆′2 e = d C ∆e ≤ T . Consider an environment in which `t ∼ D∆′,i∗ for t ∈ [T ′] and `t ∼ D∆,i∗ for t ∈ [T ′+1, T ]. Then from Lemma 2, there exists i∗ ∈ [N ] such that R̄Ti∗ ≥ R̄T ′i∗ ≥ logN
∆′ = Ω( √ C logN ∆ ). Further, we can show that the environment is in an adversarial regime with a
(i∗,∆, N,C, T ) self-bounding constraint. In fact, we have T ′(∆−∆′) ≤ C∆ (∆−∆ ′) ≤ C.
(iv) Suppose logN∆2 ≤ T ≤ C ∆ . Set ∆
′ = √
logN T and consider `t ∼ D∆′,i∗ for all t ∈ [T ]. The regret
is then bounded as R̄Ti∗ ≥ logN256∆′ = Ω( √ T logN) for some i∗, from Lemma 2. We can confirm that the environment is in an adversarial regime with a (i∗,∆, N,C, T ) self-bounding constraint, as we have ∆′T ≤ ∆T ≤ C, where the first and second inequalities follow from logN∆2 ≤ T and T ≤ C ∆ , respectively.
Via a similar strategy to that used in this proof, we can show the regret lower bound for the MAB problem as well: Theorem 6. For any ∆ ∈ (0, 1/4), N ≥ 4, T ≥ 4 logN , C ≥ 0, and for any multi-armed bandit algorithm, there exists an environment in the adversarial regime with a (i∗,∆, N,C, T ) self-bounding constraint for which the pseudo-regret is at least
R̄Ti∗ = Ω
( min { N
∆ +
√ CN
∆ , √ NT
}) . (18)
We can demonstrate this theorem by means of the following lemma: Lemma 3 ([Auer et al., 2002b]). For any multi-armed bandit algorithm and for any ∆ ∈ (0, 1/4), N ≥ 4 and T ≥ N∆2 , there exists i ∗ such that R̄Ti∗ ≥ N32∆ holds for (`t) T t=1 ∼ DT∆,i∗ .
A complete proof of Theorem 6 can be found in the appendix.

heading: 6 Discussion
text: In this paper, we have shown O(R+ √ CR)-regret bounds for the expert problem, where R stands for the regret bounds for the environment without corruption and C stands for the corruption level. From the matching lower bound, we can see that this O( √ CR)-term characterizes optimal robustness against corruption. One natural question is whether such O(R+ √ CR)-type regret bounds can be found for other online decision problems, such as online linear optimization, online convex optimization, linear bandits, and convex bandits. To our knowledge, algorithms achieving O(R+ √ CR)-regret are known at this time for the expert problem, for the MAB problem [Zimmert and Seldin, 2021], for the combinatorial semi-bandit problem [Zimmert et al., 2019, Ito, 2021a], and the problem of online learning with feedback graphs [Erez and Koren, 2021]. What these algorithms have in common is that they use a
framework of Follow-the-Regularized-Leader with decreasing learning rates and that they achieve the best-of-both-worlds simultaneously. As Amir et al. [2020] suggest, online mirror descent algorithms does not have O(R+ √ CR)-regret bounds, in contrast to the Follow-the-Regularized-Leader case. We believe that characterizing algorithms with O(R+ √ CR)-regret bounds will be important for future work.
Another question is whether we can remove the assumption that the optimal action is unique. This assumption is required for the analysis of most algorithms withO(R+ √ CT )-regret bounds [Zimmert et al., 2019, Ito, 2021a, Erez and Koren, 2021]. One exception to this is the Tsallis-INF algorithm by Zimmert and Seldin [2021], which was shown by Ito [2021b] to not require the uniqueness assumption. It is not yet known, however, whether the technique by Ito [2021b] can be applied to the expert problem.
On Potential Societal Impact This study focuses on the robustness of online optimization algorithms and includes a discussion of effective attacks on algorithms. The regret upper bounds obtained in this study suggest that the impact of the attacker on the learning outcome is rather limited. Hence, at this point, we do not see any particular negative social consequences. Researchers working on the theory of online optimization and adversarial robustness may benefit from this paper.
Acknowledgments and Disclosure of Funding
The author was supported by JST, ACT-I, Grant Number JPMJPR18U5, Japan.

Review summaries:
The paper considered expert problem and multi-armed bandits in stochastic environment with adversarial corruption. In this setting, an adversary modifies stochastic feedback up to total corruption level $C$. The authors analyzed Hedge algorithm with decreasing learning rate and algorithms with second-order regret bounds, and showed that the regret has a $\sqrt{C}$ dependency to the corruption level. Matching lower bound in the expert problem and near-tight lower bound up to logarithmic factor in the multi-armed bandit problem, suggesting the analyzed algorithms achieve optimal robustness. 

The paper investigates on the regret bounds for the expert advice problem and the multi-armed bandit in a quite general intermediate regime so called adversarial regime with a self-bounding constraint provided by Zimmert and Seldin (2021) (henceforth ZS21). For the expert advice problem in this general regime, the authors provide two regret bounds and a matching lower bound for an instance of Decreasing Hedge algorithm and algorithms with the second-order bounds. For the multi-armed bandit problem they achieve a lower bound in the mentioned intermediate regime that matches with the state-of-the-art result by ZS21 up to a logarithmic factor.