多智能体联合分配下，用探索-承诺策略实现近似最优福利。
Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
- 设计多智能体组合赌博框架，通过随机分配探索资源
- 达到T^{2/3}量级的遗憾，优于1-1/e基准
- 适用于无通信、共享约束的多智能体资源分配场景
我们研究带赌博反馈的子模福利问题（SWP），其中物品需在多个具有单调子模效用的代理间分配，以最大化总福利。经典方法假设全价值查询访问，可通过连续贪心算法实现(1-1/e)近似。本文扩展至多智能体组合赌博框架（MA-CMAB），动作是完整分配，采用全赌博反馈且代理间不通信。与以往单代理或可分离多代理模型不同，本设定中代理通过共享分配约束耦合。提出一种探索-然后承诺策略，结合随机分配，实现了对(1-1/e)基准的 ilde{ ext{O}}(T^{2/3})遗憾，是首个针对基于分配的子模福利问题在赌博反馈下的此类保证。
原文摘要 · Abstract (English)
We study the \emph{Submodular Welfare Problem} (SWP), where items are partitioned among agents with monotone submodular utilities to maximize the total welfare under \emph{bandit feedback}. Classical SWP assumes full value-oracle access, achieving $(1-1/e)$ approximations via continuous-greedy algorithms. We extend this to a \emph{multi-agent combinatorial bandit} framework (\textsc{MA-CMAB}), where actions are partitions under full-bandit feedback with non-communicating agents. Unlike prior single-agent or separable multi-agent CMAB models, our setting couples agents through shared allocation constraints. We propose an explore-then-commit strategy with randomized assignments, achieving $\tilde{\mathcal{O}}(T^{2/3})$ regret against a $(1-1/e)$ benchmark, the first such guarantee for partition-based submodular welfare problem under bandit feedback.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。