Learning Stationary Nash Equilibrium Policies in $n$-Player Stochastic Games with Independent Chains
This addresses the challenge of decentralized learning in multi-agent systems with private information, offering incremental algorithmic improvements for applications like smart grids.
The paper tackles the problem of finding stationary Nash equilibrium policies in n-player stochastic games with independent chains and limited information, showing it is intractable in general but developing polynomial-time learning algorithms that converge to ε-NE policies, with numerical experiments in smart grid energy management demonstrating effectiveness.
We consider a subclass of $n$-player stochastic games, in which players have their own internal state/action spaces while they are coupled through their payoff functions. It is assumed that players' internal chains are driven by independent transition probabilities. Moreover, players can receive only realizations of their payoffs, not the actual functions, and cannot observe each other's states/actions. For this class of games, we first show that finding a stationary Nash equilibrium (NE) policy without any assumption on the reward functions is interactable. However, for general reward functions, we develop polynomial-time learning algorithms based on dual averaging and dual mirror descent, which converge in terms of the averaged Nikaido-Isoda distance to the set of $ε$-NE policies almost surely or in expectation. In particular, under extra assumptions on the reward functions such as social concavity, we derive polynomial upper bounds on the number of iterates to achieve an $ε$-NE policy with high probability. Finally, we evaluate the effectiveness of the proposed algorithms in learning $ε$-NE policies using numerical experiments for energy management in smart grids.