Fair Algorithms for Multi-Agent Multi-Armed Bandits
Year: 2021

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.

heading: 1 Introduction
text: In the classical (stochastic) multi-armed bandit (MAB) problem, a principal has access to K arms and pulling arm j generates a stochastic reward for the principal from an unknown distribution Dj with an unknown mean µ∗j . If the mean rewards were known a priori, the principal could just repeatedly pull the best arm given by arg maxj µ ∗ 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 jt in round t, 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 a horizon T , defined as ∑T t=1(maxj µ ∗ j − µ∗jt). 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 of the arms pulled by the learning algorithm up to round T .
This problem can model situations where the principal is deliberating a policy decision and the arms correspond to the different alternatives she can implement. However, in many real-life scenarios, making a policy decision affects not one, but several agents. For example, imagine a company making a decision that affects all its employees, or a conference deciding the structure of its review process, which affects various research communities. This can be modeled by a multi-agent variant of the multi-armed bandit (MA-MAB) problem, in which there are N agents and pulling arm j generates a (possibly different) stochastic reward for each agent i from an unknown distribution Di,j with an unknown mean µ∗i,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 not 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 (NeurIPS 2021).
j may be defined as the total mean reward it gives to all agents, i.e., ∑ i µ ∗ i,j . 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 a scenario with ten agents, two arms, and deterministic rewards. Suppose four agents derive a reward of 1 from the first arm but 0 from the second, while the remaining six derive a reward of 1 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 to 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 a 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 a 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 j gives expected utility
∑ j pj · µ∗i,j to agent i. Hence, the goal is to maximize NSW(p, µ∗) =∏N
i=1( ∑K j=1 pj · µ∗i,j) 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 a 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 a wide variety of settings [4–11]. For example, a folklore result shows that in our setting such a solution will always lie in the core; we refer the reader to the work of Fain et al. [4] for a formal definition of the core as well as a 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 complete 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∑T t=1(maxp NSW(p, µ
∗) − NSW(pt, µ∗)), where pt is the distribution selected in round t. Our goal in this paper is to design algorithms whose regret is sublinear in T .

heading: 1.1 Our Results
text: We consider three classic algorithms for the multi-armed bandit problem: Explore-First, EpsilonGreedy, and UCB [1]. All three algorithms attempt to balance exploration (pulling arms only to learn their rewards) and exploitation (using the information learned so far to pull “good” arms). Explore-First performs exploration for a number of rounds optimized as a function of T followed by exploitation in the remaining rounds to achieve regret Õ ( K1/3T 2/3 ) . 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/2T 1/2 ) . Here,
Õ hides log factors. Traditionally, the focus is on optimizing the exponent of T rather than that of K as the horizon T 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-independent o(T 1/2) regret [18].1
1In instance-independent bounds, the constant inside the big-Oh notation is not allowed to depend on the (unknown) distributions in the given instance. UCB also achieves an O(log T ) instance-dependent regret bound, which is also known to be asymptotically optimal [19]. For further discussion, see Section 6.
We propose natural multi-agent variants of these three algorithms. Our variants take the Nash social welfare objective into account and select a distribution over the arms in each round instead of a single arm. For Explore-First, we derive Õ ( N2/3K1/3T 2/3 ) regret bound, which recovers the
aforementioned single-agent bound with an additional factor of N2/3. We also show that changing a parameter of the algorithm yields a regret bound of Õ ( N1/3K2/3T 2/3 ) , which offers a different tradeoff between the dependence on N and K. For Epsilon-Greedy, we recover the same two regret bounds, although the analysis becomes much more intricate. This is because, as mentioned above, Epsilon-Greedy is a horizon-independent algorithm (i.e. it does not require apriori knowledge of T ), unlike Explore-First. For UCB, we derive Õ ( NKT 1/2 ) and Õ ( N1/2K 3 2T 1/2 ) regret bounds; our
dependence on K worsens compared to the classical single-agent case, but importantly, we recover the same √ T dependence, which is provably optimal (see Appendix A).
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 a Lipschitz-continuity analysis of the Nash social welfare function and the use of new tools such as the McDiarmid’s inequality which are not needed in the standard analysis. Second, the optimization is over an infinite space (the set of distributions over arms) rather than over a 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 a multi-agent viewpoint that requires striking a tradeoff between multiple reward functions; this can be applied to other classical singleagent problems. More technically, as explained below, the existing MAB literature does not provide a√ T bound for the Nash social welfare objective. Our regret bounds may be generalizable to a broader family of objectives for which a √ T bound was previously unknown.

heading: 1.2 Related Work
text: 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] from the perspective of a single agent. We note that other multi-agent variants of the multi-armed bandit problem have been explored recently [26, 27], including in distributed environments [28–30]. However, they still involve a 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 theK-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-armed bandits, but establish a Õ ( T γ+1 γ+2 ) regret
bound, where γ is the zooming dimension, which would be Θ(K) in our case. Bubeck et al. [32] also study continuum-armed bandits and establish a 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 to our setting, are worse than our Õ (√ T ) regret bound.
The literature on bandit convex optimization [33–35] offers Õ (√ T ) regret bound, but requires the
objective to be concave, which the Nash social welfare (NSW) is not.2
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 as meritocratic fairness to the arms, i.e., that a worse arm is never preferred to a better arm regardless of the algorithm’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
2Since NSW is log-concave, one might argue that we can apply these results to log-NSW. However, a regret bound in log-NSW does not imply the desired regret bound in NSW.
each arm be pulled in at least a certain fraction of the rounds and design algorithms that achieve low regret subject to this constraint. All these papers seek to achieve fairness 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.

heading: 2 Preliminaries
text: For n ∈ N, define [n] = {1, . . . , n}. Let N,K ∈ N. In the multi-agent multi-armed bandit (MA-MAB) problem, there is a set of agents [N ] and a set of arms [K]. For each agent i ∈ [N ] and arm j ∈ [K], there is a reward distribution Di,j with mean µ∗i,j and support [0, 1];3 when arm j is pulled, each agent i observes an independent reward sampled from Di,j . Let us refer to µ∗ = (µ∗i,j)i∈[N ],j∈[K] ∈ [0, 1]N×K as the (true) reward matrix.
Policies: As mentioned in the introduction, pulling an arm deterministically may be favorable to one agent, but disastrous to another. Hence, we are interested in probability distributions over arms, which we refer to as policies. The K-simplex, denoted ∆K , is the set of all policies. For a policy p ∈ ∆K , pj denotes the probability with which arm j is pulled. Note that due to linearity of expectation, the expected reward to agent i under policy p is ∑K j=1 pj · µ∗i,j .
Nash social welfare: The Nash social welfare is defined the product of (expected) rewards to the agents. Given µ = (µi,j)i∈[N ],j∈[K], and policy p ∈ ∆K , define NSW(p, µ) =∏N i=1 (∑K j=1 pj · µi,j ) . Thus, the (true) Nash social welfare under policy p is NSW(p, µ∗). Hence, if we knew µ∗, we would pick an optimal policy p∗ ∈ arg maxp∈∆K NSW(p, µ∗). However, because we do not know µ∗ in advance, our algorithms will often produce an estimate µ̂, and use it to choose a policy; the quantity NSW(p, µ̂) will play a key role in our algorithms and their analysis.
Algorithms: An algorithm for the MA-MAB problem chooses a policy pt in each round t ∈ N. Then, an arm at is sampled according to policy pt, and for each agent i ∈ [N ], a reward Xti,at is sampled independently from distribution Di,at . At the end of round t, the algorithm learns the sampled arm at and the reward vector (Xti,at)i∈[N ], 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 t and arm j ∈ [K], let ntj = ∑t−1 s=1 1[a
s = j] denote the number of times arm j is pulled at the beginning of round t, and let µ̂ti,j =
1 ntj
∑ s∈[t−1]:as=j X s i,j denote the average reward
experienced by agent i from the ntj pulls of arm j thus far. Our algorithms treat these as an estimate of µ∗i,j available at the beginning of round t. Let µ̂ t = (µ̂ti,j)i∈[N ],j∈[K].
Regret: Recall that p∗ is an optimal policy that has the highest Nash social welfare. The instantaneous regret in round t due to an algorithm choosing pt is rt = NSW(p∗, µ∗) − NSW(pt, µ∗). The (cumulative) regret in round T due to an algorithm choosing p1, . . . , pT is RT = ∑T t=1 r
t. We note that RT and rt are defined for a specific algorithm, which will be clear from the context. We are interested in bounding the expected regret E[RT ] of an algorithm at round T , where the expectation is over the randomness involved in sampling the arms at and the agent rewards (Xti,at)i∈[N ] for t ∈ [T ].4 We say that an algorithm is horizon-dependent if it needs to know T in advance, and horizon-independent if it yields a regret bound at each possible T simultaneously.

heading: 3 Explore-First
text: Perhaps the simplest algorithm (with a sublinear regret bound) in the classic single-agent MAB framework is Explore-First. It is composed of two distinct stages. The first stage is exploration, during which the algorithm pulls each arm L times. At the end of this stage, the algorithm computes the arm â with the best estimated mean reward, and in the subsequent exploitation stage, pulls arm â in every
3We need the support of the distribution to be non-negative and bounded, but the upper bound of 1 is without loss of generality. All our bounds scale linearly with the upper bound on the support.
4The algorithms we study do not introduce any further randomness in choosing the policies.
round. The algorithm is horizon-dependent, i.e., it takes the horizon T as input and sets L as a function of T . Setting L = Θ ( K− 2 3T 2 3 log 1 3 (T ) ) yields regret bound E[RT ] = O ( K 1 3T 2 3 log 1 3 (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 â, but a 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 in 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 N1/3 at the expense of increasing K1/3 to K2/3 (and adding a logarithmic term). We later use this approach again in 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.e., p̂ ∈ arg maxp∈∆K NSW(p, µ̂). Since the Nash social welfare is known to be log-concave, this can be solved in polynomial time [41].
Our analysis of Explore-First and later algorithms relies on a few elementary lemmas regarding the behavior of the Nash social welfare function NSW(p, µ). We are mainly interested in how much the function can change when its arguments change. To that end, the following folklore result translates the difference in a product to a sum of point-wise differences that are easier to deal with. All missing proofs are in the supplementary material.
Lemma 1. Let ai, bi ∈ [0, 1] for i ∈ [N ]. Then, ∣∣∣∏Ni=1 ai −∏Ni=1 bi∣∣∣ ≤∑Ni=1 |ai − bi|.
Using Lemma 1, we can easily analyze Lipschitz-continuity of NSW(p, µ) when either p or µ changes and the other is fixed. First, we consider change in p with µ fixed. Lemma 2. Given a reward matrix µ ∈ [0, 1]N×K and policies p1, p2 ∈ ∆K , we have∣∣NSW(p1, µ)−NSW(p2, µ)∣∣ ≤ N · ∥∥p1 − p2∥∥
1 = N · ∑ j∈[K] ∣∣p1j − p2j ∣∣ . Next, we consider change in µ with p fixed. Lemma 3. Given a policy p ∈ ∆K , and reward matrices µ1, µ2 ∈ [0, 1]N×K , we have∣∣NSW(p, µ1)−NSW(p, µ2)∣∣ ≤∑i∈[N ]∑j∈[K]pj · ∣∣µ1i,j − µ2i,j∣∣ . We are now ready to establish the regret bounds for Explore-First. Theorem 1. Explore-First is horizon-dependent and has the following expected regret at round T .
• When L = Θ ( N 2 3K− 2 3T 2 3 log 1 3 (NKT ) ) , E[RT ] = O ( N 2 3K 1 3T 2 3 log 1 3 (NKT ) ) . • When L = Θ ( N 1 3K− 1 3T 2 3 log 2 3 (NKT ) ) , E[RT ] = O ( N 1 3K 2 3T 2 3 log 2 3 (NKT ) ) .

heading: 4 Epsilon-Greedy
text: A slightly more sophisticated algorithm than Explore-First is Epsilon-Greedy, which is presented as Algorithm 3 in the supplementary material. It spreads out exploration instead of performing it all at the beginning. Specifically, at each round t, it performs exploration with probability t, and exploitation otherwise. Exploration cycles through the arms in a round-robin fashion, while exploitation uses the policy pt 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-Greedy can be implemented efficiently. The only non-trivial step is to compute p̂ ∈ arg maxp∈∆K NSW(p, µ̂), which, as mentioned before, can be done efficiently. The key advantage of Epsilon-Greedy over Explore-First is that it is horizon-independent. However, in the µ̂ computed in Explore-First at the end of exploration, each µ̂i,j is the average of L iid samples, where L is fixed. In contrast, in the µ̂t computed in Epsilon-Greedy in round t, each µ̂ti,j is the
average of ntj iid samples. The fact that n t j is itself a random variable and the µ̂ t i,j-s are correlated through the ntj-s prevents a direct application of certain statistical inequalities, thus complicating the analysis of Epsilon-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.

heading: 4.1 Useful Lemmas
text: Recall that µ∗ and µ̂t denote the true reward matrix and the estimated reward matrix at the beginning of round t, respectively. Our goal is to find an upper bound on the quantity |NSW(p, µ∗)−NSW(p, µ̂t)| that, with high probability, holds at every p ∈ ∆K simultaneously. To that end, we first need to show that µ̂t will be close to µ∗ with high probability.
Recall that random variable ntj denotes the number of times arm j is pulled by an algorithm before round t, and µ̂ti,j is an average over n t j independent samples. Hence, we cannot directly apply Hoeffding’s inequality, but we can nonetheless use standard tricks from the literature.
Lemma 4. Define rtj = √
2 log(NKt) ntj
, and event Et , ∀i ∈ [N ], j ∈ [K] : ∣∣µ̂ti,j − µ∗i,j∣∣ ≤ rtj . Then,
for any algorithm and any t, we have Pr[Et] ≥ 1− 2t3 .
Conditioned on Et, we wish to bound |NSW(p, µ∗)−NSW(p, µ̂t)| simultaneously at all p ∈ ∆K . We provide two such (incomparable) bounds, which will form the crux of our regret bound analysis. The first bound is a direct application of the Lipschitz-continuity analysis from Lemma 3. Lemma 5. Conditioned on Et, we have that
∀p ∈ ∆K : ∣∣NSW(p, µ̂t)−NSW(p, µ∗)∣∣ ≤ N ·∑j∈[K]pj · rtj .
The factor of N in Lemma 5 stems from analyzing how much µ̂t may deviate from µ∗ conditioned on Et, in the worst case. However, even after conditioning on Et, µ̂t remains a random variable. Hence, one may expect that its deviation, and thus the difference |NSW(p, µ̂t)−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, µ̂t) from its expected value. If µ̂t consisted of independent random variables, like in Explore-First, this would be equal to NSW(p, µ∗). However, in general, these variables may be correlated through ntj . We use a conditioning trick to address this issue.
• We cannot hope to apply McDiarmid’s inequality at each p ∈ ∆K separately and use the union bound because ∆K is infinite. So we apply it at each p in a δ-cover of ∆K , apply the union bound, and then translate the guarantee to nearby p ∈ ∆K using the Lipschitz-continuity analysis from Lemma 2.
The next result is one of the key technical contributions of our work with a rather long proof. Lemma 6. Define the event
Ht , ∀p ∈ ∆K : ∣∣NSW(p, µ̂t)−NSW(p, µ∗)∣∣ ≤√12NK log(NKt) ·∑j∈[K]pj · rtj + 4t .
Then, for any algorithm and any t, we have Pr[Ht|Et] ≥ 1− 2/t3.
Finally, we use the following simple observation in deriving our asymptotic bounds. Proposition 1. For constant p ∈ R, ∑T t=1 t p is Θ (log T ) if p = −1 and Θ ( T p+1 ) when p > −1.

heading: 4.2 Analysis of Epsilon-Greedy
text: We can now use these lemmas to establish the regret bounds for Epsilon-Greedy. Theorem 2. Epsilon-Greedy is horizon-independent, and has the following expected regret at any round T .
• If t = Θ ( N 2 3K 1 3 t− 1 3 log 1 3 (NKt) ) for all t, E[RT ] = O ( N 2 3K 1 3T 2 3 log 1 3 (NKT ) ) . • If t = Θ ( N 1 3K 2 3 t− 1 3 log 2 3 (NKt) ) for all t, E[RT ] = O ( N 1 3K 2 3T 2 3 log 2 3 (NKT ) ) .

heading: 5 UCB
text: Algorithm 1: UCB Input: Number of agents N , number of arms K Parameters :Confidence parameter αt for each t ∈ N // Pull each arm once
for t = 1, . . . ,K do pt ← policy that puts probability 1 on arm t // Pull arm t deterministically
end for t = K + 1, . . . do
Compute the estimated reward matrix µ̂t pt ← arg maxp∈∆K NSW(p, µ̂t) + αt ∑ j∈[K] pj · rtj , where rtj , √ log(NKt)
ntj .
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 a confidence interval term similar to rtj in Algorithm 1. Our multi-agent variant similarly selects a policy that maximizes the estimated Nash social welfare plus a confidence term for a policy, which simply takes a linear combination of the confidence intervals of the arms.
Unlike Explore-First and Epsilon-Greedy, it is not clear if our UCB variant admits an efficient implementation due to the step of computing arg maxp∈∆K NSW(p, µ̂) + α t ∑ j∈[K] pjr t j . Due to the added linear term, the objective is no longer log-concave. This remains a challenging open problem. However, we notice that this can also be viewed as the problem of optimizing a polynomial over a simplex, which, while NP-hard in general, admits a PTAS when the degree is a constant [42, 43]. Hence, when the number of agents N is a constant, this step can be computed approximately, but it remains to be seen how this approximation translates to the regret bound. We show that UCB achieves the desired √ T dependence on the horizon (up to logarithmic factors). In Appendix A, we show that this is optimal.
Theorem 3. UCB is horizon-independent, and has the following expected regret at any round T . • If αt = N for all t, E[RT ] = O ( NKT 1 2 log(NKT ) ) .
• If αt = √ 12NK log(NKt) for all t, E[RT ] = O ( N 1 2K 3 2T 1 2 log 3 2 (NKT ) ) .
Proof. Fix one of two parameter choices:
1. αt = N for all t and c = N . 2. αt = √ 12NK log(NKt) for all t and c = √ 12NK log(NKT ).
Note that in both cases, αt ≤ c for all t. Hence, c serves as an upper bound on αt that does not depend on t. We show that in both cases, running UCB with the αt parameter value yields a regret bound of E[RT ] = O(cK √ T log(NKT )). Substituting the two choices of c then yields the two regret bounds. Let us again focus on the event
Ctα , ∀p ∈ ∆K : ∣∣NSW(p, µ∗)−NSW(p, µ̂t)∣∣ ≤ αt ·∑j∈[K]pj · rtj + 4t .
Recall the clean events Et and Ht defined in Lemmas 4 and 6. Conditioned on Et ∧ Ht, note that Ctα holds for αt = N due to Lemma 5, and for αt = √ 12NK logNKt due to Lemma 6. Using Lemmas 4 and 6, and the union bound, we have Pr[¬Ctα] ≤ 1−Pr[Et∧Ht] = 1−Pr[Et]·Pr[Ht|Et] ≤ 1− (1− 2/t3) · (1− 2/t3) ≤ 4/t3.
Define a clean event C∗α , ∧ t≥ √ T Ctα. Here, we do not care about the first √ T rounds because the
maximum regret from these rounds isO (√ T ) , which is permissible given our desired regret bounds. By the union bound, we have Pr[¬C∗α] ≤ T ·4/( √ T )3 = 4/ √ T . Thus, C∗α is a high-probability event. In what follows, we derive an upper bound on the expected regret conditioned on C∗α, i.e., E[RT |C∗α]. Since conditioning on a high-probability event does not affect the expected value significantly, the desired regret bound will then follow. For any t ∈ [T ], conditioned on Ctα we have that
NSW(p∗, µ∗) ≤ NSW(p∗, µ̂t) + αt ∑ j∈[K] p∗j · rtj + 4 t ≤ NSW(pt, µ̂t) + αt ∑ j∈[K] ptj · rtj + 4 t
≤ NSW(pt, µ∗) + 2αt ∑ j∈[K] ptj · rtj + 8 t ,
where the first and the last transition are from conditioning on Ctα, and the second transition is because p = pt maximizes the quantity NSW(p, µ̂t) + αt ∑ j∈[K] pj · rtj in the UCB algorithm.
Let us write p[T ] = (p1, . . . , pT ) for the random variable denoting the policies used by the algorithm, and p[T ] = (p1, . . . , pT ) to denote a specific value in (∆K)T taken by the random variable.
Instead of analyzing E[RT |C∗α] directly, we further condition on UCB choosing a specific sequence of policies p[T ]. That is, we are interested in deriving an upper bound on E[RT |C∗α ∧ p[T ] = p[T ]].5
Interestingly, we show that this quantity is O ( cK √ T log(NKT ) ) for every possible p[T ]. Fix an arbitrary p[T ]. For t ∈ [T ] and j ∈ [K], define qtj = ∑t s=1 p s j . Then, E[ntj |p[T ] = p[T ]] = qtj .
For each j ∈ [K], let Tj be the smallest t for which qtj ≥ 2 √ T log(NKT ) (if no such t exists, let Tj = T ); note that given p[T ], Tj is fixed and not a random variable. Also, we have that q Tj j = Θ (√ T log(NKT ) ) for each j ∈ [K].
Let us define a clean event B , ∀j ∈ [K], nTjj ≥ √ T log(NKT ). We first show that this is a high probability event. Indeed, using Hoeffding’s inequality, we have that for each j ∈ [K],
Pr [ n Tj j < √ T log(NKT ) ∣∣ C∗α ∧ p[T ] = p[T ]] ≤ Pr [nTjj < sTjj −√T log(NKT ) ∣∣ C∗α ∧ p[T ] = p[T ]] ≤ 1 N2K2T 2 .
Taking union bound over j ∈ [K], we have that Pr [ ¬B ∣∣ C∗α ∧ p[T ] = p[T ]] ≤ 1N2KT 2 . Next, we bound E[RT |C∗α ∧ p[T ] = p[T ]] by using event B.
E [ RT ∣∣ C∗α ∧ p[T ] = p[T ]] = T∑ t=1 E [ NSW(p∗, µ∗)−NSW(pt, µ∗) ∣∣∣ C∗α ∧ p[T ] = p[T ]] ≤ max(K, √ T ) +
T∑ t=max(K, √ T )+1
( 1 · E [ NSW(p∗, µ∗)−NSW(pt, µ∗) ∣∣ C∗α ∧ p[T ] = p[T ] ∧ B]
+ Pr [ ¬B ∣∣ C∗α ∧ p[T ] = p[T ]] · 1 )
≤ max(K, √ T ) + T∑ t=max(K, √ T )+1 E 2αt ∑ j∈[K] ptj · r t j + 8 t ∣∣∣ C∗α ∧ p[T ] = p[T ] ∧ B 
+ T · Pr [ ¬B ∣∣ C∗α ∧ p[T ] = p[T ]] ≤ max(K, √ T ) + 1 + 2c √ 2 log(NKT )
T∑ t=1 ∑ j∈[K] ptj√ cj . (1)
5Note that even after conditioning on p[T ] = p[T ], there is still randomness left in sampling actions from the policies and sampling the rewards of those actions.
The final transition holds because αt ≤ c for all t, rtj = √
2 log(NKT ) ntj , and conditioned on B, ntj ≥ cj for each j ∈ [K] and t ∈ [T ], where cj = 1 if t < Tj , and cj = √ T log(NKT ) if t ≥ Tj . Hence,
E [ RT ∣∣∣∣∣ C∗α ∧ p[T ] = p[T ] ] ≤ max(K, √ T ) + 1 + 2c √ 2 log(NKT ) ∑ j∈[K] T∑ t=1 ptj√ cj
= max(K, √ T ) + 1 + 2c √ 2 log(NKT ) ∑ j∈[K] Tj−1∑ t=1 ptj 1 + T∑ t=Tj ptj√ T log(NKT )  ≤ max(K, √ T ) + 1 + 2c √ 2 log(NKT )
∑ j∈[K] ( q Tj j + T√ T log(NKT ) ) = O ( cK √ T log(NKT ) ) .
Because this bound holds for every possible p[T ], we also have that E[RT |C∗α] = O ( cK √ T log(NKT ) ) . Finally, we can see that
E[RT ] = Pr[C∗α] · E[RT |C∗α] + Pr[¬C∗α] · E[RT |¬C∗α] ≤ 1 · O ( cK √ T log(NKT ) ) +
4√ T · 1 = O
( cK √ T log(NKT ) ) .
Recall that substituting c = N and c = √ 12NK log(NKT ) 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 our setting in which the algorithm can “pull” a probability distribution over the arms. The corresponding expression in case of the classical UCB turns out to be much simpler and straightforward to bound. In contrast, we need to use additional tricks to derive the bound of O ( cK √ T log(NKT ) ) .
Finally, in the proof presented above, we 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, a 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., [1]): assuming a different clean event, the classical UCB algorithm is guaranteed to not pull suboptimal arms too many times.

heading: 6 Discussion
text: Our work leaves open several directions for the future. There are immediate technical challenges such as a 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 agentsN (see Appendix A). It would also be interesting to consider other fairness notions such as the egalitarian welfare or the core [4]. More broadly, our work promotes a multi-agent variant in which one must strike a tradeoff between the reward functions of multiple agents. An exciting future direction would be to consider such multi-agent variants of other classical single-agent decision-making problems.
Acknowledgments and Disclosure of Funding
Nisarg Shah acknowledges support from an NSERC Disocvery Grant.

Review summaries:
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.  The 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).

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.

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. 

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.