We note that much of the work on learning coordination to date has dealt with case 3 above in the more restricted setting of a repeated game.

Case 4: Known action set sizes.   What prevents us from using the approach of Case 2 is the lack of common ordering over the agents. We can deal with this problem as follows:  In an initial order exploration phase, each agent randomly selects an ordering over the agents and acts based on this ordering. This is repeated for m trials. The length of each trial is T ′ , where T ′ is such that R-MAX will return an actual average reward that is c-close to optimal after T ′ steps with a probability of at least 1 - δ/2, provided that an identical ordering was chosen by all agents. m is chosen so that with high probability in one of the trials all agents will choose the same ordering.

Once the order exploration phase is done, each agent selects the ordering that led to the best average reward in the order exploration phase and uses the policy generated for that ordering for Q steps. Q must be large enough to ensure that the losses during the order exploration phase are compensated for - an explicit form is given below. Hopefully, the chosen ordering is indeed identical. However, it may be that it was not identical but simply led to a good average reward in the order exploration phase. In the exploitation phase, it could however lead to lower average rewards. Therefore, while exploiting this policy, the agent checks after each step that the actual average reward is similar to the average reward obtained by this policy in the order exploration phase. T' is chosen to be large enough to ensure that a policy with c-return mixing time of T mix will, with high probability yield an actual reward that is c close to optimal. If the average is not as expected, then with high probability the chosen ordering is not identical for all agents.  Once this happens, the agents move to the next best ordering. Notice that such a change can take place at most m - 1 times.

Notice that whenever we realize in step T that the actual average reward is too low, a loss of at most R maz is generated. By choosing T ′ such that R maz < 5 , we get that we remain in the scope of the desired payoff (i.e., 2 c from optimal). The 1/m factor is needed because this error can happen at most m times.

We now show that Q and m can be chosen so that the running time of this algorithm is still polynomial in the problem parameters, and that the actual average reward will be e-close to optimal times 1 - γ with probability of at least 1 - δ. First, notice that the algorithm can fail either in the order exploration phase or in the exploitation phases. We will ensure that either failure occurs with a probability of less the 5/2.

Consider the order-exploration phase. We must choose m so that with probability of at least 1 - δ/2 an iteration occurs in which:
- An identical ordering is generated by all agents; - R- MAX leads to an e-close to optimal average reward.

In a two-player game, the probability of an identical ordering being generated by both agents is 1/2. With an appropriate, and still polynomial, choice of T ′ , the probability of R- MAX succeeding given an identical ordering is at least 1 - δ/2.  We now choose m so that
[1 - (1/2 (1 - 6/2))] m < 6/2, and this can be satisfied by an m that is polynomial in 6.

Notice that this bounds the failure probability in selecting the right ordering and obtaining