for all states s. Second, this optimal value can be obtained by a stationary policy, i.e., by a policy that depends on the current stage-game only. In particular, in the case of CISGs, this optimal value can be obtained using a pure stationary strategy.

In a sense, there seems to be little point in theoretical discussions of learning in the context of MDPs and CISGs that are not ergodic. It is evident that in order to learn the agent must perform some sort of implicit or explicit exploration. If the MDP is not ergodic, the agent's initial choices can have irreversible consequences on its long-term value. But one cannot expect the agent to always make correct initial choices when it has no knowledge of the game.

Next, we wish to discuss the central parameter in the analysis of the complexity - the mixing time - first identified by Kearns and Singh (1998).  Kearns and Singh argue that it is unreasonable to refer to the efficiency of learning algorithms without referring to the efficiency of convergence to a desired value given complete information. They defined the e-return mixing time of a policy π (in an MDP) to be the smallest value of T such that for all t > T, and for any starting state s, the expected average reward of π is at least ε close to the expected infinite horizon average reward of π . That is, letting U ( s, π, t ) denote the expected t-step average reward of π starting at s, define U(π) = lim inf L →∞ U(s,π,t), where this latter value does not depend on the choice of s because of the ergodicity assumption.

The e-return mixing time of r, T satisfies:
T = min ∀ s, t ′ ≥ T ′ : U( s, π, t ′ ) > U( π ) − ε.

Notice that the mixing time has nothing to do with learning.  It is influenced by the stochastic nature of the model and its interaction with the policy - however obtained.

We adopt their definition, but with respect to the MDP induced by the CISG of interest.

Finally, we define a near-optimal polynomial-time learning algorithm for CISGs to be a learning algorithm A such that given a CISG M , some c > 0, γ > 0 and 0 < δ < 1, there exists some T > 0 that is polynomial in 1/ε, 1/δ, 1/γ, the ε-return mixing time of an optimal policy, and the size of the description of the game, such that for every t > T the actual t-step average reward obtained by A is at least (1 - γ)( v ( M ) - 2 c ), with a probability of at least 1 - 6.

Notice that the above definition requires that if we consider any particular, fixed t > T,
then the actual average reward will be close to optimal with an overwhelming probability.

## 3. The Algorithms The Following Is Our Basic Result:

Theorem 1 There exists an near-optimal polynomial time algorithm for learning in twoplayer CISGs under imperfect monitoring provided that all agents have a shared polynomial bound 2 on the number of actions of each other.

We note that in certain special sub-cases, e.g., under perfect monitoring, there will be no need for the multiplicative factor of 1 - γ