Model-based Learning of Interaction Strategies in Multi-Agent Systems

David Carmel and Shaul Markovitch. Model-based Learning of Interaction Strategies in Multi-Agent Systems. Journal of Experimental and Theoretical Artificial Intelligence, 10:309-332, 1998.

Abstract

Agents that operate in a multi-agent system need an efficient strategy to handle their encounters with other agents involved. Searching for an optimal interaction strategy is a hard problem because it depends mostly on the behavior of the others. One way to deal with this problem is to endow the agents with the ability to adapt their strategies based on their interaction experience. This work views interaction as a repeated game and presents a general architecture for a model-based agent that learns models of the rival agents for exploitation in future encounters. First, we describe a method for inferring an optimal strategy against a given model of another agent. Second, we present an unsupervised algorithm that infers a model of the opponent's strategy from its interaction behavior in the past. We then present a method for incorporating exploration strategies into model-based learning. We report experimental results demonstrating the superiority of the model-based learning agent over non-adaptive agents and over reinforcement-learning agents.

Keywords: Opponent Modeling, Multi-Agent Systems, Learning in Games

Secondary Keywords: Repeated Games, Learning DFA

Online version:

Bibtex entry:

 

@article{Carmel:1998:MBL,
  Author =      {David Carmel and Shaul Markovitch},
  Title =       {Model-based Learning of Interaction Strategies in Multi-Agent Systems},
  Year =        {1998},
  Journal =     {Journal of Experimental and Theoretical Artificial Intelligence},
  Volume =      {10},
  Number =      {3},
  Pages =       {309--332},
  Keywords =    {Opponent Modeling, Multi-Agent Systems, Learning in Games},
  Secondary-keywords =  {Repeated Games, Learning DFA},
  Url =         {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Carmel-Markovitch-jetai1998.pdf},
  Abstract =    {Agents that operate in a multi-agent system need an efficient strategy to handle
             their encounters with other agents involved. Searching for an optimal
             interaction strategy is a hard problem because it depends mostly on the
             behavior of the others. One way to deal with this problem is to endow the
             agents with the ability to adapt their strategies based on their interaction
             experience. This work views interaction as a repeated game and presents a
             general architecture for a model-based agent that learns models of the rival
             agents for exploitation in future encounters. First, we describe a method for
             inferring an optimal strategy against a given model of another agent. Second,
             we present an unsupervised algorithm that infers a model of the opponent's
             strategy from its interaction behavior in the past. We then present a method
             for incorporating exploration strategies into model-based learning. We report
             experimental results demonstrating the superiority of the model-based learning
             agent over non-adaptive agents and over reinforcement-learning agents.}
}