On Optimal Robustness to Adversarial Corruption in Online Decision Problems
Authors: Shinji Ito
Venue: NeurIPS 2021 Poster (2021)
Keywords: regret analysis
adversarial corruption
best of both worlds
best of three worlds
adversarial robustness

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( \frac{\log N}{\Delta} + \sqrt{ \frac{C \log N }{\Delta} } )$-regret, where $N, \Delta$, 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.

On Optimal Robustness to Adversarial Corruption in Online Decision Problems
Shinji Ito NEC Corporation --shinjinnec... com
Abstract
This paper considers two fundamental sequential decision-makin problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus stochastic regimes in which an adversary may corrupt losses, and inves- tigate what level of robustness can be achieved against adversarial corruption. The main contribution of this paper is to show that optimal robustness be expressed by 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 Nog A
C'log N )-regret,
where N, A, and C' represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi- bandit problem, we also provide nearly-tight lower bound up to a logarithmic factor.
Introduction
In this work, we consider two fundamental sequential decision-making problems, the problem of prediction with expert advice (expert problem) and the a player chooses probability vectors over a given action set [A]] = {1, 2....... .N } in sequential manner. More precisely, in each round t, player chooses probability vector p. [0, 1]x over the action set, and then an environment chooses a loss vector l E [o, 1| The player chooses pt. and then observes l, in the expert problem. In the MAB problem, the player picks action E [N] following pt and then observes tii. The goal of the player is to minimize the (pseudo-) regret Ri defined as
bandit (MAB) problem. In both,
T c 1=1
RIY
Σ
R = E RRre, R = max RI 1' E
(1)
For such decision-makin problems, two main types of environments have been studied: stochastic environments and adversarial environments. 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 A > which denotes the minimum gap between the expected losses for the optimal action and for suboptimal actions. Given the parameter
A, mini-max optimal regret bounds can be expressed as O
log
N in the expert problem Degenne and
A
Perchet 2016 Mourtada and Gaïffas 2019) and O log o in the MAB problem [Auer al. 2002a
Lai and Robbins (1985]] [985]Lai 1987] In contrast to the stochastic model, the adversarial model does not
assume any generative models for loss vectors, but the loss each round may behave adversarially depending the choices of the player up until that round. The mini-max optimal regret bounds
for the adversarial model are ((v log N) the expert problem [Cesa-Bianchi and Lugosi 2006
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table I: Regret bounds in stochastic regimes with adversarial corruption
Problem setting
Upper bound
Lower bound
Expert problem
log N
+
Amir et al.
2020
Ω
log N
C log N
log N A
+
N A
Theorems 3
[Theorem 5
Multi-armes bandit
0
NloR
+
CN Ing T
Ω
CN
Zimmert and Seldin, 2021
[Theorem 6
Freund and Schapire, 1997] and ((VTN) 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 many practical applications. One promising solution to this challenge is to develop hest-of-bothh-ood (BOBW) algorithms, which perform (nearly) optimally in both stochastic and adversarial regimes. For the expert problem. Gaillard et al. (2144) provide algorithm with a BOBW property, and Mourtadal and Gaiffas (2119] have shown that the well-known Hedge algorithm with decreasing learning rate (decreasing Hedge) enjoys BOBW property as well. For the MAB problem, the Tsallis-INF algorithm by Zimmert and Seldin (2021) has BOBW property, i.e., achieves O N log )-regret 3
in the stochastic regime and O (VVNT)) (NT) in the adversarial regime. One limitation of BOBW guarantees is, however, that they do not necessarily provide nontrivial regret bounds for situation in which the stochastic and the adversarial regimes are mixed, i.e., an intermediate situation.
To overcome this BOB limitation, our work focuses on an intermediate (and compre- hensive) regime between the stochastic and adversarial settings. More specifically, we consider the adversarial regime with self-bounding construint introduced by Zimmert and Seldin [2021 As shown by them, this regime includes the stochastic regime with adversarial corruption Lykouris et al., 2018 Amir al. [2200] 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 parame- ter referred to the corruption level. For expert problems in the stochastic regime with adver- sarial corruption, AAmir et al. (020) have shown that the decreasing Hedge algorithm achieves O log A + -rerggett. For the MAB problem. Zimmert and Seldin 2021 have shown that Tsallis-INF
achieves ( ( A + CN CN
log
--regret in adversarial regimes with self-bounding constraints. To
be more precise, they have proved regret upper bound of O log where i E [N] is the optimal action and A; represents the suboptimality gap for each action i E [M] \ { Ito (202Ib) has shown that similar regret bounds hold even when there are mul- tiple optimal actions, I.e., even if the number of actions i with A; 0 is greater than 1. In such cases, the terms of Eign 1/A, in regret bounds are replaced with Et,, >0 A. In addi- tion to this, Masoudian and Seldin [202T] have improved the analysis to obtain a refined regret
VC 1
A;
1
bound of (Eifir 2.) log
[ (Eie 22 )
1N-
Vc /( 2.)
log+
(N-1)T 1)T Chier 37
where
log,, (I) max (1, (1,log=).
The contributions of this work are summarized in Table [ alongside previously reported results. As shown in Theorems and this paper provides an improved regret upper bound of O Nog
Clog for the expert problem in the adversarial regime with self-bounding constraints. This regret upper bound tight up to constant factor. In fact, we provide a matching lower bound in Theorem In addition this, we show an Ω N CN -loeer bound for MAB, which implies that
Note that Amir et al. 2020] adopt different definition of regret than in this paper. Details and notes for comparison discussed in Remark

---

ISsllis-INF by Zimmert and Seldin [202]] achieves a nearly optimal regret bound up to an Ollog T) factor in the adversarial regime with bounding constraints.
The regret bounds in Theorems 3 and are smaller than the regret bound shown by Amir et al.
[2020] for the stochastic regime with adversarial corruption, especially when C' = Q Log ), and they can be applied to more general problem settings in the adversarial regime with self- 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 '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 sense, stronger than theirs, as is discussed in Remark of this paper. In particular,
we would like to emphasize that the new bound of O A
provides the first theoretical evidence implying that the corresponding algorithms are more robust against adversarial corruption than the naive Follow-the-Lesee tight as long as the former regret definition used.
N. + /Clg
algorithm. Note also that the regret bound by Amir et al. [2200] is
This work shows the tight regret upper bounds for two types of known algorithms. The first, (Theorem 33. is the decreasing Hedge algorithm, which has been analyzed by |Amir al. [2020) and Mourtada and Gaiffas 2019] as well. The second (Theorem (4) represents algorithms with
2007 Gaillard al. 2014 Hazan and Kale, 2010 Steinhardt and Liang, 2014 Luo and Schapire, 2015 It is worth mentioning that Gaillard et al.
second-order regret bounds Cesa- et al.,
[2014] have shown that a kind of second-order regret bounds implies O log }-regret in the stochastic regime. Theorem in this work extends their analysis to a broader setting of the adversarial regime with self- eeff-bounding constraints. In the proof of Theorems [3 and 4 we follow a proof technique given by Zimmert and Seldin [2021] to exploit self- eeff-bounding constraints.
To show regret lower bounds in Theorems 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 nearly-tight lower bound in MAB up logarithmic factor in I' (Thcorem 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 [202]] is tight up to a constant f'ccoor.
2 Related work
In the context of the expert problem, studies on stochastic settings seem be more limited than those on adversarial settings. De Rooij et al. (2014) have focused on the fact that the Follow-the- Leader (FTL) algorithm works well for 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 Vrs- (in Pt las- )2 in place of T and have shown that such algorithm achieves O log )-regret in the stochastic regime. Mourtada and Gaiffas [019) have shown that a simpler Hedge algorithm with decreasing learning
rates of = Ø(v log N 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 log N + C'e-reret in the stochastic regime with adversarial corruption. For online linear optimization, a generalization of the expert problem, HHang 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 [aaii ct al. (2014).
For MAB, there are a number of studies on bost-of-both- worlds algorithms Bubeck and Slivkins
2012 Zimmert and Seldin [022 Seldin and Slivkins 2014 (Seldin and Lugosi| [011 Pogoo and
Pogodin
Lattimore 2020 Auer and Chiang [016 Wei and Luo 2018 Zimmert et 2019
et al. 2021 Ito 2021b). Among these, studies by Wei and Luo| 20188, Zimmert and Seldin [202]] Zimmert et al.
[2019] are closely related to this work. In their studies, gap-dependent regret bounds in the stochastic
regime are derived via (p:) ( -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. 22000)
3

---

Studies on online optimization algorithms robust against adversarial corruption have been extended
variety of models, including those for the multi- armed bandit [Lykouris al. 2018 Gupta et
2019 Zimmert and Seldin 2021 Hajiesmaili et al. 2020). Gaussian process bandits |Bognnviic
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. 202 Lee et al.
2021]. Literature can also be found
regarding effective attacks on bandit algorithms [Jun et al. 2018 Liu and Shrofi 2019).
As summarized by Hajiesmaili 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
al. [2018). Gupta al. (2019), [Bounnviic et al. [2020]) the
attacker may corrupt the losses & after observing 44 Pt. without knowing the chosen action 2, while, in the latter (e.g., in studies by Jun et al. (0088) Hajiesmaili et al. [2020). Liu and Shrofi (2019).
Bogunovic et al. [202T], Ito [021aa, |rrez
and Koren [2021]) the attacker can choose corruption
depending on (fe. Pt, it) We discuss differences between these models Section This work mainly focuses 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 L
as well as achieving best-of-both-worldd.
3 Problem setting
player is given N, the number of actions. In each round = 1,2,... the player chooses a probability vector Pt (pr Pray............................ P.N) E [0, 1| |lpli 1), and then the environment chooses loss vector & (Le1, 42..... LeN)
10. In the expert problem, the player observe all entries of & after outputting Pt. By way of contrast, in the MAB problem, the player picks is w.r.t, Pt. i.c., chooses i, that Probfi: rlpp] Pts, and then observes lua The performance of the player measured by means of the regret defined in I..
Note that in MAB problems we have
T (e - kxx))
E
Σ (la, (ca,- Cxs+)
E
Σ
= RTi
(2)
under the assumption that &, is independent of it, given Pt.
This paper focuses environments in the following regime:
Definition 1 (Adversarial regime with a self-bounding constraint Zimmert and Seldin 2021 D. We say that the environment is in an adversarial regime with a (i*, A, C,T) self-hounding constraint
T
T
RIV = E
E lxs.)
A
Σ
- (1-pss)
C
(3)
holds for any algorithms, where E [0, 1] and C 2
In this paper, we deal with the situation in which the player is not given parameters (,,A,C,T), The regime defined in Definition includes the following examples:
Example (Stochastic regime). Suppose l E 10, follows an unknown distribution D over ii.d. for & E
Denote = Be-D[(], and let 1" E arg min /4 and A mingg (14- - p.+). The environment is then in the adversarial regime with self-bounding constraint (3) with
O. Note here that A > implies that the optimal action is unique, i.e..
M4 > m.- holds for any action i E [N] {i*).
we set = 1 and C = 2T, for any i' E [N] and for any algorithms,, arbitrary loss sequences {4.7=1 S [], satisfy ( This means that the (purely) adversarial environment will be in the adversarial regime with a (i", T,2T, T) self-hounding constraint for any i* E [N] and T.
Example (Adversarial regime).
Example 3 (Stochastic regime with adversarial corruption). Suppose 4, E [0, is given as follows: (i) a temporary loss & E [0. 1J is generated from an unknown distribution D (i.i.d. for and (ii) an adversary corrupts f after observing Pt to determine & subject to the constraint of

---

E'
C. As shown in Zimmert and Seldin 2021). this regime satisfies ( L.., is special case of the adversarial regime with sell-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 (T regret w.r.t. losses without corruption, i.., RT:- = Σ (4, pt - p.--)) ) (Rt'y., and Ry can also be defined 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 's prediction is itself corrupted, the player's performance should be evaluated in terms of the regret Ry, as the consequential prediction performance is determined by the losses l after corruption, not by é. In contrast, if only the observation of the player is comupted, the performance should be evaluated in terms of R/y-
We can easily see that [R/v-- - RT-- I 2C' Amir et al. [2200] have shown a regret bound of =0(Lor
Py = =0 Log + C). which immediately implies Rr = O log + C). Similarly, a regret bound
of RT = O log + Clog A
immediately implies Rt = O log N
cc. In fact, from the
AM-DM inequality, we have
log N
C'log N
log N
1 C
log N
0 <c+ log N A
A
A
2
A
Note here that the former bound of Ry
O
log N
is properly stronger than the latter
of RG. = O log N
+ c). as the latter does not necessarily imply the former.
A
Remark 2. In MAB, targeted corruption model has been considered to be variant of the model in Example 3 In this model, the adversary corrupts the losses after observing 4. In this case, the loss 4 after corruption and i, are dependent given pt, and hence (2) does not always hold.
4 Regret upper bound
4.1 Known regret bounds for adversarial regimes by hedge algorithms
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 [1944) is known to be mini-mat max optimal algorithm for the expert problem. In the Hedge algorithm, the probability vector Pt is defined as follows:
1-1
W
Wti = exp (- Tht
Pr
(4)
j=1
where 7/2 > 0 are learning rate parameters. If P. is given by ④ the regret is bounded as follows:
Lemma 1. If {pr)T= is given by (4) with decreasing learning rates (i.e., Mi 2 qe+1 for all t), for any (T) and i" E [N]. the regret is bounded as
log N
(---1) H Honeii)
RT S
Σ
pag (ni(-Lu aa))
az))
(5)
711
1141
1h:
for any {at)T= C IR, where g and H are defined as
1
g(ø) exp(x) 1, H(p) Σ pi log
(6)
pi
From this lemma, using g(x) 12 and (p) < log N, we obtain the following regret bounds for adversarial settings:
Theorem (Theorem 2.3 in [Cea- Bianchi and Lugosi 2006)). If Pe is given by 44 with me
8 log N for any T. i [N] and (4.) C [0, 1 the regret bounded as RTy /2T
21 log N + N/8.
5

---

). as in Theorem are referred to as decreasing Hedge, e.g., in (Mourtada and Gaiffas 2019). Such algorithms shown by Mourtada and Gaiffas 2019 achieve O( Nog -regret in stochastic regimes, and are also shown, by Amir
Hedge algorithms with decreasing learning rates 1/2 = O ,
et al. 2020], to achieve OVv log N
reeggettt stochastic regimes with adversarial corruption.
Besides such worst-case regret bounds as found Theorem a variety of data-dependent regret bounds have also been developed (see, e.g., (Steinhardi and Liang 2014]). One remarkable example that the second-order bounds by
et al. 2007 which depend on parameters Vi
defined as follows:
T (lu - p.)?, VT Σ 1=1
Σ
2t- t=1
(8)
A regret bound depending Vr rather than T can be achieved wih the following adaptive learning rates:
Theorem (Theorem 5 in (Cesa-Bianchi et al. 2007]). If Pt is given by with, 7
min
1
2(v N ( 2)-
the regret is bounded as
RTV S 4v VT log N + 2 N + 1/2
for any T, i" and (4))=1 S 10,
As VT < follows from the definition 8 the regret bound in ( includes the worst-case regret
bound of Ri-- O(y WivTTo Tog. J). Further, shown in Corollary 3 of (Cesa-Bianchi al. 2007
the bound in Theorem 2 implies Ris = O(v Lae (T-Lr=)) log N), where LTv- = Σi= bes. This means that the regret will be improved if the cumulative loss LTx- for optimal action 8 is small or is close to T.
T
4.2 Refined regret bound for decreasing Hedge
This subsection shows that the algorithm described in Theorem @ecoremmenjorr enjoys the following regret bound as well:
Theorem 3. If Pt is given by with YJ 8log
we have
Riy S 100 log N
Clog N
10
(10)
under the assumption that holds.
Proof. Using the fact that g(x) < (e-1) 1)x²
for x < 1 and H(p) I (1-p:))(1+ogg - -og([1 loollogl1pp 1 -p:-))
2
from Lemma]
I we obtain
Pti Vt
12 N + log 1
Rie < 9log N
(11)
4 N
Pti
proof for 11) can be found in the appendix. From
33 and (1). D. for any X O, we have
Ris- (1 A) - ABrr-
E (1 2) 9log N +
Σ
T
Pei
12
N + logg 1- prs
1-pte- )) - ( T
1.-
) -
(1 (1-pti)) -c)
4vlog N
Vi
t=1
t=1
9(1 + log N + XC + 4vlog
1+1
E
T
-
Pt
12llg
4AA MAAtlogg N
log(1 pri-) p2:t)
V1
1+>
[=1

---

To bound the values of the expectation, we use the following inequality
T Ft
2a +
Σ 1=1
Vi
a
bv -log S
(12)
which holds for any a, T and {ar]==1 S (0, A proof of (12) is given in the appendix.
Combining the above two displayed inequalities with = 12 12g N and b = 4AAvlog
we obtain
1+A
1+
1+
4AA N
AC + 4vlog N Ri-- - 9(1 AC
(2(12log.N) + 1)
4AA AlAvlog! N
1+1
(1 + A)2
1
=9(1 + log N + XC
18(1og N)²
+
λA lAlogN
16
38 log N
19 log N
19 log N
< log N +
+ 9log N +C+
+
A
By choosing
19 19 A
19 19 (9log C++
we obtain
A
RTV. S 19log N + +A+
38 38log N
/
(9log C+
19 19 N
19 19 N
A
A
38 log N
log N
19C'log
< <olog N +++++++
+ 2
532
A
A
log N
C C'log N
log N
Clog N
9 log N + A + (38 + 2v 532)
+ 2v 19
I 100
+ 10
A
A
where the third inequality follows from /x + y S V + /y for x. 22
Combining Theorems
andd
we can see that the decreasing Hedge with 17:
8 N achieves
log N)) in the adversarial regive with self- boffdinnn con- straints. This bound will be shown to be tight up to constant factor in Section
Bre- = Ominn NogN
log A
A
4.3 Refined regret bound for adaptive Hedge
In this subsection, show that second-order regret bound seen in Theorem 2 implies tight gap-dependent regret bounds in the adversarial regime with self-bounding constraint.
We start from the observation that ii defined in (8) satisfies vs I (1 Pts-) ) for any i In fact, we N
have v. Eiz Pra(ee - ai² for any a E IR the right-hand side is minimized when a E Pt
from which it follows that
N
U/2 S Σ
(er - )
Σ (E(NIV(O))
Priles - 22
Σ
=== 1 Prr
(13)
(E(
Hence, the regret bound in Theorem implies
T Bry S 4 log N Σ pre)) + 2og N + 2
(14)
leads to a tight gap-dependent regret bound, as Such regret bound depending on Σt= (1 P(s))
shown in the following theorem: Theorem 4. Suppose that the regret is bounded as
Rrr S
p(s-) ) + B.
(15)
7

---

Then, under the condition of 33. the pseudo-regret is bounded as
A(B + C)
RTT. S + BB+
(16)
A
Proof. From
15 and 3 for any À > O we have
RT- = (1 + X) RTV ARTi-
T
- c
< E 11+
A A 1=1
pa-) +B - -
A
(1
-
P
t=1
A(1 + x)
A
1 A
A
+ (1+ A)B + XC' =
+B +
+1
+
41A
2A
A
4A
where the second inequality follows from a a/ bu -b(v
26
+
a²
16
a²
for 0, b
and x 2 O. By choosing
V
4
)/(
B + C) we obtain
A
A
A
A +
A
2
A(B C)
Riv
<
+
+ +2
+
2A
4A
4A
2A
A
A
A(B + C)
A
A(B + C)
<
+
B
+
+
+
2A
2A
A
A
A
where the second inequality follows from v + y S Vr vy for y, 20
Combining this theorem and (1)). we obtain the following regret bound for the algorithm described in Theorem 2
Corollary 1. Pf is chosen by with 1jp = min
2(v2 log N (e- (e-2)V; }. under the condition of 33)
the pseudo regret is bounded as Rer & log A + 4v 33 N+C) log +3log N.
Theorem 4 can be applied to algorithms other than the one in Theorem 2 One example is an Corollary of their paper, a regret bound of RTV- S
algorithm by Gaillard et al. (2014).
C log Ex=((Tp - lx.. )a + C2 is provided. Then, as it holds that (e, p: - la-)² < Pas
we have 15 with appropriate A and B, and, consequently, we obtain the regret bound given in (16).
5 Regret lower bound
This section provides (nearly) tight lower bounds for the expert problem and the MAB problem the adversarial regime with self-bounding constraint. Let begin by describing the statement for the expert problem:
Theorem 5. For any A E 10,1/4), 2 T llgg CZ O, and for any algorithm for the expert problem, there exists environment in the adversarial regime with a (i" M,A,N,C, self-bounding constraint for which the pseudo-regret is at least
log N
Cloog N A
v T Tlog }
RTV =Q
min
+
(17)
To show this lower bound, we define a distribution DA over {0. 1 for A E (0, and 1" E [N], as follows: if & ~ DA. ls- follows Bernoull distribution of parameter 1/2 A, i.e.,
Prob 2,- = 1 = 1/2 - A and Prob/e;- = 0] = 1/22 + A, and & follows a Bernoulli distribution of parameter 1/2 for i [M] i*, independently. We then employ the following lemma:
Lemma 2 (Proposition 2 in [Murtada and Gaiffas 2019). For any algorithm and for any A E (0, 1/4), N 2 4 and T
log N AT
there exists i" such that RT
log holds for (L.)T= DTT
2563
8

---

Using this lower bound, we can show Theorem 5
Proof of Theorem 5
We show lower bounds for the following four cases:
(i)
If < N
A
Ri- D(V Tlog. loggNN
(i)) If
C
I log
I T. RT:- Q No
(ii)
log If
A S
I
T.
RTr- V Cloog N
(iv) If log N
S
S
C Rr. = OovTlog N). Combining all four cases of A
A
A²
(iv-iiv), we obtain 17
(i) Suppose T < Nog A. Set A'
log N T
We then have T log N T and A < A S 1/4. If
4 ~ D for all t E [T], the environment is then an adversarial regime with a (i*, A, N, C,T) self-bounding constraint for any C' 2 0, and the regret is bounded as Ry.- 2 from Lemma 2
log
(V (TVVooo N)
256A
(ii) Suppose C for some i* from Lemma
A E N A
T. 1f ~ Da. for all & [T], the regret is bounded as RTV- 2 250A
2
The environment is then in an adversarial regime with (i", A, N, C,T)
self-bounding for any C
2 0.
(iii) Suppose
C
< T.
Define A'
< A. We then have log A'
v Clogg log
A
A
Let T = log
[ < T. Consider an environment in which & ~ Da for E [T'] and
A
=
4 ~ Da for E (T' +1, TJ. Then from Lemma there exists i" E [N] such that RT 2 RT 2 show that the environment is in adversarial regime with (i', C, self-bounding constraint. In fact, we have (A A { A') S C.
log N S2(
log N
Further,
A
(iv) Suppose log N <T Set A' = log N and consider & D for all t [T]. The regret T
then bounded as RT: 2
log
Tog N) for some i", from Lemma We can confirm that
25627
the environment is in an adversarial regime with (i", A, N. C, C) self-bounding constraint, as
have AT AT < C, where the first and second inequalities follow from respectively.
log N
A < T and T <
Via 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 A E 10,1/4), N 4,72 4log N. C and for any multi-armed bandit algorithm, there exists an environment in the adversarial regime with a (i*, A, N,,, C,T) self-bounding constraint for which the pseudo-regret
least
N
CN
RT-- Ω
min
A V
+
(18)
A
We can demonstrate this theorem by means of the following lemma:
Lemma 3 ([Auer et al., (002b)). For any multi-armed bandit algorithm and any A (0,1/4),
N and T AT, there exists i such that RT N holds for (Lx)²= DJ.
complete proof of Theorembeent be found in the appendix.
Discussion
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(VC (CCR))ttem characterizes optimal robustness against corruption.
One natural question is whether such O(R+ / CCR)-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 ORR VCR))regree 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 202 What these algorithms have in common is that they use

---

framework of Follow-the-Reeee Leader with decreasing learning rates and that they achieve the sitl-fffooth-wolllee simultaneouslyy. As Amir al. (2020) suggest, online mirror descent algorithms does not have O(R+ + -Cegetreget bounds, in contrast to the Follow-the- www-tthheRRRuiieeee Leeearrized-Lederr case. We believe that characterizing algorithms with O reeret bounds will be important for future work.
Another question is whether we can remove the assumption that the optimal action is unique. This assumption required for the analysis of most algorithms with O v -regget 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 [tt|] [2021b] 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 algo- rithms and includes a discussion 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 JPMJPRI8U5, Japan.
References
I. Amir, I. Attias, T. Koren, Y. Mansour, and R. Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 2020.
Arora, E. Hazan, and S. Kale. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 811):12 2012.
J.-Y. Audibert and Bubeck. Minimax policies for adversarial and stochastic bandits. In Conference on Learning Theory, pages 217-226, 2009.
P. Auer and C.-K. Chiang, An algorithm with nearly optimal pscudo-regret for both stochastic and adversarial bandits. In Conference on Learning Theory, pages 116-120. PMLR, 2016.
P. Auer, N. Basachianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235-256, 2002a.
Auer, Cesa-Bianchi, Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing. 32(1):48-71) 2002b.
I. Bogunovic, A. Krause, and J. Scarlett. Commptiion-tolerant gaussian process bandit optimization. In International Conference on Artificial Intelligence and Statistics, pages 1071-1081. PMLR, 2020.
I. Bogunovic, A. Losalka, A. Krause, and J. Scarlett. Stochastic linear bandits robust to adversarial attacks. In International Conference on Artificial Intelligence and Statistics, pages 991-999. PMLR, 2021.
S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference on Learning Theory, pages 42.1-42.23, 2012.
N. Resa-Bianchh and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
N. Cesa-Bianchi, Mansour, and G. Stoltz. Improved second-order bounds for prediction with expert advice. Machine Learning, 66(2):321-352, 2007.
Y. Chen, Du, and K. Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. In International Conference Machine Learning, pages 1561-1570, 2021.
10

---

S. De Rooij, T. Van Erven, P. D. Grünwald, and W. M. Koolen. Follow the leader if you can, hedge if you must. The Journal of Machine Learning Research, 15(1):1281-1316, 2014.
R. Degenne and Perchet. Anytime optimal algorithms stochastic multi-armed bandits. In International Conference Machine Learning, pages 1587-1595, PMLR, 2016.
L. Erez and T. Koren. Best-of-all-worlds bounds for online learning with feedback graphs. In Advances in Neural Information Processing Systems, to appear, 2021.
Y. Freund and E. Schapire. decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1): (5(1):19-1133 19-139, 1997.
Gaillard, G. Stoltz, and T. Van Erven. second-order bound with excess losses. In Conference on Learning Theory, pages 176-196. PMLR, 2014.
A. Gupta, T. Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
M. Hajiesmaili,, M. S. Talebi, J. Lui, W. S. Wong, et al. Adversarial bandits with corruptions: Regret lower bound and no-regret algorithm. Advances in Neural Information Processing Systems, 33, 2020.
E. Hazan and S. Kale. Extracting certainty from uncertainty: Regret bounded by variation costs. Machine Learning, 80(2-3):165-188) 2010.
R. Huang, T. Lattimore, A. György, and C. Szepesvári. Following the leader and fast rates in linear prediction: Curved constraint sets and other regularities. In Advances in Neural Information Processing Systems, pages 4970-4978, 2016.
S. Ito. Hybrid regret bounds for combinatorial comi-bandits and adversarial linear bandits. In Advances in Neural Information Processing Systems, to appear, 2021a.
S. Ito. Parameter- free multi-armed bandit algorithms with hybrid data lata-dependent regret bounds. In Conference on Learning Theory, pages 2552-2583. PMLR, 2021b.
Jin, L. Huang, and H. Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. arXiv preprint arXiv:2106.04 04111.066111,,1.1 2021.
K.-S. Jun, L. Li, Y. Ma, and X. Zhu. Adversarial attacks stochastic bandits. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3644-3653, 2018.
T. L. Lai. Adaptive treatment allocation and the multi-armed bandit problem. Annals of Statistics, 15 (3):1091-1114, 1987.
T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4 22, 1985.
Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
C.wW. Lee, H. Luo, C.-Y. Wei, M. Zhang, and X. Zhang. Achieving near instance-optimalle and minimax-optimality in stochastic and adversarial linear bandits simultancously. In International Conference on Machine Learning, pages 6142-6151, 2021.
Y. Li, E. Y. Lou, and L. Shan. Stochastic linear optimization with adversarial corruption. arXiv preprint 1909iv9990.00 0009002109 2019.
N. Littlestone and M. Warmuth. The weighted majority algorithm. Information and Computation, 108(2):212-261, 1994.
F. Liu and N. Shroff. Data poisoning attacks on stochastic bandits. In International Conference on Machine Learning, pages 4042 4050. PMLR, 2019.
H. Luo and F. Schapire. Achieving with no parameters: Adanormalhedge. In Conference on Learning Theory, pages 1286-1304. PMLR, 2015.

---

T. Lykouris, V. Mirrokni, and R. Paes Leme. Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Anmual ACM SIGACT Symposium on Theory of Computing, pages 114-122, 2018.
T. Lykouris, M. Simchowitz, A. Slivkins, and W. Sun. Corruption-rouust exploration in episodic reinforcement learning. In Conference on Learning Theory, pages 3242-3245. PMLR, 2021.
Masoudian and Y. Seldin, Improved analysis of the tsallis-inf algorithm in stochastically constrained adversarial bandits and stochastic bandits with adversarial corruptions. In Conference Learning Theory, pages 3330-3350. PMLR, 2021.
J. Mourtada and S. Gaïflas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20:1-28, 2019.
R. Pogodin and Lattimore. On first-order bounds, variance and gap-dependent bounds for adver- sarial bandits. In Uncertainty in Artificial Intelligence, pages 894-9044 2020.
A. Sani. G. Neu, and A. Lazaric. Exploiting easy data in online optimization. In Advances in Neural Information Processing 27, 2014.
Y. Seldin and G. Lugosi. An improved parametrization and analysis of the exp3++ algorithm for stochastic and adversarial bandits. In Conference Learning Theory, pages 1743-1759, 2017.
Y. Seldin and Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference on Machine Learning, pages 1287-1295, 2014.
J. Steinhardt and P. Liang. Adaptivity and optimism: An improved exponentiated gradient algorithm.
In International Conference on Machine Learning, pages 1593-1601. PMLR, 2014.
C.-Y. Wei and Luo. More adaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291, 2018.
J. Zimmert and Y. Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1-49, 2021.
J. Zimmert, H. Luo, and C.-Y. Wei. Beating stochastic and adversarial semi-bandits optimally and simultaneously. In International Conference on Machine Learning, pages 7683-7692. PMLR, 2019.
12


Reviews:
[{"review_id": "so3_7kenod", "reviewer": "Reviewer_M84b", "summary": "This paper considers the online decision problems with corruptions and provide upper bounds on the regret of the Hedge algorithm and lower bounds for any algorithm.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper presents quite a rich amount of contents, but there seems to be lack of clear discussions. My major concerns are as follows:\n1. In the abstract, it states that this work will study the problem of prediction with expert advice and the multi-armed bandit problem. However, somehow I failed to find the results of the problem of prediction with expert advice.\n1. Definition 1 introduces the self-bounding constraint. Though this is implied by Zimmert and Seldin [2021], I think that some discussion on the motivation and the interpretation of this definition would be appreciated.\n1. This work reviews the existing literature on corruptions, best-of-both-work algorithms and so on. However, I failed to find what is the focus of this work.\n1. There are a bunch of theoretical results in this work, but somehow I cannot easily tell what is the specific problem (stochastic/adversarial? with or without corruption?) the result in each section is for. I think more discussions would be appreciated.\n1. Furthermore, some experiments to show the regret of the algorithm (maybe the Hedge?) grows as shown in the upper/lower bounds would make the results more convincing.\n1. Among the many results, is there any analytic challenge?\n\n=====================================\n\nThanks you for your response.\n\nMost of my concerns are solved. However, as claimed in the feedback, the results hold for any instances satisfy Definition 1. This suggests that some existing results should be comparable to your work. May you include some comparisons and discussions among the theoretical results in the paper? Numerical comparison is also appreciable but I understand that can be time-consuming.\n\nAnyway, I would like to increase my rating to 6 for the time being.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "More discussions on the results may make the big picture and the focus of this paper clearer.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "TWLl4o6yJz3", "reviewer": "Reviewer_sGi4", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThe paper studied an important problem: stochastic online decision making with adversarial corruption. Many recent works focused on this line of research. The key contribution is the refined regret analysis of Hedge algorithms for expert problem and multi-armed bandit problem under corruption. It is interesting to see that in both settings, the regret has a $\\sqrt{C}$ dependency to the corruption level. Another contribution is the lower bound of the two problems, showing the analysis is (near) optimal. \n\nOne thing to note is that the regret definition in this paper is based on losses after corruption. The authors explained the difference from defining regret based on losses before corruption and analyzed the regret difference in Remark 1.\n\nConcern:\n\nI do not have significant concerns about the paper. One comment is that the authors may want to discuss the technical novelty in Theorem 3 comparing with Amir et al. 2020, since both papers analyzed Hedge algorithm with $\\eta_t = O(\\sqrt{\\log N / t}) learning rate. The authors already provided a comparison on the regret bounds in Remark 1; it would be better to provide more explanation on how the stronger result is achieved.\n\nQuality and clarity:\n\nThe writing is clear. The related works are thoroughly discussed. The theoretical analysis looks sound to me although I did not check every step of proof.\n\nReferences:\nI. Amir, I. Attias, T. Koren, Y. Mansour, and R. Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33, 2020.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed the limitations and potential social impact of the paper.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "NgdCCHHKbT", "reviewer": "Reviewer_Kpdi", "summary": "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.       ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n- Theorem 3 and Theorem 4 are new bounds for already existing algorithms for the expert advice problem. \nThe analysis of these two theorems consist of two key steps:  1) Providing upper bound for the regret in terms of probabilities played by the player. 2) Combining this upper bound with the self-bounding constraint. \nLemma 1 in the paper provides the first step for the proof of Theorem 3  that I believe this is almost same bound as Lemma 6 of Amir et al., (2020). Also Theorem 2 in the paper (Theorem 5 of Cesa-Bianchi et al., (2007)) provides the first step for the proof of Theorem 4. The second step, which I think is the most important step, follows the same idea and steps provided by ZS21 for the analysis of Tsallis-INF algorithm for MAB problem that combines self-bounding constraint to their provided upper bound. Hence, I think the novelty is questionable here since the main contribution of these Theorems is applying ZS21 idea to combine the existing upper bounds and self-bounding constraint.   \n - Theorem 5 and Theorem 6 provide lower bounds for the regret in expert advice and MAB problem. In spite of the fact that the example construction provided for lower bound is similar to the prior works but the inference steps for the intermediate regimes seems interesting.\n\nQuality:\n- There are many minor issues and small bugs in the proofs but after reading the details of the proofs, finally found out they are technically sound.  I noticed small bugs in the analysis steps of the regret upper bounds, Mostly in Theorem 3, but they won't change the order of the regret bounds however they still affect the constants factors in the regret bounds. Generally I suggest that the authors revise the equations at the end of page 6 and page 7 and also construction of example for lower bound in page 8.\n\nClarity: \n- The writing is generally clear. However reading the proofs takes too much energy from a reader since in many equations the intermediate steps are missing. \n- There are some small typos and grammatical issues throughout the paper.\n\nSignificance:\n- As it is mentioned in the paper there is a work by Amir et al., (2020) that studies the expert advice problem with adversary corruptions and give linear regret on the _original version of losses_ w.r.t. total amount of corruption. However, there is no regret bound on the _corrupted version of losses_ and this paper gives a the tight one for this. So the result on expert advice problem seems significant to me but I would still like to see some motivating examples and practical real world examples of such problems.\n- The multi-armed bandit part of paper has no important significance since the provided lower bound have quite naive construction and doesn't match completely with the state-of-the-art result by ZS21. \n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n- As I mentioned earlier, the analysis of the paper follows the ZS21 approach. The main drawback of ZS21 in analyzing Tsallis-INF algorithm was that their analysis technique relies on the uniqueness zero entry (i*) of the self-bounding constraint. One of the important open problem followed by ZS21 is to remove this assumption. This paper also implicitly have the same assumption in their analysis so the authors must clearly state this issue in the paper. \n\n- Two notions of regret have been expressed in the paper: 1- Regret on original version of losses, 2- Regret on corrupted version of losses. It is clear that the regret bounds with these two notions are not comparable but in Table 1 the regret bound by Amir et al., (2020) is compared to the results of Theorems 3 and 4. At least the notions of regret used for evaluation must be represented clearly in the table.\n\n- In MAB problem the authors compare their provided lower bound to ZS21 result, however, recently ZS21 result was improved by a paper titled: \"Improved Analysis of Robustness of the Tsallis-INF Algorithm to Adversarial Corruptions in Stochastic Multiarmed Bandits\" (Masoudian and Seldin, 2021).  So it is better that the authors compare their lower bound with the improved result. \n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "JfZfrp57-tc", "reviewer": "Reviewer_8E6J", "summary": "This paper study the expert problem and multi-armed bandit problem in the adversarial regive with self-bounding constraints. Compared to prior work, this paper provides tight lower-bound for both problems and refined upper-bound for the expert setting, achieving matching upper and lower bounds in both settings up to constant and logT factors respectively.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper nearly closes the theoretical gap between the upper and lower bounds in both problems mentioned above, effectively solved these two problems to completion. The presentation is clear and the analysis is intuitive. It is obviously above the acceptance threshold of the conference.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously support acceptance of the paper.
Decision: Accept (Poster)