\section{Proposed Research}

I propose to study the problem of learning to act in the presence of
other learning agents, specifically when these agents may have
realistic limitations on their capabilities or rationality.  In
general this problem can be nearly impossible as other agents can
arbitrarily change their actions, which reduces the problem to that of
learning in an arbitrary non-stationary environment.  Realistically,
other agents rarely change their policies arbitrarily.  Rather they
adapt their behavior towards specific goals.  It is precisely this
regularity that makes the multiagent learning problem possible.

As I presented in Section~\ref{sec:background}, current multiagent
algorithms rely on the assumption that agents always act optimally.
They limit what they can learn to equilibrium solutions, which are the
only stationary strategies that make sense against an agent that is
perfectly optimal.  In situations where multiple equilibria exist, the
exact rewards of the other agents are unknown and unobservable, or
where agents can not or do not act perfectly optimal, then these
algorithms don't make sense.  I propose to develop learning algorithms
to specifically address the latter case, where agents do not always
act optimally.  I hope, though, to apply the same techniques to the
other multiagent situations where current techniques fail.

In particular, I propose to:
\begin{itemize}
\item Continue development of multiagent learning algorithms that 
are rational and convergent.

\item Examine the existence of equilibria in
stochastic games when other players have limitations.

\item Investigate extensions of rational and convergent learning
algorithms to address limited agents.

\item Examine questions that arise in multiagent learning, such as
partial observability and knowledge transfer.
\end{itemize}
The specifics of my proposed research are divided into the problems
and issues which I will definately investigate, and other work which I
hope to address.

\subsection{Expected Work}

\subsubsection{Rational and Convergent Learning Techniques}

The rational and convergent properties embody much of the goal of
learning with multiple agents.  I am interested in learning techniques
that are rational and will converge against a class of players that
includes practical learning techniques, which may be subject to
limitations.  A first step towards this goal is to focus on players at
the two extremes of the limitation continuum: players that are
completely rational and players that do not learn at all (i.e. they
follow stationary policies.)

I have begun work on developing learning techniques that will converge
to best-response policies when playing agents that do not learn and
agents that are using the same learning technique.  I plan to continue
the development of these techniques, both with further empirical study
and to understand them from a theoretical perspective.  Specifically I
intend to,

\begin{itemize}
\item Extend the APHC principle to construct other learning techniques 
(e.g. model-based learner, SARSA on-policy learner.)
\item Develop an extension of Exp3 to stochastic games.
\item Examine these algorithms in more large scale domains.
\item Analyze the dynamics of the algorithm theoretically.
\end{itemize}

\subsubsection{Equilibria with Limited Agents}

In order to extend the principles of rational and convergent learners
to learning in the presence of agents with limitations, it first must
be determined what is the ``goal'' of these algorithms.  I am
interested in learning against other agents that have limitations but
are {\em otherwise rational}.  That is they seek to maximize their
reward within the scope of their limitations.\footnote{This is not
unlike the notion of {\em bounded-optimal} agents by
Russell~\citeyear{Russell97} applied to the other agents of a
multiagent system.}  If we want a rational and convergent learner for
this class of other players, then we know that what the players
converge to must be an equilibria solution given the limitation.  That
is, the player must be playing best responses given their limitations
to the other players' policies.

An important question that needs answered in order to address this
problem is wether such an equilibrium exists under various type of
limitations.  This is not trivial.  For example, consider the
limitation restricting a player to only play deterministic policies.
Clearly in the game R-P-S there is no equilibrium given this
limitation.  

Some limitations, on the other hand, do still preserve the existence
of equilibrium.  Consider the limitation which restricts a player to
only playing linear combinations of a subset of actions.\footnote{This
is in fact a crude form of policy approximation by reducing the number
of parameters that define a strategy or policy.}
Figure~\ref{table:equilibrium-limitation} shows an example of this
situation in R-P-S where one player can only player linear
combinations of the strategies $s_1$ and $s_2$.  With this sort of
limitation, it can be viewed that the limited player is actually
unlimited in the context of a different SG, which I call the {\em
implicit game}.  This implicit game has an equilibrium which can also
be represented in the explicit game.

\begin{table}
\centerline{\psfig{figure=figures/rps-limit-ex.eps,width=0.4\hsize}}
\[
\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} 0 & -\frac{1}{2} \\[0.5ex] -\frac{1}{2} & \frac{1}{2} \\[0.5ex] 0 & \frac{1}{2}  
\end{array}\right) \\[5ex]

\mbox{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{1}{3}, \frac{2}{3}\right> \\[2ex]

\mbox{Limited 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 an equilibrium under limitations.  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{table:equilibrium-limitation}
\end{table}

I propose to investigate the existence of equilibria under
limitations, defining which limitations still preserve equilibria.  I
hope to determine classes of limitations that can be modeled as an
implicit game.  I also hope to define a broader class of policy
limitations that still contain an equilibrium.  Specifically I hope to
prove the following conjecture,
\begin{conjecture}
\label{conj:equilibrium}
For any zero-sum stochastic game, $(2, \SS, \AA_{1,2}, T, R_{1,2})$,
where player 2's set of available policies, $\Pi_2$, is convex and
compact.  There exists policies, $\pi_1$ and $\pi_2$ such that,
\[
\forall s\in\SS \quad\quad
\begin{array}{rcl}
V_1^{\pi_1,\pi_2}(s) &\ge& 
  \max_{\pi_1' \in PD(\AA_1)} V_1^{\pi_1',\pi_2}(s),\quad \mbox{and}\\
V_2^{\pi_1,\pi_2}(s) &\ge& 
\max_{\pi_2' \in \Pi_2} V_2^{\pi_1, \pi_2'}(s).
\end{array}
\]
\end{conjecture}
The conjecture claims that if a player is restricted to a policy space
that is compact and convex, then there still exists an equilibrium
point within the player's restricted space of policies.

\subsubsection{Learning with Limited Agents}

I propose to extend my original work with rational and convergent
learners and build upon my results of the existence of equilibria
under limitations to the problem of learning in the presence of
limited agents.  I plan to investigate empirical learning in the
context of agents with various realistic limitations.  These
limitation include:
\begin{itemize}
\item Physical limitations such as inability to execute certain
actions, or the inability to distinguish between which of its actions
get executed.
\item Function approximation, specifically those that limit the space
of policies that can be executed.
\item Use of subproblems.
\item Maximizing an incorrect/different reward function.
\item Partial observability or state aliasing.
\end{itemize}
All of these limitations in some form restrict the agent to learning
often suboptimal solutions.  This means current learning techniques
(e.g. Q-learning or Minimax-Q) will not be able to converge to
policies that can take advantage of or compensate for the other
agents' limitations.  On the other hand, the scaling of reinforcement
learning and the practical application to real problems demand these
limitations making this problem critical to making multiagent learning
actually practical.

Many of these limitations can be embodied within the notion of an
implicit game, therefore preserving the existence of equilibrium.
Others can fit into the assumptions of
Conjecture~\ref{conj:equilibrium} and so also may have an equilibrium.
This shows at least that it is possible for rational and convergent
learners to exist within the limited agent framework.  I believe that
algorithms similar to APHC from Section~\ref{sec:previous:rc} show
promise to be able to extend to these situations.  I propose to
examine such algorithms in detail within a realistic multiagent
domain.

\subsection{Possible Work}

\subsubsection{Partial Observability}

Partial observability is an important issue in the application of
learning algorithms to practical problems.  The issues that arise in
single-agent still remain in the multiagent learning problem.
Although, the explicit representation of a mixed policy can be helpful
for learning in POMDPs~\cite{Singh94}.

Additionally, a number of new partial observability issues are raised
in the multiagent setting.  The observability of the action's selected
by the other agents may not be feasible.  Likewise, the actual rewards
received by the other agents may not be known or observable, or may be
partially observable.  I hope to address some of these issues in my
development of multiagent learning techniques.

\subsubsection{Multiagent Knowledge Transfer}

Another issue in multiagent learning is that of knowledge transfer.
The goal we present in this paper is to perform on-line learning of a
best response policy when playing specific other players, possibly
with limitations.  This raises the question of what sort of knowledge
can be transferred to playing against different players that may have
different limitations.  One obvious approach is to specifically learn
a model of the transition function, which would easily transfer when
changing opponents.

What is not obvious, is whether other higher-level knowledge might
still be useful?  For example, would the knowledge of an equilibrium
solution for playing a particular player, be useful when learning
against another player, where the equilbrium may be different?  Is
there other high-level, player independent knowledge about the
structure of a game that may be useful to speed learning.  I hope to
consider some of these questions in my research.

\subsection{Evaluation}

The evaluation of my work will be based on compelling results of
multiagent learning techniques in a non-trivial domain, involving
other learning agents with realistic limitations.  I tentatively plan
to apply these learning techniques to the RoboCup Rescue
domain~\cite{KitanoEtAl99}, a simulated multiagent search and rescue
task that is in development.

I will also produce theoertical results about the rationality and
convergent propertis of the developed learning algorithms.  I will
also examine theoeretically the existence of equilibria in the
presence of agents with limitations.  Although, I hope these results
will have practical implications they will likely involve a number of
restrictions on the game structure (e.g. zero-sum), the other players
(e.g. a simpler model of learning), and the applicable classes of
limitations.

