Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games

Large-scale systems where agents interact competitively with each other have received significant attention recently, motivated by applications in power systems (Shi et al., 2022), EV charging (Lee et al., 2022), and board games (Silver et al., 2017), etc. Controlling such systems can be challenging due to the scale of the system, uncertainty about the model, communication constraints, and the interaction between agents. Inspired by the recent success of reinforcement learning (RL), there is an increasing interest in applying RL methods to environments with multi-agent interactions. However, in multi-agent RL (MARL), the analysis of the system behavior becomes challenging due to the time-varying nature of the environment faced by each agent, which results from the (time-varying) competitive decisions of other agents. As a result, the theoretical analysis of MARL, especially in the competitive setting, is still limited, especially when it comes to large-scale systems. The results of MARL in competitive settings to this point have tended to focus on games with a small number of players, e.g., 2-player zero-sum stochastic games (Littman, 1994), or games with special structure, e.g., Markov potential games (MPGs) (Fox et al., 2022). MPGs in particular provide a setting in which the challenges of large-scale systems can be studied.