Multiplayer Information Asymmetric Contextual Bandits
Authors: William Chang
Yuanhao Lu
Venue: Accepted by TMLR ()

Abstract: Single-player contextual bandits are a well-studied problem in reinforcement learning that has seen applications in various fields such as advertising, healthcare, and finance. In light of the recent work on information asymmetric bandits, we propose a novel multiplayer information asymmetric contextual bandit framework where there are multiple players each with their own set of actions. At every round, they observe the same context vectors and simultaneously take an action from their own set of actions, giving rise to a joint action. However, upon taking this action the players are subjected to information asymmetry in (1) actions and/or (2) rewards. We designed an algorithm mLinUCB by modifying the classical single-player algorithm LinUCB in \cite{chu2011contextual} to achieve the optimal regret $O(\sqrt{T})$ when only one kind of asymmetry is present. We then propose a novel algorithm ETC that is built on explore-then-commit principles to achieve the same optimal regret when both types of asymmetry are present.

Published in Transactions on Machine Learning Research (03/2025)
Multiplayer Information Asymmetric Contextual Bandits
William Chang
chang314 Gg. ucla edu
Deportment of Mathematics, UCLA, Los Angeles, CA, USA
Yuanhao Lu
terrylu@princetonn.de edu
Princeton University, Princeton, NJ, USA
Reviewed on OpenReview: https: // openreview. pet/formm? id=nMCJ88F94B
Abstract
Singlo-player contextual bandits are a well-studied problem in reinforcement learning that has seen applications various fields such as advertising, healthcare, and finance. In light of the recent work on information asymmetric bandits Chang et al. (2022); Chang and Lu (2023), we propose a novel multiplayer information asymmetric contextual bandit framework where there multiple players each with their own set of actions. At every round, they observe the same context vectors and simultaneously take an action from their own set of actions, giving risc to a joint action. However, upon taking this action the players are subjected to information asymmelry in (1) actions and/or (2) rewards. We designed an algorithm LinUCB by modifying the classical single-player algorithm LinUCB in Chu et al. (2011) to achieve the optimal regret O(VT) when only one kind of asymmetry is present. We then propose novel algorithm ETC that is built on pollor-then-commiee principles to achieve the same optimal regret when both types of asymmelry are present.
1 Introduction
The problem of Multi-armed Bandits (MAB) is one of the most well-studiod classic reinforcement lcarning problems. The algorithms in the field designed to find an optimal balance between the exploration- exploitation tradeoff dilemma. In the traditional setting of this problem, single agent chooses one action (arm) from m available actions over numerous itcrations, where each action gives off reward sampled from some unknown sub- Gabbsanssian distribution. The primary objective is to minimize the agent's regret, defined as the difference between the expected reward of the agent's 's chosen actions and that of the optimal actions. Thus, the success of policy can be measured by the regret as a function of time (number of actions taken). Under this classical setting, Lai and Robbins (1985) showed that no policy can achieve better than O(VT) regret. The UCB algorithm first attains this lower bound.
Although single-player MABs are well-studied, they fail to model more complex real-world problems involving multiple participants. Recently, there has been escalating interest in cooperative multiplayer MAB challenges, wherein several agents aim to maximize their aggregate expected returns collaboratively Chang and Lu (2023); Chang et al. (2022); Wang et al. (2020); Brânzei and Peres (2021); Pacchiano et al. (2023). Although these problem settings extend the MAB problems into multiple players, they still remain restrictive in real- world applications in these three aspects:
(1) These settings do not model the agents' access to information that might help agents predict the reward quality of an action (i.e no context vectors).
These settings assume the rewards obtained by each player independent of the actions taken by other players (i.e. joint actions are not considered).
(3) These settings assume the agents can freely communicate their actions taken and rewards received to another (i.e. information is perfectly symmetric).

---

Published in Transactions on Machine Learning Research (03/2025)
To deal with restriction (1), prior works such as Chu et al. (2011) analyze the linear contextual bandit framework. Linear contextual bandits generalize the classical finite-armed MAB by allowing players to utilize side information to predict the quality of rewards. In each round of the contextual bandit problem, the agent observes one random context vector x per action, where the expectation of the reward distribution of that action a zero-mean noise plus the inner product of the context vector x and an underlying parameter I that unknown to the players.' This framework Chu et al. (2011) relaxes the aforementioned restriction (1) by allowing agents to make use of the observed context 0 to predict the rewards.
In this paper, address restriction (2) by extending the contextual bandit framework into a cooperative multiplayer setting where the joint action of all players determines the reward distribution. Furthermore, we add novel information asymmetry to make our setting even more general. At each round, each player takes an action individually and simultaneously resulting in a joint action. This joint action generates the rewards for all players. In every round, all agents observe the same context vectors (one context vector per joint action). This multiplayer extension relaxes restriction (2).
To restrict communication between players and relax restrictions (3), we separately consider the following two types of information asymmetries: (1) Action asymeetrry At each round, each player receives the same reward but cannot observe other player's actions (the joint actions remains hidden to the players). (2) Reward asymmelry - at each round, each player receives an ITD reward that can be only observed by themsel while they are allowed to observe the actions of other players. Although players cannot communicate during the learning process, they are aware of the possible actions other players can take and can agree on a strategy beforehand.
Our Contribution This is the first paper on multiplayer contextual bandits. We propose a multiplayer information asymmetric environment that was originally from the multi-armed bandit setting Chang et al. (2021); Chang and Lu (2023) and apply it to contextual bandits. We then propose two algorithms that are based on the single agent linear contextual bandit setting in Chu et al. (2011) called LinUCB. Remarkably, we show that by modifying LinUCB slightly, we obtain an algorithm that is able to take on both forms of information asymmettr, More specifically, through coordination scheme, we are able to recover the same regret bound O(VT) as in the single-agent sctting when the players receive the same reward but can't 't observe the other player's actions (Problem A). On the other hand, when the players receive their own IID reward but can observe the other player's actions (Problem B), we obtain the first sublinear regret bound of O(VT). Finally, when there are both types of information asymmetry (Problem C), we propose a new algorithm that involves principles in the classical Explore and then commit algorithm that achieves the same order regret bound.
Related Works The single-player contextual bandit with linear payoff functions is a well-studied problem with efficient algorithmic solutions Agarwal et al. (2014); Agrawal and Goyal (2013). There are many variants to the single-player linear contextual bandit setting such as Agrawal and Devanur (2016) and Badanidiyuru resource allocations. Furthermore, Bouneffouf
et al. (2014) which consider bandits with constraints et al. (2017) studies the problem with restricted context vectors, Allesiardo et al. (2014) analyzes contextual bandits that do not need hypothesis on stationary properties of contexts and rewards.
Linear contextual bandits have numerous real-world applications, encompassing healthcare, recommender systems, information retrieval, and risk management. For example, Durand et al. (2018) employs the contex- tual bandit framework to adaptively treat mice in the early stages of cancer. Li et al. (2010) and Bouneffouf et al. (2012) leverage contextual information to enhance mobile and news article recommendation systems. BounefToul et al. (2013) applies contextual bandits to optimize context-based information retrieval. Further- more, Soemers et al. (2018) utilizes contextual bandits to adaptively distinguish between fraud and concept drifts in credit card transactions. Within machine learning, Laroche and Féraud (2017) employs contextual bandits for algorithmic selection in off-policy reinforcement learning, while BounefTouf et al. (2014) integrates them to improve active learning.
18 is global and Independent of the actions. Moreover, 0 is inherent to the contextual environment and does not change in between rounds.
2

---

Published in Transactions on Machine Learning Research (03/2025)
We will now overview the literature on multiplayer bandits. Within the domain of multiplayer stochastic bandits, numerous studies permit restricted communication, as observed in prior research such as Martínez- Rubio et al. (2018; 2019); Szorenyi et al. (2013); Karpov et al. (2020); Tao et al. (2019). Recent studies, building upon the foundations laid by Chang et al. (2021), have delved into investigations of information asymmetry in the context of multiplayer bandits, as explored in works such as Mao et al. (2022); Kao et al. (2022); Mao et al. (2021); Kao (2022).
In cooperative multiplayer bandits, the objective is to determine the optimal arm from set of shared arms among players. The communication structure between players is represented by graph. This concept first introduced by Awerbuch and Kleinberg (2008). Since then, several strategies have been proposed, in- cluding e-greedy Szorenyi et al. (2013), gossip UCB Landgren et al. (2016), accelerated gossip UCB Martínez- Rubio et al. (2019), and leader-based approaches Wang et al. (2020). The problem has also been explored in an adversarial setting by Bar-On and Mansour (2019), who introduced a strategy where followers adopt the EXP3 algorithm. Another line of rescarch allows players to observe the rewards of their neighbors at each time step, based their relative positions in the graph Cesa-Bianchi et al. (2016). Additionally, some studies have considered asynchronous settings where only subset of players is active in each round Bonnefoi et al. (2017); Bisa-Biacchi et al. (2020). In the collision setting, when multiple players select the same arm, a collision occurs, preventing them from collecting rewards. This setting does not account for joint arms. An extension to the Lipschitz setting was explored in Proutiere and Wang (2019), where they introduced DPE (Decentralized Parsimonious Exploration), an algorithm designed to minimize communication while enabling players to maximize their cumulative rewards.
The concept of competing bandits was introduced by Liu et al. (2020). This model resembles the collision setting but incorporates player preferences. When multiple players select the same arm, only the highest- ranked player receives the reward. In this framework, a centralized CUB algorithm was proposed, where players communicate their UCB indices to a central agent. Cen and Shah (2022) demonstrated that log- arithmic optimal regret can be achieved if the platform also manages transfers between players and arms. Jagadeesan et al. (2021) further explored this by considering a stronger equílibrium notion, where agents negotiate these transfers. Liu et al. (2020) also introduced an ETC algorithm that attains logarithmic op- timal regret without requiring transfers, but assuming knowledge of the reward gaps. Sankararanan et al. (2021) extended this approach by climinating the need for such knowledge. Furthermore, Liu et al. (2021) proposed decentralized UCB algorithm incorporating a collision avoidance mechanism.
2 Preliminary
We consider information asymmetric contextual bandits, which is generalization of the single player setting given in Chu et al. (2011). In particular, they propose a UCB-index based algorithm LinUCB, and we propose a multiplayer version with joint arms of this algorithm.
In particular, we suppose there are m players, and each player can pick from a set of arms A,, For simplicity, we can assume that |A,| K although the case where each player has a different number of arms is easily generalizable (the coordination techniques still work as long as all the players know how many actions they have access to prior to learning). At every round f, each player will pick an arm from their action set without communication. This gives rise to juinl arm (which can be represented as vector of actions from each player) := A₁ x ... x Am and can be denoted as as which produces stochastic reward ft.a.. We will use bold to denote any quantity that is a vector. Given a joint action a we define the term corresponding action for player i to be the ith component in the vector a. We shall use T to denote the total number of rounds in the learning process. The collective goal of all the players is to maximize the total expected rewards up to horizon T.
Furthermore, at the start of each round, every player is given the same Km context vectors Dia E Rdd corresponding to each joint arm a E A. Suppose that each contextual vector at, satisfies || lle, < L. under the l norm. The reward that is produced from pulling joint arm a satisfies the linear realizability assumption, that is,
Elre,a [t,aaa (x 0*)
(1)
3

---

Published in Transactions on Machine Learning Research (03/2025)
for some 0 Rd. This means that in order to determine which arms have the best context it is desirable to have an accurate estimate of 0*
Let Or be the joint arm that is selected at round t. Furthermore, let ot be the best arm at round t. That is a; = arg a )*). To understand the success of a policy, we shall use the notion of regret Rr up to horizon T, defined as
T RT Σ (e,,0"
T Ft,a. 0*)
(Ii,a, 0")
( )-)= t=1
(2)
In Chu et al. (2011), they were able to prove that LinUCB attains O(vT) regret, which matches the lower bound for this problem. We can use the lower bound from the single agent setting but on the KM joint actions. We now state the information asymmetric problems we will be studying taken from Chang el al. (2022); Chang and Lu (2023). They are as follows (recall that all players receive the same contexts for all the joint actions each round).
Problem A: Information asymmelry in actions. At every round, after joint action is taken, the agents cannot observe the actions of the other players but all players receive the same rewards.
Problem B: Information asymmetry in rewards. At every round, after a joint action a is taken, agents only observe their own i.i.d. copy of the reward but they can observe the actions of other players.
Problem C: Information asymmetry in both actions and rewards. This combines the challenges in problem A and problem B where every round the players get their own i..d. reward (without sceing other players' rewards) and they cannol observe the actions laken by other players.
To be precise, in problems B and C, since each player obtains a different reward, we should use R2 to be the regret for player i. However as the distributions of the rewards have the same mean, and regret is defined under expectation, it follows that even in this setting each player experiences the same regret.
2.1 Challenges in the Contextual Bandit Setting
In this section we compare our work to that given in Chang et al. (2022). In their paper, they study the information asymmetry bandit problem for the classical arme bandit setting. For problem A, information asymmetry in only actions, all the players receive the same reward feedback but are unable to communicate as well as observe the other player's actions at each round. However, because they reccive the same reward feedback, they are to correctly infer the other player's actions then they are able to maintain the same UCB estimates of all the arms. Similarly, in the contextual bandit setting, they observe the same rewards as well as the same contexts. Thus, they are able to maintain the same estimate for 0* as well as the same confidence set. The novelty is constructing way to break ties when two arms have the same LinUCB index so that each player can accurately infer the correct action that is taken at the time step despite not being able to observe the actions of the other players. This is where Definition 1 plays a role in Algorithm 1.
On the other hand, problem B, which is information asymmetry in rewards is a bit more challenging. Since each player observes only their own IID copy of their reward, they will maintain different estimates of Ø* (and therefore have different confidence sets for this parameter as well). In the bandit's case studied in Chang and Lu (2023), this issue addressed using a UCB-interval algorithm, where initially all the arms were pulled in a predefined order. In that paper, each player maintains for each arm their own UCB-interval, and when two UCB intervals are disjoint the suboptimal arm gets climinated. However, such an climination method no longer applies lo the contextual bandit case because at every round the distribution of each arm changes in accordance with the context receives. However, we make this problem easier by assuming the context vectors are stochastically generated. This makes it casier for players coordinate their actions by simply improving their estimates of 0*, which can be done by pulling any joint arm. In comparison to the standard MAB, the empirical mean of the joint action only improved when that action is taken.
4

---

Published in Transactions on Machine Learning Research (03/2025)
3
Main Results
3.1 LinUCB
We describe how LinUCB works from Chu et al. (2011) using the multiagent environment. In particular, this algorithm maintains an estimate of 0r by solving the following least squares estimator (for player i).
0 = arg min deRd
Σ (ri.a - (0, v(..a))))) 2))++ 2110
(3)
which has solution
0 V,
Tta
(4)
1=1
where Vi are d matrices
T Vo = XZ and V = Vo + Σ D0
(5)
This 0f gives an estimate of 6* in the contextual bandit setting.
For the estimate of 0*, construct confidence interval Ci(0) which is the set of vectors in I& that are most certain distance away from under the norm || v V More explicitly our confidence set is,
C2(0) = fv e R || - 01L S 3r}
(6)
For each arm, each player can construct an Upper Confidence Bound by solving the following optimization problem
max (t, (E))
This optimization problem has the solution
(I O + /Bll|=rally
(8)
and each player will pick the arm with the highest index. In the classical case, 3e can be chosen
v Vdma + y 22og (1) dlo
dd 112
(9)
d)
where À is used to initialize Vo and is in this setting can be any positive number.
In the following subsections, we will generalize the LinUCB algorithm from Chu al. (2011) to account for the information asymmetries namely action asymmetry (Problem A) and reward asymmetry (Problem B), and state their regret bounds.

---

Published in Transactions on Machine Learning Research (03/2025)
3.2
Asymmetry in Actions
Algorithm LinUCB-A for asymmetry in actions
1: Input: a > 0, K K,m,d E
V 5 la:
b< 0d
for 1,2.3....... T do
O. + -
6: Observe Tm arm contexts Etaa for each joint arm E A.
7: for each joint arm E A do -
8: Pt.a + 0, Fi,a + a
Dtaa
end for
10:
All players take their corresponding action for a arg maxa Pr,a: where joint action d, is chosen that it's smallest by Definition 1.
11:
Observe reward Ti {0,1]
12:
Update V + V Dr, Dr.a.
13:
Update b b + Jt.
14:
end for
In this section, we generalize the LinUCB algorithm action asymmetry (Problem A) and call it LinUCB-a A. This the setting where each player receives the same reward but unable to observe the other player's actions every round. Since the fcedback from all the players is the same, the only challenge comes inferring the other player's actions. In particular, when two joint actions have the same UCB index, there needs to be way to break ties. Therefore, define the following ordering the joint space.
Definition 1. Number the players 1,..., m and the K individual actions, and consider each set of joint action
digit rumber with each digit corresponding to the joint action. Call this base K number Na. Por joinl aclion b E A, we say that a < b is Na < No-
This is similar to what done in Chang al. (2022). The idea is that even though the players cannot observe, the other player's actions, because they obtain the same feedback, they infer what the other players are doing as long as they have a way to break ties should two joint actions have the same index. Because of this coordination, the players are behaving as if they were single agent in larger joint action space. From this, we can deduce the following regret bound.
Thcorem 2. In the action asymmetric (Problem A) contertual bandit setting where the content vectors, the frequentist regret bound of Algorithm is
Ry = CoVTlog(TL)
(10)
Proof. See Corollary 19.3 of Lattimore and Szepesvári (2020).
We note that this bound truly reduces to the single agent setting case as it doesn't even grow with the number of arms. This is because the success of the algorithm only depends on the accuracy the estimate of 8* In comparison, in the multiarmed bandit problem, the regret grows with action space because every needs to be estimated.
3.3 Asymmetry in Rewards
In this section, we generalize the LinUCB algorithm reward asymmetry (Problem B) and call LinUCB-B BB. This the sctting where each player reccives an i.i.d copy the reward but is able observe the other player's actions every round. This algorithm is similar to LinUCB-A A but takes into account that the reward feedback is different for different players.

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 2 LinUCB-B for asymmetry in rewards
Input: > 0, K,m,d d E N a, <- Ala, where À T 2 d' t 0a
2: for t= 1,2,3...... do
3: Each player updates 0j + V-
4: Each player Observe Km arm contexts Zi,a for each joint arm a E A.
5: for each joint arm a E A do
Each player i updates pi,a < (0)) Fi,a + a L Vaava
end for
8:
Each player chooses their corresponding action for their observed a, = arg max Pi.a:
9:
Each player observes the other player's actions.
10: Each players observes an I.I.D. reward r E {0,1}
11: Each player updales = V Ft,aa "
12: Each player updates b' + + Di.a.
13:
end for
The central idea to modify À and vB, so that each player's confidence set small enough so that for some distribution of context vectors there very high probability that all the players agree the optimal arm for each particular round. In doing so, allow the players to implicitly coordinate their actions without any need for the players to communicate during the learning process. More specifically we set,
BBr (T</210011)
(11)
with e e= 1/2 and our initialization for Vo = Al is
T
(12)
Compare this equation In particular, the ratio of Br/A A much smaller for this setting than is for the setting in problem A. This is because Or (as we show in Lemma 7) is the lower bound for the radius of the confidence interval for estimate of 0*, and need these to be sufficiently small in order for the a aforementioned coordination to occur.
We shall show that remarkably, even using the same algorithm as Algorithm (with just modifying X = VT) we can obtain a regret bound that is still sublinear. Note this algorithm that the rewards rī at time are indexed by i, since each player observes their own copy of an IDD reward, without seeing the other players' copy. Therefore each player has their own estimate of 6² as well. This also causes their estimate of the parameter 0* to be different from each other, resulting in different confidence sets for 8 as well. The explicit algorithm is stated in Algorithm 2, where the quantities that superscript attached to them. For this algorithm to work we have to assume that the context vectors are generated by some fixed (but unknown) distribution in the unit ball of radius L.
now different for each player have
To see that is impossible to obtain sublinear regret using adversarial contexts consider the 2 player environment, and suppose each player has two arms 21, Then we consider the following matrix where the row labels are the actions of one player and the column labels are the actions for the other player. Furthermore, each entry corresponds to context vector for that joint action.
1
V2 0
2
0
where either v is the best contex vector, and v ~ v in that (v, 0*) and (v', are really close to each other. When they are sufficiently close since the players have IID rewards, their estimates 0 will also be slightly different. If two players disagree on which context vector is the best, they will obtain reward. For the appropriate context vectors, this happens with constant probability, and thus we obtain constant
7

---

Published in Transactions on Machine Learning Research (03/2025)
regret. Note that refrained from setting = v' because when two context vectors are the same the players can still coordinate by ordering the arms as in Definition 1 which was done while studying Problem A. Furthermore, this is not an issue that shows up in the single-agent setting because even if the player is unable to dccide which of a or o' is better, it doesn't matter because pulling either incurs little regret. In the multiplayer settings, the issues show up when two players disagree on which arm to select for many of the rounds.
Therefore, let (x)) be Lebesgue integrable probability distribution density of this ball that contains the context vectors and suppose that || < oc. Note that it does not need to be continuous. Letting be the Lebesgue mcasure over (with M is the o-algebra of Borel sets), it follows that for any subset U, we have
P U) [ (z))du()) < U(U
It follows that as p(U) + 0, we have (a(x E U) 0 as well. This also means that as the players refine their estimate of 8", the chances that the players will disagree on which arm to pull will decrease in probability. This intuition is formalized in Lemma and Lemma 8.
We can now state the regret bound of Algorithm 2 under reward asymmetry (Problem B).
Theorem 3. In the reward asymmetric (Problem B) contertual bundit setting where the contect vectors are distributed with fized distribution the frequentist regret bound of Algorithm 2 is,
Rr = Ommk2m V (og(
(13)
The proof of this is given in the supplementary materials.
Note that this result depends on the number of actions. That's because in order for the players to be coordinated the context vectors of the joint action to have be sufficiently far, This is formalized in Lemma 7
3.4 Asymmetry in Both Rewards and Actions
In this section, we propose ETC which will be applied to Problem C. In the previous section, we showed that LinUCB does well even when the rewards are IID (problem B). This is because in this setting the players are still able to observe the other player's actions and therefore they can make the correct updates. However, in this setting, as they cannot observe the other player's actions, we camnot guarantee each player will attempt to pull the same joint arm. In particular, at the beginning of the learning process, when the estimate of 0 isn't very accurate for any player, this increases the probability of mis-coordination.
We circumvent this by giving an exploration sequence of time T where will be shown in the proof that = 1 is optimal. During the exploration sequence, all the players will pull arm 1 (or any other fixed arm(s)) as long they agree on which ones to pull at each round. In this time they will update their V, and b; parameters. After the exploration phase they will run regular Lin UCB, but they will not update their V, and by values. The idea is that after sufficient exploration they will each have (different) but accurate estimates of 0. Since the context voctors are generated at random (rather than adversarial), there is a high probability that they will be able to successfully coordinate pulling the best act al every round.
Similar to Algorithm 2, our choice of À VT is important. By selecting a large enough À we ensure that the confidence ball for 0 is sufficiently small. However, we cannot choose À too big, or else our confidence ball for 0 will not contain O with sufficiently high probability.
We have the following regret bound for this algorithm
Theorem 4. In the reward and action asymmetric (problem C) contextual bandit setting where the context vectors are distributed with fized distribution the frequentist regret bound of the algorithm
RT = Omm22m V CTTTTollT log(T))
(14)
The proof of this is given in the supplementary materials.
8

---

Published in Transactions on Machine Learning Research (03/2025)
Algorithm 3 ETC for asymmetrr in rewards and actions
Input: Br 0, K, m, d N, exploration parameter 7
de < AIa, with À To where
bj 0a
4: for 1,3,33
T do
5: All players will pull the corresponding arm to the joint action 1.
Update Vi+1 f- Vi Li.
7: Update 6' + + Tr.a.
8: end for
9: 0 V
10: for t= T + 1,...,, do
11: Observe KT arm contexts Tt,a for each joint arm A.
12: for each joint arm A do
13: Pi.a (0:) Lt,a + vBT 0i V-1xt,a Tt.a
14: end for
15: Each player chooses their corresponding action for their observed a, = arg max Pt.a-
16: end for
140
143
163
LHUCS-A
UHUCB-A
0.10
UHUCB-A
LIUCS--_ET
L-UCB-BETC
LHUCB-S,EE
0.08
0.76
0.08
d
0.500
0:04
0:25
0.85
0.02
0.000
0.00
0.00
Timettop
163
Timslisp
Tiessoo
168
M-2 K-2
M-d K-3
Mnd K-d
LHUCS-A
UHÚGBA
UHLEBA
LHUCIS- ETC
UnUCB4_ETE ETC
L.UEB-B
0.8
LTC
LHUGS--
0.16
LiUGB-C_ETC
LrUcB-
0.002
LHUEB-S
LIUUBB-C_ETC
d= 10
02
0.075
0.10
0.000
0.85
0.028
10
Threntop
Timattp
Trnasto
Figure 1: Regret plots comparing different algorithms to different information asymmetry. Red is the regret of LinUCE-A A on Problem A (asymmetry in actions). Brown the regret for ETC on Problem B (asymmetry in rewards). Green is the regret plot for LinUCB-B on Problem B. Finally black is the regret for ETC on Problem C (asymmetry both rewards and actions).
Similar to the regret bound of Algorithm 2 provided by Thcorem 3, this depends on the number of actions due the fact that every round the players are miscoordinated (i.e. when the context vectors are too close each other), we incur linear regret.
4 Experiments
In this section, we execute simulations to corroborate the empirical efficacy of the proposed algorithms in this paper. Figure 1, we plot the regret versus time for both algorithms LinUCB-A and LinUCB-B. It should be emphasized these algorithms assume different types of asymmetry: LinUCB-A assumes action asymmetry while LinUCB-B assumes reward asymmetry.
9

---

Published in Transactions on Machine Learning Research (03/2025)
4.1 Experiment Details
We conduct the simulations using O and context vectors x uniformly sampled from the unit cube [0, 3al- This parametrization ensures that ||0]l,, and || measured using the lz norm, does not exceed I. = vd, in line with the constraints of our problem setting. Furthermore, it's clear this uniform distribution is bounded over our space for z. Each reward is set to be Gaussian, and the standard deviation of them is randomly uniformly pre-selected to be from the range [0, 1]. For each environment, the simulations were executed over 7= = 10, 000 rounds. We repeat these simulations 5 times to compute the median regret and report the 95% confidence interval. The hyperparameter 3T is set to vT for all algorithms analyzed.
In the proceeding section, we perform the experiment on environments with m and K equal to 2. respectively, with d 5, 10. Moreover, we use LinUCB-B ETC to denote the ETC algorithm run problem B. Similarly, LinUCB-C_ETI ETC is used to denote the ETC algorithm run on problem C.²
4.2 Analysis
We note that since LinUCB-A is the same algorithm the single-player setting but with an added ordering, it serves as the baseline to compare with our other algorithms. LinUCB performs relatively well as compared to LinUCB-A A but LinUCB-A tends to perform better. This is because while LinUCB-A A has the more favorable leedback, LinUCB-B has a. larger X parameter which encourages less exploration. In the analysis, this affects the probability of the "good event" that the will stay within the confidence ball. However, in our simulations, due to the small environment, it's unlikely that the 'bad' events will occur. Therefore, in this case, it's more favorable to do less exploration.
We note that ETC appears to be piecewise lincar. In particular, the first piece which only occurs for VT rounds is steeper as this is the exploration phase. In the second piece, the algorithm takes the parameters taken from the periods of exploration and then runs LinUCB without updating these parameters. Philosophically, the slope of the regret curve reflects an algorithm's learning. Because the parameters don't update, ETC does not perform better as the rounds continue (which is different than the standard LinUCB, the slope of the regret curve remains constant. Despite being piecewise linear, however, asymptotically the regret will still grow in the same order as LinUCB-B.
In comparing ETC and LinUCB-B on the asymmetry in the rewards environment (Problem B), we note that, LinUCB-B performs superior. However, ETC is more robust as it achieves around the same level of performance in both Problem B And Problem C settings. This makes sense because ETC is a fully coordinated algorithm so it does not need to rely on observing actions to achieve its performance.
5 Conclusions and Future Work
In this paper, we adapted LinUCB from Chu et al. (2011) to the multiagent setting with different types of information asymmetry. Namely, we studied action asymmetry (Problem A) where each player receives the same reward but cannot observe other player's actions. Using a coordination scheme were able reduce this to the single agent setting and obtain an O(VT) regret bound. On the other hand, we also studied reward asymmetry (Problem B) where each player receives an iid copy of the reward but can observe the other player's actions. In this setting, we can prove that if the context vectors are distributed with a fixed distribution (rather than adversarial), then we obtain a O(vT) regret bound. We were able to achieve this using the same algorithm as that Problem A but modifying À be VT. Both of these regret bounds are the first for this setting. For asymmetry in both (Problem C), we proposed fully coordinated ETC algorithm which did exploration for the first vT rounds and then ran LinUCB for the remaining time, which achieved the same regret as the multiplayer LinUCB. Finally, we corroborated our results with some simulations.
In our regret. bound, we have a dependence on KM, the number of joint actions. This occurs because we assumed the contextual vectors are randomly generated and so we need these to be 'well behaved' enough so
3 All the source code that has been used to generate the results presented in this paper can he found via http://tinyurl. con/yty68ucp.
10

---

Published in Transactions on Machine Learning Research (03/2025)
that the players can coordinate. However, this takes away from the true power of linear reward models where the regret bound doesn't depend on the number of actions. For future work, we can perhaps show that this is necessary via a lower bound, or propose new setting (perhaps the players pull their arms successively rather than simultancously).
References
Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. 2014. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning. PMLR, 1638 1646.
Shipra Agrawal and Nikhil Devanur. 2016. Linear contextual bandits with knapsacks. Advances in Neural Information Processing Systems 29 (2016).
Shipra Agrawal and Navin Goyal. 2013. Thompson sampling for contextual bandits with lincar payoffs. In International conference on machine learning. PMLR, 127 135.
Robin Allesiardo, Raphaäl Féraud, and Djallel Bouneffouf. 2014. A neural networks committee for the contextual bandit problem. In Neural Information Processing: 21st International Conference, ICONIP 2014, Kuching, Malaysia, November 9-6, 2014. Proceedings, Part I 21. Springer, 374-381.
Baruch Awerbuch and Robert Kleinberg. 2008. Competitive collaborative learning. J. Comput. System Sci. 74, 8 (2008), 1271-1221 1288.
Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins. 2014. Resourceful contextual bandits. In Conference Learning Theory. PMLR, 1109 1134.
Yogev Bar-On and Yishay Mansour. 2019. Individual regret in cooperative nonstochastic multi-armed ban- dits. Advances in Neural Information Processing Systems 32 (2019).
Rémi Bonnefoi, Lilian Besson, Christophe Moy, Emilic Kaufmann, and Jacques Palicot. 2017. Multi-Armed Bandit Learning in IoT Networks: Learning helps even in non-stationary settings. In International Con- ference on Cognitive Radio Oriented Wireless Networks. Springer, 173-185
Djallel Bouneffouf, Amel Bouzeghoub, and Alda Lopes Gançarski. 2012. A contextual-bande algorithm for mobile context-aware recommender system. In Newral Information Processing: 19th International Conference, ICONIP 2012, Doha, Qalar, November 12-15, 2012, Proceedings, Part III 19. Springer, 324 331.
Djallel Bouneffuff, Amel Bouzeghoub, and Alda Lopes Gançarski. 2013. Contextual bandits for context- based information retrieval. In Neural Information. Processing: 20th International Conference, ICONIP 2013, Daegu, Korea, November 3-7, 2013. Proceedings, Part 11 20. Springer, 35 42.
Djallel Bouneffouf, Romain Laroche, Tanguy Urvoy, Raphael Féraud, and Robin Allesiardo. 2014. Con- textual bandit for active learning: Active thompson sampling. In Neural Information Processing: 21st International Conference, TCONTP 2014, Kuching, Malaysia, November 3-6, 2014. Proceedings, Parl 21. Springer, 405-412.
Djallel Bouneffouf, Irina Rish, Guillermo A Cecchi, and Raphaël Féraud. 2017. Context attentive bandits: Contextual bandit with restricted context. arXiv preprint 1=Xiu:1005.0882 (2017).
Simina Brânzei and Yuval Peres. 2021. Multiplayer bandit learning, from competition to cooperation. Conference on Learning Theory. PMLR, 679 723.
Sarah H Cen and Devavrat Shah. 2022. Regret, stability & fairness in matching markets with bandit learners. In International Conference on Artificial Intelligence and Statistics. PMLR, 8938-8968.
Nicolò Cesa-Bianche Tommaso Cesari, and Claire Montcleoni. 2020. Cooperative online learning: Keeping your neighbors updated. In Algorithmicc learning theory. PMTRR, 234-20 250..
11

---

Published in Transactions on Machine Learning Research (03/2025)
Nicol'o Desa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora. 2016. Delay and cooperation in nonstochastic bandits. In Conference. on Learning Theory. PMLR, 605-622.
William Chang, Mehdi Jafarnia-Jahromi, and Rahul Jain. 2021. Online learning for cooperalive multi- player multi-armed bandits. arXáv preprint arXiv:2109. 03818 (2021).
William Chang, Mehdi Jafamia-JJahrmi,, and Rahul Jain. 2022. Online learning for cooperative multi player multi-armed bandits. In 2022 IEEE 61st Conference on Decision and Control (CDC). IEEE, 7248 1253.
William Chang and Terry Lu. 2023. Optimal Cooperative Multiplayer Learning Bandits with No Commu- nication. In arzic preprint.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. 2011. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 208 214.
Audrey Durand, Charis Achilleos, Demetris lacovides, Katerina Strati, Georgios D Mitsis, and Joelle Pineau. 2018. Contextual bandits for adapting treatment in a mouse model of de novo carcinogenesis. In Machine learning for healthoure conference. PMLR, 67-82.
Meena Jagadeesan, Alexander Wei, Yixin Wang, Michael Jordan, and Jacob Steinhardt. 2021. Learning equilibria in matching markets from bandit feedback. Advances in Neural Information Processing Systems 34 (2021), 3323 3335.
Hsu Kao. 2022. Efficient Methods for Optimizing Decentrolized Multi-Agerd Systems, Ph. D. Dissertation.
Hsu Kao, Chen- Yu Wei, and Vijay Subramanian. 2022. Decentralized cooperative reinforcement learning with hicrarchical information structure. In International Conference on Algorithmic Learning Theory. PMLR, 573-605.
Nikolai Karpov, Qin Zhang, and Yuan Zhou. 2020. Collaborative top distribution identifications with limited interaction. In 2020 IEEE 61st Anneual Symposium on Foundations of Computer Science (FOCS). IEEE, 160-171.
Tze Leung Lai and Herbert Robbins. 1985. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics 6, 1 (1985), 4-22.
Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. 2016. On distributed cooperative decision- making in multiarmed bandits. Tn 2016 European Control Conference (ECC). TEFE, 243 133-248.
Romain Laroche and Raphaäl Féraud. 2017. Algorithm selection of off-policy reinforcement learning algo- rithm. arXiv preprint arXiv:1701.000 7001088000 (2017).
Tor Lattimore and Csaba Szepesvári. 2020. Bondil algorithms. Cambridge University Press.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. 2010. A conlextual-bandi approach to per- sonalized news article recommendation. In Proceedings of the 19th international conference on World wide web. 661-670.
Lydia T Liu, Horia Mania, and Michael Jordan. 2020. Competing bandits in matching markets. In Interna- tional Conference on Artificial Intelligence and Statistics. PMLR, 1618-1628.
Lydia T Lin, Feng Ruan, Horia Mania, and Michael I Jordan. 2021. Bandit learning in decentralized matching markets. Journal of Machine Learning Research 22, 211 (2021), 1 34.
Weichao Mao, Tamer Basar, Lin F Yang, and Kaiqing Zhang. 2021. Decentralized Cooperative Multi-Agent Reinforcement Learning with Exploration. arXiv preprint 1xXi::2110005110 (2021).
Weichao Mao, Lin Yang, Kaiqing Zhang, and Tamer Basar. 2022. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning. PMIRR 15007-15049.
12

---

Published in Transactions on Machine Learning Research (03/2025)
David Martinez-Rubio, Varun Kanade, and Patrick Rebeschini. 2018. Decentralized Cooperative Stochastic Bandits. Xiv preprinl. or arXiu:1810.04460 (2018).
David Martinez-Ran Rubio, Varun Kanade, and Patrick Rebeschini. 2019. Decentralized cooperative stochastic bandits. (2019).
Aldo Pacchiano, Peter Bartlett, and Michael Jordan. 2023. An instance-dependent analysis for the coop- erative multi-player multi-armed bandit. In International Conference on Algorithmic Learning Theory. PMLR, 1166-1215.
Alexandre Proutiere and Po-An Wang. 2019. An Optimal Algorithm for Multiplayer Multi-Armed Bandits. arXiv preprinl Xie: 13079 (2019).
Abishek Sankararaman, Soumya Basu, and Karthik Abinav Sankararaman, 2021. Dominate or delete: De- centralized competing bandits in serial dictatorship. In International Conference on Arlificial Intelligence and Statistics. PMLR, 1252 1252-1260.
Dennis Soemers, Tim Brys, Kurt Driessens, Mark Winands, and Ann Nowé. 2018. Adapting to concept drift in credit card transaction data streams using contextual bandits and decision trees. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 32.
Balazs Szorenyi, Róbert Busa-Fekete, István Hegedus, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. 2013. Gossip-based distributed stochastic bandit algorithms. In International Conference on Machine Learning. PMLR, 19-27.
Chao Tao, Qin Zhang, and Yuan Zhou. 2019. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. In 2019 IEEE 60th Anreal Symposium on Foundations of Computer Science (FOCS). IEEE, 126-146.
Po-An Wang, Alexandre Proutiere, Kaito Ariu, Yassir Jedra, and Alessio Russo. 2020. Optimal algorithms for multiplayer multi-armed bandits. In International Conference on Artificial Intelligence and Statistics. PMLRR 4120-4125
13

---

Published in Transactions on Machine Learning Research (03/2025)
6 Supplementary Material
6.1
Concentration Lemmas
The following taken from Theorem 20.5 of Lattimore and Szepesvári (2020). It gives us the size of the ball that contains 0 with high probability.
Lemma 5. Let 8 1). Then, with probubility at least 1 - ô, it holds that for all t N,
10. 0. ollveco) < <VX110ulla + 2
1 g
det V₂(A)
+
log
X
Furthermore, if 1101112 S T, then P( enists i LEN+ 0. $ Ci) s 6 with
C. - 1= Rd 110-- 0 (1-1(1)
-
1
det (
<IVA+
2
log
8
Ad
6.2 Proofs of Main Theorems
In this section, we prove that the algorithm satisfies the regret bound given Theorem Consider the 'good' event defined as follows
m
m an (of C,(0*))
(15)
This event states that at every round t [T], every player i i [m]] has empirical estimate of 0* that is within the confidence interval centered at 0* This ensures that all of the player's estimates of 0* are not too far from each other. This also means that despite each player having different empirical estimate of 0", if the context vectors of each arm are not too close for most rounds, then the players will be able to coordinate properly. This is formalized in lemma 7, To do that we first show that the eigenvalues of V are nondecreasing
Lemma 6. For any X and Br, have the sollowing inequality for each players estimale for 0f and Or
|10: 1P1-6-11- 8T
Proof. To prove this note that C is an ellipsoid where the inverse of the eigenvalues of V give the lengths of the principle axes. We first note that based on the fact that Vn = AI, and therefore Co is a circle with radius & We will done if we can show that V2, has nondecreasing eigenvalues. Let of 2 of Z 2 of be the eigenvalues of V,
From the definition of Vi, it's clear that V. is symmetric. Thus, we can apply the Courant-Fischhe Fischer min-max Theorem to obtain
of (A) = mix (v) and v + 03 dim(U)) = k}
where the Rayleigh Quotient Ry, (v) is defined as,
(Vi. v)
(v)
||/||
14

---

Published in Transactions on Machine Learning Research (03/2025)
Therefore, we have
0+1 min (max
1 (x) (
UU, 00 dim(U) =
min ( T (x) U + 0} dim(U) = k3
((V + Dt,a, L )u,
E tEU, )
min
max
10
dim(U)
(Vov,)) v)
(Err, 2i,a v,
=min
max
E U, #0
||0||
dU)
(V.v, v)
of ddm(U)=() k =
v E 100000
min
max
||/l
of
where in the inequality we used the fact that (Ire, TT v, (2t,a, "Ta u) u)T v. TT TT.a ||0 el|
0.
Now we show that when all the players have their estimates inside the confidence ball around 0r, then they can fully coordinate.
Lemma 7. Suppose 0j E Ce) is an empirical estimate of 0* for plagers i. Then under the good event E, if ata and ay aa are context veclors such that
0 x1,a) (0", xr,aa) (0"))))))) >2 1rL
2
(16)
X
then (0) xi,a) > x1,') for all players i.
Proof. From the defintion of C())), we know that
(0, )r,aa)) = (0*, )', + (0) 0*, xi,aa)
(17)
< 10" at,aa) + |10
(18)
< 10" at,aa) + |00 0- 0-
(19)
Similarly,
( v1,a)
(0", Fi,aa + (0) 0" Fi,a)
(20)
0 Ft,aa) |00 0*
x x1,a|
(21)
0 v),a) |0: 0- L
(22)
Therefore combining the two inequalities above yields
(0) xt,a)
(0), xt,a
2 (0" x(,a)) - |00 0^
( Dt,aa) + |10: 0" z))
(0,, x(,a) 1 xt.a')
2|10: 001|
15

---

Published in Transactions on Machine Learning Research (03/2025)
Figure 2: The set of points aag such that equation 23 is satisfied lies outside of the region bounded by the blue and green hyperplanes determined by Vt.a, The dotted vector 0", and these hyperplanes are a distance of 4 LrL X||01|| apart.
Form Lemma 6, 00 0-1 I Sr. then equation equation 16 will show (0*, 0 and the desired result. will follows.
2 - 00| > arra) -2
This proves the desired result.
The next result tells us that the probability that the context vectors satisfy the hypothesis in Lemin 7 is lower bounded by some constant that will grow as T oc. This will be used to define the good event G. that will allow the players agree on which arm they want pull.
Lemma 8. At any given round 1, if all the contert vectors Dr, are generated at random with probability density function (x)) < M, with || Il S L, Then let Pe be the probability for the following event at a round t: Ang two joint actions a and a' satisfies the following inequality
110,,z1h - -6" 21,aa) TTL
(23)
A
Then
P. 121-K2n (c
(24)
x
for universal constants C1, C2 E R.
Proof. Aribtrailiry order the joint actions 01, a2, ... and suppose T has been placed that the given conditions are satisfied. Now let's bound the volume where the next context vector can be placed. In particular, the set of points at,a, such that it satisfies equation 23 satisfies
10" Ft,az) > (0" rr,a +2 BrT. or
(25)
L
0 )1,) (0", F(,01)
(26)
From the definition of the inner product, the set of Dr,a, that satisfy the equation above lies outside of two hyperplanes normal to 0* and at distance of 4 BrL "|[0=T] apart. See Figure 2 for an example in d d= 3. Call the region between these two parallel hyperplanes contained within the sphere U. Then the volume of U can be bounded by the volume of a cylinder whose base is d - dimensional sphere with radius L, and with height 4 3r Thus the volume of each such region is upper bounded by -
B1L (x110=1
3r
P(U)
4
Ld
4
I
d+1
r
d+1
2
Thus the probability that Dt,ag satisfies equation 23 is at least
16

---

Published in Transactions on Machine Learning Research (03/2025)
1 v())dr 2a-1221-MM
(27)
2 M + La
4 (x110-11 1) A
3r
(28)
(29)
for some universal constants C2. Repeating inductively, the probability that all Km context vectors satisfy equation 23 is at least
K
(c)
(2 Km
(30)
A 2 1
K 2m (2 Br
(31)
x
where the last inequality we used (1 x)" 2 nxr for x 2 0.
Theorem In the reward and action asymmetric (problom C) contextual bandit setting where the context vectors are distributed with fixed distribution the frequentist regret bound the algorithm is
RT Ommk2m 2m 2d L log((T)
(32)
Proof. Consider the 'good' event time t defined as,
3r G: = n 1100, x(,a) (0*, ;taa)) >
L
a,''Ed
and let
G G
This is the event. that at round T, the context. vectors for any two joint actions a and a' are not too close in the sense that their inner product with 0* sufficiently far.
We suppose there are To rounds of exploration for some a (0, 1) and then optimize over a. We can decompose the regret follows:
17

---

Published in Transactions on Machine Learning Research (03/2025)
Rr E
0, 3a. - x²))
(33)
T
T
S E
( Da. - x²) +
Σ
(0, Do. - x²)
(34)
1=1
t=
T
$ ((T)) E
(0 aa. x²)
(35)
T
O(T²)
(0, Da.
x xIG E] E)
(36)
I=
T
= O(7") + IE
(0, Da.
x ([[ EJ 1[(G, n E)
(37)
T=
O(T)) LE
(0, Da. x " B
(38)
T
S 0T()) +
(0, Da. - x TT F.]
Σ [P(G))+ P(F))
(39)
After To rounds of exploration, have == Furthermore, as in Lemma 5, the probability that for all players i, E [M] their estimator is within the confidence interval (determined by 3T) is at least 1 - 6. Thus the probability that everyone's estimator is within this confidence interval is 1 - md. Picking 5 + this gives
P(E") S mō T
Using our choices of 8 and X = T", we have (by Theorem 19.2 of Lattimore and Szepesvári (2020))
det (VT(
dd dx TL2
B = VIL V 2og (T) + log
-T0/2
V 2 (T) + log
Xd
Tad
So that we can use lemma to upper bound the probability of the complement of the good event happening, we have
P(G)) < 2m Mc) km
2og (T) + log
(ee((Vr(A)) Tad
}]
( (x L log(TT)
O
(40)
A
To
Ta
According to Lemma 7, under the event I[G, n E] the players are completely coordinated. This means that we are reduced to a single agent setting with a Km size action space. However, the bound for the single agent LinUCB regret bound doesn't depend on the size of the action space so we do not expect the exponentially larger action space affect the regret. The regret for this can be bounded as follows.
Let rt be the instantancous regret in round (under the good event G₁ O E defined by,
(f., Na; Fa.)
where at the optimal arm for round f based on the context vectors received. Let 0, E C2 be the parameter in the confidence for which (0c. a.) = UCB, (a:). Then, using the fact that 0., C2 and the definition of the algorithm leads
(O., Roa) < UCB, (xa;) UCB, (Ra,) (0e, Ra.)
18

---

Published in Transactions on Machine Learning Research (03/2025)
Using Canchy-Schwaer incquality and the assumption that 0₂ E C. and facts that O C. and Ce S & leads
to
Tt = (0,, Fa; - -aai) S (0, -0,, Fa.) S | 11, 110 0~ 0x1lvz
(41)
(2 (2_.Vorr
< 2 =2llva,llv'' VBT= = aa V La. v BT S
(42)
T.
V x |
Where use used the fact that || = max
is upper bounded by the largest eigenvalue = (
(given by )) since V is positive semidefinit.
Therefore, picking a = 1o which gives us the tightest bound by AM-GM, we have
R Σ [(())) + P(E))
Σ n I.
(43)
We can now prove the regret bound of Algorithm 2 under reward asymmelry (Problem B).
Theorem 3 In the reward asymmetric (Problem B) contextual bandit setting where the context vectors are distributed with fixed distribution the frequentist regret bound of Algorithm 2
Rr = Ommk2m La log(T))
(44)
Proof. Remarkably we can follow the same proof structure as in Theorem 4. In ETC we have two main phases
They pull fixed arbitrary arm for T exploration rounds while updating their å estimate.
The remaining T T rounds they will do regular Lin-UCB while not updating their paramcters.
Even though in Algorithm LinUCB-B, they follow LinUCB for all T rounds, however, rounds into the set of first T rounds and the remaining T - T rounds to capitalize on the decomposition given by equation 39. This is because the first 7 rounds we are still updating our estimate for 0 which is exactly what happens phase of ETC, Given that our initialization = T unchanged in LinUCB-B Ô rounds they will do regular
decompose these
from ETC this means that equation 40 still holds. While for the remaining Lin-UCB while still sharpening the parameters which essentially a better version of phase 2 of ETC, This means that equation 42 still holds. In fact, this equation can be made slightly sharper by
LLVBT Br
Te S.
(45)
Therefore will obta ain sharper bound but of the same order O(-) hides the constants.
19


Reviews:
[{"review_id": "lRVmefSK0G", "reviewer": "Reviewer_KpK6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The following are some questions: \n1. There are a rich line of works studying the multi-agent bandit problem. In some cases, the agents are cooperative and aim to maximize the collective rewards. In some cases, the agents are competitive and aim to maximize their own rewards. And also some are homogeneous setting where agents' preferences are the same and some are heterogeneous where agents' preferences are different. This paper does not discuss these related works. And in these works, usually single agent can also only observe their own rewards. What is the difference between the considerred setting with existing setting? Is the proposed framework more general and can cover existing setting? \n2. For the action asymmetry setting, single agent can only observe its own action but cannot observe other agents' actions. In such a case, why the agent can observe the full $x_{t,a}$ context where $a$ is the joint action over all agents. \n3. The theoretical significance is limited. The analysis in the action asymmetry setting is a direct extension of previous LinUCB algorithm only a minor modification of how to break the tie. For the reward asymmetry setting, the regret has an exponential term which does not appear in existing multi-agent bandit works. \n4. Some typos: the second paragraph in page 4 \"each player is observes\", \"Each player maintains for each arm their own UCB-interval and when two UCB-intervals are disjoint. However, such an elimination method...\"; The last paragraph in page 10 \"a $O(T \\sqrt{T})$ regret bound\", \"the first $\\sqrt{T}$ rounds\". \n5. I am not convinced that \"However, this problem is easier than the bandits’ case in the sense that we only have to estimate one parameter θ ∗ , whereas in the bandits case, we had to estimate the mean of each arm.\" Usually, due to limited observation, the linear bandit problem is much harder than the tabular multi-armed bandit setting. Many problems are first solved in the tabular setting and then the fuction approximation setting (such as the linear bandit setting) are solved.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper formulates a new multi-agent contextual bandit problem. It considers three types of asymmetry scenarios, the action, the reward, and both. For each asymmetry scenario, the paper provides a variant of LinUCB algorithm. For the action scenario, it proves an $O(\\sqrt{T})$ regret. For the latter two scenarios, it proves an $O(mK^{2m}L^d\\sqrt{T})$ regret.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the last part.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5pMpgq6cAs", "reviewer": "Reviewer_4zmn", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The LinUCB algorithm is described in Section 3.1 in detail.\n1. Some related works are discussed.\n\nWeaknesses:\n1. What is the motivation of the several multiplayer settings?\n1. Are there lower bounds to show the efficiency of proposed algorithms?\n1. Consider the similarity to Chang et al. (2022), can the algorithms be compared in some setting?\n1. In Section 2, it is stated that 'the case where each player has a different number of arms is easy'. Why?\n1. I suggest the author(s) to provide the proof of Theorem 2.\n1. The design of Algorithms 1 and 2 look confusing. It is not easy to understand the pseudocodes.\n1. It is better to clearly describe the formulation of problem B.\n1. The setting studied in section 3.4 can be mentioned in Section 1.\n\nOther comments: The author(s) can more careful about the writing. Some suggestions are as below.\n1. can be improved: 'Furthermore, at the start of each round, every player is given the same $K^m$ context vectors $x_{t,a} \\in R^d$ corresponding to each joint arm $a \\in A$.\n1. can be improved: 'Each player maintains for each arm their own UCB-interval and when two UCB-intervals are disjoint.'\n1. can be improved: 'This algorithm is similar as mLinUCB-A but takes into account that the reward feedback is different for different players'?\n1. Title of Section 3.2: 'Asymmetry in actions'?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studied the contextual bandits where the multiple players obtain asymmetric information. It considered there different settings: (a) an agent can observe others' actions but only their own i.i.d. reward; (b) an agent cannot observe others' actions but their unique reward; (c) an agent cannot observe others' actions and their own i.i.d. reward. It derived the regret of proposed algorithms and evaluated them with simulations.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Suggestions are in the section of 'Strengths And Weaknesses'.", "broader_impact_concerns": "No ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "22oBBxAQF7", "reviewer": "Reviewer_Ytk6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nIn addition to being the first work to study multiplayer contextual bandits, the authors have investigated information asymmetry under action and/or reward information asymmetries, and provided a well-thought-out presentation under the 3 cases. The disposition is clear and coherent, and the theoretical results and algorithms have been presented concisely and discussed well.\n\nWeaknesses\n- The regret bounds for Problems B and C scale poorly with the actions $K$, and players $m$, potentially making practical applications challenging. For instance, even with moderate values like $K = 10$ and $m = 4$, the polynomial dependency leads to high regret. It would be beneficial to investigate the empirical consistency of these bounds to assess their practical relevance.\n-  The purpose and goals of the experiments are not clearly stated. Providing a detailed introduction to the experimental setup, including the specific objectives and hypotheses being tested, would improve clarity.\n- The experiments primarily focus on small configurations of $d$, $K$, and $m$. Expanding the investigation to include higher-dimensional contexts ($d$), larger action spaces ($K$), and more players ($m$) would help validate the theoretical bounds and offer deeper insights into the scalability and robustness of the algorithms.\n- It is unclear which baselines, if any, are being compared. Explicitly include comparisons with either naively constructed baselines or existing algorithms for multiplayer bandits, to contextualize the performance of the proposed methods.\n- There also seems to be quite a lot of typos and hanging sentences in the paper. Please do a comprehensive proofread of the paper, particularly in the Analysis and conclusion.\n\nOther comments: Have you considered selecting $\\lambda$ in the ETC algorithm dynamically e.g. stopping exploration when confidence intervals shrink sufficiently?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a formulation and associated algorithms for multiplayer contextual bandits under action and/or reward information asymmetries. The authors propose adaptations of the LinUCB algorithm tailored to this setting, present regret bounds and experimental results to support the theoretical arguments. For the case of action asymmetry, they demonstrate that the regret achieves the optimal sublinear bound of $O(\\sqrt{T})$ Additionally, for reward asymmetry, and action and reward asymmetry, they present the first sublinear regret bounds, with polynomial dependency on the size of the joint action space.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Improve the experiments section as in above\nProofread the paper", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers recommended the following suggestions for revision: 

- an extended discussion of related works on multi-agent bandits
- provide more real-world motivations on the three settings studied in the paper
- explain why removing the exponential factor in the current regret bounds may be challenging 
- clarifications and typos (as also acknowledged in the author feedback)


I also had the same confusion as Reviewer KpK6 even after reading the rebuttal: since linear bandits generalizes multi-arm bandits (with theta being the reward vector), why is the stated problem easier than the bandit case? More explanations will be appreciated.
Decision: Accept (poster)