An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits
Authors: Geovani Rizk
Igor Colin
Albert Thomas
Rida Laraki
Yann Chevaleyre
Venue: NeurIPS 2022 Accept (2022)

Abstract: We propose the first regret-based approach to the \emph{Graphical Bilinear Bandits} problem, where $n$ agents in a graph play a stochastic bilinear bandit game with each of their neighbors. This setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. In this paper, we fill this gap and present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of $\tilde{O}(\sqrt{T})$ on the $\alpha$-regret and evidences the impact of the graph structure on the rate of convergence. Finally, we show through various experiments the validity of our approach.

An a-No-Regret Algorithm For Graphical Bilinear Bandits
Geovani Rizk
Igor Colin Huawei Noah's Ark Lab,
PSL Université Paris Dauphine, CNRS, LAMSADE, Paris, France geovani cwwnn.rizkkeee www.kkdauphiie.ppa..... peciiinneesls..... psl.eu
Paris, France
i gorr .olr.colloo www.unweiiw......mmm com
Albert Thomas
Rida Laraki
Huawei Noah's s Ark Lab, Paris, France
PSL - Université Paris Dauphine,
CNRS, LAMSADE, Paris, France
albert. eh com
rida.
dauphine ff
Yann Chevaleyre
PSL Université Paris Dauphine,
CNRS, LAMSADE, Paris, France
yann www.alerreeeeeeee..... amsade dauphine.fr
Abstract
We propose the first regret-based approach to the Graphical Bilinear Bandits problem, where agents in a graph play stochastic bilinear bandit game with each of their neighbors. This setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. In this paper, we fill this gap and present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of Ö(vT) on the a-regret and evidences the impact of the graph structure on the rate convergence. Finally, we show through various experiments the validity our approach.
Introduction
In this paper, we are interested in solving centralized multi-agent problems that involve interactions between agents. For instance, consider the problem of the configuration of antennas in a wireless cellular network (Siomina et al. 2006 or the adjustment of turbine blades in wind farm van Dijk
et al. 2016 Bargiacchi et al., 2018]. Choosing parameter for an antenna (respectively adjusting turbine blade) has an impact on its signal quality (respectively its energy collection efficiency) but also on the one of its neighboring antennas due to signal interference (respectively its neighboring turbine blade due to wind turbulence). By considering each antenna turbine blade these problems can be modeled as a multi-agent multi-armed bandit problem (Brgiiachi et al. 2018 with the knowledge of coordination graph [Guestrin et al. 2002 where each node represents an agent and each edge represents an interaction between two agents. As natural extension of the well-studied linear bandit to this multi-agen setting focus the graphical bilinear bandit setting introduced in Rizk et al. [202T]: at each round, a central entity chooses an action for each agent and observes bilinear reward for each couple of neighbors in the graph that is function of the actions chosen by the two neighboring agents.
agent,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The objective of the leamer can either be to maximize the cumulative reward, which requires trade-off between exploration and exploitation, or identify the best action without being concerned about suboptimal rewards obtained during the learning process, known as the pure exploration setting [Bubeck et al., 2009; Audibert and Bubeck 2010]. For graphical bilinear bandits, while the latter has already been addressed in Rizk et al. 202TJ, maximizing the cumulative reward (and thus minimizing the associated regret) remains an open question that we address in this paper.
Contribution. Given the NP-Hardness property of the problem and the impossibility of designing an algorithm that has sublinear regret with respect to the horizon T', we propose the first regret-based algorithm for the graphical bilinear bandit problem that gives guarantee on the orregret of Ö(VT) where (greater than 1/2) is a problem- dependent parameter and O hides the logarithmic factors. The problem as well as the notion of o-regret are introduced in Section 2 We provide a first algorithm identify the problem-dependen
and establish theoretical guarantees in Section In Section 4 parameters that one could use to improve both theoretical guarantees and empirical performances of the algorithm. Accordingly, we state a refined bound that significantly improves a. Finally, Section S gives an experimental overview of the various theoretical bounds established for the regret.
Related work. Centralized multi-agent bandit problems where the learner has to choose the actions of all the agents each round implies deal with parallelizing the learning process on the agents. In the context of linear rewards where all the agents share the same reward function, Chan et al. [202T] give detailed analysis of the problem and show that sublinear regret in T' can be reached but with an additional cost specific to the parallelization. The main difference with their work is that they consider independent agents, whereas we assume interactions between the agents.
Choosing an action for each node of a graph to then observe a global reward over the graph is a combinatorial bandit problem
-isnchi and Lugosi 2012). the number of joint arms scaling exponentially with the number of nodes. This has been studied in the regret-based context [Chen et al. 2013, Perrault al. 2020 where the notion of o-regret is introduced cope with the NP-Hardness of the problem. Most papers assume the availability of an oracle to solve the inner combinatorial optimization problem each round. In this paper, do not make this assumption and present an algorithm that takes into account the graph structure, which has not been considered in the combinatorial framework.
Bandit problems in graphs have been studied from several angles. For instance, on the one hand, in Valko al. 2014), Mannor and Shamir 2011] , each node of the graph is arm of the bandit problem, which, if pulled, gives information on its neighboring arms. On the other hand, in (Cea-BBianch et al. 2013 each node is an instance of a linear bandit and the neighboring nodes are assumed to have similar unknown regression coefficients. In this setting, the reward observed for each agent only depends on its chosen action which does not take into consideration agent interactions.
The graphical bilinear bandit setting has been first established in Rizk et al. 2021 where they tackle the problem of identifying the 1/2-best joint arm (which has associated global reward equal to at least 1/2 of the optimal one). They study the pure exploration setting while we tackle the regret- based one. To the best of our knowledge, our paper is the first one to provide regret-based algorithms for the graphical bilincar bandits setting.
2 Problem setting
Let G (V. E) be the directed graph defined by V the finite set of nodes representing the agents and
E the set of edges representing the agent interactions. We assume that if (i.j) E E then (j. E E T
The Graphical Bilinear Bandit with a graph & consists in the following sequential problem RRizk
et al. 2021 at each round f, each agent i E chooses an arm (0) in finite arm set X' and receives for each of its neighbors j bilinear reward
y (1))
(i.) (i) M. + m
'One could define an undirected graph instead. However, we consider that interactions between two neighbors are not necessarily symmetrical, with respect to the obtained rewards, so we choose to keep the directed graph to emphasize this asymmetry.

---

where M, E Rdxd is an unknown matrix, and v/2 (1.)) zero-mean r-sub-Gaussian random variable
For all agent i E V, we denote Ng the set of its neighboring agents. Let n Card (V) denote the number of nodes, m = Card (E) the number of edges and K = Card (2¹) the number of arms. We assume that for all E X, ||a|| Σ L. Let ||,, be the Frobenius norm of M, with [M, IS S. We assume that the expected reward of each edge is positive which gives for all (x, E X², 0 < x M, < LS.
For each round t, we define the global reward Y/ Easeerth (65) (65) the sum of the local rewards obtained over the graph at round t, and (2 arg max (.......())))) E(.ee global reward. The corresponding global pseudo-regret over T rounds then defined as follows:
( M.x as the optimal joint arm that maximizes the expected
R(T)-
J.
( M.
(3)
Σ
2i
(() M.
(
t=1
(iJE
(A,)EE
We know from Rizk al. [202 that finding (2f4)
is NP-Hard with respect the number (n)
of agents n. Propusition 2.1
Rizk et al. 2021 Theorem 4.1). Consider a given matrix M. E Rdxd and a finite set X Rdd Unless N=NP, there is polynomial time algorithm guaranteed find the optimal solution of
Σ x00TM. x(
max ((().....(n))
JEX" (1,))E
Hence, the objective of designing an algorithm with a sublinear regret in T not feasible in polynomial time with respect to However, some NP-hard problems are a-approximable (for some a E (0, 1J, which means that there exists a polynomial-time algorithm guaranteed to produce solutions whose values are at least times the value of the optimal solution. For these problems, makes sense to consider the a-pseudo-regret as in Chen et al. 2013 which defined for all
(0, 1] follows
T Ra (T) A
Σ
ax,
M. M.
Σ
xt M.
t=1
(()))
(KJ)E
and set the objective of designing an algorithm with a sublinear a-regret. The linear form. The reward can either be viewed as a bilinear reward as shown in or as a linear
reward higher dimension (Jun al. 2019] with (f.1) /vec (2 24 (T)) vec (M.) m (i.)
(0)
where for any matrix A TRaxd, vec (A) denotes the vector in ddd which is the concatenation of all the columns of A, and (.:)) refers the dot product between two vectors.
To simplify the notation, let us refer to any æ E X' as a node-arm and define the arm set Z {vec (axx" (z x²) X²} where any Z will be referred
edge-arm. If the arm x X represents the node-arm allocated to the node i E at time f, for each edge (i,j) E E we will denote the associated edge-arm by 2 (6-5) == vec (1 xx (1)))) 2 and define 0, = vee (M,) the vectorized
'One may wish that the agent's reward also takes into account the quality of its chosen arm alone (i.e., compared to the one chosen by its neighbors). We discuss this case in the appendix and show that we add a linear term as function of x to the bilinear reward, the new reward can still be reduced to simple bilinear reward with unknown matrix M. (dd+1)

---

version of the unknown matrix M. with ||0, 12 S. With those notations, the (now) linear reward can be rewritten as follows:
vi (1.0 -0:00 (2)
(6.)) 0.) + ni
(h.)
(2)
When needed, for any node-arms (x,x²) E X² we use the abbreviation Zzz' veo( Finally for any vector IRd and symmetric positive-definit matrix A E Rdddd, we define || vx Av.
3 Optimism in the face of uncertainty for Graphical Bilinear Bandit
Let us first notice that given the linear reward 2 that can be observed for each of the m edges (i,j) E E, the central entity is trying solve parallel and dependent linear bandit problems. The parallel aspect comes from the fact that at each round t the learner has to allocate all the m edge-arms of the graph (one for each edge (i.j) in E) before receiving the corresponding linear rewards. The dependent aspect comes from the fact that the choice of most of the edge-arms are depending on
other edge-arms. Indeed, two adjacency edges (i and (j, k.) share the node j, hence their allocated
edge-arms must share the node-arm xx("
In this paper, we choose to design an algorithm based on the principle of optimism in the face of uncertainty Auer et al. [002], and in the case of a linear reward [L et al. (2000) Abbasi- Yadkori
et al. 2011 we need to maintain an estimator of the true parameter 0,. To do so, let us define for all rounds E {I,..., . the OLS estimator of 0, as follows:
0, AT br
where,
A AL
((.)) 28
(i.))EE
with A 0 regularization parameter and
b
#
2(.51 (5-5)
8=1 (KJ)E
We define also the confidence set
C, - f0: 0: 110 0,1 00:10-0:14,;15 ////
1 (1+ [1+mL///A + vās]
dolog log
where with probability 5, 5, we have that 0, E Cr) for all / (1,..., and 8 E (0, 1]. Since the graphical bilinear bandit can be seen as linear bandit dimension d² and with K possible arms the idea of method is to overcome the NP- Ha-Hard optimization problem that one would have to solve at each round when directly applying the OFUL algorithm as defined in Abbasi- Yadkori et al. 2011 Indeed, at each round, instead of looking for the best optimistic joint arm
(x) (1)
(1))
max (at11 EE) (EC+-1(8)
arg max
Σ
22(0
(LJ)EE
'It can be seen as a linear bandit problem because the goal the central entity is to maximize at each round t the expected global reward E 21 (T)
M.x(5) = E(ttree 21 (15)T 8, = (Eessre
(6,)) 2(.)) 0,

---

Algorithm 1: Adaptation of OFUL algorithm for Graphical Bilinear Bandit
Input :graph (V. F), node-arm set X
(V,, V2) = Approx-MAX-CIO for
do
// Find the optimistic best couple of node-arms
Ft, T/z 0--1) = arg max(x,x" (ls,,,,0))xe ())x=xxC--1 (Zeal + Zxtar 0);
I1 Allocate 2tz and of in the graph
dt 2i for all in Vi; ( = x for all i in V/2;
Obtain for all (1,j) in E the rewards y/ (6.).
Compute 0, as in
end
return 8,
Algorithm 2: ApproX-MAX-CUT
Input :9 (V, E)
Set V1 = 0. V/2
for i in V do
n1 = Card ({(i,)) E E jeejje v));:
n2 n > n2 then 1/2 - (1) else Vi + [1
Card (((i.) E j V2)):
end
return (V1, V2)
max(x we consider the couple of node-arms (I+, xx,) = arg max (2,x") exx (Zar + 22'2, 0.) maximizing the
reward along one edge Given the optimal joint arm (x ,...,,"! 5. (n) and the associated optimal edge-arms (4.f) vec (ar (6) (0) for all (i,j) E F,, we have
(2.
(1)) + (1.5) 0.) S (Za.a) + Rxt 0.)
(4)
Hence, an alternative objective is to construct as many edge-arms ب and Rata, as possible in the graph. Naturally, we do not have access 0., so use the principle of optimism in the face of uncertainty, which is to find the couple (Iz; 2/) such that
(Ie, x4) arg max max (Zew' + 2x' (x." 6EC.-1(6)
and then allocate the node-arms to maximize the number of locally-optimal edge-arms 2nzz and Zzja, The motivation of this alternative goal can be understood thanks to (4) where we know that the associated expected reward is better than the obtained with the edge-arms created with the optimal joint arms. Of course, one can also easily understand that for general type of graph it is not possible to allocate those edge-arms everywhere (ie., to all the edges). For example take complete graph of three nodes, allocating the edge-arms 2z,2/ and 2 is equivalent to allocate 2; and af to the nodes. By doing so, two nodes will pull 2, and the third one will pull z/ which makes inevitable to allocate sub-optimal and unwanted edge-arms of the form Zaraat-
The main concern with this method round (relative to the total number m of edges) in order to minimize their impact the resulting regret. Assigning De to a subset of nodes and z to the complementary is equivalent to cutting the graph into two pieces and creating two distinct sets of nodes V1 and V/ such that V V1 U 1/2 and Vi 1/2 = 0. Pulling the maximum amount of optimal edge-arms thus boils down to finding a cut passing through the maximum number of edges.
control how many unwanted edge-arms are drawn in each
'The reward of an edge here denotes the sum of the rewards of the two corresponding directed edges in E.
5

---

This problem is known as the Max-Cu problem, which is also NP-Hard. However, the extensive attention this problem has received allows us to use one of the many approximation algorithms (see, e.g., Algorithm 2 which are guaranteed to yield cut passing through at least a given fraction of the edges in the graph
Proposition 3.1. Given a graph 9 (V, Algorithm 2
returns couple (V1, V2) such that
Card (1(i,)) E E ( (a) vi))
Using Algorithm we can thus divide the set of nodes V into two subsets V1 and 1/2 with the guarantee that at least m/2 edges connect the two subsets. Combining this algorithm with the principle of optimism in the face of uncertainty for linear bandits Abbasi- Yadkori et al. [011] obtain Algorithm| D for which we can state the following guarantees on the a-regret.
Theorem 3.2. Given the Graphical Bilinear Bandit problem defined in Section ler S y S bea
problem-dependen parameter defined by
(z 0.)
7 min ZEX 1 EGSEE (15) (,.,)),,,
20,
,0,)
1+7, then the a-regret of Algorithm satisfies and set 2
(T) S S =0((od ((ox++5VX) / T' (2, (LS)3) + LSm d loga Tmm12 //1/////))))/
where Ô hides the logarithmic factors.
One can notice that the first term of the regret-bound matches the one of a standard linear bandit that pulls sequentially T'm edge-arms. The second term captures the cost of parallelizing m draws of edge-arms per round. Indeed, the intuition behind this term is that the couple (xz, 2x) chosen at round (and thus after having already pulled tm adge-arms and received tm rewards) is relevant to pull the (Im 1) edge-arm but not necessarily the (m - 1) edge-arms that follows (from the (Im + 2)-th to the (tm + m))th one) since the reward associated to the (Im + 1)-th edge-arms could have led change the central entity choice if it had been done sequentially. In Chan et al. (202T), they characterize this phenomenon and show that this potential change in choice occurs less and less often as we pull arms and get rewards, hence the dependence in (llog(Tmm))).
What is y and what value can we expect? This parameter measures what minimum gain with respect to the optimal reward one could get by constructing the edge-arms of the form εez- For example, there exists Zo E X' such that (Zzpzy 0.) 0, then & = 0 as well and we are in the worst case c-regret with 1/2. In practice, having y 0
scenario where can only have guarantee is reached when given the couple 24) = arg max (x.="))) (Zzx' + Za'a, 0x), this æn is either t. or x²_ In other words, if the unwanted edge-arms associated to the couple (æ,, x'.) gives low rewards, then the guarantee on the regret will be badly impacted. Hence we can wonder how can prevent this phenomenon. We answer this question in the next section by taking into account both the proportion of undesirable edge arms allocated and their potential rewards the selection of the pair x/) in order to improve in practice but also theoretically the performance of the algorithm.
4 Improved Algorithm for Graphical Bilinear Bandits
In this section, we want to capitalize on Algorithm 1 and its - 1+% -no-rerrttt property to optimize the allocation of the arms I, and a/ such that the unwanted and suboptimal arms Zr,z, and Zntat penalize as less as possible the reward.
Most of the guarantees for the approximation of the Max- Cut problem are stated with respect to the optimal Max- Cut solution, which is not exactly the guarantee we are looking for: we need a guarantee as a proportion of the total number of edges. We thus have to be careful the algorithm choose.

---

Indeed, in Algorithm D the choice of the couple (zt, 2.) is driven by the optimistic reward of the edge-arms Sayat and ب but on the one of the unwanted arms Sazara and 2xja4 Here, the first improvement that we can provide is to include them the selection of the couple (2t, a() as follows
(1),
arg maxx (Zaz' Zaax + Raz + Rafa', 0) (2,2")EX² REC, 1(6)
However, this selection suggests that the number of unwanted edge-arms Ræ,æ, and žtद will be equal to the number of optimal edge-arm بх,ي, and Prfas (in the sense of optimism), which is in general not true | Hence, one has to take into consideration the proportion edges that will be allocated by suboptimal and unwanted edge-arms by optimistically optimal edge-arms.
To do so, let us define mi (respectively m2) the number of edges that goes from nodes in Vi (respectively V2) to nodes in V12 as well (respectively V/2) and m1-- (respectively m2-+1) the number of edges that goes from nodes in V/1 (respectively V22 to nodes V2 (respectively Vi). One can notice that by definition of the edge set E, we have m1-22 m22-1 and that the total number of edges m 1 + m22-1 + mi + m2. By choosing the couple (Iz, x() as follows
(It, x1)
(m1-+2 Zzw! + M2-+1 Ze' my Zex + m2 Zata' 0) (m,=))xx² (EC.-1(6)
arg
we are optimizing the total optimistic reward that one would obtain when allocating only two arms (x., x in the graph. This strategy is described Algorithm
Algorithm 3: Improved OFUL for Graphical Bilinear Bandits
Input :graph 9 = (V. F), node-arm set X'
(Vi, V22 Approx-MAX-CUT(S)
m1-22 = m2_11 = Card (((i,)) E EVEE V2]);
m, Card (1 E Eli e Vi V AjE])) m2 Ca E Va));;
for - 10 do
Iz,, (2, 1...(,00-)==
arg (x,=' ,,,xx (m1-2 Zxx' m2-+1 Re'a + m2 Azx + m2 Z''''' ,);
x, 24 for all in Vi: at x for all in Vz; Obtain for all (i.j) in E the rewards vt (6.))
Compute O2 as in B
end return 0,
Before stating the guarantees on the a-regret of this improved algorithm, let us recall that we defined x!,) arg max (Zaz' + Z 0.) and let us define the couple (ā., Ø(,) such that
(T+, ...)) arg max (maxxm11222 Zzan + 12--11 Zy'n + my + m2 Zata', Oz) (x,2")eX
We define A > 0 to be the expected reward difference of allocating (œ., (.,, instead of (æx, 2.),
(m1142 (Eg, zz,ws) + M22+1 (Zzça, - Zz. + mi (Za,a, ae, ) + m2 (zzçaς Zzfat) O.)
The new guarantees that we get on the a-regret of Algorithm Y are stated in the following theorem.
'It is for instance true in complete graphs with an even number of nodes n but it is already false when the number of nodes become odd.
7

---

Table 1: Value of several parameters with respect the type of graph. Experiments performed on graphs of n 100 nodes, and results for the random graph are averaged over 100 draws.
Graph types
Complete
Random
Circle
Star
Matching
ml-m2
0.495
0.453
0.01
0
0.5 + 0.5ry
0.505 + 0.495% +
0.547 + 0.453y +
0.99 0.011 +
1
Theorem 4.1. Given the Graphical Bilinear Bandit problem defined as in Section 2 let y be defined as in Theorem 3.2 let 0 S S 2/ be a problem dependent parameter that measures the gain of optimizing on the suboptimal and unwanted arms defined as:
A
Euseen (6.) 0.)
and set 1 ml+m2 (1 7) c) where 2 1/2 by construction, then the a-regret of Algorithm 3 saatisfies
(T) zō (lod+ +SVP+ VI' (2, (LS)²) + LSm d logg
Tm
)
8
where Ô hides the logarithmic factors.
Here one can see that the improvement happens in the of the a-regret. Let analyze more precisely this term. First of all, notice that in a complete graph (which is the worst case scenario terms of graph type and guarantees of the cut), we get a 2 1+7 + which shows that optimizing over the suboptimal arms already improves our bound by Ön the contrary, in the most favorable graphs, which are bipartite graphs (i.e., graphs where all the m edges goes from nodes in V1 to nodes in V/2 or vice versa), we have m2 + m 0 and 0 which gives no-regret algorithm. What may also be of interest is to understand how a varies with respect to 7, and the quantity mi and my for graphs that are between complete graph and bipartite graph. We investigate experimentally this dependency in Section 5
2
1 and makes the Algorithm B
Experiments Influence of the problem parameters on the regret
In this section, give some insights on the problem-dependeet parameters y and and the corre- sponding a. Let and ag be the stated respectively in Theorem 3.2 and Theorem 4.1 In the first experiment, we show the dependence of αд and a2 on the graph type and the chosen approximation algorithm for the max-cut problem with respect to and We also highlight the differences between the two parameters On and a2 and the significant improvement in guarantees that one can obtain using Algorithm depending on the type of the graph. The results are presented in Table
One can notice that the complete graph seems be the one that gives the worst guarantee on the a-regret with respect to and Thus, we conducted a second experiment where we consider the worst case scenario in terms of the graph type -e,g., the complete graph- and where there is π 10 agents. The second experiment studies the variation of and y with respect to the unknown parameter matrix M.. To design such experiments, we consider the arm-set X' as the vectors (e1...., of canonical base in IRd, which implies by construction that the arm-set Z contains the vectors (e....., c,2)) of the canonical base d We generate the matrix M, randomly in the following way: first, all elements of the matrix are drawn i.i.d. from a standard normal distribution, and then we take the absolute value of each these elements ensure that the matrix only contains positive numbers. The choice of the vectors of the canonical base as the arm-set allows us to modify the simple way the dependence on y and 6. Consider the best couple (i*, (i*,j") arg (aXe (1.....d) (Zeze, Zeze, 0.), we want to how the reward of the suboptimal
matrix M, and to illustrate
8

---

0.9
0.5
0.7
0.4
0.3
0.2
0.1
0.5
0.0
0.0
0.2
0.6
1.0 2500
3000
7500
12000
11500
15000
37500
20005
Figure 1: Variation of c, 7, O11 and 02 with spect to the parameter Ç. The closer Ç is to the lower the reward of the unwanted arms Ze. and eg. the closer Ç is to the higher the reward of the unwanted arms. The dimension d of the arm-set is 10 (which gives linear reward with unknown parameter 0, of dimension 100). The plotted curve represents the average value of the parameters over 100 different matrices M. initiated randomly with positive values.
Figure 2: Fraction of the global reward obtained each round by applying the Algorithm Algo- rithm and the Explore- Seeene--TTh--coomiii a algorithm (here named GBB-BAI) using the exploration strategy in Rizk et al. 202T] We use complete graph of 5 nodes, we run the experiment on different matrices as in Figure [ with Ç = 0 and run it 10 different times plot the average frac- tion of the global reward
edge-arms Res and Reg impact the value of y, and thus Notice that the reward associated to the edge-arm Seg (respectively ze).e,-) is M. (respectively M.j Hence we define 1 (M. + M.j+.)) We study the variation of
0 < 1 and set M.r. = Maar.j" 04 and a2 with respect to Ç. The results are presented in Figure One can see that when the associated rewards of ee and = [
low (thus is low and high), Algorithm 3 givees |sinee will focus on other node-arms than eş- and e,- that
much better guarantees than Algorithm will give higher global reward. Moreover, even when the unwanted edge-an gives high reward, the guarantees on the regret Algorithm are still stronger because it takes into consideration the quantities m, and m2 of the constructed suboptimal edge-arms.
experiment that compares in practice the performance of Algorithm and Algorithm 3 with the Explore-Ther Then-Commit algorithm by using the exploration strategy designed in
Finally, we design
Rizk et al. [202T] during the exploration phase, and by allocating the nodes V1 and V/2 with the best estimated couple (x, x') = arg max (x,2")
(x.x"),2)) (Zzz' + Zz'x; 02) during the commit phase.
Conclusion & discussions
In this paper, we presented the first regret-based algorithm for the stochastic graphical bilinear bandit problem with guarantees the a-regret. We showed that by exploiting the graph structure and the typology of the problem, one can both improve the performance practice and have a better theoretical guarantee on its a-regret. Also, we showed experimentally that our algorithm achieves a better performance than Explore-Then-Expe Then-Exploit on our synthetic datasets. The method presented in this article can be extended many ways. First, one can consider cutting the graph into 3 or more pieces, which is equivalent to approximating the problem of a Max-k Cur [Frieze and Jerrum 1997 with t: 2 3. With the knowledge of such a partition of nodes Vi..... Ve. one may want to look for k-tuple of node-arms maximizing the optimistic allocated reward rather than pair, therefore introducing an elegant tradeoff between the optimality of the solution and the computational complexity of the arms allocation. One could also study this problem in the adversarial setting, in particular adapting adversarial linear bandit algorithms our case. Finally, our setting could be extended to the case where each agent has its own reward matrix.

---

References
Y. Abbasi- Yadkor,, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
J.-Y. Audibert and S. Bubeck. Best arm identification in multi-armed bandits. In Proceedings the 23th Anmual Conference on Learning Theory, pages 41-53, 2010.
P. Auer, N. Cesa-Biances and P. Fischer. Finite- thite-timeeto analysis of the multiarmed bandit problem. Machine learning. 47(2-3):235-2555 2002.
E. Bargiacchi, Verstraeten, D. Roijers, A. Nowé, and H. Hasselt. Learning coordinate with coordination graphs in repeated single-stage multi-agent decision problems. In International conference on machine learning, pages 482-490, 2018.
Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In Interna- fional conference Algorithmic learning theory, pages 23 37. Springer, 2009.
N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5):1404 1422, 2012.
N. Cesa-Bianchi, C. Gentile, and G. Zappella. A gang of bandits. In Advances in Neural Information Processing Systems, pages 737-745, 2013.
Chan, A. Pacchiano, N. Tripuraneni, Y. Song, P. Bartlett, and M. I. Jordan. Parallelizing contextual linear bandits. arXiv preprint 200. 2021.
W. Chen, Y. Wang, and Y. Yuan. Combinatorial multi-armed bandit: General framework and applications. In International Conference on Machine Learning, pages 151-159, 2013.
A. Frieze and M. Jerrum. Improved approximation algorithms for max k-cut and max bisection. Algorithmica, 18(1):67-81, 1997.
C. Guestrin, M. G. Lagoudakis, and Parr. Coordinated reinforcement learning. In Proceedings of the Nineteenth International Conference on Machine Learning, page 227-234, 2002.
K.-S. Jun, R. Willett, S. Wright, and R. Nowak. Bilinear bandits with low-rank structure. In International Conference on Machine Learning, pages 3163-3172, 2019.
T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2018.
L. Li, W. Chu, J. Langford, and R. E. Schapire. contextual-handi approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
S. Mannor and O. Shamir. From bandits to experts: On the value of side-observations. In Advances in Neural Information Processing Systems, pages 684-692, 2011.
Perrault, E. Boursier, M. Valko, and V. Perchet. Statistical efficiency of thompson sampling for combinatorial semi-bandits. In Advances in Neurul Information Processing Systems, 2020.
G. Rizk, A. Thomas, I. Colin, R. Laraki, and Y. Chevaleyre. Best arm identification in graphical bilinear bandits. International Conference on Machine Learning, pages 9010-9019, PMLR, 2021.
I. Siomina, P. Varbrand, and D. Yuan. Automated optimization of service coverage and base station antenna configuration in UMTS networks. IEEE Wireless Communications, 13(6):16-25, 2006.
M. Valko, R. Munos, B. Kveton, and T. Kocák. Spectral bandits for smooth graph functions. In E. Xing and T. Jebara, editors, International conference on machine learning. volume 32 of Proceedings of Machine Learning Research, pages 46-54, 2014.
M. T. van Dijk, J.-W. van Wingerden, T. Ashuri, Y. Li, and M. A. Rotea. Yaw-nisalignment and its impact on wind turbine loads and wind farm power output. In Journal of Physics: Conference Series, volume 753, page 062013. IOP Publishing, 2016.
10

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proof's of all theoretical results? [Yes] In the appendix section
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No] The code will
be released if the paper is accepted to the conference
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] All the details explained again in the supplementary material
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] Also in the appendix
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [No]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [No]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [No]
(c) Did you include the estimated hourly wage paid to participants and the total amount
spent participant compensation?
[No]


Reviews:
[{"review_id": "yhLonUHBrx7", "reviewer": "Reviewer_DZQi", "summary": "The paper claims to analyze the first regret-based approach to the Graphical Bilinear Bandits problem, where n agents in a graph play a stochastic bilinear bandit game with each of their neighbors. They showed that the setting reveals a combinatorial NP-hard problem that prevents the use of any existing regret-based algorithm in the (bi-)linear bandit literature. The authors present the first regret-based algorithm for graphical bilinear bandits using the principle of optimism in the face of uncertainty. Theoretical analysis of this new method yields an upper bound of the α-regret which characterizes the dependence of the graph structure on the rate of convergence. Experiments are provided in support of their claim.\n", "questions": "The O(d^2) dependency on regret is believed to be not tight in general. Can the authors comment on the tightness of the upper bound guarantee (for Thm 3.2 and 4.1)?\nIn the algorithmic ideas or regret analysis, is there a new idea that is specific to this setting distinct from what has been already explored for the linear bandit scenario?", "limitations": "See points for Weaknesses listed above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n- The alpha regret formulation and setting of bilinear bandit is well motivated since the original problem is NP-hard (Rizk et al,21).\n- Theoretical regret guarantees\n- Experimental evaluation\n\nWeakness: \n- Motivating applications are missing that fit the linearity framework\n- Technical novelty: The proposed algorithmic idea posed the bilinear problem as a linear problem in d^2 dimensions to the best of my understanding. The remaining challenge is to lift the techniques from the d-dimension linear bandit problem and apply it to the current setting. \n- Optimality guarantees are not tight?\n- No comparisons with state-of-the-art bilinear optimization routines, e.g. As pointed out, we can pose the problem as a linear bandit problem in O(d^2) dimension, so in that case, I am curious to understand how the regret and runtime performance of the proposed methods compare against existing linear bandit algorithms, Thompson sampling or OFUL? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mc-HWFA75h", "reviewer": "Reviewer_7vV1", "summary": "The paper describes an algorithm for achieving sublinear `\\alpha-'regret for the problem of graphical bilinear bandits introduced by Rizk etal '21. The algorithm is based in the well-known optimism under uncertainty principle. Further they do some modification on some of the problem-dependent parameters to achieve better regret guarantees. They show some numerical results to support their claims. ", "questions": "1) Regarding the analysis novelty: please see the comment above on technical novelty.\n\n2) Since I am not very well versed on this topic, are their attempts to show any lower bounds for this problem setting? If not, is there a fundamental difficulty in showing such bounds?", "limitations": "I agree that the authors are transparent that the paper draws connections with existing works by Rizk etal and Abbasi yadkori etal 2011. However given these already existing works, the contributions made in this paper are not very surprising to me.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper attempts to tackle the regret minimizing aspect of the graphical bilinear bandit problem, which is a positive contribution.\n+ The paper is clearly written, defining the quantities of interest and citing appropriate literature works.\n+ Experiments show their claims of changing the parameter values which support their claims\n\n- The problem setting introduced is not novel, however this is not a major concern for me.\n- The algorithms introduced are somewhat the first choice that one would follow for solving a regret minimization metric for this setting. It would be great if the authors make a small section on the technical challenges faced (and how they overcome them) while adapting the OFUL algorithm to their setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "V6Ix5CSvj1_", "reviewer": "Reviewer_shTc", "summary": "This paper addresses the problem of bilinear bandits with graphical structure. In this problem, the agent must attribute at each round $t\\leq T$ an action $x_t^{(i)}$ for each node $i$ of a graph. Then, he receives an expected reward $\\sum_{(i,j) \\in E} x_t^{(i)} M_* x_t^{(j)}$, where $M_*$ is an unknown matrix, and E is the set of edges of the graph. \n\nEven in the case where $M^*$ is known, the problem of finding the best action is known to be NP-hard. For this reason, the authors focus on the problem of minimizing the $\\alpha$-regret for some $\\alpha \\in [1/2,1]$, i.e. the difference between $\\alpha$ times the cumulative reward of the oracle agent, and their reward. They present two algorithms for this problem, and establish bounds on their $\\alpha$-regret. They also study its empirical properties on simulated datasets.", "questions": "Can the author please either include a proof of Proposition 3.1 (regarding the efficiency of Max-Cut approximation), or provide a reference proving it?\n\nCould you provide a reference more explicit for lower-bounding the probability of the critical covariance inequality? For the sake of completeness, it would be interesting to include a (sketch of) proof of this result.\n\nI believe there might be a typo in the definition of $\\epsilon$ in Theorem 4.1. It should be defined as $\\frac{\\Delta}{\\sum \\langle z_*^{(i,j)} \\vert \\theta_*\\rangle}$, instead of $\\frac{\\Delta}{\\sum z_*^{(i,j)}}$.", "limitations": "The authors discuss possible extensions of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality : This problem addresses a well motivated problem of bilinear bandits with a graph structure. While this problem is related to that of bilinear bandit, the parallelization changes the nature of the problem. This problem has already been studied with the objective of finding the best action, as well as in the linear setting, and some proof technics are common to these results.\n\nClarity : This paper is very well written, pedagogical, and the arguments are well explained.\n\nSignificance : This paper addresses a well-motivated problem that had not been studied previously.\n\nQuality :  This paper is very well written, and addresses a problem not solved before. The numerical experiments are convincing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept