Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards

📄 arXiv: 2611.04774v1 📥 PDF

作者: Yasaman Zolfimoselo, Nikolas Geroliminis, Maryam Kamgarpour

分类: cs.LG, cs.MA

发布日期: 2026-11-03

💡 一句话要点

提出一种新算法以优化多智能体强化学习中的轨迹奖励问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 多智能体系统 强化学习 轨迹奖励 贪婪算法 交通监控 优化算法

📋 核心要点

  1. 现有方法在处理非加性奖励时，最优策略依赖于所有智能体的历史，导致优化复杂度指数级增长。
  2. 论文提出通过引入预窗口曲率$c_m$来控制策略的历史依赖性，从而设计出贪婪算法以优化局部策略。
  3. 实验结果表明，该算法在多智能体交通监控中表现出色，达到了$ rac{1-c_m}{2-c_m}$的近似保证，计算效率高。

📝 摘要（中文）

我们研究了具有解耦动态和单调子模奖励函数的合作多智能体强化学习。由于奖励的非加性，最优策略可能依赖于所有智能体的历史，这使得精确优化在时间和智能体数量上呈指数级增长。为了解决这一挑战，我们引入了预窗口曲率$c_m$，量化了早于$m$步访问的状态如何降低当前的边际收益。通过控制每个智能体的策略仅依赖于其最后$m+1$个状态的限制误差，我们提出了一种贪婪算法，利用解耦动态顺序优化局部策略。对于固定的$m$，该算法在估计误差下实现了$ rac{1-c_m}{2-c_m}$的近似保证，计算时间在智能体数量和时间范围内是多项式的。我们将多智能体交通监控作为该框架的一个例子，并对其进行了评估。

🔬 方法详解

问题定义：本论文旨在解决合作多智能体强化学习中的轨迹奖励优化问题。现有方法由于奖励的非加性，导致最优策略依赖于所有智能体的历史，优化过程复杂且计算量大。

核心思路：论文的核心思路是引入预窗口曲率$c_m$，量化早期状态对当前边际收益的影响，从而允许每个智能体的策略仅依赖于其最近的$m+1$个状态，降低了优化的复杂性。

技术框架：整体架构包括状态访问的历史管理、曲率计算、局部策略优化和贪婪算法实现。算法通过顺序优化局部策略，利用解耦动态特性来提高效率。

关键创新：最重要的技术创新在于引入了预窗口曲率$c_m$，这使得算法能够在保持理论保证的同时，显著降低计算复杂度。与现有方法相比，该方法在处理非加性奖励时具有更好的适应性和效率。

关键设计：算法的关键设计包括固定的$m$值选择、曲率的计算方法以及贪婪策略的实现。通过这些设计，算法在多智能体环境中能够有效地优化局部策略，且计算时间保持在多项式级别。

📊 实验亮点

实验结果显示，该算法在多智能体交通监控任务中达到了$ rac{1-c_m}{2-c_m}$的近似保证，计算时间在智能体数量和时间范围内为多项式级别，相较于传统方法显著提升了效率和可扩展性。

🎯 应用场景

该研究的潜在应用领域包括多智能体系统中的交通监控、无人驾驶车辆协调、智能物流等。通过优化多智能体的决策过程，可以显著提高系统的整体效率和安全性，具有重要的实际价值和未来影响。

📄 摘要（原文）

We study cooperative multi-agent reinforcement learning with decoupled dynamics and a monotone submodular reward function over joint trajectories. Due to the non-additive reward, an optimal policy may depend on the history of all agents. This dependence makes exact optimization exponential in the horizon and the number of agents. To overcome this challenge while retaining theoretical guarantees, we introduce pre-window curvature $c_m$, which quantifies how states visited more than $m$ steps earlier reduce current marginal gains. Using this curvature to control the error from restricting the policy of each agent to depend only on its last $m+1$ states, we propose a greedy algorithm that exploits the decoupled dynamics to optimize local policies sequentially. For fixed $m$, the algorithm achieves a $\frac{1-c_m}{2-c_m}$ approximation guarantee up to estimation error, and its computation time is polynomial in the number of agents and the horizon. We recover the known $1/2$-factor approximation for time-additive rewards and obtain an approximation factor no smaller than the known total-curvature bound for a single agent. We formulate multi-agent traffic monitoring as an example of this framework and evaluate our algorithm on it.