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.
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