# An $\alpha$-No-Regret Algorithm For Graphical Bilinear Bandits

Geovani Rizk
PSL - Université Paris Dauphine,
CNRS, LAMSADE, Paris, France
<EMAIL_ADDRESS>
&Igor Colin
Huawei Noah’s Ark Lab,
Paris, France
<EMAIL_ADDRESS>
&Albert Thomas
Huawei Noah’s Ark Lab,
Paris, France
<EMAIL_ADDRESS>
&Rida Laraki
PSL - Université Paris Dauphine,
CNRS, LAMSADE, Paris, France
<EMAIL_ADDRESS>
&Yann Chevaleyre
PSL - Université Paris Dauphine,
CNRS, LAMSADE, Paris, France
<EMAIL_ADDRESS>

###### Abstract

We propose 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. 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.

##  1 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 a wind farm (van Dijk et
al., 2016; Bargiacchi et al., 2018). Choosing a parameter for an antenna
(respectively adjusting a 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 or turbine
blade as an agent, these problems can be modeled as a multi-agent multi-armed
bandit problem (Bargiacchi et al., 2018) with the knowledge of a coordination
graph (Guestrin et al., 2002) where each node represents an agent and each
edge represents an interaction between two agents. As a natural extension of
the well-studied linear bandit to this multi-agent setting we focus on the
_graphical bilinear bandit_ setting introduced in Rizk et al. (2021): at each
round, a central entity chooses an action for each agent and observes a
bilinear reward for each couple of neighbors in the graph that is function of
the actions chosen by the two neighboring agents.

The objective of the learner can either be to maximize the cumulative reward,
which requires a trade-off between _exploration_ and _exploitation_ , or to
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. (2021),
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 a guarantee on the $\alpha$-regret of
$\tilde{O}(\sqrt{T})$ where $\alpha$ (greater than $1/2$) is a problem-
dependent parameter and $\tilde{O}$ hides the logarithmic factors. The problem
as well as the notion of $\alpha$-regret are introduced in Section 2. We
provide a first algorithm and establish theoretical guarantees in Section 3.
In Section 4, we identify the problem-dependent 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
$\alpha$. Finally, Section 5 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 at each round implies to 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. (2021) give a detailed
analysis of the problem and show that a 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 (Cesa-Bianchi 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 et al., 2020) where the notion of $\alpha$-regret is introduced to
cope with the NP-Hardness of the problem. Most papers assume the availability
of an oracle to solve the inner combinatorial optimization problem at each
round. In this paper, we do not make this assumption and we 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 et al. (2014); Mannor and Shamir (2011), each node
of the graph is an arm of the bandit problem, which, if pulled, gives
information on its neighboring arms. On the other hand, in Cesa-Bianchi 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 an 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 bilinear bandits setting.

##  2 Problem setting

Let $\mathcal{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)\in E$ then $(j,i)\in E$.111One 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. The Graphical Bilinear Bandit with a graph $\mathcal{G}$ consists
in the following sequential problem (Rizk et al., 2021): at each round $t$,
each agent $i\in V$ chooses an arm $x^{(i)}_{t}$ in a finite arm set
$\mathcal{X}$ and receives for each of its neighbors $j$ a bilinear reward

$\displaystyle
y^{(i,j)}_{t}=x^{(i)\top}_{t}\mathbf{M}_{\star}x^{(j)}_{t}+\eta^{(i,j)}_{t}\enspace,$
(1)

where $\mathbf{M}_{\star}\in\mathbb{R}^{d\times d}$ is an unknown matrix, and
$\eta^{(i,j)}_{t}$ a zero-mean $\sigma$-sub-Gaussian random variable.222One
may wish that the agent’s reward $i$ also takes into account the quality of
its chosen arm alone (i.e., not compared to the one chosen by its neighbors).
We discuss this case in the appendix and show that if we add a linear term as
a function of $x^{(i)}_{t}$ to the bilinear reward, the new reward can still
be reduced to a simple bilinear reward with an unknown matrix
$\mathbf{M}_{\star}\in\mathbb{R}^{(d+1)\times(d+1)}$.

For all agent $i\in V$, we denote $\mathcal{N}_{i}$ the set of its neighboring
agents. Let $n=\mathrm{Card}\left(V\right)$ denote the number of nodes,
$m=\mathrm{Card}\left(E\right)$ the number of edges and
$K=\mathrm{Card}\left(\mathcal{X}\right)$ the number of arms. We assume that
for all $x\in\mathcal{X},\|x\|_{2}\;\leq L$. Let $\|\mathbf{M}_{\star}\|_{F}$
be the Frobenius norm of $\mathbf{M}_{\star}$ with
$\|\mathbf{M}_{\star}\|_{F}\leq S$. We assume that the expected reward of each
edge is positive which gives for all $(x,x^{\prime})\in\mathcal{X}^{2},\;0\leq
x^{\top}\mathbf{M}_{\star}x^{\prime}\leq LS$.

For each round $t$, we define the global reward $y_{t}=\sum_{(i,j)\in
E}y^{(i,j)}_{t}$ as the sum of the local rewards obtained over the graph at
round $t$, and
$\left(x_{\star}^{(1)},\dots,x_{\star}^{(n)}\right)=\mathop{\mathrm{arg\,max}}_{\left(x^{(1)},\dots,x^{(n)}\right)}\sum_{(i,j)\in
E}x^{(i)\top}\mathbf{M}_{\star}x^{(j)}$ as the optimal joint arm that
maximizes the expected global reward. The corresponding global pseudo-regret
over $T$ rounds is then defined as follows:

$\displaystyle R(T)=\sum_{t=1}^{T}\left[\sum_{(i,j)\in
E}x^{(i)\top}_{\star}\mathbf{M}_{\star}x^{(j)}_{\star}-\sum_{(i,j)\in
E}x^{(i)\top}_{t}\mathbf{M}_{\star}x^{(j)}_{t}\right]\enspace.$

We know from Rizk et al. (2021) that finding
$\left(x_{\star}^{(1)},\dots,x_{\star}^{(n)}\right)$ is NP-Hard with respect
to the number of agents $n$.

######  Proposition 2.1 (Rizk et al. (2021) Theorem 4.1).

Consider a given matrix $\mathbf{M}_{\star}\in\mathbb{R}^{d\times d}$ and a
finite arm set $\mathcal{X}\subset\mathbb{R}^{d}$. Unless P=NP, there is no
polynomial time algorithm guaranteed to find the optimal solution of

$\displaystyle\max_{\left(x^{(1)},\ldots,x^{(n)}\right)\in\mathcal{X}^{n}}\sum_{(i,j)\in
E}x^{(i)\top}\mathbf{M}_{\star}\ x^{(j)}\enspace.$

Hence, the objective of designing an algorithm with a sublinear regret in $T$
is not feasible in polynomial time with respect to $n$. However, some NP-hard
problems are $\alpha$-approximable (for some $\alpha\in(0,1]$), which means
that there exists a polynomial-time algorithm guaranteed to produce solutions
whose values are at least $\alpha$ times the value of the optimal solution.
For these problems, it makes sense to consider the $\alpha$-pseudo-regret as
in (Chen et al., 2013) which is defined for all $\alpha\in(0,1]$ as follows

$\displaystyle R_{\alpha}(T)$
$\displaystyle\triangleq\sum_{t=1}^{T}\left[\sum_{(i,j)\in E}\alpha
x^{(i)\top}_{\star}\mathbf{M}_{\star}x^{(j)}_{\star}-\sum_{(i,j)\in
E}x^{(i)\top}_{t}\mathbf{M}_{\star}x^{(j)}_{t}\right]\enspace,$

and set the objective of designing an algorithm with a sublinear
$\alpha$-regret.

The linear form. The reward can either be viewed as a bilinear reward as shown
in (1) or as a linear reward in higher dimension (Jun et al., 2019) with
$y^{(i,j)}_{t}=\left\langle\operatorname*{vec}{\left(x^{(i)}_{t}x^{(j)\top}_{t}\right)},\operatorname*{vec}{(\mathbf{M}_{\star})}\right\rangle+\eta^{(i,j)}_{t}$
where for any matrix $\mathbf{A}\in\mathbb{R}^{d\times d}$,
$\operatorname*{vec}{(\mathbf{A})}$ denotes the vector in $\mathbb{R}^{d^{2}}$
which is the concatenation of all the columns of A, and
$\left\langle\cdot,\cdot\right\rangle$ refers to the dot product between two
vectors.

To simplify the notation, let us refer to any $x\in\mathcal{X}$ as a _node-
arm_ and define the arm set
$\mathcal{Z}=\\{\operatorname*{vec}{(xx^{\prime\top})}|(x,x^{\prime})\in\mathcal{X}\\}$
where any $z\in Z$ will be referred as an _edge-arm_. If the arm
$x^{(i)}_{t}\in\mathcal{X}$ represents the node-arm allocated to the node
$i\in V$ at time $t$, for each edge $(i,j)\in E$ we will denote the associated
edge-arm by
$z^{(i,j)}_{t}:=\operatorname*{vec}{\left(x^{(i)}_{t}x^{(j)\top}_{t}\right)}\in\mathcal{Z}$
and define $\theta_{\star}=\operatorname*{vec}{(\mathbf{M}_{\star})}$ the
vectorized version of the unknown matrix $\mathbf{M}_{\star}$ with
$\|\theta_{\star}\|_{2}\leq S$. With those notations, the (now) linear reward
can be rewritten as follows:

$\displaystyle y^{(i,j)}_{t}=\left\langle z^{(i,j)}_{t},\
\theta_{\star}\right\rangle+\eta^{(i,j)}_{t}\enspace.$ (2)

When needed, for any node-arms $(x,x^{\prime})\in\mathcal{X}^{2}$ we use the
abbreviation $z_{xx^{\prime}}\triangleq\operatorname*{vec}(xx^{\prime\top})$.
Finally for any vector $x\in\mathbb{R}^{d}$ and a symmetric positive-definite
matrix $\mathbf{A}\in\mathbb{R}^{d\times d}$, we define
$\|x\|_{\mathbf{A}}\triangleq\sqrt{x^{\top}\mathbf{A}x}$.

##  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)\in E$, the central entity is trying to solve $m$
_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 $m$ 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,j)$ and $(j,k)$ share the node $j$, hence
their allocated edge-arms must share the node-arm $x^{(j)}_{t}$.

In this paper, we choose to design an algorithm based on the principle of
optimism in the face of uncertainty Auer et al. (2002), and in the case of a
linear reward Li et al. (2010); Abbasi-Yadkori et al. (2011), we need to
maintain an estimator of the true parameter $\theta_{\star}$. To do so, let us
define for all rounds $t\in\\{1,\dots,T\\}$ the OLS estimator of
$\theta_{\star}$ as follows:

$\displaystyle\hat{\theta}_{t}=\mathbf{A}^{-1}_{t}b_{t}\enspace,$ (3)

where,

$\displaystyle\mathbf{A}_{t}=\lambda\mathbf{I}_{d^{2}}+\sum_{s=1}^{t}\sum_{(i,j)\in
E}z^{(i,j)}_{s}z^{(i,j)\top}_{s}\enspace,$

with $\lambda>0$ a regularization parameter and

$\displaystyle b_{t}=\sum_{s=1}^{t}\sum_{(i,j)\in
E}z^{(i,j)}_{s}y^{(i,j)}_{s}\enspace.$

We define also the confidence set

$\displaystyle
C_{t}(\delta)=\left\\{\theta:\|\theta-\hat{\theta}_{t}\|_{A_{t}^{-1}}\leq\sigma\sqrt{d^{2}\log\left(\frac{1+tmL^{2}/\lambda}{\delta}\right)}+\sqrt{\lambda}S\right\\}\enspace,$

where with probability $1-\delta$, we have that $\theta_{\star}\in
C_{t}(\delta)$ for all $t\in\\{1,\dots,T\\}$, and $\delta\in(0,1]$.

Input : graph $\mathcal{G}=(V,E)$, node-arm set $\mathcal{X}$

$(V_{1},V_{2})=\text{Approx-MAX-CUT}(\mathcal{G})$

for  _$t=1$ to $T$_ do

// Find the optimistic best couple of node-arms

$\left(x_{t},x_{t}^{\prime},\tilde{\theta}_{t-1}\right)=\mathop{\mathrm{arg\,max}}_{\left(x,x^{\prime},\theta\right)\in\mathcal{X}^{2}\times
C_{t-1}}\langle z_{xx^{\prime}}+z_{x^{\prime}x},\theta\rangle$;

// Allocate $x_{t}$ and $x_{t}^{\prime}$ in the graph

$x_{t}^{(i)}=x_{t}$ for all $i$ in $V_{1}$; $x_{t}^{(i)}=x_{t}^{\prime}$ for
all $i$ in $V_{2}$;

Obtain for all $(i,j)$ in $E$ the rewards $y_{t}^{(i,j)}$;

Compute $\hat{\theta}_{t}$ as in (3)

end for

return $\hat{\theta}_{t}$

Algorithm 1 Adaptation of OFUL algorithm for Graphical Bilinear Bandit

Input : $\mathcal{G}=(V,E)$

Set $V_{1}=\emptyset$, $V_{2}=\emptyset$

for  _$i$ in $V$_ do

$n_{1}=\mathrm{Card}\left(\\{(i,j)\in E\ |\ j\in V_{1}\\}\right)$;

$n_{2}=\mathrm{Card}\left(\\{(i,j)\in E\ |\ j\in V_{2}\\}\right)$;

if $n_{1}>n_{2}$ then $V_{2}\leftarrow V_{2}\cup\\{i\\}$ else $V_{1}\leftarrow
V_{1}\cup\\{i\\}$;

end for

return $(V_{1},V_{2})$

Algorithm 2 Approx-MAX-CUT

Since the graphical bilinear bandit can be seen as a linear bandit in
dimension $d^{2}$ and with $K^{n}$ possible arms,333It can be seen as a linear
bandit problem because the goal of the central entity is to maximize at each
round $t$ the expected global reward $\sum_{(i,j)\in
E}x^{(i)\top}_{t}\mathbf{M}_{\star}x^{(j)}_{t}=\sum_{(i,j)\in
E}z^{(i,j)\top}_{t}\theta_{\star}=\left\langle\sum_{(i,j)\in E}z^{(i,j)}_{t},\
\theta_{\star}\right\rangle$ the idea of our method is to overcome the NP-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

$\displaystyle(x^{(1)}_{t},\dots,x^{(n)}_{t})=\mathop{\mathrm{arg\,max}}_{(x^{(1)},\dots,x^{(n)})\in\mathcal{X}^{n}}\max_{\theta\in
C_{t-1}(\delta)}\left\langle\sum_{(i,j)\in
E}z_{x^{(i)}x^{(j)}},\theta\right\rangle\enspace,$

we consider the couple of node-arms
$(x_{\star},x^{\prime}_{\star})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\theta_{\star}\rangle$ maximizing the reward
along one edge.444The reward of an edge here denotes the sum of the rewards of
the two corresponding directed edges in $E$. Given the optimal joint arm
$(x^{(1)}_{\star},\dots,x^{(n)}_{\star})$ and the associated optimal edge-arms
$z^{(i,j)}_{\star}=\operatorname*{vec}{(x^{(i)}_{\star}x^{(j)}_{\star})}$ for
all $(i,j)\in E$, we have

$\displaystyle\langle
z^{(i,j)}_{\star}+z^{(j,i)}_{\star},\theta_{\star}\rangle\leq\langle
z_{x_{\star}x^{\prime}_{\star}}+z_{x^{\prime}_{\star}x_{\star}},\theta_{\star}\rangle\enspace.$
(4)

Hence, an alternative objective is to construct as many edge-arms
$z_{x_{\star}x^{\prime}_{\star}}$ and $z_{x^{\prime}_{\star}x_{\star}}$ as
possible in the graph. Naturally, we do not have access to $\theta_{\star}$,
so we use the principle of optimism in the face of uncertainty, which is to
find the couple $(x_{t},x^{\prime}_{t})$ such that

$\displaystyle(x_{t},x^{\prime}_{t})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\max_{\theta\in
C_{t-1}(\delta)}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\theta\rangle\enspace,$

and then allocate the node-arms to maximize the number of locally-optimal
edge-arms $z_{x_{t}x^{\prime}_{t}}$ and $z_{x^{\prime}_{t}x_{t}}$. The
motivation of this alternative goal can be understood thanks to (4) where we
know that the associated expected reward is better than the one obtained with
the edge-arms created with the optimal joint arms. Of course, one can also
easily understand that for a general type of graph it is not possible to
allocate those edge-arms everywhere (i.e., to all the edges). For example take
a complete graph of three nodes, allocating the edge-arms
$z_{x_{t}x^{\prime}_{t}}$ and $z_{x^{\prime}_{t}x_{t}}$ is equivalent to
allocate $x_{t}$ and $x_{t}^{\prime}$ to the nodes. By doing so, two nodes
will pull $x_{t}$ and the third one will pull $x_{t}^{\prime}$, which makes it
inevitable to allocate sub-optimal and unwanted edge-arms of the form
$z_{x_{t}x_{t}}$.

The main concern with this method is to control how many unwanted edge-arms
are drawn in each round (relative to the total number $m$ of edges) in order
to minimize their impact on the resulting regret. Assigning $x_{t}$ to a
subset of nodes and $x_{t}^{\prime}$ to the complementary is equivalent to
cutting the graph into two pieces and creating two distinct sets of nodes
$V_{1}$ and $V_{2}$ such that $V=V_{1}\cup V_{2}$ and $V_{1}\cap
V_{2}=\emptyset$. Pulling the maximum amount of optimal edge-arms thus boils
down to finding a cut passing through the maximum number of edges.

This problem is known as the Max-Cut 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 a cut passing through at least a given fraction of the edges in the
graph.555Most 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 on the algorithm we choose.

######  Proposition 3.1.

Given a graph $\mathcal{G}=(V,E)$, Algorithm 2 returns a couple
$(V_{1},V_{2})$ such that

$\displaystyle\mathrm{Card}\left(\\{(i,j)\in E\ |\ \left(i\in V_{1}\wedge j\in
V_{2}\right)\vee\left(i\in V_{2}\wedge j\in
V_{1}\right)\\}\right)\geq\frac{m}{2}\enspace.$

Using Algorithm 2 we can thus divide the set of nodes $V$ into two subsets
$V_{1}$ and $V_{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. (2011) we obtain
Algorithm 1 for which we can state the following guarantees on the
$\alpha$-regret.

######  Theorem 3.2.

Given the Graphical Bilinear Bandit problem defined in Section 2, let
$0\leq\gamma\leq 1$ be a problem-dependent parameter defined by

$\displaystyle\gamma=\min_{x\in\mathcal{X}}\frac{\langle
z_{xx},\theta_{\star}\rangle}{\frac{1}{m}\sum_{(i,j)\in E}\left\langle
z^{(i,j)}_{\star},\theta_{\star}\right\rangle}\geq 0\enspace,$

and set $\alpha=\frac{1+\gamma}{2}$, then the $\alpha$-regret of Algorithm 1
satisfies

$\displaystyle R_{\alpha}(T)\leq\tilde{O}\left(\left(\sigma
d^{2}+S\sqrt{\lambda}\right)\sqrt{Tm\max\left(2,(LS)^{2}\right)}\right)+LSm\left\lceil
d^{2}\log_{2}\left(\frac{TmL^{2}/\lambda}{\delta}\right)\right\rceil\enspace,$

where $\tilde{O}$ 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 $Tm$ 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 $(x_{t},x_{t}^{\prime})$
chosen at round $t$ (and thus after having already pulled $tm$ edge-arms and
received $tm$ rewards) is relevant to pull the $(tm+1)$-th edge-arm but not
necessarily the $(m-1)$ edge-arms that follows (from the $(tm+2)$-th to the
$(tm+m)$-th one) since the reward associated to the $(tm+1)$-th edge-arms
could have led to change the central entity choice if it had been done
sequentially. In Chan et al. (2021), 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 $O(\log(Tm)))$.

What is $\gamma$ 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 $z_{xx}$. For example, if there exists
$x_{0}\in\mathcal{X}$ such that $\langle
z_{x_{0}x_{0}},\theta_{\star}\rangle=0$, then $\gamma=0$ as well and we are in
the worst case scenario where we can only have a guarantee on an
$\alpha$-regret with $\alpha=1/2$. In practice, having $\gamma=0$ is reached
when given the couple
$(x_{\star},x^{\prime}_{\star})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\theta_{\star}\rangle$, this $x_{0}$ is either
$x_{\star}$ or $x_{\star}^{\prime}$. In other words, if the unwanted edge-arms
associated to the couple $(x_{\star},x^{\prime}_{\star})$ gives low rewards,
then the guarantee on the regret will be badly impacted. Hence we can wonder
how we 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 at the selection of the pair
$(x_{t},x_{t}^{\prime})$ 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
$\frac{1+\gamma}{2}$-no-regret property to optimize the allocation of the arms
$x_{t}$ and $x_{t}^{\prime}$ such that the unwanted and suboptimal arms
$z_{x_{t}x_{t}}$ and $z_{x_{t}^{\prime}x_{t}^{\prime}}$ penalize as less as
possible the reward.

Indeed, in Algorithm 1, the choice of the couple $(x_{t},x_{t}^{\prime})$ is
driven by the optimistic reward of the edge-arms $z_{x_{t}x_{t}^{\prime}}$ and
$z_{x_{t}x_{t}^{\prime}}$ but not on the one of the unwanted arms
$z_{x_{t}x_{t}}$ and $z_{x_{t}^{\prime}x_{t}^{\prime}}$. Here, the first
improvement that we can provide is to include them in the selection of the
couple $(x_{t},x^{\prime}_{t})$ as follows

$\displaystyle(x_{t},x^{\prime}_{t})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\max_{\theta\in
C_{t-1}(\delta)}\left\langle
z_{xx^{\prime}}+z_{x^{\prime}x}+z_{xx}+z_{x^{\prime}x^{\prime}},\theta\right\rangle\enspace.$

However, this selection suggests that the number of unwanted edge-arms
$z_{x_{t}x_{t}}$ and $z_{x_{t}^{\prime}x_{t}^{\prime}}$ will be equal to the
number of optimal edge-arm $z_{x_{t}x_{t}^{\prime}}$ and
$z_{x_{t}^{\prime}x_{t}}$ (in the sense of optimism), which is in general not
true.666It 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. Hence,
one has to take into consideration the proportion of edges that will be
allocated by suboptimal and unwanted edge-arms or by optimistically optimal
edge-arms.

To do so, let us define $m_{1}$ (respectively $m_{2})$ the number of edges
that goes from nodes in $V_{1}$ (respectively $V_{2}$) to nodes in $V_{1}$ as
well (respectively $V_{2}$) and $m_{1\rightarrow 2}$ (respectively
$m_{2\rightarrow 1}$) the number of edges that goes from nodes in $V_{1}$
(respectively $V_{2}$) to nodes in $V_{2}$ (respectively $V_{1}$). One can
notice that by definition of the edge set $E$, we have $m_{1\rightarrow
2}=m_{2\rightarrow 1}$ and that the total number of edges $m=m_{1\rightarrow
2}+m_{2\rightarrow 1}+m_{1}+m_{2}$. By choosing the couple
$(x_{t},x_{t}^{\prime})$ as follows

$\displaystyle(x_{t},x^{\prime}_{t})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\max_{\theta\in
C_{t-1}(\delta)}\left\langle m_{1\rightarrow 2}\cdot
z_{xx^{\prime}}+m_{2\rightarrow 1}\cdot z_{x^{\prime}x}+m_{1}\cdot
z_{xx}+m_{2}\cdot z_{x^{\prime}x^{\prime}},\theta\right\rangle\enspace,$

we are optimizing the total optimistic reward that one would obtain when
allocating only two arms $(x,x^{\prime})\in\mathcal{X}^{2}$ in the graph. This
strategy is described in Algorithm 3.

Input : graph $\mathcal{G}=(V,E)$, node-arm set $\mathcal{X}$

$(V_{1},V_{2})=\text{Approx-MAX-CUT}(\mathcal{G})$;

$m_{1\rightarrow 2}=m_{2\rightarrow 1}=\mathrm{Card}\left(\\{(i,j)\in E|i\in
V_{1}\wedge j\in V_{2}\\}\right)$;

$m_{1}=\mathrm{Card}\left(\\{(i,j)\in E|i\in V_{1}\wedge j\in
V_{1}\\}\right)$; $m_{2}=\mathrm{Card}\left(\\{(i,j)\in E|i\in V_{2}\wedge
j\in V_{2}\\}\right)$;

for  _$t=1$ to $T$_ do

$\left(x_{t},x_{t}^{\prime},\tilde{\theta}_{t-1}\right)=\mathop{\mathrm{arg\,max}}_{\left(x,x^{\prime},\theta\right)\in\mathcal{X}^{2}\times
C_{t-1}}\left\langle m_{1\rightarrow 2}\cdot z_{xx^{\prime}}+m_{2\rightarrow
1}\cdot z_{x^{\prime}x}+m_{1}\cdot z_{xx}+m_{2}\cdot
z_{x^{\prime}x^{\prime}},\theta\right\rangle$;

$x_{t}^{(i)}=x_{t}$ for all $i$ in $V_{1}$; $x_{t}^{(i)}=x_{t}^{\prime}$ for
all $i$ in $V_{2}$;

Obtain for all $(i,j)$ in $E$ the rewards $y_{t}^{(i,j)}$;

Compute $\hat{\theta}_{t}$ as in (3)

end for

return $\hat{\theta}_{t}$

Algorithm 3 Improved OFUL for Graphical Bilinear Bandits

Before stating the guarantees on the $\alpha$-regret of this improved
algorithm, let us recall that we defined
$(x_{\star},x_{\star}^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\theta_{\star}\rangle$ and let us define the
couple $(\tilde{x}_{\star},\tilde{x}_{\star}^{\prime})$ such that

$\displaystyle(\tilde{x}_{\star},\tilde{x}_{\star}^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}}\langle
m_{1\rightarrow 2}\cdot z_{xx^{\prime}}+m_{2\rightarrow 1}\cdot
z_{x^{\prime}x}+m_{1}\cdot z_{xx}+m_{2}\cdot
z_{x^{\prime}x^{\prime}},\theta_{\star}\rangle\enspace.$

We define $\Delta\geq 0$ to be the expected reward difference of allocating
$(\tilde{x}_{\star},\tilde{x}_{\star}^{\prime})$ instead of
$(x_{\star},x_{\star}^{\prime})$,

$\displaystyle\Delta=$ $\displaystyle\,\langle m_{1\rightarrow
2}\left(z_{\tilde{x}_{\star}\tilde{x}_{\star}^{\prime}}-z_{x_{\star}x_{\star}^{\prime}}\right)+m_{2\rightarrow
1}\left(z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}}-z_{x_{\star}^{\prime}x_{\star}}\right)$
$\displaystyle+m_{1}\left(z_{\tilde{x}_{\star}\tilde{x}_{\star}}-z_{x_{\star}x_{\star}}\right)+m_{2}\left(z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}^{\prime}}-z_{x_{\star}^{\prime}x_{\star}^{\prime}}\right),\theta_{\star}\rangle\enspace.$

The new guarantees that we get on the $\alpha$-regret of Algorithm 3 are
stated in the following theorem.

######  Theorem 4.1.

Given the Graphical Bilinear Bandit problem defined as in Section 2, let
$\gamma$ be defined as in Theorem 3.2, let $0\leq\epsilon\leq\frac{1}{2}$ be a
problem dependent parameter that measures the gain of optimizing on the
suboptimal and unwanted arms defined as:

$\displaystyle\epsilon=\frac{\Delta}{\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle}\enspace,$

and set $\alpha=1-\left[\frac{m1+m2}{m}\left(1-\gamma\right)-\epsilon\right]$
where $\alpha\geq 1/2$ by construction, then the $\alpha$-regret of Algorithm
3 satisfies

$\displaystyle R_{\alpha}(T)\leq$ $\displaystyle\tilde{O}\left(\left(\sigma
d^{2}+S\sqrt{\lambda}\right)\sqrt{Tm\max\left(2,(LS)^{2}\right)}\right)+LSm\left\lceil
d^{2}\log_{2}\left(\frac{TmL^{2}/\lambda}{\delta}\right)\right\rceil\enspace,$

where $\tilde{O}$ hides the logarithmic factors.

Here one can see that the improvement happens in the $\alpha$ of the
$\alpha$-regret. Let us analyze more precisely this term. First of all, notice
that in a complete graph (which is the worst case scenario in terms of graph
type and guarantees of the cut), we get
$\alpha\geq\frac{1+\gamma}{2}+\epsilon$ which shows that optimizing over the
suboptimal arms already improves our bound by $\epsilon$. On the contrary, in
the most favorable graphs, which are bipartite graphs (i.e., graphs where all
the $m$ edges goes from nodes in $V_{1}$ to nodes in $V_{2}$ or vice versa),
we have $m_{2}+m_{1}=0$ and $\epsilon=0$ which gives $\alpha=1$ and makes the
Algorithm 3 a no-regret algorithm. What may also be of interest is to
understand how $\alpha$ varies with respect to $\gamma$, $\epsilon$ and the
quantity $m_{1}$ and $m_{2}$ for graphs that are between a complete graph and
a bipartite graph. We investigate experimentally this dependency in Section 5.

##  5 Experiments - Influence of the problem parameters on the regret

In this section, we give some insights on the problem-dependent parameters
$\gamma$ and $\epsilon$ and the corresponding $\alpha$. Let $\alpha_{1}$ and
$\alpha_{2}$ be the $\alpha$ stated respectively in Theorem 3.2 and Theorem
4.1. In the first experiment, we show the dependence of $\alpha_{1}$ and
$\alpha_{2}$ on the graph type and the chosen approximation algorithm for the
max-cut problem with respect to $\gamma$ and $\epsilon$. We also highlight the
differences between the two parameters $\alpha_{1}$ and $\alpha_{2}$ and the
significant improvement in guarantees that one can obtain using Algorithm 3
depending on the type of the graph. The results are presented in Table 1.

Table 1: Value of several parameters with respect to the type of graph. Experiments were 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
$\frac{m1+m2}{m}$ | $0.495$ | $0.453$ | $0.01$ | $0$ | $0$
$\alpha_{1}$ | $0.5+0.5\gamma$
$\alpha_{2}$ | $0.505+0.495\gamma+\epsilon$ | $0.547+0.453\gamma+\epsilon$ | $0.99+0.01\gamma+\epsilon$ | 1 | 1

One can notice that the complete graph seems to be the one that gives the
worst guarantee on the $\alpha$-regret with respect to $\epsilon$ and
$\gamma$. 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 $n=10$ agents. The second experiment studies the variation of
$\epsilon$ and $\gamma$ with respect to the unknown parameter matrix
$\mathbf{M}_{\star}$. To design such experiments, we consider the arm-set
$\mathcal{X}$ as the vectors $(e_{1},\dots,e_{d})$ of canonical base in
$\mathbb{R}^{d}$, which implies by construction that the arm-set $\mathcal{Z}$
contains the vectors $(e_{1},\dots,e_{d^{2}})$ of the canonical base in
$\mathbb{R}^{d^{2}}$. We generate the matrix $\mathbf{M}_{\star}$ 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 of
these elements to 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 matrix $\mathbf{M}_{\star}$ and to illustrate in a simple way the
dependence on $\gamma$ and $\epsilon$. Consider the best couple
$(i^{\star},j^{\star})=\mathop{\mathrm{arg\,max}}_{(i,j)\in\\{1,\dots,d\\}^{2}}\langle
z_{e_{i}e_{j}}+z_{e_{j}e_{i}},\theta_{\star}\rangle$, we want to see how the
reward of the suboptimal edge-arms $z_{e_{i^{\star}}e_{i^{\star}}}$ and
$z_{e_{j^{\star}}e_{j^{\star}}}$ impact the value of $\gamma$, $\epsilon$ and
thus $\alpha$. Notice that the reward associated to the edge-arm
$z_{e_{i^{\star}}e_{i^{\star}}}$ (respectively
$z_{e_{j^{\star}}e_{j^{\star}}}$) is $\mathbf{M}_{\star i^{\star}i^{\star}}$
(respectively $\mathbf{M}_{\star j^{\star}j^{\star}}$). Hence we define
$0\leq\zeta<1$ and set $\mathbf{M}_{\star
i^{\star}i^{\star}}=\mathbf{M}_{\star
j^{\star}j^{\star}}=\zeta\times\frac{1}{2}(\mathbf{M}_{\star
i^{\star}j^{\star}}+\mathbf{M}_{\star j^{\star}i^{\star}})$. We study the
variation of $\gamma$, $\epsilon$, $\alpha_{1}$ and $\alpha_{2}$ with respect
to $\zeta$. The results are presented in Figure 2. One can see that when the
associated rewards of $z_{e_{i^{\star}}e_{i^{\star}}}$ and
$z_{e_{j^{\star}}e_{j^{\star}}}$ are low (thus $\gamma$ is low and $\epsilon$
high), Algorithm 3 gives a much better guarantees than Algorithm 1 since it
will focus on other node-arms than $e_{i^{\star}}$ and $e_{j^{\star}}$ that
will give a higher global reward. Moreover, even when the unwanted edge-arm
gives a high reward, the guarantees on the regret of Algorithm 3 are still
stronger because it takes into consideration the quantities $m_{1}$ and
$m_{2}$ of the constructed suboptimal edge-arms.

Figure 1: Variation of $\epsilon$, $\gamma$, $\alpha_{1}$ and $\alpha_{2}$
with respect to the parameter $\zeta$. The closer $\zeta$ is to $0$ the lower
the reward of the unwanted arms $z_{e_{i^{\star}}e_{i^{\star}}}$ and
$z_{e_{i^{\star}}e_{i^{\star}}}$, the closer $\zeta$ is to 1 the higher the
reward of the unwanted arms. The dimension $d$ of the arm-set is $10$ (which
gives linear reward with unknown parameter $\theta_{\star}$ of dimension
$100$). The plotted curve represents the average value of the parameters over
100 different matrices $\mathbf{M}_{\star}$ initiated randomly with positive
values.

Figure 2: Fraction of the global reward obtained at each round by applying the
Algorithm 1, Algorithm 3 and the Explore-Then-commit algorithm (here named
GBB-BAI) using the exploration strategy in Rizk et al. (2021). We use a
complete graph of 5 nodes, we run the experiment on 5 different matrices as in
Figure 2 with $\zeta=0$ and run it 10 different times to plot the average
fraction of the global reward

Finally, we design a last experiment that compares in practice the performance
of Algorithm 1 and Algorithm 3 with the Explore-Then-Commit algorithm by using
the exploration strategy designed in Rizk et al. (2021) during the exploration
phase, and by allocating the nodes in $V_{1}$ and $V_{2}$ with the best
estimated couple
$(x,x^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\hat{\theta}_{t}\rangle$ during the commit
phase.

##  6 Conclusion & discussions

In this paper, we presented the first regret-based algorithm for the
stochastic graphical bilinear bandit problem with guarantees on the
$\alpha$-regret. We showed that by exploiting the graph structure and the
typology of the problem, one can both improve the performance in practice and
have a better theoretical guarantee on its $\alpha$-regret. Also, we showed
experimentally that our algorithm achieves a better performance than Explore-
Then-Exploit on our synthetic datasets. The method presented in this article
can be extended in 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-
Cut_ (Frieze and Jerrum, 1997) with $k\geq 3$. With the knowledge of such a
partition of nodes $V_{1},\dots,V_{k}$, one may want to look for a $k$-tuple
of node-arms maximizing the optimistic allocated reward rather than a 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 to our case. Finally, our setting could
be extended to the case where each agent has its own reward matrix.

## References

  * Abbasi-Yadkori et al. (2011) Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , pages 2312–2320, 2011.
  * Audibert and Bubeck (2010) J.-Y. Audibert and S. Bubeck.  Best arm identification in multi-armed bandits.  In _Proceedings of the 23th Annual Conference on Learning Theory_ , pages 41–53, 2010.
  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, and P. Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Bargiacchi et al. (2018) E. Bargiacchi, T. Verstraeten, D. Roijers, A. Nowé, and H. Hasselt.  Learning to coordinate with coordination graphs in repeated single-stage multi-agent decision problems.  In _International conference on machine learning_ , pages 482–490, 2018.
  * Bubeck et al. (2009) S. Bubeck, R. Munos, and G. Stoltz.  Pure exploration in multi-armed bandits problems.  In _International conference on Algorithmic learning theory_ , pages 23–37. Springer, 2009.
  * Cesa-Bianchi and Lugosi (2012) N. Cesa-Bianchi and G. Lugosi.  Combinatorial bandits.  _Journal of Computer and System Sciences_ , 78(5):1404 – 1422, 2012.
  * Cesa-Bianchi et al. (2013) N. Cesa-Bianchi, C. Gentile, and G. Zappella.  A gang of bandits.  In _Advances in Neural Information Processing Systems_ , pages 737–745, 2013.
  * Chan et al. (2021) J. Chan, A. Pacchiano, N. Tripuraneni, Y. S. Song, P. Bartlett, and M. I. Jordan.  Parallelizing contextual linear bandits.  _arXiv preprint arXiv:2105.10590_ , 2021.
  * Chen et al. (2013) 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.
  * Frieze and Jerrum (1997) A. Frieze and M. Jerrum.  Improved approximation algorithms for max k-cut and max bisection.  _Algorithmica_ , 18(1):67–81, 1997.
  * Guestrin et al. (2002) C. Guestrin, M. G. Lagoudakis, and R. Parr.  Coordinated reinforcement learning.  In _Proceedings of the Nineteenth International Conference on Machine Learning_ , page 227–234, 2002.
  * Jun et al. (2019) 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.
  * Lattimore and Szepesvári (2018) T. Lattimore and C. Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, 2018.
  * Li et al. (2010) L. Li, W. Chu, J. Langford, and R. E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Mannor and Shamir (2011) 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 et al. (2020) P. Perrault, E. Boursier, M. Valko, and V. Perchet.  Statistical efficiency of thompson sampling for combinatorial semi-bandits.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Rizk et al. (2021) G. Rizk, A. Thomas, I. Colin, R. Laraki, and Y. Chevaleyre.  Best arm identification in graphical bilinear bandits.  In _International Conference on Machine Learning_ , pages 9010–9019. PMLR, 2021.
  * Siomina et al. (2006) 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.
  * Valko et al. (2014) M. Valko, R. Munos, B. Kveton, and T. Kocák.  Spectral bandits for smooth graph functions.  In E. P. Xing and T. Jebara, editors, _International conference on machine learning_ , volume 32 of _Proceedings of Machine Learning Research_ , pages 46–54, 2014.
  * van Dijk et al. (2016) M. T. van Dijk, J.-W. van Wingerden, T. Ashuri, Y. Li, and M. A. Rotea.  Yaw-misalignment 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.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [No]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes] In the
appendix section

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [No]
The code will be released if the paper is accepted to the conference

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes] All the details are explained again in the
supplementary material

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Also in the
appendix

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [No]

    2. (b)

Did you mention the license of the assets? [No]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [No]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [No]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [No]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [No]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [No]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [No]

##  Appendix A Proof of Proposition 3.1

###### Proof.

Let consider the subgraph $\mathcal{G}^{(i)}$ containing all the nodes that
have been assigned to $V_{1}$ or $V_{2}$ at the end of iteration $i$ of
Algorithm 2. Let us denote $m^{(i)}$ the number of edges in the graph
$\mathcal{G}^{(i)}$.

At the first iteration, the algorithm chooses the node $1$, computes $n_{1}=0$
and $n_{2}=0$, and then assigns node $1$ to $V_{1}$. With only one node in
$\mathcal{G}^{(1)}$, we have $m^{(1)}=0$. By denoting $c^{(i)}$ the number of
additional cut edges induces by the assignment of node $i$ at iteration $i$,
we have

$\displaystyle\sum_{i=1}^{1}c^{(i)}=c^{(1)}=0\geq\frac{m^{(1)}}{2}$ (5)

Indeed, at the end of iteration $1$, there is only one node assigned, hence
the number of cut edges induced by this assignment is $c^{(1)}=0$.

Suppose that $\sum_{i=1}^{p}c^{(i)}\geq\frac{m^{(p)}}{2}$ for a certain
$p\in\\{1,\dots,n-1\\}$, let us prove that $\sum_{i=1}^{p+1}c^{(i)}\geq
m^{(p+1)}/2$.

Indeed, at the iteration $p+1$, the algorithm chooses the node $(p+1)$ and
computes $n_{1}$ and $n_{2}$. Since $n_{1}$ represents the number of neighbors
of the node $(p+1)$ in $V_{1}$, if the node $p+1$ is added to $V_{2}$, then
$2\times n_{1}$ edges would be cut (the factor $2$ comes from the fact that
between two nodes $i$ and $j$, there are the edges $(i,j)$ and $(j,i)$).
Similarly, since $n_{2}$ represents the number of neighbors of the node
$(p+1)$ in $V_{2}$, if the node $(p+1)$ is added to $V_{1}$, then $2\times
n_{2}$ edges would be cut. Notice also that there is a total of $2\times
n_{1}+2\times n_{2}$ edges between the node $(p+1)$ and the nodes in
$\mathcal{G}^{(p)}$. In the algorithm, the node $(p+1)$ is added to $V_{1}$ or
$V_{2}$ such that we cut the most edges, indeed one has

$\displaystyle
c^{(p+1)}=\max\left(2n_{1},2n_{2}\right)\geq\frac{2n_{1}+2n_{2}}{2}=n_{1}+n_{2}\enspace.$

Hence,

$\displaystyle\sum_{i=1}^{p+1}c^{(i)}=\sum_{i=1}^{p}c^{(i)}+c^{(p+1)}\geq\frac{m^{(p)}}{2}+c^{(p+1)}\geq\frac{m^{(p)}}{2}+n_{1}+n_{2}$
(6)

The number of edges that is added to the subgraph $\mathcal{G}^{(p)}$ when
adding the node $(p+1)$ is equal to $2n_{1}+2n_{2}=m^{(p+1)}-m^{(p)}$, hence,

$\displaystyle\frac{m^{(p)}}{2}+n_{1}+n_{2}=\frac{m^{(p)}}{2}+\frac{m^{(p+1)}-m^{(p)}}{2}=\frac{m^{(p+1)}}{2}$
(7)

We have shown that $\sum_{i=1}^{1}c^{(i)}\geq\frac{m^{(1)}}{2}$ and that if
$\sum_{i=1}^{p}c^{(i)}\geq\frac{m^{(p)}}{2}$ for a certain
$p\in\\{1,\dots,n-1\\}$, then
$\sum_{i=1}^{p+1}c^{(i)}\geq\frac{m^{(p+1)}}{2}$. Thus,
$\sum_{i=1}^{p}c^{(i)}\geq\frac{m^{(p)}}{2}$ for any $p\in\\{1,\dots,n\\}$,
especially for $p=n$ where $\mathcal{G}^{(n)}=\mathcal{G}$. By definition
$\sum_{i=1}^{n}c^{(i)}$ is the total number of edges that are cut which also
means that

$\displaystyle\sum_{i=1}^{n}c^{(i)}=\mathrm{Card}\left\\{(i,j)\in E\ |\
\left(i\in V_{1}\wedge j\in V_{2}\right)\vee\left(i\in V_{2}\wedge j\in
V_{1}\right)\\}\right)\enspace.$

∎

##  Appendix B Proof of Theorem 3.2 and Theorem 4.1

To properly derive the regret bounds, we will have to make connections between
our setting and a standard linear bandit that chooses sequentially $Tm$ arms.
For that matter, let us consider an arbitrary order on the set of edges $E$
and denote $E[i]$ the $i$-th edge according to this order with
$i\in\\{1,\dots,m\\}$. We define for all $t\in\\{1,\dots,T\\}$ and
$p\in\\{1,\dots,m\\}$ the OLS estimator

$\displaystyle\hat{\theta}_{t,p}=\mathbf{A}^{-1}_{t,p}b_{t,p}\enspace,$

where

$\displaystyle\mathbf{A}_{t,p}=\lambda\mathbf{I}_{d^{2}}+\sum_{s=1}^{t-1}\sum_{b=1}^{m}z^{E[b]}_{s}z^{E[b]\top}_{s}+\sum_{k=1}^{p}z^{E[k]}_{t}z^{E[k]\top}_{t}\enspace,$

with $\lambda$ a regularization parameter and

$\displaystyle
b_{t,p}=\sum_{s=1}^{t-1}\sum_{b=1}^{m}z^{E[b]}_{s}y^{E[b]}_{s}+\sum_{k=1}^{p}z^{E[k]}_{t}y^{E[k]}_{t}\enspace.$
(8)

We define also the confidence set

$\displaystyle
C_{t,p}(\delta)=\left\\{\theta:\|\theta-\hat{\theta}_{t,p}\|_{A_{t,p}^{-1}}\leq\sigma\sqrt{d^{2}\log\left(\frac{1+tmL^{2}/\lambda}{\delta}\right)}+\sqrt{\lambda}S\right\\}\enspace,$
(9)

where with probability $1-\delta$, we have that $\theta_{\star}\in
C_{t,p}(\delta)$ for all $t\in\\{1,\dots,T\\}$, $p\in\\{1,\dots,m\\}$ and
$\delta\in(0,1]$.

Notice that the confidence set $C_{t}(\delta)$ defined in Section 3 is exactly
the confidence set $C_{t,m}(\delta)$ defined here. The definitions of the
matrix $A_{t,m}$ and the vector $b_{t,m}$ follow the same reasoning.

###  B.1 Proof of Theorem 3.2

###### Proof.

Recall that
$(x^{(1)}_{\star},\dots,x^{(n)}_{\star})=\mathop{\mathrm{arg\,max}}_{\left(x^{(1)},\dots,x^{(n)}\right)}\sum_{(i,j)\in
E}x^{(i)\top}\mathbf{M}_{\star}x^{(j)}$ is the optimal joint arm, and we
define for each edge $(i,j)\in E$ the optimal edge arm
$z^{(i,j)}_{\star}=\operatorname*{vec}{(x^{(i)}_{\star}x^{(j)\top}_{\star})}$.

We recall that the $\alpha$-pseudo-regret is

$\displaystyle R_{\alpha}(T)$
$\displaystyle\triangleq\sum_{t=1}^{T}\sum_{(i,j)\in E}\alpha\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$ (10)
$\displaystyle=R(T)-\sum_{t=1}^{T}\sum_{(i,j)\in E}(1-\alpha)\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle\enspace,$ (11)

where the pseudo-regret $R(T)$ is defined by

$\displaystyle R(T)=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\enspace.$

Let us borrow the notion of _Critical Covariance Inequality_ introduced in
(Chan et al., 2021), that is for a given round $t\in\\{1,\dots,T\\}$ and
$p\in\\{1,\dots,m\\}$, the expected covariance matrix $\mathbf{A}_{t,p}$
satisfies the critical covariance inequality if

$\displaystyle\mathbf{A}_{t-1,m}\preccurlyeq\mathbf{A}_{t,p}\preccurlyeq
2\mathbf{A}_{t-1,m}\enspace.$ (12)

Let us now define the event $D_{t}$ as the event where at a given round $t$,
for all $p\in\\{1,\dots,m\\}$, $\mathbf{A}_{t,p}$ satisfies the critical
covariance inequality (CCI).

We can write the pseudo-regret as follows:

$\displaystyle R(T)$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\left\langle
z^{(i,j)}_{t},\theta_{\star}\right\rangle+\mathds{1}[D_{t}^{c}]\sum_{(i,j)\in
E}\langle z^{(i,j)}_{\star},\theta_{\star}\rangle-\left\langle
z^{(i,j)}_{t},\theta_{\star}\right\rangle$
$\displaystyle\leq\underbrace{\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\langle z^{(i,j)}_{\star},\theta_{\star}\rangle-\left\langle
z^{(i,j)}_{t},\theta_{\star}\right\rangle}_{(a)}+\underbrace{LSm\sum_{t=1}^{T}\mathds{1}[D_{t}^{c}]}_{(b)}\enspace.$

We know that the approximation Max-CUT algorithm returns two subsets of nodes
$V_{1}$ and $V_{2}$ such that there are at least $m/2$ edges between $V_{1}$
and $V_{2}$, and to be more precise: at least $m/4$ edges from $V_{1}$ to
$V_{2}$ and at least $m/4$ edges from $V_{2}$ to $V_{1}$. Hence at each time
$t$, if all the nodes of $V_{1}$ pull the node-arm $x_{t}$ and all the nodes
of $V_{2}$ pull the node-arm $x_{t}^{\prime}$, we can derive the term $(a)$ as
follows:

$\displaystyle(a)$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\mathds{1}\left[i\in V_{1}\wedge j\in
V_{2}\right]\langle z^{(i,j)}_{t},\theta_{\star}\rangle$ $\displaystyle\hskip
123.76965pt-\mathds{1}\left[i\in V_{2}\wedge j\in V_{1}\right]\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$ $\displaystyle\hskip
123.76965pt-\mathds{1}\left[i\in V_{1}\wedge j\in V_{1}\right]\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$ $\displaystyle\hskip
123.76965pt-\mathds{1}\left[i\in V_{2}\wedge j\in V_{2}\right]\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\enspace.$

Notice that $\sum_{(i,j)\in E}z^{(i,j)}_{\star}=\sum_{(i,j)\in
E}\frac{1}{m}\sum_{(k,l)\in E}z^{(k,l)}_{\star}$, so one has

$\displaystyle(a)$
$\displaystyle=\underbrace{\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[i\in V_{1}\wedge j\in
V_{2}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\right)}_{(a_{1})}$ $\displaystyle\ \ \ \
+\underbrace{\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[i\in V_{2}\wedge j\in
V_{1}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\right)}_{(a_{2})}$ $\displaystyle\ \ \ \
+\underbrace{\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[i\in V_{1}\wedge j\in
V_{1}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\right)}_{(a_{3})}$ $\displaystyle\ \ \ \
+\underbrace{\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[i\in V_{2}\wedge j\in
V_{2}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\right)}_{(a_{4})}\enspace.$

Let us analyse the first term:

$\displaystyle(a_{1})$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in
N_{i}\\\ j>i\end{subarray}}\mathds{1}\left[i\in V_{1}\wedge j\in
V_{2}\right]\left\langle\frac{2}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star}-\left(z^{(i,j)}_{t}+z^{(j,i)}_{t}\right),\theta_{\star}\right\rangle\enspace.$
(13)

By defining
$(x_{\star},x_{\star}^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\theta_{\star}\rangle$, and noticing that in
the case where a node $i$ is in $V_{1}$ and a neighbouring node $j$ in is
$V_{2}$, then $z^{(i,j)}_{t}=z_{x_{t}x_{t}^{\prime}}$, we have,

$\displaystyle\frac{2}{m}\sum_{(k,l)\in E}\left\langle
z^{(k,l)}_{\star},\theta_{\star}\right\rangle$
$\displaystyle=\frac{2}{m}\sum_{k=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{k}\\\
j>k\end{subarray}}\left\langle
z^{(k,l)}_{\star}+z^{(l,k)}_{\star},\theta_{\star}\right\rangle$
$\displaystyle\leq\frac{2}{m}\sum_{k=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{k}\\\
j>k\end{subarray}}\left\langle
z_{x_{\star}x_{\star}^{\prime}}+z_{x_{\star}^{\prime}x_{\star}},\theta_{\star}\right\rangle$
$\displaystyle=\langle
z_{x_{\star}x_{\star}^{\prime}}+z_{x_{\star}^{\prime}x_{\star}},\theta_{\star}\rangle$
$\displaystyle\leq\langle
z_{x_{t}x_{t}^{\prime}}+z_{x_{t}^{\prime}x_{t}},\tilde{\theta}_{t-1,m}\rangle\
\ \ \ \ \ \text{w.p}\ \ \ 1-\delta$ $\displaystyle=\langle
z^{(i,j)}_{t}+z^{(j,i)}_{t},\tilde{\theta}_{t-1,m}\rangle\enspace.$

Plugging this last inequality in (13) yields, with probability $1-\delta$,

$\displaystyle(a_{1})$
$\displaystyle\leq\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in
N_{i}\\\ j>i\end{subarray}}\mathds{1}\left[i\in V_{1}\wedge j\in
V_{2}\right]\left\langle
z^{(i,j)}_{t}+z^{(j,i)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\right\rangle$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[i\in V_{1}\wedge j\in V_{2}\right]\left\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\right\rangle\enspace.$

We define, as in Algorithm 1,
$\mathds{1}\left[z^{(i,j)}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\triangleq\mathds{1}\left[i\in
V_{1}\wedge j\in V_{2}\right]$. Then, one has, with probability $1-\delta$,

$\displaystyle(a_{1})$
$\displaystyle\leq\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[z^{(i,j)}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\left\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\right\rangle$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{k=1}^{m}\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\left\langle
z^{E[k]}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\right\rangle$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{k=1}^{m}\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\left\langle
z^{E[k]}_{t},\tilde{\theta}_{t-1,m}-\hat{\theta}_{t-1,m}\right\rangle+\left\langle
z^{E[k]}_{t},\hat{\theta}_{t-1,m}-\theta_{\star}\right\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{k=1}^{m}\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\|\tilde{\theta}_{t-1,m}-\hat{\theta}_{t-1,m}\|_{\mathbf{A}_{t,k-1}}$
$\displaystyle\hskip
71.13188pt+\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\|\hat{\theta}_{t-1,m}-\theta_{\star}\|_{\mathbf{A}_{t,k-1}}$
$\displaystyle\leq\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{k=1}^{m}\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\sqrt{2}\|\tilde{\theta}_{t-1,m}-\hat{\theta}_{t-1,m}\|_{\mathbf{A}_{t-1,m}}$
(14) $\displaystyle\hskip
71.13188pt+\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\sqrt{2}\|\hat{\theta}_{t-1,m}-\theta_{\star}\|_{\mathbf{A}_{t-1,m}}$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{k=1}^{m}\mathds{1}\left[z^{E[k]}_{t}=z_{x_{t}x_{t}^{\prime}}\right]2\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}$
(15)
$\displaystyle\leq\sum_{t=1}^{T}\sum_{k=1}^{m}2\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\enspace,$
(16)

with
$\sqrt{\beta_{t}(\delta)}\leq\sigma\sqrt{d^{2}\log\left(\frac{1+tmL^{2}/\lambda}{\delta}\right)}+\sqrt{\lambda}S$
and where (14) uses the critical covariance inequality (12), (15) comes from
the definition of the confidence set $C_{t-1,m}(\delta)$ (9) and (16) upper
bounds the indicator functions by 1.

Using a similar reasoning, we obtain the same bound for $(a_{2})$:

$\displaystyle(a_{2})$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{k=1}^{m}2\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\enspace.$
(17)

Let us bound the terms $(a_{3})$ and $(a_{4})$.

$\displaystyle(a_{3})=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[z^{(i,j)}_{t}=z_{x_{t}x_{t}}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\right)$ (18)

For all $x\in\mathcal{X}$, let $\gamma_{x}$ be the following ratio

$\displaystyle\gamma_{x}=\frac{\langle
z_{xx},\theta_{\star}\rangle}{\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle}\enspace,$ (19)

and let $\gamma$ be the worst ratio

$\displaystyle\gamma=\min_{x\in\mathcal{X}}\frac{\langle
z_{xx},\theta_{\star}\rangle}{\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle}\enspace.$ (20)

We have

$\displaystyle(a_{3})$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[z^{(i,j)}_{t}=z_{x_{t}x_{t}}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\gamma_{x_{t}}\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle\right)$
$\displaystyle\leq\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[z^{(i,j)}_{t}=z_{x_{t}x_{t}}\right]\left(\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle-\gamma\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle\right)$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\mathds{1}\left[z^{(i,j)}_{t}=z_{x_{t}x_{t}}\right](1-\gamma)\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle$ $\displaystyle\leq
T\frac{m}{4}(1-\gamma)\left\langle\frac{1}{m}\sum_{(k,l)\in
E}z^{(k,l)}_{\star},\theta_{\star}\right\rangle$ (21)
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{1}{4}(1-\gamma)\left\langle
z^{(i,j)}_{\star},\theta_{\star}\right\rangle\enspace,$

where (21) comes from the fact that there is at most $m/4$ edges that goes
from node in $V_{1}$ to other nodes in $V_{1}$ and that $\mathds{1}[D_{t}]\leq
1$ for all $t$.

The derivation of this bound for $(a_{3})$ gives the same one for $(a_{4})$

$\displaystyle(a_{4})$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{1}{4}(1-\gamma)\left\langle
z^{(i,j)}_{\star},\theta_{\star}\right\rangle\enspace.$ (22)

By rewriting $(a)$, we have :

$\displaystyle(a)$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{k=1}^{m}4\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}+\frac{1}{2}(1-\gamma)\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle\enspace.$

In (Chan et al., 2021), they bounded the term $(b)$ as follows

$\displaystyle LSm\sum_{t=1}^{T}\mathds{1}[D_{t}^{c}]\leq LSm\left\lceil
d^{2}\log_{2}\left(\frac{TmL^{2}/\lambda}{\delta}\right)\right\rceil\enspace.$
(23)

We thus have the regret bounded by

$\displaystyle R(T)\leq$
$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{m}4\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}+\frac{1}{2}(1-\gamma)\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle+LSm\left\lceil
d^{2}\log_{2}\left(\frac{TmL^{2}/\lambda}{\delta}\right)\right\rceil\enspace,$

which gives us

$\displaystyle
R_{\frac{1+\gamma}{2}}(T)\leq\sum_{t=1}^{T}\sum_{k=1}^{m}4\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}+LSm\left\lceil
d^{2}\log_{2}\left(\frac{TmL^{2}/\lambda}{\delta}\right)\right\rceil\enspace.$

Let us bound the first term with the double sum as it is done in (Abbasi-
Yadkori et al., 2011; Chan et al., 2021):

$\displaystyle\sum_{t=1}^{T}\sum_{k=1}^{m}4\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{k=1}^{m}\min\left(2LS,4\sqrt{2\beta_{t}(\delta)}\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\right)$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{k=1}^{m}4\sqrt{2\beta_{t}(\delta)}\min\left(LS,\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}\right)$
$\displaystyle\leq\sqrt{Tm\times
32\beta_{T}(\delta)\sum_{t=1}^{T}\sum_{k=1}^{m}\min\left((LS)^{2},\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}^{2}\right)}$
$\displaystyle\leq\sqrt{32Tm\beta_{T}(\delta)\sum_{t=1}^{T}\sum_{k=1}^{m}\max\left(2,(LS)^{2}\right)\log\left(1+\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}^{2}\right)}$
(24)
$\displaystyle=\sqrt{32Tm\beta_{T}(\delta)\max\left(2,(LS)^{2}\right)\sum_{t=1}^{T}\sum_{k=1}^{m}\log\left(1+\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}^{2}\right)}$
$\displaystyle\leq\sqrt{32Tm\beta_{T}(\delta)\max\left(2,(LS)^{2}\right)d^{2}\log\left(1+\frac{TmL^{2}/\lambda}{d^{2}}\right)}$
(25)
$\displaystyle\leq\sqrt{32Tmd^{2}\max\left(2,(LS)^{2}\right)\log\left(1+\frac{TmL^{2}/\lambda}{d^{2}}\right)}\left(\sigma\sqrt{d^{2}\log\left(\frac{1+TmL^{2}/\lambda}{\delta}\right)}+\sqrt{\lambda}S\right)$

where (24) uses the fact that for all $a,x\geq 0$,
$\min(a,x)\leq\max(2,a)\log(1+x)$, (25) uses the fact that
$\sum_{t=1}^{T}\sum_{k=1}^{m}\log\left(1+\|z^{E[k]}_{t}\|_{\mathbf{A}_{t,k-1}^{-1}}^{2}\right)\leq
d^{2}\log\left(1+\frac{TmL^{2}/\lambda}{d^{2}}\right)$ from Lemma 19.4 in
Lattimore and Szepesvári (2018).

The final bound for the $\frac{1+\gamma}{2}$-regret is

$\displaystyle R_{\frac{1+\gamma}{2}}(T)\leq$
$\displaystyle\sqrt{32Tmd^{2}\max\left(2,(LS)^{2}\right)\log\left(1+\frac{TmL^{2}/\lambda}{d^{2}}\right)}\left(\sigma\sqrt{d^{2}\log\left(\frac{1+TmL^{2}/\lambda}{\delta}\right)}+\sqrt{\lambda}S\right)$
$\displaystyle+LSm\left\lceil
d^{2}\log_{2}\left(\frac{TmL^{2}/\lambda}{\delta}\right)\right\rceil$

∎

###  B.2 Proof of Theorem 4.1

###### Proof.

For the sake of completeness in the proof we recall that we defined the
couples $(x_{\star},x_{\star}^{\prime})$ and
$(\tilde{x}_{\star},\tilde{x}_{\star}^{\prime})$ and the quantity $\Delta$ as
follows:

$\displaystyle(x_{\star},x_{\star}^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}^{2}}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\theta_{\star}\rangle$
$\displaystyle(\tilde{x}_{\star},\tilde{x}_{\star}^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})\in\mathcal{X}}\langle
m_{1\rightarrow 2}\cdot z_{xx^{\prime}}+m_{2\rightarrow 1}\cdot
z_{x^{\prime}x}+m_{1}\cdot z_{xx}+m_{2}\cdot
z_{x^{\prime}x^{\prime}},\theta_{\star}\rangle\enspace.$

and

$\displaystyle\Delta=$ $\displaystyle\,\langle m_{1\rightarrow
2}\left(z_{\tilde{x}_{\star}\tilde{x}_{\star}^{\prime}}-z_{x_{\star}x_{\star}^{\prime}}\right)+m_{2\rightarrow
1}\left(z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}}-z_{x_{\star}^{\prime}x_{\star}}\right)$
$\displaystyle+m_{1}\left(z_{\tilde{x}_{\star}\tilde{x}_{\star}}-z_{x_{\star}x_{\star}}\right)+m_{2}\left(z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}^{\prime}}-z_{x_{\star}^{\prime}x_{\star}^{\prime}}\right),\theta_{\star}\rangle\enspace.$

And we recall that in Algorithm 3, the tuple
$(x_{t},x_{t}^{\prime},\tilde{\theta}_{t-1,m})$ is obtained as follows:

$\displaystyle\left(x_{t},x_{t}^{\prime},\tilde{\theta}_{t-1,m}\right)=\mathop{\mathrm{arg\,max}}_{\left(x,x^{\prime},\theta\right)\in\mathcal{X}^{2}\times
C_{t-1}}\left\langle m_{1\rightarrow 2}\cdot z_{xx^{\prime}}+m_{2\rightarrow
1}\cdot z_{x^{\prime}x}+m_{1}\cdot z_{xx}+m_{2}\cdot
z_{x^{\prime}x^{\prime}},\theta\right\rangle$

We can write the regret $R(T)$ as in the proof of Theorem 3.2:

$\displaystyle R(T)$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\left\langle
z^{(i,j)}_{t},\theta_{\star}\right\rangle+\mathds{1}[D_{t}^{c}]\sum_{(i,j)\in
E}\langle z^{(i,j)}_{\star},\theta_{\star}\rangle-\left\langle
z^{(i,j)}_{t},\theta_{\star}\right\rangle$
$\displaystyle\leq\underbrace{\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in
E}\langle z^{(i,j)}_{\star},\theta_{\star}\rangle-\left\langle
z^{(i,j)}_{t},\theta_{\star}\right\rangle}_{(a)}+\underbrace{LSm\sum_{t=1}^{T}\mathds{1}[D_{t}^{c}]}_{(b)}$

Here, $(b)$ doesn’t change, we thus only focus on deriving $(a)$.

$\displaystyle(a)$
$\displaystyle=\sum_{t=1}^{T}\mathds{1}[D_{t}]\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\langle
z^{(i,j)}_{t},\theta_{\star}\rangle\hskip 56.9055pt\text{(where
$\mathds{1}[D_{t}]\leq 1$)}$
$\displaystyle=\underbrace{\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1\rightarrow 2}+m_{2\rightarrow 1}}{m}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle}_{(a_{1})}+\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$

We have

$\displaystyle(a_{1})$ $\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{2m_{1\rightarrow 2}}{m}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2m_{1\rightarrow 2}}{m}\langle
z^{(i,j)}_{\star}+z^{(j,i)}_{\star},\theta_{\star}\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2m_{1\rightarrow 2}}{m}\langle
z_{x_{\star}x_{\star}^{\prime}}+z_{x_{\star}^{\prime}x_{\star}},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2}{m}\langle m_{1\rightarrow 2}\cdot
z_{x_{\star}x_{\star}^{\prime}}+m_{2\rightarrow 1}\cdot
z_{x_{\star}^{\prime}x_{\star}},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2}{m}\langle m_{1\rightarrow 2}\cdot
z_{x_{\star}x_{\star}^{\prime}}+m_{2\rightarrow 1}\cdot
z_{x_{\star}^{\prime}x_{\star}}+m_{1}\cdot z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle\ \ \ \ \
-\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2}{m}\langle m_{1}\cdot
z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2}{m}\langle m_{1\rightarrow 2}\cdot
z_{\tilde{x}_{\star}\tilde{x}_{\star}^{\prime}}+m_{2\rightarrow 1}\cdot
z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}}+m_{1}\cdot
z_{\tilde{x}_{\star}\tilde{x}_{\star}}+m_{2}\cdot
z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}^{\prime}},\theta_{\star}\rangle-\frac{2}{m}\Delta$
$\displaystyle\ \ \ \ \
-\sum_{t=1}^{T}\sum_{i=1}^{n}\sum_{\begin{subarray}{c}j\in\mathcal{N}_{i}\\\
j>i\end{subarray}}\frac{2}{m}\langle m_{1}\cdot
z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\langle m_{1\rightarrow 2}\cdot
z_{\tilde{x}_{\star}\tilde{x}_{\star}^{\prime}}+m_{2\rightarrow 1}\cdot
z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}}+m_{1}\cdot
z_{\tilde{x}_{\star}\tilde{x}_{\star}}+m_{2}\cdot
z_{\tilde{x}_{\star}^{\prime}\tilde{x}_{\star}^{\prime}},\theta_{\star}\rangle-\Delta$
$\displaystyle\ \ \ \ \ -\sum_{t=1}^{T}\langle m_{1}\cdot
z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\left\langle m_{1\rightarrow 2}\cdot
z_{x_{t}x_{t}^{\prime}}+m_{2\rightarrow 1}\cdot
z_{x_{t}^{\prime}x_{t}}+m_{1}\cdot z_{x_{t}x_{t}}+m_{2}\cdot
z_{x_{t}^{\prime}x_{t}^{\prime}},\tilde{\theta}_{t-1,m}\right\rangle-\Delta\hskip
28.45274pt\text{w.p}\ \ \ 1-\delta$ $\displaystyle\ \ \ \ \
-\sum_{t=1}^{T}\langle m_{1}\cdot z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}\rangle-\sum_{t=1}^{T}\Delta-\sum_{t=1}^{T}\langle
m_{1}\cdot z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$

By plugging the last upper bound in $(a)$ and with probability $1-\delta$, we
have,

$\displaystyle(a)$ $\displaystyle\leq\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}\rangle-\sum_{t=1}^{T}\Delta-\sum_{t=1}^{T}\langle
m_{1}\cdot z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle\ \ \ \ \ +\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle-\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle-\sum_{t=1}^{T}\Delta-\sum_{t=1}^{T}\langle
m_{1}\cdot z_{x_{\star}x_{\star}}+m_{2}\cdot
z_{x_{\star}^{\prime}x_{\star}^{\prime}},\theta_{\star}\rangle$
$\displaystyle\ \ \ \ \ +\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}\langle z^{(i,j)}_{\star},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle-\sum_{t=1}^{T}\Delta-\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}}{m}\gamma_{x_{\star}}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle+\frac{m_{2}}{m}\gamma_{x_{\star}^{\prime}}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle$ $\displaystyle\ \ \ \ \
+\sum_{t=1}^{T}\sum_{(i,j)\in E}\frac{m_{1}+m_{2}}{m}\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle-\sum_{t=1}^{T}\Delta-\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}\gamma\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle+\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}\langle z^{(i,j)}_{\star},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle-\sum_{t=1}^{T}\Delta+\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}(1-\gamma)\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle-\sum_{t=1}^{T}\sum_{(i,j)\in
E}\epsilon\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle+\sum_{t=1}^{T}\sum_{(i,j)\in
E}\frac{m_{1}+m_{2}}{m}(1-\gamma)\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle$
$\displaystyle=\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle+\sum_{t=1}^{T}\sum_{(i,j)\in
E}\left[\frac{m_{1}+m_{2}}{m}(1-\gamma)-\epsilon\right]\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle$

By plugging $(a)$ in the regret and with probability $1-\delta$, we have,

$\displaystyle R(T)\leq\sum_{t=1}^{T}\sum_{(i,j)\in E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle+\sum_{t=1}^{T}\sum_{(i,j)\in
E}\left[\frac{m_{1}+m_{2}}{m}(1-\gamma)-\epsilon\right]\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle+LSm\sum_{t=1}^{T}\mathds{1}[D_{t}^{c}]$

which gives,

$\displaystyle R(T)-\sum_{t=1}^{T}\sum_{(i,j)\in
E}\left[\frac{m_{1}+m_{2}}{m}(1-\gamma)-\epsilon\right]\langle
z^{(i,j)}_{\star},\theta_{\star}\rangle\leq\sum_{t=1}^{T}\sum_{(i,j)\in
E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle+LSm\sum_{t=1}^{T}\mathds{1}[D_{t}^{c}]$
$\displaystyle
R_{1-\left[\frac{m_{1}+m_{2}}{m}(1-\gamma)-\epsilon\right]}(T)\leq\sum_{t=1}^{T}\sum_{(i,j)\in
E}\langle
z^{(i,j)}_{t},\tilde{\theta}_{t-1,m}-\theta_{\star}\rangle+LSm\sum_{t=1}^{T}\mathds{1}[D_{t}^{c}]$

The upper bound of the right hand term follows exactly what we have already
done for Theorem 3.2 by applying the upper bounds (16) and (23) ∎

##  Appendix C Additional information on the experiments

###  C.1 Table 1

The number of nodes in each graph is equal to $100$. The random graph
corresponds to a graph where for two nodes $i$ and $j$ in $V$, the probability
that $(i,j)$ and $(j,i)$ is in $E$ is equal to $0.6$. The results for the
random graph are averaged over 100 draws. The matching graph represents the
graph where each node $i\in V$ has only one neighbour:
$\mathrm{Card}(\mathcal{N}_{i})=1$.

###  C.2 Figure 2

The graph used in this experiment is a complete graph of $10$ nodes. The arm
set $\mathcal{X}=\\{e_{1},\dots,e_{d}\\}$ which gives
$\mathcal{Z}=\\{e_{1},\dots,e_{d^{2}}\\}$. The matrix $\mathbf{M}_{\star}$ is
randomly initialized such that all elements of the matrix are drawn i.i.d.
from a standard normal distribution, and then we take the absolute value of
each of these elements to ensure that the matrix only contains positive
numbers. We plotted the results by varying $\zeta$ from $0$ to $1$ with a step
of $0.01$. We conducted the experiment on 100 different matrices
$\mathbf{M}_{\star}$ randomly initialized as explained above and plotted the
average value of the obtained $\gamma$, $\epsilon$, $\alpha_{1}$ and
$\alpha_{2}$.

###  C.3 Figure 2

For the last experiment, we used a complete graph of $5$ nodes. The arm set
$\mathcal{X}=\\{e_{1},\dots,e_{d}\\}$ which gives
$\mathcal{Z}=\\{e_{1},\dots,e_{d^{2}}\\}$. The matrix $\mathbf{M}_{\star}$ is
randomly initialized as explained in the previous experiment. We fixed
$\zeta=0$ and the horizon $T=20000$. We ran the experiment 10 times and
plotted the average values (shaded curve) and the moving average curve with a
window of 100 steps for more clarity.

The Explore-Then-Commit algorithm has an exploration phase of $T/3$ rounds and
then exploits by pulling the couple
$(x_{t},x_{t}^{\prime})=\mathop{\mathrm{arg\,max}}_{(x,x^{\prime})}\langle
z_{xx^{\prime}}+z_{x^{\prime}x},\hat{\theta}_{t}\rangle$. Note that we set the
exploration phase to $T/3$ because most of the time, it was sufficient for the
learner to have the estimated optimal pair $(x_{t},x_{t}^{\prime})$ equal to
the real optimal pair $(x_{\star},x_{\star}^{\prime})$.

Machine used for all the experiments : Macbook Pro, Apple M1 chip, 8-core CPU

The code is available here.