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,n) 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
2 =). 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
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)
log 1og ((())) 1/3 T2/33
Ω max
6(G) log"
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
(jEU 93 = 1 called vertex packing o.ue (i) S
ser on U. It enjoys the property that for every
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 seF
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 (17JCC420200).
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": "i-xQPMf6Fa", "reviewer": "Reviewer_pb7N", "summary": "This paper considers the multi-armed bandit problem with graph feedbacks.  The authors focus on the class of weakly observable graphs for which the minimax regret is known to be of order $\\Theta(T^{2/3})$. In previous work, the existing upper and lower bounds were expressed in terms of the weak domination number of the graph and showed a gap. To reduce it, the authors propose two new notions to measure the complexity of a graph: the k-packing independence and the fractional weak domination number. \n\nThey design an algorithm based on Online Stochastic Mirror Descent (OSMD) to which they add an exploration that depends on the graph. Their algorithm satisfies an upper bound on regret in terms of the graph's fractional weak domination number, instead of the (larger) weak domination number that was used for the existing upper bounds. \n\nThe authors also prove a lower bound in terms of the k-packing independence number, from which they derive various lower bounds. For some graphs (such as complete bipartite graphs), their upper and lower bounds are of the same order (no gap) and for many others (trees, bounded degree,...) the gap between the two is smaller than in previous work.", "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": "This article is relatively well written and the bandit problem with graph feedback is surely relevant to the community with many applications. The main contributions of the paper are in my opinion the following:\n- the paper introduces two new notions for understanding the complexity of graph feedback that seem to provide tighter results than existing ones. \n- The paper designs a new variant of OSMD for bandits with graph feedback with a tight upper bound on its regret. For some graphs, it exactly matches their lower bound and it is thus optimal.\n- The authors were able to relate their two notions and express their lower and upper bounds in terms of fractional low dominance numbers. The approach used for the lower bounds seems to use new technical tools that could be useful to the community.  \n\nOn the other hand, the improvements over previous work mainly consist of gaining logarithmic terms in the rates. At this point, we would like to get the tightest possible results. It is therefore unfortunate that the bounds still suffer from a logarithmic gap in many cases and even worse for some cases. In particular, for general graphs, it seems that the gap between the upper and lower bound may be of order $\\delta^*/n$, which makes the gap even larger than in previous work.   \n\n\nComments:  \n1. What is the cost of solving the linear program in the pre-processing part of the algorithm? Is it simpler to solve the fractional program than to solve the integral one? Do the other algorithms for graph feedbacks also need this pre-processing step?\n\n2. Some simulations to illustrate for some graphs the difference between the bounds could be interesting. \n\nMinor comments:\n- Table 1 should be re-worked. It is too large, with a lot of information which may yield some confusion. \n- It is stated in line 97 that \"we can not find an instance\", does it mean that you could not find one but their might be some? Did you try simulations with random graphs?\n- Lem. 7: \"The graph\". Which one? Do you mean \"For any graph\"?\n- Thm. 8: it only outperforms in the regimes $\\log^2 n > \\delta > \\log n$", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Idjc9jWhFFo", "reviewer": "Reviewer_xh89", "summary": "The authors study the problem of adversarial $K$ armed bandits with graph feedback, where selecting an arm $i$ provides an observation of the reward of all arms $j$ that are neighbors of $i$ in a given graph $G = (V,E)$, with $V$ the set of arms. The authors prove new regret lower bounds and provide new regret upper bounds for online mirror descent applied to this problem. The main idea is to consider the \"fractional weak domination number\" which, to the best of my understanding, quantifies the number of rounds necessary in order to obtain observations from all of the arms. While the results seem interesting, the paper is quite technical and difficult to read. ", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "1) The paper is quite dry and hard to read, especially for a new reader:\n- the results are presented before stating the model. This makes section 1 almost impossible to understand without reading Sections 2 and 3.\n- The results are stated as a succession of theorems and lemmas, with little intuition nor graphical illustrations about the notions introduced (dominating sets, vertex packing sets, 1-degenerate graphs etc.)\n\n\n2) No numerical experiments are presented, although simulating the proposed algorithm on some topologies and computing the corresponding regret lower bounds does not seem very hard to do. \n\n3) There is no discussion about the practical applications, in particular to justify the structural assumptions on the graphs at hand. The authors demonstrate that, in some graph structures, their results outperform the literature. However since one does not know what kind of structures are practically relevant, this seems relatively arbitrary.\n\n4) Minor remarks:\n- In Lemma 7, what does \"the Graph G contains...\" mean? Do the authors mean \"Any graph $G$ contains ...\" ? Are there any assumptions on $G$ required ?\n- \"Theorem 8 outperforms ...\" is a part of the sentence missing ?  \n- There are some \"??\" references.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "FoAly4zo0n", "reviewer": "Reviewer_hwCL", "summary": "This paper tries to improve our understanding of the hardness parameters in adversarial bandits with weakly observable graphs.\nThey propose a slightly modified algorithm with improved regret guarantee in certain instances and novel lower bounds.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper tries to narrow the gap between upper and lower bounds for adversarial bandits with graph feedback in the `weakly observable' $T^{2/3}$ regime.\nThey do that on two frontiers, first of all, they show that the weak domination number used in previous upper bounds is not the exact quantity that appears in the analysis of OSMD with Shannon entropy. Instead, the fractional weak domination number appears, which in special cases can be up to a factor $\\ln(n)$ smaller. The algorithm used for the upper bound is a standard mirror descent with shannon entropy.\nAside from special constructions, the ratio between fractional and vanilla weak domination number is often O(1) and hence the upper bound does improve on special instances only.\nThey present three types of lower bounds. First is a general bound based on the k-independent packing number. This result subsumes the SOTA lower bound as a special case.\nSecond is a reduction to the special case of 1-independent packing. One can relate the upper and lower bound in this case based on the integrality gap, which is incomparable to the previously known lower bound and it is unclear if it is always tighter.\nFinally they also show that a lower bound based on the logarithm of the Independence number (over the subgraph without self-loops) is possible.\nThis allows them to close the gap between upper and lower bound completely for instances where the fractional weak domination number is O(1) and the independence number is Omega(|V|).\n\nThe paper is written clearly and the proofs seem to be correct.\n\nThe main question is the significance of the results. Previous algorithms are provably optimal up to a $\\ln(n)$ gap. Even with the new theorems, the worst-case gap is at least $\\ln(n)/\\ln\\ln(n)$ in general graphs. \nOn the positive side, this problem is very difficult, even in the T^1/2 regime. They have at least closed the gap between upper and lower bounds on some special graphs for the first time.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "9DxHFS8JMY", "reviewer": "Reviewer_G8Mu", "summary": "This paper studies adversarial multi-armed bandits with graph feedback and provides new upper and lower bounds for the regret, which sharpen previous bounds in some regimes and provide tight bounds for some graphs.\n\nOne new idea is to define a linear program for fractional weak domination in a graph and its dual, fractional vertex packing. Lower and upper bounds are given in terms of the optimal value of this LP and its integrality gap (Theorems 1 and 3). \n\nAnother lower bound is proved by using the notion of the maximum k-packing independent set of a graph (Theorem 2).\n\nA summary of new bounds is given in Table 1. The min-max regret rate is determined for complete bipartite graphs up to the constant and for trees and bounded in-degree graphs up to a $(\\log n)^{1/3}$ factor.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like this paper. The ideas are new and interesting from a mathematical perspective, and the results are strong. This is a natural, important problem in online learning and even slightest improvements are of significant interest.\n\nThe paper is generally well-written. It needs just a round of proofreading to improve its flow. Some minor comments below.\n\nI haven't verified the proofs, which appear in the supplementary material.\n\nComments:\n- Line 63: section number is missing.\n- Lemma 7: \"The graph\" should be \"Any graph.\"\n- Corollary 10: it's weird that the bound hasn't been simplified.\n- Line 272: \"If fact\" should be \"In fact\"", "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": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the reviewers felt that the results are limited in their relevance and scope (they only apply to weakly observable graphs and the improvements are within log factors), they also thought---and I concur---that the paper is tackling a very basic and challenging problem, and from a mathematical point of view it contains some interesting ideas (the connection to integrality gaps of LPs is particularly compelling).  I strongly encourage the authors to take the reviewers’ comments into consideration when preparing the final version and carefully implement their suggestions.
Decision: Accept (Poster)