An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
This addresses fairness in online learning for multi-agent systems, offering an incremental improvement in regret efficiency.
The paper tackles the problem of achieving fairness in multi-agent multi-armed bandits by optimizing Nash social welfare, proposing an efficient algorithm that reduces regret to $ ilde{O}(\sqrt{NKT} + NK)$, improving over previous bounds like $ ilde{O}(\min(NK, \sqrt{N} K^{3/2})\sqrt{T})$.
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.