Statistical and Computational Trade-off in Multi-Agent Multi-Armed Bandits
Authors: Filippo Vannella
Alexandre Proutiere
Jaeseong Jeong
Venue: NeurIPS 2023 poster (2023)
Keywords: Multi-Agent Multi-Armed Bandits
Multi-Armed Bandits
Regret Minimization

Abstract: We study the problem of regret minimization in Multi-Agent Multi-Armed Bandits (MAMABs) where the rewards are defined through a factor graph. We derive an instance-specific regret lower bound and characterize the minimal expected number of times each global action should be explored. Unfortunately, this bound and the corresponding optimal exploration process are obtained by solving a combinatorial optimization problem with a set of variables and constraints exponentially growing with the number of agents. We approximate the regret lower bound problem via Mean Field techniques to reduce the number of variables and constraints. By tuning the latter, we explore the trade-off between achievable regret and complexity. We devise Efficient Sampling for MAMAB (ESM), an algorithm whose regret asymptotically matches the corresponding approximated lower bound. We assess the regret and computational complexity of ESM numerically, using both synthetic and real-world experiments in radio communications networks.

Statistical and Computational Trade-off in Multi-Agent Multi-Armed Bandits
Filippo Vannella KTH and Ericsson Research
Alexandre Protiuere KTH Stockholm, Sweden aleprockth.se
Stockholm, Sweden Bannellacktan
Jacseong Jeong Ericsson Research Stockholm, Sweden
aeseong. . wwwoooonnneongrrreeee jeong@ericsson.com com
Abstract
We study the problem of regret minimization in Multi-Agent Multi-Armed Bandits (MAMABs) where the rewards are defined through factor graph. We derive an instance-specific regret lower bound and characterize the minimal expected number of times each glohal action should be explored. This bound and the corresponding optimal exploration process are obtained by solving combinatorial optimization problem whose set of variables and constraints exponentially grow with the number agents, and cannot be exploited in the design of efficient algorithms. Inspired by Mean Field approximation techniques used in graphical models, provide simple upper bounds of the regret lower bound. The corresponding optimization problems have reduced number of variables and constraints. By tuning the latter, may explore the trade-off between the achievable regret and the complexity of computing the corresponding exploration process. We devise Efficient Sampling for MAMAB (ESM), an algorithm whose regret asymptotically matches the approximated lower bounds. The regret and computational complexity of ESM assessed numerically, using both synthetic and real- world experiments in radio communications networks.
Introduction
The stochastic Multi-Agent Multi-Armed Bandits (MAMABs) [35] 2 3] is a combinatorial sequential decision-mi docision-making problem that generalizes the classical stochastic MAB problem by assuming that (i) a global action is defined by actions individually selected by a set of agents, and (ii) the reward function is defined through factor graph, which defines dependeeessssss between agents. This reward structure arises naturally in applications where agents interact in a graph with the need to coordinate towards common goal. MAMABs can model wide range of real-world problems, from wind farm control 2 (7 to radio communication networks parameters optimization (see Fig. I.
Despite the wide spectrum of their potential applications, MAMABs are extremely hard to solve, even when the reward function is known. The main challenge stems from the combinatorial structure of the action set (there K possible global actions, where N is the number of agents and K is the number of actions per agent). This issue is exacerbated the learning setting where the reward function has to be inferred. In this work, study the regret minimization problem in MAMABs, and more specifically, the trade-off between statistical efficiency (the learner aims at achieving low regret), and computational efficiency (she will typically have to solve combinatorial optimization problems over the set of possible global actions while learning).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Contributions. We present statistically and computationally efficient algorithms for MAMABs. Our algorithms enjoy (in the worst case) regret guarantees scaling as pk pk log(T), where K is the number of actions per agent, / and d are the number of factors and the maximal degree of the graph defining the reward function. This scaling illustrates the gains one may achieve by exploiting the factor graph structure: without leveraging it, the regret would scale as KN log(T). Our algorithms have controllable computational complexity and can be applied in large-scale MAMABs. More precisely, our contributions are follows.
1) Regret lower bound. We derive a regret lower bound satisfied by any algorithm. The bound is defined through convex program (the lower bound problem), whose solution provides an optimal exploration strategy. Unfortunately, because of the factored reward structure, this optimization problem contains an exponential number of variables and constraints, and is hard to use in practice.
2) Approximations of the lower bound problem. We devise approximations of the lower bound problem by combining variable and constraint reduction techniques inspired by methods in the probabilistic graphical model literature [39] 20 To reduce the number of variables, we propose (i) locally tree-like approximation, a tight relaxation for MAMAB instances described by acyclic factor graphs, and (ii) Mean Field (MF) approximation for general graphs. The MF approximation yields an upper bound of the regret lower bound, scaling as pkd (T'( (where T is the time horizon).
Both approximations yield lower bound problems with a polynomial number of variables and exponential number of constraints (in N). To reduce the number of constraints, we propose technique that leverages an ordering of the m smallest gaps and Factored Constraint Reduction (FCR) method to represent the exponentially many constraints in compact manner. The corresponding optimization problems have a reduced number of variables and constraints. By tuning the latter, we may explore the trade-off between the achievable regret and the complexity of computing the corresponding exploration process.
3) The ESM algoritium. Based on this approximation, we devise Efficient Sampling for MAMABs (ESM), an algorithm whose regret provably matches our approximated regret lower bound. The algorithm trades off statistical and computational complexity by performing exploration as prescribed by the solution of the approximated lower bound problem. We test the performance of ESM numerically on both synthetic experiments and learn to coordinate the antenna tilts in radio communication network. In both sets of experiments, ESM can solve problems with a large number of global actions in a statistical and computationally efficient manner.
Related Work
Our work belongs to the framework of structured regret minimization in MABs, which encompasses a large variety of reward structures such as linear [2T), unimodal (9). Lipschitz (T], etc. For general structured bandits, [8) propose Optimal Sampling for Structured Bandits (OSSB), statistically optimal algorithm, i.c., matching the regret lower bound. The algorithm is computationally inefficient when applied to the MAMABs combinatorial structure. Our algorithm is inspired by OSSB, but relies on approximated lower bound problems to trade-off statistical and computational complexity.
A few studies investigate MAMABs with the same factored reward structure as ours [5] 37 These works focus on devising algorithms with regret guarantees using methods based on, e.g., Upper Confi-
dence Bound (UCB) [35] 2 or Thompson Sampling (TS) (37). For example, Stranders et al. 35 pro- pose HEIST, an UCB-type algorithm whose asymptotic regret scales as O KNN Amax/ /min log(T)) (T))
where Amin and Amax are the minimal and maximal gaps, respectively. The MAUCE algorithm from Bargiacchi et al., (2) improves over (35) yielding asymptotic regret O(p² Kdd A2 / A log(T)). Our worst approximation improves of a factor Amax w.r.t. this bound, quantity that typically scales with pkd (see App. M).
There is large body of work 24 10 12 13 38 investigating regret minimization in the (linear) combinatorial semi-bandis feedback setting. Although our model can be interpreted as a particular instance of this setting (see App. E for details), the MAMAB combinatorial structure has never been explicitly considered this context. The closest related work is [12), in which the authors study a regret lower bound problem with an exponentially large number of variables and constraints. They leverage [12, Assumption 6) to compactly represent the lower bound optimization problem and propose a gradient- baadieent-baedddddeee procedure to solve it in polynomial time. Unfortunately, for MAMABs, the

---

above-mentione assumption only holds for rewards described by acyclic factor graphs (see App. Mp. We propose computationally efficient approximations valid for any factor graph while retaining statistical tightness in the case of acyclic factor graphs.
3 Problem Setting
We consider the generic MAMAB model with factored structure introduced in 2 The model is defined by the tuple (S, A r), where:
1. S = [ _ NJ is a set of N agents;
2. - X=E a of global actions, which is the Cartesian product over i of the set A; of actions available to the agent i. We assume w.l.o.g. that |A|| K, for all i [M] and define A - |A| KN;
3. r the reward function mapping the global action to the collected reward.
Rewards and their factor-graph representation. We model the collected rewards. There are possibly overlapping groups of agents (Se)ee(p). with S. S S and [Se] Ne- The local reward generated by group e depends on group actions a A (a;)ies, E Ae - Xies A, only. More precisely, each time a, is selected, the collected local rewards are i.i.d. copies of random variable re(a.) ~ (O.()a))) 1/2). Rewards collected in various groups are independent. The global reward for action is then r(a)= Σee[s] (a.), random variable with expectation ((a) Eeelp) (ax).
The number of possible group actions in group e is A. - Ael KN,, and we define Ā EeSte) A..
The reward function can be represented using factor graph (39] Factor graphs are bipartite graphs with two types of node: N action nodes, one for each agent, and p factor nodes, one for each group. An edge between factor and an agent i exists if the action a, selected by the agent is an input re: E S., Fig. shows an example of a factor graph modeling interference in a radio communication network.
F1
Figure Factor graph in a radio communication network. An agent (represented by a circle) corresponds to base-station (BS) whose transmissions cover cell. The possible actions at BS may correspond to different transmission power levels and antenna tilts (the physical angle of the antennas). The local rewards correspond to the throughput (in bit/s) achieved in given cell, and hence each cell is associated with a factor (represented by a square). The throughput in given cell depends the action of the corresponding BS but also those of neighboring BSs through interference. In the factor graph, each BS or agent has hence an edge to factors or cells it interferes.
Sequential decision process. The decision maker sequentially selects global actions based on the history of previous observations and receives the various groups. Specifically, in each round t 2 1, the decision maker selects global action a; (at.1.... ar,N) and observes the local rewards r; (rr.1... .......... Tt.p) from each group. The global action a++1 is selected based on the history of observations H. (a., Te) This type of interaction is known as bani- feedback.
of samples of the local rewards associated to
Regret minimization. The goal is devise an algorithm (a1)22 i.e., a sequence of global actions o, E A selected in each round 2 1, that minimizes the regret up to time T 2 1, defined as
Σ Maab) a(a))
RdT (T)
3

---

where ag E arg m ((a) denotes the best global action. Throughout the paper. we assume that ap unique and we use a" and ag interchangeably. We define the gap of sub-optimal global action by (a) = 0(a*)(())))))))){()))))) ((a).
4 Regret Lower Bound
To derive instance- -ppecicf--eeiiccccc regret lower bounds, restrict attention the class of uniformly good algorithms: An algorithm π is uniformly good if for any 8, Va > O, we have that R (T) = o(T").
Theorem 4.1. The regret of any uniformly good algorithm satisfies for any 8, lim inf (T)
2 Cg.
log(T)
T-500
where Co is the value of the following convex optimization problem
-1
min VER 20
E Eva((a
s.t.
E
E
Ub
S S((a)? Va A.
(I)
eElp):a, #0;
The proof of this result leverages classical change-of-measung arguments 25 (see App. A. for
details). If v- denotes the solution of the lower bound optimization problem, then for 7 ag. 2 log((') can be interpreted as the asymptotic expected number of times the sub-optimal action explored under a uniformly good algorithm minimizing regret. We conclude this section by reformulating I
using group variables e. Introduce the marginal cone:
V
ú UE 3u Ro Ve E [p], a. E Aes Te,ac
Σ
Ubs
The set Y contains group variables i = (ūe)eE(o) where i. = (Be,aa)aaa EAc Lemma 4.2. For any O, Cj is the value of the following convex optimization problem
min REV
Σ E.
(Oc(a)) (oc((a))-aaa)) (a())) s.t.
Σ eElplacetat
Ve < Aia?, Va A..
(2)
Again, the solution of (2) ö* then for any E [p] and ae Acs "e lTg(T) can be interpreted as the asymptotic expected number of times the group action ag is selected under an optimal algorithm when it explores, i.c., when the global action + ag.
5 Lower Bound Approximations
As suggested above, if we are able to solve T and hence obtain v², , the latter specifies the optimal exploration process. From there, we could devise algorithm with minimal regret (8). Unfortunately. solving I is an extremely hard task, even for relatively small problems. Indeed, the problem has KN variables and KN constraints, and using general-purpost solvers, e.g., based based on the interior- point method, would require poly(K" log(1/s) floating-point operations (33). To circumvent this difficulty, we present approximations the lower bound problem with a reduced number of variables and constraints. We will then leverage these approximations to design efficient algorithms.
5.1 Variable reduction
To reduce the number of variables, we apply approximation techniques inspired by methods in the probabilistic graphical model literature (39). In Sec. [5.II] we first propose a locally tree-like reduction, yielding an optimization problem whose value C exactly matches the true lower bound O for MAMABs with acyclic factor graphs (see App. A a formal definition and examples). For graphs containing cycles however, we have C/ < Cj and hence for those graphs, impossible devise an algorithm based on this reduction (such an algorithm would lead regret Cj log(T"). which contradicts the lower bound).
Instead, for general graphs, propose in Sec. 5.1.2 the wi-mean-field reduction, approximation based on a local decomposition inspired by Mean Field (MF) methods [39]. The v--mean field reduction leads to optimization problem whose value CMF provably upper bounds Cg and hence that can be used to devise algorithm with regret approaching CM log(T))

---

5.1.1 Locally tree-like reduction
This reduction imposes local consistency constraints between group variables and local variables local variables (Wi)eE(N) where w; (Wi,a)oreA, E R 20' Define the local cone as:
Vr TERÁ: Bw E RRN Ve E Va, E Ai, wi,o
E
be b.E.Abbe mac
where the notation de a; means that the hh element of ae equals a, The locally tree-like approximation, presented in the next lemma, is obtained by replacing by Vr. in (2).
Lemma 5.1. For any 0 with rewards described by an acyclic factor graph, we have that Cp - C/ where Cg is the value of the following convex optimization problem:
min 6EVL
Σ
(0s 0c(ae)) s.t.
Σ
V S s((a), Va A.
(3)
EE
eElpla.zaat
The proof is presented in App. À + KNN. The lemma states that, for acyclic factor graphs, the locally tree-like approximation is tight, i.e., C Cg. Unfortunately, for general graphs, we have that C/ < C (a direct consequence of 39 Prop. 4.1]), and hence it is impossible devise algorithms based on this approximation.
A.2
This approximation reduces the number of variables from K. to
5.1.2
Me-e--FFilld reduction
Our dMMF reduction is loosely inspired by MF approximation methods in graphical models 39 It consists in decomposing global variables
function t of the local variables (w])ie|N]- Specifically, the 1f-M reduction introduces the following set of constraints: va (w)).. Va & ag- where Vo RKN > Rzo. Let V = {u E R2 Fw E RNN the oMMF marginal cone as
20 = va(w). Va & ag }. and define
V PMMMF
8 UE V Ef Vo, Ve E (,) E Aes To,ee
Σ
Ub
We get the MF approximation, Cg-ME by replacing D by Do- in (2)
Lemma 5.2. For any 0, vb we have that Cg S C where Cr is the value of the optimization problem:
min
Σ
(e. 0e (ae)) s.t.
Te A(a)),
Va E A.
(4)
NE cELp).a.EA.
Clearly, the tractability of the problem Cy depends on the choice of v. A natural choice would be (w) [[<e[N] W/,,,, proposed, e.g., in approximate inference methods (39). However, this choice leads non-convex program (see App. B The following lemma proposes choice of sb
which leads to convex program over local variables w only.
Lemma 5.3. Let (a(w) = EiE[N] Wi,a Va +
a". Then Cy-MP is the value of the following convex
optimization problem:
min WERKN 20
Σ
Seaa (w)((((())))) Oc(ax)) s.t.
Σ
Sa.a, (w) < Va A, (5)
EAl
cElp):a,ta:
where fe,a, (w) K-N-18e1 EiES. Wi,, + 1-N-1Sall1 Eigs. Wi Furthermore, holds that C <PA- Ecelp) (O(at) (0(at) Oc(a))) where Amin minage A(a).
MF
The proof is presented in App. A.3 The lemma provides a worst-case scaling of C CPP-MP it scales at most as À = EeElo) k.S.l (remember that if we were considering MAMAB standard bandit problem, the latter would have KN arm and hence regret scaling exponentially in N). The number of variables involved in (5) is KNN. The quantities (fe.a, (w) ) EA, group quantities interpreted as the group variables ūe,a., and uniquely determined by local variables w. In
the following. we use the notation OM to represent C for the function & defined in Lemma 5.3
5

---

5.2 Constraint reduction
The remaining challenge is to reduce the number of constraints in (3) or 5 For each global action a, the constraint writes LeEjp] 3edd A())?. The major issue the non-linearity of the function appearing in the constraints w.r.t. group actions de. Upon inspection, it appears that the heterogeneity in the gaps (generally ((a) * (b) for a * b) is causing the non-linearity. To address this problem, ordering of the first smallest gaps. For E [K*], let a!m) be the m best global action and, for m E [K- 1]. let Am = 0(ag) (a) be the m²th minimal non-zero gap (with ties breaking arbitrarily).
present, in the following lemma, family of approximations leveraging an
Lemma 5.4. Let m E [K~ N - 1], and o E [L, Let (m) be the value of the convex program:
min RED
Σ
Te,a, (Be(a-)) - (c()))
eElp),,EE.
s.t.
Σ
0-1 (. S $3 Vj E [m]
(7)
<Elp)aa/*1)
Σ
S A.
Va E A UsEimi (10+1)).
(8)
eElp)a, Koz
Then, for any E (L, [F,, m E [KN 2]. we have Cg (m + 1) S (3(m), Cp S Cg (m)) and by definition O% (K- 1) = Og.
The proof is reported in App. Clearly, (m)) has still |A| constraints
However, as the gap Am used in (8) is constant, these constraints are now linear sum of terms depending on group actions de. For constraints with this type of structure, there exists an efficient and provably equivalent representation. The procedure yielding this representation, which we refer to as FCR, is based on generalization of the popular Factored LP algorithm described in 19 20 for Factored Markov Decision Processes (FMDPs).
For the sake of brevity, briefly describe the procedure below and postpone its detailed exposition to App. G FCR is inspired by the Variable Elimination (VE) procedure in graphical models (14). It iteratively climinates constraints from (8). according to elimination order O. The elimination procedure induces an elimination graph, which encodes dependencies between constraints as we perform elimination. As shown in the following lemma, the number of constraints is exponential in the degree Ao of the elimination graph induced by the order of elimination O.
Lemma 5.5. There exists a procedure which, given the constraints in 8 returns a provably equivalent constraint set of size ONN ONNKAo+) KA++1).
Although for general graphs finding ordering O minimizing Ao is an Whhhard problem [14), for specific graphs there are orderings yielding Ao < N. For example, these orderings yield Ao = for line star factor graphs, and Ao 3 for ring factor graphs, independently of the number of agents N (see Fig. 3 and refer to App. for details). Solving (m). requires computing the first m + 1 best global actions and the minimal gaps. To solve this task, the elim-m-opt algorithm [15] has complexity O(m + 1)NK Ao+1) (see App. G). Fig. 2 shows an illustration of the trade-off between statistical and computational complexity. Note that ESM is meant to be applied when m does not grow exponentially in N. In practice, observed that selecting m A yields a good trade-off between statistical complexity and computational complexity.
6 The ESM algorithm
In this section, present ESM, algorithm whose regret matches (asympiotically) our approx- imated lower bounds. The algorithm is inspired by OSSB (8.. It ensures that sub-optimal actions sampled prescribed by the solution of the approximated optimization problems CMF (m) or (m)) each group must explore each group action for ër,a, log(T) times, and selecting the action yielding the largest estimated reward for the remaining rounds. As the lower bounds depend on the unknown parameter 0, it has to be estimated.

---

Shabetted compienn
Statotiral exmplestty
[o
(1)
6 (w0)
Ca
O(KNA))
OpKM
O(ANK(o)
O(K*)
Computatiionl complexity
Computational complesity
Figure 2: Left: idealized curve illustrating possible ranges of the trade-off between statistical and computational complexity for CM (m), when varying m. Right: an instance of this trade-off for line factor graph (darker colors for the points represent higher running times). Selecting m = A yields good trade-off between computational and statistical complexity for this instance.
Generally, the estimation of 0 would require evaluating an exponentially large number of com- ponents, i.e. ((a), Ya E A. Instead, by leveraging the factored reward structure, ply focus on estimating group parameters (9e)ne(p)- We define the estimate at time t, group e, and action ae as O Ne,e.ng Exe[t]oa,.. ma. Tsee where Nr,,, E.e(f (an.=a.)) is the number of times action a, selected for group e. We also define o (Br.aa))ee and N₂
sim-
Algorithm 1 ESM((A, E, 9, m))
Sample each group actions in Ao once and update (NTr 0r, ST, 0 for t = To..... .' do
Initialization
(((L,))EE(p) f- Solve C% (m)
Ne,,,, 2 (1 + a,, log(t), Ve E [p], E A. then
D Exploitation
Qt = 81-1
a
else
= 81-1 +1
if mine Ne,a, 88 then
Estimation
0t E Ao ard be with (e', be) arg min Ne,c,ac else
Exploration
EEA: A: at,e' = by with (e', ber) E arg min., 0t.ciee Update (Nv,,,ar, 01,e,as.)eeE/1
Na.ea
The pseudocode of ESM is presented in Alg. [ It takes as inputs two exploration parameters
E, > an exploration set An C A, the approximation parameter m [K* 1]. and (MF, L} depending on the targeted regret lower bound approximation. The parameters s, y > 0 impact the amount of exploration performed by ESM. When decreasing both these parameters the exploration of ESM also decreases. After an initialization phase, the algorithm alternates between three additional phases as described below.
Initialization. In the initialization phase, we select actions from An to ensure that each group action is sampled at least once. The set Ao A is chosen in such way that it covers all possible group actions, i.e. Ag is such that Ve E [p]. Va, E Ac, 3b E An : be ae- In App. [ we present an efficient routine select An- Let To inf (t 2 0: N > 0, Ve [p]. ag A.) be the length of the initialization phase. For < To we select d, E Ao at,e' = by with (e',br) E arg min Nt, (with ties breaking arbitrarily), i.e., select global action containing the most under-explored group action. This choice ensures that To Å. For / To. the algorithm solves the approximated lower bound optimization problem Co (m) and alternates between exploitation, exploration, and estimation.

---

Exploitation. If Nt.e,a, 2 (1 + r, log(t), ESM enters the exploitation phase: it selects the best empirical action az arg max Enehy 0 fr,e,a.- Generally, computing dj requires operation over an exponential number actions A. Fortunately, due to the factored structure, we can implement the max operation efficiently through VE procedure (39 (see App. G
Estimation. not enough information has been gathered, ESM enters an estimation phase, where it selects the least explored group action similarly to the initialization phase. This ensures that the certainty equivalence holds, i.e., that O, is estimated accurately.
Exploration. Otherwise, the algorithm enters the exploration phase and selects actions suggested by the solution of C% (m). More precisely, we select global action a, E AA which contains group
action at.e' by. that minimizes the following ratio where e' and b are the group index and group action which minimize Na.a.
Upper bound. We establish that the ESM algorithm achieves a regret, matching the approximate lower bound C3 (m) log (T), asymptotically as T - co. The proof is given in App. D
Theorem 6.1. Let < Aol For any m E [KN 1). we have that
1. limsupr-co log (T)
RM(T) (T)
C CM (m)E(E,
ESM( E, Y, MF, m), for any 0
2. lim supp- [T]
(T)
< ()) f). LEM(MA, 7, m), for any 0 described
by acyclic factor graphs.
where & a function such that lim(e,)) 7) =
Experiments
In this section, present numerical experiments propose two sets of experiments: (i) a set of synthetic MAMABs with different graph topologies, and (fi) industrial use-case from the radio communication domain: antenna till optimization. The code for the synthetic experiments and the additional experiments presented in App. Kiis is available at this link
the performance of algorithm. We
7.1 Synthetic Experiments
Problem instances. We consider the factor graphs depicted in Fig. The expected rewards are selected uniformly at random in the interval [0, 10). In experiments, select N = 5 and K We execute our experiments for Nsim = 5 independent runs. Following previous work (8), we select ? 0, and ş 0.01. The climination order chosen O [N]. We implement the solver for the lower bound optimization problems using CVXPY [7] with a MOSEK solver
3
Figure 3: Factor graphs used in the synthetic experiments: ring (left), line (center), star (right).
Results. The results for the regret (in log scale) are presented in Fig. 4 The performance of ESM is compared to that of MAUCE 33. HEIST [35]. and to random strategy selecting actions uniformly random. The computational complexity results, reported in Fig. 5 measure the running time (in sec.) to solve an instance of the approximate lower bound optimization problem Că (m). We use A. and
MF for the ring, L for the star and line graph topologies.

---

Ring Sechr goob
Line foctor praph
Star Sacre graph
125
37
337
[F((2)
Fitel (It A]
127
Liva Bocad
231
240
240
7"
Figure 4: Regret results for the synthetic instances.
Ping factor graph
Line foxtor graph
Star factor graph
00
045
04
Figure 5: Running time (in sec.) to solve an instance of (m(), when varying m.
7.2 Antenna tilt optimization
Next, we test algorithm on radio network optimization task. The goal is to control the vertical antenna tilt at different network Base Stations to optimize the network throughput. In the following, we detail the network model, our simulation setup, and present our experimental results.
Network model. We consider sectorized radio network consisting of set of sectors The set of sectors corresponds to the set of agents in our MAMAB framework. Since each sector is associated a unique antenna, we will use the terms sector and antenna interchangeably. We assume that each sector E S serves (on the downlink) fixed set of Users Equipments (UEs) L4; (each UE is associated with a unique antenna, that from which receives the strongest signal).
[N].
Factor graph. We model the observed reward in the radio network as a factor graph with = SS] agent nodes and م = factor nodes. Each sector is associated with unique factor, which models the rewards observed in that sector. We build the factor graph based on the interference pattern of the antennas, i.e., antennas that can interfere with each other connected common factors. An example of such a graph and additional experimental details are reported in App. L
Actions and rewards. The action ar,i represents the antenna tilt for sector i E S and at time is chosen from discrete set of K tilts, ie., 0, E {a)..... ax) J. The tilt for a group of sectors is denoted by ae. Rewards
based on the throughput of UEs in sector i, which depends on the actions of a group of agents a.: re(a.) Eneu, Ti, (az), where Tū,, is the throughput of an UE associated to sector i. Hence, the global reward for tilt configuration r(a) = Eie(N] [N] Eneu, (ae). The throughput Ti,. depends on channel conditions (or fading) between the antenna and the user. These conditions rapidly evolve over time around their mean.
A is
Simulator. We run experiments in proprictary mobile network simulator in urban environ- ment. The simulation parameters used our experiments are reported in App. K Based on the user positions and network parameters, the simulator computes the path loss in the network environment using a BEZT propagation model (22 and returns the throughput for each sector by conducting user association and resource allocation full-buffer traffic demand scenario.
Results. We test our algorithm for A, {2", 70, 13"), and for |S] sectors. As the factor graph contains cycles, we use o MF and select vm 3. The results, presented in Fig. 6 are in line with the experimental findings of the previous section. However, the ESM running time higher due to the higher complexity of the factor graph.

---

Ca [m)
SHAND
SMARCK
ii Regret (log-scale).
(ii) Running (in sec.).
Figure 6: Results for the antenna tilt optimization experiments.
Conclusions
In this paper, we investigated the problem regret minimization in MAMABs: we derived regret lower bound, proposed approximations of it, and devised ESM, an algorithm trading off statistical and computational efficiency. We then assessed the performance of ESM both synthetic examples and the antenna tilt optimization problem. Interesting future research directions include proposing efficient distributed implementations of ESM, quantifying on communication complexity, and investigating representation learning problems in MAMABs where the underlying factor graph defining the reward is unknown and needs be learned.
Acknowledgement
This research supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
References
[1] MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9.0. 2019. [2] Eugenio Bargiacchi et al. "Learning to Coordinate with Coordination Graphs in Repeated Single-Stage Multi-Agent Decision Problems". In: Proc. of ICML. 2018.
[3] Eugenio Bargiacchi et al. "Multi-agent RMax for Multi-Agent Multi-Armed Bandits". In: Proc. of Adaptive and Learning Agents Worksh. 2022.
[4] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[5] Stephen Boyd et al. A tutorial on geometric programming. Optimization and Engineering, 2004.
[6] Shouyuan Chen "Combinatorial Pure Exploration Multi-Armed Bandits". In: Proc. of NeurIPS. 2014.
[7] Wei Chen, Yajun Wang. and Yang Yuan. "Combinatorial Multi-Armed Bandit: General Frame- work and Applications". In: Proc. of Mach. Learn. Res. 2013.
[8] Richard Combes, Stefan Magureanu, and Alexandre Proutiere. "Minimal Exploration in Structured Stochastic Bandits". In: Proc. of NeurIPS. 2017.
[9] Richard Combes and Alexandre Proutiere, "Unimodal bandits: Regret lower bounds and optimal algorithms".. In: Proc. of ICML. 2014.
[10] Richard Combes al. "Combinatorial Bandits Revisited". In: Proc. NeurlPS. 2015.
[11] Richard Combes et al. "Learning to rank: Regret lower bounds and efficient algorithms". In:
Proc. of SIGMETRICS. 2015.
[12] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. "Asymptotically Optimal Strategies For Combinatorial
in Polynomial Time". In: Proc. of ALT. 2021.
10

---

[13] Thibaut Cuvelier, Richard Combes, and Eric Gourdin. "Statistically Efficient, Polynomial-
Time Algorithms for Combinatorial Semi-Bandite In: Proc. ACM Meas. Anal. Comput. Syst.
(2021).
[14] Rina Dechter. "Bucket Elimination: A Unifying Framework for Reasoning". In: Artif. Intell. (1999).
[15] Rina Dechter, Natalia Flerova, and Radu Marinescu. "Search Algorithms for M Best Solutions for Graphical Models". . In: AAAI Press, 2012.
[16] Rémy Degenne and Vianney Perchet. "Combinatorial semi-bandit with known covariance". In: Proc. of NeurIPS. 2016.
[17] Steven Diamond and Stephen Boyd. "CVXPY: A Python-embeddee modeling language for convex optimization". In: JMLR (2016).
[18] Todd Graves and Tze Leung Lai. "Asymptotically efficient adaptive choice of control laws incontrolled markov chains". In: SIAM journal on control and optimization (1997).
[19] Carlos Guestrin, Daphne Koller, and Ronald Parr. "Max-norm Projections for Factored MDPs". In: Proc. of IJCAL. 2001.
[20] Carlos Guestrin et al. "Efficient Solution Algorithms for Factored MDPs". In: J. Artif. Int. Res. (2003).
[21] Botao Hao, Tor Lattimore, and Csaba Szepesvári. "Adaptive Exploration in Linear Contextual Bandit". In: Proc. of AISTATS. 2020.
[22] Yassir Jedra and Alexandre Proutiere. "Optimal Best-arm Identification in Linear Bandits". In: Proc. of NeurIPS. 2020.
[23] Emilie Kaufmann. "Contributions to the Optimal Solution of Several Bandit Problems". Habilitation à diriger des recherches. Université de Lille, Nov. 2020.
[24] Branislav Kveton et al. "Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits", In:
PLMR. Proceedings of Machine Learning Research. PMLR, 2015.
[25] Tze Leung Lai and Herbert Robbins. "Asymptotically efficient adaptive allocation rules". In: Advances in applied mathematics (1985).
[26] E.L. Lawler. "A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem".. In: Management Science (1972).
[27] Marloes Maathuis et al. Handdbook of Graphical Models. CRC Press, Inc., 2018.
[28] Stefan Magureanu, Richard Combes, and Alexandre Proutiere. "Lipschitz Bandits: Regret
Lower Bound and Optimal Algorithms". In: Proc. of COLT. 2014.
[29] P.J. Modi. "Distributed constraint optimization for multiagent". PhD thesis. University of Southern California, 2003.
[30] D. Nilsson. "An Efficient Algorithm for Finding the M Most Probable Configurationsin
Probabilistic Expert Systems". In: Statistics and Computing (1998).
[31] Pierre Perrault et al. "Statistical Efficiency Thompson Sampling for Combinatorial Semi- Bandits". In: Proc. of NeurlPS. 2020.
[32] Theodore Rappaport. Wireless Communications: Principles and Practice. Prentice Hall, 2001.
[33] James Renegar. "A polynomial-time algorithm, based on Newton's method, for linear pro- gramming". In: Mathematical Programming (1988).
[34] David Sontag and Tommi Jaakkola. "On Iteratively Constraining the Marginal Polytope for Approximate Inference and MAP". In: Semantic Scholar (2007).
[35] Ruben Stranders et al. "DCOPs and bandits: exploration and exploitation in decentralised coordination".. In: Proc. of AAMAS. 2012.
[36] Filippo Vannella, Alexandre Proutiere, and Jaeseong Jeong. "Best Arm Identification in Multi- Agent Multi-Armed Bandits". In: Proc. of ICML. 2023.
[37] Timothy Verstraeten et al. "Multi-Agent Thompson Sampling for Bandit Applications with Sparse Neighbourhood Structures". In: Scientific Reports (2020).
[38] Andrew Wagenmaker, Julian Katz-Samuels, and Kevin Jamieson. Experimental Design for Regret Minimization in Linear Bandits. 2020.
[39] Martin Wainwright and Michael Jordan. Graphical Models, Exponential Families, and Varia- tional Inference. Now Publishers Inc., 2008
[40] Siwei Wang and Wei Chen. "Thompson Sampling for Combinatorial
In: Proc.
of ICML. 2018
11


Reviews:
[{"review_id": "SnkqTrLxOn", "reviewer": "Reviewer_Pi4y", "summary": "This paper consider the regret minimization problem in MAMABs, which typically has an exponentially large action space in relation to the number of agents. The authors first establish a lower bound result for general MAMAB by generalizing techniques from single agent bandit literature. More precisely, the lower bound is obtained by solving a convex optimization problem with exponentially many variables and constraints. Next, the authors present an equivalent characterization of the program for reward structures with acyclic factor graphs and provide mean-field approximation programs for general graph models. Finally, the authors design computationally tractable algorithms based on the proposed equivalent(approximation) program for acyclic factor graphs(general graphs). ", "questions": "1. What is the trade-off when letting $\\varepsilon, \\gamma\\to 0$ in Algorithm 1? It appears that Theorem 6.1 always encourages selecting small values for $\\varepsilon,\\gamma$\n\n2. In the acyclic factor graphs setting, while the proposed characterization is statistically tight, what is the computational complexity of the proposed algorithm to achieve optimal regret(i.e. select $m = K^N - 1$)?  Will it achieve the same polynomial-time complexity as in [11] in this setting?\n\n3. In line 155, authors said \"Unfortunately, for general graphs, we have that $C^L_\\theta < C_\\theta^\\star$ (a direct consequence\n156 of [36, Prop. 4.1]), and hence it is impossible to devise algorithms based on this approximation.\" \nI am wondering why it is impossible to propose an approximation algorithm based on the  $C^L_\\theta$ value (since the proposed approximation program in the mean-field approximation is also not guaranteed to have a value equal to $C_\\theta^\\star$)\n", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Most writing is clear and easy to follow, even for those without extensive knowledge in MAMABs. Most claims and definitions are well-supported by existing literature.\n\n2. Both the proposed lower bound and the proposed approximation scheme are interesting.\n\n3. Authors also provide simulations and real-world applications to further enhances the relevance and practicality of the proposed methods.", "weaknesses": "While the paper overall is well-written and informative, I found some parts of the presentation to be unclear. Specifically, there were several points where I had questions and would have appreciated more explanation or clarification.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer Pi4y for the constructive and comprehensive review. We clarify the main questions in the following.\n\n\n1. *\"What is the trade-off when letting $\\varepsilon,\\gamma \\to 0$ in Algorithm 1? It appears that Theorem 6.1 always encourages selecting small values for $\\varepsilon,\\gamma$*\n\nThe choice of $\\varepsilon, \\gamma$ in our algorithm does not really involve any trade-off. These parameters are \"safety parameters\" that should just be strictly positive for our analysis to hold. The parameters impact the amount of exploration performed by ESM. When decreasing both these parameters the exploration of ESM also decreases, and this in turn improves the statistical performance of the algorithm. More precisely, in the proof of Thm. 6.1 (see App. D), we show that the regret upper bound is minimized when $(\\varepsilon,\\gamma) \\to (0,0)$. We will include these clarifications in the final version of the paper.\n    \n2. *\"In the acyclic factor graphs setting, while the proposed characterization is statistically tight, what is the computational complexity of the proposed algorithm to achieve optimal regret (i.e. select $m = K^N-1$)? Will it achieve the same polynomial-time complexity as in [11] in this setting?*\"\n\nIn the acyclic factor graph setting, the leading term in the computational complexity of ESM is given by the cost of determining the $m$ smallest gaps. Finding the best algorithm for solving this task is still an active area of research (see [15] and references therein for details). For example, the elim-$m$-opt algorithm has complexity $O((m + 1)NK^{A_{\\mathcal{O}}+1})$ (see line 203 and App G). Hence, for $m = K^N-1$ the computational complexity of ESM in this case would be exponential in $N$. In fact, in practice, our method is meant to be applied when $m$ does not grow exponentially in $N$ (we will clarify this), because if it does, then the algorithm we obtain is at least as complex as the initial lower bound problem. As explained in Sec. 5.2, in practice selecting $m \\simeq \\tilde{A}$ yields a good trade-off between statistical complexity and computational complexity (see Fig. 2), and the latter will be polynomial in this case. \n\nAbout the computational complexity of [11], we believe that even for acyclic factor graphs, the algorithm of [11] would not lead to a polynomial-time computational complexity. Indeed, to prove a polynomial sample complexity of their algorithm, the authors postulate the existence of a *\"budgeted linear maximization\"* oracle (Assumption 2 in [11]), and we are not aware of the existence of such an oracle for these types of MAMABs instances. We will include these considerations in the final version of the paper. \n\n3. *\"In line 155, authors said \"Unfortunately, for general graphs, we have that $C^L_{\\theta} < C^\\star_{\\theta}$ (a direct consequence 156 of [36, Prop. 4.1]), and hence it is impossible to devise algorithms based on this approximation.\" I am wondering why it is impossible to propose an approximation algorithm based on the $C^L_{\\theta}$ value (since the proposed approximation program in the mean-field approximation is also not guaranteed to have a value equal to $C^{\\star}_{\\theta}$).\"*\n\nThis is an interesting question! We cannot devise algorithms based on $C^{\\text{L}}_{\\theta}$ for MAMABs instances with cyclic factor graphs because it would contradict the lower bound result in Thm. 4.1. \n\nTo see why, note that:\n\n(i) for acyclic factor graphs, we have that $C^L_{\\theta} < C^\\star_{\\theta}$, and \n\n(ii) the lower bound dictates that any (consistent) algorithm must satisfy $R^{\\pi}(T)/\\log(T) \\ge C^\\star_{\\theta}$ as $T\\to \\infty$ (see Thm. 4.1). \n\nNow, if one could devise an algorithm based on ESM which target $C^L_{\\theta}$, we would get an algorithm with an upper bound than that attains $R^{\\pi}(T)/\\log(T) \\le C^L_{\\theta} < C^\\star_{\\theta}$ as $T\\to \\infty$ (see Thm. 6.1), which clearly contradicts the lower bound.\n\nOn the other hand, for the Mean-Field (MF) approximation, we have that $C_{\\theta}^{\\psi\\text{-MF}} >  C^\\star_{\\theta}$, for any $\\psi$, and hence the problem described above for $C^L_{\\theta}$ is avoided. We will include these clarifications in the final version of the paper. "}, {"review_id": "dfIK07YT0q", "reviewer": "Reviewer_7bJY", "summary": "This paper focuses on an interesting problem, which is a version of multi-armed bandits in which there are multiple agents and an action needs to be selected for each one of them. This is a problem that has been studied before in the literature and the authors here provide improved bounds on the regret by approximately a factor of k^d, where k is the number of agents and the degree of a graph that defines the reward function. Moreover, the authors' algorithm gives a knob that controls the tradeoff between the regret and the time spent solving the multi-agent optimization problem of each round.\n\nThe authors finally provide an experimental evaluation of their algorithm on a synthetic and a real dataset. The plots show that the regret is low and improves over a simple baseline and over previous work.", "questions": "- Why do you not compare against [2] and [36] in the experiments and rather choose weaker baselines?\n- How does your problem compare against combinatorial bandits and why can't techniques from there be used in your setting?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper improves over the state of the art in theoretical guarantees\n- The paper is well written, easy to follow\n- The experimental evaluation shows good results", "weaknesses": "- The theoretical results are shown to be an improvement against [2] and [36] but the experimental part does not compare against [2] and [36].\n- The related work pointers seem incomplete. The vast literature of combinatorial bandits seems to be very related (again combinatorial problems need to be solved in each round) but is not mentioned.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 7bJY for the comprehensive and detailed review. We address the main questions in the following. \n\n- *\"The theoretical results are shown to be an improvement against [2] and [36] but the experimental part does not compare against [2] and [36]. Why do you not compare against [2] and [36] in the experiments and rather choose weaker baselines?\"*\n\nThank you for noticing this issue, only due to a mistake we made when referencing a paper. Indeed, unfortunately, we realized that we misplaced a reference in the experiment section: [3] should be replaced by [2] in line 255. In our experiments, we do not choose a weaker baseline but the MAUCE algorithm shown in Figs. 4,5,6, actually corresponds to the reference [2]. We thank the reviewer for highlighting this issue, which we will fix in the final version of the paper.\n\nNow, to the best of our knowledge, the MAUCE algorithm [2] is the state of the art in MAMABs and the best competitor to our algorithm. As stated in lines (73-75), the HEIST algorithm proposed in [36] is very similar to MAUCE: it is a UCB-type algorithm but with a different constant in the UCB term. However, HEIST has worse regret guarantees for most MAMABs instances: its asymptotic regret scales as $O(K^N\\Delta_{\\max}/\\Delta_{\\min}\\log(T))$, while the scaling of the regret of MAUCE is $O(\\rho^2 K^d\\Delta_{\\max}^2/\\Delta_{\\min}^2\\log(T))$ (please refer to Sec. 2 and App. M.1 for details). Hence, in the experiments, we choose to compare our algorithm to MAUCE only. However, for the sake of completeness, we have now performed a few additional experiments testing the performance of HEIST [36]. The results of these experiments are included in Fig. 1 of the accompanying document attached to this rebuttal. We will include these experiments in the final version of the paper. \n\n- *\"The related work pointers seem incomplete. The vast literature of combinatorial bandits seems to be very related (again combinatorial problems need to be solved in each round) but is not mentioned. How does your problem compare against combinatorial bandits?\"*\n\nThank you for your question. Although we acknowledge your concern, we believe that related works in combinatorial bandits (and the relationship between combinatorial bandits and MAMABs) have been covered in the paper and the appendices, as we explain below. \n\n1. First, the connection between combinatorial bandits and MAMABs is presented in App. E, where we explain that our MAMAB setting can be interpreted as a particular instance of combinatorial bandits with semi-bandit feedback, and we provide an example of this connection. \n2. Second, in lines (78-87) of the related work section, we mention different related works in the combinatorial semi-bandit feedback literature ([24, 9, 11, 12, 35]) and we discuss the closest and most relevant work [11] in the main body of the paper. In the current submission, other related works in combinatorial bandits are discussed in detail in App. M.2, for reasons of space. \n\nWe will include this discussion in the main body of the paper by using the extra space in the final version of the paper. We have further included a few additional references in the answer to the next question, which are reported at the end of this rebuttal. Moreover, should the reviewer be aware of other relevant works in combinatorial bandits that are not already covered in the current manuscript, we would welcome the opportunity to include them.\n    \n- *\"Why can't techniques from there be used in your setting?\"*\n    \nWe believe that this point has been addressed in App. M.2 and App. H, and we are glad to provide further clarification. As the reviewer suggests, in principle, one could indeed use combinatorial bandit methods as those referred into Sec. 2 or App. M.2, but most likely these will yield computationally inefficient algorithms, as we explain in the following. \n    \nFor example, combinatorial bandit algorithms based on Thompson Sampling (TS) techniques [34, a, b] usually require, at each time step, a maximization step of the type $\\max_{a\\in\\mathcal{A}} \\sum_{e\\in[\\rho]} \\theta_e(a_e)$. We show in Lem. H.1 that, for general factor graphs, performing this operation is $\\mathcal{NP}$-hard. \n    \nOther combinatorial bandit algorithms, employing e.g., Upper Confidence Bound (UCB) methods such as [16, 9, c], often involve even harder maximization steps w.r.t. the maximization presented above. For example, the algorithms proposed in [16, 9, c] require solving an index maximization problem of the type\n    $$\n    \\max_{a\\in\\mathcal{A}}  \\sum_{e\\in[\\rho]} \\theta_e(a_e) + \\sqrt{\\sum_{e\\in[\\rho]} c\\log(T)/N_{e,a_e}(t)}.\n    $$\nFor many combinatorial structures (e.g. even for $m$-sets), there is no polynomial time algorithm to solve the task above [11]. We will include the above discussion in the final version of the paper. \n\n**Additional references**\n\n[a] Siwei Wang and Wei Chen, *Thompson sampling for combinatorial semi-bandits*. In Proc. of ICML, 2018.\n\n[b] Pierre Perrault,  Etienne Boursier, Vianney Perchet, Michal Valko, *Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits*. In Proc. of NeurIPS, 2020.\n\n[c] Wei Chen, Yajun Wang, Yang Yuan. *Combinatorial Multi-Armed Bandit: General Framework, Results and Applications*. In Proc. of ICML, 2013."}, {"review_id": "FF20i2rwrD", "reviewer": "Reviewer_EJNU", "summary": "This paper proposes the ESM algorithm for the regret minimization problem in Multi-Agent Multi-Armed Bandits, where the rewards are defined through a factor graph. The ESM algorithm attains a dedicate trade-off between statistical efficiency and computational efficiency in n Multi-Agent Multi-Armed Bandits.  The ESM algorithm is inspired by simple upper bounds of the regret lower bound, which characterizes the minimal expected number of times each global action should be explored and is computationally intractable to be exploited in the design of efficient algorithms. By tuning this upper bound, the ESM explores the trade-off between the achievable regret and the complexity of computing the corresponding exploration process. The ESM has a regret that asymptotically matches this upper bound. The regret and computational complexity of ESM are assessed numerically, using both synthetic and real-world experiments in radio communications networks.  ", "questions": "Please refer to the weakness part. ", "limitations": "See comments above. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper establishes a lower bound for the Multi-Agent Multi-Armed Bandits, where the rewards are defined through a factor graph. \n\nSimple upper bound of the regret lower bound is established, which enables the design ESM. \n\nAsymptotic regret upper bound of ESM is derived. \n", "weaknesses": "The regret lower bound looks not new and the proofs does not contribute new techniques. They look like straightforward applications of techniques from structured bandits.  \n\nThough upper bounds of the regret lower bound are established, the tightness of the upper bound is not proved. It is unknown how tight the upper bound is. Thus, it is unknown how much statistical efficiency is lost.  \n\nThe regret upper bound of ESM is asymptotic, which looks much weak than the finite round regret upper bound. \n\nThe gap between the regret upper bound of ESM and the regret lower bound is not quantified. It is unknown how tight the regret upper bound is.   \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer EJNU for the comprehensive and detailed review. We address the main questions in the following. \n\n- *\"The regret lower bound looks not new and the proofs does not contribute new techniques. They look like straightforward applications of techniques from structured bandits.\"*\n\nWe agree that the lower bound is derived using classical techniques. We clearly state, after Theorem 4.1, that the bound is derived by using \"classical change-of-measure arguments\" and again in App. A, that the bound \"is a direct consequence of an analogous bound in the combinatorial semi-bandit feedback setting, first given in [9, Th. 1] and leverages general techniques for controlled Markov chains\". \n    \nHowever, we do not understand why the reviewer is considering this point as a weakness. Presenting the lower bound serves two important purposes in the paper:\n\n1. Previous works in the literature on MAMABs do not provide any lower bound. \n\n2. More importantly, the lower bound is used in our paper as a starting point for the lower bound approximations and the algorithm design. \n\n- *\"Though upper bounds of the regret lower bound are established, the tightness of the upper bound is not proved. It is unknown how tight the upper bound is. Thus, it is unknown how much statistical efficiency is lost -- The gap between the regret upper bound of ESM and the regret lower bound is not quantified. It is unknown how tight the regret upper bound is.\"*\n\nThank you for raising this point. We are aware that a complete analytical quantification of the lower bound approximation is lacking and we believe that this is an important point for which further investigation is required. We would like to mention that addressing this point in its generality (for any $m$ and for both $\\diamond \\in \\\\{\\text{L, MF}\\\\}$) is very challenging due to the intricacy of the lower-bound optimization problems involved in the approximations.\n\nHowever, we would also like to mention that we presented different results on the quantification of our approximations as summarized in the following points. \n    \n(i) We proved in Lem. 5.4 that for any $m$ and any $\\diamond \\in \\\\{\\text{L, MF}\\\\}$, that $C^\\diamond_{\\theta}(m+1)\\le  C^\\diamond_{\\theta}(m)$, i.e. the approximations tightens as we increase $m$, and that $C^\\diamond_{\\theta}(K^N-1)\\le  C^\\diamond_{\\theta}$. \n\n(ii) We proved in Lem. 5.1 that for acyclic factor graphs, it holds that $C^L_\\theta = C^{\\star}_{\\theta}$ and hence the approximation is tight. \n\n(iii) We proved in Lem. 5.3 the following scaling for the MF approximation: for any $\\psi$, we have that $$C^{\\psi\\text{-MF}} \\le \\rho/\\Delta_{\\min}^2 \\sum_{e\\in [\\rho], a_e\\in\\mathcal{A}_e}\\theta_e(a_e^\\star)- \\theta_e(a_e).$$\n\nWe believe that these results complement each other and provide an overall understanding of the statistical properties of our approximations. \n\nIn Fig. 2 of the accompanying document attached to this rebuttal, we show a sample of the approximation ratio $C^\\diamond_{\\theta}(m)/C^\\star_{\\theta}$ for $m \\in \\\\{1, 3, 18, 37, 75, 100 \\\\}$, and $\\diamond \\in \\\\{\\text{MF}, \\text{L}\\\\}$ for different graph topologies. The results show that the $C^{\\text{MF}}_{\\theta}(m)$ is close to $C^{\\star}\\_\\theta$ (they are equal up to a small constant) and decreases with $m$. For $C^\\text{L}\\_{\\theta}(m)$, the same hold, and for $m$ large enough the approximation is tight $C^L\\_{\\theta}(m) = C^{\\star}\\_{\\theta}$, as predicted by our results.\n\nFinally, we would like to mention that the main contribution of the paper is to break the combinatorial nature of the problem. In other words, going from a regret scaling as $\\Theta(K^N)$ to one scaling as $\\Theta(\\rho K^d)$ (this scaling is guaranteed with our approximations) in a computationally efficient manner is the main contribution of the paper.\n\n- *\"The regret upper bound of ESM is asymptotic, which looks much weak than the finite round regret upper bound\"*\n\nAlthough we present the regret upper bound of ESM in the asymptotic form (as $T\\to \\infty$), we also obtain a finite time upper bound in App. D, as a byproduct of the proof of Thm. 6.1. The bound is: For any $\\kappa >0$, and $T\\ge 1$,\n\n$$\nR^{\\pi}(T) \\le \\theta(a^\\star) \\left(M(\\gamma,\\rho) + \\frac{2\\tilde{A}}{\\varepsilon\\delta(\\kappa)^2}\\right) + ((1+\\kappa)C^{\\diamond}_{\\theta} + 2 \\varepsilon\\psi^{\\diamond}(\\theta)(1+\\gamma))\\log(T),\n$$\n\nwhere $M(\\gamma,\\rho)$ is a constant depending only on the exploration constant $\\gamma$ and the number of groups $\\rho$, $\\psi^{\\diamond}(\\theta)= \\tilde{A} \\\\|\\tilde{v}^\\diamond(\\theta) \\\\|\\_\\infty \\sum_{e\\in[\\rho],a_e\\in \\mathcal{A}_e} (\\theta_e(a^\\star_e) - \\theta_e(a_e))$ (see App. D for details). We will highlight the finite-time regret upper bound by using the extra space in the final version of the paper. "}, {"review_id": "7BpY2kGi3b", "reviewer": "Reviewer_pqkD", "summary": "This paper studies the Multi-Agent Multi-Armed Bandits problem with factor graph reward structure, which is motivated by the real-world antenna tilt optimization problem. It first proposes an asymptotic lower bound that involves an optimization problem with exponential number of variables and constraints. Then, this optimization problem is relaxed by approximation techniques motivated from probabilistic graphical model. Finally, this paper proposes an learning algorithm based on the approximated lower bound and supports it with both synthetic and real-world experiments.", "questions": "- What is the intuition behind using $\\min_{a_i\\in\\mathcal{A}\\_i}\\frac{N_{t, i, a_i}}{w_{t, i, a_i}}$ as the action selection for exploration? In particular, how does this selection rule approximately satisfies the lower bound interpretation that action $a$ should expectedly be selected about $v^\\star_a\\log(T)$ times?\n- It seems the varialbes $w=(w_i)\\_{i\\in[N]}$ is undefined for $C^{\\diamond}_{\\hat{\\theta}_t}(m)$ when $\\diamond=\\mathrm{L}$. How will the ESM algorithm proceed when $\\diamond=\\mathrm{L}$?\n- Is that possible to analyze how the algorithm will perform when $\\diamond=\\mathrm{L}$ and the factor graph is not an acyclic factor graph? (It certainly cannot be better than the lower bound.) Also, can we see how it will perform empirically?\n- Is that possible to quantify the difference between $C^\\star_{\\theta}$ and $C^{\\diamond}_{\\theta}(m)$? That is, how far is the approximation away from the exact lower bound?\n- In the antenna tilt experiment, does the choice of action set $\\mathcal{A}_i=\\lbrace 2^\\circ, 7^\\circ, 13^\\circ\\rbrace$ contain any special considerations (why these three degrees)?", "limitations": "The limitations are addressed well in this paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The relaxation contains novel application of various techniques from probabilistic graphical model to this concrete problem.\n- The proposed algorithm can be computationally efficient and is flexible to lie at different points on the trade-off curve between statistical and computational complexity.\n- The proposed algorithm enjoys good asymptotic regret and the theoretical guarantee is corroborated with real-world experiment.\n", "weaknesses": "Although I don't view this as a serious issue, it seems this paper focuses a lot in how to solve the problem in a computationally efficient way while the analysis of the algorithm's performance is a little bit limited. For example, we do not know how far the approximation is away from the exact lower bound and how the algorithm with locally tree-like reduction will perform in general.\n\n### Suggestions on Writing\n- It may be better to briefly mention the rough magnitude of $C^{\\diamond}_{\\theta}(m)$ again after stating Theorem 6.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer pqkD for the constructive and comprehensive review. We address questions in the order they are presented.\n    \n- The intuition here is that in the exploration phase, we sample local actions that are the farthest from satisfying $N_{t,i,a_i} \\approx w_{t,i,a_i} \\log(T)$, for all agents $i\\in[N]$. This is naturally achieved by selecting, local actions that minimize the ratio $N_{t,i,a_i}/w_{t,i,a_i}$. Now, the interpretation for the lower bound in terms of group variables $\\tilde{v}$ (see Lem 4.2 and lines (124-126)) is that an optimal algorithm should sample each group arm $a_e$ for about $\\tilde{v}^\\star\\_{e,a_e}\\log(T)$ times. To see why the local action selection above will eventually satisfy this, we need to consider that (i) the condition in the exploitation phase of ESM enforces that $N_{t,e,a_e} \\ge \\tilde{v}\\_{t,e,a_e}(1+\\gamma)\\log(T)$, and (ii) $C^\\diamond\\_{\\hat{\\theta}\\_t}(m)$ is defined as an optimization problem over a constraint set $\\tilde{\\mathcal{V}}\\_{\\diamond}$ which imposes consistency between local variables $w$ and group variables $\\tilde{v}$. These constraints are key to ensure that ultimately this local sampling will ensure that $N\\_{t,e,a_e} \\approx \\tilde{v}\\_{t,e,a_e}(1+\\gamma) \\log(T)$. We will include this discussion in the final version of the paper. \n\n- For $\\diamond=L$, the variables $w=(w_{i,a_i})\\_{i\\in[N], a_i \\in\\mathcal{A}_i}$ are defined as $w\\_{i,a_i} = \\sum\\_{b\\in\\mathcal{A}:b_e \\sim a_i} \\tilde{v}\\_{e,b_e}, \\forall e\\in[\\rho],\\forall i\\in\\mathcal{S}_e,\\forall a_i \\in\\mathcal{A}_i$ (recall that the notation $a_e\\sim a_i$ means that the $i$-th element of $a_e$ equals $a_i$). This definition directly follows from the one of $\\tilde{\\mathcal{V}}\\_L$ in Sec. 5.1.1.\n\n    In practice, when running ESM, we proceed as follows: to solve the optimization problem defined by $C^L\\_{\\hat{\\theta}\\_t}(m)$, we instantiate both the group variables $(\\tilde{v}\\_{t,e,a_e})_{e\\in[\\rho], a_e \\in\\mathcal{A}_e}$ and the local variables $(w\\_{t,i,a_i})\\_{i\\in[N], a_i\\in\\mathcal{A}_i}$, and the corresponding constraints, as defined by $\\tilde{\\mathcal{V}}\\_{L}$, so that both variables are naturally returned by the solver. We will include this clarification in the final version of the paper.\n\n- Thank you for your question. We acknowledge that quantifying the tightness of the approximation is an important point, which requires further investigation. However, we believe that addressing this point in its generality (for any $m$ and for both $\\diamond = \\\\{L,MF\\\\}$) is very challenging due to the intricacy of the lower bound optimization problems involved in the approximations. Observe however that we presented different results on the quantification of our approximations in the paper, as summarized in the following points. \n    \n    (i) We proved in Lem. 5.4 that for any $m$ and any $\\diamond \\in \\\\{L, MF\\\\}$, that $C^\\diamond\\_\\theta(m+1)\\le  C^\\diamond\\_\\theta(m)$, i.e. the approximations tightens as we increase $m$, and that $C^\\diamond\\_\\theta(K^N-1) = C^\\diamond\\_\\theta$. \n\n    (ii) We proved in Lem. 5.1 that for acyclic factor graphs, it holds that $C^L_\\theta = C^\\star_\\theta$ and hence the approximation is tight. \n\n    (iii) We proved in Lem. 5.3 the following scaling for the MF approximation: for any $\\psi$ we have that $$C_\\theta^{\\psi-MF} \\le \\rho/\\Delta_\\min^2 \\sum_{e\\in [\\rho], a_e\\in\\mathcal{A}_e}\\theta_e(a_e^\\star)- \\theta_e(a_e).$$\n    \n    We believe that these results complement each other and provide an overall understanding of the statistical properties of our approximations. \n\n    Finally, we would like to highlight that the main contribution of the paper is to break the combinatorial nature of the problem. In other words, going from a regret scaling as $\\Theta(K^N)$ to one scaling as $\\Theta(\\rho K^d)$ (this scaling is guaranteed with our approximations) in a computationally efficient manner is the main contribution of the paper.\n\n- Thanks for the very interesting question. Analyzing the performance of ESM with $\\diamond=L$ for factor graphs with cycles is actually one of the future directions we want to explore. Although we do not have any conclusive results on the analysis yet, we present a few empirical results in the attached document. \n    \n    We consider the cyclic factor graph in Fig. 3 (left) of the document accompanying this rebuttal with $K=3$ local actions. We compare the performance of ESM for $\\diamond=\\\\{\\star,L\\\\}$ and $m=\\tilde{A}$. In Fig. 3 (center), we show the lower bound as $C^\\diamond_\\theta\\log(T)$ for $\\diamond=\\\\{\\star,L\\\\}$ and in Fig. 3 (right), we show the results for the regret of ESM. As expected, although $C^L\\_\\theta\\le C^\\star\\_\\theta$, $ESM(\\diamond=L)$ cannot outperform $ESM(\\diamond=\\star)$.\n\n    In general, for many instances, we empirically observed that $C^{L}\\_{\\theta}$ and $C^\\star\\_\\theta$ are usually close. For example, in Fig. 12 (App. K), we compare these two quantities for $100$ randomly generated instances (of the group means) for a ring factor graph (see Fig. 3). As shown in such figure, $C^L\\_\\theta$ is very close or indistinguishable from $C^{\\star}\\_{\\theta}$ for all the instances. We observed similar behavior for other types of cyclic graphs. Based on these empirical observations, we believe that, potentially, it might be possible to use ESM with $\\diamond=L$ even for cyclic factor graphs, and we will explore this direction in the future. We will include the above discussion in the final version of the paper.\n\n- The choice of the tilt angles in our experiments has no particularly deep explanation and is based on simulation-dependent observations. \nThe choice of the maximum tilt ($13^\\circ$) is also backed by the intuition that one may not want to select tilts with excessive values as these create blind spots in the coverage where network users are not connected to the network (see also App. L for additional details).  We will include this discussion in the final version of the paper."}]

Author rebuttal:
We thank the reviewers for their comprehensive and detailed reviews. We address the reviewers' questions individually in the rebuttals below. As requested by the reviewers, we have run additional experiments during the rebuttal period. We present the results of these experiments in the accompanying document attached to this rebuttal. 

Meta-review: The reviewers agreed in the opinion that the paper makes good progress on the multi-agent bandit problems and gives an interesting insight on the tradeoff between the regret and the computational efficiency. On the other hand, some concerns on the contribution of the paper in relation with existing work are raised. They seem to be largely solved by the rebuttal but I expect that the authors carefully incorporate them in the final version.
Decision: Accept (poster)