Nadella and Sen [17] adopted linear regression as an online learning method in designing soccer agents. A soccer agent learns about the linear relation between shooting error and shooting distance. The predicted shooting error is used as a guide for shooting a ball. In this paper, we explore more sophisticated regression methods such as nearest neighbor regression and applied them to online learning.
In multiagent systems, an agent can learn about its own optimal actions without explicitly modeling other agents. One widely applied online learning method is reinforcement learning [14,22]. Originally designed for single-agent systems, reinforcement learning has been applied in a variety of multiagent systems like robotic soccer [1,17] and pursuit games [5]. Simple implementation of reinforcement learning makes an agent ignore the existence of other agents. However, de Jong [5] and Claus and Boutilier [3] found that agents who take other agents into account perform better than those who do not. Such taking other agents into account is usually in the form of a simple model of other agents' states or actions. Carmel and Markovitch [2] designed a learning agent that learns about the other agents' actions by observing the history of the other agent's actions and its own actions. This approach is very close to our 0-level learning agent in this paper. In addition to 0-level agents, we designed learning agents with recursive models of other agents to see whether such sophisticated agents performs even better.
Explicit recursive modeling of other agents in multiagent settings was proposed by Gmytrasiewicz and Durfee [10]. Their model was defined in the framework of static games, while we explore the problem in dynamic games framework. Vidal and Durfee [26] implemented learning recursive models in a particular exchange market. They used the terms 0-level, 1-level and 2-level in describing levels of recursion. Even though we use the same terms in this paper, our definition to some extent differs from theirs. The 1-level agent in their paper is the 0-level learning agent in our paper, such an agent is aware of the existence of other agents but does not model the internal decisions of others. Vidal and Durfee have not explored the behavior of their 3-level agents who are corresponding to 2-level agents in our paper and have been implemented here. In another paper, Vidal and Durfee [27] defined recursive modeling in an abstract knowledge model. Different recursive levels of others were represented by agents' different knowledge of the world. We find such abstraction says little about agents' decision making. In addition, the abstraction was not formulated in a general model of multiagent systems, which leaves the analysis of agent interaction incomplete.
Stochastic games (also called Markov games ) [7,23] as a general framework for multiagent systems has been recently adopted in AI [15,13]. The application so far has been limited in analyzing multiagent reinforcement learning. In this paper, we want to show that stochastic games can be used to analyze a general class of multiagent systems and their learning.
In the following sections, we present first the framework of stochastic games and characterize recursive-modeling agents within this framework. Second, we map this characterization to a particular instance of dynamic multiagent systems, representing a prototypical dynamic market game.