R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning

1 Introduction

Reinforcement learning has attracted the attention of researchers in AI and related fields for quite some time. Many reinforcement learning algorithms exist and for some of them convergence rates are known. However, Kearns and Singh's BX BF algorithm [Kearns and Singh, 1998] was the first provably near-optimal polynomial time algorithm for learning in Markov decision processes (MDPs). BX BF was extended later to handle single controller stochastic games (SCSGs) [Brafman and Tennenholtz, 2000] as well as structured MDPs [Kearns and Koller, 1999]. In BX BF the agent learns by updating a model of its environment using statistics it collects. This learning Moshe Tennenholtz A3

A3 Permanent address: Faculty of Industrial Engineering and Management, Technion, Haifa 32000, Israel

Computer Science Department Stanford University

Stanford, CA 94305 moshe@robotics.stanford.edu

process continues as long as it can be done relatively efficiently. Once this is no longer the case, the agent uses its learned model to compute an optimal policy and follows it. The success of this approach rests on two important properties: the agent can determine online whether an efficient learning policy exists, and if such a policy does not exist, it is guaranteed that the optimal policy with respect to the learned model will be approximately optimal with respect to the real world.

The difficulty in generalizing BX BF to adverserial contexts, i.e., to different classes of games, stems from the adversary's ability to influence the probability of reaching different states. In a game, the agent does not control its adversary's choices, nor can it predict them with any accuracy. Therefore, it has difficulty predicting the outcome of its actions and whether or not they will lead to new information. Consequently, it is unlikely that an agent can explicitly choose between an exploration and an exploitation policy. For this reason, the only extension of BX BF to adverserial contexts used the restricted SCSG model in which the adversary influences the reward of a game only, and not its dynamics.

To overcome this problem, we suggest a different approach in which the agent never attempts to learn explicitly. Our agent always attempts to optimize its behavior, albeit with respect to a fictitious model in which optimal behavior often leads to learning. This model assumes that the reward the agent obtains in any situation it is not too familiar with, is the maximal possible reward - CA D1CPDC . The optimal policy with respect to the agent's fictitious model has a very interesting and useful property with respect to the real model: either it performs optimally, or it leads to efficient learning. The agent does not knowwhether it is optimizing or learning efficiently, but it always does one or the other. Thus, the agent will always either exploit or explore efficiently, without knowing ahead of time which of the two will occur. Since there is only a polynomial number of parameters to learn, as long as learning is done efficiently we can ensure that the agent spends a polynomial number of steps exploring, and the rest of the time will be spent exploiting. Thus, the resulting algorithm may be said to use an implicit explore or exploit approach, as opposed to Kearns and Singh's explicit explore or exploit approach.

This learning algorithm, which we call R-MAX, is very simple to understand and to implement. The algorithm converges in polynomial-time to a near-optimal solution. Moreover, R-MAX is described in the context of zero-sum stochastic game, a model that is more general than Markov Decision Processes. As a consequence, R-MAX is more general and more efficient than a number of previous results. It generalizes the results of Kearns and Singh 1998 to adverserial contexts and to situations where the agent considers a stochastic model of the environment inappropriate, opting for a nondeterministic model instead. R-MAX can handle more classes of stochastic games than the LSG algorithm [Brafman and Tennenholtz, 2000]. In addition, it attains a higher expected average reward than LSG. R-MAX also improves upon previous algorithms for learning in repeated games [Aumann and Maschler, 1995], such as Megiddo's [Megiddo, 1980] and Banos [Banos, 1968]. It is the only polynomial time algorithm for this class of games that we know of, and it is much simpler, too. Finally, R-MAX generalizes the results of Monderer and Tennenholtz [Monderer and Tennenholtz, 1997] to handle the general probabilistic maximin (safety level) decision criterion.

The approach taken by R-MAX is not new. It has been referred to as the optimism in the face of uncertainty heuristic, and was considered an ad-hoc, though useful, approach (e.g., see Section 2.2.1 in [Kaelbling et al., 1996], where it appears under the heading "Ad-Hoc Techniques" and Section 2.7 in [Sutton and Barto, 1998] where this approach is called optimistic initial values and is referred to as a "simple trick that can be quite effective on stationary problems"). This optimistic bias has been used in a number of well-known reinforcement learning algorithms, e.g. Kaelbling's interval exploration method [Kaelbling, 1993], the exploration bonus in Dyna [Sutton, 1990], the curiosity-driven exploration of [Schmidhuber, 1991], and the exploration mechanism in prioritized sweeping [Moore and Atkenson, 1993]. More recently, Tadepalli and Ok [Tadepalli and Ok, 1998] presented a reinforcement learning algorithm that works in the context of the undiscounted average-reward model used in this paper. One variant of their algorithm, called AH-learning, is very similar to R-MAX. However, as we noted above, none of this work provides theoretical justification for this very natural bias. Thus, an additional contribution of this paper is a formal justification for the optimism under uncertainty bias.

The paper is organized as follows: in Section 2 we define the learning problem more precisely and the relevant parameters. In Section 3 we describe the R-MAX algorithm. In Section 4 we sketch the proof that it yields near-optimal reward in polynomial time. We conclude in Section 5. Because of length limitations, proofs are not included. A full version of this work appears at www.cs.bgu.ac.il/˜brafman/sg01.ps.

2 Preliminaries

We present R-MAX in the context of a model that is called a stochastic game. This model is more general than a Markov decision process because it does not necessarily assume that the environment acts stochastically (although it can). In what follows we define the basic model, describe the set of assumptions under which our algorithm operates, and define the parameters influencing its running time.

2.1 Stochastic Games

A game is a model of multi-agent interaction. In a game, we have a set of players, each of whom chooses some action to perform from a given set of actions. As a result of the players' combined choices, some outcome is obtained which is described numerically in the form of a payoff vector, i.e., a vector of values, one for each of the players. We concentrate on two-player, fixed-sum games (i.e., games in which the sum of values in the payoff vector is constant). We refer to the player under our control as the agent, whereas the other player will be called the adversary.

A common description of a game is as a matrix. This is called a game in strategic form. The rows of the matrix correspond to the agent's actions and the columns correspond to the adversary's actions. The entry in row CX and column CY in the game matrix contains the rewards obtained by the agent and the adversary if the agent plays his CX D8CW action and the adversary plays his CY D8CW action. We make the simplifying assumption that the size of the action set of both the agent and the adversary is identical. However, an extension to sets of different sizes is trivial.

In a stochastic game (SG) the players play a (possibly infinite) sequence of standard games from some given set of games. After playing each game, the players receive the appropriate payoff, as dictated by that game's matrix, and move to a new game. The identity of this new game depends, stochastically, on the previous game and on the players' actions in that previous game. Formally:

Definition 1 A fixed-sum, two player, stochastic-game [SG]  on states CB BP CUBDBN BM BM BM BN CV, and actions BT BP CUCP BD BN BM BM BM BN CP CZ CV, consists of:

• AF Stage Games: each state D7 BE CB is associated with a two-player, fixed-sum game in strategic form, where the action set of each player is BT. We use CA CX to denote the reward matrix associated with stage-game CX.
• AF Probabilistic Transition Function:   B4D7BN D8BN CPBN CP BC B5 is the probability of a transition from state D7 to state D8 given that the first player (the agent) plays CP and the second player (the adversary) plays CP BC .

An SG is similar to an MDP. In both models, actions lead to transitions between states of the world. The main difference is that in an MDP the transition depends on the action of a single agent whereas in an SG the transition depends on a joint-action of the agent and the adversary. In addition, in an SG, the reward obtained by the agent for performing an action depends on its action and the action of the adversary. To model this, we associate a game with every state. Therefore, we shall use the terms state and game interchangeably.

Stochastic games are useful not only in multi-agent contexts. They can be used instead of MDPs when we do not wish to model the environment (or certain aspects of it) stochastically. In that case, we can view the environment as an agent that can choose among different alternatives, without assuming that its choice is based on some probability distribution. This leads to behavior maximizing the worst-case scenario. In addition, the adversaries that the agent meets in each of the stage-games could be different entities.

R-MAX is formulated as an algorithm for learning in Stochastic Games. However, it is immediately applicable to fixed-sum repeated games and to MDPs because both of these models are degenerate forms of SGs. A repeated game is an SG with a single state and an MDP is an SG in which the adversary has a single action at each state.

For ease of exposition we normalize both players' payoffs in each stage game to be non-negative reals between 0 and some constant CA D1CPDC . We also take the number of actions to be constant. The set of possible histories of length D8 is B4CB A2 BT BE B5 D8 A2 CB, and the set of possible histories, , is the union of the sets of possible histories for all D8 AL BC, where the set of possible histories of length 0 is CB.

Given an SG, a policy for the agent is a mapping from to the set of possible probability distributions over BT. Hence, a policy determines the probability of choosing each particular action for each possible history.

We define the value of a policy using the average expected reward criterion as follows: Given an SG  and a natural number CC , we denote the expected CC-step undiscounted average reward of a policy AP when the adversary follows a policy AQ, and where both AP and AQ are executed starting from a state D7 BE CB, by CD  B4D7BN APBN AQBN CCB5 (we omit subscripts denoting the SG when this causes no confusion). Let CD  B4D7BN APBN CCB5 BP D1CXD2 AQ CXD7 CP D4D3D0CXCRDD CD  B4D7BN APBN AQBN CCB5 denote the value that a policy AP can guarantee in CC steps starting from D7. We define CD  B4D7BN APB5 BP D0CXD1CXD2CU CCAXBD CD  B4D7BN APBN CCB5. Finally, we define CD  B4APB5 BP D1CXD2 D7BECB CD  B4D7BN APB5. BD

2.2 Assumptions, Complexity, and Optimality

In what follows, we make two central assumptions. First, we assume that the agent always recognizes the identity of the state (or stage-game) it reached (but not its associated payoffs and transition probabilities) and that after playing a game, it knows what actions were taken by its adversary and what payoffs were obtained. Second, we assume that the maximal possible reward CA D1CPDC is known ahead of time. This latter assumption can be removed. BE

Next, we wish to discuss the central parameter in the analysis of the complexity of R-MAX - the mixing time, first identified by Kearns and Singh 1998. Kearns and Singh argue that it is unreasonable to refer to the efficiency of learning algorithms without referring to the efficiency of convergence to a desired value. They defined the AF-return mixing time of a policy AP to be the smallest value of CC after which AP guarantees an expected payoff of at least CDB4APB5A0AF. In our case, we have to take into account the existence of an adversary. Therefore, we adjust this definition slightly as follows: a policy AP belongs to the set A5B4AFBN CCB5 of policies whose AF-return mixing time is at most CC, if for any starting state D7 and for any adversary behavior AQ, we have that CDB4D7BN APBN AQBN CC B5 BQ CDB4D7BN APB5 A0 AF.

That is, no matter what the initial state is and what the adversary does, on the average, we have to apply policy AP no more than CC steps before our average accumulated reward is sufficiently close to the value of AP for the state D7. Notice that this means that an agent with perfect information about the nature of the games and the transition function will require at least CC steps, on the average, to obtain an optimal value using an optimal policy AP whose AF-return mixing time is CC . Clearly, one cannot expect an agent lacking this information to perform better.

BD We discuss this choice below.

BE We would need to run the algorithm repeatedly for increasing values of CA D1CPDC . The resulting algorithm remains polynomial in the relevant parameters.

We denote by D4D8B4A5B4AFBN CCB5B5 the optimal expected undiscounted average return from among the policies in A5B4AFBN CCB5. When looking for an optimal policy (with respect to policies that AF-mix in time CC , for a given AF BQ BC), we will be interested in approaching this value in time polynomial in CC, in BDBPAF, in BDBPÆ (where Æ is the failure probability), and in the size of the description of the game.

The reader may have noticed that we defined CD  B4APB5 as D1CXD2 D7BECB CD  B4D7BN APB5. This choice may appear to make the learning task too easy. For instance, one may ask why shouldn't we try to attain the maximal value over all possible states, or at least the value of our initial state? We claim that the above is the only reasonable choice, and that it leads to results that are as strong as previous algorithms.

To understand this point, consider the following situation: we start learning at some state D7 whose value is very high. However, if we do not execute the action CP in D7, we reach some state D7 BC that has a very low value. A learning algorithm without any prior knowledge cannot be expected to immediately guess that CP should be done in D7. In fact, without such prior knowledge, to conclude that CP is appropriate it must compare its outcome to that of the other actions in D7. Thus, one can expect an agent to learn a near-optimal policy only if the agent can visit state D7 sufficiently many times to learn about the consequences of different options in D7. In a finite SG, there will be some set of states that we can sample sufficiently many times, and it is w.r.t. these states that we can learn how to behave.

In fact, it probably makes sense to restrict our attention to a subset of the states such that from each state in this set it is not too hard to get to any other state. In the context of MDPs, Kearns and Singh refer to this as the ergodicity assumption. In the context of SGs, Hoffman and Karp 1966 refer to this as the irreducibility assumption. An SG is said to be irreducible if the Markov-chain obtained by fixing any two (pure) stationary strategies for each of the players is irreducible (i.e., each state is reachable from each other state). In the special case of an MDP, irreducibility is precisely the ergodicity property used by Kearns and Singh in their analysis of BX BF .

Irreducible SGs have a number of nice properties, as shown by [Hoffman and Karp, 1966]. First, the maximal long-term average reward is independent of the starting state, implying that D1CXD2 D7BECB CD  B4D7BN APB5 BP D1CPDC D7BECB CD  B4D7BN APB5 for an optimal policy AP. Second, this optimal value can be obtained by a stationary policy (i.e., one that depends on the current stagegame only). We believe that our results are primarily interesting in this class of games.

3 The R-MAX algorithm

Recall that we consider a stochastic game  consisting of a set CB BP CUBZ BD BN BM BM BM BN BZ  CV of stage-games in each of which both the agent and the adversary have a set BT BP CUCP BD BN BM BM BM BN CP CZ CV of possible actions. We associate a reward matrix CA CX with each game, and we use CA CX D1BND0 to denote a pair consisting of the reward obtained by the agent and the adversary after playing actions CP D1 and CP D0 in game BZ CX , respectively. In addition, we have a probabilistic transition function,   , such that   B4D7BN D8BN CPBN CP BC B5 is the probability of making a transition from BZ D7 to BZ D8 given that the agent played CP and the adversary played CP BC . It is convenient to think of   B4CXBN A1 BN CPBN CP BC B5 as a function associated with the entry B4CPBN CP BC B5 in the stage-game BZ CX . This way, all model parameters, both rewards and transitions, are associated with joint actions of a particular game. Let AF BQ BC. For ease of exposition, we assume throughout most of the analysis that the AF-return mixing time of the optimal policy, CC , is known. Later, we show how this assumption can be relaxed.

The R-MAX algorithm is defined as follows:

Initialize: Construct the following model  BC consisting of  B7 BD stage-games, CUBZ BC BNBZ BD BN BM BM BM BNBZ  CV, and CZ actions, CUCP BD BN BM BM BM BN CP CZ CV. Here, BZ BD BN BM BM BM BNBZ  correspond to the real games, CUCP BD BN BM BM BM BN CP CZ CV correspond to the real actions, and BZ BC is an additional fictitious game. Initialize all game matrices to have B4CA D1CPDC BN BCB5 in all entries. BF Initialize   B4BZ CX BNBZ BC BN CPBN CP BC B5 BP BD for all CX BP BCBN BM BM BM BN and for all actions CPBN CP BC .

In addition, maintain the following information for each entry in each game BZ BD BN BM BM BM BNBZ  : (1) a boolean value known/unknown, initialized to unknown; (2) the states reached by playing the joint action corresponding to this entry (and how many times); (3) the reward obtained (by both players) when playing the joint action corresponding to this entry. Items 2 and 3 are initially empty.

Repeat:

Compute and Act: Compute an optimal CC-step policy for the current state, and execute it for CC-steps or until a new entry becomes known.

Observe and update: Followingeach joint action do as follows: Let CP be the action you performed in BZ CX and let CP BC be the adversary's action.

• AF If CPBN CP BC are performed for the first time in BZ CX , update the reward associated with B4CPBN CP BC B5 in BZ CX , as observed.
• AF Update the set of states reached by playing B4CPBN CP BC B5 in BZ CX .
• AF If at this point your record of states reached from this entry contains

 BD BP D1CPDCB4B4CS BECCCA D1CPDC AF B5 BF CTBN CSA0BKD0D2 BF B4 Æ BICZ BE B5CTB5 B7 BD elements, mark this entry as known, and update the transition probabilities for this entry according to the observed frequencies.

BF The value 0 given to the adversary does not play an important role here.

As can be seen, R-MAX is quite simple. It starts with an initial estimate for the model parameters that assumes all states and all joint actions yield maximal reward and lead with probability 1 to the fictitious stage-game BZ BC . Based on the current model, the optimal policy is computed and followed. Following each joint action the agent arrives at a new stagegame, and this transition is recorded in the appropriate place. Once we have enough information about where some joint action leads to from some stage-game, we update the entries associated with this stage-game and this joint action in our model. After each model update, we recompute the policy and repeat the above steps.

4 Optimality and Convergence

In this section we provide the tools that ultimately lead to the proof of the following theorem:

Theorem 1 Let  be an SG with  states and CZ actions. Let BC BO Æ BO BD, and AF BQ BC be constants. Denote the policies for  whose AF-return mixing time is CC by A5  B4AFBN CC B5, and denote the optimal expected return achievable by such policies by D4D8B4A5  B4AFBN CCB5B5. Then, with probability of no less than BD A0 Æ the R-MAX algorithm will attain an expected return of D4D8  B4A5B4AFBN CC B5B5 A0 BEAF within a number of steps polynomial in BN CZBN CCBN BD AF , and BD Æ .

In the main lemma required for proving this theorem we show the following: if the agent follows a policy that is optimal with respect to the model it maintains for CC steps, it will either attain near-optimal average reward, as desired, or it will update its statistics for one of the unknown slots with sufficiently high probability. This is the implicit explore or exploit property of R-MAX: The agent does not know ahead of time whether it is exploring or exploiting - this depends in a large part on the adversary's behavior which it cannot control or predict. However, it knows that it does one or the other, no matter what the adversary does. Using this result we can proceed as follows: As we show, the number of samples required to mark a slot as known is polynomial in the problem parameters, and so is the total number of entries. Therefore, the number of CC -step iterations in which non-optimal reward is obtained is bounded by some polynomial function of the input parameters, say CC BC . This implies that by performing CC-step iterations BW BP CC BC CA D1CPDC BPAI times, we get that the loss obtained by non-optimal execution (where exploration is performed) is bounded by AI, for any BC BO AI BO BD.

Before stating our main lemma we extend Kearns and Singh's Simulation Lemma [Kearns and Singh, 1998] to the context of SGs with a slightly improved bound as well.

Definition 2 Let  and AM  be SGs over the same state and action spaces. We say that AM  is an AB-approximation of  if for every state D7 we have:

1. If   B4D7BN D8BN CPBN CP BC B5 and  AM  B4D7BN D8BN CPBN CP BC B5 are the probabilities of transition from state D7 to state D8 given that the joint action carried out by the agent and the adversary is B4CPBN CP BC B5, in and AM  respectively, then,   B4D7BN D8BN CPBN CP BC B5A0 AB AK  AM  B4D7BN D8BN CPBN CP BC B5 AK   B4D7BN D8BN CPBN CP BC B5 B7 AB
2. For every state D7, the same stage-game is associatedwith D7 in AM  and in .

Lemma 1 Let  and AM  be SGs over  states, where AM  is an AF CCCA D1CPDC -approximation of , then for every state D7, agent policy AP, and adversary policy AQ, we have that

Next, we define the notion of an induced SG. The definition is similar to the definition of an induced MDP given in [Kearns and Singh, 1998] except for the use of R-MAX. The induced SG is the model used by the agent to determine its policy.

Definition 3 Let  be an SG. Let  be the set of entries B4BZ CX BN CPBN CP BC B5 marked unknown. That is, if B4BZ CX BN CPBN CP BC B5 BE  then the entry corresponding to the joint action B4CPBN CP BC B5 in the stagegame BZ CX is marked as unknown. Define   to be the following SG:   is identical to , except that   contains an additional state BZ BC . Transitions and rewards associated with all entries in   which are not in  are identical to those in . For any entry in  or in BZ BC , the transitions are with probability 1 to BZ BC , and the reward is CA D1CPDC for the agent and 0 for the adversary. BG

Given an SG  with a set  of unknown states, and some state D7, let AP A3   BND7 denote the optimal CC-step policy for the induced SG   starting at D7. When   and D7 are clear from the context, we refer to AP A3   BND7 as the R-max policy (because this would be the policy executed by the R-MAX algorithm at this point).

We now state the implicit explore or exploit lemma:

Lemma 2 Let  be an SG, let  and   be as above. Let AQ be an arbitrary policy for the adversary, let D7 be some state, and let BC BO AB BO BD. Then either (1) CYD4D8B4A5  B4AFBN CCB5B5 A0 CE D7 CAA0D1CPDC CY BO AB, where CE D7 CAA0D1CPDC is the expected CC-step average reward of AP A3   BND7 in  starting from D7; or (2) An unknown entry will be played in the course of running AP A3   BND7 on for CC steps starting at D7 with a probability of at least AB CA D1CPDC .

In practice, we cannot determine AQ, the adversary's policy, ahead of time. Thus, we do not knowwhether R-MAX will attain near-optimal reward or whether it will reach an unknown entry with sufficient probability. The crucial point is that it will do one or the other, no matter what the adversary does.

We can now outline the proof of Theorem 1. First, we wish to show that the expected average reward is as stated. We must consider three models: , the real model,  BC  the actual model used, and  BC , where  BC is an AFBPBECCCA D1CPDC - approximation of  such that the SG induced by  BC and  is  BC  . At each CC-step iteration of our algorithm we can apply the Implicit Explore or Exploit Lemma to  BC and  BC  for the set  applicable at that stage with AB BP AFBPBE. Hence, at each step either the current R-max policy leads to an average reward that is AFBPBE close to optimal with respect to the adversary's behavior and the model  BC or it leads to an efficient learning policy with respect to the same model. However, because BC is an AFBPBECCCA D1CPDC -approximationof, then if the R-max policy is AFBPBE-close to optimal w.r.t.  BC , it must be AFclose to optimal w.r.t. . We know that the number of CC -step phases in which we are exploring can be bounded polynomially. This follows from the fact that we have a polynomial number of parameters to learn (in  and CZ) and that the probability that we obtain a new, useful statistic is polynomial in AFBN CC and . Thus, if we choose a large enough (but still polynomial) number of CC -step phases, we shall guarantee that our average reward is as close to optimal as we wish.

BG Any alternative definition of   assigning to arbitrary entries in  the same reward as that associated with their counterparts in  is suitable as well.

The above analysis was done assuming we actually obtain the expected value of each random variable. This cannot be guaranteed with probability 1. Yet, we can ensure that the probability that the algorithm fails to attain the expected value of certain parameters be small enough by sampling it a larger (though still polynomial) number of times. This is based on the well-known Chernoff bound. Using this technique one can show that when the variance of some random variable is bounded, we can ensure that we are sufficiently close to its average with probability BD A0 Æ by using a sufficiently large sample that is polynomial in BDBPÆ.

To remove the assumption that the AF-return mixing time is known, we proceed as in [Kearns and Singh, 1998]. From the proof of the algorithmwe deduce some polynomial  in the problem parameters such that if CC is the mixing-time, then after B4CCB5 steps we are guaranteed, with probability BD A0 Æ, the desired return. We repeatedly execute the algorithm for all values of CC BP BDBN BEBN BFBN BM BM BM, each time performing B4CCB5 steps. Suppose that CC BC is the mixing time, then after  CC BC CXBPBD B4CXB5 BP B4B4CC BC B5 BE B5 steps, we will obtain the desired return.

Notice that the R-MAX algorithm does not have a final halting time and will be applied continuously as long as the agent is functioning in its environment. The only caveat is that at some point our current mixing time candidate CC will be exponential in the actual mixing time CC BC , at which point each step of the algorithmwill require an exponential calculation. However, this will occur only after an exponential number of steps. This is true for the BX BF algorithm too.

Another point worth noting is that the agent may never know the values of some of the slots in the game because of the adversary's choices. Consequently, if AP is the optimal policy given full information about the game, the agent may actually converge to a policy AP BC that differs from AP, but which yields the best return given the adversary's actual behavior. This return will be no smaller than the return guaranteed by AP. The mixing time of AP BC will, in general, differ from the mixing time of AP. However, we are guaranteed that if CC BC is the AF-return mixing time of AP, and DA is its value, after time polynomial in CC BC , the agent's actual return will be at least DA (subject to the deviations afforded by the theorem).

5 Conclusion

We described R-MAX, a simple reinforcement learning algorithm with guaranteed polynomial-time convergence to nearoptimal average reward in zero-sum stochastic games.

R-MAX is an optimistic model-based algorithm that formally justifies the optimism in the face of uncertainty bias. Its analysis is similar, in many respects, to Kearns and Singh's BX BF algorithm. However, unlike the BX BF , the agent does not need to explicitly contemplate whether to explore or to exploit. In fact, the agent may never learn an optimal policy for the game, BH or it may play an optimal policy without knowing that it is optimal. The "clever" aspect of the agent's policy is that it "offers" a catch to the adversary: if the adversary plays well, and leads the agent to low payoffs, then the agent will, with sufficient probability, learn something that will allow it to improve its policy. Eventually, without too many "unpleasant" learning phases, the agent will have obtained enough information to generate an optimal policy.

R-MAX can be applied to MDPs, repeated games, and SGs provided that the latter satisfy the condition that the value of a state game can be computed efficiently. In particular, all single-controller stochastic game instances covered in [Brafman and Tennenholtz, 2000] fall into this category. However, R-MAX is much simpler conceptually and easier to implement than the LSG algorithm described there. Moreover, it also attains higher payoff: In LSG the agent must pay an additional multiplicative factor AU that does not appear in R-MAX.

Two other SG learning algorithms appeared in the literature. Littman [Littman, 1994] describes a variant of Qlearning, called minimax Q-learning, designed for 2-person zero-sum stochastic games. That paper presents experimental results, asymptotic convergence results are presented in [Littman and Szepesvri, 1996]. Hu and Wellman [Hu and Wellman, 1998] consider a more general framework of multiagent general-sum games. This framework is more general than the framework treated in this paper which dealt with fixed-sum, two-player games. Hu and Wellman based their algorithm on Q-learning as well. They prove that their algorithm converges to the optimal value (defined, in their case, via the notion of Nash equilibrium). However, convergence is in the limit, i.e., provided that every state and every joint action has been visited infinitely often. Note that an adversary can prevent a learning agent from learning certain aspects of the game indefinitely and that the polynomial time convergence of R-MAX to optimal payoff is guaranteed even if certain states and joint actions have never been encountered.

The class of repeated games is another sub-class of stochastic games that satisfies the conditions of R-MAX. In repeated games, CC BP BD, there are no transition probabilities to learn, and we need not use a fictitious stage-game. Therefore, a much simpler version of R-MAX can be used. The resulting algorithm is much simpler and much more efficient than previous algorithms by Megiddo [Megiddo, 1980] and by Banos [Banos, 1968]. Moreover, for these algorithms, only convergence in the limit is proven.

Acknowledgments: We thank Amos Beimel for his help in improving the error bound in Lemma 1 and the anonymous referees for their useful comments. The first author was partially supported by the Paul Ivanier Center for Robotics and Production Management.