MB-AIM-FSI: a model based framework for exploiting gradient ascent multiagent learners in strategic interactions

ABSTRACT

Future agent applications will increasingly represent human users autonomously or semi-autonomously in strategic interactions with similar entities. Hence, there is a growing need to develop algorithmic approaches that can learn to recognize commonalities in opponent strategies and exploit such commonalities to improve strategic response. Recently a framework [9] has been proposed that aims for targeted optimality against a set of finite memory opponents. We propose an approach that aims for targeted optimality against the set of all possible multiagent learning algorithms that perform gradient search to select a single stage Nash Equilibria of a repeated game. Such opponents induce a Markov Decision Process as the learning environment and appropriate responses to such environments are learned by assuming a generative model of the environment. In the absence of a generative model, we present a framework, MB-AIM-FSI, that models the opponent online based on interactions, solves the model off-line when sufficient information has been gathered, stores the strategy in the repository and finally uses it judiciously when playing against the same or similar opponent at a later time.

REFERENCES

• 1: Bikramjit Banerjee , Jing Peng, RV_σ(t): a unifying approach to performance and convergence in online multiagent learning, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160775]
• 2: M. Bowling. Convergence and no-regret in multiagent learning. In Neural Information Processing Systems 17. MIT Press, 2005.
• 3: Michael H. Bowling , Manuela M. Veloso, Convergence of Gradient Dynamics with a Variable Learning Rate, Proceedings of the Eighteenth International Conference on Machine Learning, p.27-34, June 28-July 01, 2001
• 4: M. H. Bowling and M. M. Veloso. Rational and convergent learning in stochastic games. In IJCAI, pages 1021--1026, 2001.
• 5: S. J. Brams. Theory of Moves. Cambridge University Press, Cambridge: UK, 1994.
• 6: Y. Chang and L. Kaelbling. Playing is believing: the role of beliefs in multi-agent learning. In NIPS-2001, 2001.
• 7: V. Conitzer and T. Sandholm. Awesome: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents. pages 83--90, 2003.
• 8: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 9: R. Powers and Y. Shoham. Learning against opponents with bounded memory. In IJCAI, pages 817--822, 2005.
• 10: S. Singh, M. Kearns, and Y. Mansour. Nash convergence of gradient dynamics in general-sum games. pages 541--548.
• 11: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 12: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Performance

Keywords:
multiagent learning, strategic interactions