# A Taxonomy of Similarity Metrics for Markov Decision Processes

Álvaro Visús1 Javier García1 Fernando Fernández1
1Departamento de Informática, Universidad Carlos III de Madrid
Avda. de la Universidad, 30. 28911 Leganés (Madrid). Spain<EMAIL_ADDRESS>{fjgpolo<EMAIL_ADDRESS>
###### Abstract

Although the notion of task similarity is potentially interesting in a wide
range of areas such as curriculum learning or automated planning, it has
mostly been tied to transfer learning. Transfer is based on the idea of
reusing the knowledge acquired in the learning of a set of source tasks to a
new learning process in a target task, assuming that the target and source
tasks are close enough. In recent years, transfer learning has succeeded in
making Reinforcement Learning (RL) algorithms more efficient (e.g., by
reducing the number of samples needed to achieve the (near-)optimal
performance). Transfer in RL is based on the core concept of similarity:
whenever the tasks are similar, the transferred knowledge can be reused to
solve the target task and significantly improve the learning performance.
Therefore, the selection of good metrics to measure these similarities is a
critical aspect when building transfer RL algorithms, especially when this
knowledge is transferred from simulation to the real world. In the literature,
there are many metrics to measure the similarity between MDPs, hence, many
definitions of similarity or its complement distance has been considered. In
this paper, we propose a categorization of these metrics and analyze the
definitions of similarity proposed so far, taking into account such
categorization. We also follow this taxonomy to survey the existing
literature, as well as suggesting future directions for the construction of
new metrics.

##  1 Introduction

Markov decision processes (MDPs) are a common way of encoding decision making
problems in Reinforcement Learning (RL) tasks Sutton and Barto (2011). In RL,
an MDP is considered to be solved when a policy (i.e., a way of behaving for
each state) has been discovered which maximizes a long-term expected return.
However, although RL is known as an effective machine learning technique, it
might perform poorly in complex problems, leading to a slow rate of
convergence. This issue magnifies when facing realistic continuous problems
where the curse of dimensionality is inevitable. Transfer learning in RL is a
successful technique to remedy such a problem. Speciﬁcally, rather than
learning a new policy for every MDP, a policy could be learned on one MDP,
then transferred to another, similar MDP, and either used as is, or treated as
a starting point from which to learn the new policy. Clearly this transfer
cannot be done successfully between any two MDPs, but only in the case they
are similar.

Therefore, in this context one question arises: when are two MDPs similar? We
must give a better definition of what constitutes similar MDPs. In this paper,
we consider the concept of similar is related to the notion of “positive
transfer” Taylor and Stone (2009). Formally, positive transfer happens when
the knowledge in the source task contribute to the improved performance of
learning in the target task, and it is considered a negative transfer
otherwise, i.e., when the transfer hurts the learning performance when
compared with learning from scratch. Additionally, the greater the improvement
in the target task, i.e., the greater the positive transfer, the more similar
the tasks has to be considered. It is important to be aware of the fact that,
based on this description, the concept of similarity might not be related with
the structural similarities between the MDPs. So the correct selection of
metrics that allow us to measure the similarity between MDPs is a critical
issue in transfer learning, precisely to avoid the negative transfer.

The literature in transfer learning has proposed different metrics to measure
the level of similarity between MDPs, hence, different definitions of the
concept of similarity have been considered so far. This paper surveys the
existing similarity metrics and contributes a taxonomy that, in its root,
classifies them into two clearly distinct categories: model-based, and
performance-based metrics. We consider such a distinction as a core
contribution, allowing to categorize metrics in a novel and useful way. Model-
based metrics are based on the structural similarities between the MDP models.
Such model-based metrics can be computed in different ways depending on what
elements of the MDP models come into play to compute the similarity Ammar et
al. (2014); Taylor et al. (2008b); Milner (1982); Castro and Precup (2011);
Svetlik et al. (2017). Instead, performance-based metrics are computed by
comparing the performance of the learning agents in the source task and the
target task. Such a performance comparison can be done in two different ways:
by comparing the resulting policies from learning in the source task and the
target task Carroll and Seppi (2005); Karimpanal and Bouffanais (2018) or,
from a transfer point of view, by measuring the reuse gain, i.e., the positive
transfer Mahmud et al. (2013); Sinapov et al. (2015); Fernández and Veloso
(2013). Many metrics can be used to measure such a reuse gain of transfer
(e.g., jumpstart, asymptotic performance, total reward) Taylor and Stone
(2009). In some ways, this reuse gain could be the best method for measuring
similarity between two tasks Carroll and Seppi (2005). Unfortunately, it is
often difficult to compute all of these performance-based measures before
actually solving the target task, since most of them require to be computed a
posteriori, i.e., after the learning processes. However, there are some few
exceptions to this rule, within which, for example, the similarity is computed
on-line, i.e., during solving the target task Fernández and Veloso (2013).

We hope our taxonomy applies to a wide range of researchers, not just those
interested in transfer learning. For example, the proposed metrics could also
be a critical step forward to sort the samples and tasks in Curriculum
Learning Narvekar et al. (2020), or could be used to measure the distance
between simulation and the real world in a Sim-to-Real context Zhao et al.
(2020). They could also be used to understand the similarities within a set of
tasks in Multi-task Learning Shui et al. (2019), or Automated Planning
Fernández et al. (2011).

The remainder of the paper is organized as follows. Section 2 provides some
preliminary concepts required to better understand the rest of the paper.
Section 3 presents our proposed taxonomy, explaining how we group and
categorize the different metrics. The model-based metrics are examined in
Section 4, whilst the performance-based metrics are considered in Section 5.
In Section 6 we discuss the surveyed methods and in Section 7 we identify open
areas of research for future work. Finally, we conclude with Section 8.

##  2 Background

This section introduces key concepts required to better understand the rest of
the paper. First, it is introduced some background in RL (Section 2.1), then
the main concepts of transfer RL are visited (Section 2.2), and finally the
concepts of similarity and distance (Section 2.3).

###  2.1 Reinforcement Learning

Typically, RL tasks are described as Markov Decision Processes (MDPs)
represented by tuples in the form $\mathcal{M}=\langle S,A,T,R\rangle$, where
$S$ is the state space, $A$ is the action space, $T:S\times A\rightarrow S$ is
the transition function between states, and $R:S\times A\rightarrow\mathbb{R}$
is the reward function Sutton and Barto (2011). At each step, the agent is
able to observe the current state, and choose an action according to its
policy $\pi:S\rightarrow A$. The goal of the RL agent is to learn an optimal
policy $\pi^{*}$ that maximizes the return $J(\pi)$:

$J(\pi)=\sum_{k=0}^{K}\gamma^{k}r_{k}$ (1)

where $r_{k}$ is the immediate reward obtained by the agent on step $k$, and
$\gamma$ is the discount factor, which determines how relevant the future is
(with $0\leq\gamma\leq 1$). The interaction between the agent and the
environment tends to be broken into episodes, that end when reaching a
terminal state, or when a fixed amount of time has passed. With the goal of
learning the policy $\pi$, Temporal Differences methods Sutton and Barto
(2011) estimate the sum of rewards represented in Equation 1. The function
that estimates the sum of rewards, i.e., the return for each state $s$ given
the policy $\pi$ is called the value-function $V^{\pi}(s)=E[J(\pi)|s_{0}=s]$.
Similarly, the action-value function $Q^{\pi}(s,a)=E[J(\pi)|s_{0}=s,a_{0}=a]$
is the estimation of the value of performing a given action $a$ at a state $s$
being $\pi$ the policy followed. The Q-learning algorithm Watkins (1989) is
one of the most widely used for computing the action-value function.

###  2.2 Transfer Learning for Reinforcement Learning

In the transfer learning scenario we assume there is an agent who previously
has addressed a set of source tasks represented as a sequence of MDPs,
$\mathcal{M}_{1},\dots,\mathcal{M}_{n}$. If these tasks are somehow “similar”
to a new task $\mathcal{M}_{n+1}$, then it seems reasonable the agent uses the
acquired knowledge solving $\mathcal{M}_{1},\dots,\mathcal{M}_{n}$ to solve
the new task $\mathcal{M}_{n+1}$ faster than it would be able to from scratch.
Transfer learning is the problem of how to obtain, represent and, ultimately,
use the previous knowledge of an agent Torrey and Shavlik (2010); Taylor and
Stone (2009).

However, transferring knowledge is not an easy endeavour. On the one hand, we
can distinguish different transfer settings depending on whether the source
and target tasks share or not the state and action spaces, the transition
probabilities and the reward functions. It is common to assume that the tasks
share the state space and the action set, but differing the transition
probabilities and/or reward functions. However, in case the tasks do not share
the state and/or the action spaces, it is required to build mapping functions,
$\mathcal{X}_{S}(s_{t})=s_{s}$, $\mathcal{X}_{A}(a_{t})=a_{s}$, able to map a
state $s_{t}$ or action $a_{t}$ in the target task to a state $s_{s}$ or
action $a_{s}$ in the source task. Such mapping functions require not only
knowing if two tasks are related, but how they are related, which means an
added difficulty. On the other hand, it is required to select what type of
information is going to be transferred. Different types of information have
been transferred so far ranging from instance transfer (a set of samples
collected in the source task) to policy transfer (i.e., the policy $\pi$
learned in the source task). Nor is this a simple task, because depending on
how much and how the source and target tasks are related, it could be
transferred one type of information or another.

Finally, the most “similar” task among $\mathcal{M}_{1},\dots,\mathcal{M}_{n}$
to solve $\mathcal{M}_{n+1}$ should be selected in the hope that it produces
the most positive transfer. For this purpose, similarity metrics could be
used, which translate into a measurable quantity of how related two tasks are.

###  2.3 Similarity and Distance Metrics

Similarity metrics are a very important part of transfer learning, as they
provide a measure of distance between tasks. Similarity functions, or their
complementary distance functions, are mathematical functions that assign a
numerical value to each pair of concepts or objects in a given domain. This
value measures how similar these two concepts or objects are: if they are very
similar, it is assigned a very low distance, and if they are very dissimilar,
it is assigned a larger distance Ontañón (2020).

##  3 Taxonomy of Similarity Metrics for MDPs

We consider there are two tasks, $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$,
described formally by the tuples $\mathcal{M}_{i}=\langle
S_{i},A_{i},T_{i},R_{i}\rangle$ and $\mathcal{M}_{j}=\langle
S_{j},A_{j},T_{j},R_{j}\rangle$, where they could share (or not) the state
space, the action space, or the transition and reward dynamics.

######  Definition 1.

Given two tasks $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, we define a task
distance metric as a heuristic function
$d(\mathcal{M}_{i},\mathcal{M}_{j})\rightarrow[0,\infty)$, such that if
$d(\mathcal{M}_{i},\mathcal{M}_{j})<d(\mathcal{M}_{k},\mathcal{M}_{j})$, then
$\mathcal{M}_{i}$ is considered more similar to $\mathcal{M}_{j}$ than
$\mathcal{M}_{k}$.111It should be noted that in the context of task similarity
such a measure of distance need not be a “metric” in the mathematical sense of
this term, but it needs to allow us to define an order between tasks.

Definition 1 allows us to use the function $d(\cdot,\cdot)$ to obtain an
ordering between tasks in such a way that we can select the more similar one.
Ideally, the concept of similarity should be related to the concept of
positive transfer: the smaller the distance
$d(\mathcal{M}_{i},\mathcal{M}_{j})$, the greater the positive transfer.
Additionally, $d(\mathcal{M}_{i},\mathcal{M}_{j})$ should be computed before
or, at least, during the transfer experiment, in order to select an adequate
task to use in transfer. However, the literature proposes different ways to
compute $d(\mathcal{M}_{i},\mathcal{M}_{j})$.

In this paper, we consider two main trends for the computation of the distance
metric $d(\mathcal{M}_{i},\mathcal{M}_{j})$. Such trends are depicted in
Figure 1. The first one measures the structural or model similarities between
the given MDPs. The second measures the similarities by using the performance
of the learning agent in both the source and target tasks.

##  4 Model-based Metrics

As regards the first, model-based metrics measure the degree of similarity
between a source and a target task by using their corresponding MDP models
(i.e., states, actions, transition and rewards dynamics). There are several
alternatives to this model-based metrics depending on what components of the
MDPs are taken into account. In our proposed taxonomy, we categorize these
metrics in five groups: (i) transition and reward dynamics, (ii) transitions,
(iii) rewards, (iv) state and actions and (v) states.

$\parbox{36.98866pt}{Similarity Metrics}\begin{cases}\text{Model
Based}\begin{cases}\parbox{36.98866pt}{Transition \& reward
dynamics}\begin{cases}\text{Abstraction}\begin{cases}\text{Bisimulation}\\\
\vskip 4.0pt\cr\text{Homomorph.}\\\ \end{cases}\\\ \vskip
4.0pt\cr\text{Compliance}\\\ \vskip 4.0pt\cr\text{MDP graphs}\\\
\end{cases}\\\ \vskip 4.0pt\cr\text{Transitions}\\\ \vskip
4.0pt\cr\text{Rewards}\\\ \vskip 4.0pt\cr\text{State \& Actions}\\\ \vskip
4.0pt\cr\text{States}\\\ \end{cases}\\\ \vskip
9.0pt\cr\parbox{48.36958pt}{Performance Based}\begin{cases}\text{Policy
similarity}\begin{cases}\text{Policy values}\\\ \vskip 4.0pt\cr\text{Policy
parameters}\\\ \end{cases}\\\ \vskip 9.0pt\cr\text{Reuse
gain}\begin{cases}\text{Off-line reuse gain}\\\ \vskip 4.0pt\cr\text{On-line
reuse gain}\\\ \end{cases}\end{cases}\end{cases}$

Figure 1: Overview of the similarity metrics considered in this survey

###  4.1 Transition & reward dynamics

They require complete knowledge of the MDP models both of the source and the
target tasks. We distinguish three ways of computing similarity metrics using
such a complete knowledge: (i) by a sort of metrics based on state abstraction
(or state aggregation) techniques Li et al. (2006); Ferns et al. (2004, 2012);
Castro (2020), (ii) by compliance metrics Lazaric et al. (2008); Lazaric
(2008); Fachantidis et al. (2015); Fachantidis (2016) and (iii) by metrics
based on the construction of MDP graphs Kuhlmann and Stone (2007); Wang et al.
(2019).

####  4.1.1 State abstraction

In RL, a common practice is to aggregate states in order to obtain an abstract
description of the problem, i.e., a more compact and easier representation of
the task to work with Li et al. (2006). These approaches are based on the same
common principle: if a number of states are considered to be similar, they can
be aggregated as a single one. This same principle can also be used to compute
the similarity between two states belonging to different MDPs. In this paper,
we survey two of these methods which actually have been used for transfer in
RL: bisimulation Ferns et al. (2004, 2012); Castro and Precup (2011); Song et
al. (2016), and homomorphism Ravindran and Barto (2002); Sorg and Singh
(2009).

######  Definition 2.

Given two MDPs $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, we define
$d(\mathcal{M}_{i},\mathcal{M}_{j})=d(S_{i},S_{j})$, where $d(S_{i},S_{j})$
measures the distance between $S_{i}$ and $S_{j}$ by computing the
bisimulation or homomorphism distances of the individual state pairs,
$d(s_{i},s_{j})$, $\forall s_{i},s_{j}\in S_{i}\times S_{j}$.

Bisimulation metrics compute $d(s_{i},s_{j})$ by comparing the transition and
reward dynamics of $s_{i}$ and $s_{j}$: the more similar the reward and
transition structures of $s_{i}$ and $s_{j}$ are, the smaller
$d(s_{i},s_{j})$. One of the shortcomings of the bisimulation metrics is that
they require both MDPs, $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, to have the
same action sets, $A_{i}=A_{j}$. However, such a shortcoming has been
successfully addressed by the homomorphism metrics which are able to deal with
different action spaces, $A_{i}\neq A_{j}$ Ravindran and Barto (2002); Sorg
and Singh (2009). Once the distance between all state pairs in
$\mathcal{M}_{i}$ and $\mathcal{M}_{j}$ is computed, it is required to
composite them to compute the distance $d(\mathcal{M}_{i},\mathcal{M}_{j})$
between the two MDPs. It could not be appropriate to simply accumulate or
average the distances between all different state pairs, so it is typical to
define $d(S_{i},S_{j})$ as a function which measure the distance between the
sets corresponding to the state spaces $S_{i}$ and $S_{j}$, e.g., the
Hausdorff, or the Kantorovich function Song et al. (2016), although other
metrics between sets would also be possible Conci and Kubrusly (2018).

####  4.1.2 Compliance

The compliance measure is defined as the probability of a sample $\langle
s,a,s^{\prime},r\rangle$ in a target task $\mathcal{M}_{j}$ of being generated
in the source task $\mathcal{M}_{i}$ Lazaric et al. (2008); Fachantidis
(2016); Fachantidis et al. (2015). Therefore, it is easy to deduce that the
compliance between the entire target task and the entire source task allows us
to measure the similarity between the two tasks.

######  Definition 3.

Given two MDPs, $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, and two sets of
experience tuples generated $D_{\mathcal{M}_{i}}$ and $D_{\mathcal{M}_{j}}$
gathered from $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, the compliance between
$\mathcal{M}_{i}$ and $\mathcal{M}_{j}$ is computed as:

$\Lambda=\frac{1}{n}\sum_{t=0}^{n}P(\sigma_{t}|D_{\mathcal{M}_{i}})$ (2)

where $n$ is the number of samples in $D_{\mathcal{M}_{j}}$, and $\sigma_{t}$
is the $t$-th tuple in $D_{\mathcal{M}_{j}}$.

$\Lambda$ is not strictly a distance metric but a probability: the more likely
the samples of the target task are generated in the source task, the closer
$\Lambda$ to $1$. Therefore, compliance could be used to obtain a distance
metric between MDPs like the ones this survey is looking for, e.g.,
$d(\mathcal{M}_{i},\mathcal{M}_{j})=1-\Lambda$.

####  4.1.3 MDP graphs

They are based on the construction of graphs that represent the transition and
the reward functions both of the source task and the target task. Then, they
find structural similarities between tasks based on graph-similarity or graph-
matching algorithms.

######  Definition 4.

Given two MDPs $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$ and their corresponding
alternative representation as graphs, $G_{\mathcal{M}_{i}}$ and
$G_{\mathcal{M}_{j}}$, we define $d(\mathcal{M}_{i},\mathcal{M}_{j})$ as
inversely related to $\Phi(G_{\mathcal{M}_{i}},G_{\mathcal{M}_{j}})$, where
$\Phi(\cdot,\cdot)\rightarrow[0,\infty)$ is a function that measures the
structural similarity between $G_{\mathcal{M}_{i}}$ and $G_{\mathcal{M}_{j}}$.

Wang et al. (2019) represents the MDPs as bipartite directed graphs, which
permits the computation of structural similarity measures between them.
Although several of these structural functions $\Phi(\cdot,\cdot)$ could be
used such as RoleSim Jin et al. (2014) or MatchSim Lin et al. (2012), Wang et
al. are based on SimRank Jeh and Widom (2002), which basic idea is that two
nodes are similar iff their neighbors are similar. On the other hand, Kuhlmann
and Stone (2007) represents the MDPs as rule graphs instead of bipartite
graphs for the particular problem of General Game Playing Genesereth et al.
(2005). Such a rule graph is an accurate abstraction of the MDP problem, and
can be properly compared to other rule graphs using an isomorphic function as
$\Phi(\cdot,\cdot)$ McKay and Piperno (2014). Finally, Liu and Stone (2006)
models the problem as a Qualitative Dynamic Bayes Network (QDBN). This assigns
types to the nodes and edges, providing additional characteristics to compare.

###  4.2 Transitions

The metrics considered in this category use tuples in the form $\langle
s,a,s^{\prime}\rangle$ to measure the similarity between MDPs.

######  Definition 5.

Given two tasks $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, and two sets
$\mathcal{D}_{\mathcal{M}_{i}}$ and $\mathcal{D}_{\mathcal{M}_{j}}$ of
experience tuples in the form $\tau=\langle s,a,s^{\prime}\rangle$ gathered
from $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, we can define the distance
between them as
$d(\mathcal{M}_{i},\mathcal{M}_{j})=d(\mathcal{D}_{\mathcal{M}_{i}},\mathcal{D}_{\mathcal{M}_{j}})$.

Ammar et al. (2014) use $\mathcal{D}_{\mathcal{M}_{j}}$ to build an RBM model
which describes the transitions in $\mathcal{M}_{j}$ in a richer feature
space. Then, they feed the tuples $\tau_{k}\in\mathcal{D}_{\mathcal{M}_{i}}$
into this RBM model to obtain a reconstruction $\tau^{\prime}_{k}$. Afterward,
they compute the Euclidean distance between $\tau_{k}$ and
$\tau^{\prime}_{k}$. Similarly, Taylor et al. (2008b) use
$\mathcal{D}_{\mathcal{M}_{j}}$ to learn a one-step transition model
$M(s,a)\rightarrow s^{\prime}$. Afterward, for each tuple $\tau_{k}=\langle
s,a,s^{\prime}\rangle$ in $\mathcal{D}_{\mathcal{M}_{i}}$, they compute the
Euclidean distance between $s^{\prime}$ and $M(s,a)$. In both cases, the
distance $d(\mathcal{D}_{\mathcal{M}_{i}},\mathcal{D}_{\mathcal{M}_{j}})$ is
computed as the average of the Euclidean distances obtained for each
$\tau_{k}\in D_{\mathcal{M}_{i}}$.

###  4.3 Rewards

The metrics can also measure the similarity between MDPs according to the
distance between their reward dynamics.

######  Definition 6.

Given two MDPs $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, we define the distance
between them as $d(\mathcal{M}_{i},\mathcal{M}_{j})=d(R_{i},R_{j})$.

For instance, Carroll and Seppi (2005) computes $d(R_{i},R_{j})$ as
$d(R_{i},R_{j})=\frac{1}{n}\sum_{s\in S}\sum_{a\in
A}(R_{i}(s,a)-R_{j}(s,a))^{2}$, where $n$ is the total number of state-action
pairs in the source and the target task. Instead, Tao et al. (2021) assumes
the reward functions are a linear combination of some common features
$\phi(\cdot,\cdot)$, $R_{i}(s,a)=\phi(s,a)^{T}w_{i}$ and
$R_{j}(s,a)=\phi(s,a)^{T}w_{j}$, and then use the cosine distance function
between $w_{i}$ and $w_{j}$ to compute $d(R_{i},R_{j})$. Finally, in the
literature there are several ways of computing $d(R_{i},R_{j})$ Gleave et al.
(2020).

###  4.4 State & Action Spaces

In this case, the distance between MDPs is computed as the distance between
the state-action spaces.

######  Definition 7.

Given two MDPs $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, and their
corresponding state-action spaces, $S_{i}\times A_{i}$ and $S_{j}\times
A_{j}$, we define the distance as
$d(\mathcal{M}_{i},\mathcal{M}_{j})=d(S_{i}\times A_{i},S_{j}\times A_{j})$.

For instance, Narayan and Leong (2019) compute this distance as the averaged
difference between the corresponding state-action transition distributions of
the two tasks. Instead, Taylor et al. (2008) compute the Euclidean distance
between state-action pairs in the source and target tasks. This work is not
focused on the construction of a distance measure between MDPs, but such
Euclidean distances between all the state-action pairs could be composited to
obtain a sort of similarity metric.

###  4.5 States

Finally, the metrics in this category use the state space in both the source
and target tasks to compute the similarity between them.

######  Definition 8.

Given two MDPs $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, we can define the
distance between them as $d(\mathcal{M}_{i},\mathcal{M}_{j})=d(S_{i},S_{j})$,
where $d(S_{i},S_{j})$ measures the distance between $S_{i}$ and $S_{j}$.

Svetlik et al. (2017) propose to compute $d(S_{i},S_{j})$ as the relation
between the applicability of the value function (measured as the number of
states in $\mathcal{M}_{i}$ that also appears in $\mathcal{M}_{j}$), and the
experience required to learn in $\mathcal{M}_{j}$ (measured as the difference
of size between $S_{j}$ and $S_{i}$). Another area of research that is
relevant in this category is that of case based reasoning (CBR) Aamodt and
Plaza (1994). RL approaches based on CBR use a similarity function between the
states in the target task and the states stored in a case base corresponding
to a previous source task Celiberto et al. (2011). Such similarity function
could be used to measure the similarity between the state spaces, hence, the
similarity between the two tasks.

##  5 Performance-based Metrics

As regards the second major category in the proposed taxonomy, they are based
on the performance of the agents in the source task and the target task, where
this performance can be related to the policies themselves learned by the
agents in these tasks, or to the reuse gain an agent obtains reusing the
knowledge of a source task in a target task. So, we distinguish two different
approaches to overcoming the problem of computing such a performance-based
similarities: (i) by the policy similarity and (ii) by the reuse gain obtained
transferring the knowledge from a source task to the target task.

###  5.1 Policy similarity

They are based on the use of the learned value function $V^{\pi}$ or the
action-value function $Q^{\pi}$, or equivalently, on the behavioral policies
$\pi$ obtained in the source task and the target task. Therefore, these
metrics require the full (or partial) learning of these policies before the
computation of the similarity between tasks. Such a comparison can be
conducted in two different ways depending on what is being compared: (i) the
policy values, or (ii) the policy parameters.

####  5.1.1 Policy values

In this case, the comparison is conducted by observing the specific $q$-values
or $v$-values of the $Q^{\pi}$-function or the $V^{\pi}$-function of the
source and target tasks. Therefore, in this case, it is really being measured
the degree of similarity of the policies obtained in both tasks.

######  Definition 9.

Given two tasks $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$ and the $q$-values of
$Q^{\pi_{i}}$ and $Q^{\pi_{j}}$ learned in these tasks, we define
$d(\mathcal{M}_{i},\mathcal{M}_{j})=d(Q^{\pi_{i}},Q^{\pi_{j}})$. This metric
is transformed into
$d(\mathcal{M}_{i},\mathcal{M}_{j})=d(V^{\pi_{i}},V^{\pi_{j}})$ if
$V^{\pi_{i}}$ and $V^{\pi_{j}}$ are computed instead.

Carroll and Seppi (2005) propose to compute $d(V^{\pi_{i}},V^{\pi_{j}})$ as
the number of states with identical maximum $v$-value, and
$d(Q^{\pi_{i}},Q^{\pi_{j}})$ as the mean squared error of the $q$-values in
$Q^{\pi_{i}}$ and $Q^{\pi_{j}}$. Instead, Zhou and Yang (2020) compute
$d(Q^{\pi_{i}},Q^{\pi_{j}})$ deriving latent structures of tasks and ﬁnding
matches between $Q^{\pi_{i}}$ and $Q^{\pi_{j}}$.

####  5.1.2 Policy Approximation Parameters

In RL, the value function $V^{\pi}$ or the action-value function $Q^{\pi}$
usually are represented or approximated with a parameter vector $\theta$.
Intuitively, the metrics within this category compare the particular weights
of the parameter vectors corresponding to the value functions of the source
task and the target task in order to measure the similarity between them.

######  Definition 10.

Given two tasks $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$ and the parameterize
functions $Q^{\theta_{i}}\approx Q^{\pi_{i}}$ and $Q^{\theta_{j}}\approx
Q^{\pi_{j}}$ learned in these tasks, we consider
$d(\mathcal{M}_{i},\mathcal{M}_{j})=d(\theta_{i},\theta_{j})$.

The distance $d(\theta_{i},\theta_{j})$ can be computed using the cosine
similarity between two non-zero vectors Karimpanal and Bouffanais (2018). Such
an approach opens the door to the comparison of other policy representations
Ferrante et al. (2008).

###  5.2 Reuse gain

In these techniques, the level of similarity is an approximation to the
advantage gained by using the knowledge in one source task to speed up the
learning of another target task Carroll and Seppi (2005); Carroll (2005);
Taylor and Stone (2009).

######  Definition 11.

Given two tasks $\mathcal{M}_{i}$ and $\mathcal{M}_{j}$, and
$g(\mathcal{M}_{i},\mathcal{M}_{j})$ which denotes the gain of transferring
the knowledge learned in $\mathcal{M}_{i}$ to $\mathcal{M}_{j}$, we can
consider $d(\mathcal{M}_{i},\mathcal{M}_{j})$ as inversely related to
$g(\mathcal{M}_{i},\mathcal{M}_{j})$.

Therefore, it is important to bear in mind that these metrics actually require
that the transfer experiment be entirely or partially run before measuring the
degree of similarity between tasks. However, regardless of the particular
technique used to compute such a reuse gain, the higher the reuse gain, the
greater the similarity between the tasks. In this paper, we distinguish two
approaches within this category depending on whether the reuse gain is
computed after or during the transfer process: (i) off-line reuse gain, and
(ii) on-line reuse gain.

####  5.2.1 Off-line reuse gain

In this case, the reuse gain $g(\mathcal{M}_{i},\mathcal{M}_{j})$ is estimated
as the difference in performance between the learning process with and without
transfer, and once the learning processes are considered to be finished
Carroll (2005); Mahmud et al. (2013); Sinapov et al. (2015); Zhan et al.
(2016). Such gain $g(\mathcal{M}_{i},\mathcal{M}_{j})$ can be computed as the
jumpstart Sinapov et al. (2015); Carroll (2005), the time to convergence
Carroll (2005), the asymptotic performance Mahmud et al. (2013), although
other metrics such as the total reward or the transfer ratio could be also
used Taylor and Stone (2009).

####  5.2.2 On-line reuse gain

On the contrary, in these approaches, the reuse gain is estimated on-line at
the same time that the policy in the target task is computed Fernández and
Veloso (2013); Azar et al. (2013); Li and Zhang (2017). It is important to
bear in mind that the on-line computation of this gain only makes sense if
during the learning process we have several transfer sources to choose from.
At the beginning of the learning process, these approaches have at its
disposal the knowledge learned in solving a set of previous tasks
$\\{\mathcal{M}_{1},\dots,\mathcal{M}_{n}\\}$ to learn the new task
$\mathcal{M}_{j}$. During learning, they compute
$g(\mathcal{M}_{i},\mathcal{M}_{j})$ of each past task
$\mathcal{M}_{i}\in\\{\mathcal{M}_{1},\dots,\mathcal{M}_{n}\\}$. To do that,
they transfer the knowledge acquired solving $\mathcal{M}_{i}$ to
$\mathcal{M}_{j}$ during a limited number of episodes $m$. Then,
$g(\mathcal{M}_{i},\mathcal{M}_{j})$ is computed as the average reward
obtained during those $m$ episodes Fernández and Veloso (2013); Azar et al.
(2013). Once all gains are computed, it is possible to decide on-line which is
the closest task to $\mathcal{M}_{j}$ within
$\\{\mathcal{M}_{1},\dots,\mathcal{M}_{n}\\}$, so that the knowledge of the
selected closest task can have a greater influence on learning about the
policy in $\mathcal{M}_{j}$.

##  6 Discussion

From a transfer point of view, the ultimate goal of all similarity metrics is
in some way to predict the relative advantage that would be gained by using a
source task in a target task. The more similar the source and target tasks
are, the greater the positive transfer. The correct selection of a distance
metric should be carried out attending to four dimensions: nature of the
state-action space, amount of information available on the tasks, computation
moment, and transfer technique.

Obviously, the selection of the metric depends on the nature of the state-
action space. Some approaches typically require enumerating all the states
both in the source and the target tasks Castro (2020); Zhou and Yang (2020),
but such full state enumeration is impractical for large state spaces, and
impossible for continuous state spaces. Other methods require that both tasks
have the same state-action space Lazaric et al. (2008); Azar et al. (2013),
which is not true in most of the cases. However, the latter can be partially
alleviated by the construction of inter-task mapping functions,
$\mathcal{X}_{S}$ and $\mathcal{X}_{A}$.

Another issue that needs to be addressed is how much information we have about
the tasks to solve. Most model-based approaches require prior full information
(or accurate approximations) about the transition and reward dynamics Castro
and Precup (2010); Lazaric et al. (2008); Wang and Liang (2019), or about the
size of the state and action spaces Svetlik et al. (2017); Carroll (2005). In
this sense, performance-based metrics have a clear advantage over model-based
ones: in general, performance-based metrics require less a priori information
about the task to be solved, although as a counterpoint they need to fully or
partially run the transfer experiment to obtain the distance measurement.

This leads us to the third issue: the computation moment. Ideally, the
computation of the similarity metric should be before or, at least, during the
transfer. Off-line reuse gain approaches are undoubtedly the best method for
measuring similarity between two tasks: they produce such a measure after the
transfer experiment has been run, in such a way that we can compute the real
gain. However, if the point is to use the task similarity measure to choose a
task to use in transfer, these metrics are useless. In this case, model-based
metrics take advantage over performance-based metrics: they allow to compute
the metrics before the transfer process. These metrics can be used to choose
the most similar MDP before transfer, but as far as we know there is no
theoretical guarantees that the most similar MDP is similar enough to produce
a positive transfer. By contrast, the metrics based on the on-line reuse gain
are at the point half-way between both. They allow to compute the similarity
metric during transfer, so that depending on the similarity of the source
task, it will introduce a greater or lesser exploration bias in the learning
process of the new task.

Finally, the success of a metric is intimately tied with the transfer
technique that uses it Carroll (2005); Carroll and Seppi (2005). This means
that there is probably no one best universal metric that works with all
transfer techniques and problems, in the same way that there is no one best
universal transfer technique. Since each metric can capture different types of
similarity and each transfer technique induces different bias in the learning
process, the question of selecting the best metric turns into finding the
correct metric for a transfer technique to be applied to a particular task.

##  7 Future Directions

The previous discussion points out several future directions. On the one hand,
since there is not a best metric, it would be useful to use several of them.
For instance, model-based metrics can be used to return a useful approximation
of task similarity before the tasks are learned, although this measure can be
adapted on-line during the learning process so that the bias that the source
task induces in the exploration process is adjusted dynamically. On the other
hand, given that different metrics compute different types of similarity
(i.e., model-based metrics measure structural similarities, whilst
performance-based metrics measure performance similarities), the agent can be
equipped with the ability not only to determine which source task to use, but
also which transfer technique to use given the type of similarity between the
source and target tasks.

Another interesting line of research is that based on building semantic
representations of the tasks through domain-dependent features. For instance,
we can define a particular Pac-Man task from features like the number of
ghosts, behavior of the ghosts, or the type of the maze, and use these
features to build a similarity metric between different Pac-Man tasks. In
fact, one may heuristically combine structural, performance, but also semantic
similarity aspects into a same metric. Thus, it could be obtained a metric
more aligned with the way in which humans decides what is similar, since
humans analyze the similarity between concepts or objects from different
perspectives Kemmerer (2017).

Finally, transferring learned models from simulation to the real world remains
one of the hardest problems in control theory Zhao et al. (2020). In this
case, similarity metrics can help to answer how similar simulations and the
actual world are. They could be used to provide theoretical guaranties that
ensure the learned policies transferred from simulation to the actual world
will perform as required, or to deﬁne mechanisms to tune/modify the simulated
environments, so the gap between the simulated world and the actual one
decreases.

##  8 Concluding Remarks

This paper contributes a compact and useful taxonomy of similarity metrics for
Markov Decision Processes. The leaves of the taxonomy have been used to
provide a literature review that surveys the existing work. We differentiated
between model-based and performance-based metrics, depending on whether a
structural or performance criterion has been used in its creation. The
proposed taxonomy permits to organize clearly the different similarity
metrics, or find commonalities between them. This can help the reader to
choose similarity metrics for their tasks, or even define their own. We also
discussed different selection criteria and some promising future research
directions.

## Acknowledgements

This research was funded in part by JPMorgan Chase & Co. Any views or opinions
expressed herein are solely those of the authors listed, and may differ from
the views and opinions expressed by JPMorgan Chase & Co. or its affiliates.
This material is not a product of the Research Department of J.P. Morgan
Securities LLC. This material should not be construed as an individual
recommendation for any particular client and is not intended as a
recommendation of particular securities, financial instruments or strategies
for a particular client. This material does not constitute a solicitation or
offer in any jurisdiction.

This work has been supported by the Madrid Government (Comunidad de Madrid-
Spain) under the Multiannual Agreement with UC3M in the line of Excellence of
University Professors (EPUC3M17), and in the context of the V PRICIT (Regional
Programme of Research and Technological Innovation).

## References

  * Aamodt and Plaza [1994] Agnar Aamodt and Enric Plaza.  Case-based reasoning: Foundational issues, methodological variations, and system approaches.  AI communications, 7(1):39–59, 1994.
  * Ammar et al. [2014] Haitham Ammar, Eric Eaton, Matthew Taylor, Constantin Decebal, Decebal Mocanu, Kurt Driessens, Gerhard Weiss, and Karl Tuyls.  An automated measure of mdp similarity for transfer in reinforcement learning.  In Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence, 07 2014.
  * Azar et al. [2013] Mohammad Gheshlaghi Azar, Alessandro Lazaric, and Emma Brunskill.  Regret bounds for reinforcement learning with policy advice.  In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 97–112. Springer, 2013.
  * Carroll and Seppi [2005] J. L. Carroll and K. Seppi.  Task similarity measures for transfer in reinforcement learning task libraries.  In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 803–808 vol. 2, 2005.
  * Carroll [2005] James Lamond Carroll.  Task localization, similarity, and transfer; towards a reinforcement learning task library system.  2005\.
  * Castro and Precup [2010] Pablo Castro and Doina Precup.  Using bisimulation for policy transfer in mdps.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, 2010.
  * Castro and Precup [2011] Pablo Samuel Castro and Doina Precup.  Automatic construction of temporally extended actions for mdps using bisimulation metrics.  In European Workshop on Reinforcement Learning, pages 140–152. Springer, 2011.
  * Castro [2020] Pablo Samuel Castro.  Scalable methods for computing state similarity in deterministic markov decision processes.  In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20), 2020.
  * Celiberto et al. [2011] Luiz A Celiberto, Jackson P Matsuura, Ramón López de Mántaras, and Reinaldo Bianchi.  Using cases as heuristics in reinforcement learning: a transfer learning application.  2011\.
  * Conci and Kubrusly [2018] AURA Conci and CS Kubrusly.  Distance between sets-a survey.  arXiv preprint arXiv:1808.02574, 2018.
  * Fachantidis et al. [2015] Anestis Fachantidis, Ioannis Partalas, Matthew E Taylor, and Ioannis Vlahavas.  Transfer learning with probabilistic mapping selection.  Adaptive Behavior, 23(1):3–19, 2015.
  * Fachantidis [2016] Anestis Fachantidis.  Knowledge Transfer in Reinforcement Learning.  PhD thesis, 01 2016.
  * Fernández and Veloso [2013] Fernando Fernández and Manuela Veloso.  Learning domain structure through probabilistic policy reuse in reinforcement learning.  Progress in Artificial Intelligence, 2(1):13–27, 2013.
  * Fernández et al. [2011] Susana Fernández, Ricardo Aler, and Daniel Borrajo.  Knowledge transfer between automated planners.  AI Magazine, 32(2):79–94, 2011.
  * Ferns et al. [2004] Norm Ferns, Prakash Panangaden, and Doina Precup.  Metrics for finite markov decision processes.  In UAI, volume 4, pages 162–169, 2004.
  * Ferns et al. [2012] Norman Ferns, Prakash Panangaden, and Doina Precup.  Metrics for markov decision processes with infinite state spaces.  arXiv preprint arXiv:1207.1386, 2012.
  * Ferrante et al. [2008] Eliseo Ferrante, Alessandro Lazaric, and Marcello Restelli.  Transfer of task representation in reinforcement learning using policy-based proto-value functions.  In AAMAS (3), pages 1329–1332, 2008.
  * Genesereth et al. [2005] Michael Genesereth, Nathaniel Love, and Barney Pell.  General game playing: Overview of the aaai competition.  AI magazine, 26(2):62–62, 2005.
  * Gleave et al. [2020] Adam Gleave, Michael Dennis, Shane Legg, Stuart Russell, and Jan Leike.  Quantifying differences in reward functions, 2020.
  * Jeh and Widom [2002] Glen Jeh and Jennifer Widom.  Simrank: A measure of structural-context similarity.  In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’02, page 538–543, New York, NY, USA, 2002. Association for Computing Machinery.
  * Jin et al. [2014] Ruoming Jin, Victor E Lee, and Longjie Li.  Scalable and axiomatic ranking of network role similarity.  ACM Transactions on Knowledge Discovery from Data (TKDD), 8(1):1–37, 2014.
  * Karimpanal and Bouffanais [2018] Thommen George Karimpanal and Roland Bouffanais.  Self-organizing maps as a storage and transfer mechanism in reinforcement learning.  7 2018.
  * Kemmerer [2017] David Kemmerer.  Categories of object concepts across languages and brains: the relevance of nominal classification systems to cognitive neuroscience.  Language, Cognition and Neuroscience, 32(4):401–424, 2017.
  * Kuhlmann and Stone [2007] Gregory Kuhlmann and Peter Stone.  Graph-based domain mapping for transfer learning in general games.  In Proceedings of the 18th European Conference on Machine Learning, September 2007.
  * Lazaric et al. [2008] Alessandro Lazaric, Marcello Restelli, and Andrea Bonarini.  Transfer of samples in batch reinforcement learning.  In ICML, pages 544–551, 2008.
  * Lazaric [2008] Alessandro Lazaric.  Knowledge Transfer in Reinforcement Learning.  PhD thesis, 01 2008.
  * Li and Zhang [2017] Siyuan Li and Chongjie Zhang.  An optimal online method of selecting source policies for reinforcement learning.  arXiv preprint arXiv:1709.08201, 2017.
  * Li et al. [2006] Lihong Li, Thomas J Walsh, and Michael L Littman.  Towards a unified theory of state abstraction for mdps.  In ISAIM, 2006.
  * Lin et al. [2012] Zhenjiang Lin, Michael R Lyu, and Irwin King.  Matchsim: a novel similarity measure based on maximum neighborhood matching.  Knowledge and information systems, 32(1):141–166, 2012.
  * Liu and Stone [2006] Yaxin Liu and Peter Stone.  Value-function-based transfer for reinforcement learning using structure mapping.  In Proceedings of the Twenty-First National Conference on Artificial Intelligence, pages 415–20, July 2006.
  * Mahmud et al. [2013] M. Mahmud, Majd Hawasly, Benjamin Rosman, and Subramanian Ramamoorthy.  Clustering markov decision processes for continual transfer.  2013\.
  * McKay and Piperno [2014] Brendan D McKay and Adolfo Piperno.  Practical graph isomorphism, ii.  Journal of Symbolic Computation, 60:94–112, 2014.
  * Milner [1982] R. Milner.  A Calculus of Communicating Systems.  Springer-Verlag, Berlin, Heidelberg, 1982.
  * Narayan and Leong [2019] Akshay Narayan and Tze Yun Leong.  Effects of task similarity on policy transfer with selective exploration in reinforcement learning.  In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 2132–2134, 2019.
  * Narvekar et al. [2020] Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone.  Curriculum learning for reinforcement learning domains: A framework and survey.  Journal of Machine Learning Research, 21(181):1–50, 2020.
  * Ontañón [2020] Santiago Ontañón.  An overview of distance and similarity functions for structured data.  Artificial Intelligence Review, 53(7):5309–5351, 2020.
  * Ravindran and Barto [2002] Balaraman Ravindran and Andrew G Barto.  Model minimization in hierarchical reinforcement learning.  In International Symposium on Abstraction, Reformulation, and Approximation, pages 196–211. Springer, 2002.
  * Shui et al. [2019] Changjian Shui, Mahdieh Abbasi, Louis-Émile Robitaille, Boyu Wang, and Christian Gagné.  A principled approach for learning task similarity in multitask learning.  In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, 2019.
  * Sinapov et al. [2015] Jivko Sinapov, Sanmit Narvekar, Matteo Leonetti, and Peter Stone.  Learning inter-task transferability in the absence of target task samples.  volume 2, 2015.
  * Song et al. [2016] Jinhua Song, Yang Gao, Hao Wang, and Bo An.  Measuring the distance between finite markov decision processes.  In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), 2016.
  * Sorg and Singh [2009] Jonathan Sorg and Satinder Singh.  Transfer via soft homomorphisms.  In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2, pages 741–748, 2009.
  * Sutton and Barto [2011] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  2011\.
  * Svetlik et al. [2017] M Svetlik, Matteo Leonetti, J Sinapov, R Shah, N Walker, and P Stone.  Automatic curriculum graph generation for reinforcement learning agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, page 2590 2596, 2017.
  * Tao et al. [2021] Yunzhe Tao, Sahika Genc, Jonathan Chung, Tao Sun, and Sunil Mallya.  Repaint: Knowledge transfer in deep reinforcement learning, 2021.
  * Taylor and Stone [2009] Matthew E Taylor and Peter Stone.  Transfer learning for reinforcement learning domains: A survey.  Journal of Machine Learning Research, 10(7), 2009.
  * Taylor et al. [2008] Matthew E. Taylor, Nicholas K. Jong, and Peter Stone.  Transferring instances for model-based reinforcement learning.  In Walter Daelemans, Bart Goethals, and Katharina Morik, editors, Machine Learning and Knowledge Discovery in Databases, pages 488–505, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
  * Taylor et al. [2008b] Matthew E Taylor, Gregory Kuhlmann, and Peter Stone.  Autonomous transfer for reinforcement learning.  In AAMAS (1), pages 283–290. Citeseer, 2008b.
  * Torrey and Shavlik [2010] Lisa Torrey and Jude Shavlik.  Transfer learning.  In Handbook of research on machine learning applications and trends: algorithms, methods, and techniques, pages 242–264. IGI global, 2010\.
  * Wang and Liang [2019] De-zhi Wang and Jun-yan Liang.  Research and design of theme image crawler based on difference hash algorithm.  In IOP Conference Series: Materials Science and Engineering, volume 563, page 042080. IOP Publishing, 2019.
  * Wang et al. [2019] Hao Wang, Shaokang Dong, and Ling Shao.  Measuring structural similarities in finite mdps.  In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pages 3684–3690. International Joint Conferences on Artificial Intelligence Organization, 7 2019\.
  * Watkins [1989] Christopher Watkins.  Learning from Delayed Rewards.  PhD thesis, King’s College, Cambridge, UK, 1989.
  * Zhan et al. [2016] Yusen Zhan, Haitham Bou Ammar, and Matthew E. taylor.  Theoretically-grounded policy advice from multiple teachers in reinforcement learning settings with applications to negative transfer, 2016.
  * Zhao et al. [2020] Wenshuai Zhao, Jorge Peña Queralta, and Tomi Westerlund.  Sim-to-real transfer in deep reinforcement learning for robotics: a survey.  In 2020 IEEE Symposium Series on Computational Intelligence (SSCI), pages 737–744. IEEE, 2020.
  * Zhou and Yang [2020] Yi Zhou and Fenglei Yang.  Latent structure matching for knowledge transfer in reinforcement learning.  Future Internet, 12, 2 2020.