Cooperative learning improves agent teamwork with efficient approximations
Cooperative Multi-Agent Reinforcement Learning with Submodular Trajectory Rewards
Machine LearningMultiagent Systems
Summary
Planning how multiple agents should work together can be very complicated because the benefits depend on their entire sequence of actions, not just single steps. The authors study this challenge when the reward is a special kind of function called monotone submodular, which captures diminishing returns over joint trajectories. They propose a new way to approximate the optimal strategies by focusing on recent steps only, controlling the resulting errors through a quantity called pre-window curvature. Their algorithm can efficiently find good strategies with theoretical guarantees and works well in a traffic monitoring task.
What this means in practice
- •For traffic control engineers: Optimize cooperative monitoring strategies for multi-agent traffic sensor networks using efficient trajectory-based policies.
- •For robotics coordination teams: Develop coordinated control policies for robot teams with decoupled dynamics to maximize collective objectives with performance guarantees.
Authors
Yasaman Zolfimoselo, Nikolas Geroliminis, Maryam Kamgarpour
Abstract
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.