Federated Combinatorial Multi-Agent Multi-Armed Bandits
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911871701876736 |
|---|---|
| author | Fourati, Fares Alouini, Mohamed-Slim Aggarwal, Vaneet |
| author_facet | Fourati, Fares Alouini, Mohamed-Slim Aggarwal, Vaneet |
| contents | 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 $(α-ε)$-approximation algorithm, having a complexity of $\tilde{\mathcal{O}}(\fracψ{ε^β})$, where the logarithm is omitted, for some function $ψ$ and constant $β$, into an online multi-agent algorithm with $m$ communicating agents and an $α$-regret of no more than $\tilde{\mathcal{O}}(m^{-\frac{1}{3+β}} ψ^\frac{1}{3+β} T^\frac{2+β}{3+β})$. This approach not only eliminates the $ε$ 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(ψT^\fracβ{β+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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05950 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Federated Combinatorial Multi-Agent Multi-Armed Bandits Fourati, Fares Alouini, Mohamed-Slim Aggarwal, Vaneet Machine Learning Artificial Intelligence Discrete Mathematics Multiagent Systems 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 $(α-ε)$-approximation algorithm, having a complexity of $\tilde{\mathcal{O}}(\fracψ{ε^β})$, where the logarithm is omitted, for some function $ψ$ and constant $β$, into an online multi-agent algorithm with $m$ communicating agents and an $α$-regret of no more than $\tilde{\mathcal{O}}(m^{-\frac{1}{3+β}} ψ^\frac{1}{3+β} T^\frac{2+β}{3+β})$. This approach not only eliminates the $ε$ 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(ψT^\fracβ{β+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. |
| title | Federated Combinatorial Multi-Agent Multi-Armed Bandits |
| topic | Machine Learning Artificial Intelligence Discrete Mathematics Multiagent Systems |
| url | https://arxiv.org/abs/2405.05950 |