A Near-Optimal Poly-Time Algorithm for Learning a class of Stochastic Games

1 Introduction

Stochastic games (SGs) extend Markov decision processes (MDPs) to a multi-agent environment. In classical stochas­ tic games [Shapley, 1953], two players, the agent and the ad­ versary, engage in a series of competitive interactions. Thus, each state in an SG is associated with a game between the agent and the adversary. Following each game, each of the players obtains some reward and both end up in a new state (i .e. , game). The reward obtained by the players is a func­ tion of the current state and their actions; the new state is a stochastic function of the current game and the players' ac­ tions.

Much like in MDPs, the agent's goal is to find an opti­ mal (or near-optimal) policy, i.e., a mapping from states (i .e., games) to actions. However, unlike in MDPs, such optimal policies are typically mixed, i.e., each game is mapped to a probability distribution over actions rather than to a par­ ticular action. The optimization criteria for SGs are similar to those used in MDPs, and include cumulative discounted reward, cumulative undiscounted reward (where the number of steps is finite but unbounded), average discounted reward, and average undiscounted reward; we concentrate on this last criterion. Unfortunately, it is not known whether station­ ary optimal policies for infinite horizon stochastic games ex­ ist when the average undiscounted reward criterion is used. Moreover, there are no known polynomial time algorithms for computing solutions for such games. However, there

Moshe Tennenholtz

Faculty of Industrial Eng. and Management Technion Haifa, 32000 Israel moshet@ ie.technion.ac.il

is an important class of stochastic games in which station­ ary optimal policies in the infinite horizon average undis­ counted reward case exist, and they can be computed in poly­ nomial time. This type of games is called single-controller stochastic games (SCSGs) [Horijk and Kallenberg, 1981; Parthasarathy and Raghavan, 1981; Vrieze, 1981], a name which derives from the fact that the state (or game) transi­ tions depend on the action of the agent alone. Hence, the adversary's action influences the rewards only. In this paper, we concentrate on learning in SCSGs containing zero-sum games. The extension of these results into zero-sum stochas­ tic games is discussed in the full version of this paper [Braf­ man and Tennenholtz, 1998].

The learning algorithm we present is based on the E 3 al­ gorithm [Keams and Singh, 1998], a model-based learning algorithm (i.e, one in which a partial model of the MDP is formed) that has introduced a number of new concepts and ideas in the area of reinforcement learning. The extension of these ideas into SGs raises a number of issues that stem from the existence of an adversary whose behavior is unknown. In particular, this adversary can, at will, hide information from the agent by refraining from taking particular actions or by rarely playing such actions. Therefore, certain aspects of the model may never be known to the agent or may take an un­ bounded time to learn, unlike in MDPs. Therefore, we cannot emulate the two phase approach of the E 3 algorithm. There, the agent first attempts to learn enough about the model to obtain near-optimal return, after which it enters an exploita­ tion phase. Instead, we will have to allow for the possibility of continuous learning.

Indeed, in stochastic games, a more complicated form of the exploration vs. exploitation problem arises. Recall that the exploration vs. exploitation dilemma refers to the ques­ tion of whether to play optimally given the current knowl­ edge, or to attempt to increase knowledge at the risk of un­ known losses. Kearns and Singh (KS) [Keams and Singh, 1998] solve this problem in the context of MDPs by using the fact that, if we know the value of the optimal policy of the MDP, we can, at each stage, examine whether we have learned enough to gu·arantee ourselves this value. Once this is the case, the agent needs no longer explore. Unfortunately, in SGs, this is not the case. Because of the ability of the ad­ versary to hide parts of the game matrix, in many cases, we lack the information to calculate the value of a given policy.

To overcome this, we employ techniques introduced by Mon­ derer and Tennenholtz [1997] in the context of learning in repeated games. Namely, we explore at two levels. First, as in E 3 , we perform global exploration. That is, we attempt to learn some facts about different games. In addition, we perform local exploration in order to extend our knowledge about particular games. Because it depends on the behavior of the adversary, this local exploration part cannot be a-priori bounded. This is to be contrasted with the initial exploration phase of E 3 , which takes polynomial time.

The algorithm presented in this paper addresses these and other issues and yields near optimal performance for the agent in time polynomial in the basic problem parameters. It is, to the best of our knowledge, the first such result in the context of stochastic games. Previous algorithms for learning in SGs [Littman, 1994; Hu and Wellman, 1998] were not concerned with analytic treatment and proof of efficiency, nor dealt ex­ plicitly with the exploration vs. exploitation issue in an ef­ ficient manner. However, Littman does provide asymptotic convergence results.

In the following section we discuss single-controller stochastic games. In Section 3 we present our measure of complexity. In Section 4 we present our main Theorem, which makes use of two basic ideas. A discussion of the first idea, based on a recent algorithm by Kearns and Singh [1998] appears in Section 5. A discussion of the second idea, which is in the spirit of work on learning in repeated games, and in particular follows recent work by Monderer and Tennenholtz [1997], is presented in Section 6. The synthesis of these ideas into a complete algorithm is presented in Section 7. We con­ clude in Section 8. The full version of this paper, [Brafman and Tennenholtz, 1998], contains all proofs, explains the is­ sues that general stochastic games pose, and explains how the results presented here can be extended to the general case.

2 Preliminaries

First, we define Single-Controller-Stochastic-Games (SCSG):

Definition 1 A single-controller-stochastic-game M on states S = {1, ... , N}, and actions A = {at. ... , ak}, consists of"

• Stage Games: each state s E S is associated with a zero-sum game in strategic form, where the action set of each player is A. The first player is termed agent and the second player is termed adversary.
• Probabilistic Transition Function: PM ( s, t, a) is the probability of a transition from s to t given that the first player (termed agent) plays a.

For ease of exposition we normalize the payoffs of each state game to be non-negative real numbers between 0 and a constant Pmax (i.e. the sum of the players' payoffs for any joint action is always P max). We will also take the number of actions to be constant. The set of possible histories oflength t is ( S x A 2 ) t, and the set of possible histories, H, is the union of the sets of possible histories for all t ~ 0, where the set of possible histories of length 0 isS. Given an SCSG, a policy for the agent is a mapping from H to the set of possible prob­ ability distributions over A. Hence, a policy determines the probability of choosing each particular action for each possi­ ble history. A stationary policy depends only on S instead of on H. Such a policy associates with each state a probability distribution on the actions.

Given an SCSG M and a natural number T, we de­ note the expected T -step undiscounted average reward of a policy 1r when the adversary follows a policy p, and where both 1r and p are executed starting from a state s E S, by UM(s, 1r, p, T) (we omit subscripts denoting the SCSG when this causes no confusion). Let UM(s, 1r, T) = minp ;$ a policy U M ( s, 1r, p, T) denote the value that 1r can guarantee in T steps starting in s. If U M ( s, 1r, T) is in­ dependent of s we denote it by U M ( 1r, T). We also de­ note UM(s, 1r) = liminfT-too UM(s, 1r, T), and UM(7r) = lim infT-too UM( 1r, T) when the value is independent of s.

In the sequel we will assume that the SCSG is ergodic in the sense that given any stationary policy of the agent, the probability of transition between each pair of states is greater than 0 regardless of the adversary behavior. This makes the value of each stationary policy well-defined (i.e., it is inde­ pendent of the initial state). In particular, the value of M is the value UM(1r*) of an optimal policy 1r* (and we know that for SCSGs, there is no loss of generality in assuming this policy is stationary).

The ergodicity assumption is consistent with the treatment of [Kearns and Singh, 1998], and is quite natural for the fol­ lowing reasons. Any Markov chain defined by a policy has one or more absorbing subsets of states. That is, subsets of the state space such that once the agent enters them, he will remain in them. In the initial stages of learning, the agent cannot be expected to know which policies will lead to which sets of absorbing states, and so we cannot really influence the choice of an absorbing state set. However, once we are within such a set, we would like to quickly learn how to behave. This is basically what we (and KS) offer.

3 Our Measure of Complexity

One of KS's contributions is the identification of the central parameter upon which the analysis of algorithms for learning in MDPs must be based, namely, the mixing time. KS 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 £-return mixing time of a stationary policy 1r to be the smallest value ofT after which 1r guarantees an expected payoff of at least U ( 1r) - £. More for­ mally, in the context of SCSGs we say that a policy 1r belongs to the set TI(t:, T) of stationary policies whose £-return mix­ ing time is at most T, if after timeT, 1r returns an expected (average, undiscounted) payoff of at least U ( 1r) - £ for every possible adversary behavior. That is, on the average, we have to employ T steps of policy 1r until our average accumulated reward is sufficiently close to the value of 1r. Notice an agent that already knows an optimal policy 1r whose £-return mix­ ing time is T, will need this much time, on the average, to obtain a value of (almost) v. Clearly, one cannot expect an agent lacking this information to perform better.

Notice that the mixing time of a policy depends on the ad­ versary's behavior: The agent's accumulated reward depends on his actions and on the adversary's actions. Hence, the ad­ versary can influence the time ,it takes to obtain a particular sum of rewards, and we must take this into account. Luckily, in SCSGs, we can show that the mixing time of any policy is finite. This follows from the following observations: Given a stationary policy, if we disregard the payoffs obtained in each state, we get a standard Markov chain. 1 Now, given a par­ ticular stationary policy of the agent, the best response of the adversary is static, i.e., it is built from best response actions at each state. If the adversary will not follow this best response strategy, the agent's payoff can only increase. (Again, in SGs in general this is not true, since the adversary can influence the transition probabilities.) For a fixed policy of the adver­ sary, it is possible to calculate the appropriate mixing time. As we have just observed, any deviation from this behavior will only increase the payoffs to the agent, thus decreasing the time needed to obtain the desired value.

We denote by Opt(II(f, T)) the optimal expected undis­ counted average return from among the policies in II(f, T). When looking for an optimal policy (with respect to policies that mix at time T, for a given f > 0), we will be inter­ ested in approaching this value. In our algorithm, we shall assume that T and Opt(IT(f, T)) are given, and we shall at­ tempt to learn a behavior whose average return is within f from Opt(II(f, T)). Once this problem is solved, we can, as in [Kearns and Singh, 1998], remove these assumptions and measure the complexity as a function of the mixing time of the (stationary) optimal policy, where this value, as well as the value of the game, are a-priori unknown.

4 The Main Theorem

Recall that we wish to obtain efficient behavior in stochastic games for agents that do not know the transition probabilities a-priori, nor do they know which games are associated with each state. We can show:

Theorem 1 Given an SCSG M with N states and some f > 0, denote the stationary policies with f-retum mixing timeT, by IIM ( f, T), and the optimal expected return achiev­ ablebysuchpoliciesbyOpt(IIM(f,T)). LetO < cS,¢ <I be constants. Then, there exists an algorithm LSG, which takes N, T, f, c5, <P as inputs, and is polynomial in N, T, ~, t, i'· such that with probability 1 - c5 the expected return of LSG is greater than (1- <P)(Opt(IIM(f, T))- 2f).

Two features are immediately apparent from the statement of this theorem: We must pay a small additive factor because of the fact that, as in MDPs, one cannot guarantee an optimal payoff within a bounded amount of time - a fact that holds even when we have an explicit, correct model. To overcome the adversary's ability to hide desired information, we must perform some sampling throughout the process. This costs a small multiplicative loss whose size is ¢.

The proof of this theorem relies on two observations:

1) Since SCSGs share much structure with MDPs, we can adopt many aspects ofthe E 3 algorithm to this context. One of the fundamental ideas in this algorithm is the definition of a known state, i.e., a state for which the agent has accumulated sufficiently accurate statistics with regards to both rewards and transitions originating from it. We will adopt a similar notion, and utilize it similarly. However, in our case, the re­ wards for different actions depend on the actions taken by the adversary, who may act maliciously. Hence, careful adapta­ tion of this notion is required for our context. Once this is done, we can follow the ideas of [Kearns and Singh, 1998], regarding the exploitation vs. global exploration issue. This point is discussed in Section 5.

1 This does not hold for SGs in general.

2) Suppose that we learned some information about a par­ ticular game, and we attempt to employ an optimal policy with respect to this information. For example, suppose that we learned two out of three columns of a given game. 2 How­ ever, so far, we do not have knowledge of what happens when the adversary chooses this third action. Furthermore, suppose that some action a is the optimal action when the adversary sticks to the two actions we are familiar with. We have the following dilemma: we could try to exploit our current infor­ mation about the game, and decide to play a. However, ifthe adversary chooses to start playing his third action now, and a is inadequate against this action, we will attain low returns. On the other hand, we could explore the whole game first, playing randomly until we learn enough about the third col­ umn. However, we have no guarantee that the adversary will actually play the third action and so we may learn nothing new while continuously attaining sub-optimal returns. This issue was referred to earlier as the local explore vs. exploit problem, and our main problem will be to find some reason­ able tradeoff between these two options, one that will allow us to achieve the desired level of performance. This issue is discussed in Section 6.

5 Exploitation with Global Exploration

We will make use of the following definition, which enables us to state a version of the simulation Lemma of [Kearns and Singh, 1998] in the context of stochastic games.

Definition 2 Let M and M be SCSGs over the same state space. We say that M is an a-approximation of M if for every states we have:

1. If PM(s,t,a) and PM(s,t,a) are the probabilities of transition to t given t!_zat the action carried out by the agent is a, in M and M respectively, then, PM ( s, t, a) - a:::; PM(s, t, a) :::; PM(s, t, a)+ a
2. The game associated with s in M is the game associ­ ated with it in M restricted to a non-empty subset of the columns.

Lemma 1 Let M and M be any SCSGs over N states, where M is an O(NT~mar ) 2 -approximation of M, then for every state s and policy 1r we have that U M ( s, 1r, T) ~ UM(s, 1r, T)- f.

We say that a state is known if we know its associated tran­ sition probabilities within a range of 0( NT ~mar ) 2 from their true value, and we know at least one column in it. That is, the transitions and rewards associated with all actions of the agent and at least one action of the adversary are known. This definition is non-trivial. In particular, notice that it ignores the fact that outcomes which are not associated with a fully known column might be relevant. Hence, when we say that a state is known we do not imply that complete empirical evi­ dence about the state exists. This point is crucial, and is the topic of the following section. Nevertheless, this definition suffices for us to apply the ideas of KS in our context.

2 That is, we've made sufficient observations of the outcome of all of our actions with two of the adversary's three actions.

Definition 3 Let M be an SCSG, and let L be any subset of S. The induced SCSG, ML, has states L U {10 }, and transi­ tions and state games as follows:

1. The states in ML are associated with the same games as inM.
2. The state 10 is associated with a game where the ad­ versary obtains the value P max for any joint action (a "worst case" state for the agent).
3. For any action a, PML (lo, lo, a) = 1.
4. For any states s, t E L, and a E A, we have that PM(s,t ,a) = PML(s,t,a).
5. For every s E L, and t fl. L, and for every action a E A, we have that PML (s, t, a) = 0.
6. For every s E L, and a E A, we have that PML (s, lo, a)= EjiLPM(s, t, a).

What follows is the SCSG version of [Kearns and Singh, 1998]'s "Explore or Exploit" lemma.

Lemma 2 Let M be an SCSG. Let L be any subset of S, and let ML be the corresponding induced SCSG. Then, for any s E L, and for every T and 0 < a < 1, we have that there exists a policy 1r in ML such that UML (s, 1r, T) 2: UM(s, 1r*, T) -a (where 1r* denotes the corresponding T­ step optimal policy in M ), or there exists a policy in ML such that the probability that a walk ofT steps of that policy will reach l0 exceeds P::u for every adversary behavior.

It is now natural to look at Ah, where L is the set of known states. The lemmas presented . above tell us that if at each known state the adversary performs only actions that are as­ sociated with fully known columns, then one can either find a policy which, if runs for T steps, attains the desired value (i.e., an exploitation policy), or a policy that, with sufficient probability, will reach some unknown state (i.e., an explo­ ration policy). The exploration policy is attained by looking for an optimal policy in Ah, where llh is defined much as llh, but such that the adversary obtains 0 for every joint ac­ tion when in lo and Pmax when in L.

Let us sum up the observations and ideas discussed so far. The basic idea is to define a known state as a state which has been visited enough times to collect meaningful statistical data on one column of the game matrix at least. When an agent reaches an unknown state it randomly selects an action and executes it. (We cannot employ the balanced wandering approach of KS, since an adversary can exploit this to prevent learning). After polynomially many states, at least one state will become known with sufficient probability.

When an agent reaches a known state, it will perform ex­ ploration or exploitation depending on the outcome of the calculation described in the explore or exploit lemma. This calculation (where we compute the optimal expected T-steps return in kh, where L is the set of known states) must be repeated each time a new state becomes known or a new.col­ umn becomes known. This can be efficiently computed (as a function of N and T) using standard dynamic programming updates. If this value is not close enough to the desired value, we will generate an exploration step in order to reach an un­ known state and make additional random sampling of actions. Notice that after at most polynomially many stages, with high probability, all states become known or the value can be ob­ tained. (Recall, we assume that the adversary plays according to the known columns only.)

Eventually, we reach a situation where we know a policy that with high probability attains the desired value assuming that the adversary executes actions which correspond to fully known columns of each game. However, the adversary, of course, could well play actions corresponding to unknown columns, leading to a payoff lower than expected. In the fol­ lowing section we explain how this problem is dealt with.

6 Exploitation with Local Exploration

In the previous sections we modified the definition of a known state introduced by KS in order to adapt their techniques to the context of stochastic games. However, we saw that an ad­ versary can exploit the existence of unknown columns within a known state, if we are not careful. To handle this problem, we adopt techniques from the work of Monderer and Tennen­ holtz [1997] on learning in repeated games.

Lemma 3 Consider an SCSG M with N states and k ac­ tions, where the transition probabilities are known and at least one column at each state is (fully) known. Consider the policies whose c-retum mixing time is T, and let 0 < 0,1 < 1. There exists an algorithm polynomial in T, N, j, ~, ~ such that its execution polynomially many steps leads to an ex­ pected average payoffof(l-O)(Opt(IT(c, T)) -c) with prob­ ability of at least 1 - 'Y·

Proof: The algorithm runs in stages that last at most T -steps. At each such stage, aT-step optimal policy with respect to known columns only, 1r, is computed. We know that 1r has an expected payoff of at least Opt(IT(c, T) - c), provided that the adversary selects only actions which correspond to known columns. However, as there is no guarantee that the adversary will act this way, we execute a policy 1r m instead of 1r . 1r m is equivalent to 1r with probability of 1 - ~, and with probability of ~ it randomly selects a time i between 1 and T and an action, and when the i-th step in the execution is reached it executes this randomly chosen action.

A stage is considered finished if either: ( 1) the policy has been executed forT steps, or (2) either the adversary used an action that corresponds to an unknown column or the agent deviated from 1r.

It can be shown that the probability that unknown columns will be selected eTk: X) 3 k2 N times before all entries are known is less than k 2 N e ~. This follows from the fact that ( 1) the probability of failure of learning all columns in at least one set (from among k 2 N sets) of eTk: X) 3 adversary deviations (i.e. selections of unknown columns) is smaller than k 2 N times the probability of failing to learn in one such set of deviations, and that (2) there are at most k 2 N entries to learn.

We run the the algorithm for Y stages, such that ('TkNX )'k'N :=ry < ~ and Y is polynomial in the problem parameters. This will guarantee that the proportion of stages in which we do not follow rr is smaller than (} /2. Hence, we must have Y > eTkfX) 3 k 2 N · j. We also need to . 2 ->kNTX lkNTX k'N reqmre that k Ne-r- < -y. Hence, e-.- > -=r· or X > log( k~N) 2k~T. As can be directly observed from these inequalities, we can indeed choose (polynomial) X and Y that satisfy these conditions.

To complete the proof we need to show that we obtain the desired expected value. This follows from the fact that after Y stages (with the corresponding probability) only at most~ of the stages correspond to adversary deviations, while in 1 - ~ ofthe stages an expected payoff of (1- ~ )(Opt(II(c, T)) -c) is obtained. I

Hence, once we have reached a situation where we have a policy that can obtain the desired value if the adversary be­ haves "nicely", we can modify this policy to a policy which obtains almost the desired value or learns a new fact about the states (with overwhelming probability). Thus, we trade­ off some exploitation for exploration in a manner that guaran­ tees that if the adversary plays an unknown column polynomi­ ally many times, we will learn this column after a polynomial number of steps. If the adversary rarely plays that column, we will rarely encounter it, and so the possible losses stemming from the randomization effect are almost surely insignificant given a sufficiently long (but polynomial) number of steps.

7 The Algorithm

The LSG algorithm can be executed for any desired number of steps t ~ oo. For sufficiently large values oft (polynomial in the problem parameters) a near optimal average return is guaranteed, as stated in Theorem 1.

1. Initialize the set L of known states to be empty.
2. If the current state is not in L:
3. (a) Randomly sample an action and execute it.
4. (b) If following this sampling the current state has been visited enough times (see Definition 2, Lemma 1, and the discussion after Lemma 1), and at least one column of the game associated with it is known, add it to the set of known states L.
5. If the current state is in L (i.e., a known state), per­ form an off-line computation on kh in order to check whether a value of at least Opt(IIM(T, c)) - c can be guaranteed, assuming the adversary uses only actions that correspond to fully known columns.
6. If such a value can be guaranteed by a policy rr, then the policy 11'm is executed. 3 The run of 11'm is halted whenever a deviation of the adversary from the actions associated with fully known columns is observed, when the agent deviates from rr, when we have reached an un­ known state, or when a new column in a state in L be­ comes fully known.
7. Otherwise, a payoff of Opt(IIM(T, c)) - c can not be obtained, and a (global) exploration policy rr' is executed (see Section 5) for T steps or until an unknown state is reached. This policy is guaranteed by Lemma 2 to reach a state outside L with probability of at least P~az within T steps.
8. In all cases, whenever an entry in a state game is learned, the value of it is kept in memory.

It is clear (from Lemma 3) that the above algorithm is poly­ nomial (i.e. leads to near optimal average return after poly­ nomial time) in the appropriate parameters. It remains to be shown that this algorithm will yield the desired return with probability of at least 1 - J for a given J > 0. To show this, we have to consider the four sources of failure of the algo­ rithm. The first three appear in the context of the E 3 algo- · rithm, while the fourth stems from the need to perform local exploration.

1. In some states the algorithm may have a poor estimate of the true next-state distribution. Using standard Chernoff bound analysis [Alon et al., 1992], as was applied by KS in the case of MDPs, we can show that, if the number of times an entry was explored is sufficiently large (but still polynomial), the probability of an error larger than we wish for is small. Notice that, for this analysis, our definition of known states enables us to ignore the fact the rewards in some columns are only partially known.
2. Repeated attempted explorations may fail to expose new information. This can be either because of failure to reach an unknown state and failure to sample a new entry in an unknown state. We can view a global exploration step, followed by random wandering, as a Bernoulli trial, with a constant positive probability of success of at least O(Pm:,k) for reaching an unknown state and explor­ ing a new entry in that state. The number of such tri­ als which might be executed before all states become known can therefore be taken (since all of the trials can be treated as independent trials) to be polynomial, with a failure prob~bility of at most 4 . Notice that in general, not all states need to become known.
3. When we perform T-step exploitation with no lo­ cal exploration we reach an expected return of Opt(IIM(T, c)) - c, but the actual return may be lower. This point is handled by the fact that after polynomially local exploitations are carried out, Opt (IIM (T, c)) - ~c can be obtained with a probability of failure of at most ~. This is obtained by standard Chernoff bounds, and

8 Recall that 11'm performs the optimal policy with respect to known states with some amount of local exploration.

• makes use of the fact that the standard deviation of the expected reward in aT-step policy is bounded.
• The agent may get a low payoff because it does not know the entries in some column and does not learn new entries in unknown columns. This is handled by Lemma 3, where we can choose the failure probability, '"'f, as needed.

By making the failure probability less than ~ at each of the above stages, we are able to get the desired result.

Finally, we remove the assump~ions that both the value and its c-retum mixing time are known. This is straightforward and almost identical to the treatment given by [Kearns and Singh, 1998]. First, as to knowledge of the value, this is needed when we have to decide whether to explore or ex­ ploit. Lemma 2 states that we can either get enough re­ turn or we have a sufficiently high probability of reaching a new state quickly. One can calculate this probability with­ out knowledge of the value and perform exploration when­ ever this probability exceeds the desired bound. Notice that by employing this technique, with overwhelming probability we remain with known states only after polynomial time. At this point, we can compute an optimal policy. Hence, we can safely apply this exploration bias.

Next, we must deal with the lack of knowledge ofT. The idea is as follows: from the proofs of the algorithm's prop­ erties, one can deduce some polynomial P in the problem parameters such that ifT is the mixing-time, then after P(T) steps we are guaranteed, with probability 1- ~.the desirable return. Hence, we can simply attempt to run this algorithm forT = 1, 2, 3, .... For each value ofT, we run the algo­ rithm P(T) time. Suppose that To is the mixing time, then after O(P(T0 ) 2 ) steps, we will obtain the desirable return.

One thing to notice is that this 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 T will be exponential in the actual mixing time To. at which point each step of the algorithm will require an exponential calculation. However, this will occur only after an exponential number of steps. This is true for the E 3 algorithm too.

Another point worth mentioning is that in SCSGs, the agent may never know some of the columns. Consequently, if rr is the optimal policy given full information about the game, the agent may actually converge to a policy rr' that differs from rr, but which yields the best return given the adversary's actual behavior. This return will be no smaller than the return guaranteed by rr. The mixing time of rr' will, in general, dif­ fer from the mixing time of 1r. However, we are guaranteed that if To is the c -return mixing time of 1r, and v is its value, after time polynomial in T0 , the agent's actual return will be at least v (subject to the deviations afforded by the theorem).

8 Conclusion

We described an algorithm for learning in a restricted class of stochastic games. This algorithm extends earlier work of Kearns and Singh [1998] on learning in MDPs using the tech­ niques of Monderer and Tennenholtz [ 1997] for learning in repeated games. These results can be extended to stochastic games in general, as explained in the full paper [Brafman and Tennenholtz, 1998]. Unfortunately, the adversary's ability to influence transitions can lead to very large mixing times and slower, though still polynomial, convergence.

In describing the algorithm we aimed for clarity rather than efficiency, with the sole constraint of providing a polynomial time algorithm. A more careful analysis will lead to reduced running time. It is worth noting a simple, but interesting, corollary of our results. If the algorithm is run concurrently by the agent and the adversary, where we consider stochastic games with stationary equilibrium, they are both guaranteed to attain near optimal performance, i.e., the value of the game (within the allowed error bounds). Finally, we remark that our algorithm would seem a natural candidate for learning in non-stochastic environment, although additional assumptions about the nature of the environment could be used to improve its efficiency.

Acknowledgement: We thank the anonymous reviewers for their useful comments. The first author was partially funded by the Paul Ivanier Center for Robotics Research and Produc­ tion Management.