Exploration and Adaptation in Multiagent Systems: A Model-based Approach

1 Introduction

The recent tremendous growth of the Internet has mo­ tivated a significant increase of interest in the field of multi agent systems (MAS). In such a system, a group of egocentric autonomous agents interact with each other to achieve their private goals. Generally, agents are de­ signed to achieve their masters ' goals by trying to maxi­ mize some given utility measurement. Designing an "ef­ fective" strategy for interaction is a hard problem be­ cause its effectiveness depends mostly on the strategies of the other agents involved . However, the agents are au­ tonomous, hence thei r strategies are private. One way to deal with this problem is to endow agents with the abil­ ity to adapt their strategies based on their interaction experience [WeiB and Sen, 1996].

A common technique used by adaptive agents in MAS is reinforcement learning [Shoham and Tennen­ holtz , 1994; Sandholm and Crites, 1995]. The adap­ tive agent adapts its strategy according to the rewards received while interacting with other agents. A major problem with this approach is its slow convergence. An effective interaction strategy is acquired only after pro­ cessing a large number of interaction examples. During the long period of adaptation the agent pays the cost of interacting sub-optimally.

In previous work [Carmel and Markovitch, 1996b] we describe a model-based approach that reduces the num­ ber of interaction examples needed for adaptation by in­ vesting more computational resources in deeper analy­ sis of past interaction experience. This approach splits the learning process into two separate stages. In the first stage, the learning agent infers a model of the other agent based on past interaction. In the second stage the agent utilizes the learned model for designing effective interaction strategy for the future .

A model-based adaptive agent might converge to sub­ optimal behavior. Acting according to the current best­ response strategy may leave unknown aspects of the op­ ponent's strategy unexplored. Finding the balance be­ tween exploitation of the current model and exploration of other alternatives is a well-known dilemma for on-line adaptive agents. In this work we describe methods for combing exploration strategies with model-based learn­ ing. The exploring model-based agent sacrifices immedi­ ate rewards to explore the opponent behavior; the better model resulted will then yield a better interaction strat­ egy.

The paper is organized as follows: First, we formal­ ize a framework for describing interaction among agents in multi-agent systems. An encounter between agents is described as a two-player game and a sequence of en­ counters as a repeated game. We also present a general architecture for a model-based adaptive strategy for re­ peated games. Second, we describe some exploration methods for on-line learning and show how to combine them with model-based learning. Third, we show ex­ perimentally the superiority of a model-based adaptive agent over non-adaptive agent and over reinforcement­ learning agent in the Iterated Prisoner's Dilemma game. We also report some experimental results comparing dif­ ferent exploration methods for model-based learning in repeated-games.

2 A general framework for a model-based interacting agent

To formalize the notion of interacting agents we consider a framework where an encounter between two agents is represented as a two-player game and a sequence of encounters as a repeated game. A two-player game is a tuple G = (R1, R2, u1, u2), where R1, R2 are finite sets of alternative moves for the players (called pure strate­ gies) , and u1, u2 : R1 x R2 ---+ ~ are utility functions that define the utility of a joint move (r1, r2) for the players. For example, the Prisoner's dilemma (PD) is a two-player game, where each player has two actions, cooperate (c) and defect(d) , R1 = R2 = {c,d} . The util­ ity functions, u1 , u2 , are described by the payoff matrix shown in Figure 1.

A sequence of encounters among agents is described as a repeated game, G# , based on the repetition of G an indefinite number of times. At any stage t of the game , the players choose their moves, ( r~, r~) E R1 x R2 , simul­ taneously. A history, h(t) of c#, is a finite sequence of joint moves chosen by the agents up to the current sta&e of the game, h(t) = ((r~,rg) , (ri,r~) , ... ,(ri- 1 ,r~-l)). H ( G#) is the set of all finite histories for G# .

A strategy s; : H ( G#) ---+ R; for player i, i E { 1, 2}, is a function that takes a history and returns an action. S; is the set of all possible strategies for player i in G#. A pair Qf strategies ( s1 , s2 ) defines an infinite sequence of joint moves (a path) while playing the game G#, g(. , ,.,) (t) .

The discounted-sum function is common utility func­ tion for repeated games:

0 ~ 1 < 1 is a discount factor for future payoffs of player i. It is easy to show that U 1 (s1 , s2 ) converges for any I< 1.

Definition 1 s?t ( Sj, U;) will be called the best response for player i with respect to strategy Sj and utility U;, iff Vs E S;, [U;(sfPt(sj, U;), Sj)?: U;(s, Sj )] .

The Iterated Prisoner 's Dilemma (IPD) is an example of a repeated game based on the PD game that attracts significant attention in the game-theory literature. Tit­ for-tat (TFT) is a simple, well known strategy for IPD that has been proven to be extremely successful in IPD tournaments [Axelrod, 1984]. It begins with cooperation and imitates the opponent's last action afterwards. The best-response against TFT with respect to U' depends on the discount parameter 1 [Axelrod, 1984]:

One of the basic factors affecting the behavior of agents in MAS is the knowledge that they possess about each other. In this work we assume that each player is aware of the other player 's actions, i.e. R1 , R2 are com­ mon knowledge , while the players' preferences , u1 , u2 , are private. In such a framework, while the history of the game is common knowledge, each player predicts the future course of the game differently. The prediction of player i is based on the player 's strategy s; and on the player 's belief about the opponent's strategy, Sj. Sj will be called an opponent model.

How can a player acquire a model for its opponent's strategy? One source of information available for the player is the history of the game. Another possible source of information is observed games between the op­ ponent and other agents. Note that any history of length t provides a sample, Ej(h(t)) = {(h(k) , rj)IO ~ k ~ t}, oft + 1 examples of the opponent's behavior.

Given a learning algorithm L; that infers an opponent model based on a sample of its behavior, and a utility function U;, we can define the strategy sf' ,L, of a model­ based learning agent as

The above definition yields a model-based player (ME­ agent) that adapts its strategy during the game. A ME­ agent begins the game with an arbitrary opponent model sJ, finds the best response s? = sfPt ( sJ, U;), and plays ac­ cording to the best response, rf = s?(.A), where ..\ is the null history. At any stage t of the game, the ME-agent acquires an updated opponent model by applying its learning algorithm L; to the current sample of the oppo­ nent's behavior, sj = L;(Ej(h(t))) . It then finds the best response against the current model, s~ = sfPt ( sj, U;) , and plays according to the best response r; = sl( h( t)). Figure 2 illustrates the general architecture of an on-line model-based learning agent for repeated games.

The efficiency of this adaptive strategy depends mainly on the two main processes involved: 1) The find­ ing of the best response against a given model; 2) the learning process of the opponent modeL In previous work [1996b] we show that when the players are re­ stricted to regular strategies, i.e. strategies that can be represented by deterministic finite automata (DFA) [Ru­ binstein, 1986], the best-response problem can be solved efficiently. We also describe a learning algorithm for in­ ferring a regular model based on the history of the game.

3 Exploring the opponent's strategy

One of the weaknesses of the model-based approach is that it might converge to sub-optimal behavior. The best-response strategy ignores the possibility that the current model is not identical to the opponent's strategy and that other actions might have a better utility ( ac­ cording to the actual opponent's strategy). The left part of Figure 3 shows an example of an opponent's strategy for IPD. If the player uses the model shown in the right part of the figure then the best-response corresponding to this model is "all-d" which yields sub-optimal utility. Furthermore, playing "all-d" prevents the player from observing counterexamples, therefore, the wrong model will never be corrected and the player will never dis­ cover the best-response for the actual opponent strategy - "play c and than all-d".

The example above demonstrates that it is better sometimes to play sub-optimally in order to explore the opponent's behavior. This phenomenon is known as the dilemma between exploration and exploitation. The learning player has to choose between the wish to exploit the current model maximally, and the desire to explore other alternatives to improve its future play.

In recent years a variety of exploration strategies have been proposed for reinforcement-learning agents. indi­ rect strategies are based on incorporating randomness into the decision procedure of the learning agent. The key idea is to associate a positive probability for any state-action pair. The agent randomly selects an action according to the given distribution and therefore no ac­ tion is neglected forever. A common exploration strategy in the reinforcement learning paradigm is to play accord­ ing to a distribution that takes into account the expected utility of the actions and the learning stage. We will use similar method for the MB-agent with the discounted­ sum utility function. The expected utility of an action r is computed by summing the instant expected reward of executing r and the discounted sum of rewards expected from following the optimal policy from then on.

Let sj = L;(h(t)) be an opponent model inferred by the learning algorithm L; based on history h(t). Let s; = s?\sj, U;') be the best-response for player i. The expected utility for action r is defined by:

U[ can be computed efficiently since any game between two automata converges to a finite cycle, and the dis­ counted sum of rewards can be computed by analyzing the expected game-cycle of the two automata.

The Boltzmann distribution [Sutton, 1990] assigns a probability for any possible action according to its ex­ pected utility and according to a decreasing parameter T called a temperature.

T depends on the stage of the game and determines the rate of convergence. We use a common tempera­ ture function T = at where a < 1 is the exploration parameter.

Direct strategies try to explore the environment more efficiently by using statistics based on the learning ex­ perience of the agent. These heuristic methods compute an exploration bonus for each possible action and in­ corporate this bonus into the decision procedure of the agent. Let E:(sj, r) be the exploration bonus computed for an action r according to the current model sj and the history h(t). The value for each action is computed according to the following formula:

As for indirect methods, a is the exploration parame­ ter that determines the ratio between exploration and exploitation.

Statistics might include action-counts [Sato et al., 1991] where higher exploration bonuses are given to ac­ tions that have been chosen less frequently. Sutton [1990] suggests an exploration bonus based on the time that have passed since the action was taken. Kaelbling [1993] suggests an exploration bonus based on the upper bound of the confidence interval computed for the expected util­ ity of the possible actions.

To summarize, at any stage t of the game, an ex­ ploring MB-agent updates the opponent model sj = L;(Ej(h(t)). It then finds the best response against the model sl = s?t ( sj). When using an indirect exploration method it computes Pr(r) for every action r E R; and randomly selects an action according to this distribution. When using directed methods it computes the exploration bonus for every action r based on the history statistics, and then selects the action with the maximal utility.

4 Experimentation: On-line learning in repeated-games

We conducted a set of experiments to test the capabil­ ities of a model-based learner in repeated games. The stage-game used in these experiments is the PD-game. The first experiment tests the basic capabilities of an on­ line learner against random opponents, the second com­ pares indirect and direct exploration methods, and the third tests the MB-agent against non-random automata.

For each experiment, a random opponent automaton was generated by choosing a random transition function and a random output function. The MB-agent begins with a random DFA as a model of its opponent's strat­ egy and plays according to the best response strategy combined with an exploration strategy. The opponent model is modified whenever it fails to predict the oppo­ nent 's actual play by using the learning algorithm IT­ US-£* with (hi(t), r}) as a counterexample [Carmel and Markovitch, 1996b] . We use the average cumulative re­ ward achieved by the player to measure the quality of its learning strategy:

Figure 4 shows the average cumulative reward attained during 400 stages of the IPD game , averaged over 100 trials against 100 different random automata of size 20. The lowest curve shows the results of the non-adaptive player TFT. TFT achieves only 2.25 points , which is the average payoff of the PD game, and this result is not improved during the game.

The three upper curves stand for ME-strategies com­ bined with Boltzmann strategies with different explo­ ration parameters, T = 5.0 * at. All the ME-strategies achieve results that are far superior to those achieved by TFT. The exploring adaptive agents are far more suc­ cessful than the non-exploring agent (with o: = 0). The graphs highlight an interesting phenomenon. At early stages of the game, the exploring agents pay for the sub­ optimal decisions induced by their "curiosity". The cost for exploration increases with the exploration parameter o:. However , the better models generated by the explor­ ing agents pay off in later stages of the game, and the exploring strategies outperform the non-exploring strat­ egy dominantly.

The second curve shows the results of a reinforcement­ learning (RL) agent. RL is based on the idea that the tendency to produce an action should be reinforced if it produces a favorable results , and weakened if it produces unfavorable results. Q-learning [Watkins and Dayan, 1992] is a well-known RL algorithm that works by esti­ mating the values of all state-action pairs. For repeated games, an entire history is needed for representing a game state. In such framework, any state is visited only once and no generalization can be made. A possible al­ ternative is to use a fixed window of previous moves for representing a state. A too wide window can cause the agent to use a too sparse table and to disable conver­ gence of the learning process in practical time. A too narrow window can cause perceptual aliasing, i.e., dif­ ferent states can appear identical and therefore can be represented by the same state.

Q-learning was tried in repeated games against Tit­ for-tat (TFT) by Sandholm and Crites [1995] . The Q­ agent succeeded in learning an optimal strategy against TFT using a window of width one, but it needed about 100,000 iterations for convergence. Similar results were obtained by us. In our experiments the Q-agent used a window of width 2 and a Boltzmann exploration strat­ egy. It is quite clear that the performance of the Q-agent is much inferior to that of the MB-agent in the given do­ main. Increasing the width of the window did not help. The Q-agent managed to achieve results comparable to those achieved by the MB-agents only when the length of the game was increased up to 40,000.

The results for the MB-agents address a question of how much exploration is needed during interaction . The answer depends on the "greed" of the learning agent . The more weight the agent gives to future payoffs , the more resources it should spend on exploration. This weight is expressed by the discount parameter I· We repeated the last experiment for various values of I· For each 1 we tried several values of exploration parameter o: and recorded the one for which the agent achieved the best performance. The left part of Figure 5 shows the best o: for each I· As expected, as 1 increases, it is better to invest more on exploration by using larger o:.

The right part of Figure 5 shows the effect of increas­ ing the complexity of the opponent strategy on the learn­ ing process. The three curves show the average results attained by an MB-agent with o: = 0.99 against 100 ran­ dom automata of sizes 20, 40, and 60 . The results show that increasing the size of the automata deteriorates the rate of adaptation. Learning effective models for com­ plex automata demands more examples and hence the learning process converges slower.

In the second experiment we compared indirect and direct exploration strategies. The indirect-ME agent uses Boltzmann distribution with temperature function T = 5 * 0.99 1 . The direct-ME agent uses recency-based exploration [Sutton, 1 990] - for every action r it counts the number of stages that have passed since the last time that r was taken, p(sj, r) , at the current state of the opponent model s]. It then computes an exploration bonus

E' ( sj , r) = J p( sj , r) and measures the utility of action r according to Equation 3, using a= 0.1. For automata of size 20, the direct and indirect methods showed com­ parable performance. However , when the size of the au­ tomata was increased to 40, the direct strategies outper­ formed the indirect one. The results are shown in Figure 6.

The exploration behavior of the indirect strategy is sensitive only to the length of the history and not to its content. Therefore it does not modify its exploration behavior when playing against different opponents. The direct strategy, on the other hand, utilizes the content of the history to modify its exploration behavior. This is the reason why it outperforms the indirect method when increasing the complexity of the opponent. However, the direct method does not reduce its exploration tendency with time. Therefore, even after learning a perfect model of the opponent , it will still pick non-optimal actions.

We have designed a combined exploration strategy that uses a combination of the direct and indirect strate­ gies: it uses recency-based exploration strategy but de­ creases the exploration parameter with time, o-1 = 0.1 * 0.99t. Figure 6 shows that the combined strategy enjoys the advantages of both methods and outperforms them both.

In the third experiment we tested the ME-strategy against non-random opponents that were hand-crafted specifically for the IPD game. We repeated the famous tournament organized by Axelrod [1984] for IPD. In the original tournament, fifteen attendees (strategies) com­ peted in a round-robin tournament, where every inter­ action was based on 200 repetitions of the PD game. The participated strategies were sent as computer programs by different researchers around the world. Most programs were designed to basically cooperate. They differ mainly in the way that they deal with defection of their rivals. For this experiment we allowed only de­ terministic regular strategies to participate. Figure 7 shows the models and the best-responses learned by the MB-agent for five different opponents. The MB-agent learned its opponents on-line during the 200 iterations using Boltzmann exploration with the temperature func­ tion T = 5 * 0.99 1 . The best-response strategies were computed according to the discounted sum utility func­ tion with 1 = 0.9.

The MB-agent succeeded very well against the strate­ gies described above. The adaptive strategy begins with­ out any knowledge about the game and only few itera­ tions are needed to converge to the best response: Co­ operate with TFT and exploit players like TF2T and Pavlov. The best-response for Nydegger which is "ail-e" was found after about 100 iterations. The model given in the figure was learned after 200 iterations. It encapsu­ lates many features of Nydegger. For example it cooper­ ates after 3 mutual defections (see the paths 2-5-6-9, 45-6-9, 11-5-6-9). The MB-agent also succeeds in finding the right model for Grim. However, the exploring agent falls into the "defection sink" and is not being able to get back to the cooperation cycle. This problem is common to all exploring strategies that eventually will explore the "wrong" action and will fall into the sink. Grim is a typical example for strategies that are problematic for on-line adaptive players.

5 Conclusions

This work presents a model-based approach for learning interaction strategies. We present an architecture for a model-based learner that uses the best-response strategy combined with an exploration strategy to explore its op­ ponent's behavior for exploitation in future encounters.

We conducted a set of experiments where an adap­ tive model-based agent played against randomly generated opponents. In these experiments, the MB-agent performed significantly better than non-adaptive agents and Q-agents. This result supports our claim that it is more effective to learn a model and use it for design­ ing a best-response strategy than trying to directly learn such a strategy. We compared direct and indirect explo­ ration methods and showed that a combination of these two methods can have an advantage. We also showed that the MB adaptive learner, without any background knowledge, outperforms hand-crafted opponents in the IPD domain.

The above experimental results demonstrate average­ case performance of our learning strategy. In the worst­ case, Fortnow and Whang [1994] show that for any learn­ ing algorithm there is an adversary DFA for which the learning process will converge to the best response in at least exponential number of stages. One way of dealing with this complexity problem is by limiting the space of automata available for the opponent [Mor et al., 1996] . Such methods are based on long exploration sequences during the course of the game. The high cost of such ex­ ploration sequences diminishes in infinite games for util­ ity functions that measure only asymptotic performance. However, these methods may fail for the discounted-sum utility which takes into account also immediate rewards. The exploration methods described in this work take into account the cost of exploration and are therefore suitable for such utility functions as well.

One of the basic assumptions of our framework is that the opponent is stationary. When this assumption is removed, we may want to look at windows of the in­ put rather than the complete history, and to increase the exploratory rate of the algorithms. An interesting class of non-stationary opponents, is the class of adap­ tive opponents. For example, we might assume that the opponent is a ME-adaptive agent. This can be further extended to a general framework of recursive modeling, where a player holds a model of the opponent which is also a modeling player. We have developed a similar framework for two-player zero-sum games [Carmel and Markovitch, 1996a].