\documentclass[11pt]{article}

\usepackage{jair}
\usepackage{theapa}
\usepackage{times}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{color}
\usepackage{comment}

\newtheorem{theorem}{Theorem}
\newtheorem{fact}{Fact}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}

\newcommand\paragraphfirstline[1]{\par\medskip\noindent{\bf#1}}
\newcommand\proof[1][\blah]{\par\noindent{\ifx#1\blah\bf Proof. \else
\bf Proof (#1).\fi}}
\newcommand\proofsketch{\par\noindent{\bf Proof. }(Sketch)~}
\newcommand\example{\par\noindent{\bf Example }}

\def\BR{\mathop{\mathgroup\symoperators BR}\nolimits}
\def\SS{{\cal S}}
\def\KK{{\cal K}}
\def\AA{{\cal A}}
\def\VV{{\cal V}}
\def\qq{\quad\quad}
\def\argmax{\mathop{\rm argmax}}
\def\R{\mathbb R}
\newcommand\rPi{\overline\Pi}
\newcommand\rBR{\mathop{\mathgroup\symoperators
\overline{BR}}\nolimits}

\newcommand\fixit{\color{red}}

\newcommand\citejustauthor[1]{(\citeauthor{#1})}
\newcommand\citejustyear[1]{\citeyear{#1}}

\begin{document}

\title{Existence of Multiagent Equilibria with Limited Agents}

\author{%
\name Michael Bowling \email bowling@cs.ualberta.ca \\
\addr
Department of Computing Science, University of Alberta \\
Edmonton, Alberta, Canada, T6G 2E8 \\
\name Manuela Veloso \email mmv@cs.cmu.edu \\
\addr
Computer Science Department, Carnegie Mellon University \\
Pittsburgh PA, 15213-3891}

\jairheading{22}{2004}{353--384}{8/03}{12/04}
\ShortHeadings{Existence of Multiagent Equilibria}{Bowling \& Veloso}
\firstpageno{353}

\maketitle

\begin{abstract}
Multiagent learning is a necessary yet challenging problem as
multiagent systems become more prevalent and environments become more
dynamic.  Much of the groundbreaking work in this area draws on
notable results from game theory, in particular, the concept of Nash
equilibria.  Learners that directly learn an equilibrium obviously
rely on their existence.  Learners that instead seek to play optimally
with respect to the other players also depend upon equilibria since
equilibria are fixed points for learning.  From another perspective,
agents with limitations are real and common.  These may be undesired
physical limitations as well as self-imposed rational limitations,
such as abstraction and approximation techniques, used to make
learning tractable.  This article explores the interactions of these
two important concepts: equilibria and limitations in learning.  We
introduce the question of whether equilibria continue to exist when
agents have limitations.  We look at the general effects limitations
can have on agent behavior, and define a natural extension of
equilibria that accounts for these limitations.  Using this
formalization, we make three major contributions: (i) a counterexample
for the general existence of equilibria with limitations, (ii)
sufficient conditions on limitations that preserve their existence,
(iii) three general classes of games and limitations that satisfy
these conditions.  We then present empirical results from a specific
multiagent learning algorithm applied to a specific instance of
limited agents.  These results demonstrate that learning with
limitations is feasible, when the conditions outlined by our
theoretical analysis hold.
\end{abstract}

\section{Introduction}

Multiagent domains are becoming more prevalent as more applications
and situations require multiple agents.  Learning in these systems is
as useful and important as in single-agent domains, possibly more so.
Optimal behavior in a multiagent system may depend on the behavior of
the other agents.  For example, in robot soccer, passing the ball may
only be optimal if the defending goalie is going to move to block the
player's shot and no defender will move to intercept the pass.  This
challenge is complicated by the fact that the behavior of the other
agents is often not predictable by the agent designer, making learning
and adaptation a necessary component of the agent itself.  In
addition, the behavior of the other agents, and therefore the optimal
response, can be changing as they also adapt to achieve their own
goals.

Game theory provides a framework for reasoning about these strategic
interactions.  The game theoretic concepts of stochastic games and
Nash equilibria are the foundation for much of the recent research in
multiagent learning, 
\cite<e.g.,>{Littman94,HuWellman98,Greenwald02,02aij-wolf}.  A Nash
equilibrium defines a course of action for each agent, such that no
agent could benefit by changing their behavior.  So, all agents are
playing optimally, given that the other agents continue to play
according to the equilibrium.

From the agent design perspective, optimal agents in realistic
environments are not practical.  Agents are faced with all sorts of
limitations.  Some limitations may physically prevent certain
behavior, e.g., a soccer robot that has traction limits on its
acceleration.  Other limitations are self-imposed to help guide an
agent's learning, e.g., using a subproblem solution for advancing the
ball down the field.  In short, limitations prevent agents from
playing optimally and possibly from following a Nash equilibrium.

This clash between the concept of equilibrium and the reality of
limited agents is a topic of critical importance.  Do equilibria exist
when agents have limitations?  Are there classes of domains or classes
of limitations where equilibria are guaranteed to exist?  This article
introduces these questions and provides concrete answers.  In
particular, we introduce two models of limitations: {\em implicit
games} and {\em restricted policy spaces}.  We use these models to
demonstrate in two key counterexamples the threat that limitations
pose to the existence of equilibria.  We refine a sufficient condition
for the existence of equilibria, and use to prove existence in three
classes of games and limitations.  This analysis is peppered with
examples of applications of these results.  We conclude with an
empirical example of learning with limitations, and a brief survey of
related work.

The article is organized as follows.  Section~\ref{sec:sg} introduces
the stochastic game framework as a model for multiagent learning.  We
define the game theoretic concept of equilibrium, and examine the
dependence of current multiagent learning algorithms on this concept.
Section~\ref{sec:limitations} enumerates and classifies some common
agent limitations and presents two formal models incorporating the
effects of limitations into the stochastic game
framework. Section~\ref{sec:existence} is the major contribution of
the article, presenting both proofs of existence for certain domains
and limitations as well as counterexamples for others.
Section~\ref{sec:learning} gives an example of how these results
affect and relate to one particular multiagent learning algorithm.  We
present interesting results of applying a multiagent learning
algorithm in a setting with limited agents.  Section~\ref{sec:related}
compares our approach with other investigations of agent limitations
in the fields of game theory and artificial intelligence.  Finally,
Section~\ref{sec:conclusion} concludes with implications of this work
and future directions.

\section{Stochastic Games}
\label{sec:sg}
A {\em stochastic game} is a tuple
$(n, \SS, \AA_{1\ldots n}, T, R_{1\ldots n})$, 
where,
\begin{itemize}
\item $n$ is the number of agents, 
\item $\SS$ is a set of states, 
\item $\AA_i$ is the set of actions available to agent $i$ with
  $\AA$ being the joint action space, $\AA_1 \times \ldots \times \AA_n$,
\item $T$ is a transition function,
  $\SS \times \AA \times \SS \rightarrow [0, 1]$, such that,
\[
\forall s\in\SS\; \forall a\in\AA \qq \sum_{s'\in\SS} T(s, a, s') = 1,
\]
\item and $R_i$ is a reward function for the $i$th agent,
  $\SS\times \AA \rightarrow \R$.
\end{itemize}
This framework is very similar to the framework of a Markov Decision
Process (MDP).  Instead of a single agent, though, there are multiple
agents whose {\em joint action} determines the next state and rewards
to the agents.  The goal of an agent, as in MDPs, is to maximize its
long-term reward.  Notice, though, that each agent has its own
independent reward function that it is seeking to maximize.  The goal
of maximizing ``long-term reward'' will be made formal in
Section~\ref{sec:sg:formulations}.

Stochastic games can also be thought of as an extension of the concept
of matrix games to multiple states.  Two common matrix games are in
Figure~\ref{fig:game-mg}.  In these games there are two players; one
selects a row and the other selects a column of the matrix.  The entry
of the matrix they jointly select determines the payoffs.
Rock-Paper-Scissors in Figure~\ref{fig:game-mg}(a) is a zero-sum game,
where the column player receives the negative of the row player's
payoff.  In the general case (general-sum games; e.g., Bach or
Stravinsky in Figure~\ref{fig:game-mg}(b)) each player has an
independent matrix that determines its payoff.  Stochastic games,
then, can be viewed as having a matrix game associated with each
state.  The immediate payoffs at a particular state are determined by
the matrix entries $R_i(s, a)$.  After selecting actions and receiving
their rewards from the matrix game, the players are transitioned to
another state and associated matrix game, which is determined by their
joint action.  So stochastic games contain both MDPs (when $n = 1$)
and matrix games (when $|S| = 1$) as subsets of the framework.

\begin{table}[htb]
\abovedisplayskip 0pt
\belowdisplayskip 0pt
\[\arraycolsep1ex
\begin{array}{c@{\hspace{5ex}}c}
R_r(s_0,\cdot) = \left(\begin{array}{rrr} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{array}\right) &
R_r(s_0,\cdot) = \left(\begin{array}{rr}2 & 0 \\ 0 & 1\end{array}\right) \\[5ex]
R_c(s_0,\cdot) = \left(\begin{array}{rrr} 0 & 1 & -1 \\ -1 & 0 & 1 \\ 1 & -1 & 0 \end{array}\right) &
R_c(s_0,\cdot) = \left(\begin{array}{rr}1 & 0 \\ 0 & 2\end{array}\right) \\[3ex]
\mbox{(a) Rock-Paper-Scissors} &
\mbox{(b) Bach or Stravinsky}
\end{array}
\]
\caption{Two example matrix games.}
\label{fig:game-mg}
\end{table}

\subsection{Policies}
Unlike in single-agent settings, deterministic policies, which
associate a single action with every state, can often be exploited in
multiagent settings.  Consider Rock-Paper-Scissors as shown in
Figure~\ref{fig:game-mg}(a).  If the column player were to play any
action deterministically, the row player could win a payoff of one
every time.  This fact requires us to consider stochastic strategies
and policies.  A stochastic policy for player $i$, $\pi_i : \SS
\rightarrow PD(\AA_i)$, is a function that maps states to mixed
strategies, which are probability distributions over the player's
actions.  We use the notation $\Pi_i$ to be the set of all possible
stochastic policies available to player $i$, and $\Pi = \Pi_1
\times \ldots \times \Pi_n$ to be the set of joint policies of all the
players. We also use the notation $\pi_{-i}$ to refer to a particular
joint policy of all the players except player $i$, and $\Pi_{-i}$ to
refer to the set of such joint policies.  Finally, the notation
$\left<\pi_i, \pi_{-i}\right>$ refers to the joint policy where player
$i$ follows $\pi_i$ while the other players follow their policy from
$\pi_{-i}$.

In this work, we make the distinction between the concept of
stochastic policies and mixtures of policies.  A mixture of policies,
$\sigma_i : PD(\SS \rightarrow \AA_i)$, is a probability distribution
over the set of deterministic policies.  An agent following a mixture
of policies selects a deterministic policy according to its mixture
distribution at the start of the game and always follows this policy.
This difference is similar to the distinction between mixed strategies
and behavioral strategies in extensive-form games~\cite{Kuhn53}.  Our
work focuses on stochastic policies as they (i) are a more compact
representation requiring $|A_i||S|$ parameters instead of
$|A_i|^{|S|}$ parameters to represent the {\em complete} space of
policies, (ii) are the common notion of stochastic policies in
single-agent behavior
learning,~\cite<e.g.,>{Jaakkola94,SuttonEtAl00,NgParrKoller00}, and
(iii) do not require the artificial commitment to a single
deterministic policy at the start of the game, which can be difficult
to understand within a learning context.

\subsection{Reward Formulations}
\label{sec:sg:formulations}
There are a number of possible reward formulations in single-agent
learning that define the agent's notion of optimality.  These
formulations also apply to stochastic games.  We will explore two of
these reward formulations in this article: {\em discounted reward} and
{\em average reward}.  Although this work focuses on discounted
reward, many of our theoretical results also apply to average reward.

\paragraphfirstline{Discounted Reward.}
In the discounted reward formulation, the value of future rewards is
diminished by a discount factor $\gamma$.  Formally, given a joint
policy $\pi$ for all the agents, the value to agent $i$ of starting at
state $s\in\SS$ is,
\begin{eqnarray}
V_i^\pi(s) = \sum_{t=0}^\infty \gamma^t E\left\{r^t_i | s^0 =
s,\pi\right\},
\label{eqn:discounted-reward}
\end{eqnarray}
where $r^t_i$ is the immediate reward to player $i$ at time $t$ with
the expectation conditioned on $s$ as the initial state and the
players following the joint policy $\pi$.

In our formulation, we will assume an initial state, $s_0\in\SS$, is
given and define the goal of each agent $i$ as maximizing
$V_i^\pi(s_0)$.  This formulation differs from the usual goal in MDPs
and stochastic games, which is to {\em simultaneously} maximize the
value of all states.  We require this weaker goal since our
exploration into agent limitations makes simultaneous maximization
unattainable.\footnote{This fact is demonstrated later by the example
in Fact~\ref{thm:convex-sg-not-exist} in Section~\ref{sec:existence}.
In this game with the described limitation, if the column player
randomizes among its actions, then the row player cannot
simultaneously maximize the value of the left and right states.}  This
same distinction was required by Sutton and
colleagues~\citejustyear{SuttonEtAl00} in their work on parameterized
policies, one example of an agent limitation.

\paragraphfirstline{Average Reward.}
In the average reward formulation all rewards in the sequence are equally
weighted.  Formally, this corresponds to,
\begin{eqnarray}
V_i^\pi(s) = \lim_{T\rightarrow\infty}\sum_{t=0}^T {1\over
T}E\left\{r_i^t | s^0 = s,\pi\right\},
\label{eqn:average-reward}
\end{eqnarray}
with the expectation defined as in
Equation~\ref{eqn:discounted-reward}.  As is common with this
formulation, we assume that the stochastic game is {\em ergodic}.  A
stochastic game is ergodic if for all joint policies any state can be
reached in finite time from any other state with non-zero probability.
This assumption makes the value of a policy independent of the initial
state.  Therefore,
\[
\forall s, s' \in \SS \qq V_i^\pi(s) = V_i^\pi(s').
\]
So any policy that maximizes the average value from one state
maximizes the average value from all states.  These results along with
more details on the average reward formulation for MDPs are summarized
by Mahadevan~\citejustyear{Mahadevan96}.

\paragraphfirstline{}%
For either formulation we will use the notation $V_i^\pi$ to refer to
the value of the joint policy $\pi$ to agent $i$, which in either
formulation is simply $V_i^\pi(s_0)$, where $s_0$ can be any arbitrary
state for the average reward formulation.

\subsection{Best-Response and Equilibria}

Even with the concept of stochastic policies and well-defined reward
formulations, there are, in general, still no optimal policies that
are independent of the other players' policies.  We can, though,
define a notion of {\em best-response}.
\begin{definition} 
For a game, the {\em best-response function} for player $i$,
$\BR_i(\pi_{-i})$, is the set of all policies that are optimal given
the other player(s) play the joint policy $\pi_{-i}$.  A policy
$\pi_i$ is optimal given $\pi_{-i}$ if and only if,
\[
\forall \pi'_i\in\Pi_i\qq
  V^{\left<\pi_i, \pi_{-i}\right>}_i \ge
  V^{\left<\pi'_i, \pi_{-i}\right>}_i.
\]
\end{definition}
The major advancement that has driven much of the development of game
theory, matrix games, and stochastic games is the notion of a
best-response equilibrium, or {\em Nash equilibrium}~\cite{Nash50}.
\begin{definition}
A {\em Nash equilibrium} is a joint policy, $\pi_{i=1\ldots n}$, with
\[
\forall i=1,\ldots,n \qq \pi_i \in \BR_i(\pi_{-i}).
\]
\end{definition}
Basically, an equilibrium is a policy for each player where each is
playing a best-response to the other players' policies.  Hence, no
player can do better by changing policies given that all the other
players continue to follow the equilibrium policy.  What makes the
notion of an equilibrium interesting is that at least one, possibly
many, exist in all matrix games and most stochastic games.  This was
proven by Nash~\citejustyear{Nash50} for matrix games,
Shapley~\citejustyear{Shapley53} for zero-sum discounted stochastic
games, Fink~\citejustyear{Fink64} for general-sum discounted
stochastic games, and Mertens and
Neyman~\citejustyear{MertensNeyman81} for zero-sum average reward
stochastic games.  The existence of equilibria for general-sum average
reward stochastic games is still an open problem~\cite{FilarVrieze97}.

In the Rock-Paper-Scissors example in Figure~\ref{fig:game-mg}(a), the
only equilibrium consists of each player playing the mixed strategy
where all the actions have equal probability.  In the
Bach-or-Stravinsky example in Figure~\ref{fig:game-mg}(b), there are
three equilibria.  Two consist of both players selecting their first
action or both selecting their second.  The third involves both
players selecting their preferred cooperative action with probability
$2/3$, and the other action with probability $1/3$.

\subsection{Learning in Stochastic Games}
\label{sec:sg:learning}

Learning in stochastic games has received much attention in recent
years as the natural extension of MDPs to multiple agents.  The
Minimax-Q algorithm~\cite{Littman94} was the first reinforcement
learning algorithm to explicitly consider the stochastic game
framework.  Developed for discounted reward, zero-sum stochastic
games, the essence of the algorithm was to use Q-learning to learn the
values of joint actions.  The value of the next state was then
computed by solving for the value of the unique Nash equilibrium of
that state's Q-values.  Littman and
Szepesvari~\citejustyear{LittmanSzepesvari96} proved that under
usual exploration requirements for both players, Minimax-Q would
converge to the Nash equilibrium of the game, independent of the
opponent's play beyond the exploration requirement.  Other algorithms
have since been presented for learning in stochastic games.  We will
summarize these algorithms by broadly grouping them into two
categories: {\em equilibrium learners} and {\em best-response
learners}.  The main focus of this summarization is to demonstrate how
the existence of equilibria under limitations is a critical question
to existing algorithms.

\paragraphfirstline{Equilibrium Learners.} 
Minimax-Q has been extended in many different ways.
Nash-Q~\cite{HuWellman98}, Friend-or-Foe-Q~\cite{Littman01-ffq}, and
Correlated-Q~\cite{Greenwald02} are all variations on this same theme
with different restrictions on the applicable class of games or the
exact notion of equilibrium learned.  All of the algorithms, though,
seek to learn an equilibrium of the game directly, by iteratively
computing intermediate equilibria.  Some of the algorithms have
theoretical guarantees of convergence to equilibrium play, others have
empirical results to this effect.  Like Minimax-Q, though, the
policies learned are independent of the play of the other agents
beyond exploration requirements.  We refer collectively to these
algorithms as {\em equilibrium learners}.  What is important to
observe is that these algorithms depend explicitly on the existence of
equilibria.  If an agent or agents were limited in such a way so that
no equilibria existed then these algorithms would be, for the most
part, ill-defined.\footnote{It should be noted that in the case of
Minimax-Q, the algorithm and solution concept are still well-defined.
A policy that maximizes its worst-case value may still exist even if
limitations make it such that no equilibria exist.  But, this minimax
optimal policy might not necessarily be part of an equilibrium.
Later, in Section~\ref{sec:existence},
Fact~\ref{thm:convex-sg-not-exist}, we present an example of a
zero-sum stochastic game and agent limitations where the minimax
optimal policies exist but do not comprise an equilibrium.}

\paragraphfirstline{Best-Response Learners.} 
Another class of algorithms is the class of{\em best-response
learners}.  These algorithms do not explicitly seek to learn an
equilibrium, instead seeking to learn best-responses to the other
agents.  The simplest example of one of these algorithms is
Q-learning~\cite{Watkins89}.  Although not an explicitly multiagent
algorithm, it was one of the first algorithms applied to multiagent
environments~\cite{Tan93,SenEtAl94}.  Another less naive best-response
learning algorithm is WoLF-PHC~\cite{02aij-wolf}, which varies the
learning rate to account for the other agents learning simultaneously.
Other best-response learners include Fictitious
Play~\cite{Robinson51,Vrieze87}, Opponent-Modeling
Q-Learning~\cite{UtherVeloso97}, Joint Action
Learners~\cite{ClausBoutilier98}, and any single-agent learning
algorithm that learns optimal policies.  Although these algorithms
have no explicit dependence on equilibria, there is an important
implicit dependence.  If algorithms that learn best-responses converge
when playing each other, then it must be to a Nash
equilibrium~\cite{02aij-wolf}.  Therefore, all learning fixed points
are Nash equilibria.  In the context of agent limitations, this means
that if limitations cause equilibria to not exist, then best-response
learners could not converge.

This nonexistence of equilibria is exactly one of the problems faced
by Q-learning in stochastic games.  Q-learning is limited to
deterministic policies.  The deterministic policy limitation can, in
fact, cause no equilibria to exist (see Fact~\ref{thm:not-exist} in
Section~\ref{sec:existence}.)  So there are many games for which
Q-learning cannot converge when playing with other best-response
learners, such as other Q-learners.

\paragraphfirstline{}%
In summary, both equilibrium and best-response learners depend, in
some way, on the existence of equilibria.  The next section explores
agent limitations that are likely to be faced in realistic learning
situations.  In Section~\ref{sec:existence}, we then present our main
results examining the effect these limitations have on the existence
of equilibria, and consequently on both equilibrium and best-response
learners.

\section{Limitations}
\label{sec:limitations}

The solution concept of Nash equilibrium depends on all the agents
playing optimally.  From the agent development perspective, agents
have limitations that prevent this from being a reality.  The working
definition of limitation in this article is {\em anything that can
restrict the agent from learning or playing optimal policies}.
Broadly speaking, limitations can be classified into two categories:
physical limitations and rational limitations.  Physical limitations
are those caused by the interaction of the agent with its environment
and are often unavoidable.  Rational limitations are limitations
specifically chosen by the agent designer to make the learning problem
tractable, either in memory or time.  We briefly explore some of these
limitations informally before presenting a formal model of limitations
that attempts to capture their effect within the stochastic game
framework.

\subsection{Physical Limitations}
One obvious physical limitation is that the agent simply is broken.  A
mobile agent may cease to move or less drastically may lose the use of
one of its actuators preventing certain movements.  Similarly, another
agent may appear to be ``broken'' when in fact the motion is simply
outside its capabilities.  For example, in a mobile robot environment
where the ``rules'' allow robots to move up to two meters per second,
there may be a robot that is not capable of reaching that speed.  An
agent that is not broken, may suffer from poor control where its
actions are not always carried out as desired, e.g., due to poorly
tuned servos, inadequate wheel traction, or high system latency.

Another common physical limitation is hardwired behavior.  Most agents
in dynamic domains need some amount of hard-wiring for fast response
and safety.  For example, many mobile robot platforms are programmed
to immediately stop if an obstacle is too close.  These hardwired
actions prevent certain behavior by the agent, which is often unsafe
but is potentially optimal.

Sensing is a common area of agent limitations containing everything
from noise to partial observability.  Here we'll mention just one
broad category of sensing problems: state aliasing.  This occurs when
an agent cannot distinguish between two different states of the world.
An agent may need to remember past states and actions in order to
properly distinguish the states, or may simply execute the same
action in both states.

\subsection{Rational Limitations}
Rational limitations are a requirement for agents to learn in even
moderately sized problems.  Techniques for making learning scale,
which often focus on near-optimal solutions, continue to be proposed
and investigated in single-agent learning.  They are likely to be even
more necessary in multiagent environments which tend to have larger
state spaces.  We will examine a few specific methods.

In domains with sparse rewards one common technique is reward shaping,
\cite<e.g.,>{Mataric94}.  A designer artificially rewards the agent for
actions the designer believes to be progressing toward the sparse
rewards.  These additional rewards can often speed learning by
focusing exploration, but also can cause the agent to learn suboptimal
policies.  For example, in robotic soccer moving the ball down the
field is a good heuristic for goal progression, but at times the
optimal goal-scoring policy is to pass the ball backward to an open
teammate.

Subproblem reuse also has a similar effect, where a subgoal is used in
a portion of the state space to speed learning, 
\cite<e.g.,>{Hauskrecht98,ijcai99-subproblem}.
These subgoals, though, may not be optimal for the global problem and
so prevent the agent from playing optimally.  Temporally abstract
options, either provided~\cite{SuttonPrecupSingh98} or
learned~\cite{McGovernBarto01,Uther02}, also enforce a particular
sub-policy on a portion of the state space.  Although in theory, the
primitive actions are still available to the agents to play optimal
policies, in practice abstraction away from primitive actions is often
necessary in large or continuous state spaces.

Parameterized policies are receiving a great deal of attention as a
way for reinforcement learning to scale to large problems, 
\cite<e.g.,>{Williams93,SuttonEtAl00,BaxterBartlett00}.
The idea is to give the learner a policy that depends on far less
parameters than the entire policy space actually would require.
Learning is then performed in the smaller space of parameters using
gradient techniques.  Parameterized policies simplify and speed
learning at the expense of possibly not being able to represent the
optimal policy in the parameter space.

\subsection{Models of Limitations}
This enumeration of limitations shows that there are a number and
variety of limitations with which agents may be faced, and they cannot
be realistically avoided.  In order to understand their impact on
equilibria, we model limitations formally within the game
theoretic framework.  We introduce two models that capture broad
classes of limitations: {\em implicit games} and {\em restricted
policy spaces}.

\paragraphfirstline{Implicit Games.}
Limitations may cause an agent to play suboptimally, but it may be
that the agent {\em is} actually playing optimally in a different
game.  If this new game can be defined within the stochastic game
framework we call this the {\em implicit game}, in contrast to the
original game called the {\em explicit game}.  For example, reward
shaping adds artificial rewards to help guide the agent's search.
Although the agent is no longer learning an optimal policy in the
explicit game, it is learning an optimal policy of some game,
specifically the game with these additional rewards added to that
agent's $R_i$ function.  Another example is due to broken actuators
preventing an agent from taking some action.  The agent may be
suboptimal in the explicit game, while still being optimal in the
implicit game defined by removing these actions from the agent's
action set, $A_i$.  We can formalize this concept in the following
definition.
\begin{definition}
Given a stochastic game 
$(n, \SS, \AA_{1\ldots n}, T, R_{1\ldots n})$
the tuple 
$(n, \SS, \hat\AA_{1\ldots n}, \hat T, \hat R_{1\ldots n})$
is an implicit game if and only if it is itself a stochastic
game and there exist mappings,
\[
\tau_i : \SS \times \hat\AA_i \times \AA_i \rightarrow [0, 1],
\]
such that,
\[
\forall s, s'\in\SS\; \forall \hat a_i \in \hat\AA_i \qq
  \hat T(s, \left<\hat a_i\right>_{i=1\ldots n}, s') =  
  \sum_{a\in\AA} \Pi_{i=1}^{n} \tau_i(s, \hat a_i, a_i)\;
  T(s, \left<a_i\right>_{i=1\ldots n}, s').
\]
The $\tau_i$'s are mappings from the implicit action space into
stochastic actions in the explicit action space.
\end{definition}
The $\tau_i$ mappings insure that, for each player, the choices
available in the implicit game are a restriction of the choices in the
explicit game.  In other words, for any policy in the implicit game,
there exists an equivalent, possibly stochastic policy, in the explicit
game.

Reward shaping, broken actuators, and exploration can all be captured
within this model.  For reward shaping the implicit game is $(n, \SS,
\AA_{1\ldots n}, T, \hat R_{1\ldots n})$, where $\hat R_i$ adds the
shaped reward into the original reward, $R_i$.  In this case the
$\tau$ mappings are just the identity, 
\[
\tau_i(s, a, a') = 
  \left\{ \begin{array}{ll} 1 & \mbox{if $a = a'$} \\ 
                             0 & \mbox{otherwise} \end{array}\right..
\]
For the broken actuator example, let $a^0_i\in\AA_i$ be some null
action for agent $i$ and let $a^b_i\in\AA_i$ be some broken action for
agent $i$ that under the limitation has the same effect as the null
action.  The implicit game, then, is $(n, \SS, \AA_{1\ldots n}, \hat
T, \hat R_{1\ldots n})$, where,
\begin{eqnarray*}
\hat T(s, a, s') &=& \left\{
  \begin{array}{ll} T(s, \left<a^0_i, a_{-i}\right>, s') & 
    \mbox{if $a_i = a^b_i$} \\
   T(s, a, s') & \mbox{otherwise} \end{array}
   \right. \\
\hat R(s, a) &=& \left\{
  \begin{array}{ll} R(s, \left<a^0_i, a_{-i}\right>) & 
    \mbox{if $a_i = a^b_i$} \\
   R(s, a) & \mbox{otherwise} \end{array}
   \right.,
\end{eqnarray*}
and,
\[
\tau_i(s, a) = \left\{ 
  \begin{array}{ll} a^0_i & \mbox{if $a = a^b_i$} \\ 
  a & \mbox{otherwise} \end{array}
  \right..
\]
For $\epsilon$-exploration, as with broken actuators, only $\hat T$
and $\hat R$ need to be defined.  They are just the $\epsilon$
combination of $T$ or $R$ with the transition probabilities or reward
values of selecting a random action.

Limitations captured by this model can be easily analyzed with respect
to their effect on the existence of equilibria.  We now restrict
ourselves to discounted reward stochastic games, where equilibria
existence is known.  Using the intuitive definition of an equilibrium
as a joint policy such that ``no player can do better by changing
policies,'' an equilibrium in the implicit game achieves this
definition for the explicit game.  Since all discounted reward
stochastic games have at least one equilibrium, so must the implicit
game, which is also in this class.  This equilibrium for the implicit
game is then an equilibrium in the explicit game given that the agents
are limited.

On the other hand, many of the limitations described above cannot be
modeled in this way.  None of the limitations of abstraction,
subproblem reuse, parameterized policies, or state aliasing lend
themselves to being described by this model.  This leads us to our
second, and in many ways more general, model of limitations.

\paragraphfirstline{Restricted Policy Spaces.}
The second model is that of {\em restricted policy spaces}, which
models limitations as restricting the agent from playing certain
policies.  For example, an $\epsilon$-exploration strategy restricts
the player to policies that select all actions with some minimum
probability.  Parameterized policy spaces have a restricted policy
space corresponding to the space of policies that can be represented
by their parameters.  We can define this formally.
\begin{definition}
A {\em restricted policy space} for player $i$ is a non-empty and
compact subset, $\rPi_i \subseteq \Pi_i$, of the complete space of
stochastic policies.
\end{definition}
The assumption of compactness\footnote{Since $\rPi_i$ is a subset of a
bounded set, the requirement that $\rPi_i$ is compact merely adds that
the limit point of any sequence of elements from the set is also in
the set.} may at first appear strange, but it is not particularly
limiting, and is critical for any equilibrium analysis.

It should be straightforward to see that parameterized policies, state
aliasing (with no memory), and subproblem reuse, as well as
exploration and broken actuators all can be captured as a restriction
on policies the agent can play.  Therefore they can be naturally
described as restricted policy spaces.  On the other hand, the
analysis of the existence of equilibria under this model is not at all
straightforward.  Since restricted policy spaces capture most of the
really interesting limitations we have discussed, this is precisely
the focus of the rest of this article.

\paragraphfirstline{}%
Before moving on to this analysis, we summarize our enumeration of
limitations in Table~\ref{tab:limitations}.  The limitations that we
have been discussing are listed as well as denoting the model that most
naturally captures their effect on agent behavior.

\begin{table}
\def\X{\checkmark}
\begin{center}
\begin{tabular}{|l|c|c|} \hline
{\bf Physical Limitations} & {\bf Implicit Games} & {\bf Restricted Policies} \\\hline
Broken Actuators   & \X & \X \\
Hardwired Behavior & \X & \X \\
Poor Control       & \X & \X \\
State Aliasing     &    & \X \\ \hline
{\bf Rational Limitations} & {\bf Implicit Games} & {\bf Restricted Policies} \\\hline
Reward Shaping or Incentives & \X &    \\
Exploration                  & \X & \X \\
State Abstraction/Options    &    & \X \\
Subproblems                  &    & \X \\
Parameterized Policy         &    & \X \\\hline
\end{tabular}
\end{center}
\caption{Common agent limitations.  
The column check-marks correspond to whether the limitation can be
modeled straightforwardly using implicit games and/or restricted policy
spaces.}
\label{tab:limitations}
\end{table}

\section{Existence of Equilibria}
\label{sec:existence}

\begin{comment}
Since the existence of equilibria is critical to multiagent learning
algorithms, and limitations are common and unavoidable it remains to
examine the effect that limitations have on equilibria.  Limitations
that can be modeled as implicit games, as stated earlier, do preserve
the existence of equilibria.  The model of restricted policy spaces,
though, does not have as simple an answer.
\end{comment}

In this section we define
formally the concept of a {\em restricted equilibrium}, which account for
agents' restricted policy spaces.  We then carefully analyze what can
be proven about the existence of restricted equilibria.  The results
presented range from somewhat trivial examples
(Facts~\ref{thm:not-exist},
\ref{thm:singleton-eq}, \ref{thm:nash-is-eq}, 
and~\ref{thm:equilibria-not-nash}) and applications of known results
from game theory and basic analysis (Theorems~\ref{thm:convex-mg} and
\ref{thm:team-game}) to results that we believe are completely new
(Theorems~\ref{thm:statewise-convex},
\ref{thm:no-control}, and~\ref{thm:single-controller}), as well as a
critical counterexample to the wider existence of restricted
equilibria (Fact~\ref{thm:convex-sg-not-exist}).  But all of the
results are in a sense novel since this specific question has received
no direct attention in the game theory nor the multiagent learning
literature.

\subsection{Restricted Equilibria}
We begin by defining the concept of an equilibrium under the model of
restricted policy spaces.  First we need a notion of best-response
that accounts for the players' limitations.
\begin{definition}
A {\em restricted best-response} for player $i$,
$\rBR_i(\pi_{-i})$, is the set of all policies from $\rPi_i$ that
are optimal given the other player(s) play the joint policy
$\pi_{-i}$.
\end{definition}
We can now use this to define an equilibrium.
\begin{definition}
A {\em restricted equilibrium} is a joint policy, $\pi_{i=1\ldots n}$,
where,
\[
\pi_i \in \rBR_i(\pi_{-i}).
\]
\end{definition}
Hence, no player can do better by changing policies given that all the
other players continue to follow the equilibrium policy, and the
player can only switch to policies within their restricted policy
space.

\subsection{Existence of Restricted Equilibria}
We can now state some results about when equilibria are preserved by
restricted policy spaces, and when they are not.  Unless otherwise
stated (as in Theorems~\ref{thm:statewise-convex} and
\ref{thm:single-controller}, which only apply to discounted reward),
the results presented here apply equally to both the discounted reward
and the average reward formulations.  We will
separate the proofs for the two reward formulations when needed.  The
first four facts show that the question of the existence of restricted
equilibria does not have a trivial answer.

\begin{fact}\label{thm:not-exist}
Restricted equilibria do not necessarily exist.
\end{fact}

\proof
Consider the Rock-Paper-Scissors matrix game with players restricted
to the space of deterministic policies.  There are nine joint
deterministic policies, and none of these joint policies are
an equilibrium.\hfill$\Box$

\begin{fact}\label{thm:singleton-eq}
There exist restricted policy spaces such that restricted equilibria
exist.  
\end{fact}

\proof
One trivial restricted equilibrium is in the case where all agents
have a singleton policy subspace.  The singleton joint policy
therefore must be a restricted equilibrium.\hfill$\Box$

\begin{fact}\label{thm:nash-is-eq}
If $\pi^*$ is a Nash equilibrium and $\pi^* \in
\rPi$, then $\pi^*$ is a restricted equilibrium.
\end{fact}

\proof
If $\pi^*$ is a Nash equilibrium, then we have
\[
\forall i\in \{1\ldots n\}\; \forall\pi_i\in\Pi_i \qq
V^{\pi^*}_i \ge V^{\left<\pi_i, \pi^*_{-i}\right>}_i.
\]
Since $\rPi_i \subseteq \Pi_i$, then we also have
\[
\forall i\in \{1\ldots n\}\; \forall\pi_i\in\rPi_i \qq
V^{\pi^*}_i \ge V^{\left<\pi_i, \pi^*_{-i}\right>}_i,
\]
and thus $\pi^*$ is a restricted equilibrium.
\hfill$\Box$

On the other hand, the converse is not true; not all restricted
equilibria are of this trivial variety.
\begin{fact}\label{thm:equilibria-not-nash}
There exist non-trivial restricted equilibria that are neither Nash
equilibria nor come from singleton policy spaces.
\end{fact}

\proof
Consider the Rock-Paper-Scissors matrix game from
Figure~\ref{fig:game-mg}.  Suppose the column player is forced, due
to some limitation, to play ``Paper'' exactly half the time, but is
free to choose between ``Rock'' and ``Scissors'' otherwise.  This is a
restricted policy space that excludes the only Nash equilibrium of the
game.  We can solve this game using the implicit game model, by giving
the limited player only two actions, 
$s_1 = (0.5, 0.5, 0)$ and $s_2 = (0, 0.5, 0.5)$, 
which the player can mix between.  This is depicted
graphically in Figure~\ref{fig:rps-implicit-game}.  We can solve
the implicit game and convert the two actions back to actions of the
explicit game to find a restricted equilibrium.  Notice this
restricted equilibrium is not a Nash equilibrium.\hfill$\Box$

\begin{figure}[htb]
\centerline{\includegraphics[width=2.25in]{figures/rps-limit-ex}}
\[
\begin{array}{lc@{\hspace{0.75in}}c}
 & \mbox{Explicit Game} & \mbox{Implicit Game} \\\cline{2-3} \\[-1ex]
\mbox{Payoffs} &
\left(\begin{array}{rrr} 0 & -1 & 1 \\[0.5ex] 1 & 0 & -1 \\[0.5ex] -1 & 1 & 0 
\end{array}\right) &
\left(\begin{array}{rr} -\frac{1}{2} & 0\\[0.5ex] \frac{1}{2} & -\frac{1}{2} \\[0.5ex] 0 & \frac{1}{2}  
\end{array}\right) \\[5ex]

\mbox{Nash Equilibrium} &
\left<\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\right>, \left<\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\right> &
\left<0, \frac{1}{3}, \frac{2}{3}\right>, \left<\frac{2}{3}, \frac{1}{3}\right> \\[2ex]

\mbox{Restricted Equilibrium} &
\multicolumn{2}{c}{\left<0, \frac{1}{3}, \frac{2}{3}\right>, \left<\frac{1}{3}, \frac{1}{2}, \frac{1}{6}\right>}
\end{array}
\]
\caption{Example of a restricted equilibrium that is not a Nash
equilibrium.  Here, the column player in Rock-Paper-Scissors is
restricted to playing only linear combinations of the strategies 
$s_1= \left<\frac{1}{2}, \frac{1}{2}, 0\right>$ and 
$s_2 = \left<0,\frac{1}{2}, \frac{1}{2} \right>$.}
\label{fig:rps-implicit-game}
\end{figure}

Notice that the Fact~\ref{thm:equilibria-not-nash} example has a
convex policy space, i.e., all linear combinations of policies in the
set are also in the set.  Also, notice that the
Fact~\ref{thm:not-exist} counterexample has a non-convex policy space.
These examples suggest that restricted equilibria may exist as long as
the restricted policy space is convex.  The convexity restriction is,
in fact, sufficient for matrix games.
\begin{theorem}\label{thm:convex-mg}
When $|S| = 1$, i.e. in matrix games, if $\rPi_i$ is convex, then there
exists a restricted equilibrium.
\end{theorem}
The proof is based on an application of Rosen's theorem for concave
games~\cite{Rosen65} and is included in Appendix~\ref{app:convex-mg}.
Surprisingly, the convexity restriction is not sufficient for
stochastic games.  

\begin{fact}\label{thm:convex-sg-not-exist}
For a stochastic game, even if $\rPi_i$ is convex, restricted
equilibria do not necessarily exist.
\end{fact}

\proof
Consider the stochastic game in Figure~\ref{fig:convex-sg-cex}.  This
is a zero-sum game where only the payoffs to the row player are shown.
The discount factor $\gamma \in (0, 1)$.  The actions available to the
row player are $U$ and $D$, and for the column player $L$ or $R$.
From the initial state, $s_0$, the column player may select either $L$
or $R$ which results in no rewards but with high probability,
$1-\epsilon$, transitions to the specified state (regardless of the
row player's action), and with low probability, $\epsilon$,
transitions to the opposite state.  Notice that this stochasticity is
not explicitly shown in Figure~\ref{fig:convex-sg-cex}.  In each of
the resulting states the players play the matrix game shown and then
deterministically transition back to the initial state.  Notice that
this game is unichain, where all the states are in a single ergodic
set, thus satisfying the average reward formulation requirement.
Also, notice that the game without limitations is guaranteed to have
an equilibrium in both the discounted reward and the average reward,
since it is zero-sum, formulations.

\begin{figure}[htb]
%FIXME \centerline{\includegraphics[width=3in]{figures/convex-sg-cex-withe}}
\centerline{\includegraphics[width=3in]{figures/convex-sg-cex}}
\caption{An example stochastic game where convex restricted policy spaces 
do not preserve the existence of equilibria.}
\label{fig:convex-sg-cex}
\end{figure}

Now consider the restricted policy space where players have to play
their actions with the same probability in all states. So,
\begin{eqnarray}
\rPi_i &=& \left\{ \pi_i \in\Pi_i |
\forall s, s'\in\SS\; \forall a\in\AA\quad
\pi_i(s, a) = \pi_i(s', a)\right\}.
\label{eqn:convex-sg-cex-rpi}
\end{eqnarray}
Notice that this is a convex set of policies.  That is, if policies
$x_1$ and $x_2$ are in $\rPi_i$ (according to
Equation~\ref{eqn:convex-sg-cex-rpi}), then for any $\alpha \in [0,
1]$, $x_3$ must also be in $\rPi_i$, where,
\begin{eqnarray}
x_3(s, a) = \alpha x_1(s, a) + (1-\alpha) x_2(s, a).
  \label{eqn:convex-sg-cex-rpi-convex}
\end{eqnarray}
The convexity of $\rPi_i$ can be seen by examining $x_3(s', a)$ for
any $s'\in\SS$.  From Equation~\ref{eqn:convex-sg-cex-rpi-convex}, we
have,
\begin{eqnarray}
x_3(s', a) &=& \alpha x_1(s', a) + (1-\alpha) x_2(s', a) \\
  &=& \alpha x_1(s, a) + (1-\alpha) x_2(s, a) \\
  &=& x_3(s, a).
\end{eqnarray}
Therefore, $x_3$ is in $\rPi_i$ and hence $\rPi_i$ is convex.

This game, though, does not have a restricted equilibrium.  The four
possible joint deterministic policies, $(U, L)$, $(U, R)$, $(D, L)$,
and $(D, R)$, are not equilibria.  So if there exists an equilibrium
it must be mixed.  Consider any mixed strategy for the row player.  If
this strategy plays $U$ with probability less than ${1\over2}$ then
the only best-response for the column player is to play $L$; if
greater than ${1\over2}$ then the only best-response is to play $R$;
if equal {\em then the only best-responses are to play $L$ or $R$
deterministically}.  In all cases, all best-responses are
deterministic, so this rules out mixed strategy equilibria, and so no
equilibrium exists.
\hfill$\Box$

Fact~\ref{thm:convex-sg-not-exist} demonstrates that convexity is not
a strong enough property to guarantee the existence of restricted
equilibria.  The discussion in Section~\ref{sec:sg:learning} concluded
that the majority of existing multiagent learning algorithms hold
some dependence on the existence of equilibria.  Therefore, this
result may have serious implications for the scaling of multiagent
learning to large problems.  We will explore these implications by
first examining this example more closely, in order to identify a new
sufficient condition.  We will then seek to rescue the equilibrium
notion by exploring specific situations where its existence can be
preserved.

\subsubsection{A Sufficient Condition for Equilibria}

Standard equilibrium proof techniques fail in the
Fact~\ref{thm:convex-sg-not-exist} counterexample because the player's
best-response sets are not convex, even though their restricted policy
spaces are convex.  Notice that the best-response to the row player
mixing equally between actions is to play either of its actions
deterministically.  But, linear combinations of these actions (e.g.,
mixing equally) are not best-responses.  This intuition is proven in
the following lemma.
\begin{lemma}
For any stochastic game, if $\rPi_i$ is convex
and for all $\pi_{-i}\in\rPi_{-i}$, $\rBR_i(\pi_{-i})$ is convex, then
there exists a restricted equilibrium.
\label{lemma}
\end{lemma}
The proof of this lemma relies on Kakutani's fixed point theorem using
the convexity of the best-response as the critical condition for
applying the theorem.  Complete details of the proof can be found in
Appendix~\ref{app:lemma}.

The consequence of this lemma is that, if we can prove that the sets
of restricted best-responses are convex then restricted equilibria
exist.  Notice that the convexity of the restricted policy space is
necessary for this condition (e.g., consider a uniform reward function
resulting in $\rBR(\pi_{-i}) = \rPi$).  The
Fact~\ref{thm:convex-sg-not-exist} counterexample demonstrates that it
is not sufficient, since a restricted policy space can be convex
without the restricted best-response sets being convex.

We now look at placing further restrictions either on the restricted
policy spaces or the stochastic game, to insure provably convex
best-response sets. After each existence proof for restricted
equilibria, we give one or more practical examples of domains where
the theoretical results apply.  These results begin to enumerate a few
general classes where restricted equilibria are guaranteed to exist.

\subsubsection{A Subclass of Restricted Policies}

The first result for general stochastic games uses a stronger notion
of convexity for restricted policy spaces.
\begin{definition}
A restricted policy space $\rPi_i$ is {\em statewise convex}, if it is
the Cartesian product over all states of convex strategy sets.
Equivalently, if for all $x_1, x_2 \in \rPi_i$ and all functions
$\alpha : \SS \rightarrow [0, 1]$, the policy $x_3(s, a) = \alpha(s)
x_1(s, a) + (1-\alpha(s)) x_2(s, a)$ is also in $\rPi_i$.
\end{definition}
In words, statewise convex policy spaces allow the policy's action
probabilities at each state to be modified (within the restricted set)
{\em independently}.  We can show that this is a sufficient condition.

\begin{theorem}\label{thm:statewise-convex}
In the discounted reward formulation, if $\rPi_i$ is statewise convex,
then there exists a restricted equilibrium.
\end{theorem}

\proof%[Discounted Reward]
With statewise convex policy spaces, there exist optimal policies in
the strong sense as mentioned in
Section~\ref{sec:sg}.  Specifically, there exists a policy that can
simultaneously maximize the value of all states.  Formally, for any
$\pi_{-i}$ there exists a $\pi_i\in\rPi_i$ such that,
\[
\forall s\in\SS\; \forall\pi_i'\in\rPi_i \qq
V_i^{\left<\pi_i, \pi_{-i}\right>}(s) 
  \ge V_i^{\left<\pi_i', \pi_{-i}\right>}(s).
\]
Suppose this were not true, i.e., there were two policies each of
which maximized the value of different states.  We can construct a new
policy that in each state follows the policy whose value is larger for
that state.  This policy will maximize the value of both states that
those policies maximized, and due to statewise convexity is also in
$\rPi_i$.  We will use that fact to redefine optimality to this strong
sense for this proof.

We will now make use of Lemma~\ref{lemma}.  First, notice the lemma's
proof still holds even with this new definition of optimality.  We
just showed that under this redefinition, $\rBR_i(\pi_{-i})$ is
non-empty, and the same argument for compactness of $\rBR_i(\pi_{-i})$
holds.  So we can make use of Lemma~\ref{lemma} and what remains is to
prove that $\rBR_i(\pi_{-i})$ is convex.  Since $\pi_{-i}$ is a fixed
policy for all the other players this defines an MDP for player
$i$~\cite[Corollary 4.2.11]{FilarVrieze97}.  So we need to show that
the set of polices from the player's restricted set that are optimal
for this MDP is a convex set.  Concretely, if $x_1, x_2 \in
\rPi$ are optimal for this MDP, then the policy 
$x_3(s, a) = \alpha x_1(s, a) + (1 - \alpha) x_2(s, a)$ is also
optimal for any $\alpha\in [0,1]$. Since $x_1$ and $x_2$ are optimal
in the strong sense, i.e., maximizing the value of all states
simultaneously, then they must have the same per-state value.

Here, we will use the notation $V^x(s)$ to refer to the value of
policy $x$ from state $s$ in this fixed MDP.  The value function for
any policy is the {\em unique} solution to the Bellman equations,
specifically,
\begin{eqnarray}
\forall s\in\SS \qq V^x(s) &=& \sum_a x(s, a) 
  \left( R(s, a) + \gamma \sum_{s'} T(s, a, s') V^x(s')\right). 
  \label{eqn:bellman}
\end{eqnarray}
For $x_3$ then we get the following,
\begin{eqnarray}
V^{x_3}(s) &=& \sum_a x_3(s, a)
  \left( R(s, a) + \gamma \sum_{s'} T(s, a, s') V^{x_3}(s')\right) \\
&=& \sum_a (\alpha x_1(s, a) + (1-\alpha) x_2(s, a))
  \left( R(s, a) + \gamma \sum_{s'} T(s, a, s') V^{x_3}(s')\right) \\
&=& \alpha \sum_a x_1(s, a) 
  \left( R(s, a) + \gamma \sum_{s'} T(s, a, s') V^{x_3}(s')\right) + 
  \nonumber\\
&& (1-\alpha) \sum_a x_2(s, a))
  \left( R(s, a) + \gamma \sum_{s'} T(s, a, s') V^{x_3}(s')\right).
\end{eqnarray}
Notice that $V^{x_3}(s) = V^{x_1}(s) = V^{x_2}(s)$ is a solution to
these equations, and therefore is the unique solution for the value of
$x_3$.  Therefore, $x_3$ has the same values as $x_1$ and $x_2$, and
hence is also optimal.  Therefore $\rBR_i(\pi_{-i})$ is convex, and
from Lemma~\ref{lemma} we get the existence of restricted equilibria
under this stricter notion of optimality, which also makes the
policies a restricted equilibrium under our original notion of
optimality, that is only maximizing the value of the initial state.
\hfill$\Box$

\begin{comment}
\par\medskip\proof[Average Reward]
The proof follows a similar line as, and uses results from, the
discounted reward case.  We will examine a stronger notion of
optimality, namely {\em bias-optimal} policies~\cite{Mahadevan96}.  As
in the discounted reward case, consider the MDP defined for player $i$
by fixing the other players' policies to $\pi_{-i}$.  For any MDP, a
policy is bias-optimal, if and only if it achieves maximal average
reward and it simultaneously maximizes its bias values, $\VV^\pi(s)$,
for all $s$, where,
\begin{eqnarray}
\VV^\pi(s) = \lim_{T\rightarrow\infty} \sum_{t=0}^T 
  E\left\{r^t_i - V^\pi | \pi, s_0 = s\right\}.
\label{eqn:bias-optimal}
\end{eqnarray}
with $V^\pi$ being the average reward received by following policy
$\pi$ in this MDP.

We are only really concerned with the bias values of those policies
from $\rPi_i$ that maximize average reward in this fixed MDP.  Let
$V^*$ be the maximum average reward from a policy in $\rPi_i$.  $V^*$
certainly exists because average reward is a continuous function of
the joint policy and $\rPi_i$ is compact and so this function attains
its maximum~\cite[Corollary 3.11]{Gaughan93}.  Therefore, we will
redefine $\VV^\pi(s)$ in terms of this average reward,
\begin{eqnarray}
\VV^\pi(s) = \lim_{T\rightarrow\infty} \sum_{t=0}^T 
  E\left\{r_t - V^* | \pi, s_0 = s\right\}.
\label{eqn:bias-optimal-redefined}
\end{eqnarray}
It is easy to observe that any policy that achieves an average reward
value of $V^*$ must have bounded $\VV^\pi(s)$.  These values can also
be written as a Bellman-like equation~\cite{Mahadevan96},
\begin{eqnarray}
\VV^\pi(s) + V^* = \sum_a \pi(s, a) 
  \left(R(s, a) + \sum_{s'} T(s, a, s') \VV^\pi(s')\right).
\label{eqn:bias-optimal-bellman}
\end{eqnarray}
Finally, we also use the fact that for any policy, $\pi$, if
$\VV^\pi(s)$ is finite, then $\pi$ achieves maximal average reward in
the original MDP.  We prove this as Lemma~\ref{lem:finite-bias} in the
Appendix, as it is only used in this single proof.

Now by manipulating Equation~\ref{eqn:bias-optimal-bellman}, we get,
\begin{eqnarray}
\VV^\pi(s) = \sum_a \pi(s, a) 
  \left(R(s, a) - V^* + \sum_{s'} T(s, a, s') \VV^\pi(s')\right).
\label{eqn:bias-optimal-mdp}
\end{eqnarray}
Notice that this is the Bellman equation for a new MDP where $V^*$ is
subtracted from the reward of every state-action pair.  Also notice
that maximizing $\VV^\pi(s)$ is equivalent to acting optimally in this
discounted MDP, where $\gamma = 1$.  We will call this constructed MDP
the {\em bias-optimal MDP}.  From the proof of the discounted reward
case, we know that there exists a policy from $\rPi_i$ that
simultaneously maximizes the value of all states of this MDP.  In
addition, the set of all optimal policies from $\rPi_i$ of this MDP is
convex.  Since any policy that simultaneously maximizes the value of
all states in the bias-optimal MDP must therefore have finite
$\VV^\pi(s)$, it must by Lemma~\ref{lem:finite-bias} maximize average
reward in the original MDP.  So the non-empty and convex set of
optimal policies in the bias-optimal MDP corresponds to the set of
bias-optimal policies from $\rPi_i$ of the original MDP.  So,
therefore the set of bias-optimal policies is convex and non-empty.

We can now make use of Lemma~\ref{lemma}.  Again, observe that the
lemma's proof still holds.  We just showed that $\rBR_i(\pi_{-i})$
with the bias-optimality criterion is non-empty and convex.  The
argument for compactness is the same as in the lemma's proof since
both the average reward values and the total reward values of the
bias-optimal MDP are continuous functions of the joint policy.  So we
can apply Lemma~\ref{lemma} and conclude that restricted equilibria
exist.
\hfill$\Box$
\end{comment}

\paragraphfirstline{{\rm\it Example: Multirobot Indoor Navigation.}}
Consider an indoor navigation domain with multiple robots traversing
constrained hallways.  The agents are the robots, all with their own
navigational goals.  A robot's state consists of a highly discretized
representation of position and orientation resulting in an intractable
number of states per robot.  The global state is the joint states of
all of the robots and is known by all the agents.  The robots' actions
are low-level navigation commands.  We will construct an example of a
useful restricted policy space for this domain that is statewise
convex, and therefore satisfies the conditions of
Theorem~\ref{thm:statewise-convex}.  Define a set of key decision
points, $\KK$, made up of the hallway intersections.  These decision
points define a subset of the complete state space, $\KK^n
\subseteq \SS$.  While between key decision points, each agent will
use a fixed policy assigning probabilities to actions to reach the
next decision point.  The agents' policies are restricted so that
decisions are only made when all agents have arrived at a key decision
point, where they all simultaneously choose an action contingent on
the global state.  The agents can independently assign action
probabilities for all states in $\KK^n$, while all the action
probabilities in $\SS -
\KK^n$ are fixed.  Hence, this is a statewise convex restricted policy
space.  Theorem~\ref{thm:statewise-convex} therefore applies and we
conclude that there exists restricted equilibria in this domain.

\paragraphfirstline{}%

Despite the above example, most rational limitations that allow
reinforcement learning to scale are unlikely to be statewise convex
restrictions.  They often have a strong dependence between states.
For example, parameterized policies involve far less parameters than
the number of states, which is often intractably large.  Either the
majority of states have fixed action probabilities, as in the above
example, or there will be fart too many parameters to optimize.
Similarly, subproblems force whole portions of the state space to
follow the same subproblem solution.  Therefore, these portions of the
state space do not select their actions independently.  Abstraction
and state aliasing use the same action probabilities across multiple
states, and so also are not statewise convex.  We now look at
retaining a simple convexity condition on the restricted policy
spaces, but examine constrained spaces of stochastic games.

\subsubsection{Subclasses of Stochastic Games}

One way to relax from statewise convexity to general convexity is to
consider only a subset of stochastic games.
Theorem~\ref{thm:convex-mg} is one example, where restricted
equilibria exist for the subclass of matrix games with convex
restricted policy spaces.  Matrix games have a highly constrained
``transition'' function allowing only self transitions, which are
independent of the players' actions.  We can generalize this idea
beyond single-state games.

\begin{theorem}\label{thm:no-control}
Consider no-control stochastic games, where all transitions are
independent of the players' actions, i.e.,
\[
\forall s,s'\in\SS\; \forall a,b \in\AA \qq T(s,a,s') = T(s,b,s').
\]
If $\rPi_i$ is convex, then there exists a restricted equilibrium.
\end{theorem}

\proof[Discounted Reward]
This proof also makes use of Lemma~\ref{lemma}, leaving us only to show that
$\rBR_i(\pi_{-i})$ is convex.  Just as in the proof of
Theorem~\ref{thm:statewise-convex} we will consider the MDP defined
for player $i$ when the other players follow the fixed policy
$\pi_{-i}$.  As before it suffices to show that for this MDP, if $x_1,
x_2 \in \rPi$ are optimal for this MDP, then the policy $x_3(s, a) =
\alpha x_1(s, a) + (1 - \alpha) x_2(s, a)$ is also optimal for any
$\alpha\in [0, 1]$.

Again we use the notation $V^x(s)$ to refer to the traditional
value of a policy $x$ at state $s$ in this fixed MDP.  Since $T(s,
a, s')$ is independent of $a$, we can simplify the Bellman equations
(Equation~\ref{eqn:bellman}) to
\begin{eqnarray}
V^{x}(s) &=& \sum_a x(s, a) R(s, a) + 
  \gamma \sum_{s'} \sum_{a} x(s, a) T(s, a, s') V^{x}(s') \\
&=& \sum_a x(s, a) R(s, a) + 
  \gamma \sum_{s'} T(s, \cdot, s') V^{x}(s') \label{eqn:no-control-1}.
\end{eqnarray}
For the policy $x_3$, the value of state $s$ is then,
\begin{eqnarray}
V^{x_3}(s) &=& \alpha \sum_a x_1(s, a) R(s, a) + 
  (1-\alpha) \sum_a x_2(s, a) R(s, a)+ \nonumber\\
  & & \gamma \sum_{s'} T(s, \cdot, s') V^{x_3}(s').
\end{eqnarray}
Using equation~\ref{eqn:no-control-1} for both $x_1$ and $x_2$ we get,
\begin{eqnarray}
V^{x_3}(s) &=& 
  \alpha (V^{x_1}(s) - \gamma \sum_{s'} T(s, \cdot, s') V^{x_1}(s')) + 
  \nonumber\\
&& (1- \alpha) (V^{x_2}(s) - \gamma \sum_{s'} T(s, \cdot, s') V^{x_2}(s')) + 
  \nonumber\\
&& \gamma \sum_{s'} T(s, \cdot, s') V^{x_3}(s') \\
&=& \alpha V^{x_1}(s) + (1-\alpha) V^{x_2}(s) + \nonumber\\
&& \gamma \sum_{s'} T(s, \cdot, s') 
  \left(V^{x_3}(s') - \alpha V^{x_1}(s') - (1-\alpha) V^{x_2}(s')\right) 
\end{eqnarray}
Notice that a solution to these equations is $V^{x_3}(s) = \alpha
V^{x_1}(s) + (1-\alpha) V^{x_2}(s)$, and the Bellman equations must
have a unique solution.  Hence, $V^{x_3}(s_0)$ is equal to
$V^{x_1}(s_0)$ and $V^{x_2}(s_0)$, which are equal since both are
optimal.  So $x_3$ is optimal, and $\rBR_i(\pi)$ is convex.  Applying
Lemma~\ref{lemma} we get that restricted equilibria exist.
\hfill$\Box$

\par\medskip\proof[Average Reward]
An equivalent definition to Equation~\ref{eqn:average-reward} of a
policy's average reward is,
\begin{eqnarray}
V_i^\pi = \sum_{s\in\SS} d^\pi(s) \sum_a \pi(s, a) R(s, a),
\label{eqn:average-reward-2}
\end{eqnarray}
where $d^\pi(s)$ defines the distribution over states visited while
following $\pi$ after infinite time.  For a stochastic game or MDP
that is unichain we know that this distribution is independent of the
initial state.  In the case of no-control stochastic games or MDPs,
this distribution becomes independent of the actions and policies of
the players, and depends solely on the transition probabilities.  So
Equation~\ref{eqn:average-reward-2} can be written,
\begin{eqnarray}
V_i^\pi = \sum_{s\in\SS} d(s) \sum_a \pi(s, a) R(s, a).
\label{eqn:average-reward-no-control}
\end{eqnarray}
As before, we must show that $\rBR_i(\pi_{-i})$ is convex to apply
Lemma~\ref{lemma}.  Consider the MDP defined for player $i$ when the
other players follow the policy $\pi_{-i}$.  It suffices to show that
for this MDP, if $x_1, x_2 \in \rPi$ are optimal for this MDP, then
the policy $x_3(s, a) = \alpha x_1(s, a) + (1 - \alpha) x_2(s, a)$ is
also optimal for any $\alpha\in [0, 1]$.  Using
Equation~\ref{eqn:average-reward-no-control}, we can write the value
of $x_3$ as,
\begin{eqnarray}
V_i^{x_3} &=& \sum_{s\in\SS} d(s) \left(\sum_a x_3(s, a) R(s, a)\right) \\
&=& \sum_{s\in\SS} d(s) \left(\sum_a 
  \left(\alpha x_1(s, a) + (1-\alpha) x_2(s, a)\right) R(s, a)\right) \\
&=& d(s) \left(\sum_a \alpha x_1(s, a) R(s,a) + 
  \sum_a (1-\alpha) x_2(s, a) R(s, a)\right) \\
&=& \alpha \left(\sum_{s\in\SS} d(s) \sum_a x_1(s, a) R(s,a)\right) + 
  (1-\alpha) \left(\sum_{s\in\SS} d(s)\sum_a x_2(s, a) R(s, a)\right) \\
&=& \alpha V_i^{x_1}(s) + (1-\alpha) V_i^{x_2}(s) \\
&=& \alpha V_i^{x_1}(s) + (1-\alpha) V_i^{x_1}(s) = V_i^{x_1}(s).
\end{eqnarray}
Therefore $x_3$ has the same average reward as $x_1$ and so is also
optimal.  So $\rBR_i(\pi_{-i})$ is convex and by Lemma~\ref{lemma}
there exists an equilibrium.
\hfill$\Box$

\paragraphfirstline{{\rm\it Example: Space Probe.}}
Consider a space probe traveling on a predefined planetary trajectory.
Consider using a multiagent approach to coordinating the gathering of
data from scientific instruments.  Each instrument is an agent making
independent decisions and maximizing an assigned reward function.  The
state of the system is the position and orientation of the probe,
which follows a fixed transition function.  The state determines the
effectiveness of the various data-gathering tasks (i.e., the agents'
rewards), which also may be determined by the decisions of the other
instruments.  For example, camera images may be occluded when
collecting atmospheric samples, or two instruments may draw too much
power if activated simultaneously, causing both to fail.  This is a
no-control stochastic game, as the instruments' actions do not control
the state, which is the predefined trajectory of the probe.  By
Theorem~\ref{thm:no-control}, restricted equilibria exist for all
convex restricted policy spaces in this domain.
\paragraphfirstline{}%

We can now merge Theorem~\ref{thm:statewise-convex} and
Theorem~\ref{thm:no-control} allowing us to prove existence of
equilibria for a general class of games where only one of the player's
actions affects the next state.  Since this theorem's sufficient
conditions are the most general of those presented, multiple examples
of applications follow.

\begin{theorem}\label{thm:single-controller}
Consider single-controller stochastic games \cite{FilarVrieze97},
where all transitions depend solely on player 1's actions,
i.e., 
\[
\forall s,s'\in\SS\; \forall a,b \in\AA \qq a_1 = b_1 \Rightarrow
T(s,a,s') = T(s,b,s').
\]
In the discounted reward formulation, if $\rPi_1$ is statewise convex
and $\rPi_{i\ne1}$ is convex, then there exists a restricted
equilibrium.
\end{theorem}

\proof
This proof again makes use of Lemma~\ref{lemma}, leaving us to show that
$\rBR_i(\pi_{-i})$ is convex.  For $i=1$ we use the argument from the
proof of Theorem~\ref{thm:statewise-convex}.  For $i\ne1$ we use the
argument from Theorem~\ref{thm:no-control}.
\hfill$\Box$

\paragraphfirstline{{\rm\it Example: Haunted House Ride.}}
An example that helps to illustrate the concept of a single-controller
stochastic game is an amusement park haunted house ride.  Consider the
system as consisting of multiple agents including the ride operator
and the ride's passengers.  Suppose the ride operator has choices over
different ride routes therefore determining the state of the world for
the passenger agents.  The passengers, on the other hand, can only
choose at each state where to look and when to try and scare their
fellow passengers.  Therefore, one agent (the operator) controls the
transitions, while all the agents' (operator and passengers) affect
the resulting rewards.  Consider that the ride operator may be
restricted to only making decisions at a few key decision points
determined by the ride designer.  Therefore, the operator's policy
space is statewise convex.  Hence, according to
Theorem~\ref{thm:single-controller} if the passengers have convex
restricted policy spaces resulting from their imposed limitations,
then restricted equilibria exist.

\paragraphfirstline{{\rm\it Example: Mobile Data Gathering.}}
The general pattern of the haunted house ride can also be seen in
practical situations.  Consider mobile data gathering, such as an
extended version of the space probe example presented earlier.  There
is one navigational agent whose actions determine the state (e.g.,
position and orientation).  The other agents are instruments choosing
how to gather data at any given moment, as in the no-control version
described above.  The rewards are determined by all of the agents
actions, but the state transition is defined only by the navigational
agent.  This fits the definition of a single-controller stochastic
game and the Theorem holds for appropriate restricted policy spaces.

\paragraphfirstline{{\rm\it Example: Asymmetric Competition}}
The above examples, although not strictly team games, do have a
cooperative nature to them.  Single-controller stochastic games can
also be competitive.  Consider an economic competition between two
firms, where one firm's supply technology is primarily
infrastructure-based, while the other's is very fluid.  For example, a
transportation company using rail lines versus a company using trucks.
Since one agent's actions are implemented on a timescale far smaller
than the other agent, we can effectively ignore that firm's state.
The global state is just the built infrastructure of the first agent,
and is only influenced by that agent's actions.  The rewards, though,
are determined by both actions of the agents, and may well be
zero-sum.  If the first firm uses a statewise convex restricted policy
space (e.g., using key decision points) and the other firm uses a
convex restricted policy space, then restricted equilibria exist.
\paragraphfirstline{}%

The previous results have looked at stochastic games whose transition
functions have particular properties.  Our final theorem examines
stochastic games where the rewards have a particular structure.
Specifically we address team games, where the agents all receive equal
payoffs.
\begin{theorem}\label{thm:team-game}
For team games, i.e.,
\[ 
\forall i,j\in\{1,\ldots,n\}\; \forall s \in\SS\; \forall a \in\AA \qq
R_i(s, a) = R_j(s, a),
\]
there exists a restricted equilibrium.
\end{theorem}

\proof
The only constraints on the players' restricted policy spaces are
those stated at the beginning of this section: non-empty and compact.
Since $\rPi$ is compact, being a Cartesian product of compact sets,
and player one's value in either formulation is a continuous function
of the joint policy, then the value function attains its
maximum~\cite[Corollary 3.11]{Gaughan93}.  Specifically, there exists
$\pi^*\in\rPi$ such that,
\[
\forall \pi\in\rPi \qq V_1^{\pi^*} \ge V_1^\pi.
\]
Since $\forall i V_i = V_1$ we then get that the policy $\pi^*$
maximizes all the players' rewards, and so each must be playing a
restricted best-response to the others' policies.
\hfill$\Box$ 

\paragraphfirstline{{\rm\it Example: Distributed Network Routing.}}
Consider a distributed network routing domain where message passing at
nodes is controlled by an intelligent agent.  The agent can only
observe its own queue of incoming messages and congestion on outgoing
links.  Hence each agent has an aliased view of the global state.
Therefore, policies mapping the observed state to actions are {\em
convex} restricted policy spaces in the fully-observable stochastic
game.  All the agents seek to maximize global throughput.  Hence, they
have an identical reward function based on global packet arrival.  As
long as further agent limitations preserve the convexity of their
policy spaces, by Theorem~\ref{thm:team-game} there exists a
restricted equilibrium.

\subsection{Summary}

Facts~\ref{thm:not-exist} and
\ref{thm:convex-sg-not-exist} provide counterexamples that show
the threat limitations pose to equilibria.
Theorems~\ref{thm:convex-mg}, \ref{thm:statewise-convex},
\ref{thm:no-control},
\ref{thm:single-controller}, and~\ref{thm:team-game} give us five
general classes of stochastic games and restricted policy spaces where
equilibria are guaranteed to exist.  The fact that equilibria do not
exist in general raises concerns about equilibria as a general basis
for multiagent learning in domains where agents have limitations.  On
the other hand, combined with the model of implicit games, the
presented theoretical results lays the initial groundwork for
understanding when equilibria can be relied on and when their
existence may be in question.  These contributions also provide some
formal foundation for applying multiagent learning in limited agent
problems.

\section{Learning with Limitations}
\label{sec:learning}

In Section~\ref{sec:sg}, we highlighted the importance of the
existence of equilibria to multiagent learning algorithms.  This
section presents results of applying a particular learning algorithm
to a setting of limited agents.  We use the best-response learner,
WoLF-PHC~\cite{02aij-wolf}.  This algorithm is rational, that is, it
is guaranteed to converge to a best-response if the other players'
policies converge and appropriate decayed exploration is
used~\cite{SinghEtAl00-onpolicy}.  In addition, it has been
empirically shown to converge in self-play, where both players use
WoLF-PHC for learning. In this article we apply this algorithm in
self-play to matrix games, both with and without player limitations.
Since the algorithm is rational, if the players converge then their
converged policies must be an equilibrium~\cite{02aij-wolf}.

The specific limitations we examine fall into both the restricted
policy space model as well as the implicit game model.  One player is
restricted to playing strategies that are the convex hull of a subset
of the available strategies.  From Theorem~\ref{thm:convex-mg}, there
exists a restricted equilibrium with these limitations.  For
best-response learners, this amounts to a possible convergence point
for the players.  For the limited player, the WoLF-PHC algorithms were
modified slightly so that the player maintains Q-values of its
restricted set of available strategies and performs its usual
hill-climbing in the mixed space of these strategies.  The unlimited
player is unchanged and {\em completely uninformed of the limitation
of its opponent}.  For all the experiments, we use very small learning
rates and a large number of trials to better display how the algorithm
learns and converges.

\subsection{Rock-Paper-Scissors}
The first game we examine is Rock-Paper-Scissors.
Figure~\ref{results:rps-unlimited} shows the results of learning when
neither player is limited.  Each graph shows the mixed policy the
player is playing over time.  The labels to the right of the graph
signify the probabilities of each action in the game's unique Nash
equilibrium.  Observe that the players' strategies converge to this
learning fixed point.

\begin{figure*}[htb]
\begin{tabular}{p{0.48\hsize}p{0.48\hsize}}
\centerline{\includegraphics[width=1.1\hsize]{results/results-rps-strategies-p1-bw}}
&
\centerline{\includegraphics[width=1.1\hsize]{results/results-rps-strategies-p2-bw}}
\end{tabular}\vspace{-1.5\baselineskip}
\caption{WoLF-PHC in Rock-Paper-Scissors. Neither player is limited.}
\label{results:rps-unlimited}
\end{figure*}

Figure~\ref{results:rps-limited} shows the results of restricting
player 1 to a convex restricted policy space, defined by requiring the
player to play ``Paper'' exactly half the time.  This is the same
restriction as shown graphically in
Figure~\ref{fig:rps-implicit-game}.  The graphs again show the
players' strategies over time, and the labels to the right now label
the game's restricted equilibrium, which accounts for the limitation
(see Figure~\ref{fig:rps-implicit-game}).  The player's strategies now
converge to this new learning fixed point.  If we examine the expected
rewards to the players, we see that the unrestricted player gets a
higher expected reward in the restricted equilibrium than in the
game's Nash equilibrium ($1/6$ compared to $0$.)  In summary, both
players learn optimal best-response policies with the unrestricted
learner appropriately taking advantage of the other player's
limitation.

\begin{figure*}[htb]
\begin{tabular}{p{0.48\hsize}p{0.48\hsize}}
\centerline{\includegraphics[width=1.1\hsize]{results/results-rps-r-strategies-p1-bw}}
&
\centerline{\includegraphics[width=1.1\hsize]{results/results-rps-r-strategies-p2-bw}}
\end{tabular}\vspace{-1.5\baselineskip}
\caption{WoLF-PHC in Rock-Paper-Scissors.  Player 1 must play ``Paper'' with
probability ${1\over 2}$.}
\label{results:rps-limited}
\end{figure*}


\subsection{Colonel Blotto}
The second game we examined is ``Colonel Blotto''~\cite{Gintis00},
which is also a zero-sum matrix game.  In this game, players
simultaneously allot regiments to one of two battlefields.  If one
player allots more armies to a battlefield than the other, they
receive a reward of one plus the number of armies defeated, and the
other player loses this amount.  If the players tie, then the reward
is zero for both.  In the unlimited game, the row player has four
regiments to allot, and the column player has only three.  The matrix
of payoffs for this game is shown in Figure~\ref{fig:game-blotto}.

\def\zerobox#1{\vbox to 0pt{\vss\hbox to0pt{\hss#1}}}

\begin{figure}[htb]
\abovedisplayskip 0pt
\belowdisplayskip 0pt
\[\begin{array}{rclrcl} \\
R_{r} &=& 
\begin{array}{c}\mbox{\bf 4-0}\\ \mbox{\bf 3-1}\\ \mbox{\bf 2-2}\\ \mbox{\bf 1-3}\\ \mbox{\bf 0-4}\end{array}
\left(\begin{array}{rrrr} 
\hbox to 18pt{\hfill 4}\zerobox{\raise15pt\zerobox{\bf 3-0}} & 
\hbox to18pt{\hfill 2}\zerobox{\raise15pt\zerobox{\bf 2-1}} & 
\hbox to18pt{\hfill 1}\zerobox{\raise15pt\zerobox{\bf 1-2}} & 
\hbox to18pt{\hfill 0}\zerobox{\raise15pt\zerobox{\bf 0-3}} \\
  1  & 3 & 0 & -1 \\
  -2 & 2 & 2 & -2 \\
  -1 & 0 & 3 & 1 \\
  0  & 1 & 2 & 4 \end{array}\right)
&
R_{c} &=& 
\begin{array}{c}\mbox{\bf 4-0}\\ \mbox{\bf 3-1}\\ \mbox{\bf 2-2}\\ \mbox{\bf 1-3}\\ \mbox{\bf 0-4}\end{array}
\left(\begin{array}{rrrr} 
\hbox to 18pt{\hfill -4}\zerobox{\raise15pt\zerobox{\bf 3-0}} & 
\hbox to18pt{\hfill -2}\zerobox{\raise15pt\zerobox{\bf 2-1}} & 
\hbox to18pt{\hfill -1}\zerobox{\raise15pt\zerobox{\bf 1-2}} & 
\hbox to18pt{\hfill 0}\zerobox{\raise15pt\zerobox{\bf 0-3}} \\
  -1  & -3 & 0 & 1 \\
  2 & -2 & -2 & 2 \\
  1 & 0 & -3 & -1 \\
  0  & -1 & -2 & -4 \end{array}\right)
\end{array}\]
\caption{Colonel Blotto Game.}
\label{fig:game-blotto}
\end{figure}

Figure~\ref{results:blotto-unlimited} shows experimental results with
unlimited players.  The labels on the right signify the probabilities
associated with the Nash equilibrium to which the players' strategies
converge.  Player 1 is then given the limitation that it could only
allot two of its armies, the other two would be allotted randomly.
This is also a convex restricted policy space and therefore by
Theorem~\ref{thm:convex-mg} has a restricted equilibrium.
Figure~\ref{results:blotto-limited} shows the learning results.  The
labels to the right correspond to the action probabilities for the
restricted equilibrium, which was computed by hand.  As in
Rock-Paper-Scissors, the players' strategies converge to the new
learning fixed point.  Similarly, the expected reward for the
unrestricted player resulting from the restricted equilibrium is
considerably higher than that of the Nash equilibrium ($0$ to
$-14/9$), as the player takes advantage of the other's limitation.

\begin{figure*}[htb]
\begin{tabular}{p{0.48\hsize}p{0.48\hsize}}
\centerline{\includegraphics[width=1.1\hsize]{results/results-blotto-strategies-p1-bw}}
&
\centerline{\includegraphics[width=1.1\hsize]{results/results-blotto-strategies-p2-bw}}
\end{tabular}\vspace{-1.5\baselineskip}
\caption{WoLF-PHC in Colonel Blotto. Neither player is limited.}
\label{results:blotto-unlimited}
\end{figure*}

\begin{figure*}[htb]
\begin{tabular}{p{0.48\hsize}p{0.48\hsize}}
\centerline{\includegraphics[width=1.1\hsize]{results/results-blotto-r-strategies-p1-bw}}
&
\centerline{\includegraphics[width=1.1\hsize]{results/results-blotto-r-strategies-p2-bw}}
\end{tabular}\vspace{-1.5\baselineskip}
\caption{WoLF-PHC in Colonel Blotto.  Player one is forced to randomly
allot two regiments.}
\label{results:blotto-limited}
\end{figure*}

There is one final observations about these results.  In
Section~\ref{sec:limitations} we discussed the use of rational
limitations to speed learning.  Even in these very small single-state
problems, our results demonstrate that limitations can be used to
speed learning.  Notice that convergence occurs more quickly in the
limited situations where one of the players has less parameters and
less freedom in its policy space.  In the case of the Colonel Blotto
game this is a dramatic difference.  (Notice the x-axes differ by a
factor of four!)  In games with very large state spaces this will be
even more dramatic.  Agents will need to make use of rational
limitations to do any learning at all, and similarly the less
restricted agents will likely be able to benefit from taking advantage
of the more limited learners.\footnote{Strictly speaking, restricted
agents are not always at a disadvantage.  In zero-sum games, such as
those for which results are presented here, and team-games where all
players rewards are identical, restrictions can never benefit the
agent.  In general-sum games, such as Bach or Stravinsky from
Table~\ref{fig:game-mg}(b), this is not true.  In this case, an
imposed restriction, such as the row player being forced to select its
first action, can actually improve the agent's equilibrium
value~\cite<see also>{LittmanStone01-threats,GilboaSamet89}.}

\section{Related Work}
\label{sec:related}

It is commonly recognized that humans are not capable of being fully
rational.  There is a whole body of work in the social sciences,
particularly economics and game theory, relating to understanding
humans' {\em bounded rationality}~\cite{Simon82}.
Bounded rationality is also a reality for artificial agents.  As we
discussed in Section~\ref{sec:limitations}, agent limitations are
unavoidable in realistic problems.  As a result, there has been much
interesting work in both the fields of game theory and artificial
intelligence on how limitations effect agent behavior.

A useful distinction presented by Simon~\citejustyear{Simon76} is the
difference between {\em substantive rationality} and {\em procedural
rationality}.  Substantive rationality is primarily concerned with
whether a resulting behavior is appropriate for the achievement of
specific goals given specific constraints.  Procedural rationality is
concerned with the behavior that is the result of appropriate
deliberation.  The difference is in whether it is the outcome that is
appropriate to the goals or the deliberation that is appropriate to
the goals.

The approach taken in this work is primarily procedural.  We take the
variety of well motivated learning procedures, both equilibrium
learners and best-response learners, as given decision mechanisms.  We
also take the variety of mechanisms for making learning tractable
(e.g., abstraction and approximation) as given mechanisms.  The focus
of our investigation is to see what is the resulting behavior of these
combined mechanisms.  In particular, do equilibria exist for
equilibrium learners to learn and to which best-response learners can
converge?  This differs from other investigations which we'll briefly
review here.

\subsection{Game Theory}

Much of the research in game theory on modeling bounded rationality,
has focused on the investigation of procedural
rationality~\cite{Rubinstein98}.  This approach is crucial given the
goal of modeling, explaining, and predicting {\em human behavior}.
An example of this approach is that taken by Osborne and
Rubinstein~\citejustyear{OsborneRubinstein97}.  They define a
decision procedure for mapping actions to discrete outcomes, rather
than distributions over outcomes.  This mapping is generated
stochastically according to the actual distribution of outcomes for
given actions.  Given a mapping, the agent selects the action whose
associated outcome is preferred.  Given the decision procedure, they
investigate whether an equilibrium fixed point exists and also how
well such a procedure corresponds to human behavior in particular
games.

Our work follows a similar approach of considering the outcome of
using particular learning procedures.  On the other hand, we are not
dealing with the problem of human behavior but rather the behavior of
artificial learning agents and how imposed limitations effect
interactions between agents.  By generalizing these effects into the
models of implicit games and restricted policy spaces, we then ask
similar questions.  Do equilibrium fixed points exist and what is the
expected outcome of employing such learning rules?  This simplifies
our problem since we're only analyzing the outcomes of known machine
learning techniques rather than explaining human behavior.

In addition to the work along the lines of procedural rationality,
there is a large body of traditional work following along the lines of
substantive rationality.  The particular goals of this approach are to
model the agents' limitations in the game itself and find optimal
behavior given the constraints of these limitations.  These results
include Bayesian games where other agents' utilities are uncertain a
priori.  Extensive form games with imperfect information is also an
interesting model accounting for situations of state aliasing.
Finally, strategies as finite state machines in repeated games try to
account for limitations on computation and memory.  A summary of this
work can be found in standard game theory
texts~\cite<e.g.,>{OsborneRubinstein94}).

\subsection{Artificial Agents}

While risking over generalizing, much of the work in the field of
artificial agents that examines the effect of limitations on agent
behavior has focused more on substantive rationality.  In particular,
a common thread of this work is the development of models of
interaction and beliefs along with efficient algorithms for computing
optimal or near-optimal behavior given these models.  This approach
focuses on what is appropriate behavior rather than what is the result
of appropriate decision procedures.  We will briefly consider some of
the recent work that consider limitations and agent behavior, and give
some comparison to the approach and results we have taken in this
work.

\subsubsection{Computational Limitations}

Larson and Sandholm~\citejustyear{LarsonSandholm01} consider the
problem of reasoning in the presence of agents with limited
computational resources.  Specifically, they examine a two agent
setting where agents have intractable individual problems, but may
gain an improvement on their solutions by solving the also intractable
joint problem.  An agent's strategy determines how to invest its
limited computational resources to improve its solution for its own
problem, its opponent's problem, or the joint problem.  When the
deadline is reached, the agents must decide whether to simply use its
own computed solution or bargain over a joint solution.  Among other
results, they demonstrate that the concept of Nash equilibrium can
be extended to this setting, where the decision of computation is part of
the agent's strategy.  They call this concept {\em deliberation
equilibria} and present algorithms for finding these equilibria
solutions in certain situations.

The concept of deliberation equilibria has many similarities to the
{\em restricted equilibria} concept we presented in
Section~\ref{sec:existence}.  The core idea is to incorporate the
agents' limitations into their choices of strategies.  Restricted
equilibria, though, incorporate limitations as restrictions on the
agents' choices, rather than incorporating limitations by adding
computational decisions into their choices.  This difference, though,
is a fundamental one as the two approaches solve different problems.
The complexity of decision-making in the Larson and Sandholm setting
is directly due to the computational limitations placed on the agents.
In Chapter~\ref{sec:limitations}, the complexity of decision-making is
part of the task, and agent limitations are required in order to
simplify the problem and make learning tractable.  This core
difference also explains the difference in results, since restricted
equilibria are not guaranteed to exist in general.

\subsubsection{Game-tree Search with Opponent Knowledge}

Jansen's Ph.D. thesis~\citejustyear{Jansen92} examined the issue of
whether ``optimal'' play in the game-theoretic sense is in fact always
``optimal''.  In the case of a fallible opponent that may make an
incorrect evaluation of future states, the answer is naturally no.  He
proposed the idea of {\em speculative play}, which uses a prediction
function for the opponent in determining its opponent's moves when
searching a game-tree.  The thesis focuses on deterministic,
alternating-move, perfect information games, specifically a subgame of
chess.  He demonstrated that using speculative play with end-game
databases as knowledge of the opponent has the potential for improving
play against humans.  In this work, limitations on human rationality
are recognized, and so game-theoretic optimal play is discarded for
optimization against particulars of human play.

\subsubsection{Planning with Opponent Models.}

Riley and
Veloso~\citejustyear{RileyVeloso00-behavior-classification,RileyVeloso02-stn}
present similar ideas for {\em using opponent models to make
decisions} in a less abstract domain.  They examine the problem of
adapting to a specific opponent in simulated robotic
soccer~\cite{NodaEtAl98}.  This work recognizes that modeling
opponents is not a new idea and there has been a great deal of related
research in the field of plan recognition.  The work, though,
contributes an actual technique for {\em using} opponent models to
improve the team behavior, hence learning.

The team designer provides a set of opponent models of possible
behavior of the other team.  These models define a distribution of
players' positions as a function of the ball's trajectory and their
initial positions.  During play, the actual opponent is matched to one
of these models through Bayesian updating from actual observations.
The model is then used to plan during set-play situations, such as
throw-ins or goal-kicks.  The planning uses hill-climbing on the
ball-trajectory to find a trajectory with low probability of being
intercepted by the other team {\em given the matched opponent model of
their movement.}  The planner then determines the positions of players
and their actions so as to carry out the planned ball trajectory.
This is compiled into a simple temporal network which can be executed
in a distributed manner by the players.  They demonstrate through
controlled empirical experiments that the plans generated depend on
the opponent model that is used during planning.  The effectiveness of
this technique in actual play against a real opponents, that may or
may not match well with the models, is still unknown.

This technique allows a team of agents to adapt their behavior in a
principled manner to better address a specific team.  This does not
strictly address the problem of concurrent learning in a multiagent
setting, which is the primary focus of this work.  The critical
assumption is that the opponents' play is not changing over time.  The
authors mention this briefly and provide a small change to their
Bayesian update through the addition of weight sharing.  A small
weight is added to each model to keep its probability bounded from
zero.  This effectively introduces a non-zero probability that the
other team may change its behavior after each observation.  There are
no results, though, of the outcome of this approach if the other
agents are also adapting.  For example, it is not clear how robust the
algorithm is to the other team employing a similar or identical
approach to defending against a set-play.  Will adaptation oscillate
or is there an equilibrium point?  How would such oscillation effect
performance?

\subsubsection{Limitations as Finite Automata.}

Carmel and Markovitch~\citejustyear{CarmelMarkovitch96,Carmel97}
examined a model-based approach to multiagent learning.  They
introduced algorithms for efficiently learning a model of the opponent
as a deterministic finite automaton (DFA).  Using this learned model,
they then compute the optimal best response automaton.  They examined
this technique in the situation of repeated games and showed
that their technique can learn effectively against a variety of DFA
opponents.  They also showed that their algorithm learned much more
quickly (i.e., was more data efficient) than Q-learning, a model-free
reinforcement learner.  It is unknown how this compares with a
model-based reinforcement learner such as prioritized
sweeping~\cite{MooreAtkeson93}.

This technique also does not address the problem of concurrent
learning in a multiagent environment.  Although a learning rule can be
be modeled by a DFA, the number of states that a rule requires may be
huge.  For example, Q-learning with a decaying learning rate would be
a completely intractable DFA.  Also, the model-based learning agent is
required to be strictly more powerful than its opponent, since its
learning rule both learns the opponent's DFA and also generates its
own.  It is unclear whether any sort of equilibrium fixed point would
be reached or even exists if two model-based DFA learners played each
other.  It is also not certain how DFA modeling scales to multiple
state stochastic games.

\subsubsection{Summary}

As we stated earlier, this body of work focuses primarily on
substantive rationality: what is appropriate behavior given these
assumptions?  In addition, most of the approaches include the
assumption of an asymmetric superiority over the other decision making
agents.  In the case of constructing DFA models of opponent behavior,
there is an implicit assumption that the opponent behavior is simple
enough to be constructed by the adapting agent.  In the case of
planning with opponent models, it is assumed that the opponent's
behavior is not changing and so the learned model is accurate in
predicting their future behavior.  Although the work recognizes that
other agents have limitations, they do so in a way that expects other
agents to be strictly inferior.  There are no results, empirical or
theoretical, of applying these model-based techniques to situations of
self-play, where all agents use the same adaptation procedure.  Larson
and Sandholm's work on computational limitations allows for
limitations on the part of both agents.  They do so by adding the
complexity of computational decisions into the strategy space.  Hence,
their approach does not make this assumption.

\section{Conclusion}
\label{sec:conclusion}

Nash equilibrium is a crucial concept in multiagent learning both for
algorithms that directly learn an equilibrium and algorithms that
learn best-responses.  Agent limitations, though, are unavoidable in
realistic settings and can prevent agents from playing optimally or
playing the equilibrium.  In this article, we introduce and answer two
critical questions: Do equilibria exist when agents have limitations?
Not necessarily.  Are there classes of domains or classes of
limitations where equilibria are guaranteed to exist?  Yes.

We have proven that for some classes of stochastic games and agent
limitations equilibria are guaranteed to exist.  We have also given
counterexamples that help understand why equilibria do not exist in
the general case.  In addition to these theoretical results, we
demonstrate the implications of these results in a real learning
algorithm.  We present empirical results that show that learning with
limitations is possible, and equilibria under limitations is relevant.

There are two main future directions for this work.  The first is
continuing to explore the theoretical existence of equilibria.  We
have proven the existence of equilibria for some interesting classes
of stochastic games and restricted policy spaces.  We have also
established in Lemma~\ref{lemma} a key criterion, the convexity of
best-response sets, as the basis for further theoretical results.  It
is still unknown whether there are other general classes of games and
limitations for which equilibria exist.

The second direction is the practical application of multiagent
learning algorithms to real problems when agents have real
limitations.  The theoretical results we have presented and the
empirical results on simple matrix games, give a foundation as well as
encouraging evidence.  There are still challenging questions to
answer.  How do specific limitations map on to the models that we
explored in this article?  Do equilibria exist for stochastic games
and limitations typically faced in practice?  What is the goal of
learning when equilibria do not exist?  This article lays the
groundwork for exploring these and other important learning issues
that are relevant to realistic multiagent scenarios.

\section*{Acknowledgments}
The authors are indebted to Martin Zinkevich for numerous insights as
well as finding the example demonstrating
Fact~\ref{thm:convex-sg-not-exist}.  The authors are grateful to Craig
Boutilier and Tuomas Sandholm for helpful discussions.  In addition,
we owe gratitude to the team of anonymous reviewers for their careful
eyes and invaluable comments.

This research was sponsored by the United States Air Force
under Cooperative Agreements No. F30602-00-2-0549 and
No. F30602-98-2-0135. The views and conclusions contained in this
document are those of the authors and should not be interpreted as
necessarily representing the official policies or endorsements, either
expressed or implied, of the Defense Advanced Research Projects Agency
(DARPA), the Air Force, or the US Government.

\appendix

\section{Proof of Theorem~\ref{thm:convex-mg}}
\label{app:convex-mg}

\proof
One might think of proving this theorem by appealing to implicit games
as was used in Fact~\ref{thm:equilibria-not-nash}.  In fact, if
$\rPi_i$ was a convex hull of a {\em finite} number of strategies,
this would be the case.  In order to prove it for any convex $\rPi_i$
we apply Rosen's theorem about the existence of equilibria in concave
games~\cite{Rosen65}.  In order to use this theorem we need to show
the following:
\begin{enumerate}
\item $\rPi_i$ is non-empty, compact, and convex.
\item $V_i^\pi$ as a function over $\pi\in\rPi$ is continuous.
\item For any $\pi\in\rPi$, the function over $\pi'_i\in\rPi_i$ 
defined as $V_i^{\left<\pi'_i, \pi_{-i}\right>}$ is concave.
\end{enumerate}
Condition 1 is by assumption.  In matrix games, where $\SS = \{s_0\}$,
we can simplify the definition of a policy's value from
Equations~\ref{eqn:discounted-reward} and~\ref{eqn:average-reward}.
For discounted reward we get,
\begin{eqnarray}
V_i^\pi &=& {1 \over 1 - \gamma} 
  \sum_{a\in\AA} R_i(s, a) \Pi_{i=1}^n \pi_i(s_0, a_i),
 \label{eqn:mg-value}
\end{eqnarray}
For average reward, the value is just the value of the one-shot matrix
game given the players' policies.  This is equivalent to setting
$\gamma = 0$ in the Equation~\ref{eqn:mg-value}.
Equation~\ref{eqn:mg-value} shows that for both reward formulations
the value is a multilinear function with respect to the joint policy
and, therefore, is continuous.  So Condition 2 is satisfied.  Observe
that by fixing the policies for all but one player,
Equation~\ref{eqn:mg-value} becomes a linear function over the
remaining player's policy and so is also concave, satisfying Condition
3.  Therefore Rosen's theorem applies and this game has a restricted
equilibrium.
\hfill$\Box$

\section{Proof of Lemma~\ref{lemma}}
\label{app:lemma}

\proof
The proof relies on Kakutani's fixed point theorem.  We first need to
show some facts about the restricted best-response function.  First,
remember that $\rPi_i$ is non-empty and compact.  Also, note that the
value (with both discounted and average reward) to a player at any
state of a joint policy is a continuous function of that joint
policy~\cite[Theorem 4.3.7 and Lemma 5.1.4]{FilarVrieze97}. Therefore,
from basic analysis~\cite[Theorem 3.5 and Corollary 3.11]{Gaughan93},
the set of maximizing (or optimal) points must be a non-empty and
compact set.  So $\rBR_i(\pi_{-i})$ is non-empty and compact.

Define the set-valued function, $F : \rPi \rightarrow \rPi$,
\[
F(\pi) = \times_{i=1}^{n} \rBR_i(\pi_{-i}).
\]
We want to show $F$ has a fixed point.  To apply Kakutani's fixed
point theorem we must show the following conditions to be true,
\begin{enumerate}
\item $\rPi$ is a non-empty, compact, and convex subset of a Euclidean space,
\item $F(\pi)$ is non-empty,
\item $F(\pi)$ is compact and convex, and
\item $F$ is upper hemi-continuous.
\end{enumerate}
Since the Cartesian product of non-empty, compact, and convex sets is
non-empty, compact, and convex we have condition (1) by the
assumptions on $\rPi_i$.  By the facts of $\rBR_i$ from above and the
lemma's assumptions we similarly get conditions (2) and (3).

What remains is to show condition (4).  Consider two sequences
$x^j\rightarrow x\in\rPi$ and $y^j\rightarrow y\in\rPi$ such that
$\forall j\; y^j\in F(x^j)$.  It must be shown that $y\in F(x)$, or
just $y_i\in\rBR_i(x)$.  Let $v$ be $y_i$'s value against $x$.  For
the purposes of contradiction assume that there exists a $y_i'$ with
higher value, $v'$, than $y_i$.  Let $\delta = v' - v$.  Since the
value function is continuous, we can choose a point in the sequence
where the policies are close enough to their limit points that they
make an arbitrarily small change to the value.  Specifically, let $N$
be large enough that the value of $y_i'$ against $x^N$ differs from
$v'$ by at most $\delta/4$, and the value of $y_i$ against $x^N$
differs from $v$ by at most $\delta/4$, and the value of $y^N_i$
against $x^N$ differs from $y_i$ against $x^N$ by at most $\delta/4$.
Adding all of these together, we have a point in the sequence $y^N_i$
whose value against $x^N$ is less than the value of $y_i'$ against
$x^N$.  So $y^N_i \notin \rBR_i(x^N)$, and therefore $y^N \notin
F(x^N)$ creating our contradiction.  The comparison of values of these
various four joint policies is shown in Figure~\ref{fig:proof-lemma}
and helps illustrate the resulting contradiction.

\begin{figure}[htb]
\centerline{\includegraphics[width=0.5\hsize]{figures/proof-lemma}}
\caption{An illustration of the demonstration by contradiction that 
the best-response functions are upper hemi-continuous.}
\label{fig:proof-lemma}
\end{figure}

We can now apply Kakutani's fixed point theorem.  So there exists
$\pi\in \rPi$ such that $\pi\in F(\pi)$.  This means
$\pi_i\in\rBR_i(\pi_{-i})$, and therefore this is a restricted
equilibrium.\hfill$\Box$

\begin{comment}
\section*{Appendix: Lemma~\ref{lem:finite-bias}}

The proof of Theorem~\ref{thm:statewise-convex} in the average reward
formulation uses the following Lemma.

\begin{lemma}
Consider the bias-optimal MDP constructed from an MDP under the
average reward formulation as described in the proof of
Theorem~\ref{thm:statewise-convex}.  If for all states $s$,
$\VV^\pi(s)$ is finite then $\pi$ maximizes average reward in the
original MDP.
\label{lem:finite-bias}
\end{lemma}

\proof
We can see this by examining the definition of average reward from
Equation~\ref{eqn:average-reward},
\begin{eqnarray}
V_i^\pi(s) &=& \lim_{T\rightarrow\infty}\sum_{t=0}^T 
  {1\over T}E\left\{r_t | s_0 = s,\pi\right\} \\
&=& \lim_{T\rightarrow\infty}\sum_{t=0}^T 
  {1\over T}E\left\{(r_t - V^*) + V^* | s_0 = s,\pi\right\} \\
&=& \left(\lim_{T\rightarrow\infty}{1\over T}\sum_{t=0}^T 
  E\left\{(r_t - V^*) | s_0 = s,\pi\right\}\right) + V^*.
  \label{eqn:bounded-bias-optimal} 
\end{eqnarray}
Since $\VV^\pi(s)$ is finite and is the infinite sum of expected
rewards in the bias-optimal MDP (where $\gamma = 1$), there must exist
an infimum, $M$, on all $T$-step expected sum of rewards in the
bias-optimal MDP.  Making this more clear, all finite sums of finite
values must be finite, and since the infinite sum, $\VV^\pi(s)$ is
also finite, then we can bound these sums from below.  This infimum,
$M$, is either attained by some value, $T^*$, or is approached as
$T\rightarrow\infty$, in which case let $T^*$ denote $\infty$.  Then
we can bound Equation~\ref{eqn:bounded-bias-optimal} by,
\begin{eqnarray}
V_i^\pi(s) &\ge& \left(\lim_{T\rightarrow\infty}{1\over T}\sum_{t=0}^{T^*}
  E\left\{(r_t - V^*) | s_0 = s,\pi\right\}\right) + V^*
  \\
&\ge& \left(\lim_{T\rightarrow\infty}{M\over T}\right) + V^*
  \\
&\ge& V^*.
\end{eqnarray}
So, $\pi$ maximizes average reward.
\hfill$\Box$
\end{comment}

\bibliographystyle{theapa}
\bibliography{bowling,rl,gametheory,mas,misc}

\end{document}
