Technical Report CIS9713

Title: Exploration Strategies for Model-based Learning in Multi-agent Systems
Authors: David Carmel and Shaul Markovitch
Abstract: An agent that interacts with other agents in {\em multi-agent systems} can benefit significantly from adapting to the others. When performing active learning, every agent's action affects the interaction process in two ways: The effect on the expected reward according to the current knowledge held by the agent, and the effect on the acquired knowledge, and hence, on future rewards expected to be received. The agent must therefore make a tradeoff between the wish to exploit its current knowledge, and the wish to explore other alternatives, to improve its knowledge for better decisions in the future. The goal of this work is to develop exploration strategies for a model-based learning agent to handle its encounters with other agents in the common environment. We first show how to incorporate exploration methods usually used in reinforcement learning into model-based learning. We then demonstrate the risk involved in exploration -- an exploratory action taken by the agent can yield a better model of the other agent but also carries the risk of putting the agent into a much worse position. We present the {\em lookahead-based exploration strategy} that evaluates actions according to their expected utility, their expected contribution to the acquired knowledge, and the risk they carry. Instead of holding one model, the agent maintains a {\em mixed opponent model}, a distribution over a set of models that reflects its uncertainty about the opponent's strategy. Every action is evaluated according to its long run contribution to the expected utility and to the knowledge regarding the opponent's strategy. Risky actions are detected by considering their expected outcome according to the alternative models of the opponent's behavior. We present an efficient algorithm that returns an {\em almost optimal} exploration plan against the mixed model and provide a proof of its correctness and an analysis of its complexity. We report experimental results in the {\em Iterated Prisoner's Dilemma} domain, comparing the capabilities of the different exploration strategies. The experiments demonstrate the superiority of lookahead-based exploration over other exploration methods.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion