Opponent Modeling in a Multi-agent System

David Carmel and Shaul Markovitch
Computer Science Department
Technion, Haifa	32000
Israel
Email: {carmel|shaulm}@cs.technion.ac.il

Abstract

Agents that operate in a multi-agent system need an efficient
strategy to handle their encounters with other agents involved in
that system.  Searching for an optimal interactive strategy is a
hard problem because it depends mostly on the behavior of the
others.  In this work, interaction among agents is represented as
a repeated two-player game, where an agents' objective is to look
for a strategy that maximizes their expected sum of rewards in the
game.  We assume that agents' strategies can be modeled as finite
automata.  A {\em model based reasoning} approach is presented as
a possible method for learning an efficient interactive strategy.
First, we describe how an agent should find an optimal strategy
against a given model. Second, we present a heuristic algorithm
that infers a model of the opponent's automata from its
input/output behavior.  A set of experiments that show the
potential merit of the algorithm is reported as well.