$K$-Level Policy Gradients for Multi-Agent Reinforcement Learning
This addresses coordination challenges in multi-agent systems, offering a novel approach with proven theoretical convergence and empirical gains, though it builds incrementally on existing actor-critic frameworks.
The paper tackles the problem of miscoordination in multi-agent reinforcement learning by introducing the K-Level Policy Gradient (KPG) method, which recursively updates policies to account for other agents' updates, resulting in superior performance in StarCraft II and multi-agent MuJoCo benchmarks.
Actor-critic algorithms for deep multi-agent reinforcement learning (MARL) typically employ a policy update that responds to the current strategies of other agents. While being straightforward, this approach does not account for the updates of other agents at the same update step, resulting in miscoordination. In this paper, we introduce the $K$-Level Policy Gradient (KPG), a method that recursively updates each agent against the updated policies of other agents, speeding up the discovery of effective coordinated policies. We theoretically prove that KPG with finite iterates achieves monotonic convergence to a local Nash equilibrium under certain conditions. We provide principled implementations of KPG by applying it to the deep MARL algorithms MAPPO, MADDPG, and FACMAC. Empirically, we demonstrate superior performance over existing deep MARL algorithms in StarCraft II and multi-agent MuJoCo.