\section{Previous Work}
\label{sec:previous}

\def\figsize{0.5\hsize}

%- ICML '00 Hu --------------------------------
\subsection{Q-Learning for General-Sum Games}
\label{sec:previous:hu}

Hu \& Wellman~\yrcite{HuWellman98} introduced a Q-learning method for
solving general-sum stochastic games.  Their algorithm is an extension
of Minimax-Q, and replaces the computation of the value of a zero-sum
game with the computation of the value of a general-sum game.  The
algorithm strives to maintain the same property of Minimax-Q that it
can learn equilibria independent of the actions selected by the other
players.

The algorithm, like Minimax-Q, maintains $Q$ values for every
state/joint-action pair.  Since the agents' rewards in general-sum
games can be completely independent, multiple $Q$ values (one for each
agent) must be maintained for each state/joint-action pair.  The entry
$Q^k(s, a)$ approximates the expected discounted reward for player $k$
if the players select joint action $a$ from state $s$ and then follow
the same Nash equilibrium of the stochastic game.  On an observation,
$\left<s, a, s', r^i\right>$ where $r^i$ is an $n$-vector of each of
the agents' rewards, the update is,
\[
Q^i(s, a) \leftarrow (1-\alpha)Q^i(s, a) + \alpha(r^i + \gamma V^i(s')),
\]
where,
\[
V^i(s') = \Value^i Q(s')
\]
For ease of notation we use $Q(s)$ to represent the general-sum matrix
game that is represented by the $n$ matrices whose entries correspond
to $Q^i(s, a \in \AA)$.  So in the update rule the $\Value^i$
operation computes the equilibrium value to player $i$ of the
general-sum matrix game defined by the $Q$ values at the state,
$s'$\footnote{Finding the value of a general-sum game requires an
involved quadratic programming solution~\cite{FilarVrieze97}.}.  Since
the update operation makes use of the equilibrium value of a state,
this is only well-defined if there is a single equilibrium (or
multiple equilibria with the same value.)  It is assumed for their
algorithm and theoretical results that there is in fact a unique
equilibrium.

Their main result is the theorem below.  The theorem claims
convergence of the algorithm for two-player, general-sum games.  In
the theorem, $r^k_t$ refers to the immediate reward received by player
$k$ at time $t$, and $\pi^1(s)Q^k(s)\pi^2(s)$ refers to player $k$'s
expected value of playing the matrix game $Q(s)$ where the players
select actions according to the strategies, $\left(\pi^1(s),
\pi^2(s)\right)$.
\begin{theorem}
\label{thm:main}
\cite{HuWellman98}
Under assumptions below, let the sequences $\left(Q^1_t, Q^2_t\right)$
be updated by,
\begin{eqnarray*}
Q^k_{t+1}(s, \left<a^1, a^2\right>) &=& 
  (1 - \alpha_t) Q^k_t(s, \left<a^1, a^2\right>) + \\ &&
\alpha_t\left(r^k_t + \gamma \pi^1(s')Q^k_t(s')\pi^2(s')\right), \\
\end{eqnarray*}
where $\left(\pi^1(s), \pi^2(s)\right)$ is a mixed strategy Nash
equilibrium for the matrix game $\left(Q^1_t(s'), Q^2_t(s')\right)$.
Then these sequences converge to the Nash equilibrium Q values
$\left(Q^1_*, Q^2_*\right)$ defined by,
\[
Q^k_*(s, \left<a^1, a^2\right>) = 
r^k_t + \gamma \pi_*^1(s')Q^k_t(s')\pi_*^2(s'),
\]
where $\left(\pi_*^1(s), \pi_*^2(s)\right)$ is a Nash equilibrium for
the stochastic game.
\end{theorem}
The theorem requires three assumptions.  Two of these assumptions deal
with exploration and the proper decay of the learning rate.  These are
the standard assumptions of Q-learning and are not provided in this
paper.  The final assumption deals with the nature of the matrix games
that are faced while learning.
\begin{assumption}
\label{asm:orig}
\cite{HuWellman98}
A Nash equilibrium $\left(\pi^1(s), \pi^2(s)\right)$ for any matrix
game $\left(Q^1_t(s), Q^2_t(s)\right)$ satisfies one of the following
properties:
\begin{enumerate}
\item The equilibrium is a global optimal.
\[
\forall \rho^k \quad 
\pi^1(s)Q^k(s)\pi^2(s) \ge \rho^1(s) Q^k(s) \rho^2(s) 
\]
\item The equilibrium receives a higher payoff if the other agent 
deviates from the equilibrium strategy.
\[
\begin{array}{cc}
\forall \rho^k \quad &
  \pi^1(s)Q^1(s)\pi^2(s) \le \pi^1(s) Q^1(s) \rho^2(s) \\
& \pi^1(s)Q^2(s)\pi^2(s) \le \rho^1(s) Q^2(s) \pi^2(s) 
\end{array}
\]
\end{enumerate}
\end{assumption}
It is interesting to note what matrix games the properties encompass.
The first property states that there's a set of strategies for the
players where each player individually receives its maximum possible
payoff.  This also ensures that such a set of strategies is an
equilibrium, since no player could benefit from deviating from the
strategy.  The second property states that the Nash equilibrium for
the game is a ``saddle point''.  This means that not only does a
player {\em not benefit} from deviating from the equilibrium, but also
that all other players {\em do benefit} if the player deviates.
Notice that all zero-sum games satisfy this second property.


The proof of their theorem makes use of a crucial lemma claiming their
update function is a contraction mapping.  Let $P^k_t$ be an update
function defined as,
\[
P^k_tQ^k(s) = r^k_t + \gamma\pi^1(s)Q^k(s)\pi^2(s),
\]
where $(\pi^1(s), \pi^2(s))$ are a Nash equilibrium for the two-player
matrix game where the matrices are $\left(Q^1(s), Q^2(s)\right)$.
Notice that this is the same update function as in
Theorem~\ref{thm:main}, but without the stochastic approximation.
Their lemma claims that $P^k_t$ satisfies the following property,
\[
\forall Q^k \quad\quad ||P^k_tQ^k - P^k_t Q_*^k|| \le \gamma ||Q^k - Q_*^k||,
\]
where $|| \cdot ||$ is the max-norm operator over all states and
actions.  This lemma effectively states that the update function will
always move $Q^k$ closer to $Q_*^k$.

\subsubsection{Counterexample and Flaw}
\label{sec:previous:hu:flaw}

In this section we show a counterexample to their lemma and also the
flaw in their proof of it.  We follow this by introducing strengthened
assumptions under which the lemma is valid.

\paragraph{Counterexample.}
Consider the stochastic game with three states shown in
Figure~\ref{fig:sg}.  State $s_0$ always transitions to state $s_1$
with rewards 0.  State $s_1$ is a $2 \times 2$ game with all actions
causing the game to transition to a terminating state, $s_2$.

\begin{figure*}[htb]
\begin{center}
\makebox[5in][l]{\input{figures/cex.epic}}
\bigskip
\[
Q^*(s_1) = (\gamma(1 - \epsilon), \gamma(1 - \epsilon))
\hspace{0.3in}
Q^*(s_1) = 
\left(\begin{array}{ll}
1,   1 & 1-2\epsilon, 1+\epsilon \\
1+\epsilon, 1-2\epsilon & \fbox{$1-\epsilon,  1-\epsilon$} \\
\end{array}\right)
\hspace{0.3in}
Q^*(s_2) = (0, 0)
\]
\end{center}
\caption{
A three state stochastic game, including the Nash equilibrium values,
$Q^*$.  All transitions are deterministic and are independent of the
actions selected.  The only choice available to the agents is in state
$s_1$, where the corresponding matrix game has a unique Nash
equilibrium where both players choose their second action.}
\label{fig:sg}
\end{figure*}

Consider the following $Q$ function,
\begin{eqnarray*}
Q(s_0) &=& (\gamma, \gamma) \\
Q(s_1) &=& 
\left(\begin{array}{ll}
\fbox{$1+\epsilon, 1+\epsilon$} & 1-\epsilon,  1 \\
1  , 1-\epsilon & 1-2\epsilon, 1-2\epsilon \\
\end{array}\right) \\
Q(s_2) &=& (0, 0).
\end{eqnarray*}
The matrix game corresponding to $Q(s_1)$ has a unique Nash
equilibrium where both players choose their first action.  Notice that
$|| Q - Q_* || = \epsilon$.  If $P$ is a contraction mapping then
after applying $P$ the values should be closer to $Q^*$.  The actual
values for $PQ$ are,
\begin{eqnarray*}
PQ(s_0) &=& (\gamma(1 + \epsilon), \gamma(1 + \epsilon)) \\
PQ(s_1) &=& 
\left(\begin{array}{ll}
1,   1 & 1-2\epsilon, 1+\epsilon \\
1+\epsilon, 1-2\epsilon & \fbox{$1-\epsilon,  1-\epsilon$} \\
\end{array}\right) \\
PQ(s_2) &=& (0, 0).
\end{eqnarray*}
Notice that $|| PQ - PQ^* || = 2\gamma\epsilon$, which is greater than
$\epsilon$ if $\gamma > 0.5$.  Hence, with the max norm $P$ is not a
contraction mapping and the lemma is false.

\paragraph{Proof Flaw.}
The flaw in their proof of the lemma is due to a missing case.  It
handles the case where $Q_*(s)$ meets property 1 of
Assumption~\ref{asm:orig}, and the case where $Q(s)$ meets property 2
of Assumption~\ref{asm:orig}.  It fails to address when $Q_*(s)$ meets
property 2 and $Q(s)$ meets property 1.  This is exactly the case of
the counterexample.  The matrix games $Q(s_1)$ and $Q_*(s_1)$ both
have unique pure strategy equilibriums (as shown by the boxes in their
respective matrices.)  The Nash equilibrium of $Q(s)$ meets property 1
because both players playing their first action is the best either
player can do.  The Nash equilibrium of $Q_*(s)$ meets property 2
because it's a "saddle point", that is if a player deviates from the
equilibrium the other player gets rewarded.  So the counterexample
does indeed satisfy their assumptions.

It is important to note that the counterexample and flaw only show
that the backup used by the algorithm is not a contraction mapping
using the max norm.  This does not necessarily disprove Theorem
\ref{thm:main}, as there may be another norm for which the backup {\em
is} a contraction mapping.  On the other hand, it leaves open whether
the theorem is actually true and provides evidence to the contrary,
which is discussed further in
Section~\ref{sec:previous:hu:discussion}.

\subsubsection{Strengthened Assumptions}
The original assumption on which their proof is based can be
strengthened in order to make the crucial lemma true.  This is done by
simply ruling out the case not handled in their proof and under which
the counterexample falls.
\begin{assumption}
\label{asm:new}
The Nash equilibrium of all matrix games, $Q_t(s)$, as well as
$Q_*(s)$ must satisfy property 1 in Assumption~\ref{asm:orig} {\bf\em
or} the Nash equilibrium of all matrix games, $Q_t(s)$, as well as
$Q_*(s)$ must satisfy property 2 of Assumption~\ref{asm:orig}.
\end{assumption}
This new assumption, although making the original theorem true, places
heavy limitations on the applicability of the results.  This is
examined in the next section.

\subsubsection{Discussion}
\label{sec:previous:hu:discussion}

In this section we discuss the applicability of Theorem~\ref{thm:main}
with the strengthened assumption that it requires.  We also examine
other issues surrounding the problem of convergence in general-sum
stochastic games.

\paragraph{Applicability of the Theorem.}

Under strengthened Assumption~\ref{asm:new} the theorem has a number
of limitations.  One of these limitations was also problematic under
the original assumption, but is even more so under Assumption~\ref{asm:new}.

The first limitation is that if the current $Q_t$ values satisfy the
assumption and the $Q_*$ values are known to satisfy the assumption,
there's still no guarantee that future $Q_{t+1}$ values will satisfy
the assumption.  Since no guarantees are made on future values, the
theorem cannot actually guarantee convergence.  Rather it only
guarantees that {\em if} the $Q$ values converge while always
satisfying the assumption, then they've converged to the game's
equilibrium.  Since Assumption~\ref{asm:new} makes a further
requirement that the values always satisfy the {\em same property},
this only magnifies this problem.

The second limitation is due directly to the strengthened assumption.
The $Q$ values must always satisfy the same property that the unknown
$Q^*$ values satisfy.  Although, the $Q$ values can be initialized to
satisfy both properties (e.g. by initializing all the values to zero),
the initial steps of learning will undoubtedly move the $Q$ values
into satisfying only one of the properties.  The theorem, then, only
guarantees convergence if the unknown $Q^*$ values for the stochastic
game satisfies the {\em exact same} property.

\paragraph{Convergence in General-Sum Games}

One question that arises is why general-sum games are more problematic
for convergence of learning algorithms.  The counterexample presented
in this paper gives some insight into this question.  Small changes in
the values of joint-actions can cause a large change in the state's
Nash equilibria.  This can cause drastic changes in the value of that
state.  Overall, this means small changes in values can propagate into
even larger changes in values.  This is evident in the counterexample
where an $\epsilon$ change in the $Q$ values propagates into a
$2\epsilon$ change.

Despite this fact, there are some classes of general-sum stochastic
games where convergent learning is not so problematic.  In fact, there
is a large class where even naive single-agent learners (e.g. standard
Q-learning~\cite{Watkins89}) can find Nash equilibria.  Fully
collaborative games, where all the agents have identical reward
functions, can be learned by simple
Q-learners~\cite{ClausBoutilier98}.  Games that are iterated dominance
solvable, where the process of eliminating universally inferior
policies by the players leaves only Nash equilibria policies, are also
solvable by naive learning~\cite{FudenbergLevine98}.

In fact even stochastic games that do not fall under these two
categories can still be solved with single-agent learners.  Consider
the two-agent gridworld game depicted in Figure~\ref{fig:game-gw},
which was introduced as an example domain for the Hu \& Wellman
algorithm~\cite{Hu99}. The agents start in two corners and are trying
to reach the goal square on the opposite wall.  The players have the
four compass actions (i.e. N, S, E, and W), which are in most cases
deterministic.  If the two players attempt to move to the same square,
both moves fail.  To make the game interesting and force the players
to interact, from the initial starting position the North action is
uncertain, and is only executed with probability 0.5.  The optimal
path for each agent, then, is to move laterally on the first move and
then move North to the goal, but if both players move laterally then
the actions will fail.  There are two Nash equilibria for this game.
They involve one player taking the lateral move and the other trying
to move North.  

\begin{figure}[htb]
\centerline{\psfig{figure=figures/game-gw.eps,width=1in}}
\caption{Gridworld game.  The dashed walls represent the actions 
that are uncertain.}
\label{fig:game-gw}
\end{figure}

\begin{table}[htb]
\begin{center}
\begin{tabular}{lcc}
Strategy & \multicolumn{2}{c}{Trials} \\
\hline
W-N             & 114 & (57\%) \\
N-E             & 86  & (43\%) \\
Other           & 0   & (0\%) \\
\hline
Total           & 200 & (100\%) \\
\end{tabular}
\end{center}
\caption{
Q-learning for the gridworld game.  The table shows the number of
trials where the players converged to a particular policy.  ``W-N''
and ``E-N'' correspond to the two Nash equilibria where one player
moves laterally in initial state while the other tries to move North.
``Other'' corresponds to all other policies.}
\label{table:results}
\end{table}

Table~\ref{table:results} shows the results of training two agents in
the gridworld game, using standard Q-learning.  The agents were
trained with a decayed learning rate for one million steps to be sure
the policies had converged.  The table shows how often the agents
converged to specific policies in the 200 trials.  The important
thing to note is that the agents always converged to one of the game's
Nash equilibria.  So naive single-agent learners can also converge to
Nash equilibrium in games that aren't fully-collaborative or iterated
dominance solvable.  Understanding what characterizes these easier
general-sum games may be helpful for isolating the difficulties
present in other general-sum games.

%- NIPS '00 -----------------------------------
\subsection{Rational and Convergent Learning}
\label{sec:previous:rc}

\subsubsection{Motivation}
\label{sec:previous:rc:motivation}

Before presenting our new learning technique, we first introduce two
properties that are desirable for a multiagent learner.  We also
examine how current multiagent RL techniques compare to these criteria.

\paragraph{Properties.}

The following are two desirable properties in a multiagent learning
algorithm, where all the players are learning simultaneously.

\begin{property} (Rational)
If the other players' strategies converge to stationary strategies
then the player will converge to a strategy that is optimal given
their strategies.
\end{property}

\begin{property} (Convergent)
Given that the other players are following behaviors from a class of
behaviors, ${\cal B}$, all the players will converge to stationary
strategies.
\end{property}

The first property requires the player to behave optimally when the
other players find stationary strategies.  The second property
requires that for some class of behaviors (i.e. learning algorithms)
for the other players (ideally a well-encompassing class) the
strategies will indeed converge.  In this paper we focus on the
convergence of a learning algorithm when playing other agents that are
using the same algorithm.  This is a crucial yet difficult first step
towards examining convergence with more general classes of behaviors.
In combination, these two properties guarantee that the player will
converge to a stationary strategy that is optimal given the play of
the other players.

It is interesting to note that when all players are rational, if they
converge they must have converged to a Nash equilibria.  Since the
other players converge to a stationary policy, each player must
converge to a best response to their policies.  Since this is true of
each player, then this is an equilibrium.  If all players satisfy {\em
both properties} with classes that include the other players'
behavior, then convergence to a Nash equilibrium is guaranteed.

Some additional justification for the desirability of these properties
is given later in Section~\ref{sec:previous:rc:discussion}.

\paragraph{Other Reinforcement Learners.}

There are few RL techniques that directly address learning in a
multiagent system.  We examine three RL techniques: independent
learners (ILs), joint-action learners (JALs), and minimax-Q.  ILs are
single agent learning algorithms and so capture the existence of other
agents as part of the environment (e.g. Q-learning~\cite{Watkins89},
TD($\lambda$)~\cite{Sutton88}, prioritized
sweeping~\cite{MooreAtkeson93}, etc.)  This is the most common
approach to learning in multiagent systems, even though the MDP
assumption of stationary transition probabilities is violated.  JALs
and minimax-Q are aware of the other players, but account for them
differently.

\subparagraph{Independent Learners.}

ILs are just the naive application of single agent (MDP) algorithms to
multi-agent domains (SGs).  They ignore the existence of other agents,
assuming their rewards and transitions are Markov and stationary.  As
a result, these algorithms only learn deterministic policies.  This
naive approach does satisfy one of the two properties.  If the other
agents play, or converge to, stationary strategies then their
Markovian assumption holds and they converge to an optimal response.
So, an IL is rational.  On the other hand, it is not generally
convergent with other players that are rational.  This is obvious in
games where the equilibrium is a mixed policy, which ILs cannot learn.

\subparagraph{Joint Action Learners.}

JALs~\cite{ClausBoutilier98}, or opponent modelling
Q-learning~\cite{UtherVeloso97}, observe the actions of the other
agents.  They assume the other players are selecting actions based on
a stationary policy, which they learn and play optimally with respect
to this learned policy.  Like ILs they are rational, but not
convergent, since they also cannot learn mixed policies.

\subparagraph{Minimax-Q.}

Minimax-Q~\cite{Littman94} and Hu \& Wellman's extension of it to
general-sum SGs~\citeyear{HuWellman98} take a different approach.
These algorithms observe both the actions and rewards of the other
players and try to learn a Nash equilibrium explicitly.  The
algorithms learn and play the equilibrium independent of the behavior
of other players.  These algorithms are convergent with rational
players, since they always converge to a stationary policy, so the
other players being rational will converge to optimal responses.
However, these algorithms are not rational.  This is most obvious when
considering a game of Rock-Paper-Scissors against an opponent that
almost always plays ``Rock''.  Minimax-Q will still converge to the
equilibrium solution, which is not optimal given the opponent's
policy.

\subparagraph{}
In essence, we are looking for a learning technique that is rational,
and therefore plays optimally when playing not necessarily rational
players.  Yet, it should still be capable of converging to mixed
policies.  We want the rational behavior of ILs and JALs, and the
convergent behavior of minimax-Q.  

\subsubsection{A New Algorithm}
\label{sec:previous:rc:APHC}

In this section we contribute an algorithm towards the goal of a
rational and convergent learner.  We first introduce an algorithm that
is rational and capable of playing mixed policies, but does not
converge in empirical experiments.  We then introduce a modification
to this algorithm that results in a rational learner that does
converge to mixed policies.

\paragraph{Policy Hill Climbing.}
A simple extension of Q-learning to play mixed strategies is policy
hill-climbing (PHC) as shown in Table \ref{alg:phc}.
\begin{table}[hbt]
\abovedisplayskip3pt
\belowdisplayskip3pt
\fbox{\parbox{\hsize}{
\begin{enumerate}
\item Let $\alpha$ and $\delta$ be learning rates.  
Initialize,
\[
Q(s, a) \leftarrow 0, \qq 
\pi(s, a) \leftarrow {1 \over |\AA_i|}.
\]

\item Repeat,
\begin{enumerate}
\item From state $s$ select action $a$ according to mixed strategy $\pi(s)$
with some exploration.

\item Observing reward $r$ and next state $s'$,
\[
Q(s, a) \leftarrow (1 - \alpha)Q(s, a) + 
  \alpha\left(r + \gamma \max_{a'} Q(s', a')\right).
\]

\item Update $\pi(s, a)$ and constrain it to a legal probability distribution,
\[
\begin{array}{lll}\pi(s, a) & \leftarrow & \pi(s, a)
  + \left\{ \begin{array}{c@{\hspace{2ex}}l} 
                           \delta & \mbox{if $a = \argmax_{a'} Q(s, a')$} \\
                           {-\delta \over |A_i| - 1} & \mbox{Otherwise}
  \end{array} \right. \\
\end{array}.
\]
\end{enumerate}
\end{enumerate}
}}
\medskip
\caption{The policy hill-climbing algorithm (PHC) for player $i$.}
\label{alg:phc}
\end{table}
The algorithm, in essence, performs hill-climbing in the space of
mixed policies.  Q-values are maintained just as in normal Q-learning.
In addition the algorithm maintains the current mixed policy.  The
policy is improved by increasing the probability that it selects the
highest valued action according to a learning rate $\delta
\in (0, 1]$.  Notice that when $\delta = 1$ the
algorithm is equivalent to Q-learning, since with each step the policy
moves to the greedy policy executing the highest valued action with
probability $1$ (modulo exploration).

This technique, like Q-learning, is rational and will converge to an
optimal policy if the other players are playing stationary strategies.
The proof follows from the proof of Q-learning, which guarantees the
$Q$ values will converge to $Q^*$ with a suitable exploration
policy\footnote{We mostly ignore the issue of exploration in this
paper.  See \cite{SinghEtAl00} for suitable exploration policies for
online learning.}.  Similarly, with a suitable exploration policy
$\pi$ will converge to the policy that is greedy according to
$Q\rightarrow Q^*$, which is a best response.  Despite the fact that it
is rational and can play mixed policies, it still doesn't show any
promise of being convergent.  We show examples of its convergence
failures in Section~\ref{sec:previous:rc:results}.

\paragraph{Adjusted Policy Hill-Climbing.}
We now introduce a modification to the naive policy hill-climbing
algorithm, which encourages the desired convergence property without
sacrificing the rational property.  The algorithm, called adjusted
policy hill-climbing (APHC), consists of a modification to the
algorithm's learning rate.  The modification has a very simple
intuition: ``Learn quickly while losing and slowly while winning.''
The required changes to policy hill-climbing are shown in Table
\ref{alg:ahc}.

\begin{table}[htb]
\abovedisplayskip3pt
\belowdisplayskip3pt
\fbox{\parbox{\hsize}{
\begin{enumerate}
\item Let $\alpha$, $\delta_l > \delta_w$ be learning rates.  
Initialize,
\[
Q(s, a) \leftarrow 0, \qq 
\pi(s, a) \leftarrow {1 \over |\AA_i|}, \qq
C(s)  \leftarrow  0.
\]

\item Repeat,
\begin{enumerate}
\item Same as PHC in Table~\ref{alg:phc}
\item Same as PHC in Table~\ref{alg:phc}
\item Update estimate of average policy, $\bar\pi$,
\begin{eqnarray*}
C(s) &\leftarrow& C(s) + 1 \\
\forall a'\in\AA_i \quad \bar\pi(s, a') &\leftarrow&
{1 \over C(s)}\left(\pi(s, a) - \bar\pi(s, a)\right).
\end{eqnarray*}

\item Update $\pi(s, a)$ and constrain it to a legal probability distribution,
\[
\begin{array}{lll}\pi(s, a) & \leftarrow & \pi(s, a)
  + \left\{ \begin{array}{c@{\hspace{2ex}}l} 
                           \delta & \mbox{if $a = \argmax_{a'} Q(s, a')$} \\
                           {-\delta \over |A_i| - 1} & \mbox{Otherwise}
  \end{array} \right. \\
\end{array},
\]
where,
\[
\delta = \left\{\begin{array}{c@{\hspace{2ex}}l}
    \delta_w & \mbox{if $\sum_{a'} \pi(s, a') Q(s, a') >
                         \sum_{a'} \bar\pi(s, a') Q(s, a')$} \\
    \delta_l & \mbox{otherwise}
  \end{array} \right..
\]
\end{enumerate}
\end{enumerate}
}}
\medskip
\caption{The adjusted policy-hill climbing algorithm (APHC) for player $i$.}
\label{alg:ahc}
\end{table}

This aids in convergence by giving more time for the other players to
adapt to changes in the player's strategy that at first appear
beneficial, while allowing the player to adapt more quickly to other
players' strategy changes when they are harmful.  Practically, the
algorithm requires two learning parameters $\delta_l > \delta_w$.  The
parameter that is used to update the policy depends on whether the
agent's current expected value is greater than the expected value of
the average policy.  If the current expected value is lower (i.e. the
agent is ``losing'') then the larger learning rate $\delta_l$ is used.

Although the learning rate modification may appear to be a somewhat
unfounded heuristic, it has been studied in some form in other areas,
notably when considering an adversary.  In evolutionary game theory
the {\em adjusted replicator dynamics}~\cite{Weibull95} scales the
individual's growth rate by the inverse of the overall success of the
population.  This will cause the population's composition to change
more quickly when the population as a whole is performing poorly.  A
form of this also appears as a modification to the {\it randomized
weighted majority} algorithm~\cite{BlumBurch97}.  In this algorithm,
when an expert makes a mistake, a portion of it's weight loss is
redistributed among the other experts.  If the algorithm is placing
large weights on mistaken experts (i.e. the algorithm is ``losing''),
then a larger portion of the weights are redistributed (i.e. the
algorithm adapts more quickly.)

Adjusted policy hill-climbing is still rational, since only the speed
of learning is altered.  Its convergence properties, though, are quite
different.  In the next section we show examples that this technique
converges to rational policies for a number and variety of stochastic
games.

\subsubsection{Results}
\label{sec:previous:rc:results}

In this section we show results of applying policy hill-climbing and
adjusted policy hill-climbing to a number of different games.  The
domains include two matrix games, which help to show how the
algorithms work and the effect of the adjustment on convergence.  The
algorithms were also applied to two multi-state SGs.  One is a
general-sum grid world domain used by Hu \&
Wellman~\citeyear{HuWellman98}.  The other is a zero-sum soccer game
introduced by Littman~\citeyear{Littman94}.

The experiments involve training the players using the same learning
algorithm.  Since PHC and APHC are rational, we know that if they
converge against themselves, then they must have converged to a Nash
equilibrium.  For the matrix game experiments $\delta_l/\delta_w = 2$,
but for the other results a more aggressive $\delta_l/\delta_w = 4$
was used.  In all cases both the $\delta$ and $\alpha$ learning rates
were decreased proportionately to $1/C(s)$, although the exact
proportion varied between domains.

\paragraph{Matrix Games.}

The algorithm was applied to two common zero-sum matrix games,
matching-pennies and rock-paper-scissors, see
Figure~\ref{fig:game-mg}.  In both games, the Nash equilibrium is a
mixed policy consisting of executing the actions with equal
probability.  The large number of trials and small ratio of the
learning rates were used for the purpose of illustrating how the
algorithm learns and converges.

The results of applying both policy hill-climbing and adjusted policy
hill-climbing to the matching pennies game is shown in
Figure~\ref{fig:results-mp}(a).  APHC quickly begins to oscillate
around the equilibrium, with ever decreasing amplitude.  Without the
adjustment, it oscillates around the equilibrium, but without any
appearance of converging.  This is even more obvious in the game of
rock-paper-scissors.  The results are shown in
Figure~\ref{fig:results-rps}(b,c), and show trajectories of the players'
strategies in policy space through one million steps.  Policy
hill-climbing circles the equilibrium policy without any hint of
converging, while adjusted policy hill-climbing very nicely spirals
towards the equilibrium.

\begin{figure}[htb]
\centerline{\psfig{figure=results/results-mp-strategies.eps,width=\figsize}}
\centerline{(a) Matching Pennies Game}
\begin{tabular}{c}
\psfig{figure=results/results-rps-na-joint-strategies.eps,width=\figsize} \\
(b) RPS: Policy Hill-Climbing
\end{tabular}
\begin{tabular}{c}
\psfig{figure=results/results-rps-joint-strategies.eps,width=\figsize} \\
(c) RPS: Adjusted Policy Hill-Climbing 
\end{tabular}
\caption{(a) Results for the matching pennies matrix game:
the policy for one of the players as a probability distribution while
learning with PHC and APHC. The other player's policy looks similar.
(b, c) Results for the rock-paper-scissors matrix game: trajectories
of the two players' policies while learning with PHC (b), and APHC
(c).}
\label{fig:results-mp}
\label{fig:results-rps}
\end{figure}

\paragraph{Gridworld.}
We also examined a gridworld domain introduced by Hu and
Wellman~\citeyear{HuWellman98} to demonstrate their extension of
Minimax-Q to general-sum games.  The game consists of a small grid
shown in Figure~\ref{fig:game-gw}(a).  The agents start in two corners
and are trying to reach the goal square on the opposite wall.  The
players have the four compass actions (i.e. N, S, E, and W), which are
in most cases deterministic.  If the two players attempt to move to
the same square, both moves fail.  To make the game interesting and
force the players to interact, while in the initial starting position
the North action is uncertain, and is only executed with probability
0.5.  The optimal path for each agent is to move laterally on the
first move and then move North to the goal, but if both players move
laterally then the actions will fail.  There are two Nash equilibria
for this game.  They involve one player taking the lateral move and
the other trying to move North.  Hence the game requires that the
players coordinate their behaviors.

\begin{figure}[htb]
\centerline{\begin{tabular}{cc}
\psfig{figure=figures/game-gw.eps,height=0.75in} &
\psfig{figure=figures/game-soccer.eps,height=0.75in} \\[2ex]
\psfig{figure=results/results-gw-strategies.eps,width=\figsize} &
\psfig{figure=results/results-soccer-v-il.eps,width=\figsize} \\
(a) Gridworld Game & (b) Soccer Game
\end{tabular}}
\caption{(a) Gridworld game.  The dashed walls represent the actions 
that are uncertain. The results show trajectories of two players'
policies while learning with APHC.  (b) Soccer game.  The results show
the percentage of games won against a specifically trained worst-case
opponent after one million steps of training.}
\label{fig:game-gw}
\label{fig:game-soccer}
\label{fig:results-soccer}
\label{fig:results-gw}
\end{figure}

Adjusted policy hill-climbing successfully converges to one of these
equilibria.  Figure~\ref{fig:results-gw}(a) shows an example trajectory
of the players' strategies for the initial state while learning over
100,000 steps.  In this example the players converged to the
equilibrium where player one moves East and player two moves North
from the initial state.  This is evidence that adjusted policy
hill-climbing can learn an equilibrium even in a general-sum game with
multiple equilibria.

\paragraph{Soccer.}

The final domain is a comparatively large zero-sum soccer game
introduced by Littman~\citeyear{Littman94} to demonstrate Minimax-Q.
An example of an initial state in this game is shown in
Figure~\ref{fig:game-soccer}(b), where player 'B' has possession of
the ball.  The goal is for the players to carry the ball into the goal
on the opposite side of the field.  The actions available are the four
compass directions.  The players select actions simultaneously but
they are executed in a random order, which adds non-determinism to
their actions.  If a player attempts to move to the square occupied by
its opponent, the stationary player gets possession of the ball, and
the move fails.  Unlike the grid world domain, the Nash equilibrium
for this game requires a mixed policy.  In fact any deterministic
policy (therefore anything learned by an IL or JAL) can always be
defeated~\cite{Littman94}.

Our experimental setup resembles that used by Littman in order to
compare with his results for Minimax-Q.  Each player was trained for
one million steps.  After training, its policy was fixed and a
challenger using Q-learning was trained against the player.  This
determines the learned policy's worst-case performance, and gives an
idea of how close the player was to the equilibrium policy, which
would perform no worse than losing half its games to its challenger.
Unlike Minimax-Q, APHC and PHC generally oscillate around the target
solution.  In order to account for this in the results, training was
continued for another 250,000 steps and evaluated after every 50,000
steps.  The worst performing policy was then considered the value of
the policy for that learning run.

Figure~\ref{fig:results-soccer}(b) shows the percentage of games won
by the different players when playing their challengers.  ``M-M''
represents Minimax-Q when trained against itself (the results were
taken from Littman's original paper.)  ``APHC-APHC'' represents
adjusted policy hill-climbing trained against itself.  ``PHC-PHC(L)''
and ``PHC-PHC(W)'' represents policy hill-climbing with $\delta =
\delta_l$ and $\delta = \delta_w$, respectively.   ``APHC-APHC(2x)''
represents adjusted policy hill-climbing trained with two million
steps of training.  The performance of the policies were averaged over
fifty training runs and the standard deviations are shown by the lines
beside the bars.  The relative ordering by performance is
statistically significant.

APHC does extremely well, performing equivalently to Minimax-Q with
the same amount of training\footnote{The results are not directly
comparable due to the use of a different decay of the learning rate.
Minimax-Q uses an exponential decay which decreases too quickly for
use with APHC.} and continues to improve with more training.  The
exact affect of the adjustment can be seen by its out-performance of
PHC, using either the larger or smaller learning rate.  This shows
that the success of APHC is not simply due to changing learning rates,
but rather to changing the learning rate at the appropriate time to
encourage convergence.

\subsubsection{Discussion}
\label{sec:previous:rc:discussion}
Adjusted policy hill-climbing is both rational and capable of
converging to mixed policy equilibria.  In this section we present
justification for the importance of these properties.

\subparagraph{Convergence.}
One major reason for desiring techniques that converge to stationary
policies is a matter of practicality.  Non-stationary policies are
very difficult to evaluate, requiring a different value criteria than
discounted future reward (e.g. average reward.)  In addition,
non-stationary policies can add a major complication to the problem of
assigning credit with delayed reward.  If the value of a state can
oscillate as the policy changes then credit assignment based on this
value can lead to an even poorer policy.

\subparagraph{Rationality.}
The alternative to a rational learner is one that directly attempts to
learn a game's equilibrium solution, like Minimax-Q.  Problems with
such an approach is that it assumes the other players will cooperate
and also play according to the equilibrium.  This approach completely
fails with general-sum games that have multiple equilibria, where
selection of the same equilibria is itself a coordination problem with
no answer independent of the other players' policies.

Even if you assume there's a single equilibrium and the other player
is trying to play optimally, there are still reasons why directly
learning the equilibrium may not be desirable.  The other players may
have physical limitations that make them not capable of playing the
equilibrium solution.  They may not be capable of executing some
action, or they can't differentiate between which of their actions get
executed.  The other players may also have rational limitations, such
as using a function approximator to represent policies or values.  We
believe these sorts of limitations are going to become much more
common as multiagent learning begins to address larger problems.

%- IJCAI '99 ----------------------------------

\subsection{Subproblem Reuse as a Limitation}

Before we can proceed we need to formalize the notion of a subproblem
within the frameworks of our restricted class of MDPs.  We also need
to define what it means to {\em use} a subproblem.  These notions
hinge on the definition of the boundary of a set of states.

\begin{definition}
For a set of states, $S$, let the {\em boundary} of $S$, denoted
$B(S)$, be the set of all states not in $S$ with a non-zero
probability transition from a state in $S$.
\end{definition}
In other words the boundary of $S$ are all the states not in $S$ that
are reachable from $S$ in a single time step.

We can now define our notion of a subproblem.
\begin{definition}
A subproblem, $\cal S$, of an MDP, ${\cal P} = (S, A, T, G)$, is a
pair $(S', G')$ satisfying:
\begin{itemize}
\item $S', G' \subseteq S$,
\item $S' \cap G = \emptyset$ and $B(S') \cap G = \emptyset$,
\item $G' \subseteq B(S')$.
\end{itemize}
This definition induces a new MDP over the states $S'$.  The state
transitions remain the same as in $\cal P$, but the reward function is
zero for all transitions except those entering states in $G'$, where
the reward is one.
\end{definition}

Given this notion of a subproblem we want to investigate the effects
of using a subproblem solution.  So we define a formal notion of {\em
using} a subproblem.

\begin{definition}
For a subproblem, ${\cal S} = (S', G')$, of a problem $\cal P$, we say
that a policy, $\pi$ for $\cal P$ {\em uses} $\cal S$ if and only if
$\pi$ restricted to states in $S'$ is optimal for the subproblem,
$\cal S$.  Additionally, the optimal policy for $\cal P$ that {\em
uses} $\cal S$ is denoted $\PiOptUsingS$.
\end{definition}

\subsubsection{Examples}
\label{sec:subproblem:examples}
Given this definition of subproblems and how they are used, we want to
examine the tradeoffs of reusing subproblem solutions.  We explored
this in the context of some simple stochastic maze problems, which are
within our class of goal state MDPs.  The two problems discussed here
are representative of more complex MDPs.

\paragraph{Hallway Example.}
Figure
\ref{fig:hallway-problem} depicts a simple grid environment that was
first investigated by Thrun and Schwartz~\yrcite{Thrun95} within
the context of sharing policies.  The agent has actions that move it
in any of the eight grid directions (including diagonal moves), but
with probability 0.1 its action is ignored and it is moved in a random
grid direction.  There is a single goal state labeled 'G' in the
diagram.  The agent receives a reward of 1 for a transition into the
goal state, and a reward of 0 otherwise.  The agent is trying to
maximize its discounted future reward with a discount factor, $\gamma
= 0.9$.

\begin{figure}[htb]
\centerline{\psfig{figure=figures/hallway-problem.eps,width=\figsize}}
\caption{Hallway example.  Each grid position represents a state.  
`S' denotes the start state, and `G' the goal state.  The shaded
regions mark off two different subproblems.}
\label{fig:hallway-problem}
\end{figure}

The shaded regions in the diagram denote subproblems.  For example the
subproblem of exiting the left room has the dark shaded region as its
state space, $S'$.  The five states in the rightmost half of the
doorway into the middle room are the boundary of $S'$, and in this
case $G' = B(S')$.  Another subproblem is exiting both the left and
middle rooms.  In this case the states, $S'$, would be both shaded
regions, and the goal states would be the five rightmost states of the
doorway to the room on the right.

We explored how using the solution to these subproblems might speed
learning of the complete problem.  We fixed the policy to always
select the subproblem's optimal action while within the subproblem's
state space (i.e. the shaded regions.)  We then use
Q-Learning~\cite{Watkins89} with a decreasing learning factor in order
to learn the optimal policy given this constraint.

\begin{figure}[htb]
\centerline{\psfig{figure=figures/hallway-results.ps,width=\figsize}}
\caption{Results from the hallway example.}
\label{fig:hallway-results}
\end{figure}

The results of this learning can be seen in figure
\ref{fig:hallway-results}.
When we use the subproblem of exiting the left and middle rooms, we
have a huge boost in learning speed.  After visiting 5000 states, it
performs approximately six times better than learning from scratch.
Notice that this sacrifices convergence to the optimal solution.  The
more conservative approach of using the subproblem of exiting just the
left room has a more conservative learning improvement.  After
visiting 5000 states it performs almost three times better than
learning from scratch.  Although the improvement isn't as pronounced,
it appears to converge to an optimal solution.

\paragraph{Doorways Example.}

A second example that we explored consisted of a similar grid world
but with multiple doorways, where $G' \ne B(S')$.  This is depicted in
figure \ref{fig:doorways-problem}.  The actions and transitions remain
the same as was described for the hallways example.  Like that
example, this also has intuitive subproblems, such as reaching a
subset of the three doorways.  We explored this domain using a number
of these subproblems.  Results are shown in figure
\ref{fig:doorways-results} for learning when using the subproblem of
reaching the right doorway, reaching either the right or middle
doorway, and learning from scratch.

\begin{figure}[htb]
\centerline{\psfig{figure=figures/doorways-problem.eps,width=0.28\hsize}}
\caption{Doorways example.  `S' denotes the start state, and `G' the 
goal state.  The shaded region marks off the state space of the
subproblem.}
\label{fig:doorways-problem}
\end{figure}

\begin{figure}[htb]
\centerline{\psfig{figure=figures/doorways-results.ps,width=\figsize}}
\caption{Results from the doorways example.}
\label{fig:doorways-results}
\end{figure}

The results are very similar to the previous example.  Subproblems
speed learning but are likely to converge on a suboptimal solution.
These results also motivate our goal, to be able to make a claim about
the amount of optimality sacrificed in order to gain the improved
learning speed.

\subsubsection{Bounding the Suboptimality}

In order to better judge this tradeoff it is important to know the
suboptimality of the solution obtained.  Formally, we want to find a
bound on the suboptimality of $\PiOptUsingS$.  This would provide us
with a quantitative measure of the trade-off of using $\cal S$ as a
subproblem.  Before we discuss possible bounds we need a notion of
suboptimality.

\begin{definition}
A policy, $\pi$, is {\em $\alpha$-optimal} if and only if $\forall s
\; V^\pi(s) \ge \alpha V^*(s)$.
\end{definition}

Using this definition, $\alpha$ values are in the range $[0, 1]$,
where large values are closer to the optimal solution.  A summary of
the optimality for our examples (figures
\ref{fig:hallway-results} and \ref{fig:doorways-results}) is given in 
table \ref{tab:results}, under the column labeled ``actual''.  These
values were computed by taking the minimum over all states of the
ratio between the value of the state when using the subproblem and the
optimal value of the state.  We can quantify our goal as finding a
guaranteed lower bound for these values without requiring knowledge of
the optimal policy or value.

We will first examine a bound based on Bellman error and give some
empirical results on our examples that show that this bound is not
satisfactorily tight.  We will then introduce a new bound based on
boundary values and show its results on these same examples.

\begin{table*}
\centering\begin{tabular}{|l|l|c|c|c|}
\hline
         & & \multicolumn{3}{c|}{\bf Optimality} \\\cline{3-5}
\bf Example  & \bf Subproblem & \bf Actual & \bf Bellman Bound & \bf Boundary Bound \\\hline
Hallway & Left and Middle Rooms & 0.66 & 0.01 & 0.65 \\\cline{2-5} &
Left Room & 0.99 & 0.22 & 0.98 \\\hline Doorways & Right and Middle
Doorway & 0.99 & 0.38 & 0.77 \\\cline{2-5} & Right Doorway & 0.52 &
0.04 & 0.16 \\
\hline
\end{tabular}
\caption{Comparison of the suboptimality bounds computed from the Bellman 
error and from our method, against the actual suboptimality of using
the subproblem.  Larger values signify a more optimal solution (or a
better guarantee).  }
\label{tab:results}
\end{table*}

\paragraph{Bound Using Bellman Error.}

The use of the Bellman error to bound the suboptimality of a policy
was developed by Williams and Baird~\yrcite{Williams93}.  Bellman
error, as mentioned earlier, is simply the maximum error in the
Bellman equations, and the optimal policy would have a Bellman error
of zero.  They proved the following for all MDPs,
\begin{theorem}
For any value function, $V$, with Bellman error, $\epsilon$.  Let
$\pi$ be a policy greedy for $V$.  Then for all states, $x$,
\[
V^\pi(x) \ge V^*(x) - \frac{2\gamma\epsilon}{1 - \gamma}.
\]
\end{theorem}
Qualitatively, this means we can bound the suboptimality of a policy
by examining the Bellman error of a value function that induces that
policy.

We can use this to compute a bound by simply calculating the Bellman
error of $\VOptUsingS$.  We define a value function that induces
$\PiOptUsingS$ and satisfies the Bellman equations for states in $S$
(because we are using an optimal solution to the subproblem) and also
for states outside of $S$ (because we are acting optimally outside of
$S$.)  Then the only states with a non-zero Bellman error would be on
the boundary of $S$.

\subparagraph{Results from the Examples.}
Table \ref{tab:results} gives the results of using this bound in the
subproblems in subsection \ref{sec:subproblem:examples}.  These values
were computed by finding the optimal solution using the subproblem,
calculating the Bellman error for that value function, and applying
the equation.  The results are quite disappointing.  Even for
subproblems that are nearly optimal (e.g. the left and middle rooms of
the hallway problem) result in a weak constraint on the suboptimality.
The computed bound does not help identify when a subproblem results in
a good solution.

\paragraph{Bound Using Boundary Values.}

The following two definitions play a crucial role in our bound on
suboptimality.  The first provides a quantitative measure of the
stochasticity of a problem.  The second provides a measure for
comparing values of sets of states.

\begin{definition}
\label{def:rho}
Let $\rho_s$ be the probability that following the optimal policy at
$s$ will transition to a state, $s'$, where $V^*(s') < V^*(s)$.  Let
$\rho = \max_{s \in S} \rho_s$.  This captures the stochasticity of
the problem, where $\rho=0$ for a deterministic problem.
\end{definition}

\begin{definition}
For a set of states $S_1$ and $S_2$, and a policy $\pi$, we say $S_1
\ge_\alpha^\pi S_2$ if and only if, 
\[
\forall s_1 \in S_1, s_2 \in S_2 \quad\quad
V^\pi(s_1) \ge \alpha V^\pi(s_2).
\]  
If $S \ge^\pi_\alpha S$ then $S$ is $\alpha$~-equivalent with respect
to $\pi$, i.e. the values of all the states in the set are within
$\alpha$.
\end{definition}

The following theorem provides a bound on the suboptimality of using a
subproblem where the goal states for the subproblem are its entire
boundary.
\begin{theorem}
\label{thm:one}
Given a subproblem ${\cal S} = (S', B(S'))$ of $\cal P$, if $B(S')$ is
$\alpha$-equivalent with respect to $\PiOptUsingS$, then,
\smallskip\centerline{$\PiOptUsingS$ is $\alpha\beta$-optimal for $\cal P$,} \\
\smallskip
where $\beta = {1 - \sigma \over 1 - \sigma\alpha}$ and $\sigma =
{\rho
\gamma^2 \over 1 - (1-\rho)\gamma}$.
\end{theorem}
The $\sigma$ value may appear cryptic but it is simply the discounted
probability of ever reaching a state of lower value.  The value
emerges from the proof which is presented in appendix
\ref{proof:one}.

We have attempted to generalize the theorem to all subproblems with
the following conjecture,
\begin{conjecture}
\label{conjecture}
Given a subproblem ${\cal S} = (S', G')$ of $\cal P$, let $\bar {G'} =
B(S')
\backslash G'$.  If $G' \ge^{\PiOptUsingS}_{\alpha_1} G'$ and 
$\bar {G'} \le^{\PiOptUsingS}_{\alpha_2} S$, then \\
\smallskip
\centerline{$\PiOptUsingS$ is $\alpha_1\alpha_2\beta$-optimal for $\cal P$,} \\
\smallskip
where $\beta = {1 - \sigma \over 1 - \sigma\alpha_1\alpha_2}$ and
$\sigma = {\rho\gamma^2 \over 1 - (1-\rho)\gamma}$.
\end{conjecture}

\begin{theorem}
\label{thm:two}
Conjecture \ref{conjecture} is true if $\cal P$ is deterministic
(i.e. if $\rho = 0$.)
\end{theorem}

Theorem \ref{thm:two} proves the conjecture true for deterministic
MDPs and the $\beta$ factor should provide the necessary adjustment
for the non-determinism as it did in theorem \ref{thm:one}.  The proof
for theorem \ref{thm:two} is given in appendix \ref{proof:two}.

\subparagraph{Results from the Examples.}
Table \ref{tab:results} gives the results of using this bound in our
example subproblems.  The values were computed much like those for the
Bellman error; an optimal solution was learned using the subproblem,
the $\alpha$ values were calculated, and the bound computed.  The
results show a reasonably tight bound, especially for the single exit
subproblems.  Thought it's not as tight on the multiple exit
subproblems it is still much improved over the bound computed from
Bellman error.

This bound provides considerable information as to the loss in
optimality of using a subproblem.  In addition to this guarantee on
the resulting policy it also helps to identify a possibly better
subproblem. This is done by examining the $\alpha$ values.  For
example, in the doorways problem using the right doorway, the
guaranteed optimality is fairly weak.  But, by examining the $\alpha$
values it becomes obvious that this bound could be improved if the
middle door was in the subproblem's goal states.  By using the ``new''
subproblem we achieve a better policy and a better bound on its
suboptimality.

