Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning
This addresses scalability and efficiency issues in cooperative multi-agent systems, representing an incremental improvement over existing methods by introducing localized constraints.
The paper tackles the curse of dimensionality and communication overhead in networked multi-agent reinforcement learning by proposing a Localized Policy Iteration algorithm that learns near-globally-optimal policies using only local information, with an optimality gap decaying polynomially in the neighborhood size κ and finite-sample convergence to the global optimum.
We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its $κ$-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in $κ$. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing $κ$. Numerical simulations demonstrate the effectiveness of LPI.