probability of no less than 1 - δ the R-MAX algorithm will attain an expected return of Opt(Π(ε, T)) - 2ε within a number of steps polynomial in N, k, T, 1, and 1.

Recall that we rely heavily on the fact that R- MAX is deterministic for MDPs. This follows from the existence of a deterministic algorithm for generating an optimal T-step policy. Algorithms for generating an optimal T -step policy for an MDP are deterministic, except for the fact that at certain choice points, a number of actions may have the same value, and each choice is acceptable. In that case, one needs only generate an arbitrary ordering over the actions and always choose, e.g., the first action.  This is why in our algorithm the generation of a shared ordering over the actions plays an important role. Note that, without loss of generality, for MDPs we can restrict our attention to deterministic T- step policies. This fact is important in our case because our coordination algorithm would not work if mixed policies were required.

## References

Bowling, M., & Veloso, M. (2001). Rational and covergent learning in stochastic games. In Proceedings of the 17th International Joint Conference on Artificial Intelligence, pp.

1021-1026.

Brafman, R. I., & Tennenholtz, M. (2002). R-max –a general polynomial time algorithm for near-optimal reinforcement learning.  Journal of Machine Learning Research, 3, 213-231.

Claus, C., & Boutilier, C. (1997). The dynamics of reinforcement learning in cooperative multi-agent systems. In Proceedings of the Workshop on Multi-Agent Learning, pp.

602-608.

Hoffman, A., & Karp, R. (1966).  On Nonterminating Stochastic Games.  Management Science, 12 (5), 359–370.

Hu, J., & Wellman, M. (1998). Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm. In Proceedings of the Fifteenth International Conference on Machine Learning (ICML-98), pp. 1095–1100.

Kearns, M., & Singh, S. (1998). Near-optimal reinforcement learning in polynomial time.

In Int. Conf. on Machine Learning.

Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Proc. 11th Intl. Conf. on Machine Learning, pp. 157-163.

Littman, M. L. (2001). Friend-or-foe q-learning in general-sum games. In Proc. ICML'01. Shapley, L. (1953). Stochastic Games. In Proc. Nat. Acad. Scie. USA, Vol. 39, pp. 1095–
1100.

Wang, X., & Sandholm, T. (2002). Reinforcement learning to play an optimal nash equilibrium in team markov games. In Proc. 16th Conf. on Neural Information Processing Systems (NIPS'02).