No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
Authors: Mengxiao Zhang
Ramiro Deo-Campo Vuong
Haipeng Luo
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Nash Social Welfare
Primary area: online_learning

Abstract: We consider the problem of online multi-agent Nash social welfare (NSW) maximization. While previous works of Hossain et al. [2021], Jones et al. [2023] study similar problems in stochastic multi-agent multi-armed bandits and show that $\sqrt{T}$-regret is possible after $T$ rounds, their fairness measure is the product of all agents' rewards, instead of their NSW (that is, their geometric mean). Given the fundamental role of NSW in the fairness literature, it is more than natural to ask whether no-regret fair learning with NSW as the objective is possible. In this work, we provide a complete answer to this question in various settings. Specifically, in stochastic $N$-agent $K$-armed bandits, we develop an algorithm with $\widetilde{\mathcal{O}}(K^{\frac{2}{N}}T^{\frac{N-1}{N}})$ regret and prove that the dependence on $T$ is tight, making it a sharp contrast to the $\sqrt{T}$-regret bounds of Hossain et al. [2021], Jones et al. [2023]. We then consider a more challenging version of the problem with adversarial rewards. Somewhat surprisingly, despite NSW being a concave function, we prove that no algorithm can achieve sublinear regret. To circumvent such negative results, we further consider a setting with full-information feedback and design two algorithms with $\sqrt{T}$-regret: the first one has no dependence on $N$ at all and is applicable to not just NSW but a broad class of welfare functions, while the second one has better dependence on $K$ and is preferable when $N$ is small.
Finally, we also show that logarithmic regret is possible whenever there exists one agent who is indifferent about different arms.

No-Regret Learning for Fair Multi-Agen gent Social Welfare Optimization
Mengxiao Zhang
Ramiro Deo-Campo Vuong
University of lowa
Corell University
mencxi.o=zlanguuooaa
amdcvêcss cornell.ecde.oeooo
Haipeng Luo
University of Southern California haipengl (aannngguusc..o @usc.
Abstract
We consider the problem of online multi- agent Nash social welfare (NSW) max- imization. While previous works of Hossain al. [2021], Jones al. [2023] study similar problems stochastic multi-agent multi-armed bandits and show that -T-regret is possible after T rounds, their fairness measure is the product all agents' rewards, instead of their NSW (that is, their geometric mean). Given the fundamental role NSW in the fairness literature, is more than natural to ask whether no-regret fair learning with NSW as the objective is possible. In this work, we provide a complete answer to this question in various settings. Specifically, in stochastic N Naagent K K-armed bandits, we develop algorithm with Ö(K T x*) regret and prove that the dependence on T is tight, making a sharp contrast to the -T-regret bounds Hossain et al. [2021]. Jones et al. [2023]. We then consider a more challenging version of the problem with adversarial rewards. Somewhat sur- prisingly, despite NSW being a concave function, we prove that no algorithm can achieve sublinear regret. To circumvent such negative results, we further consider setting with full- full-ifoormation feedback and design two algorithms with VT-regret: the first one has no dependence on N at all and is applicable to not just NSW but a broad class of welfare functions, while the second one has better dependence and preferable when N small. Finally, we also show that logarithmic regret is possible whenever there exists agent who is indifferent about different arms.
K
Introduction
In this paper, we study online multi-agent Nash social welfare (NSW) maximization, which is generalization of the classic multi-armed bandit (MAB) problem [Thompson, 1933, Lai and Robbins, 1985]. Different from MAB, in which the learner makes her decisions sequentially in order to maximize her own reward, in online multi-agent NSW maximization, the learner's decision affects multiple agents and the goal is to maximize the NSW over all the agents. Specifically, NSW is defined as the geometric mean of the expected utilities over all agents [Moulin, 2004], which can be viewed as measure of fairness among the agents. This problem includes many important real-life applications such as resource allocation [Jones al., 2023], where the learner needs to guarantee fair allocations among multiple agents. We refer the readers to [Hossain et al., 2021, Jones et al., 2023] for more applications of NSW maximization.
Recent work by Hossain et al. [2021], Jones et al. [2023] studies a similar problem but with NSW prod the objective, variant of NSW that defined as the product the utilities agents instead of
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

their geometric mean. While the optimal strategy is the same if the utility for each agent is stationary. this is not the case with non-stationary environment. Moreover, NSW prod homogeneous of degree N instead of degree 1, where N is the number of agents, meaning that NSW prod is more sensitive to the scale of the utility. Specifically, the utilities of each agent are scaled by 2, then NSW scaled by 2 as well, but NSW prod is scaled by 2% Therefore, it is arguably more reasonable to consider regret with respect to NSW, which has not been studied before (to our knowledge) and is the main objective of our work.
From a technical perspective, however, due to the lack of Lipschitzness, NSW poses much more challenges in regret minimization compared to NSW prod. For example, one cannot directly apply the algorithm for Lipschitz bandits [Kleinberg et al., 2019] to our problem, while it is directly applicable to NSW prod as mentioned in [Hossain et al., 2021, Jones et al., 2023]. Despite such challenges, we manage to provide complete answers to this problem in various setting. Specifically, our contributions are listed below (where T, N, and K denote the number of rounds, agents, and arms/actions respectively):
We first study the stochastic bandit setting, where the utility matrix at each round i.i.d. drawn from an unknown distribution, and the learner can only observe the utilities (for different agents) of the action she picked. In this case, we develop algorithm with Ö(K T "x') regret.' While our algorithm is also naturally based on the Upper Confidence Bound (UCB) algorithm as in Hossain et al. [2021], Jones et al. [2023], we show that a novel analysis with bernstein-type confidence intervals is important for handling the lack of Lipschitzness of NSW Moreover, we prove lower bound of order O
(Section 3)
~ ( Ns K T N ), showing that the dependence on T is tight.
This is in sharp contrast to the VT-regret bound of Hossain al. [2021], Jones et al. [2023] and demonstrates the difficulty of learning with NSW compared to NSW prod-
(Section 4.1) We then consider a more challenging setting where the utility matrix at each round can be adversarialyy chosen by the environment. Somewhat surprisingly, we show that no algorithm achieve sublinear regret in this case, despite NSW being concave and the vast literature on bandit online maximization with concave utility functions (the subtlety lies in the slightly different feedback model). In fact, the same impossibility result also holds for NSW pood as we show.
(Section 4.2) To bypass such impossibility, we further consider this adversarial setting under richer feedback, where the learner observes the full utility matrix after her decision (the so-called full- information feedback). Contrary to the bandit feedback setting, learning is not only possible now but can also be much faster despite having adversarial utilities. Specifically, we design two different hew.tae--eggulaieeeeeeiiieee
algorithms with -rggret. The first algorithm is based on with the log-barrier regularizer, which achieves O( O(VKTlog 7' regret (Section 4.2. 1). Notably, this algorithm does not have any dependence on the number of agents N and can also be generalized to broader class of social welfare functions. The second algorithm is based on FTRL with a
(FTRL)
Tsallis entropy regularizer, which achieves Ö(K} - & /NT) regret and is thus more favorable when K is much larger than N (Section 4.2.2). Finally, we also show that improved logarithmic regret is possible as long as at each round there exists at least one agent who is indifferent about the learner's s choice of arm (Section 4.2.3).
1.1 Related Work
Hossain al. [2021], Jones et al. [2023] are most related to our work. Hossain et al. [2021] is the first to consider designing no-regret algorithms under NSW poo for the stochastic multi-agent multi-armed bandit problem. Specifically, they propose two algorithms. The first one is based on e-greedy and achieves O(T3) ) regret efficiently, and the second one based on UCB and achieves Ö(vT regret inefficiently. Jones et al. [2023] improves these results by providing a better UCBB-bacer algorithm that is efficient and achieves the same Ö(VT) regret. To the best of our knowledge, there are no previous results for regret minimization over NSW under this particular setup.
However, several other models of fairness have been introduced in (single-agent or multi-agent) multi-armen bandits, some using NSW as well. These models differ in whether they aim to be fair among different objectives, different arms, different agents, different rounds, or others. Most
'The notation Ō(:) and (2(-) hide logarithmic dependence on K, N. and T.

---

related to this paper is multi- objective bandits, in which the learerr tries to increase different and possibly competing objectives in a fair manner. For example, Drugan and Nowe [2013] introduces the multi-objective stochastic bandit problem and offers a regret measure to explore Pareto Optimal solutions, and Busa-Fekete et al. [2017] investigates the same setting using the Generalized Gini Index in their regret measure to promote fairness over objectives. Their regret measure closely resembles the one we use, except they apply some social welfare function (SWF) to the cumulative expected utility of agents over all rounds as opposed to the expected utility of agents each round. On the other hand, some other works study fairness among different rounds which incentivizes the learner to perform well consistently over all rounds [Barman et al., 2023, Sawamn et al., 2024]. Besides, there are other models that measure fairness in different ways, including how often each arm is pulled [Joseph et al., 2016, Liu et al., 2017, Gillen et al., 2018, Chen et al., 2020] and how the regret is allocated across different groups [Baek and Farias, 2021].
Kaneko and Nakamura [1979] axiomatically derives the NSW function. It is fundamental and widely-adopted fairness measure and especially popular for the task of fairly allocating goods. Caragiannis et al. [2019] justifies the faimess of NSW by showing that its maximum solution ensures some desirable envy-free property. This result prompted the design of approximation algorithms for the problem of allocating indivisible goods by maximizing NSW, which is known to be NP-hard even for simple valuation functions [Barman et al., 2018, Cole and Gkatzelis, 2015, Garg et al., 2023, Li and Vondrák, 2021].
There a vast literature on the multi- armed bandit problem; see the book by Lattimore and Szepesvári [2020] for extensive discussions. The standard algorithm for the stochastic setting is UCB [Lai and Robbins, 1985, Auer al., 2002a], while the standard algorithm for the adversarial setting FTRL or the closely related Online Mirror Descent (OMD) algorithm [Auer et al., 2002b, Audibert and Bubeck, 2010, Abernethy et al., 2015]. For FTRL/OMD, the log- -brrier or Tsallis entropy regularizers have been extensively studied in recent years due to some of their surprising properties (e.g., [Foster et al., 2016, Wei and Luo, 2018, Zimmert and Seldin, 2019, Lee et al., 2020J). They are rarely used the full-information setting as far as we know, but our analysis reveals that they are useful even in such settings, especially for dealing with the lack of Lipschitzness of NSW.
2 Preliminaries
General Notation. Throughout this paper, we denote the set {1.2..... n. by [n]] for any positive integer n. For a matrix M E 12x, we denote the i-th row vector of M by M,. E R" the j-th column vector of M by M. E R" and the (i. j)th entry of M by M.j- We say M 2 if M is a positive semi-definite matrix. The (K 1)-dimensional simplex is denoted
Ak. and its clipped version with a parameter 5 > 0 is denoted as Ax.5 = (p E Ax I p; 2 5, Vi E []]. We use 0 and 1 to denote the all-zero and all-one vector in an appropriate dimension. For two random variables X
and Y, we use X _ Y to say X is equivalent to Y in distribution.
For twice differentiable function f. we use V (-() and (- to denote its gradient and Hessian. For concave functions that are not differentiable, V)(-) denotes a super-gradient Throughout the paper, we study functions of the form f(u T p) for u E [0, _|m=x and p E Am- In such cases, the gradient, super-grade epprrngradien,, or hessian are all with respect p unless denoted otherwise (for example, we write Vuf(u p). with an explicit subscript u, to denote the gradient with respect to u).
Social Welfare Functions A social welfare function (SWF) f J0, 1 + [o. 1] measures the desirability of the agents' expected utilities. Specifically. for two different vectors of expected utilities μ. μ² E [0, 1JN, f(x)= f(u') means that μ is fairer alternative than μ². In each setting we explore, each action by the learner yields some expected utility for each of the N agents, and the learner's s goal is maximize some SWF applied to these N expected utilities.
Nash Social Welfare (NSW) For the majority of this paper, we focus on specific type of SWF, namely the Nash Social Welfare (NSW) function [Nash, 1950, Kaneko and Nakamura, 1979]. Specifically, for j [0, 1|,, NSW is defined the geometric mean of the N coordinates:
NSW())
II [E[N]
Pm
I/N
(1)
3

---

As mentioned, Hossain et al. [2021], Jones et al. [2023] considered closely related variant that simply the product of the coordinates: NSW prea pro (p) [NE[N] Pn- It is clear that NSW has better sealing property since it is homogeneous: scaling each aAn by a constant c also scales NSW (1) by c, but it scales NSW (p) by c.. This makes NSW prod unnatural learning objective, which motivates us to use NSW as our choice of SWE. Learning with NSW, however, brings extra challenges since it is not Lipschitz in the small-utility regime (while NSW pod is Lipschitz over the entire [0, 1 We shall see in subsequent sections how we address such challenges.
We remark that while our main focus is regret minimization with respect to NSW, some of our results also apply to NSW prod or more general classes of SWFs (as will become clear later).
Problem Setup. The N V-agent K Karreed social welfare optimization problem we consider is defined as follows (with N 2 2 and K 2 2 throughout). Ahead of time, with the knowledge of the learner's algorithm, the environment decides T utility matrices Ui..... ..... utility of agent n if arm/action is selected at round t. Then, the learner interacts with the environment for T' rounds: at each round the learner decides distribution Pa E Ax and then samples action ie ~ Pt- In the full-information feedback setting, the learner observes the full utility matrix ue after her decision, and in the bandit feedback setting, the learner only observes Utin. for each agent n E [N], that is, the utilities of the selected action.
ur E [o, 1] 1jKxN, where ue,i, is the
We consider two different types of environments, the stochastic one and the adversarial one, with slight difference in their regret definition. the stochastic environment, there exists a mean utility matrix [0, 1]x** ||xNN such that at each round I, Ut is an i.i.d. random variable with mean u. Fix an SWF f. The social welfare of strategy p AK is defined as f(u p), which is with respect to the agents' expected utilities over the randomness of both the learner's and the environment's s. The regret is then defined as follows:
T Σ
Regat T max f(u p) E PEAR
s(" pe)
2)
which is the difference between the total social welfare of the optimal strategy and that of the learner. When f is chosen to be NSW prod. Eq. (2) reduces to the regret notion considered in Hossain et al. [2021], Jones et al. [2023].
On the other hand, in the adversarial environment, do not make any distributional assumption on the utility matrices and allow them to be selected arbitrarily. The social welfare of strategy E Ax for time / is defined as fu, p), and the overall regret of the learner is correspondingly defined as:
Elu. E Σ Eut
Regady
max PEAR
In both Eq. (2) and Eq. (3), the expectation is taken with respect to the randomness of the algorithm.
Social welfare of expected utilities versus expected social welfare of realized utilities. One might wonder why we measure fairness using the social welfare of expected utilities (c.g.. f(u f))T instead of the expected social welfare of realized utilities (e.g., Ef ee))). This is because a faimess measure. To see this, consider f NSW or
p)).
the former is arguably more meaningful
f f= NSW prod and a setting with 2 agents, arms, and u being the identity matrix. Then, in terms of f(u p). the uniform distribution is the best policy (which makes sense from a fairness viewpoint), while in terms of Ex [u et)], all distributions achieve the same value of O, implying that all polices are fair, which is clearly undesired.
Connection to Bandit Convex optimization. When taking / = NSW (our main focus) and considering the bandit feedback setting. our problem is seemingly an instance of the heavily-studied Bandit Convex optimization (BCO) problem, since -NSW is convex. However, there is a slight but critical difference in the feedback model: BCO algorithm would require observing fu, pc). or equivalently u, Pt, at the end of each round f, while in our problem the learner only observes Ur, much more realistic scenario. Even though they have the same expectation, due to the non-linearity of NSW, this slight difference in the feedback turns out to cause a huge difference in terms of learning the minimax regret for BCO is known to be O ((VT). while in our problem (with bandit feedback),

---

pood is Algorithm UCB for N -aggent K-armed NSW maximization
Input: warm-up phase length No > 0.
Initialization: V1.i. = 1 for all n E [N], i E [K]. Ni,; = 0 for all i E [K].
for f 1.2..... do
if S NNo then select b = 1
else calculate Pt argmaxpęAR NSW(ū,)) p) and select it ~ Pe
Observe "r,ú. for all [N].
Update counters N1+1.4. = NL.,, + and N = No, for i iorii it.
Update upper confidence utility matrix:
Unin log(N
+ 8log(NKT2)
ū1+1.6 = Ue,in + AV
(4)
No+1.
Not1,
for all n E [N] and E [K] where Uiin Nest. Erso Mriin =
end
as we will soon show, the regret is either O(T ) in the stochastic setting or even (2(T) in the adversarial setting. Therefore, in a sense our problem much more difficult than BCO. For more details on BCO, we refer the reader to a recent survey by Lattimore [2024].
3 Stochastic Environments with Bandit Feedback
In this section, we consider regret minimization over f NSW with bandit feedback in the stochastic setting, where the utility matrix at each round t E [T) is i.i.d. drawn from distribution with mean u. Again, this is the same setup as Hossain et [2021], Jones al. [2023] except that NSW replaced with NSW.
3.1 Upper Bound: a Refined Analysis of UCB with a Bernstein-Type Confidence Set
We start by describing ideas are and how the algorithm/analysi is different from previous work. Specifically, our algorithm. shown in Algorithm 1, is based on the classic UCB algorithm. It starts by picking each action for No (1) rounds. After this warm-up phase, at each time t, the algorithm picks the optimal strategy that maximizes the NSW with respect to some upper confidence utility matrix ūt After sampling an action i Pt, the algorithm observes the utility of each agent for action i, and then updates the upper confidence utility matrix u++1 as the empirical average utility plus certain Bernstein-tyee -type confidence width (Eq. (4)).
algorithm and its regret guarantee, followed by discussion on what the key
The following theorem shows that Algorithm guarantees Ö(K T expected regret (with f. in the definition of Regsto set to NSW; the same below unless stated otherwise). The full proof can be found in Appendix A.
Theorem 3.1. With No = + 18 log KT, Algorithm guarantees [Regstol Ō(K + K).
Other than replacing NSW prod with NSW, our algorithm differs from that of Jones et al. [2023] in the form of the confidence width, and the analysis sketch below explains why we need this change. Specifically, for either f NSW prod or NSW, standard analysis of UCB states that the regret is bounded by ΣT_ f(ā pt) f( pc)] When f is NSW prod. Lipschitz function, Hossain al. [2021, Lemma 3] shows
NSW prod TT. p.) NSW proa (u. Pc)) S Pe.i
ui,
and the rest of the analysis follows by direct calculations. However, when f is NSW, non-Lipschitz function, we cannot expect something similar Eq. (5) anymore. Indeed, direct calculation shows N-1
that the Lipschitz constant of NSW(u) p) with respect u.n equals to θ (ΣN (p, u.,)) which can be arbitrarily large when (p, u.n)) is close to 0 for some [N] and N 2 2.
5

---

N=1 for To handle this issue, we require a more careful analysis. Specifically, using Freedman's 's inequality, we know that with high probability,
un u4 ui + / Ui,n Log(NNTT
θ (L/NN.) = [uimm 2uln (1/NN.)). (6)
N₁.i
With the help of Eq. (6), we consider two different cases at each round f. The first case is that there exists certain [NV such that (pr, u.,)) S a for some a be chosen later. In this case, we use Eq. (6) to show
NSw p.) NSW(u p.) S (NSW(uTp.)) pt)) +ō
((2
K
Pr. N₁.
N
(( Pt,s N
x
S < +
where the first inequality uses Eq. (6) and the second inequality is because NSW T pe) S (pt, un) for any n [V]. For the second term in Eq. (7), standard analysis shows that is upper bounded by O (K&T
Now we consider the case where (pe, u.n)) a for all [N]. In this case, via decomposition lemma (Lemma C.I), we show that
N
(e Uen.n u.
(a, pt) - NSW(u T po)
(pr, Dean)) - (Pr, u.
=
N (pe, U...)
n=1
(8)
To bound Eq. (8), we use Eq. (6) again:
(pt. ur.in u.m)
K
Pr.i N
N
K
Pt.
N-1 S 0
< 0
N
(Pe, un
(pt. U.n))
where the last inequality is due to the condition (pt. u.,.) 2 for all n E [N]. Finally, combining Eq. (7), Eq. (8), Eq. (9), followed by direct calculations, we show that
E Regstll S Σ
INssaa p.) NSW(u p.)l = + T +ot (T)(
N "WKVT) KVT)
Picking the optimal choice of a finishes the proof.
We now highlight the importance of using a Bernsten-ttype confidence width in Eq. (4): if the standard Hoeffding-type confidence width is used instead, then one can only obtain ūr,in - Uin - O N.
and consequently, Eq. (8) can only be bounded by O (o Nx
KT
after taking summation over
t E [T]. This eventually leads to a worse regret bound of Ö x 2%
3.2 Lower Bound
Next, we prove an (+++ lower bound for this setting. This not only shows that the regret bound we achieve via Algorithm 1 is tight T. but also highlights the difference and difficulty of learning with NSW compared to learning with NSW NSW prod, since the latter case, ((VT) regret is minimax optimal [Hossain et al., 2021, Jones et al., 2023].
Theorem 3.2. In the bandit feedback setting, for any algorithm, there exists a stochastic environment (log K)
in which the expected regret (with respect to NSW) of this algorithm is Q N log K and sufficiently large T.
NS
We defer the full proof to Appendix A.2 and discuss the hard instance used in the proof below. First, the mean utility vector U for each agent > 2 is a constant vector 1. This makes the problem

---

equivalent to one-agent problem, but with (p, 1., as the reward, instead of (p, u.,)) as in standard stochastic K-armed bandits.
Then, for the first agent, different from the standard K-armed bandits, where the hardest instance is to hide one arm with a slightly better expected reward of 1 + VKjT among other K arms with expected reward of exactly 2 we hide one arm with expected reward K/T among other K - arms with exactly O reward (so overall the rewards are shifted towards 0 but with a smaller gap between the best arm and the others). By standard information theory arguments, within II' rounds the learner cannot distinguish the best arm from the others. Therefore, the best strategy she can apply is to pick a uniform distribution over actions, suffering ( - K +) K-*)) (K/T)*) = Ωi K T regret per
round and leading to ( "x
regret overall.
Adversarial Environments
Now that we have a complete answer for the stochastic setting, we move on to consider the adversarial case where each is chosen arbitrarily, multi-agent generalization of the expert problem (full- information feedback) [Freund and Schapire, 1997] and the adversarial multi-armed bandit problem (bandit feedback) [Auer et al., 2002b]. There are prior studies this problem, be it with f = NSW or f = NSW prod. as far as we know.
4.1 Impossibility Results with Bandit Feedback
We start by considering the bandit feedback setting. As mentioned in Section 2, even though NSW is a concave function, our problem is not an instance of Bandit Convex Optimization, since we can only observe Ue instead of NSW (u, Pt) at the end of round t. Somewhat surprisingly, this slight difference in the feedback in fact makes a sharp separation in learnability - while O (VT)) regret is achievable in BCO, we prove that ((')) regret is impossible in our problem.
Before showing the theorem and its proof, we first give high level ideas on the construction of the hard environments. Specifically, consider the environment with 2 agents, 2 arms, and binary utility matrix 4, E {0, 1]2x2. Similar to the hard instance in the stochastic environment, we set Ut..22 = 1, reducing the problem drawn from a stationary distribution over the 4 binary utility vectors {(0, 0), (0, 1), (1,0), 1))- Then, we construct two different distributions, & and ε², over these 4 binary utility vectors satisfying that: 1) the distribution of the learner's 's observation is identical for E and E 2) the optimal strategy for & and g' are significantly different. The first property guarantees that no algorithm can distinguish these two environments, while the second property ensures that there is no one single strategy that can perform well in both environments. Formally, we prove the following theorem.
single-agent one. For the first agent, we let Wr..,1 at each round & be i.i.d.
Theorem 4.1. In the bandit feedback setting, for any algorithm, there exists an adversarial environ- ment such that E. Reegady (I(T) for f = NSW.
Proof. As sketched earlier, we consider two different environments with 2 agents, 2 arms, and binary utility matrices u, {0, 1]222 1 [T'. In both environments, we have u,
Next, we construct two different distributions from which u,..1 is potentially drawn from, & and E' over {0,, 0), (0, 1), (1, 0), (1, 1)). Specifically, E is characterized by (goo- 901, 910. 911)
To To To ) where quy is the probability of the vector (z, in E; E' is characterized by (960, Loz V1 (11)
2 1 3
i To T 2., where dyy is the probability of vector (x, in Ex. With slight abuse of notation, write E for matrix (0, 2x22 if u., is drawn from & and M.2 = 1; the same for g'.
3 2
We argue that the leamner' observations are equivalent in distribution in E and E', since the marginal distributions of the utility of each action are the same. Specifically,
When action 1 is chosen, the distributions of the learner's observation in both & and El are Bernoulli random variable with mean Qı0 + Qu = Lo + di = T
"One can show that ((vT) regret is possible in this environment, thus suitable for purpose.
7

---

When action 2 is chosen, the distributions of the learner's observation in both & and g' are Bemoulli random variable with mean 901 + Qu 4n + 911
5
To
Direct calculation shows P. argmax PEAK BAwE [NSW(u] (eW(uT))) p)]
910
401
+-9
1o1
+.100
l2
0..2 and p-_ argmaxpEAw Bungr [NSW(UTP) p)]
13 13 which
910+96 0: 910
are constant apart from each other. Pick threshold value 130
(0.2, 13) Direct calculation
shows that for a strategy p with p1 2 8, we have Euve [NSW( p.) ) NSW((u) p)] 2 A where
500 similarly, for a strategy p with pı < 0, we have En [NSW p.) NSW (u p) A as well. Now, given an algorithm, let ogg be the probability that the number of rounds Pt, 2 0 is larger than & under environment E, and ae. be the probability of the complement of this event under environment E". We have.
T NSW p+)
T
agTA
Re Regadv] 1 2 Ee
Σ
NSW (c. pc)
2
2
āgiTA
Ee [Regad]]
2 B
(s pL)
Σ (s. p.)
2
Finally, since the feedback for the algorithm is the same in distribution in these two environments, we know og + 'rgg 1, and thus
Eg [Regavl + Eg [Regudvl 2
(ag + +āg)TA = 2(()),
max EEg [Reg Eg Regadd 2
2
4
which finishes the proof.
In fact, by a similar but more involved construction (that actually requires using two agents in non-trivial way), the same impossibility result also holds for f = NSW prodi see Appendix B.I. We remark that non-linearity of f in these results plays important role in the hard instance construction, since otherwise, the optimal strategy for & and E' will be the same as they both induce the same marginal distributions.
4.2 Full-Information Feedback
To sidestep the impossibility result due the bandit feedback, we shift our focus to the full- information feedback model, where the learner observes the entirety of the utility matrix u, at the end round t. As mentioned, this corresponds to multi-agent generalization of the well-known expert problem [Freund and Schapire, 1997J. We propose several algorithms for this setting, showing that the richer feedback not only makes learning possible but also leads to much lower regret.
4.2.1 FTRL with Bar-Barrier Regularizer
When f is concave, our problem is in fact also an instance of the well-known Online Convex Opti- mization (OCO) [Zinkevich, 2003]. However, standard OCO algorithms such as Online Gradient Descent, instance of the more general izer, require the utility function to also be Lipschitz and thus cannot be directly applied to learning NSW. Nevertheless, will show that using different regularizer that induces more stability than the f2 regularizer can resolve this issue.
segularized-LLadde algorithm with a l regular-
More specifically, the FTRL algorithm is shown in Algorithm 2, which predicts at time the distribution Pt argminnpeAx (p, -:=1 ff P&)) 7) (p)(()) for some learning rate and some strongly convex regularizer th. Standard analysis shows that the regret of FTRL contains two terms: the regularization penalty term that is of order 1/1 and the stability term that of order E. (u, pt) 2w(p.) where we use the notation ||a]| Va Ma. To deal with the lack the Lipschitzness, that is, the potentially large ff(u, pt). we need to find a regularizer v so that the induced local norm [|V p:)llv=2((p)) is always reasonably small despite V [u pc) being large (in lg norm for example).

---

Algorithm 2 FTRL for N-agent K K-armed SWF maximization with full-info feedback
Inputs: SWF learning rate yj 0, and strongly convex regularizer de AK -> R.
for 1 = 1.2....,7 do
Play Pt = argmin pEAx (p-- - vS(uP.))) + 1.0()
Observe uy.
end
It turns out that the log- barrberrerr regularizer, {pp) = = - log p.. ensures such a property. In fact, it induces small local norm not just for NSW, but also for broad family SWFs as long as they are concave and Pareto optimal an SWF f [0, 1|
i=
[0. 1] is Pareto optimal if for two utility vectors J and y such that I, 2 Yn for all E [M]. we have f()) 2 f(y). NSW is clearly this family, and there are many other standard fairness measures that fall into this class; see Appendix B.2.1. 1. For any SWF in this family, we prove the following regret bound, which remarkably has no dependence on the number of agents N at all.
Theorem 4.2. For any I : [0, 1j + [0.1] that is concave and Pareto optimal, Algorithm
with the nag-barrier regularizer vbp) = = E O OVKTTlogT)
guarantees Regadv = 1 log pa and r = v -
T
Proof Sketch. Using the concrete form of sh, is clear that the local norm [[u - sim-
plifies to E (u, po)] s (pt, Vf(u.p:)) where the inequality is due to (V (u, pt)] 2
O implied by Pareto optimality. Furthermore, by concavity, we have (pt, V [ pc)) z [lu pt) f(0) < 1, and thus the local norm at most 1. The rest of the proof is by direct calculation.
4.2.2 FTRL with Tsallis Entropy Regularizer
In fact, when f NSW, using the special structure of the welfare function, we find yet another regularizer that ensures small O(N) local norm, with the benefit of having smaller dependence on K for the penalty term.
Theorem 4.3. For f NSW, Algorithm with the Tsallis entropy regularizer (pp) 1- 1-EK
N. and the optimal choice of guarantees Regady Ō(Kt + /NT).
The proof more involved and deferred to Appendix B.2.3. While the regret in Theorem 4.3 suffers polynomial dependence on N, it has better dependence on K compared to Theorem 4.2, and is thus more preferable when K is much larger than N.
4.2.3 Logarithmic Regret for a Special Case
Finally, we discuss special case with f NSW where logarithmic regret is possible. This is based on a simple observation that when there is one agent who is indifferent about the learner's 's choice (that is, the agent's utility is the same for all arms for this round), then -NSW is not only convex, but also exp-concave, a stronger curvature property. Therefore, by applying known results, specifically the EWOO algorithm [Hazan et al., 2007], we achieve the following result.
Theorem 4.4. Fix f = NSW. Suppose that for each time t, there is a set of agents A, S [N] such that |A.] 2 M and We... = Cr 1 with Cr, 2 0 for each agent n. E Ar. Then the EWOO algorithm guarantees Regady O N- M K log T).
The proof, which verifies the exp-concavity pendix B.2.4. We note that the reason that we apply EWOO instead of Online Newton Step, another algorithm discussed in [Hazan et al., 2007] for exp-concave losses, is that the latter requires Lipschiz- ness (which, again, is not satisfied by NSW).
-NSW in this special case, can be found Ap-

---

5 Conclusion
In this work, motivated by recent research on social welfare maximization for the problem of multi- agent multi-armed bandits, we consider variant with the arguably more natural version of Nash social welfare as the objective function, and develop multiple algorithms and regret upper/lower bounds in different settings (stochastic versus adversarial and full-information versus bandit feedback). Our results show a sharp separation between our problem and previous settings, including the heavily studied Bandit Convex Optimization problem.
There are many interesting future directions. First, in the stochastic bandit setting, we have only shown the tight dependence on 7, so what about K and N? Second, is there more general strategy/analysia that works for different social welfare functions (similar to our result in Theorem 4.2)? Taking one step further, similar to the recent research on "omniprediction" [Gopalan et al., 2022], is there one single algorithm that works for a class of social welfare functions simultancously?
Acknowledgments and Disclosure of Funding
HL and MZ are supported by NSF Award IIS-1943607.
References
Jacob D Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with new kind of smoothness. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Alekh Agarwal, Haipeng Luo, Behnam Neyshabur, and Robert E Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12-38. PMLR, 2017.
Jvan-Yves Audibert and Sébastien Bubeck. Regret bounds and minimax policies under partial monitoring. The Journal of Machine Learning Research, 11:2785-2883 2010.
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 57:235-256, 2002a.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing. 32(1):48-71 2002b.
Jackie Back and Vivek Farias. Fair exploration via axiomatic bargaining. Advances in Neural Information Processing Systems, 34:22034-2200 2021.
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557-574, 2018
Siddharth Barman, Arindam Khan, Arnab Maiti, and Ayush Sawarni. Fairness and welfare quantifica- tion for regret in multi-arma bandits. AAAI'23, AAAI Press, 2023. ISBN 978-1-57735-880-00 doi: w..1600/aaaivv376.222. 43716.25829.
Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intellignnce and Statistics, pages 19-26. JMLR Workshop and Conference Proceedings, 2011.
Róbert Buka-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-objective bandits: Optimizing the generalized gini index. In International Conference on Machine Learning, pages 625-634. PMLR, 2017.
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare, ACM Truns. Econ. Comput., 7(3), sep 2019, ISSN 2167-8375. doi: 10.1145/3355902
10

---

Violet Xinying Chen and J.N. Hooker. A guide to formulating faimess in an optimization model. Annals of Operation Research, 326:581-619, 2023.
Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual multi-armed bandits: Theory and experiments. Conference on Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
Richard Cole and Vasilis Gkatzelis. Approximating the nash social welfare with indivisible items. In Proceedings of the seventse annual ACM symposium Theory of computing, pages 371-380, 2015.
Madalina M Drugan and Ann Nowe. Designing multi-objective multi-armed bandits algorithms: A study. In The 2013 international joint conference on neural networks (IJCNN) pages 1-8. IEEE, 2013.
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. Learning in games: Robustness fast convergence. Advances in Neural Information Processing Systems, 29, 2016.
Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997.
Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating nash social welfare under submod- ular valuations through (un) matchings. ACM Transactions on Algorithms, 19(4):1-25, 2023.
Stephen Gillen, Christopher Jung, Michael Kearns, and Aaron Roth. Online learning with an unknown fairness metric. Advances in neural information processing systems, 31, 2018.
Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredic- tors. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215, pages 79:1-79:21, 2022.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192 2007.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 2(3-4):157-322 2016.
Safwan Hossain, Evi Micha, and Nisarg Shah. Fair algorithms for aulti-agent Advances in Neural Information Processing Systems, 34:24005-2445 2021.
bandits.
Matthew Jones, Huy Nguyen, and Thy Nguyen. An efficient algorithm for fair multi-agent multi- armed bandit with low regret. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 8159-8167, 2023.
Matthew Joseph, Michael Kearns, Jamie H Morgenstem, and Aaron Roth. Fairness in learning: Classic and contextual bandits. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Mamoru Kaneko and Kenjiro Nakamura. The nash social welfare function. Econometrica, 47: 423-435, 1979.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts in metric spaces. Journal of the ACM (JACM), 66(4):1-77, 2019.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22) 1985.
Tor Lattimore. Bandit convex optimisation. arXiv preprint 0rXiv:2402.06535, 2024.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

---

Chung- Wei Lee, Haipeng Luo, Chen- Yu Wei, and Mengxiao Zhang. Bias no more: pooh-prbbbbilityy data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 13:15522-155333 2020.
Wenzheng Li and Jan Vondrák. Estimating the nash social welfare for coverage and other submodular valuations. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 11 119-1130. SIAM, 2021.
Yang Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, and David C Parkes. Cali- brated faimess in bandits. arXiv preprinl arXiv: 2017.
Haipeng Luo. Lecture note 13, Introduction to Online Learning. 2017. URL https://
haipeng- 1uo. hotoo///e/oooueeeeecctt/////olll
pdf.
Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
John Nash. The bargaining problem. Econometrica, 18(2):155-162, 1950.
Ayush Sawarni, Soumyabrata Pal, and Siddharth Barman. Nash regret guarantees for linear bandits. Advances in Neural Information Processing Systems, 36, 2024.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294, 1933.
Chen- Yu Wei and Haipeng Luo. More udaptive algorithms for adversarial bandits. In Conference On Learning Theory, pages 1263-1291. PMLR, 2018.
Julian Zimmert and Yevgeny Seldin. An optimal algorithm for stochastic and adversarial bandits. In The 22nd International Conference Artificial Intelligence and Statistics, pages 467-475. PMLR, 2019.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference machine learning (icml-03), pages 928-936 2003.
12

---

A Omitted Details in Section 3
In this section, we provide the omitted proofs for the results in Section 3. Appendix A.I, we provide the proof for Theorem 3.1 and in Appendix A.2, we provide the proof for Theorem 3.2.
A.1 Proof of Theorem 3.1
To prove Theorem 3.1, we first consider the following two events.
Event 1. For all E No + ,...,TT and i E [K],
t
No No
Σ
Pr.
18 log(KT),
T=KNo
where Ne.'s 's and pt, 's are defined in Algorithm 1. Event 2. For all E NK + MWNo+1,.... 1,..., Th E [K], and n E [N],
Ui log (Ng(N(72) 15 logg (NgK(
Vi, I Ut.im S Us,n + 8V
N₂s
No,1
where N 's defined in Algorithm 1.
As we prove in Lemma A. and Lemma A.2, Event and Event 2 hold with probability at least 1 7
Now we prove Theorem 3.1. For convenience, we restate the theorem as follows.
Theorem 3.1. With No 1+ 18 log KT, Algorithm I guarantees |eeg Ö(K & xx + K).
Proof. Let p" = argmax p NSW(u p). According to a standard regret decomposition for UCB-type algorithms, we know that Regsto be upper bounded as follows:
E
[Re
E
(NS((u pT) NSW(u p())
E
(NSW("Tp) - NSW(" pi))
Event and Event 2 hold + 2
(according to Lemma A. and Lemma A.2)
E
(NSW(uTp)) x²) -N)
Event and Event hold
+ KNo + 2
1= KN
+
E
Σ
(NSW(T, -NNW(, pc))
Event and Event hold
K=
+ E
Σ
(NSW(2, p.) NSW(u p.))
Event I and Event 2 hold
t= K=
E
(NSW(TT NSW(G) pi))
+
Σ
(N, px) - NSW p.))
+ KN + 2
(based on Event 2)
T
E
(NSW(G) p.) NSW(uT Pt))
Event I and Event 2 hold + KN,, + 2.
LE 1N+1
(based on the definition of p.)
13

---

In the following, we bound the first term
E
Σ (NSW(GTT)) p.) Lo=
-NW (eW(uTp))
Event and Event hold
As discussed in Section 3.1, we consider two cases. First, consider the set of rounds To such that for all To there exists least one n E [VV] such that (Pt, u.n)) S a for some a that will specify later. Denote such n to be nt (if there are multiple such n n's, we pick an arbitrary one). According to Event 2, we know that for all E [K],
Ut,, log(NKT3)
15 15lgg(NKKT)
[og([NKT² No.i
Mi,n; S Utii,n S Mg,n, + VV
I 20 + O
N₂,
N1,1
where the last inequality is because of AM-GM inequality. Therefore, we know that
K Σ j=1
(pt, Ue..mer S 2 (pe, u. +
Σ
Pt. Nos
S 20 +
PLj
No.
Now consider EIET. (NSW p.) NSW(u pc)). Direct calculation shows that (1. p.) NSW(" pc))
TET
NSW(ATTP) pt)
(since NSW(u pt) 2 0)
1ET
(Pes ue..me)
IET
< 2 O
+ Σ
Pt.j
(since (a ()+ S <ab + +b)
No.
1=1
i=1
K
2///o
+
Pl.d
(Hölder's 's inequality)
Ne.
1=1
2T xx -((xt p Tm )
(using Lemma A.3)
Now consider the regret within & E {N + I,..., TT... in which we have (pe, u.m) 2 a for all n E [N]. In this case, we bound ΣiET. (NSW(T)) p.) - (s pc)) as follows:
Σ (NSW(TTP.) NNS("" (p)))
TTT,
(ps Denn)) (Pe, u,n)
(using Lemma C. and Event 2)
TE nE(M]
(pe, Teaa u.n))
=k=0 (pe, Tean) & (pe, u..))
N-1
ET nE(N]
(pe, ueen u.n)
(since ue,em 2 Wi, for all i,t, based on Event 2)
TT nE[M]
N (pr, u.m)
Ejm Pt.j (8y unn (TT
logt NTT
Nos
No.i
(using Event 2)
N-1
N (pe, Unm)
TT nE[N]
14

---

Σラ 8y pes log(NKT2)
8pc, (
Nos
N-1
N (pe, (:.n)
N (pe: u:,n)
To ne[M]
(since v (pr, u.,.) 2 v Ptt,eli,n for all [K])
0
Pej
Pt.i t= N j= No.
No
Nos
No
:=
s 0 at KVT K.o 1
where the last inequality is because Lemma A.3. Combining the regret for both parts, we know that
Re < K +T tt + - KVT Ko Ax² + +K).
Picking the optimal a leads to the expected regret bounded by E EeRegttol S o 0KKTT xy
+ +K)
Lemma A.I. Event 1 happens with probability at least
4.
Proof. According to Algorithm 1, we know that N(K = No for each i E [K]. Consider the case when K No++1. at least 1 - 6, for a fixed 2 NNo + 1,
+ 1. According Freedman's 's inequality (Lemma C.3), we have with probability
1 = 2
Pr.t - 2,
Pr.i Pr. log(1/6) log(1/6)
+1
T= K No+
T=KNg No
2 2 No
Pri - 9 1lgg(10)).
Therefore, know that with probability least 1 8, for fixed 2 KNo + 1,
No. No
1(i, i No
Pr, 9 llg(11/)).
T=KNN+1
7=KNo+1
Picking 5 KT and taking a union bound over all i E [K] and KN + 1 S / S T reach the result.
Lemma A.2. Event 2 huppens with probubility least
Proof. According Freedman's 's inequality Lemma C.3, applying union bound over t [T].
i E K]. and n E [N], we know that with probability at least 8, for all t E (T), i e [K]. and [N].
Uin log log(N (KT/5)
log(NKT/0)
0e.im Wi,nl S V
(10)
N
Solving the inequality with respect Wi,,, we know that
log(NKT/8)
2 2log (NTg(N
14,
Te.in
Nr
No.i
20 +
(using AM-GM inequality)
No.
2
log log(NKX/6)
Vuin +
No.i
15

---

[log(N
Zuinn
(using AM-GM inequality)
N1 Using the above inequality and picking 7, we can lower bound Up.im as follows:
Ui,in log (Ng(N
8log(NKT3)
Ur Ue,an + 4
No,
N₁
log NKT3)
Ui,n
3 3lg
8 Slog(NKT)
Ue,in + +41
+
No.
No.
No,6
Wi,n log( (NKT2)
(8 4V3) log log(NKT2)
Ueiim + +4
2N
Ni,
(using va - 2 vā - vbror
Ugn log( (NK72)
log(NKT3)
Uegin + +2
N₂,
N1,1
Ug,,s
where the last inequality uses Eq. (10). To upper bound ig we have
Uni log(NKT²)
8log(NKT2)
un = -, + 4
Noi
No.
Ui log (og(N
log(N
S Uin +2
(using Eq. (10))
No.
No.
log( (TT2)
2u + Alog(NNTT)
8 (oog(N
+ 1/
Ni.i
N
N₂,1
Ui
log(NNT))
15
I Unn + St
(using AM-GM inequality)
Ni,
N₂
Combining the lower and the upper bound finishes the proof.
Lemma A.3. Under Event 1, Algorithm I guarantees that
Pr.i
S S0 (log T),
Nr.i
T= K No+1
Σ
Pr.i Nr.
00 <V(TlogT))
K
for all i E [K] and KN, + +1SEST.
2 k KN +1 Pr.: + holds for all E [K] and 7 2 KNN based on the choice of No log KT Therefore, we know that for each
Proof: Since Event holds, we know that N., 2 1 L
t KNo +
Prá N
2pr.i
KN Pri.i +2
T= No+1
T=KNo+1
Ei=kNott Pr.
2
da S 22log(T + 2).
x 2
As for the term ΣT=KNo+1
Pri Ny."
we have
Prá N
S.
(1 (N))
Σ
Pr.s N
(Cauchy-Schwarr inequality)
No+1
==KNot
16

---

I <((TToog])
A.2 Omitted Details in Section 3.2
Theorem 3.2. In the bandit feedback setting, for any algorithm, there exists a stochastic environment in which the expected regret (with respect to NSW) of this algorithm is Q N 2 log K and sufficiently large T.
(log KY K x
for
N3
Proof. Consider the environment that picks uniformly from {u()) : ..... (K)), where u.! e, E R and (8) 1 for all E ( N). Here, (0, b] is some constant be specified later. Denote (0) to be the environment where Vs,n = 0 for all E [M. At each round (, U1,i, is an i.i.d. Bernoulli random variable with di,n- For notational convenience, we use [4[1] when we take expectation over the environment (6) for i {0) [K]. Let nı be the number of rounds that action is selected over the total horizon T for all i E [K]] Therefore, the expected regret with respect to environment & (a uniform distribution over u (*), i [K]) is lower bounded as follows:
Eg Regl]
1 K
Σ E2
Pt.))
EN T
N-1
K
2 Te N
Σ
Pt.i
(Hölder's inequality)
K
1=1
1=1
E
N
K
T
2 TEN
E
Pt.
(Jensen's 's inequality)
K
[=1
T
2 -
K N
E
Pt.i
(11)
where the last inequality is again due to Hölder's inequality. Let Ber(a) be the Bernoulli distribution with mean a. Combining Exercise 14.4 of [Lattimore and Szepesvári, 2020], Pinsker's inequality, and Lemma 15.1 of [Lattimore and Szepesvári, 2020], we have
E
Σ
Peçi
E, [ms] Eo [m.]] TV
2 Ro(n: (I.((r())
S Eo [ng] +
Eo[n/]oon log
1+
2
1 1
s Eo [m4]] + T Eo [nx]
(using log(1 + x))
2(1 -
37
Eo
[n.] +
v [oo[neJe
T
T
3T
= Eo Σ
Pt.
Eo
Σ
Pr,i
E.
(12)
4
t=1
where the last inequality is because S
9:
Taking summation over all [K], we obtain that
T
Σ
E
Σ
Pr.
[E[
1=1
17

---

T
K
T
Σ |E[K]
EO
Ptç
+
T
Eg
pt,
Lt=1
1=1
1=1
K
T
37
T +
K
4
37
T VKT
(13)
where the second inequality is due to Cauchy- Applying Eq. (13) to Eq. (11), we obtain that
Cauchy-Schwarz Schwarz inequality.
Eg Reg]
3T 2 Teb K- N8 T+
VKTE
(1 - (1-K~*) Te K 2x g T N
(using (a+ Sa b
> log K
Ted K iN & 2N
28+1 "
2N
where the third inequality is according Lemma C.2 with x
N and
K. meaninn that
N
K
K
(log K)AN know that (1N)2NT
Picking E
28
T K
(log K)a
K x N=1
K
Ω
4N
N3
Combining the above all together, we know that Eg [Rgg] 2 Ω
(log K\" (logK)'
K T - Therefore,
N3
there exists one environment among u((), E [K] such that E, [Reg] which finishes the proof.
2 S
(lng K) K x
B Omitted Details in Section 4
B.1 Omitted Details in Section 4.1
In this section, we prove that that in the adversarial environment, also impossible achieve sublinear regret when f = NSW The hard instance construction shares a similar spirit to the one for f NSW shown in Theorem 4.1.
Theorem B.1. In the bandit feedback setting, for any algorithm, there exists an adversarial environ- ment such that B[Regadv] (QT for NSW prod-
Proof. We consider the learning environment with two agents and two arms. The agents utilities are binary, meaning that E {0, 2x2_ We construct two distributions & and E' with support {0. 1 To define environment ε, we use Qwzys for any w, x. y. E {0, to denote the probability that w1.: (w, æ) and w2 (v. when E. For simplicity of notation, the binary number ways will be written decimal form (i.e. Os = Prase (u1, (1,0), u2, = O)). For environment E, assign the probabilities
1
( 0.0. (
for E (O..... 15) (0,2,4,6)
(go- 42, 24 96)
16
Similarly, for environment E', we use Pwzyz for any w, x, 2, E {0, } to denote the probability that 2/. (w, 2) and u/2 = (y,2) 2) when u' ~ E'. Again, we will write the binary number wayz in decimal form for ease of notation. To environment 8' we assign probabilities
1
1
de = 16
for (o....,15)] (1,3,5,7)
(gh de. d' gf)
0.
8 :''0
18

---

Next, we argue that the learner's observations are equivalent in distribution in & and E', since the marginal distribution of every possible observation of each action the same. Specifically,
When action 1 is played, the learner's observation u1; in both & and E' are given by the following marginal distribution.
The probability of observation (0, 0) qo + 91 + - % q + + 4/2
The probability of observation (0, is 44 + + + q7 1/ + + + +
The probability of observation (1, is ys + +10 = d6 + 410 + gíi
-he probability of observation (1,1) 912 913 914 91s = 4/ hs d/4 9/5 =
When action 2 is played, the learner's observation u2 in both & and are given by the following marginal distribution.
The probability of observation (0,0) is yo + + 0 % + 1/ + 18 + 412
The probability of observation (0, 1) is + + 913 = gi + + 1 + 413
The probability of observation (1,0) 92 + 96 + 910 914 d/ + 0 410 + 9/4
The probability of observation (1,1) ds 47 + 915 dg +
915
Direct calculation shows that
Byng
NSW
prod (u' P)]
(95
96
99
q10)pi
+ (ge 97 -2gs + 99 + 911 913 qu1)p + (gs + gr 913 915)
pi
16 P1 4
16
Buve [NSW proa( p)]
(46 % 1/
holp + (g6 1/6 24's 0/ 1/11 ds Kul)r + (á's + o + + (1s)
2 1
1
16 Pi 16 P1 4
Therefore, we compute the learner's 's best strategy for environments and E' by direct calculation:
1 1
P. = argmax B [NSW prod proa(1l (u ')]] PEA=
argmax PEA:
4
16
P1
16
2'2
P- argmax E En NSW pma (TTp) p)]
argmax PEAz
1
P1
1
{(0, (1.0))
4
16
16
PEA2
Next, consider a distribution p E A2 such that pi E [0, 10.40[B
[3. For such p. direct calculation
shows that En_g [NSW p (u pp)) - NSW prod p)] 2 A, where A = 256 On the other hand, for prou
strategy p E A2 with P1 E (1 .). we have Euwsr [NSW prod (u TT)p) NSW prod (u") p) > A as
well. Given any algorithm, let ag be the probability that the number of rounds Pt, E [o, 1. U [ 1]
larger than T under environment E. Let āg. be the probability of the complement of this event under environment E". By definition
T
agTA
Eg [eegadv] 2 Eg
NSW Noo (u, p.)
NSW prod pt)
>
2
Tg
Eg [egaudd
2 Egg
NSW prod (1 p(.)
NSW (u, T Pt)
2
Since the feedback for the algorithm is the same in distribution, have ag +āg. 1. Thus, have
Eg Regadvl Eg [Regudel
(ar + Tg 2(T).
max [Regaav] LEg Regady]]
>
2
4
19

---

B.2
Omitted Details in Section 4.2
B.2.1
Concave and Pareto Optimal SWFs
Formally, for a function f [0, 1] + [0, 1}, concavity and Pareto Optimality are defined as:
Concavity: f(ar (1 - a)y) _ (z) + (1 fv) for any a E [0. 1] and æ, y [0, 1] Pareto optimality: for any x, E [0. 1| 2n 2 yn for all n E [N] implies f() 2 f(y)-
Pareto optimality is a "fundamental property" in social choice theory because it ensures that SWF prefers alternatives that strictly more efficient: everyone is no worse off [Kaneko and Nakamura, 1979]. Concavity appears less in social choice literature. However, it promotes equity by modeling diminishing levels of desirability with the increase single agent's utility.
In the following, we provide examples of SWFs that satisfy concavity and Pareto optimality. Each of the following SWFs are parameterized by fixed weights w AK.
Utilitarian SWF: (u) = (w., u);
Generalized Gini Index (GGI): f(u) = min (W=, u), where Sy is the set of permutations over N items and w, weights w permuted according to i E SN;
Weighted NSW: [u) Il " "
The last notable fact about the class of concave and Pareto Optimal SWFs is that it is closed under convex combinations. Specifically, for two concave and Pareto Optimal functions f. [0. 1] [0, 1], the function h(.) Xf(-) + ()g(.) for any À E [0, 1] is concave and Pareto Optimal. [Chen and Hooker, 2023] discusses how such convex combinations can be used to combine a SWF prioritizing efficiency and another prioritizing equity to derive different SWF that prioritizes balance between efficiency and equity.
B.2.2 Omitted Details in Section 4.2.1
In this section, we prove Theorem 4.2, which shows that O(VKT regret is achievable for all concave and Pareto optimal SWFs.
Theorem 4.2. For any f [0, 1J - [0, that is concave and Pareto optimal, Algorithm with the log-barrier regularizer ((p) = Ex
=i=1 log and T guarantees Regadv
Proof. Using the concavity of upper bound Regadv follows:
Regadv
max PEAx
Σ f(u p)
Σ fluTpo
T Σ pl)
max PEA, x,
Σ (-V pt). (Vf(uppt).P.
p)
max
Σ
f(uTp)
max PEA
PEAK
Tern (1)
Tern (2)
where AK, 2. = (pe
p. 2 KT. Vi (K]).
To bound Term (1), according to a standard analysis of FTRL/OMD with log-barrier regularizer (e.g. Lemma 12 of [Agarwal et al., 2017]), know that:
(p.P.
K [Vf(u] p:)
Term (1)
2 Pis i=
(14)
PEA
RT 7
where (p. 9) A (pp) (q)) (V q) is the Bregman divergence between p and g with respect to gb. To further bound the right-hand side, note that p1 1/2 Direct calculation shows that for any E AK. +
Do(ppi)) = Σ
Pi
log
Pi
P1,i
P1,7
20

---

K
log
Kpi
< log
1 (since pi 2 KT for all E [K]
K KT
$ K log T.
(15)
Using the Pareto optimality property of f and the positivity of the utility matrix ue we know that [V p)] 2 meaning that Σ př.; [V p:)], (pe. V po))
Moreover, using the concavity property of f. we know that (pe. VS(u, pi)) S f(ug S()
f(u pi) I 1. Combining the above two inequalities means that
ΣΣ i=
Pi. [f Po]. ST.
(16)
Combining Eq. (15) and Eq. (16), we can upper bound Term (1) as follows:
K log T
Term (1)
+ +nT.
(17)
7
Denote the optimal distribution p" argmaxpes, upper bound Term (2) follows:
Et (u,Tp) Recall that p1 1. Now
T
Term (2) =
f(u. p²)
max DEd K. गे. t=1
Σ S(TTp)
Σs S " ((1-7)
p" + T pP)) ))
<
[uTTT" p²)
t=1
((1 #)p- + #or AK.gT)
Σ (1--7) +) -fuu pz) + T f(u, pi)
T
5
f(u, p²) -
(Concavity)
1=1
1 T
<
p')
(since f(u pı) 2 0)
T
t=1
< 1.
(18)
Combining Eq. (17) and Eq. (18), and choosing 1)
K Klog T T
finishes the proof.
B.2.3 Omitted Details in Section 4.2.2
In this section, we present the omitted proof for Theorem 4.3, which shows better dependency on K compared with Theorem 4.2.
Theorem 4.3. For f NSW, Algorithm with the Tsallis entropy regularizer vbp) = 1-
1-3
2 8 N and the optimal choice of guarantees Regady = (
Proof. Consider the case when N 3. Direct calculation shows that
[V((T))) S
Us.
(19)
P n
Using the concavity of f and standard analysis of FTRL with Tsallis entropy (e.g., [Luo, 2017, Theorem I]), we know that
Regady Σ (S(u) p²) - p())
21

---

(Vf(u Pt).P" -Pt)
(concavity of f)
K1-B-
T
1
2-8
Pe,s
1711 3)
3
t=1
KI-8-1 -1
7
T
K
N
Pt,i Utiin
(using Eq. (19))
711 - 8)
N
k
Ueji Pe.))
==
K -1
T
Pt, iiim
u
(Cauchy-Schwel inequality)
711 B)
NB
Meiin po.j)
t=
j=1
K1-8 -1
1/
i=
Pi.i 11i.n
2-8
(since x1) Σ I for 2 1)
11( - B)
NB
N 2-
f= Pt.j
K2-8
N
2-9 2- U1ii. 2- x- ==
K
Pt.
S 111 3)
+
(since Ue,in E [0, 1)
NB
t=
n=1
1== Pt.j
Picking 3 2 the first term can be upper bounded by 3K' and the second term can be upper bounded by 97 NNT 2
"
Further picking the optimal choice of finishes the proof.
When = and B = & = 1, the regularizer (p()) 1- ااميخ becomes the negative Shannon
1-9
entropy vpp) = Σ pi log Using the concavity of f and following standard analysis of FTRL
with Shannon entropy regularizer (e.g.. [Hazan et al., 2016, Theorem 5.2)), we obtain that
Regade
(f(uT p¹) - fe(uT
ff ffuTpp).P pp)
(using the concavity of f)
(p') - ((11)
+2n Σ Σ
Pt, [V po)], (by [Hazan et al., 2016, Theorem 5.2])
7
log K
U1ii11
M4,12
+ 217
Pt.
71
2 (pe, u4,:1)
2 (pt. (e,.2)
1=1 i=1
log K
i= Pi
i==
+ 17
(AM-GM inequality)
K
1
Pt,.l
Li=1 Pt,
log K
2T/T.
(since Ueiin [0. 1] for all i,
Picking 17
V
log K
shows that Regady 0 (VTlog Ö(VT) for N 2.
B.2.4 Omitted Details Section 4.2.3
In this section, we show the proof for Theorem 4.4, which shows that logarithmic regret is achievable when there is at least one agent who is indifferent about the learner's 's choice. Theorem 4.4. Fix f = NSW. Suppose that for each time t, there a set of agents A, S [N] such that [A,] 2 M and U4... = Cr, 1 with Ct 2 for each agent n E Ag. Then the EWOO algorithm guarantees Regady = O N MM K log T).
Proof. To show that EWOO algorithm achieves logarithmic regret, need show that ft(p) 2 (u, p) is c-exp-concave for some 0 for all t [T]. meaning that
v f((p) av : 0.
22

---

Let A, S [N] be the set of agents with ue... Ct.n 1 for all E A on round t E [T]. It is
guaranteed that |A, M for all t [T]. Denote B, [N] A. Direct calculation shows that
1m Ae C. Vf((p)
fe(p)
(D, ue.am) We,n,s
NEB
A. C.m
Wtia V (p, uen..) (2( (p)
fe((p))
N
(p. uessm))
B
T
Sa(D) mE A, c.m
Σ
Weii (p, ueiin
Uti.n (p, Ue,.,o)
N2
NEB
nEB,
f((p) 4.
Ueni Mein iEB, (p, Ve.ia) )
N
For notational convenience, d = Am m.
M 1. Picking a N-M we know that
f4D VV
Xp)e(p)
Ue:i:.n (p, Messine?
Sefe(p) N
N2
(p. u.iii))
BE {D, ue,i.)
B,
me Bs
at (D)
Weiiin (p, Me,i.))
Σ WEB.
Ueiin
N2
(p. ueliin)
MEB.
de(1 - af((p))
Σ ne
Weis me Br {p, Meis
N
(p. ve.in)
N
(p, uemim)
nEB:
-ef((())
Σ We (p, ue,in)
afr(p)
Σ
Urii.n
Weiion
(p, ut,im)
(p, ueinn
NEB.
mEB.
ne B,
-)f((()
Σ
Munnuu.... kiim (p, ue.im)
++a
Whin
N
N
(p, men.m)
(p, ue,im)
mEB,
-xef(())
Σ Mennn nEB.
Ueii
Weain (p. ue,.,)
N
(p. Me..n)
N- M
(p, up,
nE
-xf((())
Uean Mrn nEB, (D, ue..n) ?
1
Uti.o
N
Be
{p, Me,ion)
(p, ue,.,)
AnE B,
0,
(Cauchy-Schwarl inequality)
where the first inequality because A < 1 and f((p) < O; the second inequality is because fe(p) 2 -1; the third inequality is because [&]] S N-M This shows that the (e(p) [7- -xxp- concave. Therefore, according to Theorem 4.4 of [Hazan et al., 2016], we know that the EWOO algorithm guarantees that
NN (N-M )
2(N M)
(f(lm)) <
K log T'
M
M
23

---

C Auxiliary Lemmas
In this section, we include several auxiliary lemmas that are useful in the analysis.
Lemma C.I. Let 01,-..; Ony bn E [0, 1}, where a; by for all [m]. Then, I II by S >i (a; b.).
Proof. Direct calculation shows that
n
72
II
01
04
bi
j=1
im
1
5-1
(aj bj)
01
j=1
1=++1
(aj - bj).
j=l
Lemma C.2. For all x E (0, 1) and (0, 1) satisfying + x log 2 0, we have L-a"
loga
2
Proof. Let y = log or < O. We know that
a
log a
x
Ty
2
Ty
RM < 1 2
which is true since e $ 1 + for all u [-1,0] 0] and xy log a 2
Lemma C.3 (Theorem I in [Beygelzimer et al., 201 1]). Let XI...., XT [-B, Bor some B >>> be a martingale difference sequence and with >T [x]] S V for some fixed quantity 0.
have for all 8 E (0, 1), with probability at least 1 8.
log(1/6) < 22 V log((16) + log(11/))
X
min
AV
XE 0,,1 B]
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
See abstract and Section 1.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how be expected to generalize other settings.
much the results
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification:
See Section 3, Section 4, and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer:
[NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https: /tts:://nips... cc/
pub / gu des Codeeuuomi i ss assiooolll liyylyyyyyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //niss. cc/ wttpccccppcccccccccccc.. httpp/ulcc/// httpc//gguss//eeeeeeceooecce /Codeee//Seaa CodeS Sumeeuubmiiee ss soliissinnn cessonoPoiccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
27

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tte:///neuue mwwriiuusssssse cttp./////biii//tcctcctuuuue
inne?
Answer: [Yes]
Justification: The authors have reviewed the NeurIPS Code of Ethics. The research con- ducted in this paper conforms with in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This work is mostly theoretical, and we do not foresee any negative ethical or societal outcomes.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers aw! thcode com da set. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "ZccC1VX5Ho", "reviewer": "Reviewer_t2CF", "summary": "The paper studies the problem of online social welfare maximization. More precisely, the authors consider the online learning setting where the learner, at each round $t \\in [T]$, picks an action $i \\in [K]$ that then determines the utility of each of the $n$ agents. The utility of agent $j$ is given by the $(i,j)$ entry of a utility matrix $u_t \\in \\mathbb{R}^{K \\times n}$, which can either change arbitrarily or be sampled from a predetermined probability distribution. The cost of the learner is given by the Nash Welfare, defined as the geometric mean of the agents' utilities: $NW(\\mu) = (\\Pi_{n \\in [n] \\mu_n})^{1/n}$. The goal of the learner is to pick a sequence of mixed actions to achieve social welfare comparable to that achieved by the best fixed mixed actions.\n\nThe authors consider both the stochastic and the deterministic versions of the problem, as well as both the bandit and full-information feedback models. For the stochastic case with bandit feedback (where the learner learns only the utilities of the agents for the randomly sampled action), the authors provide an $O(T^{N-1/N})$-regret online learning algorithm and show that this regret bound is tight for the stochastic setting. They then study the bandit feedback model with adversarial changes and establish an $\\Omega(T)$ regret lower bound. In view of this negative result, the authors shift their attention to the full-information feedback and adversarial changes case, for which they provide $O(\\sqrt{T})$-regret online learning algorithms using Follow the Regularized Leader with log-barrier regularization.", "questions": "Could you elaborate more on the potential applications of the considered setting?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies an interesting and technically challenging setting. The writing is relatively good, and the authors clearly explain their contributions and the crucial differences between their setting and classical online concave optimization with bandit feedback. I found it particularly interesting that there is a significant discrepancy in the possible regret bounds between online concave optimization and the bandit feedback case of the considered setting. Additionally, I appreciate that the authors present both upper and lower bounds for all the considered settings.", "weaknesses": "Despite the paper's solid technical contribution, my only concern lies with the motivation for the setting. The authors briefly mention that the setting has applications in resource allocation but do not provide any concrete examples or a convincing discussion on why this setting is particularly interesting. While I do not doubt that the setting is indeed interesting, I believe a detailed discussion on the potential applications of the model would significantly enhance the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reviewer's appreciation of our paper! We answer the reviewer's question as follows.\n\n**Q1: A detailed discussion on the potential applications of the model.**\n\nOne important application of the model is fair repeated policy decision making. In fact, we believe that Hossain et al. [2021], the main work we improve upon, already provided very good justification for studying this model, and we copy one such discussion from their introduction below: \n\n*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 problem of making a fair collective decision when the available alternatives affect multiple agents is well-studied in computational social choice. The literature offers a compelling fairness notion called the Nash social welfare, named after John Nash… 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, and maximizing the egalitarian social welfare (minimum utility to any agent), which is considered too extreme. The solution maximizing the Nash social welfare is also known to satisfy other qualitative fairness desiderata across a wide variety of settings.*", "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": "", "extra_scores": {}}, {"review_id": "TrGYFZNME1", "reviewer": "Reviewer_aYwg", "summary": "The authors address the problem of maximizing Nash Social Welfare (NSW) in a centralized multi-agent multi-armed bandit setting. In each round, a central entity selects a probability distribution $p_t$ over the $K$ actions, and draw an action $i_t  \\sim p_t$.  Upon selecting an action, the central entity observes the $i$-th row of the $K\\times N$ utility matrix $u_t$ which indicates the utility received by each of the $N$ agent when choosing one of the $K$ actions.The goal of the central entity is to maximize the sum of the Nash Social Welfares over the rounds, where the NSW for a given round is defined as the geometric mean of the expected utilities received by the agents: $$NSW(p_t, u_t) = \\Pi_{j = 1}^{N} \\langle p_t \\vert u_t\\rangle^{1/N}.$$\n\nThe authors note that, unlike the product of expected utilities, the Nash Social Welfare (NSW) is not Lipschitz continuous. Consequently, the analytical techniques used in previous works that study the product of expected utilities are not applicable here. In the scenario where the utility matrix $u_t$is drawn i.i.d. from some unknown distribution, the authors develop an algorithm for this problem and establish both upper and lower bounds that match in terms of scaling with the horizon $T$. Next, they consider the adversarial framework. They demonstrate that with bandit feedback, the worst-case regret must scale linearly. They propose two different algorithms for the adversarial case with full information and show that both achieve a regret of $\\tilde{O(\\sqrt{T}}$, with different dependence in $N$ and $K$.  Finally, they show that in some special cases, the regret can be logarithmic in $T$.", "questions": "- Could you please quickly comment on why the Nash Social Welfare is defined as the geometric average of the expected utility, instead of the expectation of the geometric averages of the utilities? Admittedly, the latter might be less interesting from a mathematical standpoint. Is this a choice you are making, or is it a commonly accepted definition? \n- Could you please detail a bit more how you obtain the thrid line from the second line of the computations at the end of page 14?\n- There is a typo at the last line of page 4, where a \"O\" is capitalized in the middle of a sentence.", "limitations": "The limitations are well addressed.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I am not very familiar with the literature on Nash Social Welfare; however this paper seem to address a well-motivated problem in multi-agent decision-making.\n\nThe authors propose a UCB algorithm for maximizing the sum of Nash Social Welfares (NSW), utilizing new confidence bounds to achieve optimal regret rates. They establish a matching lower bound on the regret, providing theoretical robustness to their approach. Additionally, they explore the adversarial case, a scenario that had not been previously addressed. Their results reveal that bandit feedback alone is insufficient to achieve sub-linear regret rates. To complete their investigation, they propose a Follow-the-Regularized-Leader (FTRL) algorithm. While FTRL is not a novel algorithm, its application here concludes a comprehensive analysis of the problem at hand.\n\nThe paper is very clear, with the key ideas of the proofs well outlined and the problem effectively contrasted with existing works.", "weaknesses": "I see no major weaknesses. As a minor remark, the use of the Nash Social Welfare is not motivated. While it is a standard welfare measure in economics, it may be unfamiliar to those in the bandit literature. Therefore, it is worth introducing and discussing its significance and relevance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the reviewer's detailed and valuable comments to our paper. We address the reviewer's questions as follows.\n\n**Q1: the use of the Nash Social Welfare is not motivated**\n\nA: We will add more discussion on the significance and relevance of the use of NSW in the next version as suggested. We point out that Hossain et al. [2021], the main work we improve upon, has provided very good motivation on studying NSW, and we copy one such discussion below for reference:\n\n*This problem of making a fair collective decision when the available alternatives affect multiple agents is well-studied in computational social choice. The literature offers a compelling fairness notion called the Nash social welfare, named after John Nash… 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, and maximizing the egalitarian social welfare (minimum utility to any agent), which is considered too extreme. The solution maximizing the Nash social welfare is also known to satisfy other qualitative fairness desiderata across a wide variety of settings.*\n\n**Q2: Could you please quickly comment on why the Nash Social Welfare is defined as the geometric average of the expected utility, instead of the expectation of the geometric averages of the utilities? Admittedly, the latter might be less interesting from a mathematical standpoint. Is this a choice you are making, or is it a commonly accepted definition?**\n\nA: We point out that the former (geometric average of expected utilities, which we study) is arguably more meaningful as a fairness measure than the latter (expected geometric average of utilities). To see this, simply consider a setting with 2 agents and 2 arms, where the first agent always gets reward 1 from arm A and reward 0 from arm B, while the second agent is the opposite (reward 0 from arm A and reward 1 from arm B). Then, in terms of geometric average of expected utilities, the uniform distribution is the best policy (which makes sense from a fairness viewpoint); on the other hand, in terms of the expected geometric average of utilities, all distributions achieve the same value of 0, implying that all polices are as fair, which is clearly not what we want.\n\nTherefore, both previous works (Hossain et al. [2021] and Jones et al. [2023]) and ours study the former notion (which is in fact also mathematically more interesting as the reviewer pointed out).\n\n**Q3: Could you please detail a bit more how you obtain the third line from the second line of the computations at the end of page 14?**\n\nA: We use the fact that $a^N-b^N=(a-b)\\cdot (\\sum_{k=0}^{N-1} a^kb^{N-1-k})$ with $a=<p_t, \\hat{u}_{t,:,n}>^{1/N}$ and $b=<p_t, u_{:,n}>^{1/N}$.\n\nFinally, thanks for pointing out the typo on Page 4! We will fix that in the next revision.", "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": "", "extra_scores": {}}, {"review_id": "7xmN6ZCA4X", "reviewer": "Reviewer_izKh", "summary": "The paper considers a new fairness measure, say NSW, lacking Lipschitzness. Unlike previous measures, the multi-armed bandit problem cannot obtain common $O(\\sqrt T)$ regret. For stochastic MAB, the authors find an algorithm achieving $\\tilde{O}(T^{\\frac{N-1}{N}})$ regret and show its tightness. For adversary scenarios, the authors show that no algorithm can achieve sublinear regret. Then, they consider an easier information structure, say full-information feedback and $\\sqrt T$ regret is possible. Finally, they consider the situation when logarithmic regret is achievable.", "questions": "1. What will happen if the learning can only observe NSW rather than everyone's utility? Will it change the dependence of $K$ and $N$?\n\n2. In Line 324, what is $f(p_t)$? I believe the input of $f$ is an $R^N$ vector. However, $p_t$ belongs to $R^K$.\n\n3. Typo: In Line 338, \"is not only convex\" should be \"concave\".", "limitations": "No limitations.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The model is clear and the algorithms proposed are easy to understand. Besides, the authors consider different information structures and models to depict the problem completely. And the construction of lower bounds is very nice.", "weaknesses": "1. The paper shows why considering $NSW$ is better than considering $NSW_{prod}$. However, why not consider simple average which is more intuitive? I recommend that the authors provide some realistic applications for NSW.\n\n2. If I understand correctly, you consider an addictive utility, for example, you consider expected regret when showing lower bounds. However, for (2), why do you use $NSW(u^Tp_t)$ rather than $\\sum_i p_{t,i}NSW(u_{t,i})$? The definition of regret seems strange.\n\n3. The statement in Line 165 is not correct. We don't need to observe $u^T_t p_t$ when using BCO though we may need the dimension of $u$ to be 1, i.e. $N=1$. When you prove the lower bounds, I think the negative result, i.e., Thm 3.2, holds because NSW is concave but https://arxiv.org/pdf/2402.06535 needs convexity. However, in Appendix B. 1., you have convexity, so you can only construct a hard-to-learn example with at least two agents. I'm not sure whether my intuition is correct. If it is, some statement in the paper doesn't hold. If not, please explain more about the construction of your lower bounds to make it easy to understand.\n\n4. You mention that NSW is not Lipschitz, but why not make a truncation? If an agent has a very small utility, like $\\sigma$ in the paper, the regret will be small. Otherwise, we can use Lipschitzness. Is there any difference between your methods? If not, show the reason why NSW doesn't make the problem harder. Also, if you have time, it's meaningful to use experiments to compare these two ideas.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and valuable comments to our paper. We address the reviewer's questions as follows.\n\n**Q1: However, why not consider a simple average, which is more intuitive? I recommend that the authors provide some realistic applications for NSW.**\n\nA: It is well-known that a simple average does not promote fairness. To see this, consider the following example mentioned by Hossain et al. [2021]: suppose there are 10 agents and 2 arms, where the first 4 agents receive reward 1 from arm A and reward 0 from arm B, and the other 6 agents receive reward 0 from arm A and reward 1 from arm B. If we use average as the measure, then the best policy is to always pull arm B, while if we use NSW as the measure, the distribution (0.4, 0.6) over the two arms is the best policy, which is clearly more reasonable from a fairness viewpoint.\n\nFor “some realistic applications for NSW”, we refer the reviewer to our first response to Reviewer t2CF.\n\n**Q2: For (2), why do you use $𝑁𝑆𝑊(u^\\top p_t)$ rather than $\\sum_{i\\in[N]}p_{t,i}𝑁𝑆𝑊(𝑢_{𝑡,𝑖})$? The definition of regret seems strange.**\n\nA: This is because the former (geometric average of expected utilities) is arguably more meaningful as a fairness measure than the latter (expected geometric average of utilities). To see this, simply consider a setting with 2 agents and 2 arms, where the first agent always gets reward 1 from arm A and reward 0 from arm B, while the second agent is the opposite (reward 0 from arm A and reward 1 from arm B). Then, in terms of geometric average of expected utilities, the uniform distribution is the best policy (which makes sense from a fairness viewpoint); on the other hand, in terms of the expected geometric average of utilities, all distributions achieve the same value of 0, implying that all polices are as fair, which is clearly not what we want.\n\n\n**Q3: The statement in Line 165 is not correct. We don't need to observe 𝑢𝑡𝑇𝑝𝑡  when using BCO though we may need the dimension of 𝑢 to be 1, i.e. 𝑁=1. When you prove the lower bounds, I think the negative result, i.e., Thm 3.2, holds because NSW is concave but https://arxiv.org/pdf/2402.06535 needs convexity. However, in Appendix B. 1., you have convexity, so you can only construct a hard-to-learn example with at least two agents. I'm not sure whether my intuition is correct. If it is, some statement in the paper doesn't hold. If not, please explain more about the construction of your lower bounds to make it easy to understand.**\n\nA: We believe that there are some significant misunderstandings from the reviewer. First of all, when $N=1$, our problem simply reduces to the classic multi-armed bandit problem, whose minimax regret rate is well-studied, so our focus is on the case when $N\\geq 2$. After all, what is the point of considering fairness when there is only one agent? \n\nSecond, you mentioned that our NSW is concave while standard BCO needs convexity, but note that our problem is about **utility maximization** while BCO is about **loss minimization**, so concavity in the former is just equivalent to convexity in the latter by simply taking negation of the objective.\n\nFinally, your comment about Appendix B.1 also does not make sense to us. In Appendix B.1, we consider the product version of NSW used by previous works, which is neither convex nor concave.\n\n**Q4: You mention that NSW is not Lipschitz, but why not make a truncation? If an agent has a very small utility, like 𝜎 in the paper, the regret will be small. Otherwise, we can use Lipschitzness. Is there any difference between your methods? If not, show the reason why NSW doesn't make the problem harder. Also, if you have time, it's meaningful to use experiments to compare these two ideas.**\n\nA: We are not sure if we fully understand the reviewer’s idea, and will clarify based on our understanding below. If this does not address your question, please do follow up on this.\n\nFirst, note that our truncation in the analysis is on the quantity $\\langle p_t, u_{:,n}\\rangle$ (Line 202), which is related to the unknown utility $u$ and is thus cannot be explicitly implemented in the algorithm itself.\n\nSecond, if what the reviewer meant is to truncate $\\langle p_t, \\hat{u}_{t,:,n}\\rangle$ instead, that is, replace NSW in Algorithm 1 by \n\n$$NSW_{\\sigma}(\\mu)=\\prod_{i=1}^N \\max(\\sigma, \\mu)^{1/N},$$ \n\nthen, regardless whether the analysis works, it does not seem that the algorithm can be efficiently implemented since it is unclear how to compute $p_t$ given that $NSW_{\\sigma}$ is not concave (and neither is $\\log NSW_{\\sigma}$).\n\n**Q5: What will happen if the learning can only observe NSW rather than everyone's utility? Will it change the dependence of $𝐾$ and $𝑁$ ?**\n\nA: As we discussed in Lines 161-171, in this case, the problem is just an instance of standard bandit convex minimization (or equivalently, bandit concave maximization). Therefore, applying the state-of-the-art algorithms from [Fokkema et al., 2024] achieves $O(K^{1.75}\\sqrt{T})$ regret in the stochastic setting and $O(K^{3.5}\\sqrt{T})$ in the adversarial setting (both without $N$ dependence).\n\n\n**Q6: In Line 324, what is $𝑓(𝑝_𝑡)$? I believe the input of $𝑓$ is an $\\mathbb{R}^𝑁$ vector. However, $𝑝_𝑡$ belongs to $\\mathbb{R}^𝐾$.**'\n\nA: It should be $f(u_t^\\top p_t)$ instead. Thanks for pointing out the typo!\n\n**Q7: In Line 338, \"is not only convex\" should be \"concave\".**\n\nA: This is **not** a typo. Note that we are talking about -NSW here, which is indeed convex since NSW is concave.\n\n**Reference**\n\n[Fokkema et al., 2024] H. Fokkema, D. van der Hoeven, T. Lattimore, and J. Mayo. Online Newton method for bandit convex optimisation. In Conference on Learning Theory, 2024.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work derives minimax regret bounds for the objective of Nash social welfare (NSW). Prior work did consider a similar objective (product of utilities) but the NSW objective (i.e. geometric mean) presents some unique challenges and requires new proof techniques. I also like the adversarial setting considered in the paper, and the paper is well-written and all the ideas are carefully explained. In the future version of the paper, it would be useful to have some discussions about the applications of NSW.
Decision: Accept (poster)