Each history of length t in a game with perfect monitoring consists of a sequence of t tuples of the form (stage-game, joint actions, payoffs), followed by the last state reached. Thus, the set of possible histories of length t in a game with perfect monitoring is ( S × A 2 × P) t × S.  We denote the set of histories of any length in this setting by H p. Similarly, in the case of imperfect monitoring, each history is a sequence of tuples of the form ( stage-game, single-agent action, single-agent payoff), followed by the last state reached. Thus, the set of possible histories of length t in a game with imperfect monitoring is ( S × A × P ) f × S ,
and the set of possible histories in this setting is denoted Himp.

Given a CISG with imperfect monitoring (respectively, perfect monitoring), a policy for the agent is a mapping from H imp (respectively, H p ) to the set of possible probability distributions over A. Hence, a policy determines the probability of choosing each particular action for each possible history. A pure policy is a deterministic policy. A stationary policy is one in which the action is a function of the last state only.

In defining the value of a CISG, we treat it much like an MDP because the ultimate goal is to provide a coordinated strategy for the agents that will lead to the maximal reward. We use the average expected reward criterion. Given a CISG M and a natural number T ,
U(s, π, ρ, T) denotes the expected T-step undiscounted average reward when player 1 follows policy π and player 2 follows policy ρ starting from state s. The optimal T-step value for M starting at s is U ( s, T ) = max ( x, ρ ) U ( s, π, ρ, T ). We define U ( s ) = liminf τ→∞ U ( s, T ),
and refer to it as the value of s

## 2.2 Assumptions, Complexity And Optimality

The setting we consider is one in which agents have a common interest. We assume that these agents are aware of the fact that they have a common interest and that they know the number of agents that participate in this game. This is most natural in a distributed ssssem. Moreover, we assume that they all employ the same learning algorithm; this latter assumption is common to most work in coordination learning. It is quite natural if the agents are part of a distributed system, or if there exists a standard, commonly accepted algorithm for coordination learning.

We make a number of additional assumptions: First, we assume that the agent always recognizes the identity of the stage-game it reached, but not its associated payoffs and transition probabilities.  Second, we assume that the maximal possible reward, Rmax is known ahead of time. Finally, we restrict our attention to ergodic CISGs, which, in a sense, are the only class of CISGs for which the type of result we seek is possible. Kearns and Singh introduced the ergodicity assumption in the context of their E 3 algorithm for learning in MDPs (Kearns & Singh, 1998). A similar assumption was used by Hoffinan and Karp (1966) in the context of stochastic games, where it is referred to as irreducibility. An MDP is said to be ergodic if the Markov-chain obtained by fixing any pure stationary policy is ergodic. That is, if any state is reachable from any other state. We restrict our attention to CISGs whose induced MDP is ergodic.

Irreducible stochastic games and ergodic MDPs have a number of nice properties, as shown by Hoffman and Karp (1966). First, the maximal long-term average reward is independent of the starting state, implying that U ( s ) is actually independent of s . Thus, from now on we use v(M) to denote the optimal value of the game M, which is identical to U(s)