Achieving Near-Optimal Individual Regret & Low Communications in Multi-Agent Bandits

Xuchuang Wang, Lin Yang, Yu-Zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, Don Towsley, John C.s. LuiICLR 2023 · OpenReview

Introduction

In the realm of machine learning, Multi-Armed Bandits (MAB) model the classic dilemma of exploration versus exploitation. When multiple agents collaborate to solve the same MAB problem, it is known as Cooperative Multi-Agent MAB (CM2AB). This framework is highly applicable to distributed systems like drone swarms, sensor networks, and multi-server recommendation engines.

Historically, research in CM2AB has focused on maximizing group performance—minimizing the total regret accumulated across all agents. However, in many real-world applications, a system's overall success is dictated by its weakest link. For instance, if a single drone in a swarm learns too slowly and crashes, the entire mission may fail. Therefore, optimizing the performance of the "bottleneck" agent (the one with the highest individual regret) is critical.

The challenge lies in balancing three competing objectives: maximizing group performance, ensuring individual fairness (so no single agent suffers disproportionately), and maintaining communication efficiency. Prior algorithms typically sacrificed individual fairness—such as in "leader-follower" models where the leader bears the brunt of risky exploration—or required prohibitive amounts of communication.

The UCB-TCOM Algorithm

To address these challenges, the authors introduce UCB-TCOM (Upper Confidence Bound with Tunable COMmunication), a novel algorithm designed to achieve near-optimal performance for both the group and the worst-off individual agent, all while drastically reducing communication overhead.

UCB-TCOM relies on two primary innovations:

  1. Communication Arm Set ($C_t(\alpha)$): Instead of broadcasting every observation, agents only share data about arms that are potentially suboptimal. The intuition is straightforward: agents do not need constant reinforcement about a "good" arm they are already exploiting; they benefit most from being warned away from "bad" arms. A tunable parameter, $\alpha$, controls how aggressively the algorithm identifies and communicates these suboptimal arms.
  2. Observation-Buffering Broadcast: To further minimize network chatter, agents do not send updates immediately. Instead, they buffer their observations and only broadcast the average when their local count of pulls for a specific arm increases by a certain ratio, $\beta$. This geometric (or doubling phase) approach significantly spaces out communication events over time.

By forcing all agents to make decisions based solely on shared global information, UCB-TCOM enforces a symmetric learning structure. This naturally equalizes regret across all agents, preventing any single agent from becoming a bottleneck.

Results and Performance

The theoretical and empirical results of UCB-TCOM demonstrate a significant leap forward in multi-agent bandit optimization. The algorithm achieves a near-optimal group regret of $O(\frac{K}{\Delta_2} \log T)$ and an individual regret of $O(\frac{K}{M\Delta_2} \log T)$, where $K$ is the number of arms, $M$ is the number of agents, and $T$ is the number of decision rounds.

Crucially, individual regret scales by $O(1/M)$, demonstrating a clear "power in numbers" benefit: as more agents join the system, the individual burden of exploration decreases.

Comparison of theoretical regret and communication bounds across different multi-agent bandit algorithms.

As shown in the comparison table above, UCB-TCOM matches or improves upon the regret bounds of state-of-the-art baselines like Dec_UCB, GosInE, and DPE2. However, its standout achievement is in communication efficiency. While competitive baselines require $O(\log T)$ or even $O(T)$ communications, UCB-TCOM reduces the time dependence of communication frequency to an astonishing $O(\log(\log T))$. As time $T$ grows, the communication cost becomes almost negligible.

The researchers validated these theoretical bounds using both synthetic simulations (Bernoulli reward distributions) and real-world data from the Kaggle Ad-Clicks (Avito, 2015) dataset. In these empirical tests, UCB-TCOM consistently outperformed baselines in communication efficiency while maintaining competitive regret levels, particularly excelling in individual fairness compared to leader-follower models.

Conclusion and Future Directions

UCB-TCOM proves that in distributed learning, "silence is golden." By strategically ignoring the optimal arm in communications and buffering the rest, systems can achieve near-optimal regret with minimal network strain. The tunable parameters $\alpha$ and $\beta$ also provide engineers with the flexibility to trade off between communication frequency and regret based on specific hardware or network constraints.

While the current work is highly effective for stochastic environments (where rewards follow a fixed distribution), extending this approach to adversarial bandits remains an open challenge. Additionally, future work could explore the bit complexity (size of messages) rather than just the number of communication rounds, potentially integrating adaptive differential communication for even greater efficiency.

Summary updated

Abstract

Cooperative multi-agent multi-armed bandits (CM2AB) study how distributed agents cooperatively play the same multi-armed bandit game. Most existing CM2AB works focused on maximizing the group performance of all agents---the accumulation of all agents' individual performance (i.e., individual reward). However, in many applications, the performance of the system is more sensitive to the ``bad'' agent---the agent with the worst individual performance. For example, in a drone swarm, a ``bad'' agent may crash into other drones and severely degrade the system performance. In that case, the key of the learning algorithm design is to coordinate computational and communicational resources among agents so to optimize the individual learning performance of the ``bad'' agent. In CM2AB, maximizing the group performance is equivalent to minimizing the group regret of all agents, and minimizing the individual performance can be measured by minimizing the maximum (worst) individual regret among agents. Minimizing the maximum individual regret was largely ignored in prior literature, and currently, there is little work on how to minimize this objective with a low communication overhead. In this paper, we propose a near-optimal algorithm on both individual and group regrets, in addition, we also propose a novel communication module in the algorithm, which only needs \(O(\log (\log T))\) communication times where \(T\) is the number of decision rounds. We also conduct simulations to illustrate the advantage of our algorithm by comparing it to other known baselines.
BibTeX
@inproceedings{wang2023achieving,
  author = {Xuchuang Wang and Lin Yang and Yu-Zhen Janice Chen and Xutong Liu and Mohammad Hajiesmaili and Don Towsley and John C.S. Lui},
  title = {{Achieving Near-Optimal Individual Regret \& Low Communications in Multi-Agent Bandits}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=QTXKTXJKIh},
}
Figure