Part of Advances in Neural Information Processing Systems 14 (NIPS 2001)
Yu-Han Chang, Leslie Pack Kaelbling
We propose a new classiﬁcation for multi-agent learning algorithms, with each league of players characterized by both their possible strategies and possible beliefs. Using this classiﬁcation, we review the optimality of ex- isting algorithms, including the case of interleague play. We propose an incremental improvement to the existing algorithms that seems to achieve average payoffs that are at least the Nash equilibrium payoffs in the long- run against fair opponents.