% This file was updated slightly by Andrew Moore for ICML-2006
% This file was updated slightly by Kristian Kersting for ICML-2005
% from the file made available from the ICML-2004 web site.

% This file was updated by Dale Schuurmans and Jennifer Dy for ICML-2004
% from a file modifed slightly by Terran Lane for to support/document 
% the new option to the ``usepackage'' statement that selects between the 
% review and final version of the paper.

% This file was updated slightly by Tom Fawcett for ICML-2003
% from the file made available from the ICML-2002 web site.

% This file was modified by Claude Sammut for ICML-2002 from the file
% made available by Pat Langley, Claude-Nicolas Fiechter, Mehmet Goker,
% Cynthia Thompson and Andrea Danyluck for ICML-2K and ICLML-2001.

% Use the following line _only_ if you're still using LaTeX 2.09.
%\documentstyle[icml2006,epsf,mlapa]{article}
% If you rely on Latex2e packages, replace the above line with: 
\documentclass{article}
% Use the following version of the ``usepackage'' statement for
% submitting the draft version of the paper for review.  This will set
% the note in the first column to ``Under review.  Do not distribute.''
\usepackage[accepted]{icml2006} 
% Use this version of the ``usepackage'' statement after the paper has
% been accepted, when creating the final version.  This will set the
% note in the first column to ``Appearing in''
%\usepackage[accepted]{icml2006}
\usepackage{epsf}
%\usepackage{epsfig}
\usepackage{mlapa}
%\usepackage[dvips]{graphicx}

% The \icmltitle is too long. Therefore, a short form for the running title 
% is supplied just before \begin{document} 
\icmltitlerunning{Policy Reuse for Transfer Learning}

\begin{document} 

\twocolumn[
\icmltitle{Policy Reuse for Transfer Learning Across Tasks with Different State and Action Spaces}



 
\icmlauthor{Fernando Fern\'andez}{ffernand@inf.uc3m.es}
\icmladdress{Universidad Carlos III de Madrid, Avda. de la Universidad 30, 28911 Legan\'es, Madrid, Spain}
\icmlauthor{Manuela Veloso}{veloso@cs.cmu.edu}
\icmladdress{Carnegie Mellon University, 5000 Forbes Avenue,  Pittsburgh, PA, USA}


\vskip 0.3in
]

\begin{abstract} 
Policy Reuse is a method for transfer learning in Reinforcement
Learning in which learned policies are saved and reused in similar
tasks. It relies on using the past policies as a probabilistic bias
where the learning agent faces three choices: the exploitation of the
ongoing learned policy, the exploration of random unexplored actions,
and the exploitation of past policies. However, Policy Reuse requires
that the state and action spaces of the reused policies are the same
that the state and action spaces of the policy that the agent is
currently learning. In this paper we demonstrate that to apply Policy
Reuse for transfer learning among tasks with different state/action
spaces only requires that the learning agent maps the states and
actions in the past task with the states and actions of the new
one. Then, the past policies can bias the new learning process
following the Policy Reuse framework. We provide a formal definition
of this mapping and we demonstrate in the Keepaway domain that Policy
Reuse between different tasks can outperform the results of learning
from scratch.
\end{abstract} 

\section{Introduction}
\label{sec:introduction}
Reinforcement Learning (RL)~\cite{kaelbling96,sutton98} is a powerful
technique to learn to solve different kind of tasks. The learning
process is based on a trial and error process guided by reward signals
received from the environment. Classical RL algorithms as
Q-Learning~\cite{watkins89} rely on an intensive exploration of the
action and state spaces. Due to the ``curse of dimensionality'' of
such spaces in complex domains, solving a task typically requires and
extensive interaction of the learning agent with the environment.

Although the cost (time, resources, etc.) of such a learning process
may be very high, sometimes the task can be tackled and successfully
solved~\cite{tesauro92,stone05}. There have been many different
efforts to address the complexity of the learning. To reuse the
knowledge acquired in the current learning process when solving future
problems, so the cost of future learning processes is reduced, is an
appealing idea. In RL, several efforts have been done in this line,
like the transfer of the value
functions~\cite{AAAI05-transfer}, the reuse of
options~\cite{sutton-options} and the learning of hierarchies which
modules can be used in the future~\cite{dietterich00}.

Policy Reuse is a Reinforcement Learning technique guided by past
policies offering the challenge of balancing among three choices: the
exploitation of the ongoing learned policy, the exploration of new
random actions, and the exploitation of past
policies~\cite{fernandez}. Policy Reuse is based on two main
cornerstones. On the one hand, an exploration strategy able to
probabilistically bias the exploration of the domain with a predefined
past policy; on the other hand, a similarity metric that allows the
estimation of the similarity of past policies with respect to a new
one.

However, Policy Reuse requires that the past policies and the policy
that needs to be learned are defined in the same state and action
spaces. That constraint is required to allow the agent to execute in
the current task policies previously learned. In this paper, we
propose an extension of Policy Reuse that allows to reuse past
policies even when they are defined in a different state and action
space. The method is based on a mapping among policies. This mapping
is required in most of the approaches for transfer
learning~\cite{AAMAS05-transfer,torrey05}. However, given we only need
to transfer policies, the amount of knowledge required by the mapping
is much smaller than in methods based on the transfer of the value
function. In our case, the mapping is given by expert knowledge,
although some works demonstrate that such a mapping can also be
learned~\cite{price01}.

We demonstrate empirically that Policy Reuse, together with action and
state space mapping, is able to improve the results of learning from
scratch a set of tasks. The testbed used in this work is the Keepaway
domain~\cite{stone05}, where several transfer learning methods have
been applied recently~\cite{AAMAS05-transfer,torrey05,hsu04}

\section{Policy Reuse}
\label{sec:policy_reuse}

The goal of this section is to summarize Policy Reuse. Firstly, we
describe the concepts of task, domain, and gain. Then, we define how
the reuse of a past policy is used as a bias in a new exploratory
process. We also introduce a similarity concept between policies, which
motivation is deeply described in~\cite{fernandez05}. Lastly, we
describe the PRQ-learning algorithm~\cite{fernandez05b}.

\subsection{Domain, Tasks and MDPs}

A Markov Decision Process~\cite{puterman94} is represented with a tuple
$<\cal S, \cal A, \mathcal{T}, \mathcal{R}>$, where $\cal S$ is the set of
all possible states, $\cal A$ is the set of all possible actions,
$\mathcal{T}$ is an unknown stochastic state transition function, $\mathcal{T}:
\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \Re$, and
$\mathcal{R}$ is an unknown stochastic reward function, $\mathcal{R}:
\mathcal{S}\times \mathcal{A}\to \Re$. We focus on RL domains where
different {\em tasks} can be solved. We introduce a task as a
specific reward function, but the other concepts, $\mathcal{S}$,
$\mathcal{A}$ and $\mathcal{T}$ stay constant for all the tasks. Thus, we
extend the concept of an MDP by introducing two new concepts: domain and
task. We characterize a domain, $\cal D$, as a tuple $<\cal S, \cal A,
\mathcal{T}>$. We define a task, $\Omega$, as a tuple $<\mathcal{D},
\mathcal{R}_\Omega>$, where $\cal D$ is a domain as defined before,
and $\mathcal{R}_\Omega$ is the stochastic and unknown reward
function.

In this work we assume that we are solving a task with absorbing goal
states. Thus, if $s_i$ is a goal state, $\mathcal{T} (s_i,a,s_i)=1$,
$\mathcal{T} (s_i,a,s_j)=0$ for $s_i \neq s_j$, and $\mathcal{R}(s_i,a)=0$,
for all $a\in\cal A$. %% Then equation~\ref{eq:w} must be adapted to
%% introduce the idea of executing the task a finite number of times,
%% each of one is called a trial. 
A trial starts by locating the learning agent in a random
position in the environment. Each trial finishes when a goal state
is reached or when a maximum number of steps, say $H$, is
achieved. Thus, the goal is to maximize the expected average reinforcement
per trial, say $W$, defined as $W=\frac{1}{K}\sum_{k=0}^{K} \sum_{h=0}^{H} \gamma^h r_{k,h}$,
%% as defined in equation~\ref{eq:w2}:
%% \begin{equation}
%% W=\frac{1}{K}\sum_{k=0}^{K} \sum_{h=0}^{H} \gamma^h r_{k,h}
%% \label{eq:w2}
%% \end{equation}
where $\gamma$ ($0\leq \gamma \leq 1$) reduces the importance of
future rewards, and $r_{k,h}$ defines the immediate reward obtained in
the step $h$ of the trial $k$, in a total of $K$ trials. An action
policy, $\Pi:\mathcal{S} \to \mathcal{A}$, defines for each state, the
action to execute. The action policy $\Pi^*$ is optimal if it
maximizes the gain W in such a task, say $W^*_\Omega$.

%% Action
%% policies can be represented using the action-value function,
%% $Q^{\Pi}(s,a)$ that defines for each state $s\in \cal S$, $a\in \cal
%% A$, the expected reward that will be obtained if the agent starts to
%% act from $s$, executing $a$, and after it follows the policy
%% $\Pi$. So, the RL problem is translated to learning the previous
%% function, $Q^{\Pi}(s,a)$. This learning can be performed using
%% different algorithms, as Q-Learning~\cite{watkins89}.


%% \subsection{Policy Reuse}

The goal of Policy Reuse is to describe how learning can be sped up if
different policies, which solve different tasks, are used to bias the
exploration process of the learning of the action policy of another
similar task. Then, the scope of this work is summarized as: (i) we
need to solve the task $\Omega$, i.e. learn $\Pi^*_\Omega$; (ii) we
have previously solved the set of tasks
$\{\Omega_1,\ldots,\Omega_n\}$, so we have the set of policies,
$\{\Pi^*_{1},\ldots,\Pi^*_{n}\}$, to solve them respectively; (iii)
how can we use the previous policies, $\Pi^*_{i}$, to learn the new
one, $\Pi^*_{\Omega}$?

An efficient solution to this problem is the PRQ-Learning
algorithm. This algorithm automatically answers two questions: (i) what
policy, from the set $\{\Pi_1^*, \ldots, \Pi_n^*\}$, is used to bias
the new learning process? (ii) once a policy $\Pi_i$ is selected, how
is it integrated in the learning process? The algorithm is based on an
exploration strategy, $\pi$-reuse, which is able to bias the learning
of a new policy with only one past policy. From this strategy, a
similarity metric between policies is obtained, providing a method to
select the most accurate policy to reuse. Both the $\pi$-reuse
strategy and the similarity metric, defined in~\cite{fernandez05}, are
summarized in the next subsection.

\subsection{A Similarity Metric Between Policies}
\label{sec:exploite_one}
%% Reusing a defined past policy requires integrating the knowledge of the past
%% policy into the current learning process. Our approach is
%% to bias the exploratory process of the new policy with the past
%% one.

%% We denote the old policy with $\Pi^{old}$, and the one we are
%% currently learning with $\Pi$. We assume that we are using a direct RL
%% method to learn the action policy, so we are learning its related $Q$
%% function. Any algorithm can be used to learn the $Q$ function, with
%% the only requirement that it can learn off-policy, i.e. it can learn
%% a policy while executing a different one, as Q-Learning
%% does~\cite{watkins89}.


The goal of the $\pi$-reuse strategy is to balance random exploration,
exploitation of the past policy, and exploitation of the new policy,
which is being learned currently. The $\pi$-reuse strategy follows the
past policy, say $\Pi_{past}$, with a probability of $\psi$. However,
with a probability of $1-\psi$, it exploits the new policy. Obviously,
random exploration is always required, so when exploiting the new
policy, it follows an $\epsilon$-greedy strategy, as defined in
Table~\ref{tab:pi-reuse}. Lastly, the $\upsilon$ parameter allows the
decay of the value of $\psi$ in each trial.



\begin{table}[htb]
\begin{center}
\begin{scriptsize}
\begin{tabular}{l} \\ \hline
$\pi$-reuse ($ \Pi_{old}, K, H, \psi, \upsilon$). \\ \hline
\begin{minipage}{11cm}
\begin{tabbing}
for \= $k=1$   to $K$ \\
\> Set the initial state, $s$, randomly. \\
\> Set $\psi_1 \leftarrow \psi$ \\
\> for \= $h=1$ to $H$ \\
\> \>  With a probability of $\psi_h$, $a=\Pi_{old}(s)$ \\
\> \>  With \= a probability of $1-\psi_h$, $a=\epsilon\textrm{-greedy}(\Pi_{new}(s))$  \\
\> \> Receiv current state $s'$, and reward, $r_{k,h}$ \\
\> \> Update $Q^{\Pi_{new}}(s,a)$, and therefore, $\Pi_{new}$  \\
\> \> Set $\psi_{h+1} \leftarrow \psi_h \upsilon$ \\
\> \> Set $s \leftarrow s'$ \\
$W=\frac{1}{K}\sum_{k=0}^{K} \sum_{h=0}^{H} \gamma^h r_{k,h}$ \\
Return $W$ and $\Pi_{new}$\\
\end{tabbing}
\end{minipage}
 \\ \hline
\end{tabular}
\end{scriptsize}
\end{center}
\caption{$\pi$-reuse Exploration Strategy.}
\label{tab:pi-reuse}
\end{table} 


Interestingly, the $\pi$-reuse strategy also contributes a similarity
metric between policies, based on the gain obtained when reusing each
policy.  %% , as it is summarized in
%% the next subsection.
%% \subsection{A Similarity Metric Between Policies} 
%% The exploration strategy $\pi$-reuse, as defined in
%% Table~\ref{tab:pi-reuse}, returns the learned policy, $\Pi_{new}$, and
%% the average gain obtained in its learning process.
 Let's call $W_i$ the gain obtained while executing the $\pi$-reuse
exploration strategy, reusing the past policy $\Pi_i$. 
We call $\Pi_\Omega^*$ the optimal action policy for solving the task
$\Omega$. $W^*_\Omega$ is the gain obtained when using the optimal
policy, $\Pi_\Omega^*$, to solve $\Omega$. Therefore, $W^*_\Omega$ is
the maximum gain that can be obtained in $\Omega$. Then, we can use
the difference between $W^*_\Omega$ and $W_i$ to measure the
similarity among both policies using the
distance metric shown in equation~\ref{eq:similarity_simplified}.

\begin{equation}
d_\to(\Pi_i, \Pi)= W^{*}_\Omega-
W_{i}
 \label{eq:similarity_simplified}
\end{equation}

In this case the distance metric is not symmetric, so $d_{\to}(\Pi_i,
\Pi_j)$ could be different from $d_{\to}(\Pi_j, \Pi_i)$. This distance
metric is also useful to estimate how useful to reuse the policy
$\Pi_i$ is to learn to solve the new task. Then, the most useful
policy to reuse, from a set $\{\Pi_1, \ldots, \Pi_n\}$, is $\arg_{\Pi_i} \max(W_i)
, i=1, \ldots, n $.
%% defined in equation~\ref{eq:most_similar_task2}:
%% \begin{equation}
%% \arg_{\Pi_i} \min (W^{*}_\Omega-W_{i})
%% , i=1, \ldots, n 
%% \label{eq:most_similar_task}
%% \end{equation}
%% However, $W^*$ is independent of $i$, so
%% the previous equation is equivalent to:
%% \begin{equation}
%% \arg_{\Pi_i} \max(W_i)
%% , i=1, \ldots, n 
%% \label{eq:most_similar_task2}
%% \end{equation}
Notice that $W^*_\Omega$ has disappeared of the formula, given that is
independent of $i$. Thus, $W_i$, or the average reward obtained when
reusing the policy $\Pi_i$ with the $\pi$-reuse exploration strategy,
is used as an estimation of how similar the policy $\Pi_i$ is to the
one we are currently learning. The set of $W_i$ values, for
$i=1,\ldots,n$, is unknown a priori, but it can be estimated on-line
while the new policy is computed. This idea is formalized in the
PRQ-Learning algorithm.


\subsection{PRQ-Learning Algorithm}
\label{sec:prqlearning}


 The PRQ-Learning algorithm (Policy Reuse in
Q-Learning)~\cite{fernandez05b} is shown in
Table~\ref{tab:rqlearning}. The learning algorithm used is
Q-Learning~\cite{watkins89}. It has been chosen because it is an
off-policy algorithm, and therefore, it allows to learn a policy while
following a different one. The goal is to solve a task $\Omega$,
i.e. to learn an action policy $\Pi_\Omega$. We have $n$ past policies
to solve $n$ different tasks respectively. For simplicity of the
notation, we will call these policies $\Pi_1, \ldots, \Pi_n$. Let's
call $W_i$ the expected average reward that is received when reusing
the policy $\Pi_i$ with the $\pi$-reuse exploration strategy. Also,
let's call $W_{\Omega}$ the average reward that is received when
following the policy $\Pi_{\Omega}$ greedily.  The algorithm uses the
$W$ values in a softmax way to choose between reusing a past policy
with the $\pi$-reuse exploration strategy, or following the ongoing
learned policy greedily.


\begin{table}[tbh!]
\begin{scriptsize}
\begin{tabular}{c}  \hline 
{\em Policy Reuse in Q-Learning} \\ \hline \\

\begin{minipage}{8cm}
\begin{itemize}
\item Given:
\begin{enumerate}
\item A set of $n$ policies,  $\{\Pi^*_{1},\ldots,\Pi^*_{n}\}$ to
  solve different tasks
\item A new task $\Omega$ we want to solve
\item A maximum number of trials to execute, $K$
\item A maximum number of steps per trial, $H$
%% \item A temperature parameter, $\tau$ for Boltzman policy selection strategy
%% \item A $\epsilon$ parameter, for $\epsilon$-greedy action selection
%%   strategy in a policy
\end{enumerate}
\item Initialize:
\begin{enumerate}
\item  $Q_\Omega(s,a)=0, \forall s\in \mathcal{S}, a \in \mathcal{A}$ 
\item Initialize $W_\Omega$ to 0
\item Initialize $W_i$ to 0
\item Initialize the number of trials where policy
  $\Pi_\Omega$ has been chosen, $U_\Omega=0$
\item Initialize the number of trials where policy
  $\Pi_i$ has been chosen, $U_i=0, \forall i=1, \ldots,n$
\end{enumerate}
\item For $k=1$ to $K$ do
\begin{itemize}
\item Choose an action policy, $\Pi_{j}$, randomly, assigning
  to each policy the probability of being selected computed by the
  following equation:
 \[
 P(\Pi_j)=\frac{e^{\tau W_j}}{\sum_{p=0}^n e^{\tau W_p} }
 \]

\item Initialize the state $s$ to a random state
\item Set $R=0$
\item for $h=1$ to $H$ do
\begin{itemize}
\item Use $\Pi_{j}$ to compute the next action to execute, $a$,
  following an exploitation strategy.
\item Execute $a$
\item Receive current state, $s'$
\item Receive current reward, $r$
\item Update $Q_\Omega(s,a)$ using Q-Learning update function:
\[ \label{eq:qlearning} Q(s,a) \leftarrow (1-\alpha) Q(s,a)+\alpha [r+
\gamma \max_{a'}Q(s',a')] \]

\item Set $R=R+\gamma^h r$
\item Set $s\leftarrow s'$
\end{itemize}
\item Set $W_j= \frac{W_j U_j + R}{U_j+1}$ 
\item Set $U_j=U_j+1$
\item Set $\tau=\tau+\Delta\tau$
\end{itemize}
\end{itemize}
\end{minipage} \\ \hline
\end{tabular}
\caption{PRQ-Learning}
\label{tab:rqlearning}
\end{scriptsize}
\end{table}

%% \begin{table}[tbh!]
%% \begin{scriptsize}
%% \begin{tabular}{p{5cm}p{7cm}}  \hline 
%% {\em Policy Reuse in Q-Learning} &  \\ \hline \\
%% \hspace{-1cm}
%% \begin{minipage}{6cm}
%% \vspace{-1cm}
%% \begin{itemize}
%% \item Given:
%% \begin{enumerate}
%% \item A set of $n$ policies,  $\{\Pi^*_{1},\ldots,\Pi^*_{n}\}$ to
%%   solve different tasks
%% \item A new task $\Omega$ we want to solve
%% \item A maximum number of trials to execute, $K$
%% \item A maximum number of steps per trial, $H$
%% %% \item A temperature parameter, $\tau$ for Boltzman policy selection strategy
%% %% \item A $\epsilon$ parameter, for $\epsilon$-greedy action selection
%% %%   strategy in a policy
%% \end{enumerate}
%% \item Initialize:
%% \begin{enumerate}
%% \item  $Q_\Omega(s,a)=0, \forall s\in \mathcal{S}, a \in \mathcal{A}$ 
%% \item Initialize $W_\Omega$ to 0
%% \item Initialize $W_i$ to 0
%% \item Initialize the number of trials where policy
%%   $\Pi_\Omega$ has been chosen, $U_\Omega=0$
%% \item Initialize the number of trials where policy
%%   $\Pi_i$ has been chosen, $U_i=0, \forall i=1, \ldots,n$
%% \end{enumerate}

%% \end{itemize}
%% \end{minipage} 
%% &\hspace{-1cm}
%% \begin{minipage}{8cm}
%% \begin{itemize}
%% \item For $k=1$ to $K$ do
%% \begin{itemize}
%% \item Choose an action policy, $\Pi_{j}$, randomly, assigning
%%   to each policy the probability of being selected computed by the
%%   following equation:
%%  $
%%  P(\Pi_j)=\frac{e^{\tau W_j}}{\sum_{p=0}^n e^{\tau W_p} }
%%  $

%% \item Initialize the state $s$ to a random state
%% \item Set $R=0$
%% \item for $h=1$ to $H$ do
%% \begin{itemize}
%% \item Use $\Pi_{j}$ to compute the next action to execute, $a$,
%%   following an exploitation strategy.
%% \item Execute $a$
%% \item Receive current state, $s'$
%% \item Receive current reward, $r$
%% \item Update $Q_\Omega(s,a)$ using the Q-Learning update function.
%% %%\[ \label{eq:qlearning} Q(s,a) \leftarrow (1-\alpha) Q(s,a)+\alpha [r+
%% %%\gamma \max_{a'}Q(s',a')] \]

%% \item Set $R=R+\gamma^h r$
%% \item Set $s\leftarrow s'$
%% \end{itemize}
%% \item Set $W_j= \frac{W_j U_j + R}{U_j+1}$ 
%% \item Set $U_j=U_j+1$
%% \item Set $\tau=\tau+\Delta\tau$
%% \end{itemize}
%% \end{itemize}
%% \end{minipage}
%% \\   \hline

%% \end{tabular}
%% \caption{PRQ-Learning}
%% \label{tab:rqlearning}
%% \end{scriptsize}
%% \end{table}


This algorithm has demonstrated to successfully reuse a predefined set
of policies~\cite{fernandez05b}. In addition, algorithms to build the
Policy Library has been proposed~\cite{fernando}. However, as
introduced at the begining, Policy Reuse requires that the action and
state spaces of the different policies, and therefore, the transition
function, are homogeneous. Next section describes how to apply Policy
Reuse among policies learned in different state/action spaces by
creating a mapping among them.



\section{Policy Reuse Across Different State and Action Spaces}
We assume that we have a past policy, $\Pi_{past}$.
$\Pi_{past}$ is a policy that solves the task
$\Omega_{past}=<\mathcal{D}_{past},\mathcal{R}_{past}>$, where $\mathcal{D}_{past}=<\mathcal{S}_{past}, \mathcal{A}_{past},
\mathcal{T}_{past}>$.

Now, we want to learn a new policy $\Pi_{new}$ to solve a new task
$\Omega_{new}=<\mathcal{D}_{new},\mathcal{R}_{new}>$, where
$\mathcal{D}_{new}=<\mathcal{S}_{new}, \mathcal{A}_{new}>$. We want to
reuse the past policy, $\Pi_{past}$ to learn the new problem
$\Pi_{new}$. Given the policies are functions from states and actions,
we only need to map these two elements, and we do not
need to make any mapping between tasks, rewards and transition
functions. Thus, we need to find a mapping $\rho$, that, given the
policy $\Pi_{past}$, outputs a new policy $\hat{\Pi}_{past}$ that is
executable in the domain $\mathcal{D}_{new}$


If the state and action spaces of $\Omega_{new}$ and $\Omega_{past}$
are homogeneous, then the past policies can be reused to bias the
learning of the new task directly. In that case,
$\hat{\Pi}_{past}(s)=\Pi_{past}(s)$. Then, the mapped policy $\hat{\Pi}_{past}(s)$ is added to the Policy Library and reused.

If the state and or action spaces are heterogeneous, we can not use
the past policy directly in the new task. In that case, we need to
find a mapping from the state/action spaces of the past task to the
ones of the new one. That mapping is defined in
equation~\ref{eq:mapping}. In that equation,
$\rho_{\mathcal{A}}:\mathcal{A}_{past}\to\mathcal{A}_{new}$ is a
function that maps the actions in the space $\mathcal{A}_{past}$ to
actions in the space $\mathcal{A}_{new}$; and
$\rho_{\mathcal{S}}:\mathcal{S}_{past}\to\mathcal{S}_{new}$ maps
states in the space $\mathcal{S}_{past}$ to the space
$\mathcal{S}_{new}$.


\begin{equation}
\hat{\Pi}_{past}(s)=\rho_{\mathcal{A}}(\Pi_{past}(\rho_{\mathcal{S}}(s)))
\label{eq:mapping}
\end{equation}




The way to make this mapping, i.e. to define $\rho_{\mathcal{S}}$ and
$\rho_{\mathcal{A}}$, depends on the source and the target tasks. For
instance, this mapping can be done by an expert, which decides the
correspondence among states and actions~\cite{AAMAS05-transfer,torrey05}. That
mapping can also be learned by observing to a
mentor~\cite{price01}. Last, the mapping may depend on the
generalization method used to approximate the value
function~\cite{AAMAS05-transfer}. Next section describes the
application of Policy Reuse on the Keepaway task, and how we make the
mapping between different state spaces based on the function
approximator used.







\section{The Keepaway Domain}
The Keepaway domain is a subdomain of robot soccer~\cite{stone05}. It
consists on two teams, the keepers and the takers. The behavior of the
takers is fixed and defined a priori and consists on several low level
skills as ``Go to Ball'' or ``Block a Pass'', that are combined
following some predefined rules.. There are also some low level
skills defined for the keepers, as ``Go to Ball'' or ``Hold the
Ball''. A task consists on to learn a high level control of those
skills for each of the keepers. The goal is to maximize the time
that the keepers maintain the possesion of the
ball in the lifelong term. The end condition for each episode is that
the keepers looses the ball or that the ball goes out of a fixed
sub-area of the field. Both conditions are also predefined.

There are several learning possibilities in this framework. Changing
the number of keepers or takers, the size of the play area, the
sensing capabilities of the agents, or the communication skills among
them generate different learning problems. In the next section we
describe the keepaway task as a Reinforcement Learning task,
describing some details as the state and action spaces or the reward
function. We follow the framework defined
in~\cite{AAMAS05-transfer}. Thus, each keeper learns its own behavior,
so we assume that each of them is implemented as a reinforcement
learning agent, as explained next. 

\subsection{Keepaway as a Reinforcement Learning Task}
The state features and action possibilities use information derived
from distances and angles between the keepers, the takers, and keepers
and the center of the play area. Depending on the number of keepers
and takers, the feautures used are different. Table~\ref{fig}
describes the compleate state space when 3 keepers play against 2
keepers (3 vs. 2), and when 4 keepers play against 3
keepers (4 vs. 3). In this case, keepers and takers are ordered taking into
account their respective distance to the ball, so the assignment of
numbers to the keepers and the takers may change in each moment. 

\begin{table}
\begin{scriptsize}
\begin{tabular}{p{2.2cm}p{2.2cm}p{2.2cm}}
3vs2-keepaway & 4vs3-keepaway & 5vs4-keepaway\\ \hline
dist($k_1,C$) & dist($k_1,C$) & dist($k_1,C$) \\
dist($k_2,C$) & dist($k_2,C$) & dist($k_2,C$) \\
dist($k_3,C$) & dist($k_3,C$) & dist($k_3,C$) \\
 &  dist($k_4,C$)&  dist($k_4,C$) \\
 &  &  dist($k_5,C$) \\ \hline
dist($t_1,C$) & dist($t_1,C$) & dist($t_1,C$) \\
dist($t_2,C$) & dist($t_2,C$) & dist($t_2,C$) \\
 &  dist($t_3,C$)&  dist($t_3,C$) \\
 &  &  dist($t_4,C$) \\ \hline
dist($k_1,k_2$) & dist($k_1,k_2$) & dist($k_1,k_2$) \\
dist($k_1,k_3$) & dist($k_1,k_3$) & dist($k_1,k_3$) \\
 & dist($k_1,k_4$) & dist($k_1,k_4$) \\
 &  & dist($k_1,k_5$) \\ \hline
dist($k_1,t_1$) & dist($k_1,t_1$) &dist($k_1,t_1$)\\
dist($k_1,t_2$) & dist($k_1,t_2$) &dist($k_1,t_2$)\\
 & dist($k_1,t_3$) &dist($k_1,t_3$)\\
 & &dist($k_1,t_4$)\\ \hline

%\end{tabular}

%\begin{tabular}{ccc}
%3 vs. 2 & 4 vs. 3 & 5 vs. 4 \\ \hline
$\begin{array}{c} \min(dist(k_2,t_1),\\ dist(k_2,t_2))\end{array}$ &
$\begin{array}{c} \min(dist(k_2,t_1),\\ dist(k_2,t_2),\\ dist(k_2,t_3))\end{array}$ & 
$\begin{array}{c} \min(dist(k_2,t_1),\\ dist(k_2,t_2),\\ dist(k_2,t_3),\\ dist(k_2,t_4))\end{array}$  \\ 
$\begin{array}{c} \min(dist(k_3,t_1),\\ dist(k_3,t_2))\end{array}$ &
$\begin{array}{c} \min(dist(k_3,t_1),\\ dist(k_3,t_2),\\ dist(k_3,t_3))\end{array}$ & 
$\begin{array}{c} \min(dist(k_3,t_1),\\ dist(k_3,t_2),\\ dist(k_3,t_3),\\ dist(k_3,t_4))\end{array}$  \\

&
$\begin{array}{c} \min(dist(k_4,t_1),\\ dist(k_4,t_2),\\ dist(k_4,t_3))\end{array}$ & 
$\begin{array}{c} \min(dist(k_4,t_1),\\ dist(k_4,t_2),\\ dist(k_4,t_3),\\ dist(k_4,t_3))\end{array}$  \\ 

& &
$\begin{array}{c} \min(dist(k_5,t_1),\\ dist(k_5,t_2),\\ dist(k_5,t_3),\\ dist(k_5,t_3))\end{array}$  \\ \hline

$\begin{array}{c} \min(ang(k_2,k_1,t_1),\\ ang(k_2,k_1,t_2))\end{array}$ &
$\begin{array}{c} \min(ang(k_2,k_1,t_1),\\ ang(k_2,k_1,t_2),\\ ang(k_2,k_1,t_3))\end{array}$ & 
$\begin{array}{c} \min(ang(k_2,k_1,t_1),\\ ang(k_2,k_1,t_2),\\ ang(k_2,k_1,t_3),\\ ang(k_2,k_1,t_4))\end{array}$  \\

$\begin{array}{c} \min(ang(k_3,k_1,t_1),\\ ang(k_3,k_1,t_2))\end{array}$ &
$\begin{array}{c} \min(ang(k_3,k_1,t_1),\\ ang(k_3,k_1,t_2),\\ ang(k_3,k_1,t_3))\end{array}$ & 
$\begin{array}{c} \min(ang(k_3,k_1,t_1),\\ ang(k_3,k_1,t_2),\\ ang(k_3,k_1,t_3),\\ ang(k_3,k_1,t_4))\end{array}$  \\
&
$\begin{array}{c} \min(ang(k_4,k_1,t_1),\\ ang(k_4,k_1,t_2),\\ ang(k_4,k_1,t_3))\end{array}$ & 
$\begin{array}{c} \min(ang(k_4,k_1,t_1),\\ ang(k_4,k_1,t_2),\\ ang(k_4,k_1,t_3),\\ ang(k_4,k_1,t_4))\end{array}$  \\
&&
$\begin{array}{c} \min(ang(k_5,k_1,t_1),\\ ang(k_5,k_1,t_2),\\ ang(k_5,k_1,t_3),\\ ang(k_5,k_1,t_4))\end{array}$  \\ \hline
13 features & 19 features & 25 features\\

\end{tabular}
\end{scriptsize}
\label{tab:state-space}
\caption{State spaces of the different keepaway tasks.}
\end{table}


%% \begin{table}
%% \begin{scriptsize}
%% \begin{tabular}{p{2.5cm}p{2.5cm}p{2.5cm}}
%% 3vs2-keepaway & 4vs3-keepaway & 5vs4-keepaway\\ \hline
%% dist($k_1,C$) & dist($k_1,C$) & dist($k_1,C$) \\
%% dist($k_2,C$) & dist($k_2,C$) & dist($k_2,C$) \\
%% dist($k_3,C$) & dist($k_3,C$) & dist($k_3,C$) \\
%%  &  dist($k_4,C$)&  dist($k_4,C$) \\
%%  &  &  dist($k_5,C$) \\ \hline
%% dist($t_1,C$) & dist($t_1,C$) & dist($t_1,C$) \\
%% dist($t_2,C$) & dist($t_2,C$) & dist($t_2,C$) \\
%%  &  dist($t_3,C$)&  dist($t_3,C$) \\
%%  &  &  dist($t_4,C$) \\ \hline
%% dist($k_1,k_2$) & dist($k_1,k_2$) & dist($k_1,k_2$) \\
%% dist($k_1,k_3$) & dist($k_1,k_3$) & dist($k_1,k_3$) \\
%%  & dist($k_1,k_4$) & dist($k_1,k_4$) \\
%%  &  & dist($k_1,k_5$) \\ \hline
%% dist($k_1,t_1$) & dist($k_1,t_1$) &dist($k_1,t_1$)\\
%% dist($k_1,t_2$) & dist($k_1,t_2$) &dist($k_1,t_2$)\\
%%  & dist($k_1,t_3$) &dist($k_1,t_3$)\\
%%  & &dist($k_1,t_4$)\\ \hline

%% %\end{tabular}

%% %\begin{tabular}{ccc}
%% %3 vs. 2 & 4 vs. 3 & 5 vs. 4 \\ \hline
%% Min($\begin{array}{c}dist(k_2,t_1),\\ dist(k_2,t_2))\end{array}$ &
%% Min($\begin{array}{c}dist(k_2,t_1),\\ dist(k_2,t_2),\\ dist(k_2,t_3))\end{array}$ & 
%% Min($\begin{array}{c}dist(k_2,t_1),\\ dist(k_2,t_2),\\ dist(k_2,t_3),\\ dist(k_2,t_4))\end{array}$  \\ 
%% Min($\begin{array}{c}dist(k_3,t_1),\\ dist(k_3,t_2))\end{array}$ &
%% Min($\begin{array}{c}dist(k_3,t_1),\\ dist(k_3,t_2),\\ dist(k_3,t_3))\end{array}$ & 
%% Min($\begin{array}{c}dist(k_3,t_1),\\ dist(k_3,t_2),\\ dist(k_3,t_3),\\ dist(k_3,t_4))\end{array}$  \\

%% &
%% Min($\begin{array}{c}dist(k_4,t_1),\\ dist(k_4,t_2),\\ dist(k_4,t_3))\end{array}$ & 
%% Min($\begin{array}{c}dist(k_4,t_1),\\ dist(k_4,t_2),\\ dist(k_4,t_3),\\ dist(k_4,t_3))\end{array}$  \\ 

%% & &
%% Min($\begin{array}{c}dist(k_5,t_1),\\ dist(k_5,t_2),\\ dist(k_5,t_3),\\ dist(k_5,t_3))\end{array}$  \\ \hline

%% Min($\begin{array}{c}ang(k_2,k_1,t_1),\\ ang(k_2,k_1,t_2))\end{array}$ &
%% Min($\begin{array}{c}ang(k_2,k_1,t_1),\\ ang(k_2,k_1,t_2),\\ ang(k_2,k_1,t_3))\end{array}$ & 
%% Min($\begin{array}{c}ang(k_2,k_1,t_1),\\ ang(k_2,k_1,t_2),\\ ang(k_2,k_1,t_3),\\ ang(k_2,k_1,t_4))\end{array}$  \\

%% Min($\begin{array}{c}ang(k_3,k_1,t_1),\\ ang(k_3,k_1,t_2))\end{array}$ &
%% Min($\begin{array}{c}ang(k_3,k_1,t_1),\\ ang(k_3,k_1,t_2),\\ ang(k_3,k_1,t_3))\end{array}$ & 
%% Min($\begin{array}{c}ang(k_3,k_1,t_1),\\ ang(k_3,k_1,t_2),\\ ang(k_3,k_1,t_3),\\ ang(k_3,k_1,t_4))\end{array}$  \\
%% &
%% Min($\begin{array}{c}ang(k_4,k_1,t_1),\\ ang(k_4,k_1,t_2),\\ ang(k_4,k_1,t_3))\end{array}$ & 
%% Min($\begin{array}{c}ang(k_4,k_1,t_1),\\ ang(k_4,k_1,t_2),\\ ang(k_4,k_1,t_3),\\ ang(k_4,k_1,t_4))\end{array}$  \\
%% &&
%% Min($\begin{array}{c}ang(k_5,k_1,t_1),\\ ang(k_5,k_1,t_2),\\ ang(k_5,k_1,t_3),\\ ang(k_5,k_1,t_4))\end{array}$  \\ \hline
%% 13 features & 19 features & 25 features\\

%% \end{tabular}
%% \end{scriptsize}
%% \label{tab:state-space}
%% \caption{State spaces of the different keepaway tasks.}
%% \end{table}




Thus, the number of features for the different versions of the
Keepaway are 13, 19 and 25 respectivelly. The action space is limited
to the execution of two different behaviors, $HoldBall()$ and
$PassBall(k_i)$. PassBall receives a parameter, which is the player
who will receive the pass. Thus, the complete set of actions for the
different number of keepers and takers is defined in
Table~\ref{tab:actions}.

\begin{table}
\begin{center}
\begin{scriptsize}
\begin{tabular}{ccc}
3 vs. 2 & 4 vs. 3 & 5 vs. 4 \\ \hline
$Hold$ & $Hold$ & $Hold$ \\
$Pass(k_2)$ & $Pass(k_2)$ & $Pass(k_2)$ \\
$Pass(k_3)$ & $Pass(k_3)$ & $Pass(k_3)$ \\
& $Pass(k_4)$ & $Pass(k_4)$ \\
& & $Pass(k_5)$ \\ \hline
\end{tabular}
\end{scriptsize}
\end{center}
\label{tab:actions}
\caption{Actions in the different keepaway tasks.}
\end{table}

As the table shows, the number of actions also grows with the number
of keepers. In this version of the Keepaway task, the only decission
is taken when the player holds the ball. If that cases, it needs to
decide among the previously defined actions. If the player does not
hold the ball, it executes a predefined behavior as well as the takers
do.

The reward is the time that the team holds the ball since the agent
executed the last action. Thus, the reward does not depend only of the
executed action, but also of the actions executed by the other agents,
what is called {\em inherently cooperative rewards}. As in other
different tasks as Cooperative... (CMOMMT)~\cite{}, the cooperative
behaviors is expected to emerge from the individual behavior learned
by each agent independently of the others.

The action space in the Keepaway task is reduced to a few
actions. However, state space is composed of several features that can
be considered continuous. Thus, a method for state space
generalization is required in order to improve learning
capabilities. Some methods for function approximation, as CMAC or
neural networks, have been applied for the
keepaway~\cite{AAAI05-transfer}. The next section describes the
application of the VQQL model for discretizing the keepaway state space.

\subsection{Function Approximation in the Keepaway Task}

The {\sc VQQL} algorithm (Vector Quantization for
Q-Learning)~\cite{fernandez00a,fernandez01b}, is based on the
unsupervised discretization of the state space. It applies vector
quantization methods, and more specifically, the Generalized Lloyd
Algorithm ({\sc GLA})~\cite{lloyd82}, also called k-means. This method
generates a set of prototypes, that together with the nearest neighbor
rule, defines Voronoi regions~\cite{gersho}. Each of these regions
clusters a set of states of the original state space
representation. Figure~\ref{fig:discretization_vqql} shows how to
represent the action policy following this approach.


\begin{figure}[h]
\vskip 0.2in
\begin{center}
\setlength{\epsfxsize}{2.5in}
\centerline{\epsfbox{discretizacion_vqql.eps}}
% \vskip 0.1in
\caption{Function approximation with {\sc VQQL}.}
\label{fig:discretization_vqql}
\end{center}
\vskip -0.2in
\end{figure} 


%% \begin{figure}[htb]
%% %%\centerline{\psfig{figure=rl/discretizacion_vqql.eps,width=8cm}}
%% %\centerline{\psfig{figure=discretizacion_vqql.ps,width=8cm}}
%% \includegraphics[width=5cm]{discretizacion_vqql.eps}
%% \caption{Function approximation with {\sc VQQL}.}
%% \label{fig:discretization_vqql}
%% \end{figure}

The use of vector quantization and the Generalized Lloyd Algorithm to
solve the generalization problem in RL algorithms requires two
consecutive phases:

\begin{description}
\item [Learning the quantizer.] Designing the vector quantizer,
  $VQ(s)$, composed of $B$ prototypes from the input data obtained from
  the environment during exploration.
\item [Learning the Q function.] Once the vector quantizer is designed
(i.e., the environment is clustered into $B$ different states), the Q
function must be learned, generating the Q table composed of $B$ rows
and a column for each action.
\end{description}

%% The advantage of using vector quantization techniques for discretizing the state space, instead of uniform discretizations, is their capability to eficiently cluster the domain, locating more clusters where more data is available, and hence, where it is suppose to be more information.


%% The use of vector quantization in a first step of the RL
%% phase allows to perform the policy learning from two different points of
%% view. The first one is an on-line version, where the learning phase is
%% interactive, and exploitation strategies can be followed, as defined in Figure~\ref{fig:on-line-vqql}.

\begin{figure}[htb]
\begin{center}
\begin{scriptsize}
\begin{tabular}{l} \hline 
{\em On-line {\sc VQQL}} \\ \hline \\
\begin{minipage}{8cm}

\begin{itemize}
\item Obtain a set $P$ of examples of states.
\item Design a vector quantizer (discretization function) $VQ(s)$ using $P$ with
the Generalized Lloyd Algorithm
\item Learn the Q function using the following steps:
\begin{itemize}
\item Choose an action following an exploration/exploitation
strategy. Receive the reward, obtaining  an experience 
tuple $<s,a,s',r>$  
\item Quantify the experience tuple, obtaining $<\hat{s},a,\hat{s'},r>$, where $\hat s = VQ(s)$ and $\hat{s'}=VQ(s')$
\item Update the Q table following the Q-Learning update equation
\end{itemize} 
\end{itemize}

\end{minipage}\\ 
\ \\ \hline
\end{tabular}
\end{scriptsize}
\end{center}
\caption{On-line {\sc VQQL} algorithm.}
\label{fig:on-line-vqql}
\end{figure}

%% However, given that the algorithm begins with an exploratory phase to obtain a
%% learning set of states to design the discretization, this exploration can also be
%% used to obtain a set of experience tuples that are required for learning
%% the Q table, as defined in Figure~\ref{fig:off-line-vqql}.

%% \begin{figure}[htb]
%% \begin{center}
%% \begin{small}
%% \begin{tabular}{l} \hline 
%% {\em Off-line {\sc VQQL}} \\ \hline \\
%% \begin{minipage}{11cm}

%% \begin{itemize}
%% \item Obtain a set $P$ of examples of states, and a set $T$ of experience
%%   tuples, of the kind $<s,a,s',r>$
%% \item Design a vector quantizer $S(s)$ using $P$ with the Generalized
%% Lloyd Algorithm
%% \item Quantify all the states of the experience tuples stored in $T$, so from
%%   each tuple  $<s,a,s',r>$, a tuple $<\hat s,a,\hat{s'},r>$ is stored in the new
%%   set $\hat T$, where $\hat s = S(s)$ and $\hat{s'}=S(s')$
%% \item Update the Q table following equation~\ref{eq:qlearning} for each
%%   quantified tuple in $\hat T$.
%% \end{itemize} 
%% \end{minipage}\\ 
%% \ \\ \hline
%% \end{tabular}
%% \end{small}
%% \end{center}
%% \caption{Off-line {\sc VQQL} algorithm.}
%% \label{fig:off-line-vqql}
%% \end{figure}

The Vector Quantization
technique takes advantage of the statistical characteristics of the
domain to reduce its size, considering only relevant areas from the
whole domain. The algorithm has been applied to learn the ball
interception skill of a goalie~\cite{fernandez00a}, and in Cooperative
Multi-robot Observation of Multiple Moving Targets ({\sc
CMOMMT})~\cite{par:02a}, in order to obtain collaborative behaviors in
a multi-robot observation task~\cite{fernandez01b,fernandez01c}. Those
experiments showed that the nearest prototype approach used to
discretize the state space produces better results than uniform
discretizations. 

In the following sections, the VQQL model has been applied to
solve the Keepaway. We will also show that this method allows to
transfer policies very easily.


\section{Learning in the Keepaway}

In this section, we describe the experiments performed on the Keepaway
domain. We differentiate three different tasks. Firstly the
3vs2-keepaway, where 3 keepers play against two players; secondly, the
4vs3-keepaway; and last, the 5vs4-keepaway, where 5 keepers play
against 4 takers. The three tasks are learned in the order that have
been defined. We define that there are two possibilities. In the first
one, the three tasks are learned from scratch, so the knowledge
acquired in one of them is never used to improve the learning process
of the others. In the second case, we first learn the
3vs2-keepaway. Then, the agents that participated in 3vs2-keepaway,
reuses the acquired policy to solve the 4vs3-keepaway. The agents that
did not participate in the 3vs2-keepaway learns from scratch. Last,
when learning the 5vs4-keepaway, each agent reuses the previously
learned polices (2 for keepers 1, 2, and 3; 1 for keeper 4, and none
for keeper 5), as defined in Figure~\ref{fig:transfer-keepaway}

\begin{table}
\begin{scriptsize}
\begin{tabular}{p{1.2cm}|p{1.5cm}|p{2cm}|p{2cm}|}
& 3vs2-keepaway & 4vs3-keepaway & 5vs4-keepaway\\ \hline
Keeper 1 & Learn $\Pi_{3vs2}^{k_1}$ from scratch & Learn $\Pi_{4vs3}^{k_1}$ by reusing $L^{k_1}=\{\Pi_{3vs2}^{k_1}\}$ & Learn $\Pi_{5vs4}^{k_1}$ by reusing $L^{k_1}=\{\Pi_{3vs2}^{k_1}, \Pi_{4vs3}^{k_1}\}$\\ \hline
Keeper 2 & Learn $\Pi_{3vs2}^{k_2}$ from scratch & Learn $\Pi_{4vs3}^{k_2}$ by reusing $L^{k_2}=\{\Pi_{3vs2}^{k_2}\}$ & Learn $\Pi_{5vs4}^{k_2}$ by reusing $L^{k_2}=\{\Pi_{3vs2}^{k_2}, \Pi_{4vs3}^{k_2}\}$\\ \hline
Keeper 3 & Learn $\Pi_{3vs2}^{k_3}$ from scratch & Learn $\Pi_{4vs3}^{k_3}$ by reusing $L^{k_3}=\{\Pi_{3vs2}^{k_3}\}$ & Learn $\Pi_{5vs4}^{k_3}$ by reusing $L^{k_3}=\{\Pi_{3vs2}^{k_3}, \Pi_{4vs3}^{k_3}\}$\\ \hline
Keeper 4 & Not Playing & Learn $\Pi_{4vs3}^{k_4}$ from scratch & Learn $\Pi_{5vs4}^{k_4}$ by reusing $L^{k_4}=\{\Pi_{4vs3}^{k_4}\}$ \\ \hline
Keeper 5 & Not Playing & Not Playing & Learn $\Pi_{5vs4}^{k_5}$ from scratch \\ \hline
\end{tabular}
\end{scriptsize}
\label{tab:tasks}
\caption{Description of the tasks solved. The first one is 3vs2-keepaway, the second one is 4vs3-keepaway reusing the policies acquired in the 3vs2-keepaway. The last one is 4vs-4 keepaway reusing the policies acquired in both 3vs2-keepaway and 4vs3-keepaway.}
\end{table}

The next section formalizes Policy Reuse in this scope. It also
describes how each agent performs the mapping between the
3vs2-keepaway and the 4vs3-keepaway. Mappings from 3vs2-keepaway to
5vs-4 keepaway or from 4vs3-keepaway to 5vs-4 keepaway are equivalent,
and easily instantiated from this case.

\subsection{Policy Reuse in the Keepaway}


The 3vs2-keepaway is a task, $\Omega^{3vs2}=<\mathcal{D}^{3vs2},
\mathcal{R}>$, defined in the domain $\mathcal{D}^{3vs2}$, with a
reward function $\mathcal{R}$. The domain is defined as a tuple,
$\mathcal{D}^{3vs2}=<\hat{\mathcal{S}}^{3vs2}, \mathcal{A}^{3vs2},
\mathcal{T}^{3vs2}>$. $\hat{\mathcal{S}}^{3vs2}$ is a discretized
version of the original state space $\mathcal{S}^{3vs2}$,. The
discretization is performed by a function
$VQ^{3vs2}:\mathcal{S}^{3vs2}\to
\hat{\mathcal{S}}^{3vs2}$. $\mathcal{S}^{3vs2}$ and
$\mathcal{A}^{3vs2}$ were defined in tables~\ref{} and~\ref{}
respectively. Both, the transition function $\mathcal{T}^{3vs2}$ and
the reward function are unknown for the agent. The goal is to learn an
action policy $\Pi_{\Omega^{3vs2}}:\hat{\mathcal{S}}^{3vs2}\to
\mathcal{A}^{3vs2}$ that outputs actions, given any state of the
discretized state space.

The 4vs3-keepaway task is formalized as following:


%% \begin{itemize}
%% \item $\mathcal{D}^{3vs2}=<\hat{\mathcal{S}}^{3vs2}, \mathcal{A}^{3vs2},
%%   \mathcal{T}^{3vs2}>$\\
%% where $\hat{\mathcal{S}}^{3vs2}=VQ^{3vs2}(\mathcal{S}^{3vs2})$
%% \item $\Omega^{3vs2}=<\mathcal{D}^{3vs2},
%%   \mathcal{R}>$
%% \item $\Pi_{\Omega^{3vs2}}:\hat{\mathcal{S}}^{3vs2}\to \mathcal{A}^{3vs2}$
%% \end{itemize}


\begin{itemize}
\item $\mathcal{D}^{4vs3}=<\hat{\mathcal{S}}^{4vs3}, \mathcal{A}^{4vs3},
  \mathcal{T}^{4vs3}>$
where $\hat{\mathcal{S}}^{4vs3}=VQ^{4vs3}(\mathcal{S}^{4vs3})$
\item $\Omega^{4vs3}=<\mathcal{D}^{4vs3}, \mathcal{R}>$
\item $\Pi_{\Omega^{4vs3}}:\hat{\mathcal{S}}^{4vs3}\to \mathcal{A}^{4vs3}$
\end{itemize}


Then, the mapping from a policy in the 3vs2-keepaway to the 4vs3-keepaway is performed as defined in equation~\ref{eq:policy-mapping}:
\begin{equation}
\Pi_{\Omega^{4vs3}}(s)=\Pi_{\Omega^{3vs2}}(VQ^{3vs2}(P^{4vs3}_{3vs2}(s)))
\label{eq:policy-mapping}
\end{equation}
where $P^{4vs3}_{3vs2}(s)$ is a function
$P^{4vs3}_{3vs2}:\mathcal{S}^{4vs3}\to\mathcal{S}^{3vs2}$ that, given
a state in the 4vs3-keepaway state space, $\mathcal{S}^{4vs3}$,
projects it on the 3vs2-keepaway state space, $\mathcal{S}^{3vs2}$.

In the keepaway task, this proyection is performed very easily, and is
derived from the semantic of the features, as used in other different
works~\cite{AAMAS05-transfer,}. ???????????????????????????????????????????????

\subsection{Results}

In the experiments, we have used the Keepaway layer Framework
0.6~\footnote{The software is available in the Keepaway Player
  Framework web page:
  http://www.cs.utexas.edu/users/AustinVilla/sim/keepaway/}. As in
other transfer learning paper that uses this simulator as
testbed~\cite{AAMAS05-transfer}, the field size is $25\times 25$,
vision capabilities are set to full, and the synchronous mode is set
on to speed up the simulator. However, different simulator versions
have different low level implementations of the skills, so direct
comparisons with previously published results can not be performed,
given that the simulation version used on~\cite{AAMAS05-transfer} is
not longer available. However, we will try to provide qualitative
comparisons as far as it is possible.~\footnote{Thanks to Peter Stone,
  Matthew Taylor, Yaxin Liu and Gregory Kuhlmann for their valuable
  comments about their works on the Keepaway task.} In order to have some
baseline results, in all the cases we introduce the performance of two
policies, the random action selection strategy, and a policy where the
agents always passes to the second keeper (which outperforms the
policy where the agents always hold the ball, used for comparisons in
other papers~\cite{stone05}).


In the next subsections we provide the results obtained when solving
the Keepaway tasks, following the steps described in
Table~\ref{tab:tasks}. Thus, we first learn the 3vs2-keepaway. Then,
we solve the 4vs3-keepaway by transfering the policies learned in the
3vs2-keepaway. Last, we solve the 5vs4-keepaway by reusing the
policies learned in the 3vs2 and 4vs3-keepaway. In all the cases, the
size of the discretized state space is 512 states. The state space
discretization is learned with the GLA algorithm over data generated
after 2000 episodes, where all the agents followed a random action
selection strategy. All the previous values have been chosen as a
result of an informal experimentation. Thus, they may not be optimal
for the task that we are solving, but provide us with results that are
accurate enought to make or study on Policy Reuse, without evaluating
in depth the influence of the discretizations obtained in the
performance of the keepaway task.

When learning from scratch, an $\epsilon$-greedy strategy is followed,
increasing the value of $epsilon$ from 0 (random behaviour) to 1
(greedy behaviour) by 0.0001 in each episode. As before, this strategy
demonstrated to provide good results in this domain, but no extensive
parameter tunning was performed.

\subsubsection{3vs2-keepaway}
Firstly, we have learned the 3vs2-keepaway. The results are summarized in Table~\re{fig:3vs2-results}. The $x$ axis of the figure describes the training time, while the the $y$ axis shows the episode duration, which is the value to maximize. In this task, the random behavior obtains a performance of 7.25 seconds, while the policy ``Pass K2'' obtains an average value of 8.17. When learning, the average values raises from 7.25 up to around 11 seconds.  


\begin{figure}[h]
\vskip 0.2in
\begin{center}
\setlength{\epsfxsize}{3.25in}
\centerline{\epsfbox{figures/graph-3vs2.eps}}
% \vskip 0.1in
\caption{Results of learning in the 3vs2-keepaway}
\label{fig:3vs2-results}
\end{center}
\vskip -0.2in
\end{figure} 



\subsubsection{4vs3-keepaway}
After learning the 3vs2-keepaway, the agents received the task
4vs3-keepaway. In this case, we followed two different approaches for
learning: learning from scratch, and Policy Reuse, following the
scheme introduced in Table~\ref{}. The results are summarized in
Figure~\ref{fig:4vs3-results}. In this task, the random behavior
obtains a performance of 5.56 seconds, while the policy ``Pass K2''
obtains an average value of 5.83. These results are lower than the
ones obtained in the 3vs2-keepaway, demonstrating that this task is
much harder.

\begin{figure}[h]
\vskip 0.2in
\begin{center}
\setlength{\epsfxsize}{3.25in}
\centerline{\epsfbox{figures/graph-4vs3.eps}}
% \vskip 0.1in
\caption{Results of learning in the 4vs3-keepaway}
\label{fig:4vs3-results}
\end{center}
\vskip -0.2in
\end{figure} 

When learning, we can differentiate in two phases. The first one
ranges from training time 0 until training time 20. In that phase,
when learning from scratch, the performance grows from the same result
than random behaviour (around 5.5) up to more than 6.5. However, when
the agents reuses the policy learned in the 3vs2-keepaway through
Policy Reuse, the initial value is around 6.4, growing up to more than
6.5 in around 11 ours. This demonstrates that reusing the past policy
improves the behaviour of the learning agent since the early steps of
the learning. The second phase, after 20 hours of learning, does not
show significant differences in the learning curves.

This result is qualitatively different to the one reported on value
function based behavior transfer~\cite{AAMAS05-transfer}. In that
work, both learning from scratch and behaviour transfer obtain similar
results in the initial steps of learning. The contribution of behavior
transfer is that the accurate behaviors are achieved faster than when
learning from scratch. However, in our case, the performance of the
task is much better from the early episodes of the learning. Another
difference between our work and that one is that, given that they
transfer the Q function, for instance, from 3vs2-keepaway to 4vs-3
keepaway, they need to initialize some values of the Q-function by
hand. That means that, for instance, the Q values of the action ``Pass
k3'' in the 3vs2-keepaway is transferred both to the action ``Pass
k3'' and to the action ``Pass k4'' of 4vs3-keepaway.  This
initialization of the Q values are required to make the Q table
transferred more homogeneous than if some values are set to
0. Furthermore, the results obtained may vary depending on how that
initialization is performed. Policy Reuse utilizes past policies only
as a bias in the exploration, so we do not suffer that problem, and
the amount of knowledge required for the transfer is lower.

Quantitatively, the results provided in~\cite{AAMAS05-transfer} are
different, since the authors report that they obtain values of 9 for
the performance, both when learning from scratch and when transfering
behaviors. However, given that the differences appear also when
learning from scratch, they must be due to other variables besides the
transfer lerarning, as the simulator version, the learning algorithms
(Sarsa instead of Q-Learning) or the generalization methods used (CMAC
instead of VQQL).




\subsubsection{5vs4-keepaway}
After learning the 3vs2 and 4vs3-keepaway, the situation of the agents, as defined in Table~\ref{} is different. The first three agents, that participated also in the 3vs2 and the 4vs3-keepaway, can reuse two action policies, learned in each task respectively. The forth agent can reuse only the policy of the 4vs3-keepaway, given that it did not participated in the 3vs2-keepaway. The fifth keeper never played before, so it needs to learn from scratch. The results are shown in Figure~\ref{fig:4vs3-results}.

\begin{figure}[h]
\vskip 0.2in
\begin{center}
\setlength{\epsfxsize}{3.25in}
\centerline{\epsfbox{figures/graph-5vs4.eps}}
% \vskip 0.1in
\caption{Results of learning in the 5vs4-keepaway}
\label{fig:4vs3-results}
\end{center}
\vskip -0.2in
\end{figure} 

%% \section{Domain Mappings}

%% \begin{description}
%% \item[Mapping (3 vs. 2) $\to$ (4 vs. 3)]:
%% \begin{itemize}
%% \item Map state space in (4 vs 3) to (3 vs. 2) by finding closer prototypes. Use weighted euclidean distance with values (1 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0).
%% \item Q value for ``Pass 2'' goes to ``Pass 3'' (when ``Pass 2'' was the preferred action, now it will choose randomly betweem both of them)
%% \item Alternative mapping: Q value for ``Pass 1'' goes to ``Pass 3''
%% \end{itemize}
%% \item  [Mapping (3 vs. 2) $\to$ (5 vs. 4)]:
%% \begin{itemize}
%% \item Map state space in (5 vs 4) to (3 vs. 2) by finding closer prototypes. Use weighted euclidean distance with values (1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0).
%% \item Q value for ``Pass 2'' goes to ``Pass 3'' and ``Pass 4'' (when ``Pass 2'' was the preferred action, now it will choose randomly betweem all of them)
%% \item Alternative mapping: Q value for ``Pass 1'' goes to ``Pass 3'' and ``Pass 4''
%% \end{itemize}
%% \item  [Mapping (4 vs. 3) $\to$ (5 vs. 4)]:
%% \begin{itemize}
%% \item Map state space in (5 vs 4) to (4 vs. 3) by finding closer prototypes. Use weighted euclidean distance with values (1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0).
%% \item Q value for ``Pass 3'' goes ``Pass 4'' (when ``Pass 3'' was the preferred action, now it will choose randomly betweem both of them)
%% \item Alternative mapping: Q value for ``Pass 1'' goes to ``Pass 4''
%% \end{itemize}
%% \end{description}

%% \section{Scenarios}

%% \begin{enumerate}
%% \item Learn (3 vs. 2) from scratch
%% \item Learn (4 vs. 3) from scratch
%% \item Learn (5 vs. 4) from scratch
%% \item Learn (4 vs. 3) from (3 vs. 2)
%% \item Learn (5 vs. 4) from (4 vs. 3)
%% \item Learn (5 vs. 4) from (4 vs. 3) and (3 vs. 2)
%% \item Learn (5 vs. 4) from (4 vs. 3) and (3 vs. 2) with alternative mappings

%% \end{enumerate}



\bibliography{/usr0/fernando/latex/bib/rl,/usr0/fernando/latex/bib/fernando,/usr0/fernando/latex/bib/general,/usr0/fernando/latex/bib/general-daniel,/usr0/fernando/latex/bib/daniel,/usr0/fernando/latex/bib/vq,/usr0/fernando/latex/bib/classification,/usr0/fernando/latex/bib/otros,/usr0/fernando/latex/bib/parker,/usr0/fernando/latex/bib/rrl}

%\bibliography{blindformat}
\bibliographystyle{mlapa}

\end{document} 
