Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds
Authors: Johan Östman
Ather Gattami
Daniel Gillblad
Venue: Submitted to ICLR 2023 (2023)
Keywords: Bandit optimization
multi-agent learning
decentralized learning
joint bandit-rewards

Abstract: We consider a decentralized multiplayer game, played over $T$ rounds, with a leader-follower hierarchy described by a directed acyclic graph. For each round, the graph structure dictates the order of the players and how players observe the actions of one another. By the end of each round, all players receive a joint bandit-reward based on their joint action that is used to update the player strategies towards the goal of minimizing the joint pseudo-regret. We present a learning algorithm inspired by the single-player multi-armed bandit problem and show that it achieves sub-linear joint pseudo-regret in the number of rounds for both adversarial and stochastic bandit rewards. Furthermore, we quantify the cost incurred due to the decentralized nature of our problem compared to the centralized setting. 

Under review as a conference paper at ICLR 2023
DECENTRALIZED ONLINE BANDIT OPTIMIZATION ON DIRECTED GRAPHS WITH REGRET BOUNDS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider decentralized multiplayer game, played over T'' rounds, with a leader-follower hierarchy described by a directed acyclic graph. For each round, the graph structure dictates the order of the players and how players observe the actions of one another. By the end of each round, all players receive joint bandit- reward based on their joint action that is used to update the player strategies to- wards the goal of minimizing the joint pseudo-regret. We present learning algo- rithm inspired by the single-player multi-armed bandit problem and show that it achieves sub-linear joint pscudo-regre in the number of rounds for both adversar- ial and stochastic bandit rewards. Furthermore, we quantify the cost incurred due to the decentralized nature of our problem compared to the centralized setting.
INTRODUCTION
Decentralized multi-agent online learning concerns agents that, simultaneously, learn to behave over time in order to achieve their goals. Compared the single-agent setup, novel challenges are present as agents may not share the same objectives, the environment becomes non-stationary, and informa- tion asymmetry may exist between agents (Yang Wang 2020p. Traditionally, the multi-agent problem has been addressed by either relying on a central controller to coordinate the agents' ac- tions or to let the agents learn independently. However, access central controller may not be realistic and independent learning suffers from convergence issues (Zhang al. 2019). To cir- cumvent these issues, a common approach to drop the central coordinator and allow information al., 2021).
exchange between agents (Zhang et al. 2018 2019
Decision- makinn that involves multiple agents often modeled as a game and studied under the lens of game theory to describe the learning outcomes Herein, we consider games with leader- follower structure in which players act consecutively. For two players, such games are known as Stackelberg games (Hicks) 1935). Stackelberg games have been used to model diverse learning situations such as airport security (Balcan et al. (2055), poaching (Sessa et al. (020). tax plan- ning (Zheng et al.) 2020), and generative adversarial networks (Moghadam al. (021). In Stack- elberg game, one is typically concerned with finding the Stackelberg equilibrium, sometimes called Stackelberg-Nash equilibrium, in which the leader uses mixed strategy and the follower is best- responding. A Stackelberg equilibrium may be obtained by solving bi-level optimization problem the reward functions are known (Schäfer et al. 2020 Aussel & Svensson 2020) or, otherwise, may be learnt via online learning techniques (Bai et al. 2021; Zhong et al. 2021). e.g., no-regret algorithms (Shalev-Shwartz) 2012 Deng et al. 2019 Goktas et 2022).
No-regret algorithms have emerged from the single-player multi-armed bandit problem means trade-off (Bubeck Slivkins 2012). An algorithm is called
to alleviate the exploitation-exploratee no-regret if the difference between the cumulative rewards of the learnt strategy and the single best action in hindsight is sublincar in the number of rounds Schalev-Swwarr 2012). In the multi-armed bandit problem, rewards may be adversarial (based on randomness and previous actions), oblivious adversarial (random), or stochastic (independent and identically distributed) over time (Auer et al., 2002). Different assumptions Indeed, algorithms tailored for one kind of rewards are sub-optimal for others, e.g., the EXP3 al- gorithm due to Auer et al. (2002) yields the optimal scaling for adversarial rewards but not for
the bandit rewards yield different algorithms and regret bounds.
'The convention is to use agents in learning applications and players in game theoretic applications, shall the game-theoretic nomenclature in the remainder of the paper.

---

Under review as a conference paper at ICLR 2023
stochastic rewards. For this reason, best-of-two-worlds algorithms, able to optimally handle both the stochastic and adversarial rewards, have recently been pursued and resulted in algorithms with close to optimal performance in both settings (Auer & Chiang 2016 Wei & Luo| 2018 Zimmert & Seldin 202T). Extensions to multiplayer multi-armed bandit problems have been proposed in which players attempt maximize the sum of rewards by pulling an arm each, see, e.g.. (Kalathil al.
2014 Bubeck et al. 2021).
No-regret algorithms are a common element also when analyzing multiplayer games. For example, in continuous two-player Stackelberg games, the leader strategy, based on a no-regret algorithm, converges to the Stackelberg equilibrium if the follower is best-responding (Goktas et al. 2022). In contrast, if also the follower udopts a no-regret algorithm, the regret dynamics is not guaranteed to converge to a Stackelberg equilibrium point (Goktas et al. 2022 Ex. 3.2). (Deng et al. 2019).
based it was shown for two-player Stackelberg games that follower playing a, so-called, no-regret algorithm, enables the leader to achieve reward strictly larger than the reward achieved at the Stackelberg equilibrium. This result does, however, not generalize to n-player games as demonstrated by DD' Andrea (2022). Apart from studying the Stackelberg equílibrium, several papers have analyzed the regret. For example. (Sessa et al. (2020) presented upper- boper-bounds on the regret of a leader, employing a no-regret algorithm, playing against an adversarial follower with an unknown response function. Furthermore, Stackelberg games with states were introduced by Lauffer et al. 2022) along with an algorithm that was shown to achieve no-regret.
As the follower in Stackelberg game observes the leader's action, there is information exchange. A generalization to multiple players has been studied in a series of papers (Cesa-Bianche et al. 2016)] 2020 2021). In this line of work, players with common action space form an arbitrary graph and are randomly activated in each round. Active players share information with their neighbors by broadcasting their observed loss, previously received neighbor losses, and their current strategy. The goal of the players is to minimize the network regret, defined with respect to the cumulative losses observed by active players over the rounds. The players, however, update their strategies according to their individually observed loss. Although we consider players connected on a graph, our work et al.) 2016; 2020 202I), c.g., we allow only actions to be
differs significantly from observed between players and player strategies are updated based on common bandit reward.
Contributions: We introduce the joint pseudo-regret, defined with respect to the cumulative re- ward where all the players observe the same bandit-reward in each round. We provide online for general consecutive for the single-player multi-armed bandit problem. The main novelty of our contribution resides in the joint analysis of players with coupled rewards where we derive upper bounds on the joint pseudo- regret and prove our algorithm be no-regret in the stochastic and adversarial setting. Furthermore, we quantify the penalty incurred by our decentralized setting in relation to the centralized setting.
games that relies on no-regret algorithms developed
2 PROBLEM FORMULATION
In this section, formalize the consecutive structure of the game and introduce the joint pseudo- regret that will be used as a performance metric throughout. We consider a decentralized setting where, in each round of the game, players pick actions consecutively. The consecutive nature of the game allows players to observe preceding players' actions and may be modeled by a DAG. For example, in Fig. T a seven-player game is illustrated in which player 1 initiates the game and her action is observed by players2 2, 5, and 6. The observations available to the remaining players follow analogously. Note that for a two-player consecutive game, the DAG models a Stackelberg game.
We let G (V.E) denote DAG where V denotes the vertices and È denotes the edges. For our setting, V constitutes the different players and & = ((j,4) j + i E V, E V) describes the ob- servation structure where - i indicates that player observes the action of player j. Accordingly, a given player i E V/ observes the actions of its direct parents, i.c., players j E E, = (k- : (k, i) E E). Furthermore, each player E V is associated with discrete action space A, of size A, We denote by (t). the mixed strategy of player over the action space A, in round E [T] such that (t( = with probability Pi,a for a E A.. In the special case when Pi.a referred to as pure. Let.At Ag denote the joint action space of players in a set B given by the Cartesian product Ag = Ileg A;. If player i has no parents, i.e., &, = 0, we use the convention AAg = 1.
for some E A,, the strategy is
2

---

Under review as a conference paper at ICLR 2023
We consider collaborative setting with bandit rewards given by mapping ra Av [0. 1] in
each round E [T'. The bandit rewards may be either adversarial or stochastic. Let C denote a set
of independent cliques in the DAG (Koller & Friedman, 2009 Ch. 2) and let N₁. C for & [[]]]
denote the players in the kth clique in C with joint action space AN, such that Wy NW 0 for
j * k. For joint action a(t) Av, consider bandit rewards given by linear combination of the clique-rewards as
|c| ((((t)) = _ (P
(1)
where r AA.. + [0. 3. 2 0 is the weight of the kth clique reward such that > 8x 1, and pk (a(t)) denotes the joint action of the players in Mi. As an example, Fig. lb highlights the cliques {f2, 3, 4), (1, 5), (6), {7}} and we have, e-g. Ni (2,3,4] and (a(t))
(tz(t), at(t), (t)). Note that each player influences only single term in the reward
5
(a) A game with seven players.
(b) Colored cliques comprising the bandit reward.
Figure 1: Game and reward structures.
In each round t E [T], the game proceeds as follows for player i E V: 1) the player is idle until the actions of all parents in & have been observed, 2) the player picks an action at) E A; according to its strategy (1). 3) once all the players in V have chosen an action, the player observes the bandit reward ry (a(t)) and updates its strategy. The goal of the game is find policies {t(( that depend on past actions and rewards in order to minimize the joint pseudo-regret R(T) which is defined similarly to the pseudo regret Sshale-Shwarrl
2012 Ch. 4.2) as
T
T
R(T) = r(a*) - E
Σ
r(a")= = max E aEAD
Σ re(a)
(2)
where the expectations are taken with respect to the rewards and the player actions Note that r(at) corresponds to the largest expected reward obtainable if all players use pure strategies. Hence, the pseudo-regret in (2) quantifies the difference between the expected reward accumulated by the learnt strategies and the reward- -axaaadiimiiiiiinggggmam pure strategies in hindsight.
Our problem formulation pertains plethora of applications. Examples include resource alloca- tion in cognitive radio networks where available frequencies are obtained via channel sensing (Ja-) nntiian et al., 2015) and semi-autonomous vehicles with adaptive cruise control, i.e., vehicles ahead observed before action is decided (Marsden et al.) (001I. Also recently, the importance of coupled rewards and partner awareness through implicit communications, c.g., by observation, has been highlighted in human-robot and human-Al collaborative settings (Bıyık al. 2022).
As will be shown in the next section, any no-regret algorithm can be used as a building block for the games considered herein to guarantee sub-linear pseuee-regret in the number of rounds T. As our goal is to study the joint pseudo-regret (2) for both adversarial and stochastic rewards, we resort to best-of-two-worlds algorithms for the multi-armed bandit problem (Bubeck & Slivkins 2012). In particular, we will utilize the TSALLIS- INF algorithm that guarantees a close-to-opúmal pseudo- regret for both stochastic and adversarial bandit-rewards (Zimmert & Seldin (202I) Note that our analysis in the next section pertains to adversarial rewards; for stochastic rewards, our analysis apply verbatim by replacing Theorem by (Zimmert & Seldin 2021 Th. 4).
This is called pseudo-regret r(a") is obtained by maximization outside of the expectation.
3

---

Under review as a conference paper at ICLR 2023
3 ANALYSIS OF THE JOINT PSEUDO-REGRES
Our analysis of the joint pseudo-regret builds upon learning algorithms for the single-player multi- armed bandit problem. First, let build intuition on how use a multi-armed bandit algorithm in the DAG-based game described in Section 2 Consider a 2-player Stackelberg game where the players choose actions from A1 and A2, respectively, and where player observes the actions of player 1. For simplicity, we let player use mixed strategy whereas player 2 is limited to a pure strategy. Furthermore, consider the rewards to be a priori known by the players and T for which the Stackelberg game may be viewed 2020). In this setting, the action of player imposes a Nash game on player 2 whom attempts to play optimally given the observation. Hence, player 2 has A₁ pure strategies, one for each of the A actions of player 1.
bi-level optimization problem (Aussel & Svensson,
We may generalize this idea to the DAG-based multiplayer game with unknown bandit-rewarde and 2 1 to achieve no-regret. Indeed, a player V may run |Ag, different numti--rmmd bandit algorithms,, one for each of the joint actions of its parents. Algorithm illustrates this idea in conjunction with the TSALLIS-INF update rule introduced by [Zimmert & Seldin (202T). which is given Algorithm for completeness runs single multi- multi-armed bandit algorithm whereas the follower runs A₁ learning algorithms. For simplicity, Algorithm D assumes that player i knows the size of the joint action space of its parents, i.e., | Dropping this assumption is straightforward: simply keep track of the observed joint actions and initiate a new multi-armed bandit learner upon a unique observation.
particular, for the 2-player Stackelberg game, the leader
Algorithm Learning algorithm of player E V
Note: for ease of notation, let the actions Ag, be labeled as 1,2, AAE
1: procedure
2: initialize cumulative rewards L, < 0 E & for j [|A&,1]]
3: initialize fixed-point zÿ +- 0 for all E [|Ae,]]
4: initialize counter n; t- for all j E [|.4g,1]
5: for t 1,2,... ..... T' do
6:
observe the joint action j E [|Ae, | of the preceding players
7:
increase counter ny n2 + obtain new strategy and new fixed-point (x;) < TSALLJS-INF(n,,...
8:
9:
play action (t) (t)
10:
observe the joint bandit-reward ri (a(())
update the cumulative loss Lg + L, =)((Lr((((t))/p for [A,] 12: end for
13:
end procedure
Algorithm Strategy update for player i E V
Input time step 6, cumulative rewards L E RA previous fixed point æ Output strategy (T))), fixed point
1:
procedure TSA
2: set learning rate 7) + 2/11t
3: repeat
4:
Pj <- 4(1(L, - x)) for all j [At]
5: x - x E 12:11-10 11 1) E 3/2)
6: until convergence
7: update strategy (t) + (p1.... PA.)
8:
end procedure
Next, go analyze the joint pseudo-regret of Algorithm I pseudo-regret for the single-player multi nulti-armed bandit problem that will be used throughout.
First, we present result on the
'The original TSALLJS-INF Algorithm is given in terms of losses. To use rewards, one may simply use the relationship --r.
4

---

Under review as a conference paper at ICLR 2023
Theorem (Pseudo-regret of TSALLIS-INE) Consider single-player multi-armed bandit prob- lem with A1 arms, played over T rounds. Let the player operate according to Algorithm 7 Then, the pseudo-regret satisfies
R(T) ATT
Proof. For single player, & = 0 and we have LAg = by convention. Hence, our setting becomes equivalent to that oimmietrt Seldin (2021 Th and the result follows thereof.
Next, we consider two-player Stackelberg game with joint bandit-rewards defined over two- player clique. We have the following upper bound on the joint pseudo-regret.
Theorem (Joint aseudo-regret over cliques of size 2). Consider a 2-player Stackelberg game with bundit-rewards, given by 77). defined over a single clique containing both players. Furthermore, let Then, the joint aseudo-regre satisfies
each of the players follow Algorithm 7
R(T) & A 4/ A,T +1
Proof. Without loss of generality. let player 2 observe the actions of player 1. Let a1 a1 A and (1) E A denote the actions of player and player 2, respectively, at time E [T] and let af and ag (a1) denote the swwrd-maximiziin pure strategies of the players in hindsight, i.e.,
aj arg
E
Σ (((o)))((a1))
a5(a1) arg
E
Σ (((a),2))
(3)
a
a.E
Note that the optimal joint decision in hindsight is given by (at, (z(a))). The joint pseudo-regret is given by
R(T) Σ E a(((1 (oloa(((())))((0(000000 o2((). (27,) (t,a
max E (raa(a,, (a:))) re(at, az (1)) + Fa(aj,a2(0) ( (1), (4) a,EA,
Next, let
a (t) arg max E [rr az(a:)) (r a2( a.E.1
and let T, = (t at (t) = a}. for E A,, denote all the rounds that player 1 chose action a and introduce T, = [Ta). Then, the first term in (4 upper-bounded as
Σ max [rrr az(a:)) re(as, a2())) aeAd
Σ
Σ
E E(ri(a,az(a)) a2)))
TET
Σ WATT +1
(5)
aeA:
< max
Σ
4v A2Ta +1
Σ. T==T
aελr
=4 44/ + A
(6)
where (5) follows from Theorem 1 and because player 2 follows Algorithm
Next, we consider the second term in (4) Note that, according to 3 of obtained from the optimal pure strategies in hindsight of both the players. Let
T
ai = arg max
E (11, (2))
E.A.
5

---

Under review as a conference paper at ICLR 2023
and observe that Ex= ri(ai,ar at))
E rr(as, (t))) Hence, by adding and sub-
tracting a2()), the second term in
we get
T
IE
Σ ri 02(()) ((())))()))((((())))))))))))))))
SE
Σ relaf, a2(1))
- (((())((((((
A
where the last equality follows from Theorem
[ The result follows from (6) and
From Theorem 2 we note that the joint pseudo-regret scales with the size of the joint action space as R(T) Ol A2T)). This expected as centralized version the cooperative Stackelberg game may be viewed as a single-player multi-armed bandit problem with A A2 arms where, accord- ing to Theorem 1 the pseudo-regret is upper-bounded by Av A27 + Hence, from Theorem 2 observe penalty of 4vA,7 + A1 due to the decentralized nature of our setup. Moreover, in the centralized setting, Algorithm was shown in Zimmert & Seldin (202I) to achieve the same scaling the lower bound in Cesa Bianchi & Lugosi (2006) Th. 6.1). Hence, Algorithm I achieves the optimal scaling. Next, we extend Theorem 2 cliques size larger than two.
Theorem (Joint pseudo-regret over a clique of arbitrary size). Consider DAG-based game with bandit rewards given by ( defined over single clique containing players. Let each of the players operate according Algorithm 7 Then, the joint pseudo-regre satisfies
R(T) S 4
A
Σ
Il 1=1
A + 1.
k=1
Proof. Let (T, m. denote an upper bound on the joint pseudo-regret when the bandit-reward defined over clique containing m players. From Theorem and Theorem [ have that
Rub (T, A, +1
Rub (T,2) = 4v AT + +4V A,AT + A +1,
respectively. Therefore, we form an induction hypothesis as
77
RTb 4
A
ΣI A +
II
Assume that (8) is true for clique containing m - players and add an additional player, assigned player index whose actions are observable the original m 1 players. The m players now form clique C of size m. Let (t)) E Ac denote the joint action of all the players in the clique time Acvi denote the joint action
t E [T] and let (t) (a1 (t), ..., a4-1((1 1t) 1 (t)...,,, excluding the action of player Furthermore, let
a = max E E.A)
Σ re(as, at a²)
a²_ (01) arg
E aEAcy
a))
denote the optimal actions in hindsight of player 1 and the optimal joint action of the original m players given the action of player 1, respectively. The optimal joint action in hindsight is given as

---

Under review as a conference paper at ICLR 2023
a' = (aj, a"]]a) Following the steps in the proof of Theorem verbatim, obtain
T
R(T)
Σ
E [[r((a)) - re(a a 11)) r. (a(t))
1=1
max E (r
a a +
E (1)(()))_00)))((((()))))))a
01
1=1
[re(a, a", rr Σ
E a a.)0)))a.)))))))))))))))))))))))
tETo
Σ BEAr
(ab m 1) 4v A,7 +1
S (
A1T
where Tap Ta and af are defined analogously in the proof of Theorem 2 By using the induction hypothesis (8) in (9) and by accounting for the original players being indexed from 2 to
we obtain
m-
R(T) A
4 ATTTA EI
A
Ak II k=2
+ 4v 4V AT Rub((T m)
k=
which is what we wanted to show.
As in the two-player game, the joint pseudo-regret of Algorithm Jachiees the optimal scaling, i.e., R(T) = O(VT VA,), but exhibits penalty due to the decentralized setting which is equal 4v ATT Ih VAx -m 2 Ag.
Up until this point, we have considered the pseudo-regret when the bandit-reward ( is defined over single clique. The next theorem leverages the previous results provide upper bound on the joint pseudo-regret when the bandit-rewars is defined over an arbitrary number of independent cliques the DAG.
Theorem 4 (Joint pseudo-regret in DAG-based games). Consider a DAG-based game with bandit rewards given as in ( and ler contain a collection of independent cliques associated with the Then, the joint pseudo-regret satisfies
DAG. Let each player operate according to Algorithm 7
((T)=O((
(V"
R(T)= =
R(T)
max REI
LANe
where AN, denotes the joint action-space of the players in the kth clique No. C.
Proof. Let Ng E C denote the players belonging to the kth clique in C with joint action space Ave- The structure of ①I allows us express the joint pseudo-regret as
CCI
R(T) E Σ re(a*) ro(a(t))
<
B
r (at) r rF(P
(10)
where
T
a² = arg max E aEAAv
r((a)
a = arg max E aEAN:
Σ
r
Now, for each clique Ag C. let the player indices in No. be ordered according to the order of player observations within the clique. As Theorem holds for any N₁ E C. we may, with a slight abuse of notation, bound the joint pseudo-regret of each clique
and the inequality follows since Σn (P*(t)))) S Σn= rf (at)
C
R(T)
Bub (T..BaaTTMMr (T, < max Rub (T, kE|[C]]
7

---

Under review as a conference paper at ICLR 2023
where NVx follows from Theorem 3as
as
Rab(T.Wa) = 4VT
Σ
II
VA
VA + Σ
II
A
KEN& JSUJEN,
VENE JSiJEN,
where N excludes the last element in, Ma. The result follows as (ab(T.Na) O(VT)AN)) 0
4 NUMERICAL RESULTS
The experimental setup in this section is inspired by the vecio-economic simulation in (Zheng et al. 2020 We consider simple taxation game where one player acts as a socio-economic planner and the remaining M players act workers that earn income by performing actions, e.g., constructing houses. The vocio-economic planner divides the possible incomes into brackets where [3,-1. 1, S,] In each round t [T', the socio-cconomic planner denotes the ith bracket with Bo and BN (t)) that determines the taxation rate where (p.s(t) E R; picks an action (t) = (t), (t)...., dp.N
denotes the the marginal taxation rate in income bracket i and R; is finite set. We use the discrete
set Ap = I R. of size Ap to denote the action space of the planner.
In each round, the workers observe the taxation policy (f) E Ap and choose their actions consec- utively, see Fig. 2al Worker
[MM] takes actions (t(t) Aj where Aj a finite set. A chosen consisting
action (t) E A, translates into a tuple
gross income and a marginal default labor cost, respectively. Furthermore, each worker has skill level 8, that serves sor of the default labor, resulting in an effective marginal labor (t(t) (t)//s,, Hence, given common action, high-skilled workers exhibit less labor than low-skilled workers. The gross income xr (1) worker j in round / taxed according to (1) as
divi-
N
(tr, = Σ -
> + (2, (1000)-B-111) (zz)) E 18:-1.811
where (1) is the taxation rate of the ith income bracket and {(xr(()) denotes the collected tax. Hence, worker j's cumulative net income z, and cumulative labor (() in round are given as
(t)
Σ 2 (())(1)), u=1
t = Σ (().
In round f, the utility worker j depends on the cumulative net income and the cumulative labor as
(,, (z,(1))=~ (t)
(11)
-
where 17 >> 0 determines the non-linear impact of income. An example of the utility function in (I1) shown in Fig. 2b for 7 0.3, income (t) 10, and a default marginal labor (t) different skill levels. It can be seen that the utility initially increases with income until point at which the cumulative labor outweighs the benefits of income and the worker gets burnt out.
We consider bandit-rewards defined with respect to the worker utilities and the total collected tax as
M
M
re(a,((), 01 (1),... (n) = (M +1)
Σ (=,((,())))0)) + up Σ E(ms(1) j=1
(12)
f=1
where the weights trade off worker utility for the collected tax and satisfy Mw + Wp = M + The individual rewards are all normalized to [0, 1], hence, re(aa((), 0n (I)....,aM)
E [0.
For the numerical experiment, we consider N = income brackets where the boundaries of the income brackets are {0, 14, 2o) } and the socio-cconomic planner chooses marginal taxation rate from R = {0.1, 0.3, 0.5} in each income bracket, hence, Ap = 9. We consider M = workers
'The source code of our experiments is available on bandi cendit__pttii mi zat an_dag-222c7
wwrrrrouuss......eee...... 4open sci ence/r/
8

---

Under review as a conference paper at ICLR 2023
1,000
Socio-economic planner
2
worker utility
800
3
600
400
200
0
10
10'
10a
10
10
workers
houses built
(a) Socio- cetoomccoomic setup with players among (b) Example of utility functions for different skill which 3 are designated workers.
levels when (t()) 10 and (, = 1.
Figure 2: Socio-economic setup.
with the same action set of of size 3. Consequently, the joint action space is of size 243. Furthermore,
we let the skill level of the workers coincide with the worker index, i.e., = for j E [M]. Simply, gross marginal
workers able observe others have higher skill. The worker actions translate income and a marginal labor as aI()) + (1), where x, (() 5l)(() and (((() = (1)//83
for (4) E (1,2,3) 3). Finally,
1 0.3 and let w 1/M and w, M to model situation where the collected tax is preferred over workers' individual utility.
The joint pseudo-regret the socio-cconomic simulation illustrated in Fig. Bi with the upper bound in Theorem 4 We collect 100 realizations of the experiment and, along with the pseudo-regret R(T), two standard deviations are also presented. can be seen that the players initially explore the action space and are able to eventually converge on an optimal strategy from a pseudo-regret perspective. The upper bound Fig. is admittedly loose and does not exhibit the same asymptotic decay as the simulation due to different constants in the scaling law, see Fig. 3b However, it remains valuable as provides an asymptotic no-regret guarantee for the learning algorithm.
0.5
102
Upper hound
Upper hound
.R(2)
0.4
10
0.3
10a
Regret
Regret
10
10-3
10P
10
10P
10a
(a) Linear scale.
(b) Log-scale.
Figure 3: Pseudo regret vs the upper bound in Theorem
CONCLUSION
We have studied multiplayer games with joint bandit-rewards where players execute actions con- secutively and observe the actions of the preceding players. We introduced the notion of joint pseudo-regret and presented an algorithm that is guaranteed to achieve no-regret for both adversarial and stochastic bandit rewards. A bottleneck of many multi-agent algorithms is that the complexity scales with the joint action space (Jin et al.) 2021) and our algorithm is exception. An interesting venue further study is to find algorithms that have more benign scaling properties, see e.g., (Jn
et al. 2021 Daskalakis al. 202T

---

Under review as a conference paper at ICLR 2023
REFERENCES
Peter Auer and Chao-Kai Chiang. An algorithm with nearly optimal pseudo-regret for both stochas- tic and adversarial bandits. In Proceedings of the 29th Annual Conference on Learning Theory (COLT), 2016.
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multi- armed bandit problem. SIAM Journal on Computing, 32(():48-777 -7,888777778 2002.
Didier Aussel and Anton Svensson. A short state the art on multi-leader-folloeer games. In Bilevel Optimization. Springer, Cham, Switzerland, 2020.
Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong. Sample-efficient learning of Stackelberg equilibria in general-sum games. In NeurlPS, 2021.
Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia. Commitment with- out regrets: Online learning in Stackelberg security games. In Proceedings of the 16th ACM Conference on Economics and Computation, 2015.
Sébastien Bubeck and Aleksandrs Slivkins. The best of both worlds: Stochastic and adversarial bandits. In Proceedings of the 25th Annual Conference on Learning Theory (COLT), 2012.
Sébastien Bubeck, Thomas Budzinski, and Mark Sellke. Cooperative and stochastic multi-player multi-armed bandit: Optimal regret with neither communication nor collisions. In Proceedings of the 34th Annual Conference on Learning Theory (COLT), 2021.
Erdem Bryik, Anusha Lalitha, Rajarshi Saha, Andrea Goldsmith, and Dorsa Sadigh. Partner-aware algorithms in decentralized cooperative bandit teams. In The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI), 2022.
Nicolò Cesa-Bianchi Claudio Gentile. Yishay Mansour, and Alberto Minora. Delay and cooperation in nonstochastic bandits. In the 29th Annual Conference on Learning Theory (COLT), 2016.
Nicolò
Tommaso Cesari, and Claire Monteleoni. Cooperative online learning: Keep- ing your neighbors updated. In the s1 International Conference Algorithmic Learning Theory (ALT), 2020.
Nicolò
Tommaso R. Cesari, and Riccardo Della Vecchia. Cooperative online learning with feedback graphs, 2021. arXiv:2106.04982.
Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, Cambridge, UK, 2006.
Maurizio D' Andrea. Playing against no-regret players, 2022. arXiv:2202.09364,
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. In NeurIPS, 2021.
Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. In NewrIPS, 2019.
Denizalp Goktas, Jiayi Zhao, and Amy Greenwald. Robust no-regret learning in min-max Stackel- berg games. In The AAAI-22 Workshop on Adversarial Machine Learning and Beyond, 2022.
J. R. Hicks. Marktform und gleichgewicht. The Economic Journal, 45(118):334-336, 1935.
Nafishh Janatian, Mahmoud Modarres-Hashemi, and Sumei Sun. Sensing- based resource allocation in multi-channel cognitive radio networks. In the IEEE Symposium on Communications and Vehicular Technology (SCVT), 2015.
Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learnin simple, efficient, decen- tralized algorithm for multiagent RL, 2021. 1tXiv:2110.14555
Dileep Kalathil, Naumaan Nayyar, and Rahul Jain. Decentralized learning for multiplayer multi- armed bandits. IEEE Transactions Information Theory, 60(4):2331-2335, 2014.
10

---

Under review as a conference paper at ICLR 2023
Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques Adaptive Computation and Machine Learning. The MIT Press, Cambridge, MA, USA, 2009.
Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu. No-regret learn- ing in dynamic Stackelberg Games, 2022. arXiv:2202.04788.
G. Marsden, M. McDonald, and M. Brackstone. Towards an understanding adaptive cruise con- trol. Transportation research Part C: Emerging Technologies, 91):33--11, 2001.
Monirch Mohebbi Moghadam, Bahar Boroomand, Mohammad Jalali, Arman Zareian, Alireza Daci- Javad, Mohammad Hossein Manshaci, and Marwan Krunz. Game of GANs: Game- Theoretical Models for Generative Adversarial Networks, 2021. arXiv:2106.0697
Florian Schäfer, Anima Anandkumar, and Houman Owhadi. Competitive mirror descent, 2020.
arXiv:2006.10179
Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, and Andreas Krause. Learning to play sequential games versus unknown opponents. In NeurlPS, 2020.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
Chen-Yu Yu Wei and Haipeng Luo. More adaptive algorithms for adversarial bandits. In Proceedings of the 31st Annual Conference On Learning Theory (COLT), 2018.
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theo- retical perspective, 2020. arXiv:201 11.00000000 1.00583.
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents. In Proceedings of the 35th International Conference on Machine Learning ICML), 2018.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selec- tive overview of theories and algorithms. In Handbook of Reinforcement Learning and Control. Springer, Cham, Switzerland, 2019.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C. Parkes, and Richard Socher. The Al economist: Improving equality and productivity with AI-driven tax policies, 2020. arXiv:2004.13333
Han Zhong, Zhuoran Yang. Zhaoran Wang, and Michael I. Jordan. Can reinforcement learning find Stackelberg Nash equilibria in general-sum Markov games with myopic followers?, 2021. 122iv:2112.135211
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. Journal of Machine Learning Research, 22(28):1 140 2021.


Reviews:
[{"review_id": "p0uq7d6A8Wd", "reviewer": "Reviewer_uQZP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers a decentralized multiplayer game with a leader-follower hierarchy described by a directed acyclic graph. It proposes a cooperative learning algorithm and proves that the algorithm achieves sub-linear joint pseudo-regret for both adversarial and stochastic bandit rewards. ", "summary_of_the_review": "The paper considers a decentralized multiplayer game with a leader-follower hierarchy described by a directed acyclic graph. It proposes a cooperative learning algorithm and proves that the algorithm achieves sub-linear joint pseudo-regret for both adversarial and stochastic bandit rewards. The paper is well written. The results are novel and interesting. The possible applications for the proposed setting is a bit vague. ", "strength_and_weaknesses": "+ The paper considers a novel decentralized online bandit optimization setting, motivated by cooperative Stackelberg game. \n+ The paper is well written. The results are novel and interesting.\n\n-  The possible applications for the proposed setting is a bit vague. \n-  Although a few theorems are presented, Theorem 4 is the most general one which covers the previous ones.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KE-Fm_Jdwnx", "reviewer": "Reviewer_8PKf", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies decentralized bandits on a DAG. In this model, the players perform actions consecutively and observe the actions of the preceding players. The paper proposes a novel algorithm for this model and achieves sublinear regret for both stochastic and adversarial rewards.\n", "summary_of_the_review": "Though the studied model is novel, many details should be clarified (see weaknesses). Also, both theoretical and empirical contributions are a bit below the bar.", "strength_and_weaknesses": "Strength:\n\nThe studied model is novel. The proposed algorithm achieves sublinear regrets.\n\nWeaknesses:\n\n1. The motivation of the studied model is not clear. Why do players have to execute actions consecutively? Why does the model consider the linear combination of the clique-rewards rather than all players' rewards? I suggest authors provide some real applications for the proposed model.\n2. I'm confused about the definition of the independent clique in the DAG. I do not find the corresponding definition in (Koller & Friedman 2009, Ch.2). To increase the paper's readability, I suggest the authors provide the independent clique's definition.\n3. I'm also confused about inequality (5). Notice that Theorem 1 requires the player to play T consecutive rounds. However, the rounds in the set $T_a$ are not consecutive. Thus (5) cannot be obtained by Theorem 1 directly. Am I right?\n4. Tsallis-INF can achieve log(T) regret for stochastic rewards, but the proposed methods do not achieve log(T) regret in the stochastic setting.\n5. The technical contribution is not strong enough. Most analyses are straightforward and the results are not surprising.\n6. The authors only perform experiments on the graph with one clique. It would be better if the authors could provide numerical results on various connection graphs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CwgG0t-NO5", "reviewer": "Reviewer_ibWi", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the regret bound of multi-player online bandit problems with a leader-follower (directed graph) hierarchical structure. To be specific, there are n players in total and a directed graph G, and for any two players with j having an out-edge to i, player i will observe the action of player j and take actions after player j. The reward is taken according to the joint actions taken all the players and can be either stochastic or adversarial. \nWith the above problem, the authors propose an algorithm, and proved the upper bound for single player and multi-players. For the single-player case, the regret upper bound is O(\\sqrt{AT}) where A is the number of actions of this player and T is the time horizon, which I believe is optimal (up to a constant factor) as the regret bound's order is the same as the standard MAB problem. For multiple-player cases (n > 1), the regret is of order O(\\sqrt{T\\sum{A_i}}) where A_i is the action space (number of joint actions) of the i-th clique. \nFinally the authors did some numerical simulations for the algorithm, and the results look consistent with the theory.", "summary_of_the_review": "This paper studies an interesting and novel problem, and proposes an algorithm with good regret performance. The algorithm looks not trivial and the regret results are well supported by mathematical proofs. So I tend to vote an accept.", "strength_and_weaknesses": "Strengths: The graph-structure bandit problem studied in this paper is interesting and meaningful, and I am convinced that it is a missing part of the literature and can found potential applications in the real-world systems. This paper gives an algorithm with reasonable regret upper bounds, which I think is optimal or near optimal (ignoring constant factors). \n\nWeakness: It is not sure whether the algorithm proposed in this paper is close to the lower bound. It will be much better if there can be analysis on the lower bound. Also, the numerical simulations are of small scales, but I think many real-world scenarios (such as communication networks) should have much larger scales. It will strengthen the paper a lot if there can be more large-scaled simulations.  \n\nMinor: Also wonder if the algorithm proposed in this paper can work only using local information. The step observing the reward seems to be costly in terms of communication in a large scale. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0hr89HvSPU", "reviewer": "Reviewer_fbii", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper formulates a problem of decentralized online bandit optimization on directed graphs, in which the graph structure dictates the order of the players and how players observe the actions of other players. Moreover, all players can observe a joint bandit reward, which is a linear combination of the reward of each clique in the graph. To solve this problem, the authors make an extension of an existing single-player multi-armed bandits algorithm and established upper bounds for the joint pseudo-regret.", "summary_of_the_review": "The main contributions of this paper include a new bandit setting and a corresponding algorithm with pseudo-regret bounds. However, the writing of this paper should be improved, and the novelty of this paper seems to be limited. So, I tend to reject this paper.", "strength_and_weaknesses": "1) The proposed problem of decentralized online bandit optimization on directed graphs seems to be interesting.\n2) The proposed algorithm is equipped with upper bounds on the joint pseudo-regret and its performance is partially verified by experimental results.\n\n#Weaknesses\n1) According to Algorithm 1, each player can observe the joint bandit reward, which may be unrealistic in the decentralized setting. \n2) As in Eq. (1), the authors consider a joint bandit reward, in which each clique reward has a weight. However, according to Theorem 3, the upper bound of the proposed algorithm actually does not depend on the weight. There seem to be two possible explanations. First, weight is not important. Second, the proposed algorithm cannot reflect the importance of weight. \n3) According to the analysis of this paper, it seems that it is not difficult to extend the algorithm and theory of Zimmert & Seldin (2021) into the problem in this paper, which limits the novelty of this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject