Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies stochastic multi-agent multi-armed bandits where the reward distribution could be heterogeneous, i.e., the mean reward for agents on an arm could be different.  The authors consider Nash social welfare as the fairness criteria and aim to learn a distribution on arm plays that result in optimal Nash social welfare. Thress algorithms based on Explore-Then-Commit, Epsilon Greedy, and UCB are given and their performance is analyzed.
main_review: Using Nash social welfare as a fairness criterion in multi-armed-bandits is interesting. However, I felt that setup and analysis are weak. My comments are:

1) Why do all the agents have to play the same arm in each round. If they can also play different arms, cannot they learn faster?

2. Line 219-220:  If $\hat{\mu}_{i,j}^t$ is obtained from $n_j^t$ and the rewards have bounded support, why cannot be Hoeffding's inequality be applied? What violates the hypothesis of Hoeffding's result?

3. The bound in Lemma 5 holds with some probability or it is a deterministic bound?'

4. Lemma 4: In the definition of $\Epsilon^t$, are parenthesis missed?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies multi-agent multi-armed bandits under heterogeneity (where arm means vary across users), with the objective to optimize Nash social welfare to ensure fair allocation of pulls in the obtained policy. The authors present variants of explore-first, epsilon-greedy, and upper confidence bound strategies to achieve fair decision-making. Each algorithm obtains "fair" regret matching the standard counterpart, along with a $ \Omega(\sqrt{T})$ lower bound in the Appendix. The central technical (theoretical) contribution is a concentration result on the fluctuation of NSW that exploits the Lipschitz property of the objective coupled with a covering argument, which is then utilized subsequently to derive regret bounds for each of the proposed algorithms. 
main_review: Originality and Quality: I like the topic and contributions of the paper. Fairness in multi-armed bandits is typically concerned with fairness across arms, and multi-agent decision-making typically involves purely cooperative objectives, which suffer from the _tyranny of the majority_ effect as the authors have rightly pointed out. The paper does present the feasibility of NSW as an objective for bandit algorithms and analyzes popular single-agent algorithms, and I feel that it serves as a good contribution to the development of more work in this area. However, while the paper does address multi-agent decision-making, the algorithms and setup are essentially "single-agent" in the sense that one controller decides the policy for all agents. From a theoretical and algorithmic perspective, this may appear to be a necessary first-step simplification, but most deployment scenarios for multi-agent decision-making do not allow for such synchronicity, which is something the authors should discuss.

The previous remark is related to the broader concern around neglecting quite a vast and fast-growing literature around multi-agent multi-armed bandits in more realistic, distributed environments [https://arxiv.org/abs/1606.00911, https://scholar.harvard.edu/files/shahin/files/icassp_2017.pdf, https://arxiv.org/abs/2008.06220, and references therein], where heterogeneity and delay in communication ensure that the algorithms proposed are "multi-agent" in the true sense of the term, rather than a single-agent controlling a more nuanced objective than cumulative reward. In this regard, this work is also related to multi-objective bandit optimization [https://people.eecs.berkeley.edu/~kandasamy/pubs/pariaUAI19mobo.pdf, https://arxiv.org/abs/1905.12879] where a measure of performance employed is Pareto optimality, instead of cumulative reward. Discussing these approaches in context with the proposed research will go a long way in shaping further research into practical algorithms in real-world settings, moving beyond regret bounds that are effectively "single-agent".

Going through the technical parts, I feel like the previous revisions have ironed out the remaining technical issues, although I am curious to know if Lemma 6 can perhaps be tightened more by considering a smaller class of policies than the entire K-simplex, following a similar line of argument for UCB policies as done in https://arxiv.org/abs/1907.05388, for example.

Clarity: The paper is well-written and easy to follow.

Significance: Fairness in online learning is an important topic of interest to the NeurIPS community.

In summary, after placing this work in context to the work in distributed multi-agent decision-making, I feel that it would be a good contribution to the conference.
limitations_and_societal_impact: The major limitations of the work as is are the "centralized" nature of the proposed policy and the intractability of the UCB algorithm presented. The authors should discuss this in more detail in the updated version.

Given that the paper discusses fairness in a technical sense in context of online learning, the authors have done a good job of addressing the societal impact of their work, and I do not foresee any additional negative societal impact of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a multi-armed bandits problem with multiple agents. Arms have agent specific reward distributions associated with them. An arm is pulled at each step and each agent receives a reward sampled from their corresponding agent specific reward distribution for this arm. The goal of the learner is to find a distribution over arms that maximizes an appropriate aggregate notion of rewards earned by all agents – the Nash welfare.

The paper develops variants of three standard algorithms – one that explores for a fixed number of rounds and then exploits (Explore-First), an epsilon-greedy style algorithm, and a UCB style algorithm, to minimize a notion of regret which measures the difference between the Nash welfare of the solution at time t and the optimal Nash welfare. The paper derives upper bounds on the expected regret of the algorithm in each case. For UCB, the upper bound matches the lower bound (in the appendix) in terms of its dependence on parameter T (time horizon).
main_review: Originality – This appears to be the first work that studies Nash welfare maximization in a multi-agent multi-armed bandits setting and obtains a \sqrt{T} regret bound. The paper does a good job of highlighting additional challenges posed by this setup. For instance, the mean estimates of the agents (for a given arm) are not independent as they all depend on the number of times that arm was pulled, which is same for all agents.

Quality – 
1.	The theoretical results in the paper are fairly intuitive and appear to be sound. While the upper bound for UCB matches the lower bound in terms of T, the dependence on other parameters (K: #arms, N: #agents) appears to be suboptimal. 
2.	Although the paper argues that “traditionally, the focus is on optimizing the exponent of T rather than that of K”, I do not completely agree with the statement, especially in the context of the current paper where N x K may be very large.
3.	A stronger lower bound in terms of K and N would have helped in understanding the quality of the current upper bounds. Even empirical results will provide additional information about the tightness of the current upper-bound.
4.	Combining the fact that the upper bound for UCB may be very loose (in terms of N and K) with the fact that it will be inefficient to implement, makes the assessment of the utility of the algorithm hard.

Clarity – The paper is very well written and easy to follow.

Significance – See point 4 under Quality. This makes it hard to argue for the significance of the current work. Having said that, I agree that the paper takes an important first step for an interesting problem.

Strengths – Very well written, the regret of UCB has optimal dependence in terms of T

Weaknesses – Unclear about the tightness of the bounds in terms of N and K (see details above)

**Update**: Dear Authors, thank you for your response. I agree that $T \geq K$ is a harmless assumption. However, the same is not true for $T \geq N$, and hence not true for $T \geq N \times K$ (am I missing something here?). I still believe that this is worth exploring, but the paper is undoubtedly a good first step in this direction. My score remains unchanged.
limitations_and_societal_impact: The paper discusses various limitations such as possible sub-optimal dependence on N and K, and difficulty in optimising the objective required by UCB.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: In this paper, the authors propose to minimize the Nash Social Welfare (NSW) function -- the product of utilities, in a multi agent multi-armed bandit problem. The NSW strikes a balance between utilitarian and egalitarian optimization in a multi agent framework. The product of utility maximization is a log-concave optimization for which they propose three algorithms -- Explore-then-commit, Epsilon-Greedy, and UCB.  They establish regret upper bounds for the proposed algorithms, with UCB having the best \tilde{O}(\sqrt{T}) regret.  
main_review: Pros

- The maximization of the NSW objective in a multi-agent setting promotes fairness consideration for the multi-agent bandits problem. 

- Technically, the bandit optimization problem is a special log-concave for which this paper proposes the first \tilde{O}(\sqrt{T}) regret bound (to the best of my knowledge).  The authors also discuss why the existing results will not provide such a regret bound (see drawbacks for improving this). 
  
- The writing is clear and easy to follow (except for a few aspects described shortly). The proof sketches are insightful. 

Drawbacks and Suggestions

- The key drawback of the paper is the centralized optimization in the multi-agent setting. Maybe the authors can discuss how the agents are incentivized to submit truthful feedback to the centralized arbiter. 

- Can you provide the details of the zooming dimension  (as per Kleinberg et al.) computation . Also, why the tree-search approach in  'Multi-scale exploration of convex functions and bandit convex optimization' not applicable here? 

- The related works in the no-regret learning in non-cooperative games is not discussed properly. Please add these works. E.g. 'Bandit Learning in Concave N-Person Games' - Bravo et al. and the references therein.

- Provide a proof sketch of Lemma 6 in the main paper. Can the union bound on the possible number of pulls be avoided there? Also what is the slackness added by taking such a union bound? 

- Discussions on when Lemma 5/Lemma 6 should be applied depending on N,K, and T will be useful. In particular, can we adaptively set \alpha_t in UCB by switching from N to O(\sqrt{NKlog(NKt)}) (or the opposite) to improve the regret bound? 
limitations_and_societal_impact: This work is theoretical in nature. It deals with maximizing the Nash Welfare objective that is established to promote fairness in the literature. Thus, I think this paper will not have negative societal impact.
review_title: null

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