Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs
Authors: Shinji Ito
Taira Tsuchiya
Junya Honda
Venue: NeurIPS 2022 Accept (2022)
Keywords: multi-armed bandit
learning with feedback graphs
best-of-both-worlds algorithm
follow the regularized leader

Abstract: This study considers online learning with general directed feedback graphs. For this problem, we present best-of-both-worlds algorithms that achieve nearly tight regret bounds for adversarial environments as well as poly-logarithmic regret bounds for stochastic environments. As Alon et al. [2015] have shown, tight regret bounds depend on the structure of the feedback graph: strongly observable graphs yield minimax regret of $\tilde{\Theta}( \alpha^{1/2} T^{1/2} )$, while weakly observable graphs induce minimax regret of $\tilde{\Theta}( \delta^{1/3} T^{2/3} )$, where $\alpha$ and $\delta$, respectively, represent the independence number of the graph and the domination number of a certain portion of the graph. Our proposed algorithm for strongly observable graphs has a regret bound of $\tilde{O}( \alpha^{1/2} T^{1/2} )$ for adversarial environments, as well as of  $ {O} ( \frac{\alpha (\ln T)^3 }{\Delta_{\min}} ) $ for stochastic environments, where $\Delta_{\min}$ expresses the minimum suboptimality gap. This result resolves an open question raised by Erez and Koren [2021]. We also provide an algorithm for weakly observable graphs that achieves a regret bound of $\tilde{O}( \delta^{1/3}T^{2/3} )$ for adversarial environments and poly-logarithmic regret for stochastic environments. The proposed algorithms are based on the follow-the-regularized-leader approach combined with newly designed update rules for learning rates.

Nearly Optimal Best-of-Both-World Algorithms for Online Learning with Feedback Graphs
Shinji Ito NEC Corporation, Tokyo, Japan RIKEN AIP, Tokyo, Japan E-shinji@nec..
Taira Tsuchiya Kyoto University, Kyoto, Japan
RIKEN AIP, Tokyo, Japan
tsuchiya@sys. wtt.:/aaasss......ooooooo ac..
Junya Honda
Kyoto University, Kyoto, Japan
RIKEN AIP, Tokyo, Japan honda@i handa@i.kytoo-u ac.
Abstract
This study considers online learning with general directed feedback graphs. For this problem, we present best-of-both-wordds algorithms that achieve nearly tight regret bounds for adversarial environments well as poly-logarithmic regret bounds for stochastic environments. As Alon et al.) [2015] have shown, tight regret bounds depend on the structure of the feedback graph: strongly observable graphs yield minimax regret of 122//211/2 while weakly observable graphs induce minimax regret of (//1/3/2/3 where and ô, respectively, represent the independence number of the graph and the domination number of a certain portion of the graph. Our proposed algorithm for strongly observable graphs has regret bound of 1(2//11/2 for adversarial enviromments, as well as of O alln T)²) for stochastic environments, where Amin expresses the minimum suboptimality gap. This result resolves open question raised by Erez and Koren [021]. We also provide an algorithm for weakly observable graphs that achieves a regret bound ( for adversarial environments and poly-logarithmic regret for stochastic environments. The proposed algorithms are based on the follow- theerrgullrized--eet approach combined with newly designed update rules for learning rates.
A
Introduction
In this paper, consider online learning with feedback graphs [Mannor and Shamir
201
common generalization of the multi-armed bandit problem [Li et al. 1985 Auer et al. 2002a and the problem of prediction with expert advice [Littlestone and Warmuth 1994 Freund and Schapire 1997]. This problem is sequential decision-making problem Formulated with directed feedback graph G (V, E), where V [K] = 21, 2........ K) is the of arms or available actions, and E C V x V represents the structure of feedback for choosing actions. In each round of 1, 2......
player sequentially chooses an action I, V and then incurs the loss of (It). where f : V + [0, 1] is a loss function chosen by the environment. After choosing the action, the player gets feedback of (i) for j such that the feedback graph has an edge from I, j. G consists of only self-loops, i.e., if F (ii,)) E V}. the problem corresponds to K -armed bandit problem.
a complete directed graph with self-loops, i.e., F. V x V. then the problem corresponds to problem of prediction with expert advice.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Alon et al. [2013] have provided characterization of minimax regrets for the problem of online learning with feedback graphs. They divide the class of all directed graphs into three categories. For the first category, called strongly observable graphs, the minimax regret is ((a4/2T1/2) where the independence number of the graph G, and Ô ignores poly-logarithmic factors and K. For the second category, weakly observable graphs, the minimax regret is @(51/372/3) where ó represents the weakly dominating number. For the last category of wnobservable graphs, it is not possible to achieve sublinear regret, which means that the minimax regret is (TT). The definitions of categories of graphs and a and 6 are given in Section
Best-of- worlds (BOBW) algorithms [Bubeck and Slivkins 2012 have been studied for the purpose of going beyond such minimax regret bounds; they achieve sublinear regret for adversarial environments and, as well, have logarithmic regret bounds for stochastic environments. The only BOBW algorithm for online learning with feedback graphs has been proposed by Erez and Koren (02T]. They have focused on the case in which G is symmetric and all vertices have self-loops, i.e., any edge (i,j) E E. is accompanied by its reversed edge (j. E E. and (i, E E for any i V. Note that this is special case of strongly observable graphs. For this class of problems, they provide an algorithm that achieves a regret bound of ((03/2/1122) for adversarial environments, and of O (Doolylo((T) for stochastic environments, where (2 a)) is the clique Amtn
covering number of the graph G, and Amin is the minimum suboptimality gap for the loss distributions. Their algorithm also works well for patrssariaal--oorppptee stochastic environments, achieving
O
Opolylog(T) +
(Gpolyylog(T)
1/2)
-regret, where C' represents the total amount of corruption.
Amin
Amin
As Erez and Koren [021] have pointed out, however, their results leave room for improvement, which is due to the fact that the clique covering number 0 is significantly larger than the independence number a in some cases, Indeed, there an example such that a = while K, as mentioned in Section 3 This means that regret bound depending on 0 is not minimax optimal. In response to this issue, they have raised the question of whether it possible to replace a with their regret bounds. Contributions of this study include positive solution to this question.
1.1 Contributions of this study
This study provides BOBW algorithms that achieve minimax regret (up to logarithmic factors) for online learning with general feedback graphs. Our contributions can be summarized as follows:
Theorem 1 (strongly observable case, informal). For the problem with strongly observable graphs, [a(arr")))
an algorithm achieves Ry = =O(a /2) for adversarial environments, Rr = O [a(ln T)
for
Amin
stochastic environments and RT = O (((nn)" Amin
+ (Calti TTy5) 1/2) ) for udversariialy-coruppee
Amin
stochastic environments, where is the independence number of feedback graphs.
Theorem (weakly observable case, informal). For the problem with weakly observable graphs, an algorithm achieves Rr ((6//312/3) ) for adversarial environments, RT =0 ( (5(m K" In
Amin
for stochastic environments, and R. O
8(uuTT)²
+ +( +c2o(lunr7
-2 1/3 K''nT
(CK' In
1/2
A2
Auin
Amin
min
for udversariiall-corrmppee stochastic environments, where ö is the weakly dominating number of feedback graphs, and K'(S K) is the number of vertices not covered by the weakly dominating set.
Remark 1. The regret bound in Theorem for stochastic environments include an O
K' In
Amin
term, which negligibly small compared to the other term 8(InT)² when is sufficiently large. &lnT However, if K' is larger than Amin' this term can be dominant. In such case, the regret upper bound may be improved by modifying the algorithm. Roughly speaking, by combining the approach to
A2
strongly observable case, the O In ) -term can be replaced with an O
Amis -term, where a' is the independence number of the subgraph consisting of vertices not dominated by the weakly dominating set. If a (In 7)2 < K', the modified version provides a better regret bound. Details of the modification are given Appendix
Amin

---

Table 1: Regret upper bounds for online learning with feedback graphs. Note that regret bounds by Erez and Koren [021] and Rouyer et al. [2022] only apply to a special case of strongly observable graphs with self- self-loops. We also note that the graph consisting only of self-loops, which corresponds to the standard multi-armed bandit problem, is a special case of strongly observable graphs.
feedback graph
reference
adversarial
stochastic
strongly
Alon et al.
2015
Ô (12/271/2)
(2212/122)
observable
Erez and Koren
2021
Ô (01/272122
() Σx k Au Eies ()
Rouyer et al.
2022
Ô (22/221112
A;
[This work] Theorem
Ō (a)121112
allnT) Amio
self-loops only
Zimmert and Seldin
202
O (1112212/2)
Σ Eniiio 0
0
hT A.
(standard MAB)
TTis work]
Theorem
(KK1221122)
K
Amin
weakly
Alon et al.
2015
Ô (011322133
Ô
(6 (6133//33
observable
Kong et al.
2022
Ô (K22381137213)
0
82
(luT)3/2
A3
[This work]
Theorem
Ô 0611312110
0
K' In
min
Amin
Regret bounds for online learning with feedback graphs are summarized in Table [ Note that the regret bounds by Firez and Koren (202T) apply only to the special case of strongly observable graphs that have self-loops for all vertices. Their algorithm and regret bounds are stated with clique cover (V+) of G. which a partition of all vertices V such that each V is clique. The elique covering number 0 of G is the minimum size L of clique covers. Parameters A in Table are defined to be the minimum suboptimality gap among actions in Vs, and the summation is taken over & E [L] such that Ae > 0. As the clique covering number 0 is larger than or equal to the independence number of G. adversarial regret bound of Ô (a (22 for strongly observable cases is superior to that obtained by Erez and Koren [021] and is minimax optimal up to logarithmic factors. Although our stochastic regret bound is also better than one by |Erez and Koren [2021] in many cases, it is not always so. For example, if a = and A min is much smaller than many Ag. their regret may be better. Note that the work by |Rouyer et al. [022]] which proposes BOBW algorithms for strongly observable graphs with self-loops, has been published at NeurlPS 2022, independently of this study. While their algorithms achieve better regret bounds for certain class of problem settings, our results have the advantage of being applicable to a wider range of problem settings, including directed feedback graphs without self-loops and adversarially corrupted stochastic settings. A more detailed discussion can be found in Appendix B
Our study includes the first nearly optimal BOBW algorithm that can be applied to online learning with weakly observable graphs. As shown in Table I the adversarial regret bounds obtained with the proposed algorithm match the minimax regret bound shown by Alon et al. (2015). up to logarithmic factors. Similarly to their algorithm, the proposed algorithm uses a weakly dominating set D C V of G. If D is a weakly dominating set, all elements in the set of vertices not dominated by D, which is denoted by V22 C V, have selfs Parameters 5 and K in the regret bounds are given by 5 = D] and K' 1/2. The stochastic regret bound obtained with the proposed algorithm is also nearly tight. In fact, Alon et al. 2015 have shown regret lower bound of π their paper. Further, vertices in Vz are not connected by edges except for self-loops, the problem is least harder than the armed bandit problem, which leads regret lower bound of 52
in the proof of Theorem 7 in
K' Ia
A Amin
We note that, just before the submission of this paper, Kong et al. 2022 published work on BOBW algorithms applicable to weakly observable graphs, which regret bounds are also included in Table
3

---

1.2 Techniques employed in this study
The proposed algorithms are based on the haallo-the-regulaiizeeee to the algorithms by Alon et al. [2015] and Firez and Koren| [02T]. The main differences with existing methods are in the defnnition of regularization functions and update rules for learning rates.
(FTRL) framework, similarly
For strongly observable cases, we employ the Shannon entropy regularizer functions with a newly developed update rule for learning rates. Most FTRL-based BOBW algorithms are realized by setting the learning rate adaptively and/or observations. On the other hand, is well known that FTRL with Shannon-entropy regularization corresponds to Exp3 algorithm [Auer et al. 2002b] as discussed in, e.g., Lattimoee and Szepesvári (2020) Example 28.3]. Since Exp3.G by Alon et al. 2013 achieves an diependence-numbeee cuumber-dependelt regret bound for adversarial environments, it is intuitively natural to expect that variant of Exp3.G G with adaptive learning rates can be used to achieve BOBW regret bounds. However, from the theoretical viewpoint, it is necessary to express the regret depending on the arm-selection distribution qe to apply the self-bounding technique [Gaillard et al. 2014 Zimmert and Seldin 2021]. which plays the central role in the BOBW analysis.
The proposed algorithm for weakly observable graphs uses novel regularization functions consisting of Tsallis-entropy-ber -raaee and channon-entroopy-aasee regularization. Intuitively, we divide the vertices V into the weakly dominated part Vi and non-dominated part V2, and apply Shannon-entropy regularization to 1/1 and Tsallis-entropy regularization to V2. We combine the FTRL method with exploration using a uniform distribution over the weakly dominating set, similarly to the approach by Alon ct al. [2015). However, we adjust exploration rates and learning rates in a carefully designed manner, in contrast to the existing approach that employs fixed parameters. The combination of the above techniques leads to an pntropy-depende regret bound. By applying the self- deff-bounding technique to this bound, we obtain improved regret bounds for stochastic environments.
2 Related work
Since Bubeek and Slivkins 2012
initiated the study of
(BOBW) algorithms
for the multi-armed bandit (MAB) problem, studies on BOBW algorithms have been extended to a
variety of problem settings, including the problem of prediction with expert advice (Gaillard et al.
2014 Luo and Schapire 2013). combinatorial semi-bandits [Zimmert et al.] [019]] [to 202 la linear
bandits [Lee et al. [022]] J. episodic Markov decision processes [Jin and Luo| [220 Jin al. 2021], J
bandits with switching costs RRuyyer et al.) [222]] Amir et al.] 2022]. bandits with delayed feedback
[Masoudian et al. 2022]. online submodular optimization [Ito] [022]. and online learning with feedback graphs [Erez and Koren 2021 Kong et al., 2022 Rouyer et al. 2022]. Among these studies, those using the our work. In an analysis of algorithms in this category, we show regret bounds that depend on output distributions, and we apply the self-bounding technique to derive BOBW regret bounds. In applying this approach to partial feedback problems including MAB, it has been shown that regularization based on the Tsallis entropy (Zimmert and Seldin, 202T Zimmert et al., 2019) or the logarithmic
framework [MeMahan| 201 I] are particularly relevant to
barrier (Wei and Luo 2018 Ito 202 Ito et al. 2022 useful. By way of contrast, our study employs regularization based on the Shannon entropy and demonstrates for the first time that the self-bounding technique can be applied even with such regularization.
This study includes the regret bounds for stochastic environments with adversarial corruptions Lyk ouris et 2018 Gupta et al., 2019 Amir et al.] 2020). which is an intermediate setting between stochastic and adversarial settings. Zimmert and Seldin [202T] have demonstrated that the self- bounding technique is also useful in deriving regret bounds for corrupted stochastic environments. Typically, when the self-bounding technique yields a regret bound of ( for stochastic environ- ments, it also yields a bound of O(R + VCR) for corrupted stochastic environments, where C represents the amount of corruption. Examples of such results can be found in the literature, e.g., that by Zimmert and Seldin 2021]] Erez and Koren [2021]. and [to (2021b). Our study follows the same strategy as these studies to obtain regret bounds for corrupted stochastic environments.
The problem of online learning with feedback graphs was formulated by Mannor and Shamir (001]). and Alon et al. [2015) have provided full characterization of minimax regret w.r.t. this problem. Whereas these studies have considered adversarial models, Caron et al. (2012) have considered stochastic settings and proposed an algorithm with an (In T - bound. In addition to these,

---

there can be found studies on such various extensions as models with (uninformed) time-varying feedback graphs [Cohen al.) 2016 Alon al. 2017]. stochastic feedback graphs [Kocák al.
2016 Ghari and Shen 2022 Esposito et al. [022]. non-stationary environments [Lu et al.) 2021a] and corrupted environments [Lu et al. 202 as well as such improved algorithms as those with
problem-dependent regret bounds [Hu et al. 2020).
3 Problem setting and known results
Let G = (V, F.) be directed graph with V = [ (1, K} and E S V V, which we refer to as a feedback graph. For each i E V. we denote the in-neighborhood and the out- neighborhood of G by (i) and Nour(i) respectively, i.e., (in = (j E V (i,) E F} and Noutt( (t) (i E V (i,5) E}.
Before a game starts, the player is given G. For each round 1, 2....... the environment selects the loss functions & : V + [0, I], and the player then chooses I, E V without knowing l, where the value (i) represents the loss for choosing i V in the t-th round. After that, the player incurs the loss of & (1)) and observes ((O) for all j E N (I)). Note that the player cannot observe the incurred loss if Le & No (Ig). The goal of the player to minimize the sum of incurred loss. To evaluate performance, we use the regret Ry defined by
T
T (000)
RT(1")=
Σ 4(4 1=1
-
max
max RT(("), VVVV
where the expectation is taken with respect to the randomness of l, and the algorithm's internal randomness. The minimax regret R(G, T) is defined as the minimum over all randomized algorithms, of the maximum of Ry over all loss sequences {le}. Alon et al. (2015) have shown that the minimax regret can be characterized by the notion of observability:
Definition ([Alon et al. 2015 ). A graph G is observable if (1) & á holds for each i E V. A graph G is strongly observable if {i) C. (i) or V \ {i} C (i) holds for each i V. A graph G' is weakly observable if it is observable but not strongly observable.
We further define the independence number (G) and the weak domination number ((G) as follows: Definition 2. For graph G = (V. F). an independent set S C V is a set of vertices such that u, E S. * V > (u, v) d F. The independence number (G) of is the size of its largest independent set. For graph G (V,E), E),, weakly dominating set D C V is a set of vertices such that E V & N Nont (ont(i))
(i}} C Nont Nj). The weak domination number 8GG) of G is the size of its smallest weakly dominating set.
Remark 2. The definitions of weakly dominating set and weak domination number in this paper slightly different from those by Alln et al. (2015). However, this difference is negligible as the gap between weak domination numbers in our definition and in theirs is at most one. Details are discussed in Appendix
The minimax regret can then be characterized as follows:
Theorem 3 ([Alon al. 2015). Let G be a feedback graph with [V] 2 2. Then, the minimax regret for T Z [V (i) R(G,T) 0(2-/271/2) G is strongly observable; (it) R(G,T) /38//3///3 G is weakly observable; (iii) R(G,T)= ((T) ifG is not observable.
Following this statement by Alon et al.
2015 we assume T 2 | K3 in this paper.
Regret bounds by Freez and Koren 2021 listed in Table depend on the clique covering number (G) of the feedback graph. The clique covering number (G) is the minimum value of N such that there exists clique cover {Vx J.v k= for G of size N. A clique cover is partition of vertices V for all k + k,, UP_ V = V, and V2 x V, C E
such that each V2 a clique, i.e., V₁, n V holds for any While there exists an example such that = ((G) > (G) =10 we always have ((G) 2 (GG), that is, the clique covering number is at least the independence number. In fact, for any clique cover (Vr k=1 and any independence set S C V, two distinct elements can never be
N
in single clique VN. which implies that N > |S].
For example, consider the graph G (V, b3) given by [K] and E' VV
5

---

In this work, we consider the adversarial regime with self-bounding constraint, comprehensive regime including stochastic settings, adversarial settings, and adversarially corrupted stochastic settings.
Definition 3 (adversarial regime with self- coff-bounding constraint (Zimmert and Seldin 2021 ), Let
A V [o, 1] and C 2 0. The environment is an adversarial regime with (A, C,T) self- bounding constraint if it holds for any algorithm that
Σ AIL) - -c-
Ry E
As has been shown by Zimmert and Seldin [202]] this regime includes (adversarially corrupted) stochastic settings. Indeed, if & follows distribution D independently for t 1,2,.... T we have
Rr EV E
(4((1) Ex("))
E ) where we define A by A
Ee-D(e(t) - min;-ev Eg_DDe(i [(=")(((")] This means that the environment is in an adversarial regime with (A, 0,T self-bounding constraint. Further, if l, satisfies Σ max (ex(1) - (() S C for some E D, the environment is in an adversarial regime with a (A, T) self- self-bounding constraint. bounding
Note also that, for any A : V + [0, the adversarial regime with a (A, 2T, clearly holds when C = 27.
constraint includes all the adversarial environments since 2
In this paper, we assume that there exists i" E V such that A(i*) = and that Amin min A, > O. This implies that the optimal arm i" is assumed to be unique. Similar assumptions were also made in previous works using the self-bounding technique [Gaillard et al. 2014 Luo and Schapire 2015 Wei and Luo 2018 Zimmert and Seldin 2021 Erez and Koren 2021
4 Preliminary
The proposed algorithms are based on the hegllo-te--rgullrizee--eeeee approach. this approach, we define probability distribution Pt. over V as follows:
Qt E arg min PEP(V)
Σ
(BOD) + - Pt p= (1=11-76 70)4 + YA
(3)
[0,1] Eiev p(i) 1) expresses the set of all probability distributions over V, Eg is an unbiased estimator for ls, (t,p) = Eiey (())p(i) represents the inner product, whe P - IR is a convex regularizer function, 7/ E [0, is parameter, and pær is the uniform distribution over nonempty subset U C V, i.e., (i) 1 1/L0| for U and (o) i E VİU. After computing Pt defined by (3) we choose I, following so that Pr[4, = =ipp.] (i). We then observe L+()) for each j Nou (L+). Based on these observations, we set the unbiased estimator & V - IR by
where P(V) = (
0 for
4000 = 40(i)
1li E Nouut (1)), P.( = Σ pr(i). )EN
(4)
Pi(i)
Let D, denote the Bregman divergence with respect to vht, i.e.,
Dr(p, (p() (x) (Varea)) g)-
(5)
We then have the following regret bounds:
Lemma 1. If Le is chosen by the above procedure, the regret is bounded by
Rr < E Σ
no + (le.ge- -941) De(004194 4)) + ve((-1) rhet ((0+1))
+ 2/2 (91).
(6)
where 14- (i) = 1 iifi = and p.o (i) = Ofori V {

---

This lemma can be shown by the standard analysis technique for FTRL, e.g., given in Exercise 28. of the book by|Lay Lattimore and Szepesvári [2020] combined with the fact that & defined by (4) is an unbiased estimator of l. All omitted proofs will be given the appendix.
We also introduce the following parameters Q(1*) and Q, which will be used when applying self- bounding technique:
Q(1)) = (1-)(()) ((=)) = E [Q(()), Q = min Q((). EVE
(7)
1=1
We note that these values are clearly bounded 0 < Q S Q(1)) S T for any i' E V. In an adversarial regime with a self-bounding constraint, the regret can be bounded from below, as follows: Lemma 2. In an adversarial regime with self-bounding constraint given in Definition bounded as RT - Q
3 the regret
This lemma will be used to show poly-logarithmic regret in adversarial regime with a self-bounding constraint.
5 Strongly observable case
This section provides an algorithm achieving regret bounds in Theorem t/ using the Shannon entropy H (p) as follows:
We set U V and define
(p) = (p) where H(p) = Σ
p(i)
In
(8)
p(i)
iEV
where 3, > 0 will be defined later. we choose 7 = min
1/2
and 8r = 1 for all t, the
67
2%.
FTRL algorithm (3) with (8) coincides with the Exp3.C G algorithm with the parameter setting given in Theorem 2 (i) by Alon et al. 2015). As shown by them, this round-independent parameter setting leads to a regret bound of RT = 1221/111/2 In(K))..
In this work, we modify the update rule of B, and 74 as follows: We set B1 = C₁ 2 1 and update 3 and // by
C1
Be+1 3: +
Tt
/ 1 (In K)-K Σ. ===1 02
23,
where a₂ is defined by a, = (qq)) . In the following, we will show the following regret bounds: Theorem 4. the feedback graph G is strongly observable and has the independent number = (G)), the FTRL algorithm with U = V and the defined by (8) and (9 enjoys regret bound of
Rr S. max (Q12211 13. where ė= o (eInT-In((aKT) (((cKT)
+ +avmk)
Vin(KT)
(10)
GVvnK
Consequently, we have Ry = = (êVT) in the adversarial regime and Ri = 0 in adversarial regimes with self-bounding constraints.
(Am
8²
+v
Cea Amin
Ami
When we set = - ( In (KTTT) in this theorem is at most O (Valnn (I(KK))) In
which leads the regret bounds in Theorem In the rest of this section, we provide proof for
Theorem 4
Let us start with the following lemma:
Lemma 3. If the is given by with B, 2 and 7, 2 1/(22),, the regret for the FTRL algorithum
with U V is bounded as
RT < E
Σ
1 4a In
K2
+ (Br41 - B6) )
+ 31 In
(1I)
B.
47r
where a, ((t)) is the value of the Shannon entropy for qt-
7

---

This lemma follows from Lemma and the technique used in the proof of of et al. [2015 Theorem 2]. We note that 0 I a I In K and ai In K. From Lemma and the update rules of parameters given by ② we obtain the following entropy
regret bound:
Proposition 1. Suppose
(11) holds. If Be and " are given by
9 Rr S CE
V V= az
where
(q)) and ē = 0 ( T-Ine-- + +avink)
qvmR
Proof. We will show the following two inequalities:
T
( + 4n
K2) 47x )==))=
annT an -I(g
T
Σ
7t +
Σ
a$
(12)
Be
civInK
T
(Be+1 B1)aa+1= =
Σ
at
(13)
Let us first show
12
From the definition of Yt given in
9
we have [LHS of 12
Ei 3 + Sa In k
3 In
R T Σ Be
From the definition of Br given
by Be is bounded as 3e cI +
ett
We
u==l
VI+ En-1a
V 1- Kln E a
hence have Et o IT
1
(In (In))1 E.= a. S 1+hT
1 + (In K) E at S
De
1= oft
ET=1 ae where the last inequality follows from a1 = In K. Combining the above
civink inequalities, obtain
122
Let next show
13 From
we have [LHS of 13
ΣT T
11=1
I+(In R)
Σ 0
a1+1
20, I ET
20 221
Et
0141
/ ao VIn 1
Ei-19.
201 Vink
E
- a2
E as
20 aavnn K
== as
a1
2c, Devviny
El= 1==1 at, where inequalities follow from S a1 In K. This proves
1
Inequalities 12 and 13 combined with ([] lead to the regret bound in Proposition
In addition, Σl 0: ΣT= (ge) is bounded with Q(i") defined in 7 as follows:
Lemma 4, Suppose at = H (qt). For any i E V, we have Σ a S =((") In eKT
Q(-)-
We are now ready to prove Theorem
if Q(*") S we have E I e cln(KT) and otherwise, we have ΣT ag S Qii)) In (KT)). Hence, we have DT a S In(KT) max {e, Q(i*)) Combining this with Proposition we obtain (10). Since Q $ T, we have Ry S éVT in adversarial regimes.
Proof of Theorem 4 From Lemma
implies the environment satisfies (A, C, T) self-bounding constraint 2). we have Ry 2 Amin Q C. Combining this with Proposition)
We next show Ry =
+
C22 Amiu
From Lemma
Aniu
and Lemma 4 it holds for any X > 0 that
Admin
Ry (1 R) - XRT s (1 1)ē QI((K))
Q AC
2
((1 + 2) In(T) -C
2 (I(TT)
2² (n(TT
( (()((KT) + 2C
22Amin
Amin
2A
Amin
2
Amin
where the first inequality follows from Proposition
Lemma
the condition of Q(i*) 2 e,
and 23 The second inequality follows from a
x
25
a
Vox
S
25
22
which

---

e (
e (l((K)
+ +2C),
holds for any a, b, x 2 O. By choosing À
we obtain R
Amin
Amin
+
Ca2
A
6 Weakly observable case
This section provides an algorithm achieving regret bounds in Theorem 2 Let D be a weakly
dominating set, defined in Definition 2 and let Vi = Usen (i), V/2 V V.. We consider here
the FTRL approach given by (3) with U = and regularizer functions defined as
(x(r = Be Σ h(p(i)) + Σ Vig(p(i)),
SEVi
VVV
where h(x)) = In + (1 - x) In(1 - x), g(x) = 2/- 2 x.
(14)
The regularization with h(x) for V1 variant of Shannon-entropy regularization, which can be considered as a modification of the approach of the Exp3.G by Alon et al. [2015). The remaining
part defined with g(x) for 1/2 modification of the approach used the Tsallis-NNP algorithm by
Zimmert and Seldin [2021). which is BOBW algorithm for MAB problems. Intuitively, approaches for MAB work well for vertices in 1/2 they have self-loops, i.e., choosing actions in 1/2 admits bandit feedback.
Let us define parameters "I and 3r by B1 max((22 8|D[} and
cibe
C2br
2 D|
%/
Ci + (Ein 1/31 B.11 Br +
1/2 = 7/ +
*e (c1 + E1=1 b.a.-1
(15)
where C1, > 0 are input parameters such that
2 2n K and with {ar} and {br} are defined by
ag = - Σ h())(t),,
b = Σ (1) -
(16)
SEV
iEV
Note that Og and è used in this Section arr different from those defined in Section 5 We then have the following regret bounds:
Theorem 5. If the feedback graph weakly observable, the FTRL algorithm with and ahe defined by 14 and [5) enjoys regret bound of
Rr S ē. max {QR13 .
+ +0
((((() (n -))112)
where
[ + oz Vin(KT)
Ō ca + Vai
(17)
Consequently, ifT K3, have RT 0 (3T2/3) in the adversarial regime and
(
C2
1/3
V2 Amin
C In
RT 0
+
(18)
2 min
2 min
A Amin
in adversarial regimes with self-bounding constraints.
We obtain è = O ((DD
([D))TTTIn((KT)) In(KT))1/$) by setting e₁ θ ((D) In In(KT))1/3) and
θ / D In By using weakly dominating set D such that [D] (8(G)), obtain the regret The remainder of this section is dedicated to the proof of Theorem
bounds in Theorem
2
We start with the following regret bound:

---

Lemma S. the is given by
14
and 7 2
2DD
we have Rr S nej + RG + 11131 where
Dbb
+ (5t41 (.)ae+t) )
R4
0
E
Yt
+
(19)
T
R = E
Va((i)(1 (00(1))9(00))
(20)
EV
with {ae} and {be} defined by (16..
When showing (19) and 20
techniques used in the proofs Alon al. [2013] Theorem 2]
and of Zimmert and Seldin 2021 Lemma 11]. We then have the following bound:
Proposition 2. T and Be are given by R satisfying
19)
bounded as
R = E ci B
+ &
v (InK + AT) (a1 + B
(21)
where AT Ets ar BT = Ets by and (
D + 02)
Vei
Values of Ar and BT in this proposition can be bounded with Q(i*) defined in as follows: Lemma 6. Ar and Br defined in Proposition 2 satisfy Ar s 2Q(i") In eKT and Br S 2Q()))
Q07)
Further, R in Lemma can be bounded with Q as follows:
Lemma 7. Rb satisfying 20 is bounded as RQ O
V22 In Q).
Proof of Theorem
From Proposition 2 and Lemma 6 if Q of have
RC 0
((1))233 (()))))))) + ë (())
co((a+évimm + (((((tt)k)))) @e/3).
where the inequality follows from Jensen's 's inequality. Hence, there exists è such that RC < è Q2/3 and = O ((1 + +v/In(KT) Combining this with Lemma 7 we obtain 177 As we have Q < T, in adversarial regimes with T > K3, it follows from (17) that Rr
O (c. max (T2/3, ef) + (KIn T. 1T)12) = O (ē- 72/3), where the second equality follows from m
the T 2 K., Let us next show (8). From (17 and Lemma
2 for any X E (0, 1J. we have
Ry (1 X)R ART O (1 A)e. Q2/3 + (1+ ()( T Q) Ammin
min Q + +C).
By argument similar to the proof of Theorem we have (1 + A) T
Q)1/2 XA min Q 1/3
O ((1 ))
VaalnT))
We also have (1 + A)ē Q2/3 Admin Q = AAA
(1-A)²
(A4min Q)
2/3
Amin
min
AAmin Q = O (1+1)**
0 }
where the second equality follows from
x
2/33 < f + Zy that holds for any 2, y
0. Combining these inequalities, we obtain
Rr 0 ( +
(1+ }) [V3] In
XC)
By choosing À that minimizes the RHS,
Amin
obtain 18)
Acknowledgment
TT was supported by JST, ACT-X Grant Number JPMJAX210E, Japan and JSPS, KAKENHI Grant Number JP21J21272, Japan. JH was supported by JSPS, KAKENHI Grant Number JP21K1 Japan.
10

---

References
N. Alon, N. Cesa-Bianchi, O. Dekel, and Koren, Online learning with feedback graphs: Beyond bandits. Journal of Machine Learning Research, 40(2015), 2015.
N. Alon, N. Cesa-Bianchi, C. Gentile, S. Mannor, Y. Mansour, and O. Shamir. Nonstochastic multi- armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6):1785-1826, 2017.
I. Amir, I. Attias, T. Koren, Y. Mansour, and R. Livni. Prediction with corrupted expert advice. Advances in Neural Information Processing Systems, 33:14315-14325, 2020.
I. Amir, G. Azov, T. Koren, and R. Livni. Better best of both worlds bounds for bandits with switching costs. Advances in Neural Information Processing Systems, 35, 2022.
P. Auer, N. Basa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning. 47(2):235-256, 2002a.
Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002b.
S. Bubeck and A. Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Conference Learning Theory, pages 42-1. JMLR Workshop and Conference Proceedings, 2012.
S. Caron, B. Kveton, M. Lelarge, and S. Bhagat. Leveraging side observations in stochastic bandits. In Proceedings of the eventy-Eighte Conference on Uncertainty Artificial Intelligence, pages 142-151, 2012.
A. Cohen, T. Hazan, and T. Koren. Online learning with feedback graphs without the graphs In International Conference on Machine Learning, pages 811-819. PMLR, 2016.
L. Erez and T. Koren. Towards best-of-all-worlds online learning with feedback graphs Advances in Neural Information Processing Systems, 34, 2021.
E. Esposito, F. Fusco, D. van der Hoeven, and N. Cesa-Bianchi. Learning on the edge: Online learning with stochastic feedback graphs. Advances in Neural Information Processing Systems, 35, 2022.
Y. Freund and R. E. Schapire. A decision-theoretie generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-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.
P. M. Ghari and Y. Shen. Online learning with probabilistic feedback. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4183-4187 IEEE, 2022.
A. Gupta, T. Koren, and K. Talwar. Better algorithms for stochastic bandits with adversarial corruptions. In Conference on Learning Theory, pages 1562-1578. PMLR, 2019.
B. Hu, N. A. Mehta, and Pan. Problem-dependent regret bounds for online learning with feedback graphs. In Uncertainty in Artificial Intelligence, pages 852-861. PMLR, 2020.
Ito. Hybrid regret bounds for combinatorial semiibandits and adversarial linear bandits. Advances in Neural Information Processing Systems, 34, 2021a.
S. Ito. On optimal robustness adversarial corruption in online decision problems, In Advances in Neural Information Processing Systems, 2021b.
S. Ito. Parameter-fiee free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Conference Learning Theory, pages 2552-2583. PMLR, 2021c.
S. Ito. Revisiting online submodular minimization: Gap-dependent regret bounds, best of both worlds and adversarial robustness. In International Conference on Machine Learning, pages 9678-9694 PMLR. 2022.
11

---

S. Ito, T. Tsuchiya, and J. Honda. Adversarially robust multi--rreed bandit algorithm with variance- dependent regret bounds. Conference on Learning Theory, pages 1421-1422. PMLR, 2022.
Jin and H. Luo. Simultaneously learning stochastic and adversarial episodic mdps with known transition. Advances in Neural Information Processing Systems, 33: 33:16557-16566, 2020.
T. Jin, L. Huang, and H. Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 34, 2021.
T. Kocák, G. Neu, and M. Valko. Online learning with erdós-rényi side-observation graphs. In Uncertainty in Artificial Intelligence. 2016.
F. Kong, Y. Zhou, and S. Li. Simultaneously learning stochastic and adversarial bandits with general graph feedback. In International Conference on Machine Learning, pages 11473-11482 PMLR, 2022.
T. L. Lai, H. Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
T. 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-opimmality and minimax-optimality in stochastic and adversarial linear bandits simultaneously. In International Conference on Machine Learning, pages 61 6142-6151, 2021.
N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-22) 1994.
Lu, Y. Hu, and L. Zhang. Stochastic bandits with graph feedback non-stationary environments. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021a.
S. Lu, G. Wang, and I.. Zhang. Stochastic graphical bandits with adversarial corruptions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 2021b.
H. Luo and R. E. Schapire. Achieving all with no parameters: AdaNormalHedde. 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 Annual ACM SIGACT Symposium on Theory of Computing, pages 114-122, 2018.
S. Mannor and O. Shamir. From bandits to experts: On the value of side-observations, Advances in Neural Information Processing Systems, 24, 2011.
algorithm for bandits with delayed feedback. Advances in Neural Information Processing Systems, 35, 2022.
Masoudian, J. Zimmert, and Y. Seldin. A
B. McMahan. Follow-the-regilarieeee-ee
and mirror descent: Equivalence theorems and 11 regularization. In Proceedings of the Fourteemth International Conference on Artificial Intelligence and Statistics, pages 525-533. JMLR Workshop and Conference Proceedings, 2011.
C. Rouyer, Y. Seldin, and N. Cesa-Bianchi. An algorithm for stochastic and adversarial bandits with switching costs. In International Conference on Machine Learning, pages 9127-9135. PMLR, 2021.
C. Rouyer, D. van der Hoeven, N. Cesa-Bianchi and Seldin. A near-optimal best-of-both-wook algorithm for online learning with feedback graphs. Advances in Neural Information Processing Systems, 35, 2022.
Y. Seldin and G. Lugosi. An improved parametrization and analysis of the EXP3++ algorithm for stochastic and adversarial bandits. In Conference on Learning Theory, pages 1743-1759. PMLR, 2017.
Y. Seldin and Slivkins. One practical algorithm for both stochastic and adversarial bandits. In International Conference Machine Learning, pages 1287-1295. PMLR, 2014.
12

---

C.-Y. Wei and H. Luo. More adaptive algorithms for adversarial bandits. In Conference on Learning Theory, pages 1263-1291, 2018.
Zimmert and Y. Seldin. Isa: 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 simultaneouslly In International Conference on Machine Learning, pages 7683-7692. PMLR, 2019.
13


Reviews:
[{"review_id": "whmmicsUDCj", "reviewer": "Reviewer_eXST", "summary": "The authors consider the Best-of-Both-Worlds setting in Online Learning with Feedback Graph: the rewards of arms can be stochastic or adversarial and the feedback of them is described by a directed graph of arms. The authors show for strongly observable graphs, FTRL with the negative entropy regularizer and adaptive learning rates has optimal regret bounds up to logarithmic factors in both stochastic and adversarial settings. For weakly observable graphs, a more sophisticated regularizer give similar results.", "questions": "Can authors talk about whether it is possible to get bounds scaling with $\\sum_{i\\in S}\\frac{1}{\\Delta_i}$ for strongly observable graphs under this approach?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- This is a great paper. The problem is important and challenging, but the authors give pretty simple and clear solutions. For strongly observable graphs, it is not surprising that entropy can be used for this setting, but how to properly tune the learning rates seems highly nontrivial. I roughly checked the proof and didn't find any issues. Overall the analysis is quite concise. For weakly observable graphs, the choice of the regularizer is more mysterious to me. Maybe the authors can comment more about this, for example, the intuition to add $(1-x)\\ln(1-x)$ and $\\sqrt{1-x}$ terms.   \n- Besides suboptimal orders of logarithmic terms, one weakness is that the gap-dependent constants are still not optimal. For example, consider standard bandit feedback. The bound in this case is $\\frac{\\alpha(\\ln T)^3}{\\Delta_{\\min}}$, which is not ideal once K is very large and there is only one small gap. I think it would be great to comment this somewhere or show some bounds of optimal stochastic algorithms in the table. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rd3IMlm36HE", "reviewer": "Reviewer_1CHF", "summary": "This paper considers the design of best-of-both-worlds algorithms for the problem of online learning with feedback graphs. Online learning is a sequential setting which proceeds in rounds $t = 1, \\ldots, T$, where in each round the learner issues a prediction, suffers a loss that corresponds to this prediction, and then obtains some feedback on the prediction. The goal is to control the regret, which is the difference between the cumulative loss of the learner and the cumulative loss of the best fixed prediction in hindsight. This version of online learning considers possibly partial feedback scenarios modelled by directed graphs where nodes are the available actions. In this setting, the feedback received by the learner after choosing an action is given by the loss of actions in the out-neighbourhood of the currently selected action. Best-of-both-worlds algorithms try to achieve optimal regret in both adversarial and stochastic scenarios simultaneously, where losses may or may not follow an underlying distribution. The authors extend previous work to more general feedback structures. They manage to design best-of-both-worlds algorithms for any strongly observable or weakly observable feedback graph, respectively, and prove near-optimal regret bounds for them. In particular, for strongly observable graphs with independence number $\\alpha$, the bounds are of order $\\sqrt{\\alpha T}$ for adversarial losses and $\\alpha \\ln(T)^3/\\Delta$ for stochastic losses, where $\\Delta$ is the difference between the expected loss of the best arm and the second best arm. For weakly observable feedback graphs with domination number $\\delta$, the bounds are of order $\\delta^{1/3}T^{2/3}$ for adversarial losses and $\\delta \\ln(T)^2/\\Delta^2$ for stochastic losses. ", "questions": " ", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, the paper is well written and the results are new. However, the authors should take some care in addressing the typo’s in the paper, of which some are listed below. The authors provide sufficient motivations for studying the problem at hand. Not only do the results improve upon previous work in terms of regret, they are also more general  as the feedback graphs in this paper are arbitrary feedback graphs rather than restricted feedback graphs considered in previous work. For stochastic losses, compared to the previously best known result the improvement in the strongly observable case is a factor ln(T)^2 and an improvement in the leading factor, which changes from the clique covering number to the independence number. For the weakly observable case there were no previous best of both world results. The near-optimality of the regret bound for the proposed algorithms required an improved analysis on the performance of follow-the-regularized-leader (FTRL) with the Shannon entropy regularizer, while using a novel definition for the update rule of the learning rate at the same time. The above results are indeed not immediate to achieve. As the authors themselves state, this might be useful for different applications of FTRL with a Shannon entropy regularizer too.\n\nRelevance:\nBest-of-both-worlds algorithms have been of recent interest in online learning settings. Therefore, the submitted work is sufficiently relevant since it provides significant advances addressing the online learning problem with feedback graphs.\n\nClarity:\nThe results are presented in a clear manner and are well contextualised in the literature.\n\nWeaknesses:\nIn both the weakly and strongly observable case the upper bounds for stochastic losses may be a factor $\\ln(T)^2$ away from being optimal. However, the upper bounds improve greatly on previous work, and the lower bound in the weakly observable case probably can be improved. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "jtqgiBZLDfj", "reviewer": "Reviewer_3PsX", "summary": "The authors consider the online learning with directed feedback graphs problem and present algorithms based on the follow-the-regularized-leader approach, which achieve best-of-both worlds regret guarantees in both the fully observable and the weakly observable settings. \n\nThe regret bounds presented in the paper are optimal up to polylog factors i advnersarial settings, and are polylogarithmic in $T$ in stochastic settings. The authors also prove regret bounds for the more general adversarial regime with a self-bounding constraint. \n\nIn the fully observable case, the authors employ FTRL with a negative entropy regularization and an adaptive learning rate and exploration scheme to obtain regret bounds that scale with the feedback graph's independence number $\\alpha$. In the weakly observable setting, the authors use a regularization which depends on a weakly dominating set, while employing a negative entropy regularization on vertices without self-loops, and Tsallis entropy on the vertices with self loops. In turn, the regret bounds obtained in the weakly observable case scales with the feedback graph's weak domination number $\\delta$.", "questions": "* The definition of a weakly dominating set appearing in this paper seems to differ from the definition in previous works, such as Alon et al. [2015]. In their paper, a weakly dominating set is one which dominates the weakly observable vertices. i.e. those without a self loop which also don't have incoming edges from every other vertex. However, the authors define a weakly dominating set by one that dominates all the vertices with no self loops. This makes the weak domination number - according to the authors' definition - larger in the worst case than in the definition from previous works, and in turns makes the regret bounds the authors obtain for weakly observable graphs sub-optimal in another sense. I suggest the authors either match their definition of a weakly dominating set with the definitions from previous works and modify their analysis accordingly, or alternatively, discuss the discrepancy between the two definitions and the relation between the regret bounds obtained with each one.\n* It is a bit unclear to me why the extra $\\frac{K'}{\\Delta}$ is necessary in the stochastic bound in the weakly observable setting. Since the set $V_2$ contains vertices with self-loops, i.e. fully observable vertices, instead of using Tsallis entropy on those vertices which seems to be what contributes this additive factor, why not just use the approach from the fully observable case? I.e, use negative entropy regularizer with the step size scheme described in Section 5. I'm not sure where the analysis breaks given this approach, as it seems that by Lemma 5 the regret breaks into a term which only depends on $V_1$ and a term which depends only on $V_2$ so both terms can presumably be handled separately. I would appreciate it if the authors could explain their choice of Tsallis on $V_2$ and why the approach I suggested wouldn't work.", "limitations": "The authors properly address most aspects regarding the limitations of their results, specifically the suboptimality of their regret bounds in stochastic regimes.\nSee the main review for remarks on other limitations which I believe were not properly addressed, such as the discrepancy between their definition of a weakly dominating set and previous definitions, and the required knowledge of the independence number in the fully observable setting.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The results presented in the paper improve upon currently known best-of-both-worlds regret bounds in the online learning with feedback graphs framework, and they are relevant in a very general setting of directed feedback graphs, as well as weakly observable graphs.\n* In the fully observable setting, the authors show that FTRL with negative entropy regularization suffices in order to obtain nearly optimal regret bounds, by implementing a novel adaptive step size scheme. This shows that highly complex regularizers are not essential in order to obtain such regret bounds for feedback graphs, and consequently the technical analysis in the paper is very clean and concise.\n* The authors present the first best-of-both-worlds regret bounds which hold for weakly observable graphs. while in the stochastic setting their bounds are sub-optimal, this result is highly non-trivial and is achieved with a simple algorithm which is an instantiation of FTRL with a regularizer that combines negative entropy and Tsallis entropy.\n\nWeaknesses:\n* The stochastic bounds presented in the paper are suboptimal in the following sense: For strongly observable graphs, the stochastic bound scales with $O(\\frac{\\alpha}{\\Delta})$ which in some cases could be worse than the optimal bound which scales with $O(\\sum_{i \\in A} \\frac{1}{\\Delta_i})$ where the sum is over a maximum independent set, and $\\Delta_i$ is the suboptimality gap of arm $i$. For weakly observable graphs, the stochastic bound includes an additive term which scales like $\\frac{K'}{\\Delta}$ where $K'$ is the number of arms with self-loops. In the worst case, this could scale linearly with $K$ which is known to be suboptimal.\n* In the strongly observable setting, the algorithm requires the independence number of the feedback graph in order to appropriately tune the step sizes. Since computing the independence number of a graph is computationally hard, this presents a certain limitation of the algorithm. While this limitation also appears in previous works, I think the authors should mention the algorithm's dependence on $\\alpha$.\n* A few typos: In the abstract \"follow-the-perturbed-leader\" is mentioned instead of \"follow-the-regularized-leader\", in the statement of Lemma 1 the first appearance of $\\psi_t(q_{t+1})$ should be replaced by $\\psi_{t+1}(q_{t+1})$.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0-jiszRdSlK", "reviewer": "Reviewer_7bnY", "summary": "This paper studies the best-of-both-world problem for bandits with feedback graphs.\nIt derives an algorithm which is up to log factors optimal in the adversarial regime and obtains reasonable regret guarantees in the stochastic regime.\nThe stochastic bound is sub-optimal with regard to log factors and instance dependent complexity, but it is still outperforming the best-known bound for best-of-both-worlds algorithms.\nAdditionally, it proposes best-of-both worlds algorithms in the weakly observable aka T^2/3 regime.", "questions": "Are you aware of the extremely similar paper:\n\"A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs\" ?\nGiven that you seem to have obtained almost identical results with very similar techniques in concurrent work, it might make sense to combine the two papers?\n", "limitations": "Theoretical work, no societal impact.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The math is sound and the presentation is clear.\nThere are technical novelties over the vanilla self-bounding regret analysis due to the fact that Shannon entropy is required for optimal regret in the adversarial regime.\nAn important limitation of this work is the existence of a very similar work (even up to the title): \"A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs\". \nThe other work explicitly estimates the gaps in the stochastic regime and obtains a better stochastic bound. This work on the other side is purely using the self-bounding technique which simplifies the algorithm and allows for a straightforward bound for the corrupted stochastic setting. The analysis for weakly observable graphs is also unique to this paper here.\nOverall, both paper build on the same literature and use very similar algorithmic techniques to obtain almost identical results.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept