多智能体在线优化中，实现接近最优的累积收益，且采样违规可忽略。
Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
- 设计统一算法框架，支持完整反馈与仅知收益的带通反馈。
- 理论证明算法累积遗憾为次线性，逼近最优值(1-1/e)。
- 提出受限随机管道取样法，采样违规概率随时间趋近于零。
我们研究在分区拟阵约束下的分布式在线子模最大化问题，多个智能体从各自子集中按序选择有限动作，以最大化一系列目标函数的累积价值。本文提出统一的算法框架，适用于完整信息与带通反馈模型。对于两种反馈情形，均证明所提算法实现次线性(1-1/e)-遗憾，与现有中心化方法相当。针对连续松弛与取样过程引发的采样违规问题，提出有界随机管道取样方案，证明采样违规概率渐近趋于零。结果表明，累积采样违规保持次线性，在特定条件下不可改进。数值实验验证了理论结论。
原文摘要 · Abstract (English)
We study distributed online submodular maximization under partition matroid constraints, in which multiple agents select a limited number of actions from their own subsets sequentially to maximize the cumulative value of a sequence of objective functions. We develop a unified algorithmic framework that accommodates full-information and bandit feedback models. For both feedback models, we prove that the proposed algorithms achieve sublinear $(1-1/e)$-regret guarantees, which are comparable to those achieved by existing centralized counterparts. Furthermore, to tackle the sampling violation issue caused by continuous relaxation and rounding, we develop a bounded stochastic pipage rounding scheme and show that the probability of sampling violation vanishes asymptotically. As a result, the cumulative sampling violation remains sublinear in $T$, which is further shown to be not improvable under certain conditions. Numerical results validate the theoretical findings in this paper.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。