JMLR: Nash Q-Learning for General-Sum Stochastic Games

[[Redistributed from JMLR announce]]

~From: "David 'Pablo' Cohn" <[EMAIL PROTECTED]>
~Date: 21 Nov 2003 08:23:13 -0800
~Subject: jmlr-announce: Nash Q-Learning for General-Sum Stochastic Games

The Journal of Machine Learning Research (www.jmlr.org) is pleased to
announce publication of a new paper:
----------------------------------------------------------------------------

Nash Q-Learning for General-Sum Stochastic Games
Junling Hu and Michael P. Wellman
JMLR 4(Nov):1039-1069, 2003

Abstract

We extend Q-learning to a noncooperative multiagent context, using the
framework of general-sum stochastic games. A learning agent maintains
Q-functions over joint actions, and performs updates based on assuming
Nash equilibrium behavior over the current Q-values. This learning
protocol provably converges given certain restrictions on the stage
games (defined by Q-values) that arise during learning. Experiments with
a pair of two-player grid games suggest that such restrictions on the
game structure are not necessarily required. Stage games encountered
during learning in both grid environments violate the conditions.
However, learning consistently converges in the first grid game, which
has a unique equilibrium Q-function, but sometimes fails to converge in
the second, which has three different equilibrium Q-functions. In a
comparison of offline learning performance in both games, we find agents
are more likely to reach a joint optimal path with Nash Q-learning than
with a single-agent Q-learning method. When at least one agent adopts
Nash Q-learning, the performance of both agents is better than using
single-agent Q-learning. We have also implemented an online version of
Nash Q-learning that balances exploration with exploitation, yielding
improved performance.

----------------------------------------------------------------------------
This paper, and all previous papers in Volume 4 are available
electronically at http://www.jmlr.org in PostScript and PDF formats. The
papers of Volumes 1, 2 and 3 are also available electronically from the
JMLR website, and in hardcopy from the MIT Press; please see
http://mitpress.mit.edu/JMLR for details.

-David Cohn, <[EMAIL PROTECTED]>

[ comp.ai is moderated.  To submit, just post and be patient, or if ]
[ that fails mail your article to <[EMAIL PROTECTED]>, and ]
[ ask your news administrator to fix the problems with your system. ]