A Gang of Adversarial Bandits
Year: 2021

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 toK 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 Ψ. We present two learning algorithms, GABA-I and GABA-II which exploit the network structure to bias towards functions of low Ψ values. We show that GABA-I has an expected regret bound of O( √ ln(NK/Ψ)ΨKT ) and per-trial time complexity of O(K ln(N)), whilst GABA-II has a weaker O( √ ln(N/Ψ) ln(NK/Ψ)ΨKT ) regret, but a better O(ln(K) ln(N)) per-trial time complexity. We highlight improvements of both algorithms over running independent standard MABs across users.

text: √ ln(NK/Ψ)ΨKT ) and per-trial time complexity
of O(K ln(N)), whilst GABA-II has a weaker O( √
ln(N/Ψ) ln(NK/Ψ)ΨKT ) regret, but a better O(ln(K) ln(N)) per-trial time complexity. We highlight improvements of both algorithms over running independent standard MABs across users.

heading: 1 Introduction
text: During the last decade multi-armed bandits (MAB) have received a 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 a learner explores sequentially the environment in order to find the best item (arm) within a prescribed set. At each step in the exploration the learner chooses an arm, after which feedback (typically a 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 a small cumulative loss in comparison to the cumulative loss that would have been obtained by always
* Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
selecting the best arm in hindsight. Applications of MAB are numerous, including recommender systems [1], clinical trials [2], and adaptive routing [3], among others.
In this paper we study the problem in which the learner is facing several MAB problems that are related according to 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, 5, 6, 7, 8, 9, 10, 11] 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 algorithms. 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 GABAII that learn jointly MAB models for N users over K possible actions. Both algorithms are designed to exploit network structure while being (extremely) computationally efficient. We derive expected (over the algorithms’ randomizations) regret bounds. The bounds scale with the dispersion measure Ψ ∈ [1, N ] of the best actions over the graph. For GABA-I the bound1 is of order of O( √ ln(NK/Ψ)ΨKT ), where T is the number of trials, and has a per-trial time complexity of O(K ln(N)). On the other hand GABA-II has a weaker expected regret bound of O( √ ln(N/Ψ) ln(NK/Ψ)ΨKT ) but is faster, having a per-trial time complexity of O(ln(K) ln(N)). Thus the GABA-I algorithm improves on algorithms that treat each user independently, as in the best case the regret improves from O( √ N) to O( √ lnN) 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 G is determined by a set of undirected links between users {ωu,v}Nu<v where ωu,v ∈ [0,∞) indicates the magnitude of the link between user u and v. For all t ∈ [T ] we have a user ut ∈ [N ] and a loss vector `t ∈ [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, . . . , T . On trial t:
1. Nature reveals user ut ∈ [N ] to Learner, 2. Learner selects action at ∈ [K], 3. Nature reveals loss `t,at ∈ [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 bound2 ,
E [ ∑ t∈[T ] `t,at ] − min a∈[K] ∑ t∈[T ] `t,a ∈ O (√ K ln(K)T ) , (1)
1The bounds of GABA-I and GABA-II however depend on oracular knowledge of optimal tuning parameters. We discuss this as well as a means of lessening this dependency following Corollary 5.
2An algorithm was given in [19] that removed the lnK 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 a uniform regret bound of (see e.g., [20])
E [ ∑ t∈[T ] `t,at ] − min y:[N ]→[K] ∑ t∈[T ] `t,y(ut) ∈ O (√ K ln(K)NT ) , (2)
i.e., for each user u the best action is y(u) and we now pay an additional constant factor of √ N in our regret. In this work we exploit the social network structure to prove a non-uniform regret bound for the GABA-I algorithm (see Corollary 4) of
R(y) := E [ ∑ t∈[T ] `t,at ] − ∑ t∈[T ] `t,y(ut) ∈ O (√ K ln ( KN Ψ(y) ) Ψ(y)T ) , (3)
for any mapping of users to actions y : [N ] → [K]. The non-uniform regret now depends on Ψ(y) ∈ [1, N ] (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( √ ln( eNΨ(y) )Ψ(y)). When the best action across the network is nearly uniform then the dispersion Ψ(y) ∈ O(1), in contrast when the dispersion is maximal then Ψ(y) = N thus in the best case the regret with respect to the number of users improves from O( √ N) to O( √ lnN) and in the worst case the regret only increases by a constant factor. The first algorithm GABA-I obtains the regret (3) while requiring O(K lnN) time to predict and update. The second algorithm GABA-II’s regret (see Corollary 5) is larger by a O( √ lnN/Ψ(y)) factor but now prediction is at an even faster O(ln(K) ln(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 are more closely related to 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 linear-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 to context vectors in a similar way [21, 22, 23, 24, 25, 26] but as far as we 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 in the same cluster are homogenous [27, 28, 29, 30, 31, 32, 33, 34, 35]; as well as other models [36, 37, 38, 39, 40, 41, 42, 43]. There are also works on networked, homogenous multi-user bandit models with limited communication between users [44, 45, 46, 47, 48, 49, 50]. Related to the multiuser 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 a network and it is assumed that neighbouring actions give similar losses [53, 54, 55, 56, 57, 58, 59, 60], as well as other networked-action models [61, 62, 63]. In addition to the seminal paper on adversarial bandits [18], our work utilises ideas from several different papers [13, 14, 15, 16, 64, 65].
Notation. Given a set X we define 2X to be its power-set, that is: the set of all subsets of X . For any positive integer m, we define [m] := {1, 2, . . . ,m}. For any predicate PRED , JPREDK := 1 if PRED is true and equals 0 otherwise. Given vectors x,x′ ∈ RK we define x · x′ to be their inner product (i.e., equal to ∑ i∈[K] xixi′ ) and we define x x′ to be their component-wise product (i.e., (x x′)i := xix′i for all i ∈ [K]). We define ‘1’ to be the K-dimensional vector in which each component is equal to 1 . Given a full oriented binary tree B we denote the set of its vertices also by B. Given a non-leaf vertex n ∈ B let /(n) and .(n) be its left child and right child respectively. Given a non-root vertex n ∈ B let ↑(n) be its parent. Given a vertex n ∈ B let ⇑(n) and ⇓(n) be its set of ancestors and leaf-descendants (i.e. descendants which are leaves) respectively. Given a vertex n ∈ B we define J(n) and I(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 {ωu,v : 1 ≤ u < v ≤ N}. For convenience we assume N is a power of two.3
3This assumption does not limit our results because to run our algorithms one can always add dummy vertices without altering input weights, so as to force N to be a power of two.

heading: 2 Modeling a Social Network as a Resistive Network
text: In this section we introduce the tools necessary to formalize our complexity measures, as well as the ones to implement our algorithms.

heading: 2.1 Conceptual Tools
text: To minimize the incurred loss, Learner can exploit the similarity between any pair of users defined by the weights ωu,v of user graph edges for all u, v ∈ [N ]. The function y : [N ]→ [K] is completely unknown to Learner, and can be viewed as labeling each user with its best/favorite action. Within this context, our homophilic bias can be stated as follows: users strongly connected w.r.t. the link weights ω, tend to be associated with the same label.
The complexity measure used for this problem is 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., ∑ u<vJωu,v 6= 0KJy(u) 6= y(v)K, and the weighted cutsize is defined as the sum of the edge weights ωu,v over all pairs of users u and v having different labels, i.e., ∑ u<v ωu,vJy(u) 6= y(v)K [14]. The effective resistance between two given nodes u and v of a graph is a 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 ωu,v corresponds to a 1ωu,v resistor, the effective resistance between u and v is the power required to hold between them a unit voltage difference for a 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 is 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 u and v is
r(u, v) := 1 minx∈RN { ∑N i<j ωi,j(xi − xj)2 : xu − xv = 1} .
Interestingly enough, for all u, v ∈ [N ] , r(u, v) is exactly equal to the probability that the edge {u, v} is included in a uniformly generated random spanning tree of the given user graph G (see, e.g., [66]).
The resistance weighted cutsize Φ(y) [67] is the weighted sum of the effective resistances r(u, v) between any two nodes u and v with different labels. i.e.,
Φ(y) := N∑ u<v ωu,vr(u, v)Jy(u) 6= y(v)K (4)
and then its robustifcation is defined as
Ψ(y) := 1 + min z:[N ]→[K]
( Φ(z) + ∑ u∈[N ] Jz(u) 6= y(u)K ) . (5)
The first quantity (4) can be viewed as a dispersion measure based on the above mentioned homophilic tendency. It has several advantages compared to the weighted cutsize in measuring the degree of homophily violation [67]. The most significant property is that it is locally density-dependent because the contribution to Φ(y) of each edge (u, v) such that y(u) 6= y(v) is inversely proportional to how strongly u and v are connected in their user graph local area. Indeed, because of the effective resistance, the potential contribution to Φ(y) 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 y respects these clusters then in many cases Φ(y) 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 a labeling function y(·), 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 ′ ⊂ G, suppose that there are n−1G edges connecting the nodes of C with the nodes of C ′. Then we have Φ(y) ∈ O(G).
Thus in this archetypical case our regret bounds now 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 y such that Φ(y) can be dramatically reduced by simply changing the labels of a relatively small number of users. To give an 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 0. This is precisely the labeling property that is captured by Ψ(y), which is equal to the minimum, over all labelings z, of the sum of Φ(z) and the number of vertices for which y and z differ (plus 1). In this case we have therefore Ψ(y) = 1 + Φ(y∗) + 1 = 2, where y∗ is the labeling obtained by changing y(u) to make it equal to all other labels, so that Φ(y∗) = 0, whereas Φ(y) = N − 1 .

heading: 2.2 An Embedding to Enable Fast Computation
text: A uniformly generated random spanning tree (RST) is defined as a spanning tree selected with a probability proportional to the product of the weights of all its edges (see, e.g., [66]). It represents a fundamental tool in several mathematical fields, e.g., combinatorial geometry, algebraic graph theory, stationary Markov chains [68], and can be viewed as a way to summarize the topological information of the input network. When the input graph is weighted as in our case, it can be generated in time almost linear in the number of edges [69, 70].
In a preliminary phase, our algorithms operate as follows (see Fig. 1). A RST T of the input social network is drawn (step 1). Thus, an order of the N users is determined through a depth-first visit of T (step 2). From here on we assume, without loss of generality, that user u ∈ [N ] is the u-th vertex visited. This step is necessary to make the algorithms noise-tolerant, and is strictly related to the improvement of the complexity measure Ψ(y) over Φ(y). 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 data-structures of our algorithms.
We conclude this section by showing a result which will be useful in the analysis of our algorithms, and stems directly only from the user order determined by the depth-first visit of T . If we consider the line graph L connecting the users u with u+ 1 for all u ∈ [N − 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 user graph. This result can be viewed as the multi-class extension of part 2 of Theorem 6 in [67].
Lemma 2 ([67, Theorem 6]). For any given input user graph, we have
E  ∑ u∈[N−1] Jy(u) 6= y(u+ 1)K  ≤ 2Ψ(y) , where the expectation is over the draw of the uniform random spanning tree T .

heading: 3 Predicting with Specialists
text: 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 a 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 we will exploit an analogue of message-passing as used in graphical models [75] to predict very efficiently over exponentially-sized sets of predictors. Broadly speaking we would like build a 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 NP-hard [76]. Thus a benefit of the embedding to a 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 our 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(KN) time to predict [75] per trial or using the method of [77] O(K3 logN) time. However, we will require only O(K logN) and O(logK logN) for the GABA-I and GABA-II algorithms respectively (see Figures 3 and 4). To accomplish this technically we adapt the method of specialists [15, 16].
A specialist is a prediction function s : [N ]→ {1, 2, . . . ,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 {1, 2, . . . ,K, } where [K] corresponds to predicted actions, but ‘ ’ indicates that the specialist abstains from predicting an action. Thus a specialist specializes its prediction to part of the context space. We denote the set of all specialists as S := {1, . . . ,K, }[N ]. As a single specialist only predicts over part of the context space, we need a set of specialists S ⊆ S if we wish to define a function that predicts an action for every context. A specialist set S ⊆ S is well-formed if for each u ∈ [N ] there exists a unique specialist s ∈ S such that s(u) ∈ [K]. For such a user u and specialist s we then define S†(u) := s(u) so that S† is a function from [N ] into [K]. Finally a specialist model is defined by giving a distribution w1 : S→ [0, 1] s.t. ∑ s∈S w1(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 [15, 18] into the following theorem.
Theorem 3. The expected regret of SPECIALISTEXP with initial specialist distribution w1 : S→ [0, 1] and learning rate η > 0 is bounded above by
E ∑ t∈[T ] `t,at − `t,S†(ut)  ≤ 1 η ∑ s∈S ln ( 1 w1(s)|S| ) + ηKT 2 (6)
for all well-formed specialist sets S ⊆ S.
In the following we give the two distributions that define the two specialist models corresponding to GABA-I and GABA-II in (7) and (9), and in the supplementary material we detail how these distributions lead to the regret bounds in Corollaries 4 and 5.
We now give the distribution w1(·) over S that defines the GABA-I model. The model has a single parameter φ ∈ (0, 1) and we give the following helper functions to define the distribution,
valid1(s) := J∀u, v ∈ [N ] : s(u) = s(v) or s(u) = or s(v) = K cut(s) := ∑ u∈[N−1] Js(u) 6= s(u+ 1)K
startfactor(s) := K − 1 K Js(1) 6= K + 1 K Js(1) = K.
The function valid1(·) determines the support of w1(·) which are the specialists that predict a unique action or abstain, hence the cardinality of the support of w1(·) is K × (2N − 1) + 1. The remaining two functions quantitatively determine probability mass of a specialist as:
w1(s) := valid1(s)× 1
K × startfactor(s)× (1− φ)N−1−cut(s)φcut(s) (∀s ∈ S) . (7)
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 w1(·) as defined by (7) with parameter φ = 4Ψ(y)/(K(N − 1)), learning rate η = √ 10Ψ(y) ln(KN/Ψ(y))
KT and with Ψ(y) ≤ (N − 1)/4 is bounded above by:
E ∑ t∈[T ] `t,at − `t,y(ut)  ∈ O(√K ln(KN Ψ(y) ) Ψ(y)T ) (8)
for any mapping of users to actions y : [N ]→ [K].
We now give the distribution w1(·) over S 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(2N − 1). The supported specialists in GABA-II predict a unique action over a contiguous l, . . . , r and abstain everywhere else, thus they are of the form:
sl,ra (u) := { a u ∈ {l, . . . , r} u 6∈ {l, . . . , r} ,
but not all contiguous segments are supported. The segments supported are those that correspond to the set of all leaf-descendents of a node in the BST (see Section 2.2). As an example if N = 4 the supported (l, r) segments are {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (3, 4), (1, 4)}. Expressing this algebraically leads to a relatively complex “validity” function
valid2(s) := J∃a ∈ [K]; l, r ∈ [N ]; i, j ∈ [log2N ] : 1+r−l = 2i and l = 2i(j−1)+1 and s = sl,ra K , and then the distribution is defined as,
w1(s) := valid2(s)× 1
K(2N − 1) (∀s ∈ S) . (9)
We note that this selection of specialists is a simple multi-action extension of those defined in [65]. Corollary 5. The expected regret of SPECIALISTEXP with distribution w1(·) as defined by (9) with learning rate η = √ 8Ψ(y) log2(eN/Ψ(y)) ln(3KN/2Ψ(y))
KT and with Ψ(y) ≤ N/2 is bounded above by:
E ∑ t∈[T ] `t,at − `t,y(ut)  ∈ O(√K ln( N Ψ(y) ) ln ( KN Ψ(y) ) Ψ(y)T ) (10)
for any mapping of users to actions y : [N ]→ [K].

heading: 4 The GABA Algorithms
text: We now introduce the GABA algorithms. Both algorithms are based on the BST C (see Section 2.2).

heading: 4.1 GABA-I
text: Since we have an exponential number of non-zero weight specialists in GABA-I a direct implementation 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 toO(K ln(N)) and the space down to O(KN). 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, 1} and hence takes a per-trial time of only O(ln(N)). We now detail this procedure:
GABA-I maintains a vector valued functionαt : C×{0, 1}×{0, 1} → RK which, for all i, j ∈ {0, 1} and t ∈ [T ] , has the following properties:
∀u ∈ [N ] \ {ut} , αt+1(u, i, j) = αt(u, i, j) (11)
and for all internal vertices n of C we have: αt(n, i, j) = ∑
k∈{0,1}
αt(/(n), i, k) αt(.(n), k, j) (12)
On trial t GABA-I computes pt by sending vector valued messages down the path in C from the root to ut. Specifically, we construct the left and right message functions β⇐t ,β ⇒ t : ⇑(ut)× {0, 1} → RK as follows. Each (non-root, proper) ancestor n of ut receives, for i ∈ {0, 1} , K dimensional vector messages β⇐t (↑(n), i) and β⇒t (↑(n), i) from its parent and then constructs its own messages β⇐t (n, i) from β ⇐ t (↑(n), j) and αt(/(↑(n)), j, i) and messages β⇒t (n, i) from β⇒t (↑(n), j) and αt(.(↑(n)), i, j), for all i, j ∈ {0, 1} . It then sends these messages to its child that is next on the path to ut. Once ut has received the messages from its parent it combines them with αt(ut, 1, i) (for i ∈ {0, 1}) to create pt. On the receipt of `t,at we update the function αt to αt+1 noting that by (11) and (12) we need only modify the values αt(n, i, j) when n is an ancestor of ut.

heading: 4.2 GABA-II
text: For GABA-II we have O(K ln(N)) non-zero weight specialists that don’t abstain on any given trial so a direct implementation of SPECIALISTEXP would take a per-trial time of O(K ln(N)). We now show how GABA-II implements SPECIALISTEXP, which takes the per-trial time down to O(ln(K) ln(N)) 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 ut is its descendant and abstains otherwise, is kept, by GABA-II in the following factored form:
µt(n)θt(n, a)
K(2N − 1) (13)
where µt+1(n) := µt(n) whenever n /∈ ⇑(ut) , and θt+1(n, a) := θt(n, a) whenever n /∈ ⇑(ut) or a 6= at. 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 θt(n, ·) is extended onto all internal vertices of B by the following inductive relationship:
θt(n,m) := θt(n, /(m)) + θt(n, .(m)) (14)
To sample the action at GABA-II first samples an ancestor δt of ut with probability P [δt = n] ∝ µt(n)θt(n, r) where r is the root of B. GABA-II then uses the function θt(δt, ·) to sample action at with probability P [at = a | δt = n] = θt(n, a)/θt(n, r) in O(ln(K)) time. The law of total probability and (13) can then be used to show that P [at = a] ∝ pt,a where pt,a is as defined in SPECIALISTEXP.
On the receipt of `t,at we update the functions µt and θt to µt+1 and θt+1 noting that by the equalities between these functions and (14) we need only modify the values µt(n) and θt(n,m) when n is an ancestor of ut and m is an ancestor of at.

heading: 4.3 Parameter Tuning
text: A limitation of the GABA-I regret bound is that it is dependent on knowing the optimal values of the parameters φ and η, and for GABA-II on the parameter η. In the following, we will 1) sketch how to autotune φ at little cost and 2) autotune η, however at essentially the cost of moving Ψ(y) outside of the square root.
We first sketch how to 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 φ is unknown we will “mix” over possible values of φ ∈ [0, 1]. In fact, at little cost in regret it is sufficient to just mix over the exponentially increasing values of φ = 2/N, 4/N, 8/N, . . . , N/N . Thus each specialist is split into log2N specialists, so that the new distribution over specialists is
w1(sφ) := 1 log2N × valid1(s)× 1 K × startfactor(s)× (1− φ)N−1−cut(s)φcut(s) ,
where ∑ s∈S,φ∈{2/N,4/N,...,1} w1(sφ) = 1. Implementing this efficiently is similar to the implementation of GABA-I, except that we now have log2N copies of the BST Cφ, each initialized with a different value of φ. On each trial the computed values from the log2N copies of the BST Cφ 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 O( √ log(log(N))) factor, to that of GABA-I with the optimal φ, but comes at the cost of an additional O(log(N)) factor in the computation time.
Now that we have shown how to automatically tune φ in GABA-I we are left with the learning rate η in both algorithms. We first note that, with any η, the regret of both algorithms is Υ/η + ηKT/2, where Υ is the robustified resistance weighted cutsize Ψ(y) multiplied by logarithmic terms (one in GABA-I and two in GABA-II). By setting η = √ 2/KT we get a regret of (Υ + 1) √ KT/2. In addition, if T is unknown then a doubling trick can be performed with this result to get a regret bound of O(Υ √ KT ) with no parameters needed. We compare this to the regret bound of O( √ ΥKT ) that comes from the optimal tuning of η. It remains an open problem to bring Υ inside the square-root.
Even with the above knowledge-free tuning of η, our methods improve over the baseline comparator of running an independent EXP3 algorithm for each of the N users in many natural scenarios. Recall that in this case the induced regret is then Õ( √ NKT ) (see (2)). Consider a very large social network where the bandit problem is to show 1-of-K advertisements (for simplicity assume K ∈ O(1)) at the nodes (users). Now consider the case that each user is served at most one advert, i.e., there is at most a single trial for any given user. Since N ≥ T the bound of the baseline is now the vacuous regret Θ(T ). We can intuitively see that this analysis is correct since the baseline algorithm is now just picking a single “uniformly at random” advertisement from [K] for each user independently. However, observe that when Ψ(y) ∈ õ( √ T ) we get Õ(Ψ(y) √ T ) ⊆ õ(T ), which is non-vacuous. Intuitively, GABA-I/II may achieve this result since algorithmically they are exploiting the network structure.

heading: 5 Conclusion
text: We considered a contextual, non-stochastic bandit problem in which the finite set of contexts (a.k.a users) form a 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 a 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 an 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 W911NF-16-3-0001. Stephen Pasteris and Massimiliano Pontil were supported in part by EPSRC Grant N. EP/P009069/1 and SAP SE.

Review summaries:
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.  The 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.

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).

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.  The 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).   The 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.  Finally, 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).   

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.  In 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".  This 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)$.