Efficient learning equilibrium.
We introduce efficient learning equilibrium (ELE), a normative approach to learning in noncooperative settings. In ELE, the learning algorithms themselves are required to be in equilibrium. In addition, the learning algorithms must arrive at a desired value after polynomial time, and a deviation from the prescribed ELE becomes irrational after polynomial time. We prove the existence of an ELE (where the desired value is the expected payoff in a Nash equilibrium) and of a Pareto-ELE (where the objective is the maximization of social surplus) in repeated games with perfect monitoring. We also show that an ELE does not always exist in the imperfect monitoring case. Finally, we discuss the extension of these results to general-sum stochastic games.
Introduction
Reinforcement learning in the context of multi-agent interaction has attracted the attention
of researchers in cognitive psychology, experimental economics, machine learning, articial
intelligence, and related elds for quite some time [13, 6]. Much of this work uses repeated
games [5, 8] and stochastic games [16, 15, 12, 2] as models of such interactions.
The literature on learning in games in game theory [8] is mainly concerned with the understanding
of learning procedures that if adopted by the dierent agents will converge at the
end to an equilibrium of the corresponding game. The game itself may be known; the idea is
to show that simple dynamics lead to rational behavior, as prescribed by a Nash equilibrium.
The learning algorithms themselves are not required to satisfy any rationality requirement;
it is what they converge to, if adopted by all agents that should be in equilibrium. When
facing uncertainty about the game that is played, game-theorists adopt a Bayesian approach.
The typical assumption in that approach is that there exists a probability distribution on
the possible games, which is common-knowledge. The notion of equilibrium is extended
to this context of games with incomplete information, and is treated as the appropriate
solution concept. In this context, agents are assumed to be rational agents adopting the
corresponding (Bayes-) Nash equilibrium, and learning is not an issue.
Our major claim is that the game-theoretic approach is not in line with the goals of
multi-agent reinforcement learning research in AI and must be modied. First, the Bayesian
approach used to model partial information is not in line with the common approach in theoretical
computer science and computational learning for dealing with uncertainty. Second,
the descriptive motivation underlying learning research in game-theory diers considerably
from the normative motivation for learning research in AI, and these dierences have important
ramications. We now explain these issues in more detail.
First, consider the Bayesian model of partial information. To date, most work in machine
learning, and in particular, work on single-agent reinforcement learning has taken a dierent
approach, motivated largely by work on online algorithms in computer science. Here, no
distribution is assumed over the uncertain entities, and instead, our goal is to approach
the behavior of an agent with complete information as closely and as quickly. Indeed, AI
researchers have adopted this non-Bayesian approach in their work on learning in games,
looking for algorithms that converge to an appropriate equilibrium in any game out of a
class of relevant games; and we follow suit.
However, researches in multi-agent reinforcement learning did choose to adopt other
assumptions made by game-theorists, despite the fact that here the dierences are much more
fundamental. Work on learning in games started with descriptive motivation in mind. That
is, its goal was to show that people who use simple heuristic rules for updating their behavior
in a multi-agent setting (i.e., in a game) will eventually adopt behavior that corresponds
to some appropriate equilibrium behavior. If that is the case, economic models based on
equilibria concepts are, in some sense, justied. The assumption that all agents use the
same learning rule is justied by the fact that all agents involved are people { i.e., they are
all designed similarly. But in AI we are not concerned with descriptive models of human
behavior { we are interested in designing articial agents. Except in the case of cooperative
systems, we have no reason to believe that agents designed by dierent designers will all
employ the same learning algorithms. Moreover, one should view the designer's choice of
learning algorithm for its agent as a fundamental decision, that should follow normative
criteria. Indeed, from the AI perspective, the choice of a learning algorithm is a basic action
we take in a game we play against other agent designers.
There is another related point. Game-theorists adopting the descriptive stance are not
too concerned with how quickly a learning rule leads to convergence { after all, we had ages
to evolve our behavior. But an agent designer wants its agent to learn quickly. He does
not care about its agent's \osprings." Thus, in AI, speed of convergence is of paramount
importance.
To better align the research methodology in multiagent reinforcement learning with the
AI perspective, we present in this paper a non-Bayesian normative approach to learning in
games. Our approach makes no assumptions about the distribution of possible games that
may be played { making it more re
ective of the setting studied in machine learning and AI
and in the spirit of work on on-line algorithms in computer science { and treats the choice of
a learning algorithm itself as a game. More specically, we adopt the framework of repeated
games, and view the learning algorithm as a strategy for an agent in a repeated game. This
strategy takes an action at each stage based on its previous observations, and initially has
no information about the identity of the game being played. Given the above, the following
are natural requirements for the learning algorithms provided to the agents:
1. Individual Rationality: The learning algorithms themselves should be in equilibrium.
It should be irrational for each agent to deviate from its learning algorithm, as long as
the other agents stick to their algorithms, regardless of what the actual game is.
2. E-ciency:
(a) A deviation from the learning algorithm by a single agent (while the others stick
to their algorithms) will become irrational (i.e. will lead to a situation where the
deviator's payo is not improved) after polynomially many stages.
(b) If all agents stick to their prescribed learning algorithms then the expected payo
obtained by each agent within a polynomial number of steps will be (close to)
the value it could have obtained in a Nash equilibrium, had the agents known the
game from the outset.
A tuple of learning algorithms satisfying the above properties for a given class of games
is said to be an E-cient Learning Equilibrium (ELE). Notice that the learning algorithms
should satisfy the desired properties for every game in a given class despite the fact that the
actual game played is initially unknown. Such assumptions are typical to work in machine
learning. What we borrow from the game theory literature is the criterion for rational
behavior in multi-agent systems. That is, we take individual rationality to be associated with
the notion of equilibrium. We also take the equilibrium of the actual (initially unknown)
game to be our benchmark for success; we wish to obtain a corresponding value although we
initially do not know which game is played.
The idea above constitutes the major conceptual contribution of this paper. In the
remaining sections we formalize the notion of e-cient learning equilibrium, and show that it
is not devoid of content, i.e., we prove the existence of an ELE for a general class of games
{ the class of repeated games with perfect monitoring. We also show that there are classes
of games in which an ELE does not exist. Then, we generalize our results to the context of
Pareto-ELE (where we wish to obtain maximal social surplus). We also discuss the extension
of our results to general-sum stochastic games. Technically speaking, the results we prove
rely on a novel combination of the so-called folk theorems in economics, and a novel e-cient
algorithm for the punishment of deviators in games which are initially unknown.
E-cient Learning Equilibrium: Denition
In this section we develop a denition of e-cient learning equilibrium in the context of
two-player repeated games. The generalization to n-player repeated games is immediate,
but requires additional notation, and will not be presented here. An extension to stochastic
games appears in Section 6.
A game is a model of multi-agent interaction. In a 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
payo vector, i.e., a vector of values, one for each of the players.
A common description of a (two-player) game is as a bi-matrix. This is called a game
in strategic form. 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. We make the simplifying assumption that the size of the action set of
both players is identical. The extension to sets of dierent sizes is trivial.
In a repeated game (RG) the players play a given game G repeatedly. We can view a
repeated game, with respect to a game G, as consisting of an innite number of iterations,
at each of which the players have to select an action in the game G. After playing each
iteration, the players receive the appropriate payos, as dictated by that game's matrix, and
move to the next iteration.
For ease of exposition we normalize both players' payos in the game G to be non-negative
reals between 0 and some positive constant R max . We denote this interval of possible payos
by
In a perfect monitoring setting, the set of possible histories of length t is
the set of possible histories, H, is the union of the sets of possible histories for all t  0,
where is the empty history. Namely, the history at time t consists of the history
of actions that have been carried out so far, and the corresponding payos obtained by the
players. Hence, in a perfect monitoring setting, a player can observe the actions selected
and the payos obtained in the past, but does not know the game matrix to start with. In
an imperfect monitoring setup, all that a player can observe following the performance of its
action is the payo it obtained and the action selected by the other player. The player cannot
observe the other player's payo. An even more constrained setting is that of strict imperfect
monitoring , where the player can observe its action and its payo alone. The denitions of
possible histories for an agent in both imperfect monitoring settings follow naturally.
Given an RG, a policy for a player is a mapping from H, the set of possible histories, to the
set of possible probability distributions over A. Hence, a policy determines the probability
of choosing each particular action for each possible history. Notice that a learning algorithm
can be viewed as an instance of a policy.
We dene the value for player 1 of a policy prole (; ), where  is a policy for player
1 and  is a policy for player 2, using the expected average reward criterion as follows:
Given an RG M and a natural number T , we denote the expected T -iterations undiscounted
average reward of player 1 when the players follow the policy prole (; ), by U 1
The denition for player 2 is similar. We dene U
2.
A policy prole (; ) is a learning equilibrium if
for every game matrix M (dened over the set A of actions, and the possible payos).
Our rst requirement, then, is that learning algorithms will be treated as strategies.
In order to be individually rational they should be the the best response for one another.
In addition, they should rapidly obtain a desired value. The identity of this desired value
may be a parameter. We now take a natural candidate, the Nash equilibrium of the game.
Another appealing alternative will be discussed later.
Assume we consider games with k actions, g. For every repeated game
be a Nash equilibrium of the (one-shot) game associated with
M , and denote by NV i (n(G)) the expected payo obtained by agent i in that equilibrium.
A policy prole (; ) is an e-cient learning equilibrium(ELE) if for every  > 0; 0 <
- < 1, there exists some T > 0, polynomial in 1
, and k, such that for every t  T and
game matrix G (and its corresponding RG, M ), U
for some Nash equilibrium n(G), and if player 1 deviates from  to  0 in iteration l, then
with a probability of failure of at most -. And
similarly, for player 2.
Notice that a deviation is considered irrational if it does not increase the expected payo
by more than . This is in the spirit of -equilibrium in game theory, and is done in order
to cover the case where the expected payo in a Nash equilibrium equals the probabilistic
maximin value. 1 In all other cases, the denition can be replaced by one that requires that
a deviation will lead to a decreased value, while obtaining similar results. We have chosen
the above in order to remain consistent with the game-theoretic literature on equilibrium
in stochastic contexts. Notice also, that for a deviation to be considered irrational, its
detrimental eect on the deviating player's average reward should manifest in the near
future, not exponentially far in the future.
The above captures the insight of a normative approach to learning in non-cooperative
setting. We assume that initially the game is unknown, but the agents will have learning
algorithms that will rapidly lead to the values the players would have obtained in a
Nash equilibrium had they known the game. Moreover, as mentioned earlier, the learning
algorithms themselves should be in equilibrium.
1 The probabilistic maximin value for player 1 is dened as
over the set of policies for players 1 and 2, respectively. The denition for player 2 is similar.
3 E-cient Learning Equilibrium: Existence
The denition of ELE is of lesser interest if we cannot provide interesting examples of ELE
instances. In this section we prove the following constructive result:
Theorem 1 There exists an ELE for any perfect monitoring setting.
Below we describe a concrete algorithm with this property. As we said earlier, it is based on
a combination of the so-called folk theorems in economics and a novel, e-cient punishment
mechanism which ensures the e-ciency of our approach. In the folk theorems (e.g., see [9]
and the extended discussion in [10]) the basic idea is that any strategy prole that leads to
payos that are greater than or equal to the security level (probabilistic maximin) values
that the agents can guarantee themselves can be obtained by directing the agents to use
the prescribed strategies, and telling each agent to punish the other agent if it turns out
to deviate from that behavior; the punishment remains a threat that will not be followed
in equilibrium and as a result the desired strategy prole will be executed. In order to use
this idea in our setting we need however to use a technique for punishing without (initially)
knowing the payo matrix; moreover we need to devise an e-cient punishment procedure
for that setting.
Recall that we consider a repeated game M , where at each iteration G is played. In what
follows, we often use the term agent to denote the player using the algorithm in question,
and the term adversary to denote the other player. Both players have a set
of possible actions.
Consider the following algorithm, termed the ELE algorithm.
The ELE algorithm:
Player 1 performs action a i one time after the other for k times for In parallel
to that player 2 performs the sequence of actions (a times.
If both players behave according to the above, a Nash equilibrium of the (now revealed)
game is computed, and the players behave according to the corresponding strategies
from that point on. When several Nash equilibria exist, one is selected by using a
shared selection algorithm.
If one of the players { whom we refer to as the adversary { deviates from the above,
the other player { whom we refer to as the agent , acts as follows: The agent replaces
its payos in G by the complements to R max of the adversary payos. Hence, the
agent will treat the game as a constant-sum game where its aim is to minimize the
adversary's payo. Notice that these payos might be unknown. Below we will use
G and M to refer to that modied game, and describe how the agent will go about
minimizing the adversary's payo:
Initialize: Construct the following model M 0 of the repeated game M , where the game G
is replaced by a game G 0 where all the entries in the game matrix are assigned the
rewards (R
In addition, we associate a boolean valued variable with each joint-action fassumed,knowng.
This variable is initialized to the value assumed.
Repeat:
Compute and Act: Compute the optimal probabilistic maximin of G 0 and execute
it.
Observe and update: Following each joint action do as follows: Let a be the action
the agent performed and let a 0 be the adversary's action. If (a; a 0 ) is performed
for the rst time, update the reward associated with (a; a 0 ) in G 0 , as observed,
and mark it known.
1 The ELE algorithm, when adopted by both players, is indeed an ELE.
Much of the proof of this theorem, which is non-trivial, rests on showing the agent's ability
to punish the adversary quickly. The details are presented in the Appendix.
4 Imperfect monitoring
The ELE algorithm of the previous section uses the agent's ability to view its adversary's
actions and payos. A natural question is whether this ability is required for the existence
of an ELE. In this section we show that in general, perfect monitoring is required, but there
are special classes of games in which an ELE exists with imperfect monitoring.
We start with the general case:
Theorem 2 An ELE does not always exist in the imperfect monitoring setting.
Proof:
In order to see the above consider the following games:
1. G1:

2. G2:
The payos obtained for a joint action in G1 and G2 are identical for player 1 and are
dierent for player 2.
The only equilibrium of G1 is where both players play the second action, leading to
(1,500). The only equilibrium of G2 is where both players play the rst action, leading to
(6,9). (these are unique equilibria since they are obtained by removal of strictly dominated
strategies)
Now, assume that an ELE exists, and look at the corresponding policies of the players in
that equilibrium. Notice that in order to have an ELE, we must visit the entry (6,9) most
of the times if the game is G2 and visit the entry (1,500) most of the times if the game is
otherwise, player 1 (resp. player 2) will not obtain high enough value in G2 (resp. G1),
since its other payos in G2 (resp. G1) are lower than that.
Given the above, it is rational for player 2 to deviate and pretend that the game is always
G1 and behave according to what the suggested equilibrium policy tells it to do in that case.
Since the game might be actually G1, and player 1 can not tell the dierence, player 2 will
be able to lead to playing the second action by both players for most times also when the
game is G2, increasing its payo from 9 to 10, contradicting ELE.
But while our approach is not Bayesian, it does not exclude the possibility that the agent
knows that it is participating in a game from a particular class. Thus, there may be classes
of repeated games for which an ELE exists. In particular, consider the class of repeated
common-interest games. These are repeated games M where the underlying game G is a
common-interest game, i.e., a game in which both players always receive identical payos.
In this setting our denition of imperfect and perfect monitoring denote the same setting
{ if the player knows its payo, it knows its adversary's payo as well. Thus, we examine
the case of strict imperfect monitoring . Recall that in this setting, the player knows only its
action and its payo.
Theorem 3 There exists ELE for the class of common-interest games under strict imperfect
monitoring.
Proof : The idea is quite simple and, surprisingly, has not been proposed before, while other,
more complex and less e-cient approaches have been proposed. It does require knowledge
of the number of actions available to each agent (or a polynomial bound on them). The
algorithm works as follows: First, the agents go through a series of random play. They do so
su-ciently many times to ensure that the probability that all joint-actions have been played
is greater than 1 -. During this phase, each agent maintains information about the best
payo obtained so far, and the action it used when this payo was rst obtained. Once the
exploration phase is over with, the agent plays this best action repeatedly.
This is a learning equilibria because the average reward this learning strategy leads to is
the maximal average reward for every agent. Thus, no agent has any motivation to deviate
from it. It is an ELE because a polynomial number of steps is required to attain this average
reward (see below) and any deviation will immediately reduce the average reward of the
agent. We need only a polynomial number of steps to approximately obtain the maximal
average reward because we need only O(k 4  log( k 2
steps of random play to ensure that all
joint-actions have been played with a probability of at least 1 -. This follows from the
following. Given large enough k, we get that the probability that after k 2 m trials the agents
will not play some previously unplayed joint action can be approximated by e m . Hence, we
get that after O(k 2 log( k 2
the probability we will not learn the outcome associated with a
new joint action can be approximated by -
. By repeating the process k 2 times we get the
desired result.
5 Pareto ELE
The previous sections dealt with ELE in the perfect and imperfect monitoring settings. In
both cases we were interested in having a learning procedure that will enable the agents
to obtain expected payos as the ones they would have obtained in a Nash equilibrium,
had they known the game. A more ambitious objective is the following. Let p i (a; b) denote
the payo for player i in the game in question when player 1 plays a and player 2 plays
b. We say that a pair of actions (a; b) is (economically) e-cient, if
That is, if the total payo for both agents is maximized. It is
easy to see that if all the agents can do is to choose an action in G, then there is no general
way to guarantee that agents will behave in an economically e-cient manner. This is due
to the fact that it may be the case that although (a; b) is the only economically e-cient
behavior, performing a (resp. b) by agent 1 (resp. 2) is irrational:
may be lower than the probabilistic maximin value that agent 1 (resp. 2) can guarantee
itself.
The classical approach in economics for dealing with economic (in)e-ciency is by introducing
side (monetary) payments. Formally, part of the strategy of agent i is a function
agent i is instructed to pay a certain amount of money to the other
agent as part of its strategy. 2 If an agent's reward is p and he is paid c (where c can be
positive, negative, or zero) then his utility is assumed to be type of utility
function is termed quasi linear). The sum, over all agents, of the monetary payments is
always 0, and, as a result, if the agents turn out to be using strategies that maximize u 1 +u 2
then they will also be economically e-cient.
Now we can dene the notion of a Pareto ELE. A Pareto ELE is similar to a Nash ELE,
but its aim is that the agents' behavior will be economically e-cient. Therefore, the two
distinctive aspects of Pareto ELE are:
1. We require that the agents will be able to get close to an e-cient outcome.
2. We allow side payments as part of the agents' behavior.
2 This is the denition in the perfect monitoring case. The denition in the imperfect monitoring case is
similar.
Suppose that we are considering games with k actions. For every repeated game M , let
be an economically e-cient joint action of the (one-shot) game associated
with M , and denote by PV i (M) the payo obtained by agent i in that joint action.
A policy prole (; ), which also allows side payments, is a Pareto e-cient learning
equilibrium if for every  > 0; 0 < - < 1, we have that there exists a T > 0, polynomial in
and k, such that for every t  T and game matrix G (dened over the actions in A), with
corresponding RG, M , U 1
if player 1 deviates from  to  0 in iteration l, then U 1 (M;
with a probability of failure of at most -. And similarly for player 2.
Theorem 4 There exists a Pareto-ELE for any perfect monitoring setting.
Proof
Consider the following algorithm that denes the policies and side payments for the
agents.
Player 1 performs k iterations of the action a i , for In parallel to that, player
2 performs the sequence of actions (a times.
Now, that the game is known to both agents, they compute the probabilistic maximin
values for agent 1 and agent 2. Denote the probabilistic maximin value of agent i by
and the payo it gets in the economically e-cient solution by e i . Without loss of
Choose r such that
paid rby player 1 when the e-cient solution is played then each player's total payo
is at least as high as his probabilistic maximin. This is easy to see by examining the
two cases: e 2
From now on the agents adopt the e-cient behavior with the above side-payments in
all following iterations. If several economically e-cient behaviors exist, some pre-determined
selection algorithm is used.
In case one of players (the adversary) deviates, either in the exploration stage or the following
state, the other player (the agent) will punish it as in the case of Nash ELE. It
will play as if its payos in the game are the the complements to R max of the adversary
payos.
The proof now follows the steps of the proof for the existence of ELE.
For the case of imperfect monitoring, the same result with respect to Nash-ELE hold
here.
Theorem 5 A Pareto ELE does not always exist in an imperfect monitoring setting.
6 Stochastic Games
Stochastic games provide a more general model of repeated multi-agent interactions. In a
stochastic game the players may be in one of nitely many states,
each state is associated with a game in strategic form. The joint action at each state not
only determines the payos but also determine (stochastically) the identity of the next state
the agents will reach. Formally, let be the set of actions available to the
agents. For each state s i , the game associated with s i associates a payo p i
agent
j when the joint action is (a; b). In addition, for every s i 2 S the probability that the next
state will be s j when the joint action is (a; b) is denoted by P
Now that we have multiple games, a policy  i for agent i associates a (possibly mixed)
action with every state and, potentially, a payment to the other agent. This policy is a
function of the history of states the agent visited and the payos it observed. Throughout
this section we assume the perfect monitoring setting, since our impossibility result for
imperfect monitoring in repeated games immediately rules out the existence of an ELE in
the more general context of stochastic games.
Stochastic games provide a more realistic, but also technically more challenging setting.
First, let us try and understand the issues involved. The rst obstacle we face is the lack
of general results on the existence of Nash equilibrium in average-reward stochastic games.
Thus, we restrict our attention to the case of Pareto-ELE. Conceptually, the required generalization
is straightforward { the learning algorithm should quickly lead to an economically
e-cient policy for both agents, i.e., a policy that maximizes the average sum of rewards,
and deviations should quickly lead to a lower reward. However, while in the case of repeated
games we equated \quick" with polynomial in the size of the game and the approximation
parameters  and -, the situation in stochastic games is more complicated. A parameter
that is typically used to assess the speed of convergence of a learning algorithm in stochastic
games is the -return mixing time [14, 3]. Intuitively, the -return mixing time of a policy is
the expected time it would take an agent that uses this policy to converge to a value that is
close to the value of the policy. Ideally, we would like a learning algorithm to attain the
optimal value in time polynomial in the -return mixing time of the optimal policy.
Formally, assume some xed stochastic game M , and let policy prole in
M . We denote the T -step average reward of this policy prole for agent i starting at state
. The -return mixing time of is the minimal T such that for all t > T
and all states s, we have that U(s;  Thus, after the policy prole
executed for T steps or longer, the agents' expected average sum of rewards will
be very close to their long-term average sum of rewards. Let (; ) be a policy prole that
maximizes min s U(s; ; ), and let T mix be its -return mixing time. The denition of Pareto
e-cient learning equilibrium in stochastic games is identical to that of repeated games,
except that T must be polynomial in T mix as well. Note that if the game is irreducible (i.e.,
for any xed policy prole, the induced Markov chain is ergodic), U(s; ; ) does not depend
on s.
We can show the following:
Theorem 6 Under the following assumptions a Pareto-ELE in stochastic games exists: (1)
The agents have perfect monitoring (2) T mix is known.
Proof : The intuitive idea behind the algorithm is identical to the case of repeated games
and so we elaborate only on the new issues. First, the agents run an algorithm for nding
a policy prole ;  that maximize U(; ). Next, they run an algorithm for nding the best
that each can accomplish on its own (i.e., assuming the other agent is trying to minimize
their average payo). From that point on they run the policy prole ; , adjusted with
appropriate side payments so that each agent receives more than the best it can accomplish
on its own, much like in the case of repeated games. At any point, if an agent deviates, the
other agent plays as if its goal is to minimize the other agent's average reward.
First, note that this learning algorithm is (-)Pareto-optimal. The long-term average sum
of rewards of this algorithm is -close to the optimal average sum of rewards, as desired. No
agent has an incentive to deviate at any stage because the side-payment structure guarantees
that it attain at least the value it could attain on its own. To show that this algorithm is a
Pareto-ELE, we also need to show that the value can be attained e-ciently and punishment
can be performed e-ciently. We do so by resorting to recent results on e-cient learning in
xed-sum stochastic games and common-interest stochastic games. First, to compute the
policies ;  that maximizes U(; ) we use the algorithm described in [4]. We refer the reader
there for more details. What we need to note here is that this algorithm learns the required
policy prole in polynomial time. Next, to compute the values each agent can attain on its
own we use R-max [3]. R-max is appropriate here because we are learning in a xed-sum
game. First, we do it for the xed sum game in which the rewards are based on agent 1's
rewards, and then with respect to the xed-sum game in which the rewards are based on
agent 2's rewards. We note that given some value T 0 as input, R-max will learn a T 0 -step
policy in time polynomial in T 0 and the other game parameters. This policy will be optimal
among all policies that mix in time T 0 . We shall take T . The average reward of this
policy will be used to compute the side payments structure as in the case of repeated games.
In any case, the average reward of the the policy prole ;  (suitably modied to include
the side payments) will be no lower than the value that each agent can receive on its own.
Thus, should an agent deviate from the above, we know that within T mix steps it will attain
a lower average reward, i.e., punishment can be carried out e-ciently.
Finally, note that there is a standard, though imperfect, technique for removing knowledge
of T mix in which we simply guess progressively higher values for T mix . We refer the
reader to [3] for the implications of this approach.
Most previous work on learning in games ts into one of the following two paradigms:
1. The study of learning rules that will lead to a Nash equilibrium (or other solution
concept) of a game [8].
2. The study of learning rules that will predict human behavior in non-cooperative inter-
actions, such as the ones modeled in repeated games [6].
While the approach taken in (2) has signicant merit for descriptive purposes, a normative
approach to learning should go beyond recommending behavior that will eventually lead to
some desired solution. The major issues one needs to face are:
1. The learning algorithms of the agents should be individually rational.
2. The learning algorithms should e-ciently converge to the desired values if employed
by the agents.
3. A deviation from the desired learning algorithm should become irrational after a short
period of time.
The concepts introduced in this paper address these issues. Both ELE and Pareto-ELE
provide new basic tools for learning in non-cooperative settings. Moreover, we have been
able to show constructive existence results for both ELE and Pareto-ELE in the context
of repeated games with perfect monitoring. We were also able to show that if we relax the
perfect monitoring assumption, the desired properties are impossible to obtain in the general
case. Pareto-ELE is an appealing concept in the context of stochastic games as well, and we
were able to extend our results to that context. Together, our concepts and results provide
a rigorous normative approach to learning in general non-cooperative interactions.
It is useful to contrast our approach with an important line of related work that features
algorithms that guarantee that an agent using them will attain a value which is approximately
equal to the value he would have attained had he known in advance how his adversary would
play. Algorithms along this line appear in e.g., [11] and in [7] (where special attention is
given to the issue of e-ciency). This latter result is truly in the spirit of on-line algorithms,
where our goal is to do as much as we can online as we would have been able to do o-
line. In this case, we attempt to react online to an adversary's behavior in a manner that
would be similar { in terms of our average payo { to the best we could have done had we
known the adversary's behavior before hand. These results are highly valuable, but many
readers may not notice a subtle, but crucial point about them: They treat the adversary's
policy as a xed sequence of mixed strategies (probabilistic actions), and that is contrary to
the spirit of game-theory. In reality, the adversary can adjust its policy in response to the
agent's behavior. Imagine, for example, the following instance of the well-known Prisoner's
Dilemma game:

Consider the following two adversary policies: (1) If the agent initially plays row 1 (denoted
cooperate) the adversary will always play column 1 (denoted cooperate, too). If the agent
initially plays row 2 (denoted defect) the adversary will always play column 2 (denoted defect ,
too). (2) If the agent initially plays cooperate the adversary will always play defect . If the
agent initially plays defect the adversary will always play cooperate. It is clear that no agent
can guarantee a best-response value against such an adversary, and this approach is limited
to a view of the adversary as using a (pre-determined) sequence of mixed strategies. The
bottom line is that, despite their practical and theoretical importance, these results cannot
replace concepts that are based on the notion of an equilibrium.
Another related work on normative guidelines to the design of learning algorithms is [1].
There, Bowling and Veloso suggest two criteria for learning algorithms. The rst, which they
call rationality stipulates that if the other player's policies converge to a stationary policy
then the learning algorithm will converge to the best-response policy. The second, which they
call convergence stipulates that the learner will necessarily converge to a stationary policy.
Both criteria are attractive, but as with the above work, the notion of a Nash-equilibrium of
learning strategies is a deeper notion of rationality than that of best-response upon conver-
gence. And convergence, though denitely desirable, ignores the issue of convergence rate.
Moreover, convergence, as specied, is not well dened. Indeed, in their work, Bowling and
Veloso consider the special (well-dened) case of convergence in self-play, i.e., when all agents
use the same algorithm. This is the standard notion of convergence adopted by most work on
learning in games uses. In fact, in the particular context of self-play investigated by Bowling
and Veloso, their requirements are equivalent to the requirement that the algorithm will
converge to a correlated equilibrium { a common property pursued by learning algorithms in
the game-theory literature. The concept of ELE provides a more rigorous notion of individually
rational learning strategies. Moreover, we believe that e-cient (i.e., polynomial time)
convergence rate should be an integral part of the denition of rationality. In many settings,
what happens after an exponential number of iterations is not of great interest. This applies
to the judgment of irrationality as well. An agent that makes an \irrational" choice that
leads to increased reward in the near future and decreased reward only after an exponential
number of steps does not seem too irrational.



--R

Rational and covergent learning in stochastic games.


Learning to coordinate e-ciently - a model based approach
The dynamics of reinforcement learning in cooperative multi-agent systems
Predicting how people play games: Reinforcement learning in games with unique strategy equilibrium.
Adaptive game playing using multiplicative weights.
The theory of learning in games.
The folk theorem in repeated games with discounting or with incomplete information.
Game Theory.
A reinforcement procedure leading to correlated equilibrium.

Reinforcement learning: A survey.

Markov games as a framework for multi-agent reinforcement learning
Stochastic Games.
--TR
The dynamics of reinforcement learning in cooperative multiagent systems
Distributed algorithmic mechanism design
Friend-or-Foe Q-learning in General-Sum Games
Multiagent Reinforcement Learning
Near-Optimal Reinforcement Learning in Polynominal Time
Using redundancy to improve robustness of distributed mechanism implementations
R-max - a general polynomial time algorithm for near-optimal reinforcement learning

--CTR
Jeffrey Shneidman , David C. Parkes, Specification faithfulness in networks with rational nodes, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada
David C. Parkes , Jeffrey Shneidman, Distributed Implementations of Vickrey-Clarke-Groves Mechanisms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.261-268, July 19-23, 2004, New York, New York
Yevgeniy Vorobeychik , Michael P. Wellman , Satinder Singh, Learning payoff functions in infinite games, Machine Learning, v.67 n.1-2, p.145-168, May       2007
Rob Powers , Yoav Shoham , Thuc Vu, A general criterion and an algorithmic framework for learning in multi-agent systems, Machine Learning, v.67 n.1-2, p.45-76, May       2007
Guido Boella , Leendert van der Torre, Enforceable social laws, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
Vincent Conitzer , Tuomas Sandholm, AWESOME: A general multiagent learning algorithm that converges in self-play and learns a best response against stationary opponents, Machine Learning, v.67 n.1-2, p.23-43, May       2007
stochastic games;repeated games;multi-agent learning;learning equilibrium;efficiency;ex-post equilibrium