the desired payoff, and that the above inequality holds whenever m > [ 1 - [ 1 ] = [ 1 ] 2 ] [ 1 - [ 1 ] 2 ] [ 1 ] [ 2 ]
log( δ/ 2) ), which is polynomial in the problem parameters.

Next, consider the exploitation phases.  Given that we succeeded in the exploration phase, at some point in the exploitation phase we will execute an e-optimal policy for Q
iterations. If Q is sufficiently large, we can ensure that this will yield an actual average reward that is c-close to optimal with a probability that is larger than 1 - δ/2. Thus, each failure mode has less than δ/ 2 probability, and overall, the failure probability is less than δ.

Finally, we need to consider what is required to ensure that the average reward of this whole algorithm will be as high as we wanted. We know that during the Q exploration steps an c -close to optimal value is attained. However, there can be up to m - 1 repetitions of T-step iterations in which we obtain a lower expected reward. Thus, we must have that Q (v [ M ]= ε ] > (1 − γ)  (v ( M ) − ε ). This is satisfied if Q > 1 2mT which is still polynomial in the problem parameters. Case 5:  Shared polynomial bound on action-set sizes.   We repeat the technique used in Case 4, but for every chosen ordering over the agents, the agents systematically search the space of possible action-set sizes. That is, let Sizes be some arbitrary total ordering over the set of all possible action set sizes consistent with the action-set size bounds. The actual choice of Sizes is fixed and part of the agents' algorithm. Now, for each action sets size in Sizes, the agents repeat the exploration phase of Case 4, as if these were the true action sets sizes. Again, the agents stick to the action-set size and ordering of agents that led to the best expected payoff, and they will switch to the next best ordering and sizes if the average reward is lower than expected.

Let b be the agents' bound on their action sets sizes. The only difference between our case and Case 4 is that the initial exploration phase must be longer by a factor of b 2 , and that in the exploitation phase we will have to switch O(m · b 2 ) policies at most. In particular, we now need to attempt possible orderings for the b2 possibilities for the size of the joint actions set. Thus, the failure probabilities are treated as above, and Q needs to be increased so that Q ( 1 M ) - ε 1 > ( 1 − γ )  ( v ( M ) − ε ). Q remains polynomial in the problem parameters. Case 6:  Polynomial bound on action set sizes, unknown mixing time.   In this case we reach the setting discussed in Theorem 1 in its full generality. To handle it, we use the following fact:  R- MAX provides a concrete bound on the number of steps required to obtain nnon-optimal average reward for a given mixing time. Using this bound, we can provide a concrete bound for the running time of all the cases above, and in particular, Case 5. This enables us to use the standard technique for overcoming the problem of unknown mixing time that was used in E 3 (Kearns & Singh, 1998) and in R- MAX. Namely, the agents run the algorithm for increasing values of the mixing time.  For every fixed mixing time, we operate as in Case 4-5, but ensuring that we achieve a multiplicative factor of 1 - 7/2, instead of 1 - 7. Suppose that the correct mixing time is T. Thus, when the agents run the algorithm for an assumed mixing time t smaller than T , we expect an average reward lower than optimal, and we need to compensate for these losses when we get to T . These losses are bounded by the optimal value times the number of steps we acted sub-optimally. This nmber of steps is polynomial in the problem parameters. Suppose that when T is reached,