Understanding Bandits with Graph Feedback
Authors: Houshuang Chen
Zengfeng Huang
Shuai Li
Chihao Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandits
Graph feedback
Online Learning

Abstract: The bandit problem with graph feedback, proposed in [Mannor and Shamir, NeurIPS 2011], is modeled by a directed graph $G=(V,E)$ where $V$ is the collection of bandit arms, and once an arm is triggered, all its incident arms are observed. A fundamental question is how the structure of the graph affects the min-max regret. We propose the notions of the fractional weak domination number $\delta^*$ and the $k$-packing independence number capturing upper bound and lower bound for the regret respectively.  We show that the two notions are inherently connected via aligning them with the linear program of the weakly dominating set and its dual --- the fractional vertex packing set respectively. Based on this connection, we utilize the strong duality theorem to prove a general regret upper bound $O\left(\left(\delta^*\log  |V|\right)^{\frac{1}{3}}T^{\frac{2}{3}}\right)$ and a lower bound $\Omega\left(\left(\delta^*/\alpha\right)^{\frac{1}{3}}T^{\frac{2}{3}}\right)$ where $\alpha$ is the integrality gap of the dual linear program. Therefore, our bounds are tight up to a $\left(\log |V|\right)^{\frac{1}{3}}$ factor on graphs with bounded integrality gap for the vertex packing problem including trees and graphs with bounded degree. Moreover, we show that for several special families of graphs, we can get rid of the $\left(\log |V|\right)^{\frac{1}{3}}$ factor and establish optimal regret.

Understanding Bandits with Graph Feedback
Houshuang Chen
Zengfeng Huang
Shanghai Jiao Tong University cherhoushuangg? jtu edu.
Fudan University huangzff fudan. edu.
Shuai Li
Chihao Zhang
Shanghai Jiao Tong University shuaili8@s ftu.iiiusst.ueuuuc...
Shanghai Jiao Tong University chihaols jtu. edu. cn
Abstract
The bandit problem with graph feedback, proposed in [Mannor and Shamir, NeurIPS 201 1], modeled by directed graph collection of bandit arms, and once an arm is triggered, all its incident arms are observed. fundamental question is how the structure of the graph affects the min-max regret. We propose the notions of the fractional weak domination number and the k-packing independence number capturing upper bound and lower bound for the regret respectively. We show that the two notions are inherently connected via aligning them with the linear program of the weakly dominating set and its dual the fractional vertex packing set respectively. Based this connection, we utilize the strong duality theorem to prove a general regret upper bound O ((6- log V T3 and lower bound Ω (8*/aa /a) T where a is the integrality gap of the dual linear program. Therefore, our bounds are tight up to (log [V]) factor on graphs with bounded integrality gap for the vertex packing problem including trees and graphs with bounded degree. Moreover, we show that for several special families of graphs, we can get rid of the (log [V]) factor and establish optimal regret.
(V, F)) where V the
Introduction
The multi-armed bandit is an extensively studied problem in reinforcement learning. Imagining player facing an n-armed bandit, each time the player pulls one of the n arms and incurs a loss. At the end of each round, the player receives some feedback and tries to make better choice in the next round. The expected regret defined by the difference between the player's cumulative losses and cumulative losses of the single best arm during T rounds. In this article, assume the loss each round is given in an adversarial fashion. This is called the adversarial bandit in the literature. The difficulty of the adversarial bandit problem is usually measured by the min-max regret which the expected regret of the best strategy against the worst possible loss sequence.
Player's strategy depends on how the feedback is given at each round. One simple type of feedback is called full feedback where the player can observe all arm's 's losses after playing an arm. An important problem studied in this model is online learning with experts [14. 17). Another extreme, introduced in [8], is the vanilla bandit feedback where the player can only observe the loss the arm he/she just pulled. Optimal bounds for the regret, either in in T, are known for both types of feedback.
The work of [24] initialized the study on the generalization of the above two extremes, that is, the feedback consists of the losses of collection of arms. This type of feedback can be naturally described by a feedback graph where the vertex set is [n]] and directed edge (i,j) means pulling
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

the arm can observe the loss of arm j. Therefore, the "full feedback" means that G is clique with self-loops, and the "vanilla bandit feedback" means that consists of n disjoint self-loops.
natural yet challenging question is how the graph structure affects the min-max regret. The work of [1] systematically investigated the question and proved tight regret bounds in terms of the time horizon T. They show that, if the graph is "strongly observable", the regret is O(Tà); if the graph is "weakly observable", the regret is @(T3), ); and if the graph is "non-obscrvable., the regret is (()). Here the notions of "strongly observable", "weakly observable" and "non-observablee" roughly indicate the connectivity of the feedback graph and will be formally defined in Section 2. However, unlike the case of "full feedback" or "vanilla bandit feedback", the dependency of the regret on or more generally on the structure of the graph, is still not well understood. For example, for "weakly observable" graphs, an upper bound and a lower bound of the regret in terms of the weak domination number 8(G) were proved in [1], but a large gap exists between the two. This suggests that the weak domination number might not be the correct parameter to characterize the regret.
We make progress on this problem for "weakly observable" graphs. This family of graphs is general enough to encode almost all feedback patterns of bandits. We introduce the notions of the fractional weak domination number 8* (G), the k-packing independence number and provide evidence to show that they are the correct graph parameters. The two parameters are closely related and help us to improve the upper bound and lower bound respectively. As the name indicated, 6" d'( is the fractional version of ö(G), namely the optimum of the linear relaxation of the integer program for the weakly dominating set. We observe that this graph parameter has already been used in an algorithm for "strongly observable" graphs in [3], where it functioned differently. In the following, when the algorithm is clear from the context, we use R(G, T)) to denote the regret of the algorithm on the instance G in T rounds. Our main algorithmic result is:
Theorem 1. There exists an algorithm such that for any weakly observable graph, any time horizon T 2 n² log(n)/8** (G). its regret satisfies R(G,T) = O (0 (G) (G) log T3)
Note that the regret of the algorithm in [1] satisfies R(G, O (6(G) log m)* 7 The frac- tional weak domination number 8* is always no larger than 6, and the gaps between the two can be as large as O(log rz). We will give an explicit example in Section 4.3 which the gap matters and our algorithm is optimal. Theorem can be seamlessly extended to more general tire-varying graphs and probabilistic graphs. The formal definitions of these models are in Appendix E.
On the other hand, we investigate graph structures that can be used to fool algorithms. We say set S of vertices is a k- k-packing independent set if S is an independent set and any vertex has at most out-neighbors in S. We prove the following lower bound:
Theorem 2. Let G = (V, be directed graph. If G contains a k-packing independent set S with [S] 2 2, then for any randomized algorithum and any time horizon T, there exists a sequence of loss
functions such that the expected regret is Z max
[S] log } .
For every & E N, we use St. the k- t-packing independence number, to denote the size of the maximum k-packing independent set. To prove Theorem 2, we reduce the problem of minimizing regret to statistical hypothesis testing for which powerful tools from information theory can help.
We can use Theorem 2 to strengthen lower bounds in [1]. Besides, we show that large 8* usually implies large ÇI via studying the linear programming dual of fractional weakly dominating sets and applying novel rounding procedure. This is also one of our main technical contributions. Combinatorially, the dual linear program to find the maximum fractional vertex packing set the graph. Specifically, we can establish lower bounds in terms of 8* by applying Theorem 2:
Theorem 3. If G is weakly observable, then for any algoritium and any sufficiently large time horizon 1/3
T E N. there exists a sequence of loss functions such that R(G,T)= = ((*) -T where a
=(((
the integrality gap of the linear program for vertex packing.
Clearly the exact lower bound is determined by the integrality gap of a certain linear program. In general graphs, we have universal upper bound O (n/8*). For concrete instances, we can

---

obtain clearer and tighter bounds on a. For example, the linear program has a constant integrality gap a on graphs of bounded degree.
Corollary 4. Lel A N be a constant and Ga be the family of graphs with maximum in-degree A. Then for every weakly observable G = (V, E) E Ga. any algorithm and any sufficiently large time horizon T E N. there exists sequence of loss functions such that R(G, T) = (2((5)) T)
We also show that for 1-degenerate directed graphs (formally defined in Section 2.1). the integrality gap is 1. This family of graphs includes trees and directed cycles. As consequence, we have
Corollary 5. Let G be a 1-degenerate weakly observable graph. Then for any algorithm and any sufficiently large time horizon T E N, there exists a sequence of loss functions such that R(G, = -((())) ).)).
Comparison of previous results and our results
In Table I, compare our upper bounds, lower bounds and their gap with previous best results.
Table 1: A comparison of results
Previous best results [1]
This work
Graph Type
Min-max regret
Gap
Min Min-max regret
Gap
o (6 log n) T
O (5" log n) 3 T
See discussion below
See discussion below
General graphs
Ω max { () 11 T8
Ω max {1 + T
for d = log" n:
for 8 log² n: Ω (T))
O (logn)
Ω log log n T
O
lng n log log
Trees Bounded in-degree
Same as general graphs
O (logn)
0 (6 log n) 1) T2/3)
o (log (1/3))
Ω ((5)) 1/3 //3 T2/3)
Complete
O (logn)1/83 T2235)
o (log m)
+ ((lg n)/33 T2(33
0(1)
bipartite graphs
Ω (T2/3)
Orthogonal
O (logn)22 .T/33)
o (log m)
((log)) T2/33
(
relation on F2 Ω (T2/3)
Discussion, In general, our upper bound is never worse than the previous one since S Our lower bound is not directly comparable to the previously known lower bound they are stated in terms of different parameters. In fact, we can not find an instance such that our lower bound Ω ((max(L1 (8* /a))//5) is worse than the previous lower bound [(max 1, (8/(log (8)(log)))) /))))))))))))))))))))) and there are instances on which our bound outperforms The two key quantities, namely the integrality gap of the primal linear programming and the integrality gap of the dual linear programming, seem to be correlated in a graph. The relation between the two bounds is worth further investigation.
Related work
The multi-armed bandit problem originated from the sequential decision making under uncertainty studied in [34, 6] and the adversarial bandit a natural variant introduced by [7]. The work of [24] introduced the graph feedback model with a self-loop the full feedback and bandit feedback settings. This model has been extensively studied in the work of [24, 4, 20, 3]. The work of [1] removed the self-loop assumption and considered generalized constrained graphs. They gave a full characterization of the mini-max regret in terms of the time horizon T. In contrast fixed graph feedback, recent work of [20, 15, 2, 32] considered the time- varying graphs. Another line of recent work in [22, 23, 3] is to study random graphs, or the graphs with probabilistic feedback.
each vertex in order to interpolate between
Most algorithms for adversarial bandits are derived from the EXP3 algorithm, e.g. [9, 29]. However, even for the vanilla multi-armed bandit problem, direct application of EXP3 can only get an
3

---

upper bound of O (Vn log n. T) [9], which is suboptimal. In fact, the EXP3 is special case of online stochastic mirror descent (OSMD) algorithm when using negentropy function as the potential function. OSMD was developed by [26] and [27] for online optimization. By choosing a more sophisticated potential function, namely the 1/2-Tsallis entropy function [33], OSMD can achieve the tight bound θ (vnII [35].
The idea of using domination number or related parameters to study the feedback graph appeared many times in literature, e-g. [1, 12, 13, 4, 3]. The work of [3] used the idea of the fractional dominating set to study the high-probability regret bound for the strongly observable graph. Other similar works (23, 32, 13] mainly focused stochastic settings. The follow-up works related the weakly observable graph mainly considered harder settings including the time-varying graphs [2, 15, 3], bounded-memory adversaries [19] and the feedback graphs with switching costs [30, 5J. The recent work of [21] considered the bound with respect to cumulative losses of the best arm. To the best of our knowledge, there no further development on the min-max regret since the work of [1].
Preliminaries
In this section, we formally describe the problem setting of bandits with graph feedback and introduce notations, definitions and propositions that will be used later.
Let n E N. We will use [r]] to denote the set (1,
n.) Let x E R" be an n-dimensional vector. For every [n)), we use x(i) to denote the value on the ith-coordinate. We use {el, ................................ e, to if j i for
1,
denote the standard basis of IR". That is, e, E "R" is the vector such that e:
0,
if +
every j E [n). For every E N, we define An fxER E x(1) - 1 as the n-dimensional probability simplex. Clearly An is convex and every x E A., can be viewed as distribution on [n]] Throughout the article, sometimes we will view a function é [n] - R equivalently as a vector in R", depending which form is more convenient in the context. With this in mind, we have the inner product (f, x).
Die(n) {(i) x() for every E R
2.1 Graphs
In this article, we use G = (V, E) to denote a directed graph with possible self-loops but no multiple edges. Therefore each (u, v) E E indicates a directed edge from u to v in G. If we say a graph
G == -V, E) is undirected, we view each undirected edge {u, e} E E as two directed edges (u, v) and (v, u). In the following, we assume [V| 2 2 unless otherwise specified. For any S C VVVC G(S is the subgraph
G induced by S. For every v E V, we define (rn(r) = {u E (u. v) E E} and Nou((r) [u E V (v, E E} as the set of in-neighbors and out-neighhors of e respectively. We also call [x)] and (Nouu (v) the in-degree and out-degrce of respectively. A set S V is an independent set if there is no u, E S such that (u, E E. Note that we do not consider an isolated vertex with a self-loop as an independent set.
A vertex E V is strongly observable if (v, E E or Vu E non-observable if Nn,(v) = Ø. A directed graph G is called strongly observable each vertex of G is strongly observable. It is called non-obxervable if it contains at least one non-observable vertex. The graph is called weakly observable it is neither strong observable nor non-observable.
(u, E E. A vertex v E V is
We say a directed graph G is 1-degenerate if one can iteratively apply the following two operations in arbitrary orders on G get an empty graph: Pick vertex with in-degree one and remove the in-edge; Pick vertex with in-degree zero and out-degree at most one, and remove both the vertex and the out-edge. Typical I-degenerate graphs include trees (directed or undirected) and directed cycles.
Let U = (i E VV & (i) denote the set of vertices without self-loops. Consider the following linear program defined on G. We will call the linear program
minimize Σ x4 VEV
subject to Σ (EN
x4 121, VjEU; 05 $1, VEV.

---

We use 8 (G) to denote the optimum of the above linear program. We call 8 (G) the fractional weak domination number of G. The dual of the linear program is
maximize Σ yj
subject to (N)
Σ
yj 11 VIEV; 0 s S1,
(7)
We call this linear program ).). We use C (G) to denote the optimum of the dual. We call (G) the fractional vertex packing number of G. Then follows from the strong duality theorem (sce
e.g. [11] of linear programs that 8 (G) (G).
We remark that in [1], the weakly (integral) dominating set was defined to dominate all "weakly observable vertices" instead of "vertices without self-loops". These two definitions are all equivalent for results this article. See Appendix A for more explanations on this.
2.2 Bandits
Let G = EV be a directed graph where V = [n] is the collection of bandit arms. Let E N be the time horizon which is known beforehand. The bandit problem is online-decision game running for T rounds. The player designs an algorithm with the following behavior in each round t of the game: The algorithm of chooses
A, E [n]: An adversary privately provides
a loss function & : + [0, 1] and i pays a loss (A.); The algorithm receives feedback
(l(()) j E Nout (A:))-
The expected regret the algorithm ad against specific loss sequence e = -. Er) is defined by &f, = [ [T=14(AA)) ((44)) -mina[[a] ET=16(a) Note that look the expectation of the algorithm since sí might be randomized and it is not hard to that randomization is necessary to guarantee (T)) regret due to the adversarial nature of the loss sequence. The purpose of the problem is to design algorithm performing well against the worst loss sequence, namely determining the min-max regret R(G,T) T) inf sup,- R(G,T, ",,, st)
There is another model called stochastic bandits in which the loss function at each round is not adversarially chosen but sampled from fixed distribution. is clear that this model is not harder than the one introduced above in the sense that any algorithm performing well in the adversarial setting also performs well in the stochastic setting. Therefore, we will construct instances of stochastic bandits to derive lower bounds in Section
2.3 Optimization
Our upper bound is obtained via the online mirror descent algorithm. In this section, we collect a minimal set of terminologies understand the algorithm. More details about the approach and its application to online Decision-making can be found in e.g. [28].
Let C' C R". We use int(C)) to denote the interior C. For convex function V : Rd - R U {oo}, dom( (V) A {x: (xx < oo) is the domain of V. Assume Vi is differentiable in its domain. For every x,y E dom (V), (x, y) A (x) Vyy) (x y, (v( 2 0 is the Bregman divergence between x and y with respect to the convex function V. The diameter of C with respect to W is (C) A supxyec (x) - (y)).. Let A R be definiei positive matrix and x e RR"
be vector. We define ||x||A A VxT Ax as the norm of x with respect to A.
3
The algorithm
In this section, we design an algorithm to achieve the upper bound in Theorem The proof is in Appendix B.
3.1 Online stochastic mirror descent (OSMD)
Our algorithm is based on the Online Stochasfic Mirror Descent framework that has been widely used for bandit problems various settings. Assuming the set of arms [n], possibly with many additional structures, a typicca OSMD algorithm usually consists of following steps:
5

---

Pick some initial distribution X1 over all arms.
For each round & = 1,2,..., T - Tweak X, according to the problem structure to get a distribution X, over n arms. The adversary chooses some (unknown) loss vector 4 [n] - [0, 1] with the knowledge of all previous information including X,. The algorithm then picks an arm A, ~ X, and pays a loss (At). After this, the algorithm observes some (partial) information 2, about 4. Construct an estimator l of & using collected information 4, A, and X. Compute an updated distribution X from X using mirror descent with pre-specified potential function V and the estimated "gradient" 4.
Although the framework OSMD standard, there are several key ingredients left for the algorithm designer to specify: How to construct the distribution X₂ from X₂? How to construct the estimator ? How to pick the potential function V/? In general, filling these blanks heavily relies on the
problem structure and sometimes requires ingenious construction achieve low regret. We will first describe our algorithm and then explain our choices in Section 3.2.
3.2 The algorithm for bandits with graph feedback
Let G = (V, E") be the input directed graph with V [ra]. A few offline preprocessing steps are required before the online part the algorithm. We first solve the linear program (3) to get an optimal solution { he(m Recall 8 (G) = EiE(n) 2 is the fractional weak domination number of G. Define a distribution An by normalizing (a])ee(x) i... let u(i) Esen #j
z for all
i E [n]. The distribution will be the exploration distribution whose function will be explained logn 1/3
17 --(c where is the exploration rate and 7 is the step size in the mirror descent. Finally, we let the potential function 1 - R be x E RS + E x(1 log x(i) with the convention that 0 log 0 = 0. When restricted to A., (x)
later. Define parameters 7
the negative entropy of the distribution
Algorithm 1: Online Stochastic Mirror Descent with Exploration
begin
X1 < arg min (a); aEA,
for t = .,, T do
X, - (1 x
/* use u to explore with rate Y.
Play A, ~ X, and observe 4(j) for all E Wor)(A)):
/* If j N 1ljENoml(Al)) 4(j);
the value of 4() is unset.
Vj [m]: 40) +
Eienmen Xe(1)
/* For jæ (A)), ((()) 0.
X(+1 +- arg min la) + By X.);
rEA
/+ The update rule of mirror descent w.r.t. V.
end end
Clearly our algorithm implements OSMD framework by specializing the three ingredients mentioned in Section 3.1. We choose X, (1 -)) X; 7 u. This means that our algorithm basically follows X, but with certain probability y to explore the arms according to u. The reason for doing this is to guarantee that each arm has some not-so-small chance to be observed. It will be clear from the analysis of OSMD that the performance of the algorithm depends on the variance of é, and lower bound for each Xi) implies an upper bound on the variance. On the other hand, we cannot choose 7 too large since X, who contains information on which arm good, and our probability to follow X; is 1 7. Therefore, our choice of o optimized with respect to the trade-off between

---

the two effects. The Exp3,G algorithm in [1] used uniform distribution over the weakly dominating set as an exploration probability instead of u, which the only difference between the two algorithms and leads to different graph parameters in regret bounds. Moreover, our exploration probability can be efficiently computed by solving the linear program P while it is NP-hard determine theirs.
Our estimator &, is simple unbiased estimator for 4,, namely E we used is the negative entropy function.
&g l.-
The potential function
4 Lower bounds
In this section, we prove several lower bounds for the regret in terms of different graph parameters. All the lower bounds obtained in this section are based on a meta lower bound (Theorem 2) via the notion of k --ackiing independent set.
Definition 6. Let G(V, E) be directed graph and & N. A set S S V is k-packing independent set of G if (1) S is an independent set; (2) For any u E V, it holds that Now(()) n SI S k.
Intuitively, a graph contains large k-packing independent set then one can construct a hard instance as follows: All arms in V - S are bad, say with loss 1; All arms in S have loss Ber (1) except special one with loss Ber g =). Then any algorithm with low regret must successfully identify the special arm from S without observing arms in S much (since each observation of arms in S comes from pulling V S. which costs a penalty least & in the regret), and can tweak the parameters to make this impossible. A similar idea already appeared in [1]. However, we will formally identify the problem of minimizing regret on this family of instances with the problem
2
of best arm identification. Therefore, stronger lower bounds Ω max [S] log |S| -T in
Theorem can be obtained using tools from information theory.
Remark. If maximum independent set of the graph of size one and G "weakly observable". then it has been shown in [1] that R(G,T) Q (T3) for any algorithm. If the graph has independent set, which means each vertex contains a self-loop, then the graph is "strongly observable" and its regret can be O(T²). ). In particular, the problem of vanilla n-armed bandits falls into this case.
We delay the proof of Theorem 2 to Appendix D and discuss some of its consequences in the remaining of this section. We recover and strengthen the lower bound based on the (integral) domination number of [1] in Section 4.1. Then prove Theorem 3 in Section 4.2 and discuss some of its useful corollaries. Finally, we discuss in Section 4.3 when our lower bounds are optimal.
Our main technical contribution here is that we relate 8" to the lower bound as well. This is achieved via applying the strong duality theorem of linear programming and using new rounding method to construct hard instances from fractional solutions of the dual linear programming. This approach towards the lower bounds much cleaner and in many cases stronger than previous ones [1]. To the best of our knowledge, the method is new to the community of bandits algorithms
4.1 Lower bound via the (Integral) weak domination number
We first use Theorem 2 to recover and strengthen lower bounds in [1]. Let G EV be directed graph and U C V be the set of vertices without self-loops.
The weakly dominating set of U is set S C V such that for every U, there exists with (v, u) E E. The weak domination number, denoted by ((G), is the size the minimum weakly dominating of U. In fact, 8(G) the optimum of the integral restriction of the linear program in Section 2.1:
S
minimize Σ zz subject
Σ VEN 0
x 22 VjeU a (0,1),, VieV.
(P)
YEV
The following structural lemma was proved [1]
Lemma 7. The graph G contains (log n)- packing independent set S of size at least a())
50 log
7

---

Applying Lemma 7 to Theorem 2, we obtain
Theorem 8. If G is weakly observable, then for any algorithm and any sufficiently large
time horizon T N, there exists sequence of loss functions such that R(G.T)
Ω max
6(G) log"
log 1og ((()))
1/3 T2/33
1] 1/3 log"
Note that the bound [1] is R(G,T) = Ω
max
&(G)
T2/3 Theorem outperforms
when wlognn < 8(G) < o(log" log n).
4.2 Lower bound via the linear program dual
In this section, we use Theorem to derive lower bounds in terms of (G). Recall the linear program (%) in Section 2.1 whose optimum is (*) 8 (G) by the strong duality theorem of linear programming. Consider its integral restriction (7')
maximize Σ Vj subject to JEU
YJ 11, ViEV; yj E [0,1), VjeU. (e))
Σ
(9)
For every feasible solution { yeu of (Z), the set S A EjEU 93 = 1 called vertex packing ser on U. It enjoys the property that for every
ooue (i) S
Let (G) be the optimum (9'), namely the size of the maximum vertex packing set on U. Let A (C))) be the integrality gap of (2) ). In the following, we will write 8*, 6, S* instead of (G) 8 (G) ( ((G) respectively if the graph G clear from the context.
We can use a greedy algorithm to find an 1-packing independent set of size at least [S] S and then Theorem follows from Theorem 2. Theorem is less informative if we do not know how large the integrality gap a is. On other hand, the integrality gap of linear programs for packing programs has been well-studied in the literature of approximation algorithms. The following bound due to [31] tight for general graphs.
Lemma ([31)). For any directed graph G, the integrality gap a O (n/8").
Corollary 10. If G is weakly observable, then for any algorithum and any sufficiently large time horizon T N, there exists a sequence of loss functions such thatR(G, = (622)
T
The bound for the integrality gap in Lemma 9 holds for any graphs. It can be greatly improved for special graphs.
An interesting family of graphs with small a is those bounded degree graphs. the in-degree of every vertex in U is bounded, we have the following bound for the integrality gap:
Lemma 11 ([10). If the in-degree of every vertex in U is bounded by constant A, then the integrality gap a & 8A.
Corollary 12. Let A E I be constant and GA be the family of graphs with maximum in-degree A. Then for every weakly observable G (V,E) E) E GR. any algorithm and any sufficiently large time horizon T N, there exists a sequence of loss functions such that R(G,T) = 2
Next, we show the integrality gap of another broad family of graphs, the 1-degenerate graphs, is 1. The family of 1-degenerate graphs defined in Section 1. Graphs including trees (both directed and undirected), directed cycles belong to this family. The proof the following lemma is in Appendix C.2.
Lemma 13. For any 1-degenerate directed graph, the integrality gap 1.
Corollary 14. Let G be a 1-degenerate weakly observable graph. Then for any algorithm and any sufficiently large time horizon T E N, there exists sequence of loss functions such that R(G,T) 3((6*)3 T3).
8

---

We obtained in Theorem that R(G,T) =0 0 logn) T and therefore our lower bound is tight up a factor of (log n)) on 1-degenerate graphs and graphs of bounded degree.
4.3
Instances with optimal regret
In this section, we will examine several families of graphs in which the optimal regret bound can be obtained using tools developed in this article.
4.3.1 Complete bipartite graphs
Let G = (V12 U V2, E) be an undirected complete bipartite graph with = 1V1 [V2]. Clearly 8
5 = 2. Therefore both our Theorem 1 and the algorithm in [1] satisfy R(G,T) = O (log n) T
Assuming without loss of generality that [V]] 2 [V2], then V1 is a |Vil-packing independent set of size at least 5. Therefore it follows from Theorem that any algorithm satisfies R(G, T))
Ω (logn) T
Note that the lower bound in [1] is Ω (T3) for this instance.
4.3.2 Orthogonal relation on F
Our algorithm outperforms the one in [1] when 8 < 6. Let us now construct a family of graphs where 3- 12 n).
Let F2 be the finite field with two elements and & E N be sufficiently large. The vertex set of the undirected graph G (V1 U V2, E) consists of two disjoint parts V1 and V/2 where Vi and V/2 both isomorphic to F/ {0). Therefore can write Vi { ) (o) and 1/2 {ys seFt
The set edges is as follows:
is the edge set such that G[V]] is a clique and G[[V2] is an independent set; For every Ta 1/1 and y E V2, { 15..83} E iff (a, B) Σ a(i) (()) = 1. where all multiplications and summations are in F2.
We will show that the upper bound and the lower bound of the regret for this instance proved in [1] based on d is O (logn) n) T and Ω (r3) respectively. However, we achieve the optimal (log n) T
regret. Thus we conclude that both our new upper bound and lower bound are crucial for the optimal regret on this family of instances. The details can be found in Appendix C.3
5 Conclusion
In this article, we introduced the notions of fractional weak domination number and k- k-packing independence number respectively to prove new upper bounds and lower bounds for the regret of bandits with graph feedback. Our results implied optimal regret several families of graphs. Although there are still some gaps in general, we believe that these two notions are the correct graph parameters to characterize the complexity of the problem. We now list few interesting problems worth future investigation.
Let be an n-vertex undirected cycle. What is the regret on this instance? Theorem im- plies upper bound O
n) 3 and Theorem 2 implies lower bound Ω (m3 T3).
The lower bound ? ((=))-73 . in Theorem 3 for general graphs is not satisfactory. The
lower bound proved via the construction a 1-packing independent set. This construction did not release the full power of Theorem 2 as the lower bound in the theorem applies for any k-packing independent set. It still possible to construct larger k-packing independent sets via rounding the linear program 2 to some "less integral" solution.
Is Theorem 2 tight? In fact, the bound for BESTARMID, which is constructed to prove Theorem in the full version of the paper, is tight since matching upper bound exists. Therefore, one needs new constructions of hard instances to improve Theorem 2, if possible.

---

Acknowledgements
This work was partly supported by National Key Research and Development Program of China (2020AA/0107700)), National Natural Science Foundation of China Grant (62006151, 62076161, 02076161,618020666 6 61902241), Shanghai Sailing Program, and Shanghai Science and Technology Commission Grant (17JC1420200).
References
[1] Noga Alon, Nicolo Cesa- Desa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In Annual Conference on Learning Theory, volume 40. Microtome Publishing, 2015.
[2] Noga Alon, Nicolò Desa-Bianchi,, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. arXiv e-prinis, pages arXiv-1502, 2015.
[3] Noga Alon, Nicolo Cesa- Dasa-Bianchi, Claudio Gentile, Shie Mannor, Yishay Mansour, and Ohad Shamir. Nonstochastic multi-armed bandits with graph-structured feedback. SIAM Journal on Computing, 46(6); 1785-1866, 2017.
[4] Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour. From bandits to experts: A tale of domination and independence. Advances in Neural Information Processing Systems, 26:1610-1611 1618, 2013.
[5] Raman Arora, Teodor V Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. Advances in Neural Information Processing Systems, 32, 2019.
[6] Kenneth J Arrow, David Blackwell, and Meyer A Girshick. Bayes and minimax solutions of sequential decision problems. Econometrica, Journal of the Econometric Society, pages 213-244, 1949.
[7] Peter Auer and Nicolo Cesa-Bianchi. On-line learning with malicious noise and the closure algorithm. Annals of mathematics and artificial intelligence, 23(1):83-99, 1998.
[8] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-255 2002.
[9] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1):48-77,200) 2002.
[10] Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan. Solving packing integer programs via randomized rounding with alterations. Theory of Computing, 8(1:5333-55, 2012.
[11] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[12] Swapna Buccapatnam, Atilla Eryilmaz, and Ness B Shroff. Multi-armed bandits in the presence of side observations in social networks. In 52nd IEEE Conference on Decision and Control, pages 7309-7314. IEEE, 2013.
[13] Swapna Buccapatnam, Atilla Eryilmaz, and Ness B Shroff. Stochastic bandits with side observations on networks. The 2014 ACM international conference on Measurement and modeling of computer systems, pages 289-300, 2014.
[14] Nicolo Cesa-Bianch and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[15] Alon Cohen, Tamir Hazan, and Tomer Koren. Online learning with feedback graphs without the graphs. In International Conference on Machine Learning, pages 811-819. PMLR, 2016.
[16] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
10

---

[17] Elad Eban, Aharon Birnbau,, Shai Shalev-Shwartz, and Amir Globerson. Learning the experts for online sequence prediction. 2012.
[18] Robert M Fano. Transmission of information: A statistical theory of communications. American Journal of Physics, 29 1):793-794, 1961.
[19] Zhili Feng and Po-Ling Loh. Online learning with graph-structree feedback against adaptive adversaries. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 931-935, IEEE, 2018.
[20] Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos. Efficient learning by implicit exploration in bandit problems with side observations. In Neural Information Processing Systems, pages 613-621, 2014.
[21] Chung- Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference Learning Theory, pages 2516-2566 PMLR, 2020.
[22] Shuai Li, Wei Chen, Zheng Wen, and Kwong-San Sak Leung. Stochastic online learning with probabilistic graph feedback. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pages 4675 4682, 2020.
[23] Fang Liu, Swapna Buccapatnam, and Ness Shroff. Information directed sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference Artificial Intelligence. volume 32, 2018.
[24] Shie Mannor and Ohad Shamir. From bandits to experts: on the value of side-observations. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 684 692, 2011.
[25] Shie Mannor and John Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5(Jun):623-66 648, 2004.
[26] Arkadi Nemirovski. Efficient methods for large-scale convex optimization problems. Ekonomika i Matematicheskie Metody, 15(1), 1979.
[27] Arkadij Semenović Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[28] Francesco Orabona. modern introduction to online learning. arXiv preprint 13X1v:1912.13211, 2019.
[29] Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th international conference on Machine learning, pages 784-791, 2008.
[30] Anshuka Rangi and Massimo Franceschetti. Online learning with feedback graphs and switching costs. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2435-2444. PMLR, 2019.
[31] Aravind Srinivasan. Improved approximation guarantees for packing and covering integer programs. SIAM Journal on Computing, 29(2):648-670, 1999.
[32] Aristide Tossou, Christos Dimitrakakis, and Devdatt Dubhashi. Thompson sampling for stochastic bandits with graph feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[33] Constantino Tsallis. Possible generalization of boltzmann- -gibbs statistics. Journal of statistical physics, 52(1):479-487, 1988.
[34] Abraham Wald. Sequential analysis. 1947.
[35] Julian Zimmert and Tor Lattimore, Connections between mirror descent, thompson sampling and the information ratio. In Advances in Neural Information Processing Systems, pages 11973-11922, 2019.


Reviews:
[{"review_id": "e-0tmcB3y8E", "reviewer": "Reviewer_3V7a", "summary": "The authors consider bandits with graph feedback and show improved lower and upper regret bounds involving a new quantity: fractional weak domination number. This leads to some logarithmic dependence improvement on the number of nodes. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The paper is well written and well organized, which provides sufficient background knowledge to reach the results. The table is also helpful.\n- For the upper bounds, I think it is interesting to see the improvement, but overall the the algorithm is not very novel, which seems to be still Exp3.G but with the fractional exploration probability. Related to this, I think the authors should compare their algorithm with Exp3.G or other bandit with graph feedback algorithms. The unbiased estimator and the negative entropy function are both standard in this field I think. The only difference as I mentioned should be the construction of u. The current presentation may give readers an impression that the algorithm is all new in these parts. \n- Moreover, the improvement from \\delta to \\delta* seems a little bit incremental to me. One thing I think is more interesting but the authors didn't even mention is about the computational efficiency. I think in the original Exp.G algorithm, we need to have a weak domination set to achieve such bounds, but the set is NP-hard to get in general. However, the exploration probability the authors propose can be efficiently computed via a linear program. Maybe the authors can verify whether this is the case, and it is nice to discuss this in the future revision. \n- As for the lower bounds, although the authors say \"we can not find an instance such that our lower bound is worse than the previous one\", this claim looks a little bit weak to me and I may still think the bounds are in general incomparable and the improvement in some special instances seems not very significant. \n- What is BESTARMID around Line 351? I couldn't find it in the main text. \n- Around Line 118 the authors mention [35] and say [35] gives another way to achieve the optimal regret bound. But what theorem or algorithm are the authors referring to? I thought the paper is mainly about adaptive bounds and many results in the paper have logarithmic terms in T, which may not be considered \"optimal\" here. \n\nOverall, I think the authors have an interesting observation on this problem, but the results are not a very significant improvement compared to the previous works. Also, there is not much algorithmic contribution. Therefore, I give the marginally below the acceptance threshold rating to this paper.\n\n===========\n\nI thank the authors for the valuable discussions and I increase my score based on this. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "UA9amRQMKNF", "reviewer": "Reviewer_DW8T", "summary": "This paper connects notions of the fractional weak domination number and the k-packing independence number with the graph bandits problem. Under these notions, the authors propose a new algorithm that achieves a fractional weak domination number dependent upper bound and also constructs lower bounds, including the main meta-lower bounds and other lower bounds in terms of different classical graph parameters. Therefore, tighten the gap between the upper and lower bound compared to the previous works. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "--Originality:\nFor the lower bound analysis, the technique to construct lower bound for regret via best-arm-identification problems is standard. One innovation here is that the authors use k-packing independence numbers to adopt these lower bound construction techniques into a graph structure.  Then by showing the relationship between the 1-packing independent set and the solution of the integral program defined in the paper, the author gets a fractional weak domination number dependent bound (Thm 3). The technique used in Thm3 seems purely related to graph theories. It looks interesting to me but I am not sure how novel it is in the graph theory area.\n\nFor the upper bound analysis, the choice of OMD framework, regularization functions, the estimator, and the exploration parameters are all standard techniques. One small innovation is that the exploration parameter u comes from the solution of a linear program, instead of simply a uniform distribution over some representative set.\n\nOverall, I think this paper combines some well-known techniques from online learning and graph theory (or linear programming). The combination techniques themselves have some novelty. \n\n--Quality: \nAll claims are well supported\n\n--Clarity:\nThis paper is well written\n\n--Significance:\nThis paper closes the upper bound and lower bound gaps for graph bandits and also discusses their results in several classical graph structures. So I think from a theoretical perspective, this contribution is meaningful.  \n\nThe technique's novelty here is nontrivial but somehow limited. \n\n--Questions: I wonder if this algorithm can directly extend to more adaptive settings [21, 5,19...] by combining with those existing techniques listed in the related work? If so that would be attractive.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "N20mO9b76Va", "reviewer": "Reviewer_LkFC", "summary": "This paper studies regret-bounds for semi-bandits in the feedback graph model for weakly observable feedback graphs, and (sometimes) improves both the upper and lower bounds on the regret in the adversarial setting (though in general the bounds are incomparable). In particular, they characterize the regret more precisely than existing work by going beyond weak domination number regret bounds in this setting; they use the notion of the fractional weak domination number (previously used for the case of strongly observable feedback graphs) and the k-packing independence number and show bounds in terms of these parameters. Since the gap between the upper and lower bounds on the regret depends on the integrality gap for a linear program related to the feedback graph (corresponding to the fractional weakly dominating sets problem on the graph), they then provide some natural concrete instances (e.g. bounded degree graphs) where the lower bound is now tight up to a factor of $\\log^{1/3}(n)$. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work follows an interesting line of work in proving regret bounds for the adversarial semi-bandit problem in terms of parameters of the feedback graph. The results are novel and interesting, and are definitely worth of acceptance. The paper is well-written and clearly contextualizes their results compared to the prior work. Moreover, some new techniques are introduced to get the lower bound -- the proof initially follows the same outline as in the original semi-bandit feedback paper lower bound, but is able to conduct a smarter analysis by reducing to the problem of best arm identification (e.g. Thm.2, which I found interesting and useful).  They also give a novel rounding procedure on the aforementioned LP to connect the integrality gap to k-packing independence number ( which shows up in Thm 2), thus completing the connection to the upper bound results. The upper bound result is almost standard; the only novelty here is the choice of exploration distribution, which depends on rounding the LP (the analysis is standard and the dependence on the integrality gap falls out by definition).\n\nOverall, I found the results of section D.2 and D.3 the most interesting and useful technical part of the paper, in addition to the actual result (identification of graph parameters that better characterize the regret in the weakly observable setting, and even more tightly in a few natural concrete instances).  I would encourage some re-writing of lines 741-750 -- the logical flow of the argument is a bit disjointed, and could read more smoothly given that the argument is very simple. Overall, I recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, as this is a theory paper.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "LXG5JJZ7tM4", "reviewer": "Reviewer_9yjH", "summary": "This paper studies the min-max regret bounds of the adversarial bandit with graph feedback. The graph feedback means that when pulling an arm, the learner can also get feedback from the arms that are adjacent to this arm in a specific graph $G$. The authors made non-trivial improvements on the upper bound and lower bound on the regret, especially for the “weakly observable” graphs. For some special cases such as complete\nbipartite graphs and orthogonal relation on $\\mathbb{F}^k_2$, the regret upper and lower bounds are optimal up to constant factors. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In summary, the problem is significant for the subarea of graphical bandits, and the authors made non-trivial contributions to this problem, though there are still rooms for further improvements.\n\nOriginality: The techniques and methods used in this paper are novel. By making a deeper analysis on the problem and introducing the parameter $\\delta^*(\\cdot)$ of a graph $G$, the authors were able to show a better bound compared to $\\delta(\\cdot)$ that are commonly adopted in previous works (note $\\delta^*(G) \\leq \\delta(G)$ for any graph $G$). \n\nQuality: Overall, this paper made non-trivial contributions to this problem and the introduction of $\\delta^*(\\cdot)$ can inspire future studies. In my opinion, it may be hard to make further improvements without using new techniques. Thus, although in general, there is still a $\\frac{\\log{n}}{\\log\\log{n}}$ gap, I think the results in this paper are good enough, especially for some special cases where the upper bound matches the lower bound (ignoring constant factors).\n\nClarity: The paper is well written overall but has some typos and formatting issues. For instance, Table 1 is surpassing the margin and needs to be restructured, and the reference in Line 63 is ??. \n\nSignificance: The problem is significant, but this paper only makes significant contributions to some special cases. For General cases, the improvements are limited. \n\nIn conclusion, my score lies between 6 and 7. I tend to give a score 6 for now due to the lack of practical motivations and numerical results. A typical motivation can be utilizing the information or data of the queried user's friends or connections, but this application may have potential privacy issues. It may help the readers if the authors can add more practical motivations and applications.\n\n-----------------------------------------------------------------\nAfter reading the response, the score is increased from 6 to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitation: The improvements made by the authors do not cover most of the general cases, which has been discussed in the box Main Review. \n\nI do not find negative societal impact of this work as this work is pure-theory and focuses on a fundamental abstract problem.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Several reviewers raised their scores after discussing with the authors.
Overall, we agree that the contribution of this paper is significant enough for better understanding the
minimax regret of bandits with graph feedback.
Please do incorporate all the suggestions from the reviewers into the final version.
Decision: Accept (Poster)