\section{Introduction}

I am interested in the problem of an agent, either a physical robot or
software agent, determining a ``successful''\footnote{Formal
definitions for notions like ``successful'', ``optimal'', and
``rational'', will be given in
Sections~\ref{sec:background}~and~\ref{sec:previous}.} course of
action.  Learning can be a very powerful tool that can greatly
simplify the problem of robot programming.  It also allows a robot to
adapt to unforeseen difficulties in the task.  Learning has been
studied extensively for single-agent problems, where a robot is acting
alone in an unchanging environment.  With robots and agent
technologies becoming more common, domains involving multiple
interacting agents arise.  In multiagent environments, learning is
both more important and more difficult.

In multiagent domains, the agents are forced to interact with other
agents, which may have independent goals, assumptions, algorithms, and
conventions.  In order for robots to handle these environments they
must employ some ability to learn and adapt to the other agents'
behavior.  Since the other agents are also adapting this presents a
very difficult learning problem which violates the basic stationary
assumption of traditional techniques for behavior learning.  Even
defining a desirable policy for the agent is difficult, since it
depends on the policies of the other agents, which are also being
improved through experience.

If the other agents are known to be rational and are learning to
maximize their rewards, then we can consider the game theoretic
concept of equilibria.  Equilibria are sets of policies for the
players where no player receives higher reward for deviating from
their policy.  This means equilibria in some sense are self-enforcing.
Unfortunately, some games have multiple equilibria and therefore it is
important that all the agents play the same equilibrium for it to have
its enforcing effects.  In addition, the fully rational assumption is
not always practical.

Realistically, agents are not always capable of acting optimally.
They may have physical limitations (e.g. broken actuator or
communication link) that make them incapable of behaving in certain
ways.  They also may be using learning techniques that sacrifice
optimality in order to learn more quickly (e.g. function approximation
or subproblem reuse).  That may not even be learning at all.  These
sorts of limitations are real in large, complex environments, and
create scenarios where the other agents involved may not appear to be
acting rationally.  Multiagent learning techniques that are practical
must address this possibility.  My research will develop practical
techniques for learning in the presence of agents with realistic
limitations.

\subsection{Approach}

There are two major steps towards achieving this goal.  The first is
to develop possible learning techniques that might be capable of
learning in these realistic multiagent settings.  The second is to
define what such techniques would be expected to learn.  In multiagent
domains, it is often difficult to define the optimal solution.

\paragraph{Learning Techniques.}
Previous approaches generally fall into two categories.  They either
apply naive single-agent learning algorithms or attempt to learn an
equilibrium directly.  Single-agent learning techniques ignore the
existence of other agents or assume that their behavior is unchanging.
Although they will adapt to maximize their reward given the play of
the other agents, if the other agents are learning then the agent's
behavior may not converge.  In terms that will be formalized in
Section~\ref{sec:previous}, they are rational but not convergent.

Equilibrium learning techniques will always converge to an equilibrium
policy independently of the behavior of the other agents.  They assume
the other agents are completely rational, seeking to maximize the
agent's perception of their reward.  If there are multiple equilibria,
observation of the other agents is required in order for the agents to
agree on an equilibrium.  In addition if the agents have limitations,
converging to a policy independent of their behavior will not allow
the agent to take advantage of (or compensate for) the other agents.
They do not always maximize their reward.  Hence, these techniques
converge, but are not rational.

The first step towards practical multiagent learning is to develop
learning techniques that are both rational and convergent.  In
Section~\ref{sec:previous:rc}, I present an algorithm that moves
towards achieving this goal.  The algorithm has properties of a single
agent learner, in that it constantly seeks to maximize reward.  It
also contains a mechanism that encourages convergence.

\paragraph{Equilibria Under Limitations.}
One of the difficulties facing learning in multiagent settings is
defining the goal of the algorithm.  This difficulty can be seen when
considering the children's game, Rock-Paper-Scissors.  The rules for
this two-player, single-state game are shown in
Table~\ref{table:rps-rules}.  In multiagent environments, as
demonstrated by this simple game, the reward maximizing (or win
maximizing) policy depends on the policy of the other agents.  In this
case, if the other agent were to always select the action {\em Rock}
and were not capable of adapting its policy, the optimal response is
to always play {\em Paper}.  On ther other hand, if the agent were
capable of learning and playing any policy then always playing {\em
Paper} would not be the optimal, or even a good policy.  Instead,
randomizing between all three actions would be the best stationary
policy\footnote{This policy is also the game's equilibrium solution,
which will be explained in detail in
Section~\ref{sec:background:games}.}

\begin{table}
\fbox{\parbox{\hsize}{
\begin{enumerate}
\item Each player simultaneously selects an action from the set 
\{{\em Rock}, {\em Paper}, {\em Scissors}\}.
\item If both players select the same action, they tie.
\item Otherwise, the winner is determined by the following rules:
\begin{itemize}
\item {\em Rock} always beats {\em Scissors},
\item {\em Paper} always beats {\em Rock},
\item {\em Scissors} always beats {\em Paper}.
\end{itemize}
\end{enumerate}
}}

\caption{The rules for the game Rock-Paper-Scissors, which is a 
two-player, single-state game.}
\label{table:rps-rules}
\end{table}

The approach of equilibrium learning techniques is to assume the other
agent is fully capable and rational and so strive to learn a game's
equilibrium strategy.  But if we're interested in learning in
situations where other agents may be limited in some fashion we must
consider a different solution strategy.

My approach is to assume that the other agents may have limitations
but are {\em otherwise rational}.  That is, apart from well defined
(but not publicly known) limitations on their capable behavior or
learning abilities, they seek to maximize their reward.  With this
assumption their may exist an {\em implicit} game with possibly
different actions, rewards, or transitions, under which the other
agent is acting rationally.  This implicit game incorporates the
agent's limitations into the game structure.  If such an implicit game
exists then we can define our desired solution for our multiagent
learning algorithm is one that learns an equilibrium in the implicit
game.

\paragraph{Learning with Limited Agents.}
I plan to apply the developed rational and convergent learning
techniques to successfully learn equilibria in the implicit game when
other agents are limited.  I also plan to examine further areas of
observability to make these algorithms more practical.  Issues of the
observability or knowledge of other agents actions or reward functions
or their observability of state are important in applying these
techniques.  Finally, I plan to examine this work in a complex
multiagent environment where other agents have realistic limitations.

\subsection{Expected Contributions}

\begin{itemize}
\item Multiagent learning algorithms that are rational and convergent.

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

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

\item Investigation of relaxations of these algorithms to handle
partial observability (e.g. opponent's rewards are unknown and
unobservable, opponent's actions are unobservable, POMDPs.)  

\item Examination of knowledge transfer when a task is
identical but the participating agents (and their associated
limitations) change.
\end{itemize}
