解决协作多智能体强化学习中收益递减的难题，提升团队效率。
Multi-Agent Reinforcement Learning with Submodular Reward
- 基于贪婪策略优化，实现多项式复杂度下的近似最优解。
- 已知环境动态下，达到1/2近似比，克服维度爆炸问题。
- 适合多无人机巡检、协同探索等实际协作场景研究者参考。
本文研究具有子模奖励的协作多智能体强化学习（MARL）问题，该奖励特性自然刻画了添加智能体时边际贡献递减的现象。与传统可加奖励不同，子模奖励能更真实地建模智能体间存在重叠贡献的场景（如多无人机监控、协同探索）。我们首次建立了该设置的正式框架，并提出了具有样本效率和后悔界保证的算法。对于已知系统动态的情况，所提贪婪策略优化方法在智能体数量 $K$ 的多项式时间内实现 $1/2$-近似解，突破联合策略优化固有的指数级维度灾难。对于未知动态情形，提出基于UCB的算法，在 $T$ 轮内实现 $1/2$-后悔上界为 $O(H^2KS oot{AT})$。
原文摘要 · Abstract (English)
In this paper, we study cooperative multi-agent reinforcement learning (MARL) where the joint reward exhibits submodularity, which is a natural property capturing diminishing marginal returns when adding agents to a team. Unlike standard MARL with additive rewards, submodular rewards model realistic scenarios where agent contributions overlap (e.g., multi-drone surveillance, collaborative exploration). We provide the first formal framework for this setting and develop algorithms with provable guarantees on sample efficiency and regret bound. For known dynamics, our greedy policy optimization achieves a $1/2$-approximation with polynomial complexity in the number of agents $K$, overcoming the exponential curse of dimensionality inherent in joint policy optimization. For unknown dynamics, we propose a UCB-based learning algorithm achieving a $1/2$-regret of $O(H^2KS\sqrt{AT})$ over $T$ episodes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。