No-Regret Learning for Fair Multi-Agent Social Welfare Optimization

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.

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. 2. 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. 3. 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. 4. 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.

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$? 2. 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$. 3. Typo: In Line 338, "is not only convex" should be "concave".

Rating

4

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

No limitations.

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}.$$ The 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$.

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. The 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. The 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.

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? - 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? - There is a typo at the last line of page 4, where a "O" is capitalized in the middle of a sentence.

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

The limitations are well addressed.

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. The 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.

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.

Questions

Could you elaborate more on the potential applications of the considered setting?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Rebuttal acknowledgment

I thank the authors for their rebuttal, which adequately answers my questions.

Reviewer's Response

Thank you for the response. I maintain my positive opinion for the paper and I keep my score.