Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior.
José M. Vidal, Edmund H. Durfee · Deep Blue (University of Michigan) · 1998
In this thesis, we show how to build agents that learn about agents in Multi-Agent Systems (MASs) composed of learning agents. We give a framework for describing a MAS and its agents, along with their behaviors and the errors in these behaviors. The framework is supplemented with notation that captures the knowledge of agents with recursive models of other agents. Working under the assumption that agents can generate recursive models of other agents, we design an algorithm (LR-RMM) that works by calculating an agent's expected gain in order to tell the agent when it should stop thinking about other agents and take action. We implement LR-RMM and verify its results in the Pursuit Task. We then consider agents that must learn models of other agents via observation. We extend our framework (CLRI) to capture the agents' learning abilities, regardless of the particular machine learning algorithms used by the agents, and the degree to which the agents impact each others' behaviors. CLRI predicts the correctness of the expected behavior of any learning agent in a MAS. Since agents impact each other, an agent's desired behavior might change due to changes in the other agents' behaviors, as caused by their learning. The CLRI framework takes all these changes into account when predicting the correctness of an agent's expected behavior. We confirm the CLRI predictions with experimental results from our research and from the research literature. While determining the CLRI parameter values requires an analysis of the agent's implementation, we use computational learning theory to calculate bounds on some of these parameters. These bounds apply regardless of the agent's learning algorithm. Finally, we study a specific market-based MAS in detail. We confirm the agents' behaviors, as predicted by the CLRI framework, and present other findings specific to market-based MASs, such as the fact that learning agents make the system more robust to the presence of malicious agents, and that agents can expect decreasing returns for increasing levels of strategic thinking.