equilibria exist, there is no guarantee of convergence to an optimal equilibrium. (2) They are not known to be efficient - i.e., at best, they have convergence in the limit guarantees.  In addition, many of the algorithms make strong assumptions about the information obtained by the agents during the course of the game. In particular, the agents know what actions are available to each other in each stage of the game, and they can observe the choices made by the other agents. This latter assumption is called perfect monitoring in the game-theory literature. This is to be contrasted with imperfect monitoring in which it is assumed that each agent can only observe its own payoff, but it cannot observe the actions performed by the other players.

In this paper we show that using a simple model-based approach, we can provide algorithms with far better theoretical guarantees, and often, in more general settings than previous algorithms. More precisely, we provide a learning algorithm with polynomial-time convergence to a near-optimal value in stochastic common-interest games under imperfect monitoring. In the case of repeated games, our algorithm converges to the actual optimal value. The key to our result is a recent powerful learning algorithm, R-MAX (Brafman &
Tennenholtz, 2002). In particular, the following aspect of R- MAX plays a crucial role: it is a deterministic learning algorithm that guarantees polynomial-time convergence to nearoptimal value in the single-agent case. 1 We note that in our treatment of stochastic games we make the standard assumption that the state is fully observable. That is, the agents recognize the "situation" in which they are in at each point in time.

In the following section, we provide the necessary background on stochastic games. In Section 3, we discuss the basic algorithm and its particular variants. In Section 4 we conclude the paper with a discussion of some important variants: n-player common-interest stochastic games and repeated games. Because an understanding of R-MAX and its convergence properties is needed for a more complete picture of our results, we provide this information in the Appendix.

## 2. Background

We start with a set of standard definitions and a discussion of the basic assumptions of our aproach.

## 2.1  Game Definitions

A game is a model of multi-agent interaction. In a strategic form game, we have a set of players, each of whom chooses some action to perform from a given set of actions.  As a result of the players' combined choices, some outcome is obtained which is described numerically in the form of a payoff vector, i.e., a vector of values, one for each of the players.

We concentrate on two-player games. General n-person games can be treated similarly.

A common description of a two-player strategic-form game is in the form of a matrix.

The rows of the matrix correspond to player 1's actions and the columns correspond to player 2's actions.  The entry in row i and column j in the game matrix contains the rewards obtained by the players if player 1 plays his i th action and player 2 plays his j th action. The set of possible combined choices of the agents are called joint actions. Thus, 1. In fact, R-MAX converges in zero-sum stochastic games as well, but we will not need this capability.