AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents Export

@article{citeulike:490032, abstract = {A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action repeated games--assuming that the opponent's (mixed) strategy is observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have these two properties in {\em all} repeated (finite) games. It requires only that the other players' actual actions (not their strategies) can be observed at each step. It also learns to play optimally against opponents that {\em eventually become} stationary. The basic idea behind AWESOME ({\em Adapt When Everybody is Stationary, Otherwise Move to Equilibrium}) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing other multiagent learning algorithms also.}, archivePrefix = {arXiv}, author = {Conitzer, V. and Sandholm, T.}, citeulike-article-id = {490032}, citeulike-linkout-0 = {http://arxiv.org/abs/cs/0307002}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs/0307002}, citeulike-linkout-2 = {http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2003cs........7002C}, eprint = {cs/0307002}, journal = {ArXiv Computer Science e-prints}, keywords = {agents, games, learning}, month = {July}, posted-at = {2006-02-02 23:57:33}, priority = {0}, title = {AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents}, url = {http://arxiv.org/abs/cs/0307002}, year = {2003} }

TY - JOUR ID - citeulike:490032 L3 - citeulike-article-id:490032 N2 - A satisfactory multiagent learning algorithm should, {\em at a minimum}, learn to play optimally against stationary opponents and converge to a Nash equilibrium in self-play. The algorithm that has come closest, WoLF-IGA, has been proven to have these two properties in 2-player 2-action repeated games--assuming that the opponent's (mixed) strategy is observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have these two properties in {\em all} repeated (finite) games. It requires only that the other players' actual actions (not their strategies) can be observed at each step. It also learns to play optimally against opponents that {\em eventually become} stationary. The basic idea behind AWESOME ({\em Adapt When Everybody is Stationary, Otherwise Move to Equilibrium}) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium strategy. The techniques used to prove the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing other multiagent learning algorithms also. JF - ArXiv Computer Science e-prints TI - AWESOME: A General Multiagent Learning Algorithm that Converges in Self-Play and Learns a Best Response Against Stationary Opponents KW - agents KW - games KW - learning AU - Conitzer, V AU - Sandholm, T PY - 2003/July// UR - http://arxiv.org/abs/cs/0307002 ER -