An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret

Matthew Jones, Huy Le Nguyen, Thy D. Nguyen

TL;DR

This paper introduces a new, computationally efficient algorithm for the Multi-Agent Multi-Armed Bandit (MA-MAB) problem that balances total reward with fairness using the Nash Social Welfare (NSW) metric. By maintaining the log-concavity of the optimization objective, the authors achieve significantly lower regret and faster runtimes than previous state-of-the-art methods, particularly as the number of agents and arms grows.

What Problem Does This Paper Address?

In a standard Multi-Armed Bandit (MAB) problem, a decision-maker pulls an arm and receives a reward, aiming to maximize the total sum over time. However, in many real-world scenarios—like a policy-maker choosing a resource allocation or a recommendation engine picking hyperparameters—a single decision affects multiple agents simultaneously.

If you simply maximize the sum of everyone's rewards (the utilitarian approach), you might end up being very "unfair"—for example, choosing an arm that gives 10 agents a reward of 1 and 9 agents a reward of 0, even if another arm gives all 19 agents a reward of 0.5.

To solve this, researchers use Nash Social Welfare (NSW), which is the product of all agents' expected rewards. NSW acts as a "Goldilocks" middle ground between being purely utilitarian (maximizing the sum) and purely egalitarian (maximizing the minimum reward). The challenge is that optimizing NSW in an online learning setting is mathematically difficult; previous algorithms were either computationally slow (non-convex) or had "regret" (the gap between the algorithm and the optimal strategy) that grew too quickly over time.

Methods

The authors propose two primary algorithms:

  1. Algorithm 1 (Efficient Fair UCB): This is the star of the paper. It uses an Upper Confidence Bound (UCB) approach. At each round, it estimates the mean reward for every agent-arm pair and adds a confidence interval.
  2. The Innovation: Previous work added a linear regularization term to the objective function, which made the optimization problem non-convex and hard to solve. This paper instead optimizes the NSW of the UCB estimates directly. Because the log of the NSW is concave, the authors can use standard, efficient convex optimization tools (like projected gradient ascent).
  3. Tighter Bounds: They use a more sophisticated confidence interval that scales with the empirical mean, leading to tighter estimates.
  4. Algorithm 2 (Inefficient with Lower Regret): This is a theoretical contribution. It requires a high "start-up cost" (pulling every arm many times at the beginning) but achieves a theoretically better regret bound in terms of the time horizon $T$. However, it involves non-convex optimization, making it less practical for real-world use.

Datasets

The authors evaluated their algorithms using synthetic datasets to precisely control the reward distributions and agent preferences.

  • Reward Distributions: Rewards were drawn from Bernoulli distributions.
  • Scales: They tested three configurations: Small (4 agents, 2 arms), Medium (20 agents, 4 arms), and Large (80 agents, 8 arms).
  • Comparison: They benchmarked against the previous state-of-the-art UCB algorithm proposed by Hossain et al. (2021).

Key Results

Lower Regret and Scalability

Algorithm 1 achieves a regret bound of $\tilde{O}(\sqrt{NKT} + NK)$, which is a significant improvement over the previous best bound. As shown in the experimental results, the proposed algorithm maintains significantly lower cumulative regret compared to the HMS21 baseline over long time horizons.

Cumulative regret comparison over 500,000 iterations.

This advantage is even more pronounced in larger-scale scenarios, where the gap between the two methods widens as the number of agents and arms increases, proving its effectiveness for complex, multi-user systems.

Cumulative regret comparison in a larger-scale setting showing significant performance gains.

Faster Runtimes

In the "Large" test case (80 agents, 8 arms), Algorithm 1 was nearly 8 times faster than the previous state-of-the-art (1,862 seconds vs. 14,128 seconds). The log-concavity of the objective allows the algorithm to find the optimal fair policy quickly and reliably using gradient ascent.

Limitations and Future Work

  • Initial Lag: As noted in the experiments, the algorithm can be outperformed by simpler methods in the very early stages (under 10,000 iterations) because its confidence bounds start very conservatively. This "learning phase" occurs because initial bounds are wide, leading the algorithm to pull arms almost uniformly until enough data is gathered.
  • Algorithm 2 Practicality: While Algorithm 2 has a better theoretical dependence on $T$, its "start-up cost" and non-convex nature make it perform poorly in practice.
  • Real-World Data: The study relies on synthetic Bernoulli rewards. Testing these algorithms on real-world datasets (like recommendation logs or clinical trial data) remains an open area for exploration.

Summary updated

BibTeX
@inproceedings{jones2023efficient,
  author = {Matthew Jones and Huy Le Nguyen and Thy D. Nguyen},
  title = {{An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=pKpf5U9MNw},
}
Figure