
## An Immediate Corollary Of Theorem 1 Is:

Corollary 1  There exists a near-optimal polynomial time algorithm for learning in CISGs under imperfect monitoring provided that all agents know that all stage games are coordination games. Proof: Coordination games are a special instance of CISGs. In particular, in these games we have an identical number of actions for all players, so ea player has a polynomial bound on the number of actions available to the other players.

The proof of Theorem 1 will proceed in stages using successively weaker assumptions.

The reduction will be from a particular multi-agent case to the case of single-agent learning in MDPs. The settings in the first cases is quite natural for a distributed system, whereas the latter cases make quite weak assumptions on the agents' knowledge of each other. To succeed in our proof, the single-agent learning algorithm to which the problem is reduced must have the following properties:

- It is a near-optimal polynomial time algorithm. That is, given ε > 0 and 0 < δ < 1, then with a probability of 1 - δ, the algorithm, when applied to an MDP, leads to an actual average payoff that is c-close to the optimal payoff for any t > T, where T is polynomial in 1/c, 1/g, the c-return mixing time, and the description of the MDP.

- The precise value of T can be computed ahead of time given ε, δ, the ε-return mixing time of the optimal policy, and the description of the MDP.

- The algorithm is deterministic. That is, given a particular history, the algorithm will always select the same action.
One such algorithm is R-MAX (Brafinan & Tennenholtz, 2002), described in detail in the Appendix. In order to make the presentation more concrete, and since, at the moment, R- MAX appears to be the only algorithm with these properties, we explicitly refer to it in the proof. However, any other algorithm with the above properties can be used instead.

We now proceed with the description of the reductions. Note: In Cases 1-5 below, we assume that the ε -return mixing time of an optimal policy, denoted by T mix is known. For example, in repeated games, T mix is 1. In stochastic games, on the other hand, T mix is ulikely to be known. However, this assumption is useful for later development. In Case 6, we remove this assumption using a standard technique. Finally, in all cases we assume that the learning accuracy parameters - e, o, and y - are known to all agents.

## Case 1:  Common Order Over Joint Actions.  This Case Is Handled By Reduction To The Single-Agent Case.

If all agents share an ordering over the set of joint actions in every stage game, then they can emulate the single-agent R-MAX algorithm on the induced MDP. This follows from the fact that R-MAX is deterministic. Thus, the agents start with an initially identical model. They all know which joint action a single-agent would execute initially, and so they execute their part of that joint action. Since all agents observe their own reward always. And because this is identical to all agents, the update of the model will be the same for all agents.  Thus, the model of all agents is always identical.  Therefore, in essence we