A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
Authors: Chloé Rouyer
Dirk van der Hoeven
Nicolò Cesa-Bianchi
Yevgeny Seldin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online Learning
Feedback Graphs
Beyond Bandits

Abstract: We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally-efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both stochastic and adversarial environments. The bound against oblivious adversaries is $\tilde{O} (\sqrt{\alpha T})$, where $T$ is the time horizon and $\alpha$ is the independence number of the feedback graph. The bound against stochastic environments is $O\big((\ln T)^2 \max_{S\in \mathcal I(G)} \sum_{i \in S} \Delta_i^{-1}\big)$ where $\mathcal I(G)$ is the family of all independent sets in a suitably defined undirected version of the graph and $\Delta_i$ are the suboptimality gaps.
The algorithm combines ideas from the EXP3++ algorithm for stochastic and adversarial bandits and the EXP3.G algorithm for feedback graphs with a novel exploration scheme. The scheme, which exploits the structure of the graph to reduce exploration, is key to obtain best-of-both-worlds guarantees with feedback graphs. 
We also extend our algorithm and results to a setting where the feedback graphs are allowed to change over time.

A Near-Optimal Best-of-Both-Worle Algorithm for Online Learning with Feedback Graphs
Chloé Rouyer
Dirk van der Hoeven Dept. of Computer Science Università degli Studi di Milano, Italy dirk@dirkvanerrheeee com
Dept. of Computer Science University of Copenhagen, Denmark chloe@di ku.dk
Nicolò Cesa-Bianchi Dept. Computer Science Università degli Studi di Milano, Italy nicolo. cesa- bi anchi @unimi...
Yevgeny Seldin Dept. Computer Science University of Copenhagen, Denmark seldinØdi. ku
Abstract
We consider online learning with feedback graphs, sequential Decision-making framework where the learner's feedback is determined by directed graph over the action set. We present computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both stochastic and adversarial environments. The bound against oblivious ad- versaries is Ö(vaT), where is the time horizon and a is the independence number of the feedback graph. The bound against stochastic environments is O( (In 2)² max Eies A, where I (G) is the family of all independent sets suitably defined undirected version of the graph and A; are the suboptimal- ity gaps. The algorithm combines ideas from the EXP3++ algorithm for stochastic and adversarial bandits and the EXP3.G algorithm for feedback graphs with a novel exploration scheme. The scheme, which exploits the structure of the graph reduce exploration, is key to obtain sittooffboth-wollll guarantees with feedback graphs. We also extend our algorithm and results setting where the feedback graphs are allowed to change over time.
Introduction
Online learning is general framework for studying sequential decision-making in unknown environ- ments (see, for example, (Cesa- Besa-BBicchi and Lugosi, 2006; Bubeck and Cesa- Bianchi, 2012; Orabona, 2019)). We consider setting where, each round, the player chooses action (a.k.a. arm) from a fixed set of actions and incurs the loss associated with the chosen action. The performance of the learner is quantified in terms of regret, which is the difference between the total loss incurred by the learner over the duration of the game, and the smallest cumulative loss obtained by a player that would only play the same action throughout the game.
The smallest achievable regret is determined by number of parameters. One of these parameters is the amount of feedback that the leamner receives at each round. There is whole spectrum of problems, characterized by the amount feedback received by the learner. At the one extreme of this spectrum is the bandit setting, where the learner only observes the loss of the action taken. At the other extreme is the full information setting, where the learner observes the full loss vector at the end of each round, irrespective of the action played.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

There are two common ways to interpolate between full information and bandit feedback. One is to allow the learner make limited number of additional observations without restricting how the additional observations are selected. Then no additional observations correspond to the bandit setting and K additional observations correspond to the full information setting. This way of interpolation was proposed by Seldin et al. (2014) in two variants, "prediction with limited advice" and "multiarmed bandits with paid observations". It was also studied by Thune and Seldin (2018).
The second way of interpolation, which we focus on in this paper, is via feedback graphs (Alon et al., 2017). In this setting observations of the learner are governed by a feedback graph on the actions. When an action is played, the learnrr observes the losses of all of its neighbors in the feedback graph. complete graph corresponds to the full information setting. whereas graph containing only self-loops corresponds to the bandit setting. This setting has multiple variants, depending on whether the graph is directed or undirected, observed or unobserved, static or dynamic.
Another important parameter characterizing online learning problems is the type of environment. The two primary types that we focus on are stochastic and adversarial environments. In stochastic environments each action is associated with a fixed, but unknown distribution, and in each round the loss of each action is sampled independently from the corresponding distribution. In adversarial environments the loss sequence is chosen arbitrarily. We consider oblivious adversarial environments, where the loss sequences are chosen independently of the actions taken by the learner.
For a long time stochastic and adversarial environments where studied separately, but in practice the exact nature of environment is rarely known. In recent years this has led to growing interest in "hest-of-both-worrde booth-worlds" algorithms that are robust against adversarial loss sequences and, at the same time, provide tighter regret guarantees in the stochastic regime. Most work has focused the bandit setting (Bubeck and Slivkins, 2012; Seldin and Slivkins. 2014; Auer and Chiang, 2016 Seldin and Lugosi, 2017; Wei and Luo, 2018), where the Tsallis-NN algorithm proposed by Zimmert and Seldin (2019, 2021) was shown to achieve the optimal regret rates in both stochastic and adversarial regimes, as well as number of intermediate regimes. The analysis was further improved by Masoudian and Seldin (2021) and Ito (2021). In the full information setting Mourtada and Gaïffas (2019) have shown that the well-known Hedge algorithm originally designed for the adversarial setting (Littlestone and Warmuth, 1994) also achieves the optimal stochastic regret. Best-of- cit---o--oootwwwe both-world results also spilled over to other domains, including additional approaches to full information games and online convex optimization (Koolen et al., 2016; Van Erven et al., 2021; Negrea et al., 2021), decoupled exploration and exploitation (Rouyer and Seldin, 2020), combinatorial bandits (Zimmert et al., 2019), bandits with switching costs (Rouyer et al., 2021), MDPs (Jin and Luo, 2020; Jin et al., 2021), and linear bandits (Lee et al., 2021).
In the context of online learning with feedback graphs the only sost-of-bott-wortd result known to us by Erez and Koren (2021) for undirected graphs. They present an intricate algorithm based on the Follow The Regularized Leader (FTRL) framework with regularization function that is a product of the Tsallis and Shannon entropies. The algorithm simultaneously enjoys an O(VxT (In(K))) ))
pseudo-regret bound in the adversarial regime and an O(( [In (KT))) Ex lnT")) pseudo-regret bound in the stochastic regime, where T is the number of prediction rounds, X is the clique covering number of the undirected feedback graph, and the summation in the second bound is on the smallest non-zen non-zero gap within each clique.
is tempting to apply an baRed algorithm with Tsallis entropy regularization to online learning with feedback graphs, since Tsallis entropy with power a = 1/2 leads to the optimal Ts algorithm for the bandit setting (Zimmert and Seldin, 2021) and Tsallis entropy with power a = leads to the Hedge algorithm, which is optimal in the full information setting. However, as also noted by Erez and Koren (2021), extension of the analysis to online learning with feedback graphs when the power E (1/2, 1) is not straightforward and, so far, there was success in this direction. Furthermore, at the moment it is unclear whether it is possible to derive bounds that take further advantage of the graph structure and depend on the independence number of the graph when a < 1.
Our contribution. We significantly extend and improve on the bounds of Erez and Koren (2021). Our results hold for directed graphs (with selfsloops). depend on the independence number of the graph, have a better dependence on in the stochastic regime, and extend to time-varying feedback graphs. Our approach takes advantage of the common structure shared by two exponential weights algorithms: EXP3.G (Alon et al., 2015) and EXP3++ (Seldin and Slivkins, 2014; Seldin and Lugosi,

---

2017), to obtain near-optimal best-of-both worlds guarantees. By using similar ideas as in the proof of the regret bound of EXP3.G, the proposed algorithm adapts to the independence number of the graph. We derive min { {O(VāT In K), O (Vin K /tn (KT)VAT) } pseudo-regret bound against adversarial sequences of losses, where a is the independence number of the graph and á is its strong independence number, which is graph dependent quantity smaller than the clique covering number. For undirected graphs, independence number and strong independence number are equal and the result matches the best known lower bound ((v within logarithmic factors (Alon et al., 2017). In the stochastic setting we use the idea of injected exploration from EXP3++ to estimate the suboptimality gaps of each arm. By introducing novel dynamic exploration set and an appropriate exploration rate, we derive an almost optimal regret bound in the stochastic setting. Along the way, we also improve the regret bound of EXP3++ in the stochastic bandit setting. Our exploration set constructed by sorting the arms by ascending gap estimates, and then adding a new arm to the exploration set if the arm cannot be observed by playing another arm previously added to the set. If we play each arm i in the exploration set at a rate 1/å?. where Å, is the gap estimate, then all arms in the graph are observed with probability at least 1/å3.
To present our main result we introduce some notations. Let G = (V)F) F)) be directed feedback graph with independence number a (where the independence number is computed on G ignoring edge directions). We define strongly independent set on G an independent set on the subgraph G' = (V, E"), where (i,j) E E' if and only (i.j) E E and (j, E E. We use ā to denote the strong independence number of G. and Z(G) to denote the collection of all the strongly independent sets in G. We note that a = ā for undirected graphs and a I ā for directed graphs. Now we can present an informal statement of our main result.
Theorem 1 (Informal). Given a directed feedback graph G (V, with independence number and strong independence number ā, there exists an algorithm (Algorithm 1) whose pseudo-regret can simultaneously be bounded by min { (o(VTTln In k), (vin vIn (KT)aTT) } against adver- sarial loss sequences and by O( (In T)² max Eies A7)) against stochastic loss sequences.
We emphasize that Algorithm requires neither prior knowledge of the type of the environment (adversarial or stochastic), nor the time horizon.
1.1 Additional Related Work
The study of bandits with feedback graphs was initiated by Mannor and Shamir (2011) in the adversarial regime and by Caron et al. (2012) in the stochastic regime. In the adversarial regime, the optimal regret rates for arbitrary directed graphs were characterized (up to log factors) by Alon et al. (2015). They showed an S2(T) lower bound for graphs that have non-observable nodes (i.e., with an empty in-neighborhood). For graphs with observable nodes, they derived pseudo-regret bounds of order OVVTT log( KT)) when all nodes are strongly observable (i.e., they have self-loop or their in-neighborhood contains all of the other nodes) and of order O(8 (8 In 2/33332333 for weakly observable graphs (where each non-strongly observable node is in the out-neighborhood of some observable node). Here a is the independence number of the graph and 5 is the dominating number of the weakly observable portion of the graph. Van der Hoeven et al. (2021) derived results for the multiclass classification with feedback graphs setting. The setting where the graph can adversarially change over time has been studied by Alon et al. (2017) in the case of directed graphs with self-loops. For learners that are allowed to observe the feedback graph at the beginning of each round, they
achieved a bound of 0 In K (In(KT) Σt= oz). where 0a is the independence number of the
graph at time I. For the case of undirected graphs, they proved refined bound O(y In K EE= that holds even when the learner can only observe the graph at the end of each round. Note that, as shown by Cohen et al. (2016), in order to take advantage of the graph structure in the adversarial regime, it not sufficient to observe the neighborhood of the played action at the end of each round.
In the stochastic regime, Buccapatnam et al. (2014, 2017) considered a fixed, possibly directed, feedback graph. They derived an asymptotic lower bound showing that the regret scales as 2(ce In T), where e² -which is related to the domination number of the iraph-is the solution to linear program expressing the trade-off between the loss incurred from playing an action and the observations that
3

---

can be gathered from playing that action. They proposed an algorithm that can achieve a matching O(c" In T' + Kd) pseudo-regret bound, where d is the maximum degree in the feedback graph. In the case of graphs that change over time, Cohen al. (2016) derived an O(Eies (In T)) /.)) bound, where S is a set containing an order of a arms (up to log factors), and a is an upper bound on the independence number of the graphs in the sequence. They achieved this result without requiring to observe the graphs fully, and having only access to the neighbourhood of the arm played at the end of the round. Both of these approaches are based on arm elimination algorithms, which by construction are not suitable for best-of-both worlds guarantees. The proof strategy of Cohen et al. (2016) was adapted by Lykouris et al. (2020) to provide refined bounds for both UCB-N and Thompson Sampling-N, which are variants of UCB1 (Auer et al., 2002) and Thompson Sampling (Thompson, 1933). In both cases, Lykouris et al. (2020) considered undirected feedback graphs and obtained pseudo-regret bounds that scale as O maXindeZ(C) Eietnd In(KT) / A,), where I(G) is the collection of all the independence sets of the graph.
Concurrently to our work, several other papers in online learning with feedback graphs have appeared. Ito et al. (2022) derive an algorithm with nearly optimal regret bounds in both the stochastic and adversarial setting. While their results more general than ours (they do not require self-loops in the feedback graph), their regret bounds in the stochastic regime are worse that ours, of order In(7) A.g. where Ami is the minimum suboptimality gap. Similarly to Frez and Koren (2021), the algorithm of Ito et al. (2022) based on the FTRL framework. They use the entropic regularization, which makes their algorithm equivalent to EXP3 (Auer et al., 2002). Moreover, Ito et al. (2022) rely on the self-bounding technique of Zimmert et al. (2019) together with an intricate tuning to simultancously obtain regret bounds in the stochastic regime and the ad adversarial regime, as well as in intermediate ones. In the stochastic regime, Marinov et al. (2022) provide an improved characterization of the difficulty of online learning with feedback graphs in both finite-time and asymptotic cases. Finally, Esposito al. (2022) study the more general model of stochastic feedback graphs.
2 Problem Setting and Definitions
Problem Setting We consider a sequential decision-making game, where in each round ( = 1, 2, .... the learner repeatedly plays an action I, E V. where [V] = K, receives feedback based on a feedback graph G = (V, E), and suffers a loss f, We consider directed feedback graphs with self-loops, meaning that (i, E for each vertex E V. The feedback received by the learner at the end of round is { (i,,e,)) : E NouE(T)))) where Nout (i) = {j E V (i.j) E E} is the out- neighbourhood of i. Similarly, we define (1)(1) = [jj E V (j. E E} to be the in-neighborhood of i. For each arm i E V, l,5 [0, 1] for / 2 1. In the adversarial regime the losses are generated arbitrarily by an oblivious adversary. In the stochastic regime they are independently drawn from a fixed but unknown distribution with expectation B[(,,]] The performance of the learner is measured in terms of the pseudo-regret:
T
T Σ
R₂ = E
Σ Ce.
min E eVV
In the stochastic regime, we define the best arm i as the arm with the smallest expected loss, i.e. i" = argmin,gg E(f,,] The pseudo-regret can then be expressed in terms of the suboptimality gaps A, E|4,, (1,2-).
T
Rr
Σ
E
pr..) A.,
.VV
where Pt, is the probability that the learner plays action i at round t. We define the smallest suboptimality gap Amin min..,,0 (Ai), and for all we define A, = max (Amin: A.), so that A,- = Amin- We use E, to express expectation conditioned on all randomness up to round t.
Properties of Graphs Recall that a dominating set in G is subset D V. such that for all i E V there exists j E D. such that (j, i) E E. An independent set in G is subset S C V. such that for all i E S, (i.j) & E and (j,i) g E. We define the independence number (G) as the size of the largest independent set in the graph G. For clarity, we restate below here the definition of the strong independence number which was already mentioned in the introduction.

---

Algorithm 1: EX+3.G++
Input: Feedback graph G (V, (V, Learning rates 2 122 2 > 0: exploration rates εt,i for i E V. see Equation (2)
Initialize: Lg 0g. Lo 0x and Og 0x. Play each arm once to initialize L and O
for / = + 1, K + 2.... do
L L
In (tK*))
Vi E V: UCB., min
0
20,-1,5
1
y In (tK(t//))
Vi V: LCB,,
0,
O1-1,
20c-1,5
E V Á. = max ,,,,, - min, UCB
vi E V update εt, based on the gap estimates A
exp(-nx(1.))
Vi E 41s Eievexp( (sp(--)oLa.)) Pt.i =
1 ELS jEV
91 + EL,
Sample I Pt and play
Observe (1,)) E Nout Noou((e)) (It) and suffer la,t.-
VIEV: 4, = l (I)) where P.,s = ESENi (1) Ph.j
P.s
ViEV: - E4s
VieV V: L, = in-1, 4 li (o)u((I)) and Ot, 00-15 e Nout No)t(())
end for
Definition Let G (V, E) be a directed graph. We define a strongly independent G as an independent set on the subgraph G' (V, F.), where (i.j) E E' ind only if (i,j) E E and (5, F. Furthermore, define (GG) as the independence number the subgraph G'
We use I(G)) to denote collection of all the strongly independent sets in G. We note that = ā for undirected graphs and a S ā for directed graphs.
Algorithm
We present the EXP3.G+ algorithm (Algorithm 1), which is combination of the EXP3.G algorithm of Alon et al. (2015) and the EXP3++ algorithm of Seldin and Lugosi (2017) with a novel exploration scheme deseribed in Algorithm 2. This scheme ensures that the additional feedback the leamner obtains (relative to the bandit setting) is used nearly optimally.
To understand the motivation behind the novel exploration scheme, note that in the stochastic setting EXP3.G+ needs to ensure that the loss each arm is observed sufficiently often. However, if we would play each arm too often, the regret would scale with the number of arms, rather than with the independence number or some other graph-theoren quantity. avoid that, we exploit the central gather information
property of feedback graphs: since arms the graph, we can restrict exploration to subset of nodes and yet obtain sufficient information on all the arms. We exploit this observation, to design strategy for selecting exploration set S, at each round St is defined in terms of estimated suboptimality gaps ÂL.. which maintained by EXP3.G++. Crucially, the exploration set ensures that, with high probability, the empirical gaps are reliable estimates of the true suboptimality gaps A, In turn, this ensures that observe the loss of each arm sufficiently often.
certain arms by playing adjacent
The construction of the exploration set S, is detailed in Algorithm 2, which is used by EXP3.G+ to update the exploration rates εr,, according to Equation (2). Algorithm starts by sorting the arms according to their gap estimates in ascending order. The exploration set is then greedily constructed by sequentially selecting the next with the smallest Å and discarding all the arms in the out-neighborhood of that arm. The exploration set can be constructed in O(K3) time, but note that
5

---

Algorithm 2: Exploration Set Construction
Input: K arms with associated gaps: A1, 2,...
Initialize: Exploration set S = 0.
Let A be the list of arms sorted ascending order of their associated gaps.
for i E A do
Add S for E (No do remove j from A end for end for Output: S
only need recompute it only when the order of the estimated suboptimality gaps changes. The exploration set S, has several useful properties, as shown in Proposition below.
Proposition 1. Let EV be a directed feedback graph on arms with self-loops. and let Ái,..., Âg be a sequence of suboptimality gaps estimates. Let $ be the exploration set constructed by Algorithm 2 based on the sequence of suboptimality gaps. Then S is dominating set G with the following property: for all V there exists Furthermore, S is also a strongly independent set of
such that i E (j) and Â S Å.
Proof. Let S be the output Algorithm 2. Since G contains self-loops, if E S, then i Noot (i) and Á; S Å. i & S, then was removed from A because i E (jo for some j that, previous iteration, was added to S. Since j was considered before i, we must have Å I Å, Now, for all j. E 5,, know by construction that j Noout (i). Thus (i,j) is not directed edge in G, and so S is a strongly independent set in G.
We define the exploration rates round in terms of the exploration set S,, which is constructed using the aforementioned procedure. For all arms in V,
1 1
Ann
6, min
2K
2V
tK2
Et,b
(2)
for some constant À E [1, K] and where εt.; depends on whether i S₁ or not:
(8Int))(+A?,.)
if S,
G.
4/12.
otherwise,
where / >> 0 is constant. The role of E changes depending on whether we are in an adversarial or stochastic environment. In an adversarial environment, we use 4/t² < Çt,i to ensure that we sample each arm with small positive probability, which is essential to bound the second-order term
in the regret bound in terms of the independence number. Note that Sτ, S / A choosing ensures that the cost of exploration is bounded by Ö(VaT)) In the stochastic environment, the construction of the exploration set and the choice of É.i ensure that, at each round I, each E V observed with probability least (3 In tntt//(ee (tå{) independently of whether i is in the exploration set at round E.
Formally, our procedure ensures that we can lower bound the probability with which any arm is observed. In the algorithm we use Pt,; = (á E Nout (It) to denote the probability that arm is observed at round We lower bound this quantity by only considering the minimum rate at which each arm is observed according to the exploration rate ε,, and our construction the exploration sets. We use ot, denote that quantity, and we have for all and
1
Aln K
31t
Prs 2 ot, = min
(4)
2K
2
tK

---

The definition of Oz.s uses that St is a dominating set. The difference between εt,; and ot,i is key to take advantage of the graph structure. First, we need lower bound or, to ensure that enough observations (counted by Oz,; in Algorithm 1) are made for each arm, such that our gap estimates are reliable. Simultaneously, we upper bound εt,i to ensure that the extra exploration not too costly. Here we benefit from the fact that S, is strongly independent set on G.
We ensure that all arms get sufficiently many observations and derive the following concentration bounds on the gap estimates D., computed by Algorithm Concentration of the gap estimates around the true gaps is crucial for bounding the regret in the stochastic setting.
Lemma 1. If Algorithm I is run with parameters & 2 3, 3 2 64(7 + 1) 2 256, and exploration rates Es,s. such that for all t 2 and i V, Pt, satisfies equation for some X E [1, K]. then for all E V and 2 1,
A 2 A
Ktt-I*
Furthermore, for any arm with A, > 0 let bmin (1) == max
12 120:3
0:
Aln K IK
8lat 12;
Then for
any arm with A; > O andd t 2 Emii (2),
1 S
Int
7-2
2
1
P
+
2
(5)
Kt
1
proof of the lemma is provided in Appendix C.
We run the algorithm with y = 4 and | 64(7 + 1) = 320 which is a different parameterization from the EXP3++ algorithm (Seldin and Lugosi, 2017), which 7 3 and /3 = 256. Picking larger value of y means that the confidence intervals are slightly larger, which allows us to obtain a better dependency the suboptimality gaps.
Indeed, under the same assumptions as Lemma 1, i = 4 and t 2 tmin (i), we have that
(Int)
Int
(Int)
(Int)
1
AA In K 1
AAn
implying
6
4K2
I
PA
14
4K2
I
14K233"
Adversarial Analysis
Our result for the adversarial regime generalizes the analysis of both Alon al. (2017) and Alon et al. (2015) as we derive a bound that depends on the both the independence number and the strong independence number simultaneously. In order to do so, define the quantity:
PEs
0₂ =
(6)
PE
VEV
which is the sum of the ratios of the probability of playing an arm to the probability of observing its loss. Bounding this sum of ratios is key to obtain dependency on graph quantities, and Alon et al. (2017) and Alon et al. (2015) respectively bound equation (6) in terms of the strong independence number (Lemma 8) and the independence number (Lemma 7) at the cost of logarithmic factor. By defining the learning rate in terms of 0, is possible to obtain both bounds simultaneously.
Theorem 2. Assume that Algorithm I is run with a directed feedback graph G (V, E), with K
learning rate The V 22 02 and the exploration rate defined in (2) with y 4, and 3 320. For any X E [i, (ā, I)),,, the pseudo-regret against any oblivious loss sequence satisfies
Rr < min Kn K /n (KT) + +2K,
where K [V], is the independence number G and â is its strong independence number:
On undirected graphs, the first part of the bound is always smaller, and it matches the bound of Alon et al. (2017). This implies that in the adversarial regime we are not paying price for the extra guarantees that we derive the stochastic regime. On directed graphs, if the difference between a and ā is large, the second half of the bound may be advantageous. Furthermore, note that the extra
7

---

logarithmic factor is only of order Vln(T), which is slight improvement on the In T dependency of Alon al. (2015).
We give a sketch of the proof here and defer the detailed proof to Appendix B.
Proof sketch. We separate the first K rounds, in which the algorithm plays deterministically, from the remaining rounds, where we bound separately the contributions the regret from the exponential weights and from the extra exploration. To bound the contribution of the extra exploration, we use that
εx,i S 1 V Aln for all i and meaning that the extra exploration contributes at most O(v XT In K) EK
to the regret. For bounding the contribution of the exponential weights the regret, we follow the standard analysis of EXP3 with time varying learning rate (Bubeck and Cesa- Cesa-Bianchi, 2012). We bound the second order term by exploiting the fact that it. and ft,i are close to each other because εx S 2K for all and This allows us to bound the second order term in terms of Or, which simplifies with the learning rate. This quantity can be bounded by the strong independence number of the graph (Lemma 10 Alon al. (2017) or the independence number of the graph at the cost of logarithmic factor (Lemma 5 Alon et al. (2015)), which gives the two parts of the bound.
5 Stochastic Analysis
In the stochastic regime, tuning À affects the tightness of the bound. If the learner has knowledge of the independence and strong independence numbers but does not know the time horizon, picking safe choice ensure that Theorem 2 holds.
Our result for the stochastic regime is given in the following theorem.
Theorem 3. Lei G - (V, E) be a directed feedback graph with K = |V] and independence number and strong independence number ā. Under the same conditions as in Theorem 2 and choosing À a, the pseudo-regret of Algorithm against any stochastic stochastic loss sequence, satisfies:
43 (Im
RT
max IndEZ(C)
Σ
+ 2a In
A:
(iElad:
A.70
16K
1020
3K Amin
3/2
A
A
min
where I(G) is the collection of all strongly independent subsets of G.
We remark that the last two terms do not depend on T. Moreover, the leading coefficient of the scaling with (In 2) sums over independence (as opposed summing over the entire action set). The lower bound for this problem scales as O2(c* In,, where c* is a graph dependent quantity which takes the size of the suboptimality gaps into account (Buccapatnam Compared to that, our result is suboptimal by a logarithmic factor and our dependency on the strong independence number of G is weaker. The algorithms of Buccapatnam et al. (2014, 2017) and Cohen et al. (2016) almost match the lower bound, but their elimination based structure prevents them from being applicable best-of woth-worlds settings. In the undirected case, we obtain the same dependence on 7' and the set of arms as the UCB-N algorithm analysed by Lykouris et al. (2020).
al., 2014).
We provide sketch of the proof here. The detailed version can be found in Appendix D.
The pseudo-regret can be decomposed by treating the first bmin rounds like in the adversarial case, and by using refined bound for the stochastic regime in the remaining rounds.
Proof sketch. Let Emin = max;AA, (fmin = max t 1220:30 aann 2K2
S Alnt
122
RT Rimin + Σ Σ
A, prol S Remin + Σ
Σ
+E
(-dnit V: A:A
A=Amin 1: A:50
(In
2
Note that fmin time independent: bmin D
for positive constant e, therefore,
K
K
R Coyar funin log (Imin) = C₁
[n
A
Amin
min
8

---

where the first equality follows from the second part of the bound presented in Theorem 2 and Co. C1 are universal constants. After the initial min rounds, enough observations on all arms have been gathered to ensure with high probability that the gap estimates of all arms are close to their true gaps, as stated Lemma These concentration inequalities allow us to show that the two following propositions hold.
Proposition 2 (informal). The contribution of the exponential weights to the pseudo-regret can be bounded as:
K
Σ
Σ
AE S2 E +0(al)))
A
I=tmin i: A,20
i:A.00
for universal constant Cz.
Proposition (informal). The contribution of the extra exploration to the pseudo-regres can be bounded as:
ln T A;
Σ tniin A:
Σ (R [=,)=
max IndEZ(C)
Σ
+ aalnn? In
LieInd: A,20
Formal statements and proofs of the above propositions are in Appendix D. These propositions ensure that after lmin steps the exponential weights of all suboptimal arms are small, the extra exploration ε achieves the correct rate, and that the sum of the probabilities that the suboptimality gap estimates fail in any of the rounds is of order (a In T). Applying these propositions Equation (7) finishes the proof.
Our approach bound the pseudo-regret in the initial rounds differs from the one of Seldin and Lugosi (2017) as we take advantage of the adversarial bound in these rounds. (Mourtada and Gaïffas (2019) used similar approach to derive best-of-both worlds guarantees for the Hedge algorithm.) This refinement improves upon the result of Seldin and Lugosi (2017) by replacing Σ.A,>0 A with
(numerical constants ignored) in the time indeieddeenddnt part of the bound.
A
For instances where the independence number and the strong independence number are close to each other, in particular in the case of undirected graphs, the analysis of the initial rounds be improved by using the first part of Theorem 2, which depends on & rather than the second part, which depends on when bounding the regret the initial tmin rounds.
Corollary 1. Let (V, E) be directed feedback graph with K [V| and strong independence number & Under the same conditions as Theorem 2, the pseudo-regret of Algorithm against any stochastic stochastic loss sequence, satisfies:
R S
max Inde2(G))
43 (In (l)
A
+ 2āhn+
Σ
16K
A
1613K
2
In
VBK Amin
LiElud:
A:20
1AA
min
Extension to Time Varying Feedback Graphs
The results presented in Theorem 3 and Corollary assume that the learner has knowledge of the independence and strong independence numbers of the graph. Computing those numbers are NP-hard problems, which could lead to prohibitively large computation times. This is particularly true if one considers natural extension of our results to the setting where the feedback graphs are allowed to change over time.
We consider setting where oblivious adversary chooses feedback graph at each round and the algorithm observes the graph at the beginning of the round. In the stochastic regime, the knowledge of the full feedback graph is required at the beginning of the round in order to construct the exploration set.
As we do not know the independence numbers ahead of time, we tune the exploration rates defined in equation (2) with À to ensure that the exploration never too large. This exploration rate allows us to apply Lemma 1 with À 1, and derive the following result.

---

Theorem 4. Assume that Algorithum 1 is run sequence of arbitrarily generated feedback graphs G1, G2.... with learning rate Tit V 2
/
K and exploration rates defined in (2) and (3) with
7 and B 320. Then the pseudo-regret against any oblivious loss sequence satisfies
T Σ
Ry min
Σ ai In,, 9v K in
at
+
2K,
where for all 1. 2 1, Og and ãi are the independence and strong independence numbers of G.. Simultaneously, the pseudo-regrel against stochastic losses satisfies:
43
Rr S inf OSNST
max SCV:
Σ
+
A
LIESAA,>O >0
16K
1613K3/2
VBK
+ +
Σ
In
A:
A min
Amin
iA:20
where An is the th largest element in the set containing the strong independence number of all the Go for t T.
A proof of this theorem is provided in Appendix E.
In the adversarial regime, adapting to graphs that change over time is seamless and does not come any cost, as using a sequence of fixed graphs exactly recovers the bound of Theorem 2. In the stochastic regime, using À = allows to obtain the same tight constants in Corollary 1, and only comes at the cost of multiplicative VK factor in the last term of the bound. Furthermore, the first term of the bound is sum over the An arms that have the smallest non-zero suboptimality gaps. In the case of undirected graphs, we upper bound the infimum by taking n = O, we have gaps achieved by Cohen et al. (2016),
ag max (a(G.)) which matches the dependency
who got an O ye Eies In A.
bound. This trick is particularly useful if most of graphs have small strong independence number and very few have a large independence number, as we can consider the graphs that have large independence number separately at the cost of an additive constant and in return the dominating term will scale with the strong independence number of the remaining graphs, which may be much smaller.
Conclusion
Erez and Koren (2021) left open the following questions: is it possible to achieve cast-ofbboth-worddd regret bounds in terms the independence number, and can the dependence on T in their regret bounds be improved? We partially answered these questions with the EXP3.G+ algorithm and derived near-optimal depend the independence number of the feedback graphs and improve upon the results of Erez and Koren (2021) by poly-logarithmic factors in both the adversarial and stochastic regimes. Furthermore, we extended our results time-varying feedback graphs with a computationally efficient algorithm.
sit-off-bot-worlldd guarantees for directed feedback graphs. Our regret bounds
Acknowledgments and Disclosure of Funding
CR and YS acknowledge partial support by the Independent Research Fund Denmark, grant number 9040-00361B, DvdH and NCB gratefully acknowledge partial support from the MIUR PRIN grant Algorithms,, Games, and Digital Markets (ALGADIMAR), the EU Horizon 2020 ICT-48 research and innovation action under grant agreement 251847, project ELISE (European I Learning and Intelligent Systems Excellence), and the project "One Health Action Hub: University Task Force for the resilience of territorial ecosystems" funded by Università degli Studi di Milano.
10

---

References
Noga Alon, Nicolò Resa-BBancch, Ofer Dekel, and Tomer Koren. Online learning with feedback Beyond bandits. In Proceedings of the International Conference Computational Learning Theory (COLT), 2015.
graphs:
Noga Alon, Nicolò Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing. 2017.
Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir.
Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2016.
Peter Auer, Nicolò Desa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal of Computing, 2002.
Sébastien Bubeck and Nicolò Bessa-Binnchi. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends in Machine Learning, 2012.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: stochastic and adversarial bandits. Proceedings of the International Conference on Computational Learning Theory (COLT), 2012.
Swapna Buccapatnam, Atilla Eryilmaz, and Ness B. Shroff. Stochastic bandits with side observations on networks. Association for Computing Machinery, 2014.
Swapna Buccapatnam, Fang Liu, Atilla Eryilmaz, and Ness B. Shroff. Reward maximization under uncertainty: Leveraging side-observations on networks. Journal of Machine Learning Research, 2017.
Stéphane Caron, Branislav Kveton, Mare Lelarge, and Smriti Bhagat. Leveraging side observations in stochastic bandits. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2012.
Nicolò Press, 2006.
and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University
Ioannis Chatzigeorgiou. Bounds on the lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 2013.
Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feedback graphs without the graphs. In Proceedings of the International Conference on Machine Learning (ICML), 2016.
Liad Erez and Tomer Koren. Towards best-of-all-worlds online learning with feedback graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Tim van Erven, Wouter M. Koolen, and Dirk van der Hoeven. Metagrad: Adaptation using multiple learning rates in online learning. Journal of Machine Learning Research, 2021.
Emmanuel Esposito, Federico Fusco, Dirk van der Hoeven, and Nicolò Cesa-Bianchi Learning on the edge, online learning with stochastic feedback graphs. In Advances Neural Information Processing Systems (NeurIPS), 2022.
Pierre Gaillard, Gilles Stoltz, and Tim van Erven. A second-ordes bound with excess losses. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2014.
Dirk van der Hoeven, Federico Fusco, and Nicolo Cesa-Bianchi. Beyond bandit feedback in online multiclass classification. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Shinji Ito. Parameter-free free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2021.
Shinji Ito, Taira Tsuchiya, and Junya Honda. Nearly optimal best-of-both-woond worlds algorithms for online learning with feedback graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
11

---

Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic MDPs with known transition. In Advances Neural Information Processing Systems (NeurIPS), 2020.
Tiancheng Jin, Longbo Huang, and Haipeng Luo. The best of both worlds: Stochastic and adversarial episodic MDPs with unknown transition. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Wouter M Koolen, Peter Grünwald, and Tim Van Erven. Combining adversarial guarantees and stochastic fast rates in online learning. Advances in Neural Information Processing Systems (NeurIPS), 2016.
Chung- Wei Lee, Haipeng Luo, Chen Yu Wei, Mengxiao Zhang, and Xiaojin Zhang. Achieving near onstance-optimaalty and minimax minimax-optimalig in stochastic and adversarial linear bandits simultaneously. In Proceedings of the International Conference on Machine Learning (ICML), 2021.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and Computation, 108, 1994.
Thodoris Lykouris, Éva Tardos, and Drishti Wali. Feedback graph regret bounds for Thompson Sampling and UCB. Proceedings of Machine Learning Reseurch, 2020.
Shie Mannor and Ohad Shamir. From bandits experts: On the value of side-observations. In Advances in Neural Information Processing Systems (NeurIPS), 2011.
Teodor V. Marinov, Mehryar Mohri, and Julian Zimmert. Stochastic online learning with feedback graphs: Finite-time and asymptotic optimality. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
Saeed Masoudian and Yevgeny Seldin. Improved analysis of the Tsallis algorithm in stochas- tically constrained adversarial bandits and stochastic bandits with adversarial corruptions. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2021.
Jaouad Mourtada and Stéphane Gaiffas. On the optimality of the hedge algorithm in the stochastic regime. Journal of Machine Learning Research, 20, 2019.
Jeffrey Negrea, Blair Bilodeau, Nicolò Campolongo, Francesco Orabona, and Dan Roy. Minimax optimal quantile and semi-adversarias regret via root-logarithmic regularizers. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Francesco Orabona. A modern introduction to online learning. CoRR, 2019.
Chloé Rouyer and Yevgeny Seldin. Tsallis-NN for decoupled exploration and exploitation in multi- armed bandits. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2020.
Chloé Rouyer, Yevgeny Seldin, and Nicolò Cesa- Bianchi. An algorithm for stochastic and adversarial bandits with switching costs. In Proceedings of the International Conference Machine Learning (ICML), 2021.
Yevgeny Seldin and Gábor Lugosi. An improved parametrization and analysis of the EXP3+ algorithm for stochastic and adversarial bandits. Proceedings of the International Conference on Computational Learning Theory (COLT), 2017.
Yevgeny Seldin and Aleksandrs Slivkins. One practical algorithm for both stochastic and adversarial bandits. In Proceedings of the International Conference on Machine Learning (ICML), 2014.
Yevgeny Seldin, Peter L. Bartlett, Koby Crammer, and Yasin Abbasi- Yadkori. Prediction with limited advice and multiarmed bandits with paid observations. In Proceedings of the International Conference Machine Learning (ICML), 2014.
William R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25, 1933.
12

---

Tobias Sommer Thune and Yevgeny Seldin. Adaptation to easy data in prediction with limited advice. In Advances Neural Information Processing Systems (NeurIPS), 2018.
Chen-Ye Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the International Conference on Computational Learning Theory (COLT), 2018.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
Julian Zimmert and Yevgeny Seldin. Tsalli- An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 2021.
Julian Zimmert, Haipeng Luo, and Chen- Yu Wei. Beating stochastic and adversarial cani-bandits optimally and simultaneously. In Proceedings of the International Conference on Machine Learning (ICML), 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes] All the results claimed the abstract have proofs either in the main body appendix.
(b) Did you deseribe the limitations of your work? [Yes] For each result state the parameters under which the result holds.
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work primarily theoretical and we do not foresee any potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Although some proofs may only appear in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "Y1GhdPD_paM", "reviewer": "Reviewer_VD7D", "summary": "This paper studies the multi-armed bandit problem with graph feedbacks where the learner would receive the loss information of all the arms $j$ that $e(i,j) \\in G$ after selecting arm $i$, where $G$ here is the feedback graph. The proposed algorithm aims at achieving the best of both worlds guarantee, that is, achieving $\\widetilde{O}(\\log T)$ regret with stochastic losses while ensuring worst-case robustness $\\widetilde{O}(\\sqrt{\\alpha T})$ where $\\alpha$ here is s the independence number of the feedback graph. \n\nThe idea of the proposed algorithm originates from the EXP3++ algorithm for stochastic and adversarial bandits, which achieves the near-optimal best of both worlds result for normal multi-armed bandits. To extend the EXP3++ algorithm to the graph feedback setting, the learner takes the idea of EXP3.G which was designed only for adversarial graph feedback, and build up a novel exploration scheme to carefully estimate the gaps, in order to control the magnitude of exploitation and exploration. \n\n", "questions": "1. Though the $\\frac{1}{\\Delta^2}$ term in Theorem 3 seems inevitable (as it also appears in EXP3++), is it possible to drop this term as the some best of both worlds results of MAB (including BROAD of Wei and Luo (2018) and Tsallis-INF of Zimmert and Seldin (2019)) do not have this term. \n\n2. Is it possible that SAPO approach could achieve better regret bounds? ", "limitations": "None. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper shows that the best of both worlds guarantee can be achieved by EXP3++ approach for weakly observable feedback graphs. Moreover, it seems that the algorithm can achieve $O(\\sqrt{\\alpha T})$ regret for adversarial losses while having more logarithmic terms for the stochastic setting. The specific contribution is the new exploration scheme and may be applied in other questions. \n\nThis paper does not have any specific weakness. The writing is clean and well-organized. ", "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": "NkK-YOP4Ds", "reviewer": "Reviewer_jtPY", "summary": "This paper considers online learning with feedback graphs and present an algorithm achieving (almost) best-of-both-world regret bounds in stochastic and adversarial environments. The core idea is a combination of the EXP3++ algorithm (providing adaptivity between regime) and the EXP3.G algorithm (exploiting feedback graphs) and a novel exploration scheme which exploits the structure of the graph. The results are extended to the time-varying feedback graphs.\n", "questions": "- Pseudo codes Algorithms 1 and 2 are not clear when standing alone: it might be better if it is indicated clearer where Algorithm 2 (and Equations (2)-(3)) is injected to Algorithm 1.\n\n- It is a little bit confusing that in Line 216, the observability probability is said to be lower bounded by  $(\\beta \\log t) / (t \\hat{\\Delta}^2 )$ in the stochastic case but then in Equation (4), it suggests that this might not be the case in general. My understanding for this is that in stochastic case, we can tune the parameters such that $(\\beta \\log t) / (t \\hat{\\Delta}^2 )$ is indeed the minimum of the 3 terms of (4), is this correct? \n\n- The wording in Theorem 2 makes it seem unnecessarily limited: from proofs in Appendix B, results of Theorem 2 should work with any gamma and beta such that epsilon = 1/2 $\\sqrt(\\lambda \\log K/ (t K^2))$, right? The specific choice of gamma and beta is for the purpose of achieving the bounds in Theorem 3, right? Personal opinion: one theorem covering 2 cases (such as Theorem 4) would be preferable. \n\n- The statement that the complexity of Algorithm 2 is O(K^3) seems a little bit overkilled, should it be O(K^2) instead (given an efficient sorting algorithm O(KlogK)? It seems that this is related to the \"minimum weight cover set problem\" so it might be interesting to look into the literature to reduce the complexity further. \n\n- A small speculation: Section 6 deals with the time-varying feedback graphs in an informed setting. I wonder if this can be extended even further to the case of uninformed setting, e.g., by bounding with MAS number similarly to Alon, Noga, et al. \"Nonstochastic multi-armed bandits with graph-structured feedback.\"  (2017) or at least in some special cases where the precise graphs are unknown when making decisions but we know that they belong to a certain class such as in Vu et al. Path Planning Problems with Side Observations-When Colonels Play Hide-and-Seek (2020) (note that these references are not cited in the current version). \n\n", "limitations": "the authors 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": "Strengths: The paper is well written and easy to follow. The results are interesting and in my opinion, contribute significantly to the community. While the proposed algorithm is built upon previously known algorithms, the presented exploration scheme is, as far as I know, novel and provides interesting insight. \n\nWeakness: No significant weaknesses. Two minor comments/suggestions: 1) It seems that there is still room to improve the complexity of Algorithm 2; 2) some numerical experiments comparing the proposed algorithm with non-adaptive benchmarks (showing the trade-off of adaptivity and performance) could be interesting. \n\n\n\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": "JbUfn_PB0Vk", "reviewer": "Reviewer_5QMT", "summary": "This paper considers the problem of achieving best-of-both-worlds guarantees in the bandits with graph feedback. Specifically, the authors propose an algorithm based on a combination of EXP3.G [Alon et al., 2015] designed for classic bandits with graph feedback problem and EXP3++ [Seldin et al., 2017] designed for getting best-of-both-worlds for MAB. In the adversarial environment, they achieves $\\tilde{O}(\\sqrt{\\alpha T})$ near optimal regret and $O(\\max_I \\sum_{i\\in I}(\\frac{\\ln^2 T}{\\Delta_i}))$ regret bound. The algorithm can also be extended to the time-varying feedback graph setting and achieve the corresponding regret bounds in both the adversarial and the stochastic setting.", "questions": "- Could the authors explain more about the relationship between the obtained regret bound in the stochastic environment and the instance optimal regret bound in this environment?", "limitations": "Yes, the authors addressed the limitations of the work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is very well written and the designed algorithm is intuitive and well explained.\n- This paper improves upon the previous work by [Erez and Koren 2021] in both the adversarial regret bound and stochastic regret bound. Specifically, in the adversarial environment, the obtained regret bound is optimal ignoring logarithmic factors.\n- From the algorithm perspective, the algorithm generalizes the EXP3++ algorithm, which works for MAB problem, to graph bandits with a new specific exploration set, which is a maximal independent and dominating set constructed according to the empirical gap.\n- I checked the proofs for each theorem in the main text and the appendix and they look correct to me.\n\n\nWeakness:\n- One issue is about the optimality of the regret bound in the stochastic environment. I thought that the instance-optimal regret bound in the stochastic graph bandits is O(c\\ln T) with c defined by an optimization problem with respect to the graph structure. I wonder how large the gap is between the instance-optimal regret bound and the bound derived in this paper?\n\n- One minor issue concerns me is the novelty of this paper as the algorithm generalizes the EXP3++ algorithm with a new but intuitive exploration over the nodes. Based on the exploration, it can be shown that each node can be explored with probability $1/t\\hat{\\Delta}_i^2$ as some node with smaller gap will be chosen in the exploration set according to the construction. For the other derivations, they seem similar to the analysis in [Alon et al., 2015] and [Seldin et al., 2017].\n\n- Another minor issue I do not understand is that why the results presented by the author for the fixed graph setting has $\\tilde{\\alpha}$ dependence in the adversarial regret bound while this can indeed be improved to $\\alpha$ as shown in the appendix with an additional $\\ln T$ factor. I think here the improvement from $\\tilde{\\alpha}$ to $\\alpha$ is more important as this could be an improvement of a factor of $K$ for some specific graph.\n\nTypos:\n- line 483: $\\alpha_s$ -> $a_s$\n- line 575-576: The first inequality should be $\\leq\\frac{1}{2}n\\lambda$ instead of $\\geq n\\lambda$.\n- line 632: $1+\\ell_{s,i^*}$ -> $1+\\tilde{\\ell}_{s,i^*}$", "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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "CTzhPx9_Ap1", "reviewer": "Reviewer_TM6a", "summary": "This paper studies online learning in a new setting of directed graph feedback. By combining the ideas of EXP3++ and EXP3.G, they suggest an algorithm, EXP3.G++ that can achieve near-optimal regret bound in both stochastic and oblivious adversarial settings.", "questions": "Can the authors commend on the performance of EXP3.G++ in extreme cases of bandit and full information? \n\nCan the authors commend the applications of graph feedback (especially directed graph feedback) in real-world situations?\n", "limitations": "There is no potential negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I enjoyed reading the paper and all the results are sound and well presented. The regret bound for both adversary and stochastic settings improves the previous results (Erez and Koren (2021)) by log(T) factors and achieves a near lower bound guarantee. Further, the authors also provide an extension for changing the feedback graphs and provide a regret bound for EXP3.G++ in this case.", "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