Fair Algorithms for Multi-Agent Multi-Armed Bandits
Authors: Safwan Hossain
Evi Micha
Nisarg Shah
Venue: NeurIPS 2021 Poster (2021)
Keywords: fairness
multi-armed bandits
Nash welfare

Abstract: We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are $N$ agents and $K$ arms, and pulling an arm generates a (possibly different) stochastic reward for each agent. Unlike the classical multi-armed bandit problem, the goal is not to learn the "best arm"; indeed, each agent may perceive a different arm to be the best for her personally. Instead, we seek to learn a fair distribution over the arms. Drawing on a long line of research in economics and computer science, we use the Nash social welfare as our notion of fairness. We design multi-agent variants of three classic multi-armed bandit algorithms and show that they achieve sublinear regret, which is now measured in terms of the lost Nash social welfare. We also extend a classical lower bound, establishing the optimality of one of our algorithms.

Fair Algorithms for Multi-Agent Multi-Armed Bandits
Safwan Hossain
Evi Micha Department Computer Science
Department Computer Science
University of Toronto
University of Toronto emi cha@ce toronto................oo....... edu
safwan, hww.mooossaaaaaaa il
utoronto.cca www.://mm....tmooooooommmmm
Nisarg Shah
Department of Computer Science
University of Toronto nisargocs toronto...... edu
Abstract
We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are agents and K arms, and pulling an arm generates (possibly different) stochastic reward for each agent. Unlike the classical multi-armed bandit problem, the goal is not learn the "best arm": indeed, each agent may perceive a different arm to be the best for her personally. Instead, we seek to learn fair distribution over the arms. Drawing on long line of research in economics and computer science, we use the Nash social welfare as our notion of fairness. We design multi-agent variants of three classic multi-armed bandit algorithms and show that they achieve sublinear regret, which is now measured in terms of the lost Nash social welfare.
Introduction
In the classical (stochastic) multi-armer bandit (MAB) problem, principal has access K arms and pulling arm j generates a stochastic reward for the principal from an unknown distribution D; with an unknown mean wz.. If the mean rewards were known a priori, the principal could just repeatedly pull the best amm given by arg max, j(]. However, the principal has no apriori knowledge of the quality of the arms. Hence, she uses a learning algorithm which operates in rounds, pulls arm j in round f, observes the stochastic reward generated, and uses that information to learn the best arm over time. The performance of such an algorithm is measured in terms of its cumulative regret up to horizon T, defined Σ (max, μu; (...). Note that this is the difference between the total mean reward that would have been achieved if the best arm was pulled repeatedly and the total mean reward the arms pulled by the learning algorithm up to round T'.
This problem can model situations where the principal is deliberating policy decision and the arms correspond to the different alternatives she can implement. However, in many real-life scenarios, making policy decision affects not one, but several agents. For example, imagine company making decision that affects all its employees, or conference deciding the structure of review process, which affects various research communities. This can be modeled by multi-agent variant of the multi-armed bandit (MA-MAB) problem, which there are N agents and pulling arm generates (possibly different) stochastic reward for each agent from unknown distribution Di. with an unknown mean pr.j"
Before pondering about learning the "best arm" over time, we must ask what the best arm even means in this context. Indeed, the "best arm" for one agent may be the best for another. A first attempt may be to associate some "aggregate quality" to each arm; for example, the quality of arm
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

J may be defined as the total mean reward it gives to all agents, i.e., E.ply This would nicely reduce our problem to the classic multi-armed bandit problem, for which we have an armory of available solutions [1]. However, this approach suffers from the tyranny of the majority [2]. For example, imagine scenario with ten agents, two arms, and deterministic rewards. Suppose four agents derive reward of 1 from the first arm but O from the second, while the remaining six derive a reward of from the second arm but 0 from the first. The aforementioned approach will deem the second arm as the best and a classical MAB algorithm will converge to repeatedly pulling the second arm, thus unfairly treating the first four agents (a minority). A solution which treats each group in a "proportionally fair" [2] manner should ideally converge pulling the first arm 40% of the time and the second 60% of the time. Alternatively, we can allow the learning algorithm to "pull" a probability distribution over the arms and seek an algorithm that converges to placing probability 0.4 on the first arm and 0.6 on the second.
This problem of making fair collective decision when the available alternatives - in this case, probability distributions over the arms - affect multiple agents is well-studied in computational social choice [3]. The literature offers compelling fairness notion called the Nash social welfare, named after John Nash. According to this criterion, the fairest distribution maximizes the product of the expected utilities (rewards) to the agents. A distribution p that places probability pj on each arm gives expected utility E, Py ( to agent i. Hence, the goal is to maximize NSW μ²)
1E, Pj pT,)) over p. One can verify that this approach on the aforementioned example indeed yields probability 0.4 on the first arm and 0.6 on the second, as desired. It is also interesting to point out that with single agent (N = 1), the distribution maximizing the Nash social welfare puts probability 1 on the best arm, thus effectively reducing the problem to the classical multi-armed bandit problem (albeit with subtle differences which we highlight in Appendix A).
Maximizing the Nash social welfare is often seen as a middle ground between maximizing the utilitarian social welfare (sum of utilities to the agents), which is unfair to minorities (as we observed), and maximizing the egalitarian social welfare (minimum utility to any agent), which is considered too extreme [2]. The solution maximizing the Nash social welfare is also known to satisfy other qualitative fairness desiderata across wide variety of settings [4-11]. For example, a folklore result shows that in our setting such solution will always lie in the core; we refer the reader to the work of
Fain et al. [4] for formal definition of the core as well as short derivation of this fact using the first-order optimality condition. For further discussion on this, see Sections 1.2 and 6.
When exactly maximizing the Nash social welfare is not possible (either due to a lack of com- plete information, as in our case, or due to computational difficulty), researchers have sought to achieve approximate fairness by approximately maximizing this objective [12-17]. Following this approach in our problem, we define the (cumulative) regret of an algorithm at horizon T as Ei (maxp NSW n²*) NSW )r,),, where p' is the distribution selected in round t. Our goal in this paper to design algorithms whose regret is sublinear in T.
1.1 Our Results
We consider three classic algorithms for the multi-armed bandit problem: Explore-First, Epsilon- Greedy, and UCB [1]. All three algorithms attempt balance exploration (pulling arms only to learn their rewards) and exploitation (using the information learned so far to pull "good" arms). Explore-Firss performs exploration for a number of rounds optimized as a function of T followed by exploitation in the remaining rounds to achieve regret Ô (31/3///33 Epsilon-Greedy flips a coin in each round to decide whether to perform exploration or exploitation and achieves the same regret bound. Its key advantage over Explore-First is that it does not need to know the horizon T upfront. UCB merges exploration and exploitation to achieve a regret bound of O (K1/2T1/22) Here, Ô hides log factors. Traditionally, the focus is optimizing the exponent of T rather than that of K as the horizon 7 is often much larger than the number of arms K. It is known that the dependence of UCB's regret on T is optimal: no algorithm can achieve instance-independer 122) regret [18].'
In instance instance-independeee independent bounds, the constant inside the big-Oh Oh notation is not allowed to depend on the (unknown) distributions in the given instance. UCB also achieves an Ollog I') instance-depe dependent regret bound, which is also known to be asymptotically optimal [19]. For further discussion, see Section 6.
2

---

We propose natural multi-agen agent variants of these three algorithms. Our variants take the Nash social welfare objective into account and select distribution over the arms in each round instead of a single arm. For Explore-First, we derive Ö (N2/3 /1/3////// regret bound, which recovers the aforementioned single-agent bound with an additional factor of N2/3, We also show that changing parameter of the algorithm yields regret bound of Ö ( [N1/3 /2/31/13 which offers different tradeoff between the dependence on N and K. For bounds, although the analysis becomes much more intricate. This is because, mentioned above, Epsilon-Greedi is a iriizonnindependeent algorithm (i.e. it does not require apriori knowledge of T), unlike Explore-First. For UCB, we derive Ô (NKT)/3) and Ô (N1/2 regret bounds; our dependence on K worsens compared to the classical single-agent case, but importantly, we recover the same vT dependence, which is provably optimal (see Appendix A).
we recover the same two regret
Deriving these regret bounds for the multi-agent case requires overcoming two key difficulties that do not appear in the single-agent case. First, our goal is to optimize a complicated function, the Nash social welfare, rather than simply selecting the best arm. This requires Lipschitz-coninnity analysis of the Nash social welfare function and the use of new tools such as the McDiarmid's incquality which are not needed the standard analysis. Second, the optimization over an infinite space (the set of distributions over arms) rather than over finite space (the set of arms). Thus, certain tricks such as a simple union bound no longer work; we use the concept of ô-covering, used heavily in the Lipschitz bandit framework [20], in order to address this.
Our contributions are twofold. Conceptually, we promote multi-agent viewpoint that requires striking a tradeoff between multiple reward functions; this can be applied to other classical single- agent problems. More technically, as explained below, the existing MAB literature does not provide vT bound for the Nash social welfare objective. Our regret bounds may be generalizable broader family of objectives for which /T bound was previously unknown.
1.2 Related Work
Since the multi-armed bandit problem was introduced by Thompson [21], many variants of it have been proposed, such as sleeping bandit [22], contextual bandit [23], dueling bandit [24], Lipschitz bandit [20], etc. However, all these variants involve optimizing the cumulative regret or identifying the Pareto frontier of multiple objectives [25] the perspective of single agent. We note that other multi-agent variants of the aumei bandit problem have been explored recently [26, 27], including in distributed environments [28-30]. However, they still involve common reward like in the classical multi-armed bandit problem. Their focus is on getting the agents to cooperate to maximize this common reward.
It is possible to view our work from a single-agent prespective by treating the K-simplex of probability distributions over arms as a "continuum of arms" and the Nash welfare as a non-linear objective to be
optimized. Kleinberg et al. [31] explore continuum- bandits, but establish a ①
regret
bound, where 7 is the zooming dimension, which would be O(K) in our case. Bubeck et al. [32] also study continuum-armn bandits and establish similar regret bound, but with respect to the near-optimality dimension, which is again ((K) )) in our case. Hence, the guarantees of Kleinberg et al.
[31] and Bubeck et al. [32], when applied our setting, are worse than our Ö (VT) regret bound.
(VT) regret bound, but requires the The literature on bandit convex optimization [33-35] offers δ objective to be concave, which the Nash social welfare (NSW) is not.²
Another key aspect of our framework is the focus on fairness. Recently, several papers have focused on fairness in the multi-armed bandit problem. For instance, Joseph et al. [37] design a UCB variant which guarantees what they refer to meritocratic fairness to the arms, i.e., that worse arm is never preferred better arm regardless of the algorithm's 's confidence intervals for them. Liu et al. [38] require that similar arms be treated similarly, i.e., two arms with similar mean rewards be selected with similar probabilities. Gillen et al. [39] focus on satisfying fairness with respect to an unknown fairness metric. Finally, Patil et al. [40] assume that there are external constraints requiring that
2 SSine NSW is log- lonccen,,ve, one might argue that we can apply these results to log- NSg. However, regret bound in NSW does not imply the desired regret bound in NSW.
3

---

each arm be pulled in at least certain fraction of the rounds and design algorithms that achieve low regret subject to this constraint. All these papers seek to achieve faimess with respect to the arms. In contrast, in our work, the arms are "inanimate" (e.g. policy decisions) and we seek fairness with respect to the agents, who are separate from the arms.
2 Preliminaries
For n E N. define [n)] [L. Let N,K E N. In the multi-agent multi-armed bandit (MA-MAB) problem, there is set of agents [N] and a set of arms [K]. For each agent i E [N] and arm j [ there is a reward distribution Di, with mean p and support [0, 1];² when arm j is pulled, each agent observes an independent reward sampled from Di.j. Let us refer to as the (true) reward matrix.
k² = (NN,)))( E [0, 1|
As mentioned in the introduction, pulling agent, but disastrous to another. Hence, we are interested in probability distributions over arms, which refer to as policies. The K K-simplex, denoted A K is the set of all policies. For a policy p E A Pj denotes the probability with which arm j is pulled. Note that due to linearity of expectation, the expected reward agent i under policy p is Σ Py 1
Policies:
deterministically may be favorable to one
Nash social welfare: The Nash social welfare is defined the product of (expected) rewards to the agents. Given μ (M),)))( and policy p AK, define NSW (p, μ)) Thus, the (true) Nash social welfare under policy p is NSW(p, n²).. Hence, we knew μr, we would pick an optimal policy p" E mag,aa NSW (p, μ²).. However, because we do not know fe in advance, our algorithms will often produce an estimate Jr, and use it choose a policy; the quantity NSW(p) (p. (2) will play a key role in our algorithms and their analysis.
II (Ej=1p Pj- (a.))
Algorithms: An algorithm for the MA-MAB problem chooses a policy p' in each round t N. Then, an arm is sampled according to policy p', and for each agent i [N], a reward X is sampled independently from distribution Di At the end of round t, the algorithm learns the sampled arm a' and the reward vector (X; jet )EEN) which it can use to choose policies in the later rounds.
Reward estimates: All our algorithms maintain an estimate of the mean reward matrix μ² at every round. For round f and arm j E [K]. let n² = -'= 1[a = =] denote the number of times arm is pulled the beginning of round t, and let F v Eej X denote the average reward experienced by agent i from the nz pulls of arm j thus far. Our algorithms treat these as an estimate of nT, available at the beginning of round f. Let 77t (FL,))ENN)
Regret: Recall p" is an optimal policy that has the highest Nash social welfare. The instantaneous regret in round due (cumulative) regret in round due to an algorithm choosing p² p'.....P'' D R = D r We note that R² and r² are defined for a specific algorithm, which will be clear from the context. We are interested in bounding the expected regret [[R""] of an algorithm at round T, where the expectation is over the randomness involved in sampling the arms a' and the agent rewards xXfaa)iels for I E [T]. We say that algorithm is horizon-dependent if it needs to know T in advance, and horizon-independen if it yields a regret bound at each possible simultaneously.
algorithm choosing p' is rd NSW()" ,²) NSW (p' p .J"). The
3 Explore-First
Perhaps the simplest algorithm (with sublinear regret bound) in the classic single-agen MAB framework is Explore-Firss It is composed of two distinct stages. The first stage is exploration, during which the algorithm pulls each arm I. times. At the end of this stage, the algorithm computes the arm ā with the best estimated mean reward, and in the subsequent exploitation stage, pulls arm @ in every
i We need the support of distribution to be non-negative and bounded, but the upper bound of is without loss of generality. All our bounds scale linearly with the upper bound on the support. 'The algorithms study do not introduce any further randomness in choosing the policies.

---

round. The algorithm is horizon herizen-dependent,, i.e., it takes the horizon T as imput and sets L as function
of T. Setting L = θ K - log$ (T) yields regret bound E E[R"] = O K r log (T) [1].
In our multi-agent variant, presented as Algorithm 2 in the supplementary material, the exploration stage pulls each arm L times as before. However, at the end of this stage, the algorithm computes, not an arm ã. but policy P with the best estimated Nash social welfare. During exploitation, it then uses policy p in every round. With an almost identical analysis as the single-agent setting, we recover the aforementioned regret bound with an additional N2/3 factor for N agents.
Using a novel and more intricate argument, we show that a different tradeoff between the exponents of N and K can be obtained, where N2/3 is reduced to N at the expense of increasing K K1/3 to K2/3 (and adding a logarithmic term). We later use this approach again our analysis of more sophisticated algorithms.
We remark that Algorithm 2 can be implemented efficiently. The only non-trivial step is to compute the optimal policy given an estimated reward matrix, i.c., P E arg p NSW (p. μi). Since the Nash social welfare is known be log-concave, this can be solved in polynomial time [41].
Our analysis of Explore-Fin First and later algorithms relies on a few elementary lemmas regarding the (p. (1). We mainly interested in how much the function can change when its arguments change. To that end, the following folklore result translates the difference in product to sum of point-wise differences that are easier to deal with. All missing proofs are in the supplementary material.
behavior of the Nash social welfare function NSW(p,
Lemma 1. Let a;, b, E [0, for E [N]. Then, II=-1 a. N by
S
1=11 la: - bz). EA
Using Lemma I, we can easily analyze Lipschitz-continiity of NSW μ1) when either p or f changes and the other is fixed. First, we consider change in p with μ fixed.
Lemma 2. Given a reward matrix μ E [o, 1]N and policies p', p²²²² E A we have
NNW(W', ,n) - <S: nn) S N ||'' - -v²11= NN. ESE(K) [p] p]
Next, we consider change in μe with p fixed.
Lemma 3. Given a policy p E AK, and reward matrices μ¹, .2² E E 1| we have
NSW NSW x²) S EiEin EsejKyps 11:5 pāsl-
We are now ready to establish the regret bounds for Explore-First.
Theorem 1. Explore-Fine FFrst is horizon-dependent and has the following expected regret at round T.
When L θ (N K-3T ST log (NKT)). B[R²) = o (N KN logà (NKT))
When L - e ( KV5K-337' 37 log (NKT)). = NN =
log (NKT)).
Epsilon-Greedy
A slightly more sophisticated algorithm than Explore-First is Epsilon-Greeddy, which is presented as Algorithm 3 in the supplementary material. It spreads out exploration instead of performing all at the beginning. Specifically,, at each round t, it performs exploration with probability e and exploitation otherwise. Exploration cycles through the arms in a round-robin fashion, while exploitation uses the policy p' with the highest Nash social welfare under the current estimated reward matrix (rather than choosing a single estimated best arm as in the classical algorithm).
Like Explore-First, Epsilon- can be implemented efficiently. The only non-trivial step is to compute & E arg max NSW (p. P). which, as mentioned before, can be done efficiently.
The key advantage of Grredy over Explore-Firs is that it is horizon-independeen However, in the µ computed in Explore-First at the end of exploration, each Ti. the average of L. iid samples, where L is fixed. In contrast, in the ø computed in Epsilon- Greedy in round t, each pi, is the
5

---

average of nij iid samples. The fact that n/ is itself a random variable and the - are correlated through the n prevents direct application of certain statistical incqualities, thus complicating the analysis of Fpsilon-Greedy, To address this, we first present a sequence of useful lemmas that apply to any algorithm, and then use them to prove the regret bounds of Epsilon-Greedy and later UCB.
4.1 Useful Lemmas
Recall that 1d" and Jr' denote the true reward matrix and the estimated reward matrix the beginning of round I, respectively. Our goal is to find an upper bound on the quantity JNSW (p, 1²*) - NSW (p, j²) that, with high probability, holds at every p E A simultaneously. To that end, first need to show that 72' will be close to f with high probability.
Recall that random variable ni denotes the number of times arm j is pulled by algorithm before round I, and F4 is an average over nt independent samples. Hence, we cannot directly apply Hoeffding's s inequality, but we can nonetheless use standard tricks from the literature.
Lemma 4. Define r = = [ and event 8r A Vi E [N],5 [K] [ Misl S r.. Then, for any algorithm and any t, we have Pr[E"] 2 1 A..
Conditioned on EL, we wish to bound NNS((p. (p. μx") NSW (p. 2i') simultaneously all p E A We provide two such (incomparable) bounds, which will form the crux of our regret bound analysis. The first bound is direct application of the Lipschitz-continuity analysis from Lemma 3.
Lemma 5. Conditioned on Et, we have that
Vp E A (NSW(p.P") NSW n²) SNN N. EjE[K) Py r..
The factor of N in Lemma 5 stems from analyzing how much 7J6 may deviate from μ¹ conditioned on Et in the worst case. However, even after conditioning on Et, J2' remains a random variable. Hence, may expect that its deviation, and thus the difference [NSW fi') - NSW p²)), may be smaller in expectation. Thus, to derive a different bound than in Lemma 5, we wish to apply McDiarmid's inequality. However, there are two issues in doing so directly.
McDiarmid's inequality bounds the deviation of NSW (p. fir) from its expected value. If jt' consisted of independent random variables, like in Explore-First, this would be equal to NSW (p, p²)) However, in general, these variables may be correlated through nz.. We use conditioning trick to address this issue
We cannot hope to apply McDiarmid's inequality at each p E A K separately and use the union bound because A is infinite. So we apply it at each p in a d-cover of AK apply the union bound, and then translate the guarantee to nearby p e A using the Lipschitz-continuity analysis from Lemma
The next result is one of the key technical contributions of our work with rather long proof. Lemma 6. Define the event
H. YpE NSW(p.FF) - NSW |=)] S / 112NK EJEKPs + Then, for any algorithu and any t, we have Pr( 2 1 - 2/t3.
Finally, we use the following simple observation in deriving our asymptotic bounds. Proposition 1. For constant p E R. ΣT t" is e (log T) i = -1 and @ (I++1) when p > -1.
4.2 Analysis of Ersedon-Greedy
We can now use these lemmas to establish the regret bounds for Epsilon-Greedy. Theorem 2. Opsilon-Greealy is horizon-indepennen, and has the following expected regret at any round T.
Ife' - (Ni logs (NKt) for all t, E[R"] o (N' log (NKT)).
-fe'= e (N log (NKI) for all I, B|Re" = o (og

---

UCB
Algorithm 1: UCB
Input: Number of agents N, number of arms K
Parameters :Conidence parameter af for each & N // Pull each arm once
for t = ,,..., K do pl - policy that puts probability on arm
// Pull arm deterministically
end
for 1 K + 1,... do
Compute the estimated reward matrix 77'
p' +- arg pax NSW(p, T7') + a² Σje(K] ry. where rf - [og
end
In the classical multi-armed bandit setting, UCB first pulls each arm once. Afterwards, it merges exploration and exploitation cleverly by pulling, in each round, an arm maximizing the sum of its estimated reward and confidence interval term similar to rř in Algorithm 1. Our multi-agent variant similarly selects a policy that maximizes the estimated Nash social welfare plus a confidence term for policy, which simply takes linear combination of the confidence intervals of the arms.
Unlike Explore-Firs and Epsilon- Greedy, is not clear if our UCB variant admits an efficient implementation due to the step of computing arg pa NSW ()) + a² Σjε(K) P.rj. Due to the added linear term, the objective is no longer log-concave. This remains challenging open problem. However, we notice that this can also be viewed as the problem of optimizing polynomial over simplex, which, while NP-hard in general, admits a PTAS when the degree is constant [42, 43]. Hence, when the number of agents is constant, this step can be computed approximately, but remains to be seen how this approximation translates to the regret bound.
We show that UCB achieves the desired vT dependence on the horizon (up to logarithmic factors).
In Appendix A, we show that this optimal.
Theorem 3. UCB is horizon-independent and has the following expected regret any round T.
If N for all [[R"] (VKKTbog(NNK)))
Ifa' = / log( NKt) for all E[R = (N#K3T² = log (NKT)).
Proof. Fix one of two parameter choices:
1. a² = N for all and c= N.
2. a² /12NK log( for all i. and c /12NK log(NKT)).
Note that in both cases, a' for all t. Hence, serves upper bound a' that does not depend on t. We show that in both cases, rumning UCB with the a' parameter value yields a regret bound of [[RT] = O(cK O(cKVTlon (oTllg(NTT) Substituting the two choices c then yields the two regret bounds. Let again focus the event
4 A (SS(),,""> NSW (p. S EjE[KP r t
Recall the clean events Et and H. defined Lemmas and 6. Conditioned on Et H' note that C₁ holds for a² N due to Lemma 5, and for a² V12NK log N due to Lemma 6. Using Lemmas and and the union bound, we have Pr[-Ct] S Pr 1 1 1- (1 2/t3) (1 2/t3) < 4/t3.

---

Define a clean event C; - A12VT C. Here, we do not care about the first vT rounds because the maximum regret from these rounds O (VT). which permissible given our desired regret bounds.
By the union bound, we have Pr[-Ca] < T' 44vT)) = 4/vT. Thus, C is a high-probability event. In what follows, we derive an upper bound on the expected regret conditioned on Ca i.e. EIIt" [Ca]. Since conditioning on a high-probability event does not affect the expected value significantly, the desired regret bound will then follow. For any t [77, conditioned on C2 we have that
NSW(D" ( < NS 74) of
E Pj rj + NSW ,7' + a' KE(K]
Σ jE[K]
PJ
rj
S NSW ,x" ) + 20
Σ JE[K]
p/
r
+
8 L²
where the first and the last transition are from conditioning on Ca,, and the second transition is because p = p' maximizes the quantity NSW(p. + a' EjE[k] P. rj the UCB algorithm.
Let us write p!T = (p',. (p'....,p') ,,") for the random variable denoting the policies used by the algorithm, and pl = "p.....p'''.. to denote a specific value in (A k taken by the random variable.
Instead of analyzing | [C]] directly, we further condition UCB choosing specific sequence of policies pl That is, are interested in deriving an upper bound on [E[ [Ca A y = p
Interestingly, we show that this quantity is O (cKvTlog(NKT)) for every possible p.²
Fix an arbitrary plT) For t E [T'] and j E [K], define of = - Dj. Then, = oj For each j E [K]. let TỤ be the smallest t for which of 2 (VTTT (if no such t exists, let T T); note that given pld", T₃ is fixed and not a random variable. Also, we have that To 9j" ( (VTlog(NKT)) for each j E [K].
Let us define a clean event B é Vj [K] nz 2 (ogg(T)T)) We first show that this is a high probability event. Indeed, using Hoeffding's inequality, we have that for each E [K].
T < <VTlog(VTT) Ca A Tl = TTT] Pr m
< (log((KTT) Ct A m = ]m]
S Pr
m
N²K2T22
Taking union bound over j E [K]. we have that Pr [-B C. A plf = =p11 S NKkTT
Next, we bound E RT IC A pl = pl by using event B.
T
B R
C²
[ 2
Σ E [NSW ,x" - NSW(" w²) C. -
T
EI. [NSWWw ,4" NSW(6 - Co Ap'. =p - A.
< max(K, vT)
Σ
t=max [H+1
+ Pr B3 C* A !T
=p'']....
T
< ma VT)
Σ
E 2a Σ
poJ r5
c. Ap " - B
t=max K. ~T++1
JE[K]
Pr
B C. A
(7)
< max(K, VT) + + 2cy
2 log NKT))
A]
'Note that even after conditioning p policies and sampling the rewards of those actions.
[T there is still randomness left in sampling actions from the
8

---

The final transition holds because a I c a. E, r / /2 and conditioned on B, n) 2 2g for each E [K] and & E (T), where Cj = 1 Tj and Cj
")
(Tllg if t 2 Tj. Hence,
Ca A p p.r < max(K, vT) R²
+1 (T)) 20 20gg(
Pj
Vo
KE[K]
Pj
=max(K, ++ 2cv 200111222// 2lgg(NT)
E
(log
JE[K]
S <max(K, (, vT) vT) + 2cr (NT)
T
= =0 =o(ekVTio((KKT))
(Togg(
JEIK]
Because this bound holds for every possible O (eK (cKvTlog(NKT)) Finally, can that
IT we also have that EiR²
E[ Pr[C.] B[ + Pri-Cal E
< 1 0 cK (cVTTlog( +
4
1 =1=00 O -1 (cKVTlog(NKT))
Recall that substituting c = N and c= 12NK log(NN yields the two regret bounds.
We emphasize that our analysis of the multi-agent UCB differs significantly from the analysis of the classical (single-agent) UCB. For example, the use of clean event C. is unique to our analysis. More importantly, the expression in Equation (1) is also unique to setting in which the algorithm can "pull" a probability distribution over the arms. The corresponding expression in case of the be much simpler and straightforward to bound. In contrast, need to additional tricks to derive the bound of O [K log(NNT))
classical UCB turns
Finally, the proof presented above, showed that, assuming the clean event C. the expected regret is small conditioned on any sequence of policies that the UCB algorithm might use. At the first glance, this may seem surprising. However, keen reader can observe that the clean event C, can only occur when the UCB algorithm uses a "good" sequence of policies that leads to low expected regret. A similar phenomenon is observed in the analysis of the classical (single-agent) UCB algorithm as well (see, e.g., []]): assuming different clean event, the classical UCB algorithm guaranteed not pull suboptimal arms too many times.
Discussion
Our work leaves open several directions for the future. There are immediate technical challenges such as polynomial-time implementation and a logarithmic instance-dependent regret bound for our UCB variant (see Section 5), and deriving improved lower bounds which scale with the number of agents N (see Appendix A). It would also interesting to consider other fairness notions such as the egalitarian welfare the core [4]. More broadly, our work promotes multi-agent variant in which must strike a tradeoff between the reward functions of multiple agents. An exciting future direction would be consider such multi-agent variants of other classical single-agent
-making problems.
Acknowledgments and Disclosure of Funding
Nisarg Shah acknowledges support from an NSERC Disocvery Grant.
References
[1] A. Slivkins. Introduction to multi-armed bandits. Foundations and Trends in Machine Learning, 12(1-2):1-286, 2019.
[2] H. Moulin. Fair Division and Collective Welfare. MIT Press, 2003.

---

[3] F. Brandt, V. Conitzer, U. Endress, J. Lang, and A. D. Procaccia, editors. Handbook of Computational Social Choice. Cambridge University Press, 2016.
[4] B. Fain, K. Munagala, and N. Shah. Fair allocation of indivisible public goods. Proceedings of the 19th ACM Conference Economics and Computation (EC), pages 575-592, 2018.
[5] V. Conitzer, R. Freeman, and N. Shah. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 629-646, 2017.
[6] G. Amanatidis, G. Birmpas, A. Filos-Ratsikas. A. Hollender, and A. A. Voudouris. Maximum Nash welfare and other stories about EFX. In Proceedings of the 29th International Joint Conference Artificial Intelligence (IJCAT), pages 24-30, 2020.
[7] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang. The unreason- able fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3):1332 2019.
[8] R. Freeman, S. M. Zahedi, and V. Conitzer. Fair and efficient social choice in dynamic settings. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (ICAAI), pages 4580 4587, 2017.
[9] H. Aziz, A. Bogomolnaia, and H. Moulin. Fair mixing: The case of dichotomous preferences. In Proceedings of the 20th ACM Conference on Economics and Computation (EC), pages 753-781, 2019.
[10] B. Fain, A. Goel, and K. Munagala. The core of the participatory budgeting problem. In Proceedings of the 12th Conference on Web and Internet Economics (WINE), pages 384-399, 2016.
[11] F. Brandl, F. Brandt, D. Peters, C. Stricker, and W. Suksompong. Funding public projects: A case for the Nash product rule. Manuscript, 2020.
[12] R. Cole, N. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod. Convex program duality, Fisher markets, and Nash social welfare. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 459-460, 2017.
[13] N. Anari, T. Mai, S. O. Gharan, and V. V. Vazirani. Nash social welfare for indivisible items under separable, piecewise- linear concave utilities. Proceedings of the 29th Annual ACM- SIAM Symposium Discrete Algorithms (SODA), pages 2274-2290, 2018.
[14] E. Lee. Apx-hardness of maximizing Nash social welfare with indivisible items. Information Processing Letters, 122:17-20, 2017.
[15] J. Garg and P. McGlaughlin. Improving Nash social welfare approximations. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (ICCAI), pages 294-300, 2019.
[16] R. Cole and Gkatzelis. Approximating the Nash social welfare with indivisible items. SIAM Journal Computing, 47(3):1211-1236 2018
[17] Garg, M. Hoefer, and K. Mehlhorn. Approximating the Nash social welfare with budget- additive valuations. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2326-2340, 2018
[18] Auer, N. Cesa-Bianchi, Y. Freund, and E. Schapire. The nonstochastic multi-armer bandit problem. STAM Journal Computing, 32(():48-77) 2002.
[19] T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4 1985.
[20] R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 681-690, 2008
[21] W. R. Thompson. On the likelihood that one unknown probability exceeds another view of the evidence of two samples. Biometrika, 25(3/4):285-29) 1933.
10

---

[22] R. Kleinberg, A. Niculescu-Minn and Y. Sharma. Regret bounds for sleeping experts and bandits. Machine learning, 80(2-3):245-272. 2010.
[23] M. Woodroofe. A one-armed bandit problem with concomitant variable. Journal of the American Statistical Association, 74(368):799-806 1979.
[24] Y. Yue, J. Broder, R. Kleinberg, and T. Joachims. The K-armed dueling bandits problem. Journal of Computer and System Sciences, 7835):158--155, 2012.
[25] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for oblti-objective bayesian optimization using random scalarizations. In UAI, 2019.
[26] M. Chakraborty, K. Y. P. Chua, S. Das, and B. Juba. Coordinated versus decentralized ex- ploration in multi-agent multi-armed bandits. Proceedings of the 26th International Joint Conference Artificial Intelligence (IJCAI), pages 164-170, 2017.
[27] E. Bargiacchi, T. Verstraeten, D. Roijers, A. Nowé, and H. Hasselt. Learning to coordinate with coordination graphs in repeated single-stage multi-agent decision problems. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 482-490, 2018.
(28) Peter Landgren, Vaibhav Srivastava, and Naomi Ehrich Leonard. Distributed cooperative decision-making in multiarmed bandits: Frequentist and bayesian algorithms. 2016 IEEE 55th Conference on Decision and Control (CDC), pages 167-172, 2016.
[29] Shahin Shahrampour, Alexander Rakhlin, and Ali Jadbabaie. Multi-armed bandits in multi-agent networks. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 2786-2790, 2017. doi: 10.1 10.109//CASPP..017.799222
[30] Abhimanyu Dubey and Alex 'Sandy' Pentland. Kernel methods for cooperative multi-agent contextual bandits. In /CML, 2020.
[31] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. arXiv preprint arXiv: 2013.
[32] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári. X-armed bandits. The Journal of Machine Learning Research, 12:1655-1695, 2011.
[33] Elad Hazan and Kfir Y Levy. Bandit convex optimization: Towards tight bounds. In NIPS, pages 784-792, 2014.
[34] Sébastien Bubeck and Ronen Eldan. Multi-scale exploration of convex functions and bandit convex optimization. In Proceedings of the 29th Conference Computational Learning Theory (COLT), pages 583-589, 2016.
[35] Sébastien Bubeck, Yin Tat Lee, and Ronen Eldan. Kernel-based methods for bandit convex optimization. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 72-85, 2017.
[36] Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on bayesian optimization of expensive cost functions, with application active user modeling and hierarchical reinforcement learning. ArXiv, abs/1001.2599 2010.
[37] M. Joseph, M. Kearns, J. H. Morgenstern, and Roth. Fairness learning: Classic and contextual bandits. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS), pages 325-333, 2016.
[38] Y. Liu, G. Radanovic, C. Dimitrakakis, D. Mandal, and D. C. Parkes. Calibrated fairness in bandits. arXiv preprint 170iv 01855, 2017.
[39] S. Gillen, C. Jung, M. Kearns, and A. Roth. Online learning with an unknown fairness metric. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems (NIPS), pages 2600-26099 2018

---

[40] V. Patil, G. Ghalme, V. Nair, and Y. Narahari. Achieving faimess in stochastic multi- armed bandits. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 5379, 2020.
[41] E. Eisenberg and D. Gale. Consensus of subjective probabilities: The pari- vari-mutuel method. The Annals of Mathematical Statistics,
1959.
[42] E. de Klerk, M. Laurent, and P. A. Parrilo. A PTAS for the minimization of polynomials of fixed degree over the simplex. Theoretical Computer Science, 361(2-3):210-235 2222,, 2006.
[43] E. de Klerk, M. Laurent, and Z. Sun. An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex. Mathematical Programming, 151(2):433 457, 2015.
[44] M. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Limitations of our work and
possibilities for future work are described in Section 6.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work is purely theoretical in nature, and we do not anticipate any immediate societal risks.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? assumptions can be found in Section 2.
[Yes] All the
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs of all theoretical results are included. Some of the proofs are relegated to the supplementary material due space constraints.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL.? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l rrure using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
12

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "s7aRGC4WbGr", "reviewer": "Reviewer_qaWv", "summary": "This paper studies a multi-armed bandits problem with multiple agents. Arms have agent specific reward distributions associated with them. An arm is pulled at each step and each agent receives a reward sampled from their corresponding agent specific reward distribution for this arm. The goal of the learner is to find a distribution over arms that maximizes an appropriate aggregate notion of rewards earned by all agents – the Nash welfare.\n\nThe paper develops variants of three standard algorithms – one that explores for a fixed number of rounds and then exploits (Explore-First), an epsilon-greedy style algorithm, and a UCB style algorithm, to minimize a notion of regret which measures the difference between the Nash welfare of the solution at time t and the optimal Nash welfare. The paper derives upper bounds on the expected regret of the algorithm in each case. For UCB, the upper bound matches the lower bound (in the appendix) in terms of its dependence on parameter T (time horizon).", "questions": "", "limitations": "", "rating": 6, "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": "Originality – This appears to be the first work that studies Nash welfare maximization in a multi-agent multi-armed bandits setting and obtains a \\sqrt{T} regret bound. The paper does a good job of highlighting additional challenges posed by this setup. For instance, the mean estimates of the agents (for a given arm) are not independent as they all depend on the number of times that arm was pulled, which is same for all agents.\n\nQuality – \n1.\tThe theoretical results in the paper are fairly intuitive and appear to be sound. While the upper bound for UCB matches the lower bound in terms of T, the dependence on other parameters (K: #arms, N: #agents) appears to be suboptimal. \n2.\tAlthough the paper argues that “traditionally, the focus is on optimizing the exponent of T rather than that of K”, I do not completely agree with the statement, especially in the context of the current paper where N x K may be very large.\n3.\tA stronger lower bound in terms of K and N would have helped in understanding the quality of the current upper bounds. Even empirical results will provide additional information about the tightness of the current upper-bound.\n4.\tCombining the fact that the upper bound for UCB may be very loose (in terms of N and K) with the fact that it will be inefficient to implement, makes the assessment of the utility of the algorithm hard.\n\nClarity – The paper is very well written and easy to follow.\n\nSignificance – See point 4 under Quality. This makes it hard to argue for the significance of the current work. Having said that, I agree that the paper takes an important first step for an interesting problem.\n\nStrengths – Very well written, the regret of UCB has optimal dependence in terms of T\n\nWeaknesses – Unclear about the tightness of the bounds in terms of N and K (see details above)\n\n**Update**: Dear Authors, thank you for your response. I agree that $T \\geq K$ is a harmless assumption. However, the same is not true for $T \\geq N$, and hence not true for $T \\geq N \\times K$ (am I missing something here?). I still believe that this is worth exploring, but the paper is undoubtedly a good first step in this direction. My score remains unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses various limitations such as possible sub-optimal dependence on N and K, and difficulty in optimising the objective required by UCB.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "pKTbCHiTXEY", "reviewer": "Reviewer_mA86", "summary": "In this paper, the authors propose to minimize the Nash Social Welfare (NSW) function -- the product of utilities, in a multi agent multi-armed bandit problem. The NSW strikes a balance between utilitarian and egalitarian optimization in a multi agent framework. The product of utility maximization is a log-concave optimization for which they propose three algorithms -- Explore-then-commit, Epsilon-Greedy, and UCB.  They establish regret upper bounds for the proposed algorithms, with UCB having the best \\tilde{O}(\\sqrt{T}) regret.  ", "questions": "", "limitations": "", "rating": 6, "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": "Pros\n\n- The maximization of the NSW objective in a multi-agent setting promotes fairness consideration for the multi-agent bandits problem. \n\n- Technically, the bandit optimization problem is a special log-concave for which this paper proposes the first \\tilde{O}(\\sqrt{T}) regret bound (to the best of my knowledge).  The authors also discuss why the existing results will not provide such a regret bound (see drawbacks for improving this). \n  \n- The writing is clear and easy to follow (except for a few aspects described shortly). The proof sketches are insightful. \n\nDrawbacks and Suggestions\n\n- The key drawback of the paper is the centralized optimization in the multi-agent setting. Maybe the authors can discuss how the agents are incentivized to submit truthful feedback to the centralized arbiter. \n\n- Can you provide the details of the zooming dimension  (as per Kleinberg et al.) computation . Also, why the tree-search approach in  'Multi-scale exploration of convex functions and bandit convex optimization' not applicable here? \n\n- The related works in the no-regret learning in non-cooperative games is not discussed properly. Please add these works. E.g. 'Bandit Learning in Concave N-Person Games' - Bravo et al. and the references therein.\n\n- Provide a proof sketch of Lemma 6 in the main paper. Can the union bound on the possible number of pulls be avoided there? Also what is the slackness added by taking such a union bound? \n\n- Discussions on when Lemma 5/Lemma 6 should be applied depending on N,K, and T will be useful. In particular, can we adaptively set \\alpha_t in UCB by switching from N to O(\\sqrt{NKlog(NKt)}) (or the opposite) to improve the regret bound? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is theoretical in nature. It deals with maximizing the Nash Welfare objective that is established to promote fairness in the literature. Thus, I think this paper will not have negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "IGkiocqEgIV", "reviewer": "Reviewer_2Wto", "summary": "This paper studies multi-agent multi-armed bandits under heterogeneity (where arm means vary across users), with the objective to optimize Nash social welfare to ensure fair allocation of pulls in the obtained policy. The authors present variants of explore-first, epsilon-greedy, and upper confidence bound strategies to achieve fair decision-making. Each algorithm obtains \"fair\" regret matching the standard counterpart, along with a $ \\Omega(\\sqrt{T})$ lower bound in the Appendix. The central technical (theoretical) contribution is a concentration result on the fluctuation of NSW that exploits the Lipschitz property of the objective coupled with a covering argument, which is then utilized subsequently to derive regret bounds for each of the proposed algorithms. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality and Quality: I like the topic and contributions of the paper. Fairness in multi-armed bandits is typically concerned with fairness across arms, and multi-agent decision-making typically involves purely cooperative objectives, which suffer from the _tyranny of the majority_ effect as the authors have rightly pointed out. The paper does present the feasibility of NSW as an objective for bandit algorithms and analyzes popular single-agent algorithms, and I feel that it serves as a good contribution to the development of more work in this area. However, while the paper does address multi-agent decision-making, the algorithms and setup are essentially \"single-agent\" in the sense that one controller decides the policy for all agents. From a theoretical and algorithmic perspective, this may appear to be a necessary first-step simplification, but most deployment scenarios for multi-agent decision-making do not allow for such synchronicity, which is something the authors should discuss.\n\nThe previous remark is related to the broader concern around neglecting quite a vast and fast-growing literature around multi-agent multi-armed bandits in more realistic, distributed environments [https://arxiv.org/abs/1606.00911, https://scholar.harvard.edu/files/shahin/files/icassp_2017.pdf, https://arxiv.org/abs/2008.06220, and references therein], where heterogeneity and delay in communication ensure that the algorithms proposed are \"multi-agent\" in the true sense of the term, rather than a single-agent controlling a more nuanced objective than cumulative reward. In this regard, this work is also related to multi-objective bandit optimization [https://people.eecs.berkeley.edu/~kandasamy/pubs/pariaUAI19mobo.pdf, https://arxiv.org/abs/1905.12879] where a measure of performance employed is Pareto optimality, instead of cumulative reward. Discussing these approaches in context with the proposed research will go a long way in shaping further research into practical algorithms in real-world settings, moving beyond regret bounds that are effectively \"single-agent\".\n\nGoing through the technical parts, I feel like the previous revisions have ironed out the remaining technical issues, although I am curious to know if Lemma 6 can perhaps be tightened more by considering a smaller class of policies than the entire K-simplex, following a similar line of argument for UCB policies as done in https://arxiv.org/abs/1907.05388, for example.\n\nClarity: The paper is well-written and easy to follow.\n\nSignificance: Fairness in online learning is an important topic of interest to the NeurIPS community.\n\nIn summary, after placing this work in context to the work in distributed multi-agent decision-making, I feel that it would be a good contribution to the conference.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The major limitations of the work as is are the \"centralized\" nature of the proposed policy and the intractability of the UCB algorithm presented. The authors should discuss this in more detail in the updated version.\n\nGiven that the paper discusses fairness in a technical sense in context of online learning, the authors have done a good job of addressing the societal impact of their work, and I do not foresee any additional negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "2S6iCdJ2rE4", "reviewer": "Reviewer_dz9B", "summary": "The paper studies stochastic multi-agent multi-armed bandits where the reward distribution could be heterogeneous, i.e., the mean reward for agents on an arm could be different.  The authors consider Nash social welfare as the fairness criteria and aim to learn a distribution on arm plays that result in optimal Nash social welfare. Thress algorithms based on Explore-Then-Commit, Epsilon Greedy, and UCB are given and their performance is analyzed.", "questions": "", "limitations": "", "rating": 5, "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": "Using Nash social welfare as a fairness criterion in multi-armed-bandits is interesting. However, I felt that setup and analysis are weak. My comments are:\n\n1) Why do all the agents have to play the same arm in each round. If they can also play different arms, cannot they learn faster?\n\n2. Line 219-220:  If $\\hat{\\mu}_{i,j}^t$ is obtained from $n_j^t$ and the rewards have bounded support, why cannot be Hoeffding's inequality be applied? What violates the hypothesis of Hoeffding's result?\n\n3. The bound in Lemma 5 holds with some probability or it is a deterministic bound?'\n\n4. Lemma 4: In the definition of $\\Epsilon^t$, are parenthesis missed?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers a variant of the MAB problem where there are N agents who may perceive the "reward" from the K arms differently. The goal considered in this paper is to obtain a fair distribution over the arms in terms of Nash social welfare. This application is new, even if the algorithms and analysis do not seem to be that different from the standard MAB literature. The classical lower bound is also shown to hold in this case.
Decision: Accept (Poster)