A Kernel Perspective on Behavioural Metrics for Markov Decision Processes
Authors: Pablo Samuel Castro
Tyler Kastner
Prakash Panangaden
Mark Rowland
Venue: Accepted by TMLR ()

Abstract: We present a novel perspective on behavioural metrics for Markov decision processes via the use of positive definite kernels. We define a new metric under this lens that is provably equivalent to the recently introduced MICo distance (Castro et al., 2021). The kernel perspective enables us to provide new theoretical results, including value-function bounds and low-distortion finite-dimensional Euclidean embeddings, which are crucial when using behavioural metrics for reinforcement learning representations. We complement our theory with strong empirical results that demonstrate the effectiveness of these methods in practice.

Published in Transactions Machine Learning Research (06/2023)
A Kernel Perspective on Behavioural Metrics for Markov Decision Processes
Pablo Samuel Castro Google Deep
psc@google.com com
Tyler Kastner" Universily of Toronto
tyler.kostherr@mmillmmllll
Prakash Panangaden*
prakash@cs.mciill.oo
MeGill Universily
Mark Rowland* Google Deep
markrolland@googe..cm
Reviewed on OpenReviow: hitps: // openreview. net/ forum? id= nHffPlllyy
Abstract
Behavioural metrics have been shown to be an effective mechanism for construct- ing representations in reinforcement learning. We present a novel perspective on behavioural metrics for Markov decision processes via the use of positive definite kernels. We leverage this new perspective to define new metric that is provably oquivalent to the recently introduced MICo distance (Castro et al., 2021). The ker- nel perspective further enables us to provide new theoretical results, which has so far eluded prior work. These include bounding value function differences by means of our metric, and the demonstration that our metric can be provably embedded into finite-limensional Euclidean space with low distortion error. These are two crucial properties when using behavioural metrics for reinforcement lcarning representa- tions. We complement our theory with strong empirical results that demonstrate the effectiveness of these methods in practice.
1 Introduction
As tabular methods are insufficient for most state spaces, function approximation in reinforcement learning is a well-established paradigm for estimating functions of interest, such as the expected sum of discounted returns V (Sutton & Barto, 2018). A general value function approximator can be seen composition of m-dimeusional embedding & X RT which maps a state space X to a m-dimensional space R",, and a function approzimator v m - R (c.g. V Rs v o Φ). Whilc é can be fixed, as the case in linear function approximation (Baird, 1995; Konidaris et al., 2011) an increasingly popular approach is to learn both v and ø concurrently, typically with the use of deep neural networks. This raises the question of what constitutes a good embedding o, which forms the basis of the field of representation learning.
Authors listed in alphabetical order. See below for details of contributions. Work done while student McGill University.

---

Published in Transactions on Machine Learning Research (06/2023)
Previous approaches to learning & include spectral decompositions of transition and reward op- crators (Dayan, 1993; Mahadevan & Maggioni, 2007) and implicit learning through the use of auxiliary tasks (Lange & Riedmiller, 2010; Finn et al., 2015; Jaderberg et al., 2017; Shelhamer et al., 2017; Hafner et al., 2019; Lin et al., 2019; Bellemare et al., 2019; Yarats et al., 2021); such work has shown that learning embeddings plays a crucial role in determining the success of deep reinforcement learning algorithms. This motivates the development of further methods for learning embeddings, and raises the central question as to what properties of an embedding are beneficial in reinforcement learning.
A core role played by the embedding map & is to mediate generalisation of value function predictions across states; if the embeddings ((x) and <ly) of two states I, y are close in R"" then by virtuc of the regularity (or more precisely, Lipschitz contimuity) of the function approximator sb, the states z and y will be predicted to have similar values (Gelada et al., 2019; Le Lan al., 2021). Thus, a good embedding should cluster together states which are known to have similar behavioural properties, whilst keeping dissimilar states apart.
When learning value functions for reinforcement learning, how can one determine whether a rep- resentation allows learning generalization between similar states, but avoids over-generalization between dissimilar states? Metrics over the environment state space (state metrics for short) afford us a natural way to do so via value function upper-bounds, by taking & to be a metric embedding of d in R". To illustrate the effect of metrics on generalisation, consider two metrics d1 and d2 with the property that - V(y) S dI y) < d2(x, where V X - IR is a value function. The metric d2 offers less information about the similarity between a and than dj and may suffer from ander-generallization Thus, d1 is more useful metric for representation learning by virtue of being a lighter upper-bound. State metrics satislying such bounds have accordingly played an important role in representation learning in deep RL (Castro, 2020; Zhang et al., 2021; Castro et al., 2021). Contrastingly, a metric d that violates said upper bound (e.g. for some states a and y, d(x, y) < (V()) - V(y)l) may encourage dissimlar states to be mapped near each other, and can thus suffer from nverrgeneralization.
Bisimulation metrics (Desharnais et al., 1999; van Breugel & Worrell, 2001; Ferns et al., 2004) are a well established class of state metrics that provide such value function upper bounds: (V(x)- V < d(z, y). This translates into guarantee in the function approximation setting under the assumption that can be embedded into RT, and that, for example, &b is 1-Lipschitz continuous, yielding
[v(x) - V(v) ~ (v((()) - v(((1)) < [,(()) - Φ(x)) ~ d(z, v)
Bisimulation metrics, however, are expensive to compute, even for tabular systems, due to the fact that one needs to find an optimal coupling between the next-state distributions (Villani, 2008). Castro et al. (2021) overcame this difficulty by replacing the optimal coupling with an independent one, resulting in the MICo distance U which still satisfies the above-mentioncl value function upper bound. Interestingly, this distance is not a proper metric (nor pseudo-metric), but rather a diffuse metric (a notion defined by Castro et al. (2021)) that admits non-zero self-distances. The consequences of this are that, when co-learned with 1b, the resulting feature map é 2 + Rm is approximating reduced version of the MICo distance U", denoted as IT Unfortunately, this reduced MICo does not satisfy the value function upper bound, nor was it demonstrated to be
'A extreme example of this is to take dz(r, 3) = col(æ # v]. It is vacuously an boper- but completely uninformative, and will encourage state representations be mapped far apart from each other.
2

---

Published in Transactions Machine Learning Research (06/2023)
embeddable in R" (the space spanned by neural network representations). Despite demonstrating strong empirical performance, it remained unclcar whether the resulting method was theorctically well-founded.
Thus, while there have been empirical successes in using the object IT as a means of shaping learnt representations in RL, there are two open questions that naturally arise from the precoding discussion:
1. Is it reasonable to assume that I is embeddable into finiteddimensional Euclidean space?
2. Docs I1 satisfy some form of continuity, thus potentially explaining its utility in learning representations for RL?
In this work we address these questions directly by taking an alternate view of state similarity: via the use of kernels. More precisely, we introduce the concept of a positive-defiitte kernel on Markov decision processes
measure of behavioural similarity between states. This new perspective is valuable in itself, as it enables us to leverage reproducing kernel Hilbert space (RKHS) theory for better understanding of state metrics. We extract distance from this kernel, and prove its equivalence the reduced MICo distance. Through this perspective our work provides the following contributions:
We define new state distance, dis that is constructed from the Hilbert space distance of the RKHS (Section 3.1).
We demonstrate the equality of this new distance to the reduced MICo I of Castro et al. (2021) (Section 3.2).
We derive novel result demonstrating that d% (and IU by extension) do serve an upper bound to value function differences, with an additive component (Section 3.3).
We prove that d'. can be embedded into a fiite-dimennional Euclidean space with low distortion error (Section 3.1).
We demonstrate empirically that dF, performs comparably to MICo when used in a deep reinforcement learning setting (Section 4).
Before doing so, we provide review of some background material in the next section.
2
Background
We provide a brief overview of some of the concepts used throughout this work, and provide more detailed background the appendix.
2.1 Markov decision processes
We consider Markov decision process (MDP) given by (X,,,,,RR,), where X' is finite state space, A set of actions, P X' A + ( a transition kernel, and R X x A + PR) a reward kernel (Z is the set of probability distributions on a measurable set Z). We will write Pa P(x, a) for the transition distribution from taking action in state x, RS = R(x, a) for
3

---

Published in Transactions Machine Learning Research (06/2023)
the reward distribution from taking action a in state æ, and write rz for the expectation of this distribution. A policy π is a mapping X -> (AA). We use the notation Pr = E (alxx) Pz to indicate the state distribution obtained by following one step of policy x while in state a. We use R = =aEA म (a)a: R% to represent the reward distribution from a under т, and ry to indicate the expected value of this distribution. Finally, 7 E [0, 1) is the discount factor used to compute the discounted long-term return.
The value of a policy æ the expected total return an agent attains from following n, and is described by a function V* : + R, such that for each I E X
(*(x)= = E E Re Xo =
Here, Rg is the random variable representing the reward received at time step when following policy π starting at state An optimal policy Λ² is a policy which achieves the maximum value function at each state, which we will denote V*. It satisfies the Bellman optimality recurrence:
V (*(x)
max E aEA
Ro + (Xi) Xo x, Ao a)
2.2 The MICo distance
A common approach to dealing with very large, or even infinite, state spaces is via the use of an embedding o : RT, which maps the original state space into a lower-dimensional representation space. State values can then be learned on top of these representations: e.g. V v(((x)), where & a function approximator.
A desirable property of representations is that they can bound differences with respect to the function of interest (e.g. value functions). Le Lan et al. (2021) argued state behavioural metrics are a useful mechanism for this, as they can often bound differences in values: d(x, y) 2 The structure of the metric impacts its effectiveness: picking d(z, y) = (Rmax Rmiin) (1-7)- allows one to satisfy the same upper bound, but in a rather uninformative way.
Bisimulation metrics d (Ferns et al., 2004) are appealing metrics to use, as they satisfy the above upper bound, while still capturing behavioural similarity that goes beyond simple value equivalence (see Appendix C for more in-depth discussion of bisimulation metrics). Indeed, various prior works have built reinforcement learning methods based on the notion of bisimulation metrics (Gelada et al., 2019; Agarwal et al., 2021a; Hansen-Fstruch et al., 2022). Castro (2020) demonstrated that, with some simplifying assumptions, these metrics are Icarnable with neural networks; Zhang et al. (2021), Castro et al. (2021), Kemertas & Humentado-Armstronn (2021) and Kemertas & Jepson (2022) demonstrated they are learnable without the assumptions.
Castro et al. (2021) introduced the MICo distance, along with a corresponding differentiable loss, which can be added to any deep reinforcement learning agent without extra parameters. The added loss showed statistically significant performance improvements on the challenging Arcade Learning Environment (Bellemare et al., 2013), as well as on the DeepMind control suite (Tassa et al., 2018).
Our paper builds on the MICo distance, and as such, we present a brief overview of the main defi- nitions and results in this section. We begin with a result that introduces the MICo operator (TT), defines the MICo distance as its unique fixed point (U*), and shows this distance provides an upper bound value differences between two states. Before doing so, define the Lukaszyk- KonnkkKKrmoss
4

---

Published in Transactions Machine Learning Research (06/2023)
dislance (LK-distance), which is used in the definition of the MICo distance. A more thorough discussion of the LK-distance is provided in Appendix C.1.2.
Definition 1. Given two probability measures μ and v on a set X' and metric on X, the Lukaszyk Karmowski distance dLk (Lukaszyk, 2004) is defined as
drk(d)(u,V) = d(x, () x (x,
equivalently
dex(d)(1,
E X-p,Y~ Y).
Theorem 2 (Castro et al. (2021)). Given a policy n, the MICo operator TM : RXxx R given by (U) u) = Irt - rğl + y dzk(U)(PT, PT), has a unique fixed point U*, referred to the MICo distance. 2 Further, the MICo distance upper bounds the absolute difference between policy-value functions. That is, for x, y X, we have (F)
U UZ(ZU
The MICo distance was based on the n-bisimulation metric (d") introduced by Castro (2020); the key difference is that the update operator for d= uses the Kantorovich distance between probability measures instead of dEK (see Appendix C.1.1 for more details on the Kantorovich metric).
Castro et al. (2021) adapted the MICo distance to be used for learning state feature maps d. However, the authors demonstrated the features used for control were actually "reduction" of the diffuue metric approximant: this distance was dubbed the reduced MICo distance II"
Definition (Reduced MICo). The reduced MICo distance II is defined by
1 II (α.y) = (² (U= +U
Two immediate properties of I are that it is symmetric, and satisfies II x) = 0. However, it was unknown whether - satisfied the triangle inequality, as well as whether it was positive in general. One negative result shown by Castro et al. (2021) was that the value function upper bound does not hold for IV"
Proposition 4 (Castro et al. (2021)). There erists an MDP with v,y E X, and policy & where > IU*((,)))
- -r)
While Castro et al. (2021) demonstrated the strong empirical performance yielded by the reduced MICo distance in combination with deep reinforcement learning, Proposition 4 highlights that important properties for general state similarity metrics remain unknown for the reduced MICo. We pause here to take stock of what unknown regarding II
From purely metric perspective, it is unknown whether IV* is always positive (in general, applying the reduction opcrator II a positive function does not result in IIf being pos- itive), or whether TT satisfies the triangle inequality. These are important to understand so as to guarantee that the learned representations are well-behaved.
From the behavioural similarity perspective, it is not known whether - has any quan- titative relationship to the value function V", as Proposition demonstrates the standard value function upper bound does not hold.
"The distance dex is defined in Appendix C.1.2.
5

---

Published in Transactions Machine Learning Research (06/2023)
From practical perspective, it is unknown I is even embeddable in R".
In this work we seek to resolve these mysteries through the lens of reproducing kernel Hilbert spaces, which we introduce next (a more extensive discussion is provided in Appendix C.5).
2.3 Reproducing kernel Hilbert spaces
Let X' be a finite set, and define a function & X' X' + R to be a positive definite kernel if it is symmetric and positive definite:* for any {II,..., In E X, .ci,..., Cn) I,, we have that
n ΣΣ
cack( 13) 2 0.
i=1=1
We will often use kernel as shorthand for positive definite kernel. Given a kernel k on X, one can construct a space of functions Hy referred to a reproducing kernel Hilbert space (RKHS), through the following steps:
(i) Construct a vector space of real-valued functions on X' of the form {k(x,) :) : x E X}.
(ii) Equip this space with an inner product given by (k( H) k(x,)).
(iii) Take the completion of the vector space with respect to the inner product (
( He-
The Hilbert space obtained at the end of step (iii) is the reproducing kernel Hilbert space for k. It is common to introduce the notation p(z) == k(x,,) :), where : + H is often called the feature map, and p(x) is understood as the embedding of x in H. Note that we are using yp to represent the mapping of states onto a Hilbert space (e.g. y: X' Hx), which is distinct from the symbol e which we use to represent the mapping of states onto a Euclidean space (e.g. & X - RT)). One X' in Hy. Given probability distribution μ on X, one
can also embed probability distributions can define the embedding of μ,, p(u) C H4 as
((x) E [x(X)] = / p(x)dp(x). X~W
where the integral taken is a Bochner integral, 6 as we are integrating over H4-valued functions. The embeddings of measures into Hr allow one to easily compute integrals, one can show using the Ricsz representation thcorem that for f Hk, one has
J fdu (S, p(H))
These embeddings also allow us to define metrics on X' and (X) by looking at the Hilbert space distance of their embeddings.
9The general theory of reproducing kernel Hilbert spaces holds for much more general classes of sets (Aronszajn, 1950), but as mentioned earlier in the paper, our work focuses on MDPs with finite state spaces, so we present RKHS theory in the context of finite sets, allowing us to avoid some mathematical technicalities.
WWe remark that the definition of positive definite is not consistent across the literature. We follow the convention of the kernel methods community, and define function to be strictly positive definite if the inequality is strict unless Ci -..-= C, = O. In the linear algebra and optimization communities however, this is referred to as positive definite, and the definition provided is referred as positive semidefinite.
An RKHS can be allernately defined by choosing suitable set of functions and constructing the kernel & from this set, review this approach in Appendix C.5.2.
A generalization of the Lebesgue integral to functions taking values a Banach space, further details can be
found in Arendt et al. (2001).

---

Published in Transactions Machine Learning Research (06/2023)
Definition 5. Given a posilive definite kernel k, define ph as its induced distance:
px == -(())))
By expanding the inner product, the squared distance can be written solely terms of the kernel
( x) + k(y, v) (2(
We can perform the same process to construct a metric on 3 (X) using c: Definition 6 (Gretton et al. (2012)). Let & be a kernel on X, and & ( + Hx be as defined
above. Then the Marimum Mean Discrepancy (MMD) is pseudometric on ( defined by
MM = (1) {(v)]HHH.
A semimetric is distance function which respects all metric axioms save for the triangle inequality.
A semimetric space (X, p) is of negative type for all I1,..., In X, Cn,...;Cn such that > G = O, we have
(cp(a,, < 0.
Given a semimetric of negative type on X, we can define a distance on (X) known as the energy distance, defined as
1 E ( 2 X1,1X
(())(N))==
E X-pY
+ E [2(1)
Vi
where the pairs of random variables in each expectation are independent.
If p is of negative type, this guarantees that we have (p) v) Z 0 for all u, P Semimetrics of negative type have a connection to positive definite kernels, as shown in Sejdinovic et al. (2013): the induced distance squared p is semimetric of negative type, which say is induced by k. Conversely, a semimetric negative type p induces a family of positive definite kernels K parametrised by chosen base point xo E X::
K (x, = - (p(2, 2o) + p(z' xo) - x²)..
The relationship is symmetric, so that each kernel k Kp has p its induced semimetric. With this symmetry in mind, we call a kernel k and a semimetric of negative type an equivalent pair if they induce one another through the above construction. This equivalence does not only live in X however, as the following proposition shows that it lifts into I (X) as well.
Proposition 7 (Sejdinovic et al. (2013)). Let p) be equivalent pair, and let u, ( Then we have the equivalence
(MD E(p)(uvv).
The central takcaway of the equivalences proved in Sejdinovic et al. (2013) is that using metrics of negative type and positive definite kernels are two perspectives of the same underlying structure.

---

Published in Transactions Machine Learning Research (06/2023)
2.4 Prior work using RKHS for MDPs
We are not the first to consider using the theory of reproducing kernel Hilbert spaces in the context of Markov decision processes. Indeed, Ormoneit & Sen (2002) proposed to a fixed kernel to perform approximate dynamic programming in RL problems with Euclidean state spaces; a variety of theoretical and empirical extensions of this approach have since been considered (Lever et al., al., 2021). The use of fixed RKHSs for approximate dynamic programming in more general state spaces has been studied by Farahmand et al. (2016), Yang et al. (2020), and Koppel et al. (2021). In contrast, as we will discuss below, our work learns a kernel on the state space, which classifies states as similar based on their behavioural similarity in the MDP.
2016; Barreto et al., 2016; Domingues
3 Kernel similarity metrics
We take new perspective behavioural metrics in MDPs, through the use of positive definite kernels. We define a contractive operator on the space of kernels, and show that its unique fixed point induces a behavioural distance in reproducing kernel Hilbert space, and then prove that this distance coincides with the reduced MICo distance II, We then present new properties of IU* obtained through this perspective.
3.1 Definition
Given an MDP M AX, state similarity metrics which are variants of bisimulation generally follow the form
d(z,y) = di(2, + PW))
for states x, y in X. Here, d1 is a distance on X representing one-step differences between æ and y (c.g. reward difference), and d2 "lifts" distance on X' onto distance on P P(X;; thus, (p(d)(P(z))P())) represents the long-term behavioural distance between x and y. It is worth noting the similarity to the Bellman optimality recurvence introduced in Equation 1.
In this section we take a similar approach, except rather than quantifying the difference of states (metrics), we consider quantifying the similarity of states (positive definite kernels). Following this idea, we can define state similarity kernel k : X x X - IR as positive definite kernel which takes the following form:
k(z, = kı u) + ha (p))))
Similarly to the above expression for d, k kernel on X' which measures the immediate similarity of two states x and y, and 22 lifts a kernel on X' into a kernel on (X)).
We can now present candidate state similarity kernel. We follow Castro (2020) and Castro et al. (2021) in measuring behavioural similarity under a fixed policy, in contrast to measuring behaviour across all possible actions, as done in bisimulation (Ferns et al., 2004; 2011). Following this, we fix policy which will be the policy under which measure similarity. For the immediate similarity kernel, we will assume that supp(R) 1-,, and we set k (z, y) = 1 - 2 |r - ryl, which lies [0, 1]. This is reasonable measure of immediate similarity, as it is maximised when two states have identical immediate rewards, and minimised when two states have maximally distant immediate
"This assumption is purely for the clarity of presentation, and can be relaxed to assuming boundedness of reward and setting ky (z, y) Rmax Kmiin 1r2 r.
8

---

Published in Transactions Machine Learning Research (06/2023)
rewards. To lift a kernel k into kernel on (X), we can use the kernel lifting construction given in Guilbart (1979), and define (2(k)(,, = (x= Y) Combining these, we can define operator the space of kernels whose fixed point would be our kernel of interest.
Definition 8. Let H (X) be the space of positive definite kernels on X. Given π ((A),, the
kernel similarity operator Th : (x) - H(( (x) is
(k) = (1 b r ryy
+ X Y Py
[K(X,,
2
The lact that T indeed maps X (X) to X follows from the previous paragraph describing that each operator is a kernel, and that the sum of two kernels is a kernel (Aronszajn, 1950). We now present two lemmas which are necessary to conclude whether unique fixed point of T exists. Lemma 9. T is contraction with modulus y in llle.
Proof. Let ,1, k2 E (X); we can then write out ITE (k1) - TE (k2)
max TK (k1) 9) - T (22) (xx))xXxX
[x'('', Y')]
E Ey (x2( Y')
= max (xx))XxxX
X' Y
X' Yippy
=Y =Y max (x.))XXx
E XINPEYY'
1yy (X', Y") k2(X',, rn]
sr1lks - 122lo0.
Lemma 10. The metric space (X),1 |loo) is complete.
Proof. As we assume X' is finite, the space of functions RXX. is a finite-dimensionaal Euclidean vector space, and hence is complete with respect to the _ norm. It therefore suffices to show that H (X) is closed in Xxxx" We can consider a sequence (kn]n20 in XX)) which converges to E XXXX in || oo and show that k E (x). This is equivalent to showing that k is both symmetric and positive definite, which follows immediately from the fact that each ki is and the convergence uniform. Hence H (X) is closed with respect to lloos and thus complete.
With these two lemmas, we can now show that the required fixed point indeed exists. Proposition 11. There is unique kernel keT salisfying
kst (x, = 1 1- 1 1
(1-
1 - r - + XIPPAY
E
k (X', Y')].
Proof. Combining Lemma and Lemma 10, we know that the operator T is a contraction in a complete metric space. We can now use Banach's fixed point thcorem to obtain the existence of a unique fixed point, which is A.T
Having a kernel on our MDP now gives us an RKHS of functions on the MDP, which we refer to as Hy. Moreover, we have an embedding of each state into H.r given by x0 (x) kTT (x,-). Using this construction, we can define distance between states in X by considering their Hilbert space distance in Hk..
Definition 12. We define the kernel similarity metric (KSMe) as the distance function
(a = |1:0 45 (y)1
9

---

Published in Transactions Machine Learning Research (06/2023)
3.2 Equivalence with reduced MICo distance
We will prove a number of useful theoretical properties of dys in the rest of this section. But first, we demonstrate that dgs is equal to the reduced MICo (IIU*) from Castro et al. (2021). Given that Castro et al. (2021) left a number of unresolved properties of II"", this equality will be important for the remainder of the paper as it means the new theoretical insights we prove for dh also hold for ITV
Referring to Section 2.3, we have that dhs is the semimetric of negative type induced by k" We now demonstrate that dhe can be written as sum of reward distance and transition distribution distance, similar the form of the behavioural metries discussed in Section 3.1.
Proposition 13. The kernel similarity metric dhe satisfies
(x, y) 11 - -ry + (k7
Proof. To see this, we can write out the squared Hilbert space distance
(z,(1,)) (x) 4" (
(x, + +k 21 (x,
= =Ir Ill + + (0(PT)) He* + (PP))))((P)))))) - 2y((D(P=), ((PP)) ))
IIr rgl MMMD2 (PT)
where in the first equality we expanded the norm as in Definition 5, and in the second line we used
1s kxxx,) = X4.X/~PE
[XX,, X2]]
= 7 (P()))
Belore presenting the main result of this section (Theorem 15), we state necessary technical lemma. The proof is provided in Appendix A.
Lemma 14. For any measures μ,, v, and n > O, we have that
E X2 Y1,Y2-1/
(n1, + kn (Y1, Y2) - -2 (X1, Vi)l =
E XxxXamp Y1,Y2mu
Un(X1, Yi) - ( x2)
The next result proves the equivalence of dh and IU:" the implications of this result are that all of the properties proved for dis also apply to IV" This is significant, as it implies IT" can be incorporated into non-vacuous upper bound of value function diffcrences (Theorem 16), and is guaranteed to be embeddable in a finte-ddimensional Fuclidean space of appropriate dimen- sion (Theorem 19), addressing the two core theoretical questions raised in the introduction of this paper.
Theorem 15. For any x, E X, we have that (z, y) = II (x, y).
Proof. To begin, we will make use of the sequences (kn)n20, (Un)n20 defined by ki = 0, kn (kn), Un = 0, Un+1 = Th (Un). Since both Th and T are contractions, we know that kn + b.t and Un + " uniformly. To prove the statement, will show that for all > O and x, X, we have that
1 (U,(1, x) + Un(y.))).
kn x) kn.v)) 2k, 4) (n(
2
10

---

Published in Transactions Machine Learning Research (06/2023)
We can write out (n( x) kn Sy, -2k (2,
= -
+
E
(n(x,, + (Y,, Y22 1X,, K2)l
X2.X Y1,Y2mpp
Un(X1, 1 (1xx;,))-((0((xxxx)))))))00 x + (+)
Ir
ry
E
X1.X2~P
Y1,Y2~pp
(n _ (Un(z, + Un(,,
where (+) follows from Lemma 14. Since (km)m20 and (Un)n20 both converge uniformly, we can take limits and conclude that
1 (U"(2,z) + U (U* +U*())))) v)) II"" (x,
dh () = k-t (x. x) ktt (v.3) 21 (x,1) U (z,
3.3 An additive value function upper bound
Proposition 4 asserts that IU' and hence des does not upper bound the absolute difference in value functions. However, the kernel perspective allows us to show that it satisfies upper bound with an additive constant. For x E X we introduce the notation
[rxy - Xxy
E ('
E X
Intuitivcly, (x) is the expected absolute reward difference in two trajectorics from x, where the trajectories are coupled for the first n steps, and proceed independently for the final (n + 1)th step. With this quantity, we present the following theorem.
Theorem 16. For any y E X, we have
VT(() V (3)) S " v) + Σ ('(A(()) + ATO)). n20
2
Proof. To begin, we will make use of the sequences (km)m20s (Vm)220 defined by km = 0, km Th (kim), Vm 0, Vm+1 = T (Vm). Since Tg and T are both contractions, know that km + k. and Vm + V uniformly. We will refer to the semimetric equivalent to the mth kernel iterate as dm: 62, y) = km x) + kim (v. 2km (x, y). We will now use induction to prove that for all m,
we have that
1 M (A)()) + (z)))
VV (I) - Vn) dm (x. y)
2
The base case m 0 is immediate, as the left hand side is identically 0. We can now assume the induction hypothesis, and write out
Vm+i (x) Vm++ (3)
[Vm(('))]
c x + E X'
(x)] -
rr +
E yimpp
11

---

Published in Transactions Machine Learning Research (06/2023)
<
1r
Tyl
E X'=PE P'mpp
Vmm(X') Vm((r))
m
(X)) ( AT(P1)
$
1
dm Y*) + Σ
X x'~PEYYNNP ~wp
2 n=
m+1
Y
EB X' PP
[d ,Y'] +
>" ( (T) + A7(1))
n=1
1r ryy
[dm Y')] +
E
xx + 1rgr 75.1 |x3
X'>P P PP
2 X'X">PP Y'y""pp
m++
+ 2
Σ
7" (4 (2) + Ax(1)
n=1
+ 1 mi
1r - -ry +7
[X',X', Y')l
Σ + +
X' P
2 n=
m+1
dm+1((,1) +
7 (A + A71)))
n=
where we used Ex-ep (X))) = (z). We note that the sum 1 -m= 00==0"(A4 ("(A7()) + Ag(i)) is
almost surely finite, as (x))) < 1 almost surely (since we assume supp R [ 1]), that
Ti
(x) + + S Σn
1 1-7
n=
==0
With this theorem, it is apparent that the amount by which the bound is broken is controlled by the amount of dispersion in reward coming from the transition probability function PT A standard tool to measure the dispersion a measure on R the variance, which is not directly applicable in this setting as p maps to measures on X. However, we can map each state E X to a real value ra, and use this to apply the variance. With this motivation, we define the reward variance of pat for x E X as
Varx(P)) = E X
(xx -
E
X'
With this definition in mind, we can now demonstrate that the maximal reward variance of an MDP controls the amount the value function difference upper bound is violated.
Proposition 17. Suppose there erists 0² E IR such that for each x E X, VarR(PF) S 0². Then for every E X and k 2 0 we have that (x) < /2a, and in particular
V20
(VT()- - < II + 1-7
Proof. We first note that it suffices to show that for any x we have that AT(x) S /2a, since for any > 1 we have (x Ex (x)))
[ - [
(X)()))
E NawPa
E
X'~(PF)a-1
X.
n1
X
X
12

---

Published in Transactions Machine Learning Research (06/2023)
[ - r [8
[
E
X. (P=(
(x),
where for clarity we used the notation Xm to denote random state after taking m steps in the trajectory.
We can first recall an equivalent formula for variance as Var(u) Ex,Y~=IIX+ Y/9. Using this and Jensen's inequality, we have that for any x E H.
20
E Y'pp
|r rÝ.19
X' T.
E X'>Pe 'pp
|| -
Taking the square root of both sides we obtain that (7 V20, which combined with the above completes the proof.
3.4 Distortion error bounds on Euclidean embeddings
While we consider various distance spaces (X,d) on the ground states X of the MDP, in practice we typically work with a representation (ő(x)) E X) E (R""i of the state space, from which values can subsequently be predicted with neural network function approximation. This highlights an important issue in moving from the study of behavioural metrics abstract mathematical objects to tools for shaping neural representations, which has received relatively little attention so far. Namely, does there exist an embedding & X' + R" such that [|ő(x) - <(y)ll = d(x, v) for all y E X? Stated more conciscly, we may ask whether the metric space (X, embeds into the Euclidean space R"; this is an instance of the core problem of study in the field of metric embedding theory (Deza & Laurent, 1997: Matousek, 2013), and there are several central results from this field that can be employed to cast light on the embeddability of behavioural metrics.
As an initial note of caution, Schoenberg (1935) gives a precise characterisation of which finite metric spaces can be embedded into Euclidean space, consequence of which is that many finite metric spaces cannot be embedded into Euclidean spaces of any dimension. A potential upshot is that attempting to learn exact embeddings of behavioural metrics may not be possible, even in small-scale settings. However, the kernel perspective taken earlier in the paper allows us to make immediate progress on the question of cmbeddability in the specific case of the reduced MICo metric. In particular, since Theorem 15 establishes that the reduced MICo metric can be embedded into the Hilbert space H4s, we can deduce the following result.
Corollary 18. The reduced MICo metric IT can be embedded into the space |R| with squared Euclidean metric.
Proof. From Theorem 15 and Definition 12, we have that IT,) - ( for all E, X. Since H4r is a Hilbert space of dimension at most X, there is isometry sb Hyr -> I² for some k < |X). The composition zi o T therefore embeds - exactly in IR* under the squared Euclidean metric.
In many practical settings, the dimensionality of the space Rm into which the representation func- tion maps is generally taken to be much smaller than | itself for a variety of reasons, in- cluding computational tractability and generalisation properties of the function approximator. It
13

---

Published in Transactions Machine Learning Research (06/2023)
is therefore pertinent to ask whether the guarantee established in Corollary 18 can be improved to guarantee cmbeddabilty in a lower-dimensional Euclidean space. While cxact embeddability in lower-dimensional spaces is not always possible, the Johnson-Lindenssraass lemma (Johnson & Lin- denstrauss, 1984) can be used to establish the following result, which shows that lower-dimensional embeddings of I are possible, as long as we are prepared to accept a certain level of distortion of the original metric.
Theorem 19. Let π be a policy, and ~e be the equivalence relation on X defined by I ~ = (x, O. For any given e E (0,1), if m 2 8log(1\/~al/ee,, where X/~>x denoles the quotient set with respect to the equivalence relation ~a, then there caists an embedding @ : X - R such that for all z. y X,
(1 - dFo S 1 o(u) < (1 + +5 dko(
or equivalently,
(1 - E) I1 (x, (I,
S 1d(x)) a(u) < (1 + & (z,
Proof. We recall that the RKHS Hyr is defined by the formula
HA. = span (k),,) : x EE
where we do not nced to take the completion, as there are only finitely many x C X, hence Hyr is finite dimensional inner product space, and therefore complete. HAr is in general semi inner product space, and to resolve this we take the quotient H4₂ /~x. The set of equivalence classes of ~ is equivalent to the kernel of the seminorm || Il and in particular is a miiee-iimeniionll vector space, so H is a proper inner product space. Let be an orthonormal basis for HAr H We will begin by showing that (Hxr /~pm/~> ll || ) can be isometrically embedded into (R., 112). To see this, let I: Hea /~= Ie' be defined by
dim (Hz=/~H)) and let f1, f
I(f)) - ejjevvjeel ej
Σ o55 JELI
IajI(f)) JEl1
We can now see that I is a Hilbert space isomorphism: for all i,j E [1]
(fv. = (I(F))
Letting n | we can enumerate X/~~ as Fl,..., nn and from the above isometry we know that f0i,..., } C X' can be embedded as {I((> (z1)),... II,,"(,))) Let us use the notation yk (zx)) as the embedding of 2% into R for brevity.
(αn))} C R with no distortion.
We can now apply the a linear map f R + Rm such that for any i.j E [m],
8 lemma: for any & E (0, 1), m 2 Ee log(n), there exists
(1 <) ll 1 <
(lf f < (1 + +)) ll 13
The desired statement now follows from rearranging the formula for n and using the isometry
1y: vi = ||Z({" (2:)) - I[pp" (x;))) (x:) (x;) dhs HI (æi, xz);
and taking the map o: X/~0x Rm to be the composition o T*
14

---

Published in Transactions Machine Learning Research (06/2023)
Remark 20. The spaces and maps used in the previous proof can be summarized in the following commutative diagram:
X 8/~
m
8
Hk.
I
R
Remark 21. Observe that we con improve over the result in Corollary 18 if we accept an error c, so long as log( < 8/88 in the sense that the result concerns Shuer-dimenssooal embedding.
3.5 Learnable parameterizations
Despite the theoretical appeal of the discussed distances, one of the motivating forces for our work is their applicability to online reinforcement learning with neural networks. Specifically, we are interested in using the derived metrics as means to learn embeddings ø that can speed up learning value functions for control. Towards this end, Castro et al. (2021) proposed approximating the diffuse metric U via Uw, parameterized as follows:
(z) (ow + 30(d (w()))
Uw (w y)
where is the learned representation parameterized by w, (()()), p()) is the angular distance between vectors Φ(x) and (vy), and B E (0) is a hyperparameter that weighs the importance of the angular distance.
A peculiar aspect of their method is that this parameterization is approximating the diffuse metric, yet when using the representations ow for control, they are implicitly making use only of the weighted angular distance, which can be viewed the reduced MICo distance:
(0)) R IZ,)
Although producing strong empirical performance, this results in somewhat awkward dynamic: the metric space on which the MICo loss is being optimized is different than the metric space where the representations used for control exist. Given the equivalence demonstrated in Scction 3.2, we can alleviate this by learning kernel between representations in the same inner product space used for control.
We parametrisc the kernel km (x, y) using the natural inner product on RT, written as
(x. =
(2)
From this parametrisation, we can convert the kernel update operator T into a learning target in a similar manner as was done by Castro et al. (2021). Specifically, given two transitions (I, (r, a') and
(y, Ty. y') sampled from the replay buffer, we can define T5 (r x', Ty, v') = 1- 1---/r=--- f1rr- ( (a',, v/). Here, w is separate copy of the parameters w that are updated less frequently (as suggested by Mnih et al. (2015) and used by Castro et al. (2021)). Our kernel-based loss is then:
+7k
(w) -E -E
(T ,y. - ho (x. v))
(3)
15

---

Published in Transactions on Machine Learning Research (06/2023)
Note that this squared semi-gradient loss is taken directly from what was used by MICo (Castro et al., 2021), which was based on the loss originally used by DQN (Mnih et al., 2015). Further details on theoretical properties of this loss in the general context of reinforcement learning can be found in Bertsekas & Tsitsiklis (1996), and discussion in the specific context of metric learning is given by Castro et al. (2021).
With this parametrisation, the KSMe distance between two points (x) and (v) is
k2, x) + (v. (z. = + l ((0w (w))
(())
= =1]=(() - (1))
That is, the parametrised KSMe distance is exactly the Fuclidean distance between the embeddings. This parametrisation is supported by the theory of Section 3.4, as we are approximating the Hilbert space HAr with the Hilbert space (IR", -12),, which can be summarized as:
||0(z)]12 = hiw (x, x) R (=x = -1xx ( ((((z) - <(v)13 = dis (x, v) = (2, = 1110=(()) - 40 (1))
4 Empirical evaluations
Having demonstrated the theoretical equivalence between d% and IIU", in this section we perform an empirical investigation to validate their equivalence in practice, and return to our original motivation of using state metrics for representation learning- We do so in small domains where we can compute these distance exactly (Section 4.1), and in more complex domains where we use neural networks to approximate the distances (Section 4.2). All the code for these evaluations are hatp://rrreerccoooogoeeeeeeeeeee /tree/ master/ksme.
available at
4.1 Empirical insights into KSMe properties
To investigate the bounds discussed in Section 3.3, we empirically investigate the bounds through the use of Garnet MDPs, as done in Castro et al. (2021), where an empirical analysis was conducted to investigate to what degree di (then referred to as IIU" violated the value function upper bound (x)- (z)-V* (v)1 was negative). Given Proposition 17, we can now conduct more precise study: knowing that the reward variance VarR(P*) controls the amount by which (2, y) can be greater than [I< (T()),, we plot the bound as VarR(P") changes. We plot both the minimum and average signed difference d(z, y) (<* VT(y)) for d = {d%, U*}. As can be scen in Figure 1, although df, can violate the upper bound (left plot), on average across the Garnet MDPs it is more informative of the true value difference than U and d% are; this result is consistent with the findings of Castro et al. (2021).
(e.g. how often di (z. VV
Before proceeding to evaluating di. in a more complex domain, it is worth taking stock of the implications of Figure 1. When the upper bound property is violated (see left plot), it could result in dissimilar states being mapped closely together; this could lead to over-generalization, as discussed the introduction above. However, the right plot suggests that in practice this does not happen very often, and is in fact more informative than dA (for which the upper bound property is not violated). Further, the amount of wver-generalization one could suffer is proportional to the reward variance of the environment. When taken together, these results suggest di can be an effective way of shaping RL representations during learning.
16

---

Published in Transactions Machine Learning Research (06/2023)
U
d
dksme
2.0
1.5
min(d(s, t) (s)
1.0
10"3
(2 mayg
0.5
10-4
0.0
0.
0.4 0.6 0.8
1.0
0.0
0.2
0.4 066 0.8
Reward std. dev.
Reward std. dev.
Figure 1: The minimum (left) and average (right) difference between the absolute value function difference [V*(x) V (v) and U (Castro et al., 2021), d= (Castro, 2020), and dis. across 17K random MDPs of varying state and action sizes, as the reward standard deviation VarR(P") is increased from 0 to 1.
4.2 Large-scale evaluation of KSMe
We adapted the code provided by Castro et al. (2021) to approximate KSMc instead of MICo, incorporating our new loss in the same way. Specifically, we use RL agents that estimate Q values by composing a learned m-dimensional representation du X RM (parameterized by w) with a learned value approximator 4/ IRm + R (parameterized by 0): Q(a,)) = (z))
Given two states and y; the similarity between their representations is expressed via the inner product of their embeddings (as detailed in Equation (2)):
la y) = (Ow (v)),
We then replace the MICo loss of Castro et al. (2021) (CMICO) with the KSMc loss:
(KSMe(W) -Etg.r. [TT x', ry. hew (x,)))))
As done by Castro et al. (2021), the value approximator is trained with the standard temporal difference loss of each agent. In our evaluation, we compared the use of LKSMe with LMICo on the JAX agents provided by the Dopamine library (Castro et al., 2018): DQN (Mnih et al., 2015), Rainbow (Hessel et al., 2018), QR-DQN (Dabncy et al., 2018b), IQN (Dabney et al., 2018a), and M-IQN (Vieillard et al., 2020).. We keep all hyperparameters unchanged from those used by Castro et al. (2021).
Due to the computational expense of running these experiments, we sclected four representative Atari 2600 games from the ALE suite (Bellemare et al., 2013) which, we felt, covered the varying
Note that these the agents which MTCo originally evaluated.
17

---

Published in Transactions Machine Learning Research (06/2023)
700
IQM Human Normalized Score
600
500
400
300
Agent
DQN
200
M-QQN
IQN
Rainbow
100
QR-DQN
0
KSMeloss
25
50
75
100
125
150
175
200
Number of Frames (in millions)
Figure 2: Interquantile mean (Agarwal et al., 2021b) comparison of adding KSMe versus MICo on all the Dopamine (Castro et al., 2018) value-based agents, aggregated over independent runs on four representative games.
dynamics between the original agents and those with the MICo loss. We ran 5 independent seeds for each configuration. In Figure 2 plot the Interquantile mean (IQM) values which aggregates human-normalized performance across all runs; this metric was introduced by Agarwal et al. (2021b) a more robust statistic to compare algorithmic performance.
As can be seen, the performance of KSMe is similar to that of MICo, consistent with Theorem 15, which proved their equivalence. Since no hyperparameter optimization was performed for KSMe, it is quite possible the KSMe parameterization can provide empirical gains over MICo. We leave this exploration for future work. In Appendix D we provide the learning curves for each separate agent/ game combination.
5 Discussion
The empirical results in Section 4 provide experimental validation into the theoretical results of Section 3. Figure 1 follows the trend suggested by Proposition 17, as the worst case difference between the value function difference and di increased approximately linearly with respect to the reward standard deviation. The average gap provides an interesting perspective however, as it demonstrates that on average, as the variance increases, the size of the gap is much larger for UT and d than for d=.- Having features which reflect the underlying value function critical for value-based reinforcement learning, and we hypothesize that this contributes to the empirical success achieved by using KSMe (equivalently, the reduced MICo). As demonstrated in Figure 2, both KSMe and MICo achieve similar empirical performance, which is expected as the underlying distance being learnt is the same. The differences in performance is then a result of lcarning distances opposed to kernels in the neural network.
These results also provide further explanation why KSMe (equivalently the reduced MICo) appears to achieve stronger success than bisimulation in deep reinforcement learning settings (the two distances were compared in Castro et al. (2021), where bisimulation was learnt using DBC (Zhang
18

---

Published in Transactions Machine Learning Research (06/2023)
et al., 2021)). Two possible reasons coming from this work are (i) tighter relationship to the underlying value function and (ii) superior embeddability in neural networks. The hypothesis (i) is supported empirically by Figure 1, and theoretically by the fact that in general (z, y) (x, y). We believe that this tighter bound leads to improved performance because distances which correctly approximate the value function difference between states allow for (rraighfforward value- based learning. Secondly, the fact that KSMe comes from Hilbert state structure allows efficient embeddability into low-dimension Euclidean space, a very important concept in deep settings, as this is exactly what neural networks aim to accomplish. Theorem 19 provides result guaranteeing this is possible. We note that is not clear whether a similar result for bisimulation metrics is possible, as the Kantorovich metric cannot be approximated in Euclidcan spaces with low distortion in general (Peyré & Cuturi, 2019).
6 Conclusion
In this work have taken kernel perspective learning representations in reinforcement learn- ing, and introduced a state similarity kernel on Markov decision process state spaces. This kernel naturally induces a distance, which we proved was equal to the reduced MICo distance (Castro et al., 2021). This allowed to perform theoretical analysis of the reduced MICo distance which was previously lacking, and answer important questions such as its metric properties and connection to value functions. We then analyzed a previousl-uucoosiderre question: how well the distance itsclf can be approximated in Euclidean spaces, and prove a bound demonstrating embeddability. We then adapted the loss introduced in Castro et al. (2021) to learn the kernel. While the distance learnt is theoretically equivalent to theirs, our parametrization is theoretically grounded as the neural network embeddings are an approximation to kernel Hilbert space embeddings. To the best of our knowledge, this is the first work which studied how well given state similarity metric can be approximated through a neural network, and provided bounds on the incurred error. These results provide theoretical grounding for the reduced MICo distance, and our kernel perspective analysis may be used in future work to analyze related distances.
It is worth noting that by focusing on the upper-bound properties of behavioural metrics we are providing assymetrical guarantees. Namely, while they can guarantee similar states will have similar values, they do not guarantee that dissimilar states will have dissimilar values. It would thus be valuable to investigate further why these metrics can provide such strong performance despitc the asymmetrical guarantees.
19

---

Published in Transactions Machine Learning Research (06/2023)
Acknowledgements
We thank Gheorghe Comanici for detailed feedback on an earlier version of the paper, and the anonymous TMLR reviewers and action editor Gergely Neu for helping us strengthen our submis- sion.
We would also like to thank the Python community (Van Rossum & Drake Jr, 1995; Oliphant, 2007) for developing tools that enabled this work, including NumPy (Harris al., 2020), Matplotlib (Hunter, 2007) and JAX (Bradbury et al., 2018).
Author Contributions
Authors listed in alphabetical order, and individual contributions listed below.
Pablo Samuel Castro helped give direction to the work, revised the thcoretical results, wrote the code, ran the deep RL experiments, and contributed to writing the paper.
Tyler Kastner proved most of the theoretical results, ran the toy experiments, and contributed to writing the paper.
Prakash Panangaden helped give direction to the work, revised the theoretical results, supervised Tyler, and contributed writing the paper.
Mark Rowland helped give direction to the work, revised the thcoretical results, reviewed the code, and contributed to writing the paper.
20

---

Published in Transactions Machine Learning Research (06/2023)
References
Rishabh Agarwal, Marlos C. Machado, Pablo Samuel Castro, and Marc G. Bellemare. Contrastive behavioral similarity embeddings for generalization in reinforcement learning. In In Proceedings of the Ninth International Conference on Learning Representations, 2021a.
Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron Courville, and Mare G. Bellemare. Deep reinforcement learning at the edge of the statistical precipice. In Advances in Neural Information Processing Systems, 2021b.
Wolfgang Arendt, Charles Batty, Matthias Hieber, and Frank Neubrander. Vector-calued Laplace transforms and Cuuchy problems. Springer-Vetie Verlag, Jan 2001.
Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American mathematical sociely, 6833):337-400 1950.
Leemon C. Baird. Residnal algorithms: Reinforcement learning with function approximation. In Proceedings of the International Conference on Machine Learning. 1995.
André MS Barreto, Doina. Precup, and Joelle Pineau. Practical kernel-based reinforcement learning.
The Journal of Machine Learning Research, 17(1):2372-25) 2241,,441 2016.
Mare G. Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The Arcade Learning Envi- ronment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-277 279, June 2013.
Marc G. Bellemare, Will Dabney, Robert Dadashi, Adrien Ali Taiga, Pablo Samuel Castro, Nico- las Le Roux, Dale Schuurmans, Tor Lattimore, and Clare Lyle. A geometric perspective on optimal representations for reinforcement learning. In Advances in Neural Information Process- ing Systems, 2019.
Dimitri P. Bertsekas and John N. Tsitsiklis. Newro-dymamic programming. Athena Scientific, 1996.
Richard Blute, Josée Desharnais, Abbas Edalat, and Prakash Panangaden. Bisimulation for labelled Markov processes. In Proceedings of IEEE Symposium. On Logic In Computer Science, 1997.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wandernan-Milne, et al. Jax: composable transformations of python+ numpy programs. 2018.
Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic Markov decision processos. In Proceedings of the AAAI Conference on Artificial Intelligence, 2020.
Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Mare G. Bellemare. Dopamine: A Research Framework for Deep Reinforcement Learning. arXiv, 2018.
Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland. MICo: Learning improved representations via sampling-basee based state similarity for Markov decision processes. In Advances in Neural Information Processing Systems, 2021.
Gheorghe Comanici, Prakash Panangaden, and Doina Precup. On-the-fly algorithms for bisim- ulation metrics. In Proceedings of the International Conference on Quantitative Evaluation of Systems, 2012.
21

---

Published in Transactions Machine Learning Research (06/2023)
Will Dabney, Georg Ostrovski, David Silver, and Remi Munos. Implicit quantile networks for distributional reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1096-1105. PMLR, 2018a.
Will Dabuey, Mark Rowland, Marc G. Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2018b.
Peter Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5(4):613-62) 624, 1993.
J. Desharnais, A. Edalat, and P. Panangaden. Bisimulation for labeled Markov processes. Infor- malion and Compulation, 179(2):163 193, Dec 2002.
Josée Desharnais, Vineet Gupta, Radha Jagadeesan, and Prakash Panangaden. Metrics for labeled Markov systems. In Proceedings of the International Conference on Concurrency Theory, 1999.
Michel Marie Deza and Monique Laurent. Geometry of cuts and metrics, volume 2. Springer, 1997.
Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko. Kernel-based reinforcement learning: A finite-time analysis. In Proceedings of the International Conference Machine Learning, 2021.
A.m. Farahmand, M. Ghavamzadch, Cs. Szeposvári, and S. Mannor. Regularized policy itcra- tion with nonparametric function spaces. The Journal of Machine Learning Research, 17:1 66, January 2016.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite Markov decision processes. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2004.
Norm Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden. Methods for com- puting state similarity in Markov decision processes. In Conference on Uncertainty in Artificial Intelligence (UAI), 2006.
Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous Markov decision processes. SIAM Journal on Computing, 40(6):1662-1114, 2011.
Chelsea Finn, Xin Yu Tan, Yan Duan, Trevor Darrell, Sergey Levine, and Pieter Abbeel. Learning visual feature spaces for robotic manipulation with deep spatial autoencoders. arXiv, 2015.
Carles Gelada, Saurabh Kumar, Jacob Buckman, Ofir Nachum, and Mare G Bellemare. Deep- MDP: Learning continuous latent space models for representation learning. In Proceedings of the International Conference on Machine Learning, 2019.
Corrado Gini. Variabilità e mutabilità: contributo allo studio delle distribuzioni e delle relazioni statistiche. Studi economico-giuridio pubblicati per cura della facoltà di Giurisprudenza della R. Università di Cagliari. Tipogr. di P. Cuppini, 1912.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in Markov decision processes, Artificial Intelligence, 147(1-2):163 2203,222,,1222 2003.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-77) -73,, 2012.
22

---

Published in Transactions Machine Learning Research (06/2023)
C. Guilbart. Produits scalaires sur l'espace des mesures. Annales de I'L..... Probabililés et slatis- tiques, 15(1):333-33 - 1979.
Danijar Hafner, Timothy Lillicrap, lan Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In Proceedings of the International Conference on Machine Learning, 2019.
Philippe Hanscn-Estruch, Amy Zhang, Ashvin Nair, Patrick Yin, and Sergey Levine. Bisimulation makes analogies in goal-conditioned reinforcement learning. In Procerdings of the International Conference on Machine Learning, 2022.
Charles R. Harris, K Jarrod Millman, Stéfan Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, et al. Array programming with numpy. Nature, (0557885):377-223 362, 2020.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining Improvements in Deep Reinforcement lcarning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
John D Hunter. Matplotlib: A 2d graphics environment. Computing in science & engincering, 9 (03):90-95, -5, 2007.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Leibo, David Silver, and Koray Kavukcuogln. Reinforcement learning with unsupervised auxiliary tasks. In Proceedings of the International Conference on Learning Represenlations, 2017.
William Johnson and Joram Lindenstrauss. Extensions of Lipschitz maps into a Hilbert space.
Contemporary Mathematics, 26:189-2088 01 1984.
Lconid V. Kantorovich and G. Sh. Rubinshtcin. On a space of totally additive functions. Vestnik Leningrad. Univ, 13(7):52 59, 1958.
Mete Kemertas and Tristan Aumentado Armitttod....tt.o...... Towards robust bisimulation metric learning. Advances in Neural Information Processing Systems, 2021.
Mete Kemertas and Allan Douglas Jepson. Approximate policy iteration with bisimulation metrics. Transactions on Machine Learning Research, 2022.
George Konidaris, Sarah Osentoski, and Philip Thomas. Value function approximation in rein- forcement lcarning using the Fourier basis. In Proceedings of the AAAI Conference on Artificial Intelligence, 2011.
Alec Koppel, Garrett Warnell, Ethan Stump, Peter Stone, and Alejandro Ribeiro. Policy evaluation in contimuous mdps with efficient kernelized gradient temporal difference. IEEE Trans. Autom. Control., 66(4))1856-16) 1863,,166,,11111 2021.
Sascha Lange and Martin Riedmiller. Deep auto-encoder neural networks in reinforcement learning. In Proceedings of the International Joint Conference on Neural Nelworks, 2010.
Kim G. Larsen and Arne Skou. Bisimulation through probablistic testing. Information and Com- putation, 94:1-28, 1991.
23

---

Published in Transactions Machine Learning Research (06/2023)
Charline Le Lan, Mare G. Bellemare, and Pablo Samuel Castro. Metrics and continuity in rein- forcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
G. Lever, J. Shawe-Taylor, R. Stafford, and Cs. Szepesvári. Compressed conditional mean em- boddings for modcl-basod reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2016.
Xingyu Lin, Harjatin Baweja, George Kantor, and David Held. Adaptive auxiliary task weighting for reinforcement learning. In Advances in Neural Information Processing Systems, 2019.
Sridhar Mahadevan and Mauro Maggioni. Proto- functions: A Laplacian framework for learn- ing representation and control in Markov decision processes. Journal of Machine Learning Re- search, 8:2169 2231, Dec 2007.
Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013.
Stephen G. Matthews. Partial metric topology. Annals of the New York Academy of Sciences, 728 (1):183 197, 1994.
Robert Milner. A Calculus for Communicating Systems, volume 92 of Lecture Notes in Computer Science. Springer-Verlag, 1980.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattic, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):552-558 2015.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, 29(2):429-44 443,443-4444,4 1997. ISSN 00018678.
Travis E. Oliphant. Python for scientific computing. Computing in Science & Engineering, 9(3): 10 20, 2007. doi: 10.1109/MCSE.2007.55
Dirk Ormoneit and Šaunak Sen. Kernel-based reinforcement learning. Machine Learning, 49(2-3) 3): 2002.
Prakash Panangaden. Labelled Markov processes. Imperial College Press, 2009.
David Park. Title unknown. Slides for Bad Honnef Workshop on Semantics of Concurrency, 1981.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and Trends@ Machine Learning, 11(5-6):355-60) 2019.
Svetlozar Rachev, Lev B. Klebanov, Stoyan V. Stoyanov, and Frank J. Fabozzi. The method of distances in the theory of probability and statistics. Epringer-Verlag, 2013.
Frigyes Riesz. Sur une espèce de Géométric analytique des systèmes de fonctions sommables. Gauthier- Villars, 1907.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathe- matical Statistics, 22(3):400 407, 1951.
24

---

Published in Transactions Machine Learning Research (06/2023)
Walter Rudin. Functional Analysis. Tata McGraw-Hilll 1974.
Isaac J. Schoenberg. Remarks to Maurice Fréchet's article"Sur la definition axiomatique d'une classe d' d'espace distances vectoriellement applicable sur I'espace de Hilbert". Annals of Mathe- matics, pp. 724 724-732, 1935.
Bernhard Schölkopf, Alexander J. Smola, and Francis Bach. Learning with kernels: Support vector machines, regularization, optimization, and beyond. The MIT Press, 2018
Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-based and RKHS- based statistics in hypothesis testing. The Annals of Statistics, 41 (5): 1263-22911 2013.
Evan Shelhamer, Parsa Mahmoudieh, Max Argus, and Trevor Darrell. Loss is its own reward: Self-supervision for reinforcement learning. In Proceedings of the International Conference on Learning Representations (Workshop Track), 2017.
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 2018.
Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Tas Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, and Martin Riedmiller. DeepMind control suite. arXin, 2018.
Franck van Breugel and James Worrell. Towards quantitative verification of probabilistic systems. In Proceedings of the International Colloquium on Aulomala, Languages and Programming, July 2001.
Guido Van Rossum and Fred L Drake Jr. Python reference manual. Centrum voor Wiskunde en Informatica Amsterdam, 1995.
Nino Vieillard, Olivier Pietquin, and Matthieu Geist. Munchausen reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS 2020), 2020.
Cédric Villani. Optimal transport: Old and new, volume 338. Springer Science & Business Media, 2008.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael Jordan. Provably efficient reinforcement learning with kernel and neural function approximations. In Advances in Neural Information Processing Systems, 2020.
Denis Yarats, Amy Zhang, Ilya Kostrikov, Brandon Amos, Joelle Pineau, and Rob Fergus. Im- proving sample efficiency in modcl-free reinforcement learning from images. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Shlomo Yitzhaki. Gini's mean difference: superior measure of variability for non-normal distri- butions. Metron International Journal of Statistics, LXI(2):285-311 2266,,,,,, 2003.
Amy Zhang, Rowan McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Invariant repre- sentations for reinforcement learning without reconstruction. In Proceedings of the International Conference on Learning Representations, 2021.
Szymon Lukaszyk. A new concept of probability metric and its applications in approximation of scattered data sets. Computational Mechanics, 33:299-330 -004, 03 2004.
25

---

Published in Transactions on Machine Learning Research (06/2023)
A Extra technical results
For the following two lemmas, we will make use of the sequences (km)n20, (Un)n20 defined by kn = 0, kn = (kin,, Un = 0, Uni = (Un).
Lemma 22. For any point (21, y1, X2,,, and 2 0, we have that
E Xi~NP= 21 .Yg~P y/~P
Kn (X1, X2) ki Yg) 2kn (X,,Y))
x2 1/1 92
E X/~PE , 2pp 22
Un(X), 2
(Un(X), + Un((, Y3))
V/-PT 41 122
Proof. We show this by induction. Both sides are identically zero at n = 0, so we set n 2 0 and assume the induction hypothesis. We can then write out.
1kn- I X2) + Ann1(1( Y2) 2k ( (X),)))
y Timpy 21
|1', - -v 1 -1( - rxx + 10 -1%a
Xi>PE .2PPP
y/-Pp 81 1/~PP U/
+
kx(X", + kn (x,",,,
2k 2%, (X",
xP x1 x pm
11" ppp. 87
Y2" -pp
E
11%, rx.
2 (1r%
1
xx,11 + 1/% r9,1))
Xf .GNPP
1/ 1/>PT X2mPp x1
+
E ~pa x X3 pp
hn (x', + (YT" 2k, (X), Y1")
Xj-Pp 2 .3p 2/2 1/-PT m1 1/3 1/-
Y1" ~p Y2 pm
x1
%/2
E. Ximpp, .3uup 1/-pp Y2uPi
(1rx. - 1
2 (1rx xx
+ 1, -1%11)
02
+
E
E X x1 X
Un(X Yi") (U', ("')","") + U...".
Xi-PI p1 XGrpp Y/-Ps 21 Y/-Pi xi
Y1" ~P 1.. y/" ~p7
81.
1/2
E
1rx, - -rp.1
2 1-
- rx211 1 + 1, - r1,
1
X/-PE s, X2-P3 22
1/>P7 Y/upF
1 (U,("",, + U,","""" Y(")
E ~P> x1 x -p
Un((Y,
> prr y2 pp
2
26

---

Published in Transactions Machine Learning Research (06/2023)
Un+1(X;, ( (UIn+1XX, Un+ 1
XimPE, N2 Vi-PP M1 X2
as desired.
Lemma 14. For any measures μ, v, and n 2 O, we have that
Un(X,, 1 (U, x2)
E X2 11.V200
+ ki (Y,, Y2) 2k (X1, Yi)l
E X2.N2 Yi.Y2mu
Proof. We proceed to show this by induction. The base case is straightforward, both sides are identically zero. We can now assume the induction hypothesis, and can write out
E X2m 12.
BBa+1 (X1, X2) kn+1 Y2) (X1,
E X2.N Yi,Yom
(rx rx. 181--(188 xxal+ I -1b1)) +
E
kn (X1, X2) + KY,, (2) -2.,
ximPX,
(rx, r 1 -1rx, +11 -r%a)) +
E xi-P3,
Un(X1, (U,,(X) x3),, U..0 (4)
Xi.Xam Y1,Y2mv
xg>PX,
(n1, 1 (U,411(X1; (X,,(M
E Xi.xa Vi,12wr
where (+) follows from Lemma 22.
B Background
B.1 Markov decision processes
We consider Markov decision processes (MDPs) given by (K,A,,, R,,), where X' is a finite state space, A set of actions, P X' x A (XX transition kernel, and R X A + (R) reward kernel (where (Z)) is the set of probability distributions on a mcasurable set Z). We will write Pa == P(x, a) for the transition distribution from taking action in state R. = R(x,, a) for the reward distribution from taking action in state æ, and write r for the expectation of this distribution. A policy æ a mapping X + (AA). We use the notation PTT = EGeA (alar) Pa indicate the state distribution obtained by following one step of policy π while in state a. We use R = EacA (a(ær) Ra to represent the reward distribution from x under म, and r to indicate the expected value of this distribution. E [0, 1) is the discount factor used to compute the discounted long-term return.
27

---

Published in Transactions Machine Learning Research (06/2023)
We will often make use of the random trajectory (X,, At, R1)120, where Xt, A,, and RG are random variables representing the state, action, and reward at time t, respectively. We will occasionally take expectations with respect to policies, written as ( which should be read as the expectation, given that for all we choose A ~ (-1)x,), and receive R₂ ~ R(- At) and X ,,
The value of a policy π is the expected total return an agent attains from following R, and is described by function V* X R,, such that for each E E
(T(x) = Ex
EeeRe 120
Xo x
A related quantity is the action-value function Q" X' x A -> IR which indicates the value of taking action in state, and then following the policy:
Σ RR Re Xo x, Ao d 120
(²x =
A foundational relationship in reinforcement learning is the Bellman equation, which allows the value function of a state to be written recursively in terms of next states. It exists in two forms, for v and Q" respectively:
(=(x) Eg
Ro + +Xi(
Xo 10=0
(² = Er Ro 7X1()
Xo = x, Ao a
Rewriting these equations without the use of the random trajectory, we have
(=(x)= r t [V*(')],
X'opa
E (T, ra + x' A' AQ"(
The Bellman operator T transforms the above equations into an operator over R.Y (or R.XA we will overload the use of 7 and let the type signature indicate which is being used), given by
TVV(x) = - E
[V(X']]
X
Q")(I,a) 1a + X' (( [Q(X)
Written in this way, we see that Qa and v are fixed points of T and with some work one can also see that 7 is a contraction with modulus 7. As a corollary of Banach's fixed point theorem, can choose Vo arbitrarily and update V T%, and converge to V*, this is the algorithm known as value iteration.
An optimal policy n² is a policy which achieves the maximum value function at each state, which will denote V*. It satisfies the Bellman optimality recurrence:
v (x) max [Ro + (Xx) = x].
aEA
28

---

Published in Transactions Machine Learning Research (06/2023)
C Behavioural metrics
In this section, we review various distances which have appeared in literature, and discuss how they relate to cach other. A behavioural metric is usually defined using the following pattern. Onc is comparing the difference between two states, the first and most obvious difference between the states is a reward difference, accordingly this is the first term in the behavioural metric definition. But one wants to take into account the differences in the subsequent evolution of the system starting from the two states. Thus, one needs a notion of difference in the "next states". However, since these are probabilistic systems, there is no unique next state; one has probability distribution over the next states. Thus, one needs a metric that can mcasure the differences between probability distributions.
Metrics between probability distrubutions have a rich theory (Rachev et al., 2013) and history. We review parts of this theory in the first subsection before using these metrics construct behavioural metrics between the states of an MDP.
C.1 Metrics on probability distributions
C.1.1 The Kantorovich metric
Given two probability measures μ and v on a set X, a coupling X 9 X) of the measures is a joint distribution with marginals μ and v. Formally, we have that for every mcasurable subset A ACK,
X(Ax x X) = =(A) and X(X x A) = v(A).
We define A14 v) to represent the set of all couplings of and v. This set is non-empty general, in particular the independent coupling X x always exists. Couplings are essential for the definition of the Kantorovich metric W (Kantorovich & Rubinshtein, 1958) (also known as the Wasserstein metric), a metric on the space of probability distributions on X. Given a metric d on X9, the Kantorovich metric is defined as
/ d(x; y) d)(x,y).
W(d)(, inf xcA(ur) x
The coupling which attains the infimum always exists, and is referred to as the optimal coupling of I and v (Villani, 2008).
C.1.2 The Kukaszyk-Karmowss distance
We recall that the Kantorovich metric optimizes over the space of all couplings; indeed, the com- putational difficulty of calculating the Kantorovich distance comes from calculating this infinum, since for each pair of measures one must solve an optimization problem. The Lnkaszyk-Karmoosh dislance drK (Lukaszyk, 2004)avoide this optimization, and instead considers the independent cou- pling between the measures. That is,
dr.(d)( - d(a ((t.)) d(u x
v))
equivalently
E X~uLY [d(X,Y))
9To be precise, we require (X,d) to be a Polish space, but we drop these technical assumptions for clarity of presentation.
29

---

Published in Transactions Machine Learning Research (06/2023)
Without the need for the optimization over couplings, the computation of dı reduces to the above computation, which is much more computationally efficient. When the base distance d is the Euclidean distance || |l, the Karkssyk-Karroowst distance has been used in econometrics, usually referred to as Giní's coefficient (Gini, 1912; Yitzhaki, 2003).
The computational advantage comes at a price, however. While the Kantorovich metric satisfies all the axioms of proper metric, the Knkaszyy-Karmowsse Karmowski distance does not. This is due to the fact that measures can have non-negalive self distances, meaning one may find a measure f such that dEK (1, > O. One can show that measure μ satisfies dı μ)) = O if and only if f is a Dirac measure, that μ = 6, for some E X' (Lukaszyk, 2004). Intuitively, drk (d)(d, (o) should be seen as a measure of dispersion of μ.. One interpretation of this in the litcrature (Lukaszyk, 2004) is that dEk captures concept of uncertainty: given two random variables X ~ μu, Y ~ V, unless μ and v are point masses, observed values of X and Y are less likely to be equal depending on the dispersions of μ and v. Hence dıK captures a measure of uncertainty in the observed distance of X and Y, compared to a proper probability metric which would assign distance 0 if X Y Y.
The concept of distance functions with non-zero self distances has been considered before, in par- ticular through partial metrics (Matthews, 1994). A partial metric function d : X X + [0, oo) such that for any I, V. E X:
0 d()))))
Non- -on-neggy
d(rxx) S d(z,3)
Small self- delf-distances
d(z,u) = d(y,
Symmetry
if d(xxx)) = d(xx y) = d(y, u), then x y
Indistancy implies equality
d(r,y) S d(x, 2) + d(y, =) 2(z,2)
Modified triangle inequality
We note that there were additional axioms added to this definition, rather than simply removing the requirement that d(x,x) 0. This is due to the fact that this definition was constructed so that one can easily construct a proper metric d from partial metric d, given by d(x, y) d(x,y) v) - 1 (d(x, + ((y,))) We can now show that this definition is indeed too strong for the Lukaszyk Karmowski distance, which we demonstrate in the following examples.
Example 1. The Lukaszyk Karmowski dislance does not have small self-dislances.
d11--,,= 61/2, U((0, 1]). Then one can calculate (d), So So x --yyddyy- 1,4 and dix(d)(H, S 1 -blde 1 But then we have di.(d)(v,v)) = 4 = ddd)(d)(u,,))
Proof. Take X [0, 1], = 1 1
Example 2. The Lukaszyk Karmowski distance does not satisfy the modified triangle inequality.
Proof. Take X = |0, d 1 81, 7= (60 00). We can then calculate dEk (d)
|1-0 = (d), (u,(d)(u,n) +00++((0 + 1 1/2 dık(d) + + {() Combining, we have dik(d)(H, 11 d(v, - 2. which then gives us
=
1
(d) v) = 1>
2 (d) n) + +dvv,) d(n, m)
breaking the modified triangle inequality.
30

---

Published in Transactions Machine Learning Research (06/2023)
To account for this, Castro et al. (2021) introduced new notion of distance known as diffuse metrics. A diffuse metric is a function d : X' x X' [0, oo) such that for any 2, U, 2 E X::
S d(x,1) y)
Non- Con-negativity
d(x,y) = d(y,
Symmetry
d(a,y) & d(x, 2) + d(y,z)
Triangle inequality
It is straightforward to see that the Lukaszyk Karmowski distance a diffuse metric. In addition, an attractive property of the Lukaszyk Karmowski distance for the reinforcement learning setting is that it lends itself readily to stochastic approximation. Given two independent streams of samples (In)n2I, (Un)m21 from random variables X ~ and Y ~ V, a base metric d such that d(X, ((X,Y) has finite variance, and sequence of step sizes (an) satisfying the Robbins-Mome conditions, one can construct sequence of iterates (dz) defined by
dn = =1=11- (1- (n) dn-1 + on d(Ins yn),
with do 0. Then we have dn + dek(d) as - oo (Robbins & Monro, 1951).
C.2 Bisimulation metrics
C.2.1 Bisimulation relations
Bisimulation was invented the context of concurrency theory by Milner (1980) and Park (1981). Probabilistic bisimulation (Larsen & Skou, 1991; Blute et al., 1997; Desharnais et al., 2002; Panan- gaden, 2009) (henceforth just called bisimulation) is equivalence Markov process, where two states are considered equivalent if the behaviour from the states are indistinguishable. To define indistinguishabiliyy we demand that transition probabilities to equiv- alence classes should be the same for equivalent states; that is, the equivalence classes preserve the dynamics of the process. In addition if there are more observables, for example, rewards, those should match well. Bisimulation for MDPs was defined in Givan et al. (2003). This intuition can now be transformed into a definition.
the state space of labelled
Definition 23. An equivalence relation R on X is bisimulation relation if
Ry = Va A, r = ry and VC E X/R,
We say that states a and are bisimilar there exists a bisimulation relation R such that x xRy. We remark that there exists at least one bisimulation relation, as the diagonal relation A = {x,,x) x E X} is always a bisimulation relation, albeit the least interesting one. One refers to the largest bisimulation relation as ~, which is often the one of interest. This version is due to Larsen and Skou (Larsen & Skou, 1991) and the extension to continuous state spaces is due to (Blute et al., 1997; Desharnais et al., 2002).
As Markov decision processes may be seen as Markov processes with rewards, bisimulation relations and metrics have natural analogue in this setting.
C.2.2 Bisimulation metrics
The stringency of bisimulation relations is apparent in the MDP case: if two states have bisimilar
transition dynamics, that is we have that Va and AC E X/R, PC(C) = (C) but Ire 1-2-rrc r > 0,
31

---

Published in Transactions Machine Learning Research (06/2023)
then x and y are in different equivalence classes. This motivates us to introduce metric analogue of bisimulation. We will write M(2) to represent the space of bounded pscudometrics on X. Theorem 24 (Ferns et al. (2004)). Define F ::M(: M((x) - MM()
F(d)(x,)) v) = max
aEA (122 + + ((d)
Then F is a contraction in 1lo with modulus Y,, and hence exhibits a unique fixed point di,, which we denote the bisimulation metric.
Justification lor the term bisimulation metric follows from the fact that the kernel (the kernel of a pseudometric d is the set of pairs of points deemed 'equivalent', formally the set {z, y d(x, y) = 0})
of d. is bisimulation relation.
Proposition 25 (Ferns et al. (2001)). V is 1-Lipschitz with respect to dm, that is for any r, E N,
s (z,
C.3 a-bisimulation metrics
Bisimulation considers equivalence across all possible actions, which is a strong notion of equiv- alence. In many settings, in given state agent may not be concerned with the behaviour under every possible action, but instead only with the actions which it may take under a given policy. On-policy bisimulation (Castro, 2020) was introduced to address this. The definition is a straightforward modification of bisimulation, adapted to given policy.
Definition 26 (On-policy bisimulation relations). Let π be a fixed policy. An equivalence relation R on X is a r-bisimulation relation if
RR = rT= = AC E X/R
Remark 27. It is important to nole that while the definitions of bisimulation relations and π- bisimulation relations appear very similar, they have intrinsic differences. In particular, two states which are bisimilar need not be m-bisimilar, and two states which are x-bisimilor need not be bisim- ilar. To see this intuitively, consider two states which are bisimilar, then any action from either state obtains the same reward and transitions to bisimulation equivalence classes with equal probo- bilities. But a given policy may select actions differently between the two states so that the expected rewards under the policy are different between the states, and in particular the two states are not π bisimälar. On the other hand, two states may have different dynamics across different actions, and hence not be bisimilar, but the policy can balance the actions such that the states are π T-bisimilar.
The T-bisimilarity equivalence relation, like ordinary bisimulation, is sensitive to small changes in the system parameters; so defining a metric in place of relation the natural next step.
Theorem 28 (Castro (2020)). For policy π, define F :M(X) + M(X)
FF (z) y) = - = WW(d) P.).
Then FR is a contraction in 1lo with modulus y, and hence admits a unique fixed point d=, which we define to be the r-bisimulation metric.
It is straightforward to see that the kernel of d= is an on-policy bisimulation relation, justifying its name. Akin to bisimulation metrics, r-bisimulation metrics possess desirable continuity properties when it comes policy value functions.
32

---

Published in Transactions Machine Learning Research (06/2023)
Proposition 29 (Castro (2020)). Let be any policy, then V is 1-Lipschilz with respect to d=, that is for any v, & X,
(* V vT) di (2,
C.3.1 Learning bisimulation metrics
While bisimulation metrics come from rich thcoretical background, they lack application in prac- tice due to the difficulty of learning them in online settings, which is desirable for many represen- tation learning purposes. If P and R were known exactly, then F* can be repeatedly applied in a dynamic programming fashion, and will converge as it is a contractive map. However, when P and R are unknown and only samples are available, learning de becomes troublesome, as estimates for W are generally biased and result in learning different fixed points (Ferns et al., 2006; Comanici et al., 2012).
C.4 Deep bisimulation for control
Zhang et al. (2021) propose a method of learning 7-bisimulation metrics in representation space. They train Gaussian dynamics model P to approximate P, and learn an encoder & X' + Rd. They train & so that representation distances approximate r-bisimulation distances, and use gradient descent to train
(1((x) ((y) 1 ~ l r + 72 12) P.)
The choice of W2(l (12) and Gaussian transitions P is for computational efficiency, as Σn W2(l (A) E1), N (u2, E2)) || 22ll2 + | _ 1/2 - Fr
where ||= is the Frobenius norm. As noted by Kemertas & Aumentado-Armsse computational advantage widened the theory-practice gap, as (i) it not proven whether π bisimulation existed when W2 was used (this was since proven in Kemertas & Jepson (2022)), (ii) the b norm was used for representation distances but the L2 norm was used for the base metric of W2, and (iii) dynamics model was used instead of the ground truth dynamics.
(2021), this
C.5 Background on reproducing kernel Hilbert spaces
We begin by reviewing mathematical background covering vector spaces, reproducing kernel Hilbert spaces, the MMD, and its equivalence to the energy distance.
C.5.1 Hilbert spaces
A (rcal) normed space is vector space V with function || VVVV -> R, which satisfies the following for all x, v.ye E V, a e R:
||||| 2 0
Positivity
||^||
Identity of indiscernibles
||aق|| = |a:|] ||=|||
Absolute homogeneity with respect to scalar multiplication
| + v|1 <
| + ||ll
Triangle inequality
33

---

Published in Transactions Machine Learning Research (06/2023)
A normed space is a stronger notion than metric space, since norm induces a metric d through d(z, v) = - yll- An inner product space is a stronger notion of a normed spacc, which is described vector space V with function (.-) V x V + R such that for all y, 2 E V, a, B R:
(0,v) = x)
Symmetry
ax + B2) alx y) 3(x,z)
Linearily in the first argument
(z, 2 and (a, .) = x
Positive definiteness
An inner product induces a normed space through || = (x, x) If an inner product space induces normed space whose topology is complete, then the space (V, (): is referred to as a Hilbert space. A normed space whose topology is complete is referred to as Banach space, and we remark that Hilbert spaces are a proper subset of Banach spaces.
Hilbert spaces have many desirable properties, and one which will become important for the fol- lowing theory is the Riesz represenlation theorem (Riesz, 1907). Given a Hilbert space V, a map T: V + R is linear if:
T(ax + By) = a: (xx) (T for all x, E V, a, B.
Continuity is casy to verify for lincar maps: linear map T is continuous if and only if T is bounded, meaning that there exists C' E such that
|[((=)]| C||a]], for all x V.
The set of all continuous lincar opcrators on V is known as the dual space of V, and often referred to V* The Riesz representation theorem states that if V is Hilbert space, then V and V** are isometrically isomorphic. Equivalently, this means that for any lincar operator T : V - R, there exists unique FT E V such that
(x, (T, = T(x) for all x VEV.
The interested reader can refer to any text on functional analysis for further details, such as Rudin (1974).
C.5.2 Reproducing kernel Hilbert spaces and the MMD
Let X' be a finite set and a Hilbert space of real functions on X. For a point x E X, the evaluation functional L H. + R is defined by
Lz(J)= = f(x).
If Lg is a continuous functional for all x X, we say that H is a reproducing kernel Hilbert space (RKHS) (Schölkopf et al., 2018; Aronszajn, 1950). Suppose H is a reproducing kernel Hilbert space, then for cach x E X, Lz is lincar and continuous, and the Riesz represcntation theorem implics that there exists a unique h2 H such that
La( = K.)))
Since Kg C H. we can write
kv) (ys)) (Ke, kn) H-
34

---

Published in Transactions Machine Learning Research (06/2023)
This is used to define the reproducing kernel it of H. as k(x, y) (kay ky) We will sometimes write kH to emphasize the dependence of the kernel on the Hilbert space. One can note that the functions ka and ky above can be recovered the kernel fixed at single point, that is hi k(x,,) E H, and ky =y :ky. E H. This is where the reproducing property comes from, as we see that 'reproduces" itselff
k(x, y) (k(a,, ((, k(y, ))
the previous paragraphs, we began with a Hilbert space of functions whose evaluation functional was continuous and obtained a reproducing kernel for this spacc. On the other hand, in Section 2.3 we took the opposite direction: we began with a positive definite kernel on a set and constructed a Hilbert space of functions, the equivalence of these two approaches is known as the Moore- Ahoore-Aroszajjn theorem (Aronszajn, 1950).
Let us recall the definition of the MMD introduced earlier in the main text:
Definition 6 (Gretton et al. (2012)). Let k be kernel on X, and + (x - Hk be defined above. Then the Marimum Mean Discrepancy (MMD) a pseudometric on (X) defined by
= 11 - -
The MMD can also be seen as arising from lifting of kernels on X onto kernels on ( (Guilbart, 1979). Given a kernel on X, define K(u, v) for μ, E (xX) as
k(I, K(,, (I(H), p(v)) = -x d(u @ (z,
It is immediate that K retains all properties of being a positive definite kernel as it arises from the inner product (r, The MMD can then be seen as the metric Pk on ( We remark that the MMD with K allows one to metrize P (X),,,, but we do not need this in this work.
One can also show that the MMD is an integral probability metric (Müller, 1997), since we can show that
FEHL:llfll Si 1/x fdp (
(M, = sup
To see that this corresponds to the MMD defined above, one write out
1/8 fdp / fdv
(f, - (f., (v))ma
sup
sup feHa:llf
feHa:llflly, 31
<1
KS, *(v))aal
sup SEHuell//l $1
[1 ((v)
where we used the following fact for general Hilbert spaces H: suPe:lellees (x. v) 11ll which follows from the Cauchy-Schwarz inequality.
35

---

Published in Transactions Machine Learning Research (06/2023)
D Extra empirical results
Original
AirRaid
Asterix
Breakout
Phoenix
2009
D00
2001
DQN
140
300
Rainbow
500
200
150
OR DON
ION
100
300
1000
14-ON
100
Frames (x1M)
Frames (x1M)
Frames (x1M)
Frames es (xIM)
Figure 3: Comparison of adding KSMe versus MICo all the Dopamine (Castro et al., 2018) value- based agents, on four representative games. Solid lines represent the average over 5 independent runs, while the shaded areas represent 75% confidence intervals.
36


Reviews:
[{"review_id": "DBrCS4mYPc", "reviewer": "Reviewer_9ozD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "***Strengths***\nThe main point of strength of the paper lies in the theoretical contributions that are significant and novel. The view provided in the paper about the use of RKHSs helps in deepening the understanding of these tools in RL. In particular, the properties of the operator $T^{\\pi}_{k}$ (Lemma 8 and 9) are significant.\n\n***Weaknesses***\n1. [Abstract] The abstract is slightly too synthetic and, in particular, it does not provide an effective summary of the contributions of the paper. I suggest better contextualizing the contributions.\n\n2. [Introduction] The paragraph of the Introduction devoted to the description of the MICo distance seems too technical for this point of the paper. While it attempts to point out the limitations of the MICo distance, such considerations are likely not appreciated at this point of the paper. I suggest rephrasing the paragraph in a more general way or, possibly, moving it later sections of the paper.\n\n3. [Relation between finite and continuous state space] Most of the results presented in the paper are for *finite* state spaces (e.g., the definition of MDP in Section 2.1, Lemma 9, Corollary 16). However, the authors in Footnote 2 claim that the RKHSs theory holds for \"much more general classes of sets\". Thus, the authors should clarify which results are limited to finite spaces and which results extend to a continuous one. In my opinion, this is highly relevant since the need for devising an embedding emerges primarily for continuous spaces.\n\n4. [Significance of Theorem 14] Theorem 14 provides a bound to the absolute value function difference into two states ($x$ and $y$) defined in terms of the MICo distance and an additional term which, roughly, depends on the variance of the reward w.r.t. the transition model. This latter term is non-zero even when $x=y$. I see this as a limitation of the bound that clearly shows that it is not tight. Indeed, one expects that the bound should be zero at least when $x=y$. I would appreciate it if the authors could elaborate on this point (here and in the paper) to justify why the bound remains useful even in front of this limitation.\n\n5. [Section 3.5] Section 3.5 seems a little hasty, and the actual rationale behind the loss function in Equation (2) is not properly explained in my opinion. In particular, the meaning of the variables $x'$ and $y'$ is not clear. Do they represent the next states? Furthermore, and more importantly, the properties of the loss function in Equation (2) are not discussed. For instance, is it biased for learning the kernel? I suggest extending this section to provide a more in-depth elaboration and justification behind the choice of the loss function.\n\n***Minor changes***\n- In the definition of value function $V^{\\pi}$, specify that $R_t$ is sampled from the reward distribution $\\mathcal{R}(x_t,a_t)$.\n- The definition of $d_{LK}$ should be reported in the main paper.\n- The footnote marks should appear after the punctuation symbol.\n- The proof of Theorem 13 reported in the main paper references Lemma 21 of Appendix A. Indeed, the actual interesting part of the proof lies in Lemma 21. I suggest either moving the lemma inside the proof in the main paper or postponing the full proof of Theorem 13 to the appendix. \n- There is a little notational abuse in the use of $k$ that sometimes denotes the kernel and sometimes the dimension of the embedding.\n- Theorem 14: specify that $\\mathcal{X}/\\sim$ denotes the quotient set w.r.t. the equivalence relation $\\sim$.\n- Remark 19: I suggest rephrasing it to state that Corollary 16 is improved under the specified condition if we accept an error $\\epsilon$.\n- Section 4.1: $d_{\\sim}^{\\pi}$ is not defined in the main paper. Moreover, it does not appear in Figure 1, although it is present in the legend.\n- Some equations, especially in the appendix, go beyond the margin.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of learning embeddings in Reinforcement Learning (RL) by means of Reproducing Kernel Hilbert Spaces (RKHSs). Specifically, the contributions of the paper can be summarized as follows:\n- The introduction of a novel distance between value functions based on positive definite kernels defined on the state space. This distance is induced by a fixed-point kernel, which is proven to exist unique tranks to the introduction of a suitable contractive operator.\n- The proof that the introduced distance is equivalent to the MICo distance provided in Castro et. al 2021. Furthermore, a novel upper bound on the value function difference is provided, where the bound depends on the introduced distance.\n- Several considerations on the ability to embed the introduced distance in the Euclidean space, with bounds on the requested dimensionality to achieve a given accuracy.\n- Empirical evaluations, both in evaluation to learn the value function and in control, coupled with deep-RL approaches. These results show some advantages compared to the use of the MICo loss.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Weaknesses 1, 2, 3, 4, and 5.", "broader_impact_concerns": "The paper does not contain a \"Broader Impact Statement\". Nevertheless, the contribution is mainly theoretical and, in the reviewer's opinion, it does not raise ethical concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1BARaZGZ92", "reviewer": "Reviewer_bNqr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors appear unaware of a large body of literature related to the application of reproducing kernel Hilbert space theory to Markov Decision Problems. In particular, see:\n\nOrmoneit, D., & Sen, Ś. (2002). Kernel-based reinforcement learning. Machine learning, 49(2), 161-178.\n\nLever, G., Shawe-Taylor, J., Stafford, R., & Szepesvári, C. (2016, February). Compressed conditional mean embeddings for model-based reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 30, No. 1).\n\nFarahmand, A. M., Ghavamzadeh, M., Szepesvári, C., & Mannor, S. (2016). Regularized policy iteration with nonparametric function spaces. The Journal of Machine Learning Research, 17(1), 4809-4874.\n\nYang, Z., Jin, C., Wang, Z., Wang, M., & Jordan, M. (2020). Provably efficient reinforcement learning with kernel and neural function approximations. Advances in Neural Information Processing Systems, 33, 13903-13916.\n\nKoppel, A., Warnell, G., Stump, E., Stone, P., & Ribeiro, A. (2020). Policy evaluation in continuous MDPs with efficient kernelized gradient temporal difference. IEEE Transactions on Automatic Control, 66(4), 1856-1863.\n\nIn particular, in the aforementioned references, the proposed similarity measure between states have has been previously considered in a simplified form in prior works, with the explicit goal of approximating a value (or Q) function that belongs to an RKHS. Therefore, the first bullet on page 2 is a dubious claim, as this notion of similarity pre-dates this work. The authors have not done a thorough literature review on the use of kernel methods in RL. Moreover, the reason for adding d_2 in the definition of the distance is not very clear, and it additionally cannot be easily evaluated, making it not very useful for algorithmic practical use.\n\nHow does the proposed similarity measure actually improve classical algorithms in any way, or lead to more efficient exploration or policy learning? This point is not very clear.\n\nOverall, the paper presents some interesting theoretical results, but there are few practical takeaways for algorithm design, and the proposed similarity metric is intractable to evaluate, which makes approximations to it reduce to pre-existing approaches which are already well-established. Therefore, I am not very convinced of the technical merits of the contributions of this work.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of defining and evaluating similarity measures between states in MDPs. Some theoretical tools are developed, and numerical approximations, whose practical performance is studied. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xIT7JWUJt6", "reviewer": "Reviewer_ea48", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1- the paper is well written\n2- The theory is solid\n3- The paper supports the presented claims with both theory and empirical study\n\nWeakness:\n1- The paper relies too much on the narrative of the prior work of Castro et al. (2021) on the importance of the notion of behavioral metrics. \nThe authors are encouraged to provide more arguments on why such a thing might matter. Reading the paper at its current stage, I am still not fully following why such a thing is important. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of defining behavioral metrics for a given MDP. A behavioral metric for a given policy is a quantity that for any two states attempts to give an upper bound on the difference of their values under the same policy. In this paper, the authors provide a new perspective on this problem using the RKHS theory. They show that one can use the reward function and the transition kernel of the MDP under the given policy to define a kernel that gives rise to a metric. Given this kernel, the authors argue that the feature embedding of the states in RKHS is useful for value function learning. \n\nThe authors build their work upon the prior work of Castro et al. (2021) which does not discuss the RKHS view but rather only the metric view of the behavioral metric. The current work fills the gaps of the prior work and provides a behavioral metric that upper-bounds the difference of the value functions. \n\nBorrowing the idea from the fixed policy setting (the theory developed in this paper), the authors propose to take their feature embedding method to the online RL setting where they use neural networks to learn the feature embedding, resulting in performance improvement over base methods such as DQN. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please motivate in more depth the importance of the behavioral metric.", "broader_impact_concerns": "There is no concern about the ethical implication of significant matters in this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The updates made by the authors in the last round have successfully addressed the concerns that were raised during the review process. In particular, I appreciate that the authors added further motivation to study the setting they consider, and provided a sufficient amount of technical details in the experimental section, which makes it easier for the reader to appreciate the relevance of the theory to the experiments (and more generally, makes the experimental setup much more clear).

One comment that I will make is that, even after the update, the authors still do not clearly explain why studying distance metrics that *upper-bound* the value differences is of specific interest. In the introduction, they write that "a good embedding should cluster together states which are known to have similar behavioural properties, whilst keeping dissimilar states apart." --- however, the upper-bound property they seek does not eventually guarantee that dissimilar states will have dissimilar values, only that similar states will have similar values. While I don't necessarily expect the authors to share the views I have elaborated on in my earlier comment, it would be useful to admit somewhere in the paper that guaranteeing the upper-bound property does not necessarily provide a complete picture about the usefulness of behavioral metrics, and more research may be needed to provide an understanding about the good empirical performance of the methods studied in this paper and in the related literature.

With that, my recommendation is to accept the paper without major changes. I trust the authors to implement any small changes they deem necessary to respond to the concerns mentioned above.
Decision: Accept (poster)