A Gang of Adversarial Bandits
Authors: Mark Herbster
Stephen Pasteris
Fabio Vitale
Massimiliano Pontil
Venue: NeurIPS 2021 Poster (2021)
Keywords: Online Learning
Bandits

Abstract: We consider running multiple instances of multi-armed bandit (MAB) problems in parallel. 
A main motivation for this study are online recommendation systems, in which each of $N$ users is associated with a MAB problem and the goal is to exploit users' similarity in order to learn users' preferences to $K$ items more efficiently. We consider the adversarial MAB setting, whereby an adversary is free to choose which user and which loss to present to the learner during the learning process. Users are in a social network and the learner is aided by a-priori knowledge of the strengths of the social links between all pairs of users. It is assumed that if the social link between two users is strong then they tend to share the same action. The regret is measured relative to an arbitrary function which maps users to actions. The smoothness of the function is captured by a resistance-based dispersion measure $\Psi$. We present two learning algorithms, GABA-I and GABA-II, which exploit the network structure to bias towards functions of low $\Psi$  values. We show that GABA-I has an expected regret bound of $\mathcal{O}(\sqrt{\ln(NK/\Psi)\Psi KT})$ and per-trial time complexity of $\mathcal{O}(K\ln(N))$, whilst GABA-II has a weaker $\mathcal{O}(\sqrt{\ln(N/\Psi)\ln(NK/\Psi)\Psi KT})$ regret, but a better $\mathcal{O}(\ln(K)\ln(N))$ per-trial time complexity. We highlight improvements of both algorithms over running independent standard MABs across users.

A Gang of Adversarial Bandits
Mark Herbster*, Stephen Pasteris* Department of Computer Science University College London London WCIE 6BT
Fabio Vitale
University of Lille
59653 Villeneuve d' Ascq CEDEX France fabio. vitale20umiv-llll..e
{m herbster, s. p.sterrsssssssssssseoees ucl. ac. uk
Massimiliano Pontil
CSML, Istituto Italiano di Tecnologia and Department of Computer Science University College London massimiliano pontileiit..... pot.iiiiiiioooo.iiiiit...i...... it
Abstract
We consider running multiple instances of multi-armed bandit (MAB) problems in parallel. A main motivation for this study are online recommendation systems, which each of N users is associated with MAB problem and the goal is to exploit users' similarity in order to learn users' preferences to K items more efficiently. We consider the adversarial MAB setting, whereby an adversary is free choose which user and which loss to present to the learner during the learning process. Users are in a social network and the learner is aided by a-priori knowledge of the strengths of the social links between all pairs of users. It is assumed that if the social link between two users strong then they tend to share the same action. The regret measured relative to an arbitrary function which maps users to actions. The smooth- ness of the function captured by resistance- present two learning algorithms, GABA-I and GABA-II which exploit the network structure to bias towards functions of low V values. We show that GABA-I has ( and per-trial time complexity OK IN))),, whilst GABA-II has weaker O( P(vin(N/V) V) In N K/ (TT) regret, but a better OIn( K) In(N)) per-trial time complexity. We highlight im- provements of both algorithms over running independent standard MABs across users.
dispersion measure V We
expected regret bound of (IvIn(N
Introduction
During the last decade multi-armed bandits (MAB) have received great deal of attention in machine learning and related fields, due to their wide practical and theoretical importance. The central problem is to design a decision strategy whereby learner explores sequentially the environment in order to find the best item (arm) within prescribed set. At each step the exploration the learner chooses an arm, after which feedback (typically loss or reward corresponding to the selected arm) is observed from the environment. Then the next decision is made by the learner based on past interactions, and the process repeats. The goal is to design efficient exploration strategies which incur small cumulative loss comparison to the cumulative loss that would have been obtained by always
Equal contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

selecting the best arm in hindsight. Applications of MAB are numerous, including recommender systems [ clinical trials (2), and adaptive routing [ among others.
In this paper we study the problem in which the learner is facing several MAB problems that are related according a prescribed interaction graph. A main motivation behind this problem are online recommendation systems, whereby each of several users is associated with a MAB problem (task), where the arms correspond to a finite set of products, and the graph represents a social network among users. The goal is to exploit users' similarity in order to improve the efficiency of learning users' preferences via online exploration of products. In the standard full information setting. a lot of work has been done showing that techniques from multitask learning are effective in reducing the amount of data needed to learn each of the individual tasks, both in the statistical and adversarial settings, see [4 [S O 7 8 9 [00 [T] and references therein. Graphs have been used to model task relationships, with different tasks' parameters encouraged to be close according to the graph topology. In contrast, multitask learning in the bandit setting is much less explored.
The algorithms that we present exploit the network homophily principle [12 which formulates that users that are connected in the network have similar preferences, that is, they tend to share preferred recommendations. We will show that our algorithms exploit graph structure and enjoy potentially much smaller regret bounds than the cumulative regret of standard MAB run independently on each user. Since the original graph may be dense, we exploit a randomized sparsification technique to develop fast prediction algorithmss Our approach builds upon previous work on online learning over graphs [13 14 to generate a perfect full oriented binary tree, whose leaves are in one-to-one correspondence with the nodes of the original graph. This construction approximately preserves the relevant graph properties in expectation, and provides the starting point for designing our efficient algorithms. A further ingredient in our algorithm is provided by the method of specialists [15] 16]. Our learning strategies combine the above ingredients to devise efficient online algorithms under partial feedback.
Contributions. We introduce two Gang of Adversarial BAndit algorithms, GABA-I and GABA- II that Iearn jointly MAB models for N users over K possible actions. Both algorithms are designed exploit network structure while being (extremely) computationally efficient. We de- rive expected (over the algorithms" randomizations) regret bounds. The bounds scale with the dispersion measure V E N] of the best actions over the graph. For GABA-I the bound"] is of order of O(y ///n/N (n(NK/ / L KT),, where T is the number of trials, and has a per-trial time complexity of O(K (N)).. On the other hand GABA-II has a weaker expected regret but is faster, having per-trial time complexity of
bound of O( (n(NN//// (NNK))NNK/V) (In(K) In(N)). Thus the GABA-I algorithm improves on algorithms that treat each user in- dependently, as in the best case the regret improves from O(v to (vInn N) and in the worst case the regret degrades by at most a constant factor. GABA-II has slightly weaker regret bounds; however, it is more computationally efficient.
Outline of Main Results. The social network graph is determined by a set of undirected links LN where Wa,e E [0, oo) indicates the magnitude of the link between user u and v. For all E [T] we have a user u, E [N] and a loss vector l, E [0, 1]K which are selected by Nature before learning begins and are unknown to Learner; i.e., Nature is a deterministic oblivious adversary (see e.g., [17 Section 5.1]). Learning then proceeds in trials t = 1,2, ..... On trial t:
between users {
1. Nature reveals user u [N] to Learner,
2. Learner selects action a₂ E [K].
3. Nature reveals loss lr,a, E [0, 1] to Learner.
Before reflecting on the N-user case we review the well-known results for the single user (N = 1). The seminal EXP3 algorithm [18] obtains the following (uniform) regret bound")
E
Σ (1,0 [E[T]
min KE(K]
Σ tra E O (VK (n(())))))
(1)
[E[T]
1 'The bounds of GABA-I and GABA-II however depend on oracular knowledge of optimal tuning parameters. We discuss this as well as means of lessening this dependency following Comolaay 5 An algorithm was given in [19 that removed the In K term from the regret.

---

where the expectation is with respect to the internal randomization of the EXP3 algorithm. In the N-user setting. by running a copy of EXP3 independently for each user, we may obtain uniform regret bound of (see e.g., 20
E
Σ 2,a (E[2]
min
(ev EO (VKII(K))))) Σ LE(2)
M [ [R]
i.e,, for each user u the best action is y(u) and we now pay an additional constant factor of VNN in regret. In this work we exploit the social network structure to prove non-uniform regret bound for the GABA-I algorithm (see Corollary 4 of
R(y) = E
Σ TE(T]
L1,0r]
Σ (ealte EO kE(T]
{0(1 K In
T (t)TT ((y))
KN
(3)
for any mapping of users to actions y : [N] [K]. The non-uniform regret now depends on VVy) E [1. NJ (see (5) which measures dispersion of users' 'best' actions across the network. Thus, by taking network structure into account, we may upper bound the scaling in the regret with
respect to the number of users by O In(
eN (r)) When the best action across the network ((y)
is nearly uniform then the dispersion (v) E ((1), in contrast when the dispersion is maximal then Vi (g) = N thus in the best case the regret with respect to the number of users improves from ((VN) to O(vin N) and in the worst case the regret only increases by a constant factor. The first algorithm GABA-I obtains the regret B while requiring O(K In N) time to predict and update. The second algorithm GABA-II's regret (see Corollary 5 is larger by O( /In (y) factor but now prediction is at an even faster (In(K) K) In(N)) time per trial, that is, prediction time improves exponentially with respect to the cardinality of the action set [K]. Thus both algorithms support very large user networks and the second algorithm allows efficient prediction with very large action sets.
Related Work. We mention here some of the key papers that more closely related ours and refer the reader to the technical appendices for an expanded literature review. There has been much work in the heterogenous multi-user setting for Stoca-stochastic bandits. Out of these works, those closest to us are when the users are in a known social network and it is assumed that neighbouring
users respond context vectors in a similar way 21 22 23 24 25 26 but as far as are aware no works on this model have so far been done in the adversarial setting. Other works on this topic include those in which it is assumed that there is an unknown clustering of the users, where users 35]; as well as other models 40 41 42 4 There are also works on networked, homogenous multi-user bandit 46
in the same cluster are homogenous 27 28 29 30 31
32
33
34
[36 37 38
39
48 49 50). Related to the multi- user setting are works on transfer learning and meta-learning with linear-stochastic bandits [51 52). Whilst our work assumes a known network structure over the users, there is a wide literature on bandit problems in which the actions are structured in network and is assumed that neighbouring actions give similar losses 53 54
models with limited communication between users 44 45
47
58 59 60. as well as other networked-actio models 61 62 63 In addition to the seminal paper on adversarial bandits [18. our work utilises ideas from
55
56
57
several different papers [13 14 15
16, 64 65).
Notation. Given set X we define 2-X to be its power-set, that is: the set of all subsets of X. For any positive integer m, we define [m] := {1, 2,.,...., mm. For any predicate PRED, [PRED] == 1 if PRED true and equals 0 otherwise. Given vectors æ, x R we define æ x to be their inner product (i.c.. equal to Eijn] kTTz) and we define x @ x' to be their component wiise product (i.c., (a 3 z²); == 2z22 for all component is equal to 1. Given a full oriented binary tree B we denote the set of its vertices also by B. Given a lonfleaf vertex n E B let <(n) and (nnn) be its left child and right child respectively. Given a non-root vertex n E B let (n) be its parent. Given a vertex n E B let (n) and ((n) be its set of ancestors and deaf-descesdants (i.e. descendants which are leaves) respectively. Given vertex n E B we define 4 (n) and (n) as the left-most and right-most descendants (which are leaves) of n respectively. Finally, we denote the user graph by G. which is an undirected connected graph with edge weights (Wap. 1 < a < v < N). For convenience we assume N is a power of two 3
[K]). We define '1' to be the K K-dimensional vector in which each
"This assumption does not limit our results because to run our algorithms one can always add dummy vertices without altering input weights, so to force N to be power of two.
3

---

2 Modeling a Social Network as a Resistive Network
In this section we introduce the tools necessary formalize our complexity measures, well the ones to implement our algorithms.
2.1 Conceptual Tools
To minimize the incurred loss, Learner can exploit the similarity between any pair of users defined by
the weights Wa, of user graph edges for u, v E [N]. The function y [M] + [K] is completely unknown to Learner, and can be viewed as labeling each user with its best/faworite action. Within this
context, our homophilic bias can be stated as follows: users strongly connected w.n.t. the link weights
w, tend to be associated with the same label.
The complexity measure used for this problem the robustified resistance weighted cutsize (y). which we now define formally. Within the graph-based learning context, the cutsize is defined as the number of edges connecting users with different labels, i.e., EucuIu.. o 0] [y(x) * y(v)]. and the weighted cutsize is defined as the sum of the edge weights Wa," over all pairs of users and v having different labels, i.e., Enço Wn, [v(u) * y(v)] [1]. The effective resistance between two given nodes u and v of a graph is commonly used measure that expresses the degree of the connection strength between u and v (see, e.g., (66). More precisely, viewing the graph as an electrical circuit, where each edge weight W corresponds to _
Ch.". resistor, the effective resistance between and the power required to hold between them unit voltage difference for unit time. Informally, the
more there are paths between two nodes u and v that are short, edge-disjoint and formed by edges with large weights, the lower r(u. v) because the amount of flow between the two considered nodes is larger. A formal definition of effective resistance r(u, v) between users and is
r(u, v) min (Eis Way( - xy)² Iu I. =
Interestingly enough, for all u, v E [N], r(u, v) exactly equal the probability that the edge {u, b is included in a uniformly generated random spanning tree of the given user graph 9 (see, e.g.,
66
The resistance weighted cutsize ( 667 is the weighted sum of the effective resistances r(u, v) between any two nodes u and with different labels. i.e.,
N
+ (vy) =
ru, lu(u)) # v(u)]
(4)
and then its robustifcation is defined as
((2) + Σ Ia(u)= + v(w))).
V (v) = min [
(5)
uEIN]
The first quantity 4 can be viewed as dispersion measure based on the above mentioned homophilic tendency. It has several advantages compared to the weighted cutsize measuring the degree of homophily violation 67 The most significant property is that it is locally density-dependel
because the contribution to (g) of each edge (u, v) such that y(u) * y(u) inversely proportional to how strongly u and are connected in their user graph local area. Indeed, because of the effective resistance, the potential contribution to (by)) of the edges in dense areas is smaller than the ones of the edges in sparse areas. In fact if the graph is well-clustered i.e., it can be partitioned into dense clusters (many intra-cluster edges) and fewer inter-cluster edges and the labeling respects these clusters then in many cases (yy) & N. As an archetypical instance consider the following proposition where the clusters are represented by cliques.
Proposition 1. Consider an unweighted graph G partitioned into G clusters and labeling function v-)), where each cluster is an n-clique and, if u, v are vertices in the cluster, then y(u) = y(v). For any pair of such clusters C, C' C G, suppose that there are 2=1 edges connecting the nodes of C with the nodes of C'. Then have 42y) (G)).

---

CONSTRUCTBST-C (User graph: 9)
Sample uniform random spanning tree T from the user graph.
2. Perform a depth-first visit of T provide order of the users. Without loss of generality assume that, for all E [M] we have that user u is the u-th vertex visited.
3. Construct a perfect full oriented binary tree C of depth h := log)(N) whose u-th leftmost leaf of its graphical representation is user
"In this context, by oriented we mean that the leaves of C are numbered sequentially from the leftmost to the rightmost that, for each internal vertex of C, both its left and right subtree contain subsets of leaves uniquely determined by the depth first visit T.
Figure 1: Binary Support Tree Construction Algorithm
Thus in this archetypical case our regret bounds scale strongly with the number of clusters of users G (see (3) rather than with the number of users N (comparing to the baseline (2)
The second quantity (5) is an extension of ((y) to deal with adversarial label perturbation, viz., capturing the regularity of all labelings such that +(y) can be dramatically reduced by simply changing the labels of relatively small number of users. To give insight into the advantages of (y) w.r.t. ((y) regarding its noise-tolerance property, consider an input star graph with all edge weights equal to 1 and where all vertex labels are equal except for the one of the central node u. It is natural to consider this labeling regular w.r.t. our bias, because it is sufficient to change only y(u) to obtain a cutsize equal to O. This is precisely the labeling property that is captured by (y)) which is equal to the minimum, over all labelings 2, the sum of ((2 and the number of vertices for which y and differ (plus 1). In this case have therefore (yy
(v"") 1 where y" the labeling obtained by changing y(u) to make it equal to all other labels, so that t o(y") = 0, whereas + (t) N 1.
2.2 An Embedding to Enable Fast Computation
A uniformly generated random spanning tree (RST) is defined as spanning tree selected with probability proportional the product of the weights of all its edges (see, e.g., (66)). represents fundamental tool in several mathematical fields, e.g., combinatorial geometry, algebraic graph theory, stationary Markov chains [68,, and can be viewed
way to summarize the topological information of the imput network. When the input graph is weighted as in our case, it can be generated in time almost linear in the number of edges 669 77].
In a preliminary phase, our algorithms operate as follows (see Fig. D. A RST T of the input social network is drawn (step 1). Thus, order of the N users is determined through depth-first visit of T (step 2). From here on we assume, without loss of generality, that user u E [N] is the u-th vertex visited. This step is necessary make the algorithms noise-tolerant and is strictly related to the improvement of the complexity measure (1(() over ( Finally, a full perfect binary tree, called the Binary Support Tree (BST), and having the users, ordered from left to right, as leaves (step 3) is constructed. The BST forms the geometry that underlies the tata-structure, of our algorithms.
We conclude this section by showing result which will be useful in the analysis of our algorithms, and stems directly only from the user order determined by the depth-first first visit of TT If we consider the line graph L connecting the users with
for all E IN 1]. we have that, as stated in the following theorem, the cutsize of L is at most twice the robustified resistance weighted cutsize of the input graph. This result can be viewed the multi-class extension of part 2 of Theorem 6 in 667
Lemma 2 66 Theorem 6)). For any given input user graph, we have
Σ [v(u) + v(u+ 1)1 < 22v(),
where the expectation is over the draw of the uniform random spanning tree T.
5

---

SPECIALISTEXP (Learning rate 17 0: Distribution w1 : [0, s.t. Eses wi(s) 1.)
For f .....: T do
1. Va E [K] Pt, + De wx(s):
2. Predict a, by drawing from [K] with probability P(a: pt.a /
Receive lr.a:
4. d + exp(-nte,a p 2x Ipell1/((ppel] - (1 de)pt
5. E
(s(s)
s(u)) = 0
(+++((8 +- (
s(ue) + at
(x) s(ue) = at
Figure 2: SPECIALISTEXP Algorithm
3 Predicting with Specialists
We build on the prediction with expert advice framework 71 72 73 74,, specifically that with bandit feedback: pioneered by the ExP4 algorithm [18]. This type of online algorithm maintains a distribution over a set of predictors ("experts"). After the predictors predict they incur loss and the distribution is updated accordingly. Although, except in special cases, this procedure does not have a natural Bayesian interpretation, probabilistic methods still may be transferred into the expert advice framework. In particular will exploit an analogue of message-passing graphical models (75) to predict very efficiently over exponentially-sinn speaking would like build graphical model that is isomorphic to the user graph G. However it is well-known that exact prediction with graphical models that contain cycles is Narhard (76). Thus BST (see Section 2.2 is that it enables fast and exact computation as the graph is now cycle-free and Lemma 2 ensures that the embedding only modestly increases regret bounds. Surprisingly, we improve in terms of computation over standard message passing techniques, i.e., if we embedded to a "line" graph we would require O ( N) time to predict [75] per trial using the method of (77) O(33 log N) time. However, we will require only OKK log N) and Ollog K log N) for the GABA-I and GABA-II algorithms respectively (see Figures and To
used in sets of predictors. Broadly
benefit of the embedding
accomplish this technically we adapt the method of specialists [6).
specialist is a prediction function s [N] + (1, K, [} from a context space to an extended
output space with abstentions. For us the context space is just the set of users [N]; and the extended output space is 21, K, D} where [K] corresponds to predicted actions, but 'O' indicates that the specialist abstains from predicting
action. Thus specialist specializes its prediction to part of the context space. We denote the set of all specialists as S == [1,..., K, K, () As single specialist only predicts over part of the context space, we need set of specialists S C S if we wish to define function that predicts an action for every context. A specialist set S C S is well-formed for each u E [N]] there exists a unique specialist s E S such that s(u) E [K]. For such a user u and specialist s we then define St (u) := s(u) so that St is function from [N] into [K]. Finally a specialist model is defined by giving a distribution wT S - [0. s.t. >xes (s) 1. To predict with specialists we adapt [15] to the EXP3/4 (18 setting giving the SPECIALISTEXP algorithm (see Figure 2). We then bound the regret by combining the analysis of [8] into the following theorem.
Theorem 3. The expected regret of SPECIALISTEXP with initial specialist distribution wi [0, 1] and learning rate 1) >> 0 is bounded above by
KKT 2
E
Σ l,aar - (e,st(ua)
In SES
+
(6)
w (s) S
EE(T)
for all well-formed specialist sets S S.
In the following we give the two distributions that define the two specialist models corresponding and (g). and in the supplementary material we detail how these
to GABA-I and GABA-II distributions Iead to the regret bounds in Corollaries 4 and

---

We now give the distribution wi (-) over S that defines the GABA-I model. The model has a single parameter @ E (0, 1) and we give the following helper functions to define the distribution,
valid1(s) = [vu, E [M] s(u) = s(w) or s(u) = or s(v) = []
cut(s)
Σ
[s(u) + s(u + 1)]
NE(N-1]
startfactor(s)
[s(1) + [s(1=
K
The function v.lidl(.) determines the support of w1(+) which are the specialists that predict unique
action or abstain, hence the cardinality of the support of w1 (-) is K x (2 - -) + 1. The remaining two functions quantitatively determine probability mass specialist as:
wi (s) == valid1 (s) x x startfactor(s) (1 M) 1--1)-
1 K
(As E S).
We note that this specialist selection is similar to that of the Markov circadian specialists in 16 except that the nodes of the Markov chain are now users instead of trials.
Corollary 4. The expected regret of SPECIALISTEXP with distribution wa (-) as defined by 7 with parameter Φ = 4V())/(K(N - 1)), learning rate n (N -K-1), 1)/4 4 is bounded above by:
10w(1) bn N (w)) and with ( -
KT
EO (V
KN v
Σ EE(T]
le (eptaee)
KIn
(g)T
(8)
for any mapping of users to actions y [N] [K].
We now give the distribution wh (-) over that defines the GABA-II model. Whereas for GABA-I
the cardinality of the support was exponential in N, for GABA-II the cardinality is just K K(2N - 1).
The supported specialists in GABA-II predict a unique action over a contiguous ,,...,7 and abstain everywhere else, thus they are of the form:
u {4 & (1,
( O
but not all contiguous segments are supported. The segments supported are those that correspond
the set of all leaf-descendents of node in the BST (see Section 2.2). As example if N 4
the supported (1,r) segments are {(1, 1), (2, 2). (3,3), (4,4), 4). (1, 2), (3, 4), (1,4)) Expressing this
algebraically leads relatively complex "vvaiddit"' function
valid2(s) [a E [K];4r E [N]ji, E [log2 N] 1+r-l= 2 and / --= (j-1)+1 and = s..
and then the distribution defined as.
wi (8) valid2(s) K22N 1) (As E).
We note that this selection specialists a simple multi-action extension of those defined in 665
Corollary 5. The expected regret of SPECIALISTEXP with distribution wa (-) as defined by 9 with learning rate n 840()) (eN (cN/WWW))) (w)) (2M and with (1y S N/2 is bounded above by:
KT
(V
N
KN
E
Σ EE(T]
le,a, (eslar))
EO Kin
In
V (2)
(10)
V
T Vv())
for any mapping of users to actions [N] + [K].
4 The GABA Algorithms
We now introduce the GABA algorithms. Both algorithms based on the BST C (see Section 2.2
7

---

4.1 GABA-I
Since we have an exponential number of non-zero weight specialists in GABA-I direct implementa- tion of SPECIALISTEXP would take per-trial time and space exponential in N. We now describe how GABA-I implements SPECIALISTEXP, bringing the per-trial time down to O(K In(N)) and the space down to N). The implementation works by, for each action independently, performing online belief propagation [64] over the tree C. We note that each of these K online belief propagations is over two states {0, } and hence takes per-trial time of only (In((N). We now detail this procedure:
GABA-I maintains a vector valued function or [0x00,1 - R which, for all i, E {0, and E [7]. has the following properties:
Vu E [M] \ {we), attI(,,;,j) = ax(u, i.5)
(11)
and for all internal vertices n of we have:
an(nii,))
Σ an(4()),ikk) o (n())n), (E(1).)
(12)
On trial GABA-I computes P. by sending vector valued messages down the path in C from the root to
ue- Specifically, construct the left and right message functions 3 3 : :f(( {0. - R as follows. Each (non-root, proper) ancestor n of u, receives, for i E {0, 13. . K dimensional vector messages 3. (*n),, i) and 3 (t(n), i) from its parent and then constructs its own messages 3F i) from (F(t))), j) and ax (n)))( i) and messages 377 (n, from 3 (f()), and ax (x(()))) j), for all i,j E 10, It then sends these messages to its child that is next the path to ug. Once un has received the messages from its parent it combines them with az (,, 1, i) (for i {0, 13) create Pt.
On the receipt of lta, we update the function a to 04+1 noting that by 11 and 12 we need only modify the values (n, i,j) when is ancestor of 1t.
4.2
GABA-II
For GABA-II we have ((K))(N) non-zero weight specialists that don't abstain on any given trial so direct implementation of SPECIALISTEXP would take per-trial time of O(K (N)). We now show how GABA-II implements SPECIALISTEXP, which takes the per-trial time down to OIn () In())) whilst maintaining the space complexity of O(KN).
We first note that SPECIALISTEXP maintains a weight for each specialist. For any vertex n of C and any action a, the weight, on trial t, of the specialist that predicts a whenever un is its descendant and abstains otherwise, is kept, by GABA-II in the following factored form:
me(n)..(n.cc a) K(2N 1)
(13)
where (+) == (n) whenever n & fu:)). and Peti(n, a) = Oe (, a) whenever $ (ux) or a # az.
In addition to the tree C, GABA-II also works with an oriented full binary tree B whose leaves are the actions (in this overview we assume that the cardinality of the action set is an integer power of two, although this is not required by GABA-II). For any vertex n of C the function 02 (n. -) is extended onto all internal vertices of B by the following inductive relationship:
0, (n, m) 0, 4(m)) + (1,,,(m))
(14)
To sample the action a; GABA-II III first samples an ancestor d, of ur with probability P P = n] xc (,, (n,r) where is the root of B. GABA-II then uses the function (b).-)) to sample action a, with probability P ((a = a & = n| = 0g(n a)/8, (n, r) in (In(K)) time. The law of total probability and (13) can then be used to show that P Ja: al Pt.a where Pt.a is as defined in SPECIALISTExP.
On the receipt of le.e, we update the functions μr and 0g to pe+1 and 0,+1 noting that by the equalities between these functions and (14) we need only modify the values (n) and (e(n, m) when n an ancestor of 2n and m is an ancestor of oz,
8

---

GABA-I (Learning : v O; Model parameter: (0,1))
Construct binary support tree via CONSTRUCIBST-C algorithm (see Figure D
V leaf Vi,j E (0. 1), an(n,i,)) + 1 .] =] Ø)1:
For d = 1,2,......
1, Vn E Ct dt d. Vi.j E (0, 1). do
on (n, 4- ( (1(()),,,, k;
For /
1.2...
3. Vd E [h] Di,d + ancestor of u, at depth d in C;
e [0, 3 (v).,)) (1 + l oJ(K 2))1/K: ei 10,1}, (v)r,))) 1:
5. For d =
(a) Ve,d ((v)a-1) then Vi {0,1}
i. B (M,, i) _ (1, i);
ii B7 (Vi,s i) + 1) 4=( 0 (v..-111))
(b) Pc, D(v,a-1) then vi {0.1}
i. 3 (vi,a, 1) 3, (1));
B (u), < E) 3 (v),-1, @ (<((aaaa-))
6. P: < (1/K) Exe(o,)) 3. (ML,,, (M,, 1) @ (el,,,,, @ 8i (uins));
7. Predict a, E [K] with probability P P(a+ a| Ft.a/ P
8. Receive lr.a.
9. Va E [K] ct,a exp (-nlaa a.l. p. 1/Pr.)): n' (1p::llc:)/( et):
10. {0, 1h (1 1, + n' au
11. Vi {0,1}, (1 0, (M,,,, 0,
12. Vn E C (MiLa d E [M] U (0)). vi.j (0,1), a41((,,i + an(1,, i,)n
13. For d = 1,2,... 1, do vi,j E (0, 1)
Q141 (1 1, Exe(on) 0441 (s)) ae (P(e, k))
Figure 3: GABA-I Algorithm
GABA-II (Learning rate: 1) >
Construct binary support tree via CONSTRUCTBST-C algorithm (see Figure D
Construct full perfect oriented binary tree with height [K)], whose first K leaves represent the actions [K]; Set the root of B;
2. A vertex E C:
(a) (n)) <- 1; Veaa
mm [K] then 0, m) <- 1: clse (n, m) <- O: Ad f1,2,...,9h, Vm depth g (1(m,)) m) A (n, a(m)) + 0, (m))))))
For 1,2...T. do
3. Draw 5, from (w,) with proh. ( = n] x (n,) Go.0 + r;
4. For d o.....g- 1: draw G,441 from (s(G.a)) with prob. I [G.,41 m)) Oc m):
5. Predict a; 4 St.i
Receive Er.a.
ds +- exp(( ve/er) 7. Vi < Enertue) pi (n))(()))); ei <- Enettor) (( m(())((1,.))
8. Vn E ((w)):
(a) (x) t- (u(n))i/((i X.)a)); (x) + N.0((n
(b) B Mar). 0441n, m) == 0e(n,
(c) For d 1,2....9 (1, Os0 (n, (GL(oo=)))) (n,
9. Vn E C ((u)), Met((n) = me((): Vm E B B, (0t)(a, = (n)
Figure 4: GABA-II Algorithm

---

4.3 Parameter Tuning
limitation of the GABA-I regret bound is that it dependent on knowing the optimal values of the parameters é and 77, and for GABA-II on the parameter 77. In the following, we will 1) sketch how to autotune o at little cost and 2) autotune 17, however essentially the cost of moving V (g) outside of the square root.
We first sketch how automatically tune the parameter & that appears in GABA-I. Assume, without loss of generality, that N is an integer power of 2. The idea of our tuning method is that since o is unknown we will "mix" " over possible values of Φ E [o, 1]. In fact, at little cost in regret it is sufficient to just mix over the exponentially increasing values of Φ = 2/N, 4/N, //NN/,N...... 8/N...., N//.....NNNNNN... Thus each specialist is split into logg N specialists, that the new distribution over specialists is
wi (16)))
log2 N x validl
1
x K
1
X startfactor(s) x (1 -
where E de
W1 (8&) 1. Implementing this efficiently is similar to the implemen- tation of GABA-I, except that we now have log, N copies of the BST Ca. each initialized with different value of Φ. On each trial the computed values from the log2 N copies of the BST Cg are summed to find the prediction vector. After receipt of the loss, all copies of the BST are updated as in GABA-I. The regret bound of this autotuning with respect to ó is equal, up to an Ol y (lgg))g(NN) factor, to that of GABA-I with the optimal Ø, but comes at the cost of an additional O (log(NN) factor in the computation time.
Now that we have shown how to automatically tune o in GABA-I we are left with the learning rate 1) in both algorithms. We first note that, with any 1). the regret of both algorithms is T/n /n + /2, where is the robustified resistance weighted cutsize V multiplied by logarithmic terms (one in GABA-I and two in GABA-II). By setting = / / 2/KT we get a regret of (T + 1) / addition, if T is unknown then doubling trick can be performed with this result to get a regret bound of (KT) with parameters needed. We compare this to the regret bound of O ((VKTT) that comes from the optimal tuning of ry. It remains an open problem to bring T inside the square-root.
KT/2. In
Even with the above knowledge-free tuning of 7). our methods improve over the baseline comparator of running an independent EXP3 algorithm for each of the N users many natural scenarios. Recall that in this case the induced regret is then Ö(V KT) (see (2). Consider a very large social network where the bandit problem is to show 1-of-K advertisements (for simplicity assume K E O()) at the nodes (users). Now consider the case that each user is served at most one advert, i.e., there is at most single trial for any given user. Since N > T the bound of the baseline is now the vacuous regret e (T)) We can intuitively see that this analysis is correct since the baseline algorithm is now just picking single "uniformly at random" advertisement from [K] for each user independently.
However, observe that when (y) E o( ö(VT) we get ((V()) S ö(T), which is non-vac non-vacuous. Intuitively, GABA-I/II may achieve this result since algorithmically they are exploiting the network structure.
5 Conclusion
We considered a contextual, non-stochastic bandit problem in which the finite set of contexts (a.k.a users) form social network and the inductive bias is that if the social link between two users is strong then actions that perform well for one of these users are likely to perform well for the other. We gave two highly efficient algorithms for this problem, both with good regret bounds. Since this work is theoretical in nature we cannot foresee any potential negative societal impacts.
In the future it may be interesting to investigate extensions of our algorithms to the stochastic setting, as well as continuous bandit settings. Finally, it would be valuable to study potential applications of our algorithms, with large scale recommender systems being natural candidate. On the theory side our bounds are based on an exponential potential function. Improved adversarial regret bounds were proven for an alternate potential function in [19] and it is open question if our techniques can be extended to that potential.
Acknowledgements. Mark Herbster was supported by the U.S. Army Research Laboratory and the U.K. Ministry of Defence under Agreement Number W91 16-116--0000. Stephen Pasteris and Massimiliano Pontil were supported in part by EPSRC Grant N. EP/P009069/1 and SAP SE.
10

---

References
[1] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual bandit approach to personalized news article recommendation. In Proceedings the 19th International Conference on World Wide Web, WWW '10, pages 661-670, New York, NY, USA, 2010. Association for Computing Machinery.
[2] Sofía S Villar Villar, Jack Bowden, and James Wason. Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges. Statistical Science, 30(2):199- 215, 2015.
[3] Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008.
[4] Rie Kubota Ando and Tong Zhang. framework for learning predictive structures from multiple tasks and unlabeled data. J. Mach. Learn. Res., 6:1817-1853, December 2005.
[5] Andreas Maurer and Massimiliano Pontil. Excess risk bounds for multitask learning with trace norm regularization. In Conference on Learning Theory, pages 55-76, 2013.
[6] Maria-Florina Balcan, Mikhail Khodak, and Ameet Talwalkar. Provable guarantees for gradient- based meta-learning. International Conference on Machine Learning, pages 424-433, 2019.
[7] Giovanni Cavallanti, Nicolò Cesa-Bianchi, and Claudio Gentile. Linear algorithms for online multitask classification. J. Mach. Learn. Res., 11:290122934, December 2010.
[8] Pierre Alquier, The Tien Mai, and Massimiliano Pontil. Regret Bounds for Lifelong Learning. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on rtificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 261-269, Fort Lauderdale, FL, USA, 20-22 Apr 2017. PMLR.
[9] Giulia Denevi, Carlo Ciliberto, Dimitris Stamos, and Massimiliano Pontil. Incremental learning- le-learn with statistical guarantees. arXiv preprint arXiv:
2018
[10] Giulia Denevi, Carlo Ciliberto, Riccardo Grazzi, and Massimiliano Pontil. I Learning-to-lear -ealer stochastic gradient descent with biased regularization. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1566-1575, Long Beach, California, USA, 09-15 Jun 2019, PMLR.
[11] Anastasia Pentina and Ruth Umner Lifelong learning with weighted majority votes. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 3612-3620. Curran Associates, Inc., 2016.
[12] Miller McPherson, Lynn Smith-Lovin and James M Cook. Birds of feather: Homophily in social networks. Annual Review of Sociology, 27(1):415 4444, 2001.
[13] M. Herbster, G. Lever, and M. Pontil. Online prediction on large diameter graphs. In NIPS, 2008.
[14] Nicolò Cesa-Bianchi, C. Gentile, Fabio Vitale, and Giovanni Zappella. Random spanning trees and the prediction of weighted graphs. In ICML, 2010.
[15] Y. Freund, R. Schapire, Y. Singer, and Manfred K. Warmuth. Using and combining predictors that specialize. In STOC '97, 1997.
[16] Wouter M. Koolen, Dmitry Adamskiy, and Manfred K. Warmuth. Putting bayes to sleep. In NIPS, 2012.
[17] Aleksandrs Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 121-2))1-228. 2019.
[18] Peter Auer, Nicolò Cesa-Bianchi. Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1):48-7,, January 2003.

---

[19] Jean-Yves Audibert and Sébastien Bubeck. Regret bounds and minimax policies under partial monitoring. Journal of Machine Learning Research, 11(94))2785-283) 2010.
[20] Sébastien Bubeck and Nicolo Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-125 122, 2012.
[21] N. Cesa-Bianchi, C. Gentile, and Giovanni Zappella. A gang of bandits. In NIPS, 2013.
[22] Kaige Yang, X. Dong, and L. Toni. Laplacian-regullrriedd graph bandits: Algorithms and theoretical analysis. AISTATS, 2020.
[23] Sharan Vaswani, M. Schmidt, and L. Lakshmanan. Horde of bandits using gaussian markov random fields. In AISTATS, 2017.
[24] Qingyun Wu, Huazheng Wang, Quanquan Gu, and Hongning Wang. Contextual bandits in a collaborative environment. Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 2016.
[25] Xin Wang. S. Hoi, Chenghao Liu, and M. Ester. Interactive social recommendation. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017.
[26] Huazheng Wang, Qingyun Wu, and Hongning Wang. Factorization bandits for interactive recommendation. In AAAI, 2017.
[27] C. Gentile, S. Li, and Giovanni Zappella. Online clustering of bandits. In ICML, 2014.
[28] S. Li, C. Gentile, and Alexandros Karatzoglou. Graph clustering bandits for recommendation. ArXiv, abs/1 0/bs/1605.000 605.00596, 2016.
[29] C. Gentile, S. Li, Purushottam Kar, Alexandros Karatzoglou, Giovanni Zappella, and Evans Etrue. On context-dependent clustering of bandits. In ICML, 2017.
[30] S. Li, C. Gentile, Alexandros Karatzoglou, and Giovanni Zappella. Data-dependent clustering in explovation-explootation algorithms. ArXiv, abs/1502.03473, 2015.
[31] S. Li and Purushottam Kar. Context-aware bandits. ArXiv, abss/550.003144, 2015.
[32] S. Li, C. Gentile, Alexandros Karatzoglou, and Giovanni Zappella. Online context- dependent clustering in recommendations based on exploration-exploitaiio algorithms. ArXiv, 160..03444 2016.
[33] S. Li, Alexandros Karatzoglou, and C. Gentile. Collaborative filtering bandits. Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, 2016.
[34] Kaige Yang and L. Toni. Graph-based recommendation system. 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 798-802, 2018.
[35] Trong Nguyen and H. W. Lauw. Dynamic clustering of contextual multi-armed bandits. Proceedings of the 23rd ACM International Conference Conference on Information and Knowledge Management, 2014.
[36] Zongguo Wang, Chicheng Zhang, M. Singh, L. Rick, and K. Chaudhuri. Multitask bandit learning through heterogeneous feedback aggregation. In AISTATS, 2021.
[37] Zongguo Wang, M. Singh. Chicheng Zhang. L. Rick, and K. Chaudhuri. Stochastic multi-playe bandit learning from player-dependent feedback. 2020.
[38] Hassan Saber, Pierre Ménard, and Ambryy Maillard. Optimal strategies for graph- structured bandits. ArXiv, abs/2007. 032244, 2020.
[39] Sabina Tomkins, Peng Liao, P. Klasnja, and S. Murphy, Intelligentpooling: Practical thompson sampling for mhealth. ArXiv, 0oss/200..115// 2020.
[40] Silviu Maniu, Stratis loannidis, and B. Cautis. Bandits under the influence. 2020 IEEE International Conference Data Mining (ICDM), pages 1172-1177, 2020.
12

---

[41] L. Yang, Bo Liu, L. Lin, Feng Xia, Kai Chen, and Qiang Yang. Exploring clustering of bandits for online recommendation system. Fourteenth ACM Conference on Recommender Systems, 2020.
[42] Huazheng Wang. Qingyun Wu, and Hongning Wang. Learning hidden features for contex- tual bandits. Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 2016.
[43] Swapna Buccapatnam, A. Eryilmaz, and N. Shroff. Multi-armed bandits in the presence of side observations in social networks. 52nd IEEE Conference on Decision and Control, pages 7309-7314, 2013.
[44] S. Kar, H. Poor, and S. Cui. Bandit problems in networks: Asymptotically efficient distributed allocation rules. IEEE Conference on Decision and Control and European Control Conference, pages 1771-1778, 2011.
[45] Balázs Szörényi, R. Busa-Fekete, I. Hegedüs, Róbert Ormándi, M. Jelasity, and B. Kégl. Gossip-based distributed stochastic bandit algorithms. In ICML, 2013.
[46] N. Korda, Balázs Szörényi, and S. Li. Distributed clustering of linear bandits in peer to peer networks. ArXiv, abs/1664.007700 2016.
[47] Abishek Sankararaman, A. Ganesh, and Shakkottai. Social learning in multi agent multi armed bandits. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3:1 35, 2019.
[48] L. E. Celis and F. Salehi. Lean from thy neighbor: Stochastic and adversarial bandits in a network. ArXiv, abs/ 704.044704 2017.
[49] Yogev Bar-On and Y. Mansour. Individual regret in cooperative nonstochastic multi-armed bandits. In NeurlPS, 2019.
[50] N. Cesa-Bianchi, C. Gentile, Y. Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. ArXiv, abs/1602.04741, 2016.
[51] Bo Liu, Y. Wei, Y. Zhang, Yan, and Qiang Yang. Transferable contextual bandit for cross- domain recommendation. In AAAI, 2018.
[52] L. Cella, A. Lazaric, and M. Pontil. Meta-learning with stochastic linear bandits. ArXiv, Aas/2005.085331 2020.
[53] Michal Valko, R. Munos, B. Kveton, and Tomás Kocák. Spectral bandits for smooth graph functions. In ICML, 2014.
[54] M. K. Hanawal, Venkatesh Saligrama, Michal Valko, and R. Munos. Cheap bandits. ArXiv, abs/ abs/1500.04782, 2015.
[55] A. Deshmukh, Ó. Dogan, and C. Scott. Multi-task learning for contextual bandits. In NIPS, 2017.
[56] Michal Valko. Bandits on graphs and structures. Diss., École normale supéricure de Cachan- ENS Cachanz, 2016.
[57] M. K. Hanawal and Venkatesh Saligrama. Efficient detection and localization on graph struc- tured data. 2015 IEFE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5590-5594, 2015.
[58] M. K. Hanawal and Venkatesh Saligrama. Cost effective algorithms for spectral bandits. 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1323- 1329, 2015.
[59] Sylvain Lamprier, Thibault Gisselbrecht, and P. Gallinari. Variational thompson sampling for relational recurrent bandits. In ECML/PKDD, 2017.
13

---

[60] Aadirupa Saha, Shreyas Sheshadri, and C. Bhattacharyya. Be greedy: How chromatic number meets regret minimization in graph bandits. In UAI, 2019.
[61] N. Alon, N. Desa-Bianchi, C. Gentile, Shie Mannor, Mansour, and O. Shamir. Nonstochastic multi- armed bandits with graph-structured feedback. SIAM J. Comput., 46:1785-1822 1826, 2017.
[62] N. Alon, N. Cesa-Bianchi, O. Dekel, and T. Koren. Online learning with feedback graphs: Beyond bandits. In COLT, 2015.
[63] Meng Fang and D. Tao. Networked bandits with disjoint linear payoffs. Proceedings of the 20th ACM SICKDD international conference on Knowledge discovery and data mining, 2014.
[64] M. Herbster, Stephen Pasteris, and Fabio Vitale. Online sum-product computation over trees. In NIPS, 2012.
[65] M. Herbster and Robinson. Online prediction of switching graph labelings with cluster specialists. In NeurlPS, 2019.
[66] Lyons, Russell, and Yuval Peres. Probability on trees and networks. Cambridge University Press, 2017.
[67] Nicolò Cesa-Bianchi, Claudio Gentile, Fabio Vitale, and Giovanni Zappella. Random spanning trees and the prediction of weighted graphs. Journal of Machine Learning Research, 14(2):1251- 1284, 2013.
[68] R. Pemantle. Uniform random spanning trees. arXiv: Probability, 2004.
[69] Aaron Schild, An almost-linear time algorithm for uniform random spanning tree generation. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018.
[70] D. Durfee, Rasmus Kyng, J. Peebles, A. Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017.
[71] Volodimir G. Vovk. Aggregating strategies. Proc. of Computational Learning Theory, 1990.
[72] David Haussler, Jyrki Kivinen, and Manfred K Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Transactions Information Theory, 44(5):1906 1925, 1998.
[73] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Information and computation, 108(2):212226) 1994.
[74] Yoav Freund and Robert E Schapire. A deeision-theoretcc generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-13,, 1997.
[75] David Barber. Bayesian Reasoning and Machine Learning. Cambridge University Press, 2012.
[76] Leslie Ann Goldberg and Mark Jerrum. The complexity ferromagnetic ising with local fields. Combinatorics, Probability & Computing, 16(1):43-61 61, 2007.
[77] Arthur L. Delcher, Adam J. Grove, Simon Kasif, and Judea Pearl. Logarithmic-time updates and queries in probabilistic networks. CoRR, abs/1408. 1479, 2014.
[78) Guy Bresler, D. Shah, and L. F. Voloch. Collaborative filtering with low regret. Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, 2016.
[79] Guy Bresler, D. Shah, and L. F. Voloch. Regret guarantees for item-item collaborative filtering. arXiv: Learning, 2015.
[80] Nicolò Cesa-Bianchi and G. Lsugosi. Combinatorial bandits. J. Comput. Syst. Sci., 78:1404-
1422, 2009.
[81] Alon Cohen, Tamir Hazan, and T. Koren. Tight bounds for bandit combinatorial optimization. In COLT, 2017.
14

---

[82] S. Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and K. Kawarabayashi. Improved regret bounds for bandit combinatorial optimization. In NeurlPS, 2019.
[83] Kareem Amin, M. Kearns, and U. Syed. Graphical models for bandit problems. In UAI, 2011.
[84] Aleksandrs Slivkins. Contextual bandits with similarity information. J. Mach. Learn. Res., 15:2533-255 2568, 2011.
[85] Qingyun Wu, N. lyer, and Hongning Wang. Learning contextual bandits in a non-stationary environment. The 41st International ACM SIGIR Conference on Research and Development in Information Retrieval, 2018.
[86] Qingyun Wu, Huazheng Wang, Yanen Li, and Hongming Wang. Dynamic ensemble of contextual bandits to satisfy users' changing interests. The World Wide Web Conference, 2019.
[87] Xiao Xu, Fang Dong, Yanghua Li, Shao jian He, and X. Li. Contextual-bandii based personalized recommendation with time-varying user interests. ArXiv, abs/2003.00359, 2020.
[88] Chuanhao Li, Qingyun Wu, and Hongning Wang. Unifying clustered and non-stationary bandits. In AISTATS, 2021.
[89] Mark Herbster, Stephen Pasteris, and Lisa Tse. Online multitask learning with long-term memory. In H. Larochelle, M. Ranzato, Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17779-17791 Curran Associates, Inc., 2020.
15


Reviews:
[{"review_id": "vqLK_Z4g5K", "reviewer": "Reviewer_7145", "summary": "In this paper the authors consider the problem of adversarial contextual bandits, where the contexts (finite) and the reward function are adversarial, but there exists a graph structure among the various context vectors. The goal of the online learning algorithm is to select a mapping from the context to an action that minimizes the total regret. Here, the aim is to achieve results better than naively treating the cross product of contexts and actions as an arm and running a EXP3 type algorithm. The authors present regret bounds that depend on an interesting quantity of the graph: weighted effective resistance. This quantity improves the regret to logartihmic when the max-cut size in the graph is small and recovers the worst-case bound (treating the number of context times the number of actions as the arms).", "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": "Originality: The setting considered in this paper is a new for the (oblivious) adversarial setting. Moreover, the notion of complexity used in this paper is new for the bandit literature (although well known in the graph theory and theoretical computer science communities) and it is interesting connection this paper brings about. The authors need to device new algorithms to exploit this graph. Underlying the two algorithms is a key data structure that embeds the graph G into a fully height binary tree such that the required complexity measure only increases by a constant factor in this new tree. Then they exploit prediction with expert advice type algorithm to update weights. In particular, they combine the standard belief propagation algorithm determined on the graphical model induced by this BST. This induces a distribution over the actions at time $t$ given the context $u_t$. They then sample using this distrubtion and perform a EXP3 style update of the parameters of the belief propagation algorithm. As far as I can tell both the algorithms presented in this paper (they differ in a small nuance) are original.\n\n\nQuality/Clarity: The paper is excellently written with the main results, the algorithmic ideas and the construction of the required data-structures are well-communicated (even if many of them are from prior work, they introduce the necessary components in this paper). I did not have trouble understanding the main ideas of the paper. Although some of the notations were clumsy, I think that it is unavaiodable given the nature of the graph algorithm.\n\nSignificance: The results in this paper add to the literature of learning with expert advice and also learning on social networks. Each of these areas themselves have had and have wide range of applications. Oblivious adversary goes beyond the stochastic versions that is usually made in the learning on social networks which typically makes it non-applicable in real-world settings. This paper shows that even in the adversarial setting, assuming randomness in the social graph structure as opposed to losses, one can retrieve similar bounds, which is interesting.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The primary limitation of this paper is that although mathematically interesting, they do not make good case for motivating examples. In particular, the paper would have become much more stronger if they had a concrete motivating application where the losses are (necessarily) adversarial while the graph structure is randomized. Along those lines, the paper makes claims about improving computational complexity (asymptotically) even for the belief propagation problem. It would have been interesting to see some simulations to see how this translates for reasonable sized but smaller instances. \n\nSocietal impact\nThis is a theoretical paper and the impact on society is negligible. It is as good/bad as the entire area of theoretical online learning has had on society and thus, this paper itself does not pose any issues.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "sTJ_xt1Oq9_", "reviewer": "Reviewer_Dc7h", "summary": "This paper studies the following contextual variant of the adversarial multi-armed bandit problem. Each round t (for T rounds), the adversary begins by choosing a context (“user”) u_t in [N] and a loss function l_t from [K] -> R, and reveals the context to the learning algorithm. Based on this context, the learner must select an action a_t in [K]. The adversary then reveals the value of l_t(a_t) to the learner, which the learner suffers as loss. By running a separate instance of EXP3 for each context, it is possible for the learner to achieve a total loss of O(sqrt(NKT)). This paper asks the question of whether we can do better if we believe that “similar” users should be subject to “similar” losses.\n\nThe authors answer this in the following way. They assume there is some given graph structure on the N users (“social network graph”), where users i and j are connected with a link of weight w_{i, j} (and higher weights mean users are more likely to have similar losses). They then give the following non-uniform regret bound: against the fixed policy y : [N] -> [K], their algorithms get regret of the form ~ O(sqrt(KT f(y))), where f(y) is a function that measures how “consistent” y is with the social network graph. For example, if y(s) is a constant function (doesn’t depend on user), then this is very consistent with any graph structure, and f(y) ~= log(N). On the other hand, for arbitrary y, y(s) can be as large as ~O(N), recovering the original ~O(sqrt(KTN)) bound. Formally, f(y) is something like the average effective resistance between users with different values of y(s). \n\nThe author’s algorithms are based on a technique they call “predicting with specialists” (extending the work of Freund et al.), where one maintains a distribution over functions mapping contexts to either actions or the decision to abstain. In particular, it’s possible to get a non-uniform regret bound for such an algorithm that only depends on the starting distribution and the policy to which the algorithm is being compared (similar in flavor to the regret bounds above). The authors then define two different starting distributions which lead to two algorithms (GABA-I and GABA-II) with good regret bounds for their setting. The first starting distribution has a higher support size (and larger eventual runtime), but lower overall regret than the second. The second algorithm is based off a clever embedding of the social network graph into a full binary tree that partially captures the connectedness of the original network graph.\n\nFinally, the authors demonstrate how to implement their algorithms efficiently. In particular, even though the first distribution has an exponentially large support size (and thus naively would require exponential time / space to run), they show how to implement it in only O(K log N) time per round via a clever online belief propagation algorithm. Similarly, they show how to implement GABA-II in only O(log K log N) time per round (exponentially faster than GABA-1). \n\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": "\nI enjoyed reading this paper -- the high-level setting is very natural (adversarial contextual bandits with graph-based similarity information), the technical content was non-trivial and reasonably novel (at least to me), and the paper was well-written. \n\nThe only downside I really see is that it is a little hard for me to parse what the regret bounds mean in settings that might naturally come up -- in particular, what sort of uniform regret bounds do these results imply if we impose constraints on the adversary’s behavior (which is the more common way to think about these types of bandit problems). For example, if the N contexts can be clustered into G groups, and the losses are generated stochastically in such a way that losses of actions in the same group are the same (presumably corresponding to some social network graph composed of G highly-weighted cliques), does the dependence on N decrease to a dependence on G? I think some examples like this would be helpful for conveying intuition for what the results say.\n\nI think the paper could also benefit by citing some of the literature on adversarial contextual bandits (and mentioning that their paper falls into this setting). There has even been some work on adversarial contextual bandits with similarity between contexts: see e.g. “Contextual Bandits with Similarity Information” by Slivkins et al., or “Contextual Bandits with Cross-Learning” by Balseiro et al. I don’t think any of these papers come anywhere close to subsuming these results (the graph-based model in this paper seems quite different), but some discussion would be helpful. \n\nOverall, I think this paper will be of interest to the NeurIPS audience. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns here. The authors explicitly and adequately address this in their paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "M8INsqxm8GK", "reviewer": "Reviewer_A1FJ", "summary": "This paper studies a new multi-armed bandit setting termed \"Gang of Adversarial Bandits\", in which a learner solves an instance of the adversarial MAB problem for each of $N$ different users. Without further assumptions on the $N$ users, essentially one can only solve the instances independently (e.g., running $N$ copies of the EXP3 algorithm), and incur a loss that scales as $\\sqrt{KNT}$, where $K$ is the number of actions and $T$ is the time horizon.\n\nIn contrast, the authors assumes that the connections between the users are specified by a known weighted graph $G$, and assumes that nearby vertices in the graph (measured in terms of the effective resistance) are more likely to have the same action in the \"benchmark\" mapping $y: [N] \\to [K]$. Both algorithms proposed in the paper are instantiations of the \"specialists\" framework, using graph $G$ to define certain initial/prior distributions over a carefully-chosen family of \"specialists\".\n\nThis approach involves sampling from the (exponentially large) space of mappings from users to actions, so a naive implementation would be computationally costly. The authors show that by sampling a random spanning tree and then embedding the users to a binary tree, the running time per step can be significantly reduced to either $O(K\\log N)$ or $O(\\log K\\log N)$.", "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": "The paper is generally well-written, except that some of the technical parts (e.g., Figures 3 and 4 can be hard to parse). The authors provided adequate motivation for the problem setting, as well as the specific approach that they adopt (e.g., why resistance weighted cutsize can be favorable, and the distinction between $\\Phi$ and $\\Psi$).\n\nI have a question about Corollaries 3 and 4: the choice of the learning rate $\\eta$ in both algorithms depends on $\\Psi(y)$, where $y$ is the \"benchmark\" to be compared to, and should be unknown to the learner. So why can we set $\\eta$ in this way? (My guess is that we can apply a doubling trick on this quantity, e.g., by considering $\\log N$ copies of the algorithm with $\\Psi(y)$ being $1, 2, 4, 8, \\ldots, N$ and then running another EXP3 on top of these. Even if this were true, some explanation seems to be needed.)\n\nOverall, I feel that the authors proposed a new setting that is interesting and well-motivated. The proposed solutions follow a relatively standard framework, but still require non-trivial ideas as well as tools from other fields to obtain computationally efficient algorithms. I would recommend accept.\n\nMinor comments:\n- Equation (2): Some justification/explanation would be helpful for this claim.\n- Displayed equation below Line 138: The denominator seems a bit off after the colon---is it $x_u - x_v = 1$, and should it be a constraint of the $\\min$?", "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": "2"}, "extra_text": {}}, {"review_id": "3h_M62iQM7s", "reviewer": "Reviewer_GuKU", "summary": "This paper considers the problem of contextual bandit problem with adversarial loss and finite number of contexts. Specifically, the authors consider the case where the contexts are related in some sense such that the action generated by a policy seeing one context may be related to the one seeing another similar context. The similarity is measured by a weighted undirected graph G. The authors then design two efficient algorithms which achieves $\\widetilde{O}(\\sqrt{\\Psi(y) K T})$ regret bound in this setting where $y$ is the benchmark policy and $\\Psi(y)$ is a dispersion measure of $y$ over the context. This result is better than $\\widetilde{O}(\\sqrt{NKT})$, where $N$ is the number of contexts.\n\nThe algorithm is mainly based on classic EXP3/EXP4 algorithm. As generally EXP4 is inefficient, the authors provide two efficient implementation by using online belief propagation over a complete binary tree for contexts, which is generated from the graph G. The first algorithm GABA-I has $O(K\\ln(N))$ computation complexity per round while the second algorithm GABA-II has $O(\\ln(K)\\ln(N))$ computation complexity but with a factor of $\\log(N)$ worse regret bound.", "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": "Pros:\n1. The problem proposed in this paper is well motivated and closer to the application, which considers the similarity among the contexts instead of considering them independently. \n\n\n2. The authors propose algorithms with theoretical guarantees on the regret bound and analyze the computational cost of the algorithm, which is efficient and implementable in practice. I didn't check the proof in very details, especially the second algorithm GABA-II but overall it looks sound to me. \n\n\n3. The related works are adequately cited.\n\nCons:\n1. One of my main concern of this work is about the tuning issue. As the authors mentioned in the paper, the obtained bound is an non-uniform bound which gives different bounds for different comparator policy $y$. I was assuming this is a parameter-free algorithm but it seems that $\\phi$ and $\\eta$ in the algorithm depend on $\\Psi(y)$, which may not be known during learning as we do not know which $y$ we are comparing to. Is my understanding correct? If so, then the result may be less attractive and interesting as if we have one policy $y_0$ whose $\\Psi(y_0)$ is large, then the regret will scale with this policy, even though $y_0$ is a suboptimal policy. \n\n\n2. Also I wonder whether there are some better intuitions on the social network graph G defined in the paper, especially on the weight of the edge? It seems that this weight is only used in describing the property of a uniformly generated spanning tree and giving an upper bound on the quantity $\\mathbb{E}\\left[\\sum_{i=1}^{N-1} \\mathbb{I}[y(u)\\ne y(u+1)]\\right]$ in Lemma 1, which looks more like a technical design. Although in Section 2.1, the authors say that the larger the weight is, the more paths there are between two contexts, the less penalty (on $\\Phi(y)$ or $\\Psi(y)$) will be paid if $y$ has different output actions on these two contexts, I still could not have a very intuitive idea on this weight. Or is there any other metrics to measure the similarity among contexts?\n\n\n3. About the size of $\\Phi(y)$. Although I understand $\\Phi(y)\\leq N$ and for some specific graph and policy pairs (as shown from line 156 to line 166) this value is much less than $N$, I wonder whether in some more realistic applications, this value could be much better than the worst case? I think this will show more contributions to the proposed algorithms.\n\n\n4. For the design of the two algorithms, although the runtime each round is $O(K\\ln (N))$, which is efficient, the space complexity is still $O(KN)$, which is linear in the number of contexts and is not that efficient. I was supposing that by utilizing the social network graph G, we can reduce the size of the context in some sense and lead to a better space complexity. I think reducing this space complexity should also be important.\n\n\n5. Some minor typos:\n- line 56 $[1,n]$ -> $[1,N]$\n\n\n======= After rebuttal =========\nDuring the rebuttal, the authors addressed my issues and I updated my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact is shown in the work. Suggestions are written in Cons. in the Main Review.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "7 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Some concerns from the reviewers were addressed during the discussion phase.
Despite the tuning issues and the suboptimal bounds brought up in the discussion,
reviewers reached a consensus that the paper studies a well-motivated problem with
some interesting results.
Please do incorporate all the suggestions/discussions from the reviews into the final version.

Decision: Accept (Poster)