Federated Combinatorial Multi-Agent Multi-Armed Bandits

Fares Fourati, Mohamed-Slim Alouini, Vaneet Aggarwal

Abstract

This paper introduces C-MA-MAB, a federated learning framework that enables multiple agents to collaboratively solve complex combinatorial optimization problems using only limited "bandit" feedback. By transforming offline approximation algorithms into a multi-agent online system, the authors achieve sublinear regret and demonstrate that learning speeds up linearly as more agents join the network.

Introduction

Combinatorial Multi-Armed Bandits (CMAB) represent a significant class of optimization problems where an agent selects a subset of options (arms) rather than a single one. This is particularly relevant in domains like product recommendation and sensor placement. A major hurdle in these settings is "bandit feedback," where only the aggregate reward of the chosen subset is observed, obscuring the individual contributions of each item. Furthermore, many combinatorial problems are NP-hard, necessitating the use of approximation algorithms. Previous online adaptations of these algorithms often suffered from persistent approximation errors that did not vanish over time.

The C-MA-MAB Framework

The proposed C-MA-MAB (Federated Combinatorial Multi-Agent Multi-Armed Bandits) framework addresses these challenges by treating existing offline approximation algorithms as "black boxes." The core innovation lies in the concept of "resilient" approximations—algorithms that maintain performance even when provided with noisy data, which is inherent in the bandit setting.

The framework balances exploration and exploitation by having agents explore subsets suggested by the offline algorithm and share their local reward estimates with a central server. The server aggregates these estimates to refine a global model. A key technical contribution is the dynamic optimization of the error tolerance parameter ($\epsilon$). By decreasing $\epsilon$ as the time horizon $T$ increases, the framework eliminates the persistent approximation error seen in prior literature.

Theoretical Contributions

The authors provide rigorous regret bounds for several classes of combinatorial problems. A standout result is the "linear speedup" property: the collective regret of $m$ agents scales similarly to the regret of a single agent operating for $m$ times the duration. This demonstrates the efficiency of the collaborative learning process.

Table 1: Summary of regret bounds for various offline algorithms adapted via the C-MA-MAB framework. The table highlights the improvement over prior bounds and the inclusion of the agent count $m$ in the regret term.

As shown in Table 1, the framework achieves sublinear $\alpha$-regret for a variety of algorithms, including Greedy for monotone functions and RandomizedUSM for non-monotone ones. The regret typically grows at a rate of $T^{2/3}$, with the $m^{-1/3}$ factor explicitly showing the benefit of multi-agent collaboration.

Experimental Evaluation

The framework was evaluated on a stochastic data summarization task using the CIFAR-10 and Fashion-MNIST (FMNIST) datasets. The objective was to select a representative subset of images, a classic submodular maximization problem. Empirical results confirmed the theoretical findings: C-MA-MAB consistently outperformed standard baselines like UCB1 and C-ETC-N. Furthermore, experiments with varying numbers of agents (from 1 to 32) validated the linear speedup, showing a significant drop in cumulative regret as the network size increased.

Conclusion

C-MA-MAB provides a robust and versatile framework for federated combinatorial learning. By bridging the gap between offline approximation and online multi-agent systems, it offers a scalable solution for complex optimization tasks. Future work will focus on extending the framework to asynchronous communication environments and establishing tighter lower bounds for general combinatorial bandits with bandit feedback.

Summary updated

Abstract

This paper introduces a federated learning framework tailored for online combinatorial optimization with bandit feedback. In this setting, agents select subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals. Our framework transforms any offline resilient single-agent $(\alpha-\epsilon)$-approximation algorithm—having a complexity of $\tilde{\mathcal{O}}\left(\frac{\psi}{\epsilon^\beta}\right)$, where the logarithm is omitted, for some function $\psi$ and constant $\beta$—into an online multi-agent algorithm with $m$ communicating agents and an $\alpha$-regret of no more than $\tilde{\mathcal{O}}\left(m^{-\frac{1}{3+\beta}} \psi^\frac{1}{3+\beta} T^\frac{2+\beta}{3+\beta}\right)$. Our approach not only eliminates the $\epsilon$ approximation error but also ensures sublinear growth with respect to the time horizon $T$ and demonstrates a linear speedup with an increasing number of communicating agents. Additionally, the algorithm is notably communication-efficient, requiring only a sublinear number of communication rounds, quantified as $\tilde{\mathcal{O}}\left(\psi T^\frac{\beta}{\beta+1}\right)$. Furthermore, the framework has been successfully applied to online stochastic submodular maximization using various offline algorithms, yielding the first results for both single-agent and multi-agent settings and recovering specialized single-agent theoretical guarantees. We empirically validate our approach to a stochastic data summarization problem, illustrating the effectiveness of the proposed framework, even in single-agent scenarios.
BibTeX
@inproceedings{fourati2024federated,
  author = {Fares Fourati and Mohamed-Slim Alouini and Vaneet Aggarwal},
  title = {{Federated Combinatorial Multi-Agent Multi-Armed Bandits}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=lrFwPeDdEQ},
}
Figure