Research map / Bandits and online learning / Multi-armed bandits
Federated Combinatorial Multi-Agent Multi-Armed Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
placeholder
Problem
Online stochastic combinatorial optimization with bandit (full-bandit) feedback in a multi-agent federated setting, where prior offline-to-online methods incur linear regret or retain an epsilon approximation error.
Approach
Treat an offline resilient approximation algorithm as a black box run on the server; each queried action is explored by all agents for repeated plays, with m randomly selected agents sending averaged reward estimates, and the epsilon trade-off parameter and exploration length are set in closed form from T, m, and the subroutine complexity so the regret is measured against alpha f(S*) rather than (
Key results
- Theoretical alpha-regret bound of O~(m^{-1/(3+beta)} psi^{1/(3+beta)} T^{(2+beta)/(3+beta)}) for any resilient (alpha-epsilon)-approximation subroutine, eliminating the epsilon error.
- For monotone cardinality-constrained submodular maximization with Stochastic-Greedy, the framework achieves sublinear (1-1/e)-regret of O~(m^{-1/3} k^{2/3} n^{1/3} T^{2/3}), recovering the single-agent result.
- Empirically on CIFAR10 summarization, C-MA-MAB outperforms C-ETC-N and UCB1 even with a single agent, and regret decreases as the number of agents increases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adapt a resilient offline approximation algorithm in the C-MA-MAB framework | Online combinatorial stochastic optimization with bandit feedback · General combinatorial problems | alpha-regret | Helped |
| Increase the number of communicating agents | C-MA-MAB · General combinatorial problems | alpha-regret | Helped |
| Use C-MA-MAB with Stochastic-Greedy instead of C-ETC-N or UCB1 | Stochastic data summarization · CIFAR10 | cumulative regret | Helped |
| Increase the number of agents | C-MA-MAB with Stochastic-Greedy · Stochastic data summarization | cumulative regret | Helped |
| Use Stochastic-Greedy's sub-optimal offline approximation in the framework | C-MA-MAB · Monotone submodular maximization with cardinality constraint | (1-1/e)-regret | Helped |
Surprising findings
- Using a suboptimal (1-1/e-epsilon) subroutine does not imply higher regret than using an optimal-factor algorithm when measured against the alpha-regret with alpha=1-1/e.
Limitations
- No lower bound is provided for general combinatorial stochastic bandits under bandit feedback.
- Assumes synchronized communication and that the server coordinates action selection; asynchronous communication is left open.
- Requires resilience of the offline algorithm and a problem-dependent delta function for each subroutine.
Experimental setup
Datasets: FMNIST CIFAR10
Benchmarks: CIFAR10 stochastic data summarization FMNIST stochastic data summarization
Metrics: cumulative alpha-regret
Baselines: C-ETC-N UCB1
Builds on: C-ETC Stochastic-Greedy RandomizedUSM UCB1
Closest papers by meaning
- Federated Multi-armed Bandits with Efficient Bit-Level Communications (NeurIPS 2025 · similarity 0.91)
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.90)
- Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users (AAAI 2024 · similarity 0.89)
- Federated X-armed Bandit (AAAI 2024 · similarity 0.88)
- Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.88)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.