Nash Q-Learning for General-Sum Stochastic Games

摘要

We extend Q-learning to a noncooperative multiagent context, using theframework of general-sum stochastic games. A learning agent maintainsQ-functions over joint actions, and performs updates based on assumingNash equilibrium behavior over the current Q-values. This learningprotocol provably converges given certain restrictions on the stagegames (defined by Q-values) that arise during learning. Experiments with a pair of two-playergrid games suggest that such restrictions on the game structure arenot necessarily required. Stage games encountered during learning in both grid environments violate the conditions.However, learningconsistently converges in the first grid game, which has a uniqueequilibrium Q-function, but sometimes fails to converge in thesecond, which has three different equilibrium Q-functions.In a comparison of offline learning performance inboth games, we find agents are more likely to reach a joint optimalpath with Nash Q-learning than with a single-agent Q-learningmethod. When at least one agent adopts Nash Q-learning,the performance of both agents is better than using single-agentQ-learning. We have also implemented an online version of NashQ-learning that balances exploration with exploitation,yielding improved performance. color="gray">