  Recently a multi-agent variant of the classical multi-armed bandit was
proposed to tackle fairness issues in online learning. Inspired by a long line
of work in social choice and economics, the goal is to optimize the Nash social
welfare instead of the total utility. Unfortunately previous algorithms either
are not efficient or achieve sub-optimal regret in terms of the number of
rounds $T$. We propose a new efficient algorithm with lower regret than even
previous inefficient ones. For $N$ agents, $K$ arms, and $T$ rounds, our
approach has a regret bound of $\tilde{O}(\sqrt{NKT} + NK)$. This is an
improvement to the previous approach, which has regret bound of $\tilde{O}(
\min(NK, \sqrt{N} K^{3/2})\sqrt{T})$. We also complement our efficient
algorithm with an inefficient approach with $\tilde{O}(\sqrt{KT} + N^2K)$
regret. The experimental findings confirm the effectiveness of our efficient
algorithm compared to the previous approaches.
