Recall that in our setting, each state of the MDP corresponds to a stage-game and each action of the "agent" corresponds to a joint action of our group of agents.

R- MAX is a model-based algorithm. It maintains its own model M ′ of the real world model M . M ′ is initialized in an optimistic fashion by making the payoffs for every action in every state maximal. What is special about R-MAX is that the agent always does the best thing according to its current model, i.e., it always exploits. However, if this behavior leads to new information, the model is updated.

Because, initially, the model is inaccurate, exploitation with respect to it may turn out to be exploration with respect to the real model. This is a result of our optimistic initialization of the reward function. This initialization makes state-action pairs that have not been attempted many times look attractive because of the high payoff they yield.

Let c > 0, and let R max denote the maximal possible reward, i.e., R max = max s, a R ( s, a ).

For ease of exposition, we assume that T, the c-return mixing time of the optimal policy, is known.

Initialize:  Construct the following MDP model M ′ consisting of N +1 states, { so, s 1, . . . , s N +
and k actions, { α 1 , . . , α k } . Here, s 1 , . . , s N correspond to the real states, { α 1 , . . , α k } correspond to the real actions, and so is an additional fictitious state. Initialize R such that R(s,a) = Rmax for every state s and action a . Initialize tr(s,a,so) = 1 for all i = 0 , . . , N and for all actions a (and therefore, tr ( si, a, sj ) = 0 for all j ̸= 0). In addition, maintain the following information for each state-action pair: (1) a boolean value known/unknown, initialized to unknown; (2) the list of states reached by playing this action in this state, and how many times each state was reached; (3)
the reward obtained when playing this action in this state. Items 2 and 3 are initially empty.

## Repeat:

Compute and Act: Compute an optimal T-step policy for the current state, and execute it for T -steps or until some state-action pair changes its value to known.

Observe and update: Following each action do as follows: Let a be the action you performed and s the state you were in;

- If the action a is performed for the first time in s, update the reward asso­
ciated with (s, a), as observed.

- Update the set of states reached from s by playing a .

- If at this point your record of states reached from this entry contains K 1 = max(([^NTRmaz) 3 ], [-6ln 3 ( ππδατ)]) + 1 elements, mark this stateaction pair as known, and update the transition probabilities for this entry according to the observed frequencies.
The basic property of R-MAX is captured by the following theorem:
Theorem 2 Let M be an MDP with N states and k actions. Let 0 < δ < 1, and ε > 0 be constants. Denote the policies for M whose e-return mixing time is T by Π(ε,T), and denote the optimal expected return achievable by such policies by Opt(Π(ε,T)). Then, with