Decentralized model-free reinforcement learning in stochastic games with average-reward objective
This addresses the problem of efficient decentralized learning for agents in competitive environments, representing a novel advancement in game theory and reinforcement learning.
The paper tackles decentralized model-free reinforcement learning in two-player zero-sum stochastic games with an average-reward objective, proposing the DONQ-learning algorithm that achieves sublinear high-probability regret of order T^{3/4} and expected regret of order T^{2/3}.
We propose the first model-free algorithm that achieves low regret performance for decentralized learning in two-player zero-sum tabular stochastic games with infinite-horizon average-reward objective. In decentralized learning, the learning agent controls only one player and tries to achieve low regret performances against an arbitrary opponent. This contrasts with centralized learning where the agent tries to approximate the Nash equilibrium by controlling both players. In our infinite-horizon undiscounted setting, additional structure assumptions is needed to provide good behaviors of learning processes : here we assume for every strategy of the opponent, the agent has a way to go from any state to any other. This assumption is the analogous to the "communicating" assumption in the MDP setting. We show that our Decentralized Optimistic Nash Q-Learning (DONQ-learning) algorithm achieves both sublinear high probability regret of order $T^{3/4}$ and sublinear expected regret of order $T^{2/3}$. Moreover, our algorithm enjoys a low computational complexity and low memory space requirement compared to the previous works of (Wei et al. 2017) and (Jafarnia-Jahromi et al. 2021) in the same setting.