An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
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.
Code (0)
등록된 구현이 없습니다.
Tasks
2kFairnessSimilar Papers 제목 키워드 기반
Fair Algorithms for Multi-Agent Multi-Armed Bandits
We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are $N$ agents and $K$ arms, and pulling an arm generates a (possibly different) stochastic reward for each agent. Unlike the c…
FairnessMulti-Armed BanditsMulti-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness
We investigate the problem of maximizing social welfare while ensuring fairness in a multi-agent multi-armed bandit (MA-MAB) setting. In this problem, a centralized decision-maker takes actions over time, generating rand…
FairnessMulti-Armed BanditsFair Contextual Multi-Armed Bandits: Theory and Experiments
When an AI system interacts with multiple users, it frequently needs to make allocation decisions. For instance, a virtual agent decides whom to pay attention to in a group setting, or a factory robot selects a worker to…
Decision MakingFairnessMulti-Armed BanditsNo-Regret Learning for Fair Multi-Agent Social Welfare Optimization
We consider the problem of online multi-agent Nash social welfare (NSW) maximization. While previous works of Hossain et al. [2021], Jones et al. [2023] study similar problems in stochastic multi-agent multi-armed bandit…
FairnessMulti-Armed BanditsFairness and Privacy Guarantees in Federated Contextual Bandits
This paper considers the contextual multi-armed bandit (CMAB) problem with fairness and privacy guarantees in a federated environment. We consider merit-based exposure as the desired fair outcome, which provides exposure…
FairnessFederated LearningMulti-Armed Bandits