Federated Combinatorial Multi-Agent Multi-Armed Bandits

📄 arXiv: 2405.05950v1 📥 PDF

作者: Fares Fourati, Mohamed-Slim Alouini, Vaneet Aggarwal

分类: cs.LG, cs.AI, cs.DM, cs.MA, stat.ML

发布日期: 2024-05-09

💡 一句话要点

提出联邦组合多智能体多臂赌博机框架以优化在线决策问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 联邦学习 组合优化 多智能体系统 多臂赌博机 在线学习 随机最大化 信息共享

📋 核心要点

  1. 现有的多臂赌博机算法在多智能体环境中面临信息共享和通信效率的挑战，难以实现有效的在线组合优化。
  2. 论文提出的框架通过将离线算法转化为在线多智能体算法，消除了近似误差，并实现了时间范围内的亚线性增长。
  3. 实验结果表明，该框架在随机数据摘要问题上表现优异，验证了其在单智能体和多智能体场景中的有效性。

📝 摘要（中文）

本文提出了一种针对在线组合优化的联邦学习框架，利用赌博反馈进行决策。在该框架中，智能体选择臂的子集，观察这些子集的噪声奖励，而不访问单个臂的信息，并可以在特定时间间隔内进行合作和信息共享。该框架将任何离线的单智能体$(α-ε)$-近似算法转化为在线多智能体算法，具有良好的后悔界限和通信效率。通过应用于在线随机子模块最大化，本文展示了该框架的有效性，尤其是在单智能体场景中。

🔬 方法详解

问题定义：本文旨在解决多智能体环境中在线组合优化的问题，现有方法在信息共享和通信效率上存在不足，难以适应动态决策场景。

核心思路：提出的框架通过将离线的单智能体$(α-ε)$-近似算法转化为在线多智能体算法，允许智能体在特定时间间隔内共享信息，从而提高决策效率。

技术框架：整体架构包括智能体选择臂的子集、观察噪声奖励、信息共享和合作等模块，确保在多智能体环境中进行有效的在线优化。

关键创新：最重要的创新在于消除了近似误差，并确保了后悔界限的亚线性增长，尤其是在通信效率方面，显著减少了所需的通信轮次。

关键设计：关键参数设置包括复杂度$ ilde{ ext{O}}( racψ{ε^β})$和通信轮次$ ilde{ ext{O}}ig(ψT^ racβ{β+1}ig)$，确保算法在多智能体环境中高效运行。

📊 实验亮点

实验结果显示，提出的框架在随机数据摘要问题上取得了显著的性能提升，后悔界限达到$ ilde{ ext{O}}(m^{- rac{1}{3+β}} ψ^ rac{1}{3+β} T^ rac{2+β}{3+β})$，并且通信轮次仅为$ ilde{ ext{O}}ig(ψT^ racβ{β+1}ig)$，展现了良好的通信效率。

🎯 应用场景

该研究的潜在应用领域包括在线广告投放、推荐系统和资源分配等场景，能够在多智能体环境中实现高效的决策优化，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

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.