多智能体强化学习新论文：次模轨迹奖励下的贪心算法与近似保证
Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards
一篇理论向的多智能体强化学习论文，用 pre-window curvature 把不可加奖励下的策略优化降到多项式时间，还给出近似保证，做 MARL 的可以看看。
arXiv 论文研究解耦动力学下、奖励函数为单调次模函数的协作式多智能体强化学习。由于奖励不可加，最优策略需依赖所有智能体的历史，精确优化复杂度随时域和智能体数量呈指数增长。作者提出 pre-window curvature（c_m）刻画早先状态对当前边际收益的衰减，并据此将每个智能体的策略限制为仅依赖其最近 m+1 个状态。在固定 m 时，贪心算法获得 (1-c_m)/(2-c_m) 的近似保证，计算时间在智能体数量和时域上为多项式级。论文以多智能体交通监控为示例框架，并在此任务上评估了算法。
Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards
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.