Fast Concurrent Reinforcement Learners

1 Introduction

The reinforcement learning (RL) paradigm provides techniques using which an individual agent can optimize environmental payoff. However, the presence of a non-stationary environment, central to multi-agent learning, violates the assumptions underlying convergence proofs of single agent RL techniques. As a result, standard reinforcement learning techniques like Q-learning are not guaranteed to converge in a multi-agent environment. The focus of convergence for multiple, concurrent learners is on an equilibrium strategy-profile rather than optimal strategies for the individual agents.

The stochastic-game (or Markov Games) framework, a generalization of Markov Decision Processes for multiple controllers, has been used to model learning by agents in purely competitive domains [Littman, 1994]. In that work, the author has presented a minimax-Q learning rule and evaluated its performance experimentally. The Q-learning rule, being a model-free and online learning technique, is particularly suited for multi-stage games, and as such, an attractive candidate for multiagent-learning in uncertain environments. Hu and Wellman (1998) extended Littman's framework to enable the agents to converge to a mixed-strategy Nash equi-

Jing Peng

Dept. of Computer Science Oklahoma State University

Stillwater, OK 74078

jpeng@cs.okstate.edu

librium. There have also been other research on using the stochastic-game framework in multiagent learning, such as an empirical study of multiagent Q-learning in semi-competitive domains [Sandholm and Crites, 1996] among others.

The first two techniques mentioned above are known to converge in the limit. In this paper we show that these two techniques are essentially identical in purely competitive domains. To increase the convergence rate of the minimaxQ rule, we extend it to incorporate SARSA [Rummery, 1994; Sutton and Burto, 1998] and Q(AL) [Peng and Williams, 1996] techniques, and study the convergence rates of these different methods in a competitive soccer domain [Littman, 1994].

2 Multiagent Q-learning

Definition 1 A Markov Decision Process (MDP) is a quadruple CUCBBN BTBN CCBN CACV, where CB is the set of states, BT is the set of actions, CC is the transition function, CC BM CB A2 BT AX BWB4CBB5, BW being a probability distribution, and R is the reward function, CA BM CB A2 BT AX BO.

A multiagent reinforcement-learning task can be looked upon as an extended MDP, with CB specifying the joint-state of the agents, BT being the joint-actions of the agents, BT BD A2 BT BE A2 BM BM BM BT D2 where BT CX is the set of actions available to the CXD8CW agent, CC as the joint-transition function, and the reward function is redefined as CA BM CB A2 BT AX BO D2 . The functions CC and CA are usually unknown. The goal of the CXD8CW agent is to find a strategy AP CX that maximizes its expected sum of discounted rewards, DAB4D7BN AP CX B5 BP  BD D8BPBC AD D8 BXB4D6 CX D8 CYAP CX BN AP A0CX BN D7 BC BP D7B5 where D7 BC is the initial joint-state, D6 CX D8 is the reward of the CXD8CW agent at time D8, AD BE CJBCBN BDB5 is the discount factor, and AP A0CX is the strategy-profile of CX's opponents.

Definition 2 A bimatrix game is given by a pair of matrices, B4 BD BN BE B5, (each of size CYBT BD CY A2 CYBT BE CY for a two-agent game) where the payoff of the CXD8CW agent for the joint action B4CP BD BN CP BE B5 is given by the entry  CZ B4CP BD BN CP BE B5BN BKB4CP BD BN CP BE B5 BE BT BD A2BT BE BN CZ BP BDBN BE.

Each stage of an extended-MDP for two agents (it can be extended to D2 agents using D2-dimensional tables instead of matrices) can be looked upon as a bimatrix game. A zerosum game is a special bimatrix game where  BD B4CP BD BN CP BE B5 B7  BE B4CP BD BN CP BE B5 BP BCBN BKB4CP BD BN CP BE B5 BE BT BD A2BT BE .

Definition 3 A mixed-strategy Nash Equilibrium for a bimatrix game B4 BD BN BE B5 is a pair of probability vectors B4AP A3 BD BN AP A3 BE B5 such that

where BWB4BT CX B5 is the set of probability-distributions over the CXD8CW agent's action space.

No player in this game has any incentive for unilateral deviation from the Nash equilibrium strategy, given the other's strategy. There always exists at least one such equilibrium profile for an arbitrary finite bimatrix game [Nash, 1951].

An individual learner may, but need not, use a model of the environment to learn the transition and reward functions. Qlearning is one example of model-free learning. In greedy policy Q-learning, an agent starts with arbitrary initial Qvalues (or action values) for each state-action pair B4D7BN CPB5, and repeatedly chooses actions, noting its rewards and transitions and updating as

where

and AB D8 BE CJBCBN BDB5 is the learning rate. Watkins and Dayan (1992) have proved that the above iteration converges to optimal action values under infinite sampling of each state-action pair and a particular schedule of the learning rate.

In the case of multiagent learning, the above iteration would not work, since the maximization over one's action is insufficient in the presence of multiple actors. However, if the reward-function of the opponent is negatively correlated, then actions can be selected by solving the bimatrix-game B4B4D7B5BN A0B4D7B5B5 greedily for the opponent, and pessimistically for oneself, to guarantee a minimum expected payoff. This produces Littman's minimax-Q algorithm for simultaneousmove zero-sum games, for which the value-function for agent 1 is

where BT and  are the action-sets of the learning-agent (agent 1) and its opponent respectively, and D8 BD B4D7 D8B7BD BN BMBN D3B5 is a vector of action values of the learner corresponding to its opponent's action D3. The current policy APB4D7B5 can be solved by linearprogramming for the constrained, minimax optimization on B4D7BN BMBN BMB5. The minimax-Q learning rule has been proved to converge to optimal action values [Szepesv´ari and Littman, 1997].

For general-sum games, however, the CXD8CW agent needs to know AP A0CX , in absence of which it has to model its opponents. In such games, each agent can observe the other agent's actions and rewards and maintains separate Q-tables for each of them in addition to its own [Hu and Wellman, 1998].

The value-function for agent 1 in this case is

where B4AP A3 BD BN AP A3 BE B5 are the Nash-strategies of the agents for the bimatrix game CU D8 BD B4D7 D8B7BD BN BMBN BMB5BN D8 BE B4D7 D8B7BD BN BMBN BMB5CV, which can be solved by quadratic-programming technique [Mangasarian and Stone, 1964]. In zero-sum games, the value-function in (3) simplifies to

This algorithm converges to a Nash equilibrium, for a restrictive class of Nash-equilibria [Hu and Wellman, 1998], that in addition to the constraints imposed by its definition, satisfies the following

Though this may not be true in general, it holds for zerosum domains, where any deviation by the opponent from its equilibrium-strategy decreases its expected payoff, thus increasing the modeler's expected payoff. Hence, the convergence of this algorithm is guaranteed in zero-sum domains. Furthermore, the algorithms developed by Littman (1994) and Hu and Wellman (1998) (we call the latter Nash-Q) differ structurally only in the use of rules (2) and (4) respectively, in updating . But contrary to the statement made by Hu and Wellman (1998), these expressions are functionally equivalent in zero-sum games. Game theory [Thie, 1998] states that in a zero-sum game

An informal argument may go as follows. Let BD B4D7BN BMBN BMB5 BP B4D5 BD BN D5 BE BN A1 A1 A1 BN D5 D2 B5, where D5 CX represents the CXth column of BD B4D7BN BMBN BMB5BN and D2 BP CYBT BE CY. Then AP CC BD BD B4D7BN BMBN BMB5 BP B4AP CC BD D5 BD BN AP CC BD D5 BE BN A1 A1 A1 BN AP CC BD D5 D2 B5 for any AP BD BE BWB4BT BD B5. When AP CC BD D5 is treated as a random variable from the distribution AP BE , we have

On the other hand, since any pure strategy is also a mixed strategy, we have

Consequently we have the equality (5). Therefore we observe that both minimax-Q and Nash-Q compute identical policies and value-functions in zero-sum domains.

3 Expediting minimax-Q learning

Since minimax-Q and Nash-Q algorithms are equivalent in the purely competitive domains that we consider in this paper, we focus on the minimax-Q algorithm since it does not require maintenance of opponents' Q functions and hence is resource-efficient. We now turn to explore possible ways to speed-up the chosen algorithm.

3.1 Fast minimax-Q(AL)

Since Q-learning updates only the last state with the reinforcements, it is substantially slow in updating the action values. A well-known technique to speed-up singleagent Q-learning is to integrate it with TD(AL) rewardestimation scheme, producing the Q(AL)-learning rule [Peng and Williams, 1996]. For experimentation, we have used a faster version of the Peng-Williams' algorithm, where the updates are 'lazily' postponed until necessary [Wiering and Schmidhuber, 1998]. Q(AL) can be applied to each of the two learning schemes in the previous section, by defining DAB4D7 D8B7BD B5 in the Q(AL) algorithm by the equation in (2) or (3) as the case may be. The guarantee of convergence, however, may no longer hold.

3.2 Minimax-SARSA learning

The previous techniques were all off-policy learning rules, where the expected value of the next state is used to update the value of the current state. The SARSA(0) technique is, on the other hand, an on-policy learning rule that depends heavily on the actual learning policy followed [Rummery, 1994; Sutton and Burto, 1998]. In general, off-policy algorithms can separate control from exploration while on-policy reinforcement learning algorithms cannot. Despite this, on-policy algorithms with function approximation in single agent learning appear to be superior to off-policy algorithms in control as well as prediction problems [Boyan and Moore, 1995; Sutton, 1996; Tsitsiklis and Roy, 1997]. On-policy algorithms can learn to behave consistently with exploration [Sutton and Burto, 1998] Moreover, on-policy algorithms are more natural to combine with eligibility traces than off-policy algorithms are. This raises the following question that this research effort endeavors to answer: Can on-policy RL algorithms perform equally well in multiagent domains? In that case we can possibly achieve faster convergence of a hybrid of the SARSA technique and minimax-Q rule.

In a simple Q-learning scenario, the SARSA technique modifies the update rule (1) as DA D8 B4D7 D8B7BD B5 BP D8 B4D7 D8B7BD BN CP D8B7BD B5. Thus a SARSA rule learns the values of its own actions, and can converge to optimal values only if the learning policy chooses optimal actions in the limit. In a multiagent minimax-Q setting, the rule (2) would be replaced (for agent 1) by

while the policy to choose actions would still be computed by the original minimax-Q rule. To achieve convergence of this rule to minimax-Q values, we follow an AF-minimax strategy that satisfies the need of infinite exploration while being minimax in the limit, i.e., AF decays to 0 in the limit. We call such exploration 'Minimax in the limit with infinite exploration' or MLIE. Our convergence result rests on the following lemma established by Singh et al. (2000).

Lemma 1 Consider a stochastic process (AB D8 , A1 D8 , BY D8 ), D8 AL BC, where AB D8 BN A1 D8 BN BY D8 BM CG AX BO satisfy the equations

where DC BE CGBN D8 BP BCBN BDBN BEBN BM BM BM BM Let  D8 be a sequence of increasing AR-fields such that AB BC and A1 BC are  BC measurable and AB D8 BN A1 D8 and BY D8A0BD are  D8 measurable, D8 BP BDBN BEBN BM BM BM. Assume that the following hold:

1. CG is finite.
2. BC AK AB D8 B4DCB5 AK BDBN  D8 AB D8 B4DCB5 BP BDBN  D8 AB BE D8 B4DCB5 BO BD w.p.1.
3. CZBXCUBY D8 B4BMB5CY D8 CVCZ CF AK ÆCZA1 D8 CZ CF 1 B7 CR D8 , where Æ BE CJBCBN BDB5 and CR D8 converges to 0 w.p.1.
4. CE CPD6CUBY D8 B4DCB5CY D8 CV AK ACB4BD B7 CZA1CZ CF B5 BE , for some constant AC. Then, A1 D8 converges to 0 with probability 1 (w.p.1).

The update rule for SARSA for agent 1 say, is

We also note that the fixed point of the minimax-Q rule [Szepesv´ari and Littman, 1997] (for agent 1) is

Now we state and prove the theorem for convergence of minimax-SARSA learning using Lemma 1.

Theorem 1 The learning rule specified in (6) converges to the values in equation (7) with probability 1 provided CP D8 is chosen using an MLIE scheme at each step D8, the immediate rewards are bounded and have finite variance, the Q-values are stored in lookup tables, the learning rate, AB D8 , satisfies condition 2 in Lemma 1, and the opponent plays greedily in the limit.

Proof: (Outline) Writing DC in Lemma 1 as (D7 D8 BN CP D8 BN D3 D8 ) and A1 D8 as D8 BD B4D7 D8 BN CP D8 BN D3 D8 B5A0 A3 BD B4D7 D8 BN CP D8 BN D3 D8 B5, and defining AB D8 B4D7BN CPBN D3B5 BP BC unless B4D7BN CPBN D3B5 BP B4D7 D8 BN CP D8 BN D3 D8 B5 BKD8, we have

which gives rise to

It can be shown that the measurability and variance conditions are satisfied and that

for some AD  BE CJBCBN BDB5 (since minimax-Q operator is a contraction), according to the outline provided by Singh et al. (2000). The remaining task is to show that CZBXCUCS D8 B4BMBN BMBN BMB5CY D8 CVCZ vanishes in the limit, under MLIE exploration. We consider the following cases:

1 for our purpose CZBMCZ CF is a max-norm for a uniform weightvector, CF .

Case 2: D1CPDC AP BD D1CXD2 D3 AP CC BD D8 BD B4D7 D8B7BD BN BMBN D3B5 AL D8 BD B4D7 D8B7BD BN CP D8B7BD BN D3 D8B7BD B5. Again, D1CPDC AP BD D1CXD2 D3 AP CC BD D8 BD B4D7 D8B7BD BN BMBN D3B5 AK AP A3CC BD D8 BD B4D7 D8B7BD BN BMBN D3 D8B7BD B5 where AP A3 BD BP CPD6CV D1CPDC AP BD D1CXD2 D3 AP CC BD D8 BD B4D7 D8B7BD BN BMBN D3B5. Hence A0CS D8 B4D7 D8 BN CP D8 BN D3 D8 B5 BP CYCS D8 B4D7 D8 BN CP D8 BN D3 D8 B5CY AK AP A3CC BD D8 BD B4D7 D8B7BD BN BMBN D3 D8B7BD B5 A0 D8 BD B4D7 D8B7BD BN CP D8B7BD BN D3 D8B7BD B5. The associated expected value vanishes again in the limit due to the assumption of an MLIE policy on part of agent 1, and independent of the opponent's behavior.

Let BV D8 B4D7 D8 BN CP D8 BN D3 D8 B5 be the maximum of the two upper limits on CYCS D8 B4D7 D8 BN CP D8 BN D3 D8 B5CY established above. We see that BXCUCYCS D8 B4D7 D8 BN CP D8 BN D3 D8 B5CYCV AK BXCUBV D8 B4D7 D8 BN CP D8 BN D3 D8 B5CV and the r.h.s vanishes for each state-action tuple. Hence, BXCUCYCS D8 B4D7 D8 BN CP D8 BN D3 D8 B5CYCV vanishes for each state-action tuple, which implies that CZBXCUCS D8 B4BMBN BMBN BMB5CY D8 CVCZ vanishes in the limit under MLIE exploration and optimal play by the opponent in the limit. Setting CR D8 in Lemma 1 to CZBXCUCS D8 B4BMBN BMBN BMB5CY D8 CVCZ, we conclude that minimax-SARSA rule converges to the minimax-Q values under MLIE exploration with probability 1, if the opponent plays greedily in the limit, and under appropriate structure of AB D8 . [Q.E.D.]

Note that Case 1 needs the boundedness of D8 BD that follows easily under additional assumptions. It might be argued that the condition of greedy play by the opponent in the limit is restrictive. However, this is typical of a convergence proof of on-policy algorithms that requires more details of the actions taken by the agents. Gains from on-policy algorithms in terms of learning efficiency and cost offset the condition of greedy play in the limit.

4 Experiments in a Competitive Domain

To evaluate the proposed schemes, we used the purely competitive soccer domain [Littman, 1994]. It is a BG A2 BH grid containing two agents, BT and BU, as shown in figure 1, that always occupy distinct squares. The goal of agent BT is on the left, and that of BU on right. The Figure 1 shows the initial positions of the agents, with the ball being given to an agent at random at the start of each game (agent BU in figure). Each agent can choose from a fixed set of five actions at each state: going up, left, down or right, or staying where it is.

When both the agents have selected their actions, these actions are executed in a random order. If an agent bumps onto another, the stationary agent receives the ball, and the movement fails. An agent receives reinforcements of +1 for a goal (or a sameside by the opponent) and -1 for a self-goal (or a goal by the opponent) to maintain the zero-sum character of the game, and in all other cases the reinforcement is zero. Whenever a non-zero reward is received, the game resets to the initial configuration. We shall call an agent following Littman's minimax-Q algorithm an M-agent.

In the training phase of the experiments, we performed symmetric training between two ordinary M-agents, two Magents both using the B4ALB5 rule, and two M-agents both using the SARSA rule. The respective policies learnt, are denoted as  CX BN AL CX BN D7 CX , which are recorded at the end of each CX A2 BDBCBCBCBC iterations. Each training lasted 100,000 iterations in all. We used identical exploration-probabilities as that by Littman (1994) and the decay-factor for the learningrate was set to 0.999954.

Number of iterations (10,000s)

Number of iterations (10,000s)

Figure 3: Games are played by AL CX against D7 CX for various values of CX. The percentages of wins (averaged over 10 runs) by the former in each case are plotted.

In the test phase, we allowed an D7 CX policy to play against an  CX policy, for CX BP BD BM BM BM BDBC. Each test iteration results in a draw with a probability of 0.05, to break possible deadlocks. The resultant percentages of win by the D7 CX policies over its opponent are reported in Figure 2 (left). The approximate trend suggests that ordinary minimax-Q initially dominates but minimax-SARSA gradually catches up and outperforms the former. In Figure 2 (right), the corresponding results from playing AL CX against  CX are shown. In this case the minimax-Q(AL) rule outperforms the ordinary minimax-Q algorithm from the very beginning. However, the AL policies gradually lose their edge as the ordinary minimax-Q rule learns better progressively. The figure 3 corroborates these observations, as AL CX performs well against D7 CX , but this performance decays with increasing CX. AL was set to 0.7 in both experiments.

We note that percentage of wins in such games may not be a good comparative estimator of the policies. A better estimator would be the average RMS deviations of the Q-values from their convergence values. However, the latter can be calculated in this domain only with extensive off-line computation. We also stress that the results reported are far from convergence, at which all the algorithms should perform equally well. The reason why sMM beats MM can be understood in the context of updates. While sMM uses the actual action value from the next state to update the current state, MM still uses the minimax value from the next state, which postpones relying on the individual table-entries. As a result, we expect MM to catch up (in Fig. 2 left) when learning continues.

5 Experiments in a General-sumDomain

We note that minimax-Q rule is applicable in general-sum domains as well, where the rationale of the assumption of minimizing policy of the opponent is to guarantee a minimum security level to the learner, instead of maximizing the reward of the opponent itself as in the zero-sum interpretation. The SARSA and B4ALB5 versions will still work in such domains. For the purpose of experimentation, we introduce a general-sum domain that we call "tightly coupled navigation." This is a BG A2 BF gridworld as shown in figure 4. The values in the lower left corner of each cell in figure 4 is the reward to agent 1 for reaching the state corresponding to that cell. Similarly the values in the upper right corner are those for agent 2. The rewards in this domain are state-based, i.e. the reward corresponding to a cell is received if the agents reach or remain in that cell. Here the agents are tightly coupled as they must always occupy the same cell. Each agent has three available actions in each state, viz. up, down, right. However, since they are coupled, they can move only when they choose the same action; otherwise they remain in the same state. The starting and the absorbing states have been shown in the figure 4. When the agents reach the goal state, each receives the reward 20 and without making any update in this iteration, the game restarts with the agents reshifted to the start-state and updates begin once again.

A more realistic scenario for this domain is car-driving. Consider two agents in the same car and each having a steering wheel in its hands. The car moves in a given direction if both move the wheels in that direction; otherwise the car does not move. There may be different paths that the agents wish to follow to reach their common goal. However, since they are tightly coupled, they must strike a compromise and find an intermediate path that both can be maximally satisfied with, given the coupling.

We have symmetrically trained two minimax-Q and two minimax-SARSA agents in this domain. The exploration probabilities for the agents in each iteration were the same as in the soccer domain, viz. BCBMBE. We varied the probability of rewardgeneration in each iteration using three values, viz. 0, 0.5 and 1.0, where 0 stands for the case where rewards are generated only when the agents reach the goal state. We wanted to study the effect of infrequent rewards, which is a realistic scenario in most practical domains, on the convergence of our algorithms. We expected the convergence rates to fall with more and more infrequent rewards. In order to study the convergence, the exact minimax-Q tables were computed off-line and an average RMS deviation of the learned Q-tables every 1000 training-iterations were plotted. The trainings lasted a total of 10,000 iterations.

From figures 5, 6 and 7, we can see that the minimaxSARSA rule always performs better than the ordinary minimaxQ rule. The errors in all the cases decrease monotonically which suggests that both the rules will eventually converge. As expected, the error-levels fall with increasing probability of reward-generation. A scrutiny of the minimax-Q tables show that the minimax path learned by each agent should be different from the Nash-equilibrium path that is corroborated by the learned Q-tables.

6 Conclusion and Future work

We conclude that both the SARSA and B4ALB5 versions of minimax-Q learning achieve speed-up on Littman's minimaxQ rule, and more so for the B4ALB5 rule. Though this latter rule works well, we are not aware of the theoretical convergence properties of this method. Exploring these properties is one open area. We also note that a combination of minimax-SARSA and B4ALB5 to form what could be called minimax-SARSA(AL), would probably be more expedient than either of the two, by naturally combining their disjoint areas of expedience, seen in the plots in figure 2. Results from associated experiments are awaited. We could also substitute Nash-learning for minimax-learning and achieve NashQ(AL) and Nash-SARSA, specialized fast learning procedures for general-sum domains. A theoretical proof of convergence of such a Nash-SARSA would be along the same lines as presented in this paper for minimax-SARSA. We plan to conduct experiments with all these hybrid algorithms.