2022/09/23 by Matthew Jones, Jones, Matthew, Huy L. Nguyên +3 · 3 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2209.11817
openalex publication_date 2022/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(√(NKT) + NK). This is an improvement to the previous approach, which has regret bound of O( min(NK, √(N) K3/2)√(T)). We also complement our efficient algorithm with an inefficient approach with O(√(KT) + N2K) regret. The experimental findings confirm the effectiveness of our efficient algorithm compared to the previous approaches.