Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games
This addresses the problem of decentralized learning in multi-agent systems for researchers, offering a novel theoretical framework with practical convergence guarantees, though it is incremental in leveraging symmetry for specific game types.
The paper tackles the challenge of designing independent multi-agent reinforcement learners that converge to equilibrium without observing other agents' actions, by introducing satisficing dynamics and proving structural results for existence of paths to equilibrium in symmetric and two-player stochastic games, with an algorithm achieving high-probability convergence to ε-equilibrium in symmetric games.
In multi-agent reinforcement learning (MARL), independent learners are those that do not observe the actions of other agents in the system. Due to the decentralization of information, it is challenging to design independent learners that drive play to equilibrium. This paper investigates the feasibility of using satisficing dynamics to guide independent learners to approximate equilibrium in stochastic games. For $ε\geq 0$, an $ε$-satisficing policy update rule is any rule that instructs the agent to not change its policy when it is $ε$-best-responding to the policies of the remaining players; $ε$-satisficing paths are defined to be sequences of joint policies obtained when each agent uses some $ε$-satisficing policy update rule to select its next policy. We establish structural results on the existence of $ε$-satisficing paths into $ε$-equilibrium in both symmetric $N$-player games and general stochastic games with two players. We then present an independent learning algorithm for $N$-player symmetric games and give high probability guarantees of convergence to $ε$-equilibrium under self-play. This guarantee is made using symmetry alone, leveraging the previously unexploited structure of $ε$-satisficing paths.