Authors
Giorgia Ramponi, Marcello Restelli
Abstract
Many learning problems involve multiple agents that optimize different interactive functions. In these problems, standard policy gradient algorithms fail due to the nonstationarity of the setting and the different interests of each agent. In fact, the learning algorithms must consider the complex dynamics of these systems to guarantee rapid convergence towards a (local) Nash equilibrium. In this paper, we propose NOHD (Newton Optimization on Helmholtz Decomposition), a Newton-like algorithm for multi-agent learning problems based on the decomposition of the system dynamics into its irrotational (Potential) and solenoidal (Hamiltonian) components. This method ensures quadratic convergence in purely irrotational systems and pure solenoidal systems. Furthermore, we show that NOHD is attracted to stable fixed points in general multi-agent systems and repelled by strict saddle ones. Finally, we empirically compare the NOHD’s performance with state-of-the-art algorithms on some bimatrix games and in a continuous Gridworld environment.
Full paper