Approximate Policy Iteration with Bisimulation Metrics
Authors: Mete Kemertas
Allan Douglas Jepson
Venue: Accepted by TMLR ()

Abstract: Bisimulation metrics define a distance measure between states of a Markov decision process (MDP) based on a comparison of reward sequences. Due to this property they provide theoretical guarantees in value function approximation (VFA). In this work we first prove that bisimulation and $\pi$-bisimulation metrics can be defined via a more general class of Sinkhorn distances, which unifies various state similarity metrics used in recent work. Then we describe an approximate policy iteration (API) procedure that uses a bisimulation-based discretization of the state space for VFA and prove asymptotic performance bounds. Next, we bound the difference between $\pi$-bisimulation metrics in terms of the change in the policies themselves. Based on these results, we design an API($\alpha$) procedure that employs conservative policy updates and enjoys better performance bounds than the naive API approach. We discuss how such API procedures map onto practical actor-critic methods that use bisimulation metrics for state representation learning. Lastly, we validate our theoretical results and investigate their practical implications via a controlled empirical analysis based on an implementation of bisimulation-based API for finite MDPs.

Published in Transactions on Machine Learning Research (11/2022)
Approximate Policy Iteration with Bisimulation Metrics
Mete Kemertas
kemertass@cs.orronooocoo
Department of Computer Science, University of Toronto
Vector Institute
Allan Jepson
jepson@cs.torontoo edu
Department Computer Science, University of Toronto
Samsung AI Center, Toronto
Reviewed on OpenReview: https: // openreview. net/ forum? id- It 71HeCm0
Abstract
Bisimulation metrics define a distance measure between states of a Markov decision process (MDP) based on a comparison of reward sequences. Due to this property they provide theoretical guarantees in value function approximation (VFA), In this work we first prove that bisimulation and r-bisimulation metrics can be defined via more general class of Sinkhorn distances, which unifies various state similarity metrics used in recent work. Then we describe an approximate policy iteration (API) procodure that uses bisimulation-based discretization of the state space for VFA and prove asymplotic performance bounds. Next, we bound the difference between a-bisimulation metrics terms of the change in the policies themsolves. Based on these results, we design an API(a) procodure that employs conserva- tive policy updates and enjoys better performance bounds than the naive API approach. We discuss how such APT procedures map onto practical actor-critie methods that use bisimu- lation metrics for state representation learning. Lastly, we validate theoretical results and investigate their practical implications via a controlled empirical analysis based on an implementation of bisimulation-bassd API for finite MDPs
1 Introduction
Reinforcement lcarning (RL) algorithms can be broadly grouped into two categories: (i) policy itcration (PI) methods and (ii) policy search methods. The former alternate between learning the value function of the current policy and improving the policy via greedy updates, while the latter directly optimize a performance objective in feasible set of policies. Learning the value function in large state spaces (e.g., continuous spaces) can be intractable, value function approximation (VFA) is typically employed for PI in practice. Even with powerful function approximators (e.g., deep neural networks), efficient and generalizable VFA remains an open research problem. State abstraction methods (Li et al., 2006) and state similarity metrics (Lan et al., 2021) take a reductionist approach, aiming to exploit similarities between states to treat them as one, e.g., via state aggregation (Singh et al., 1995; Bertsekas, 2019). Tn this work we study APT via bisimulation metrics with the goal of extending the theory surrounding them, bridging the gap between theory and practice, and improving the stability of API algorithms that rely on them.
Bisimulation metrics measure the functional similarity of states by design, comparing only the extent to which reward sequences differ in expectation (Ferns et al., 2004; 2011). Owing to this property, they provide error bounds in VFA, while enabling more efficient state represenlations. Recent work has tackled challenges in their estimation by introducing т- r-bisimulation (Castro, 2020), and employed them for simulated continuous control by constraining the representation space of a neural state encoder (Zhang et al., 2021). Zhang et al. (2021) showed that such constraints promote invariance to background distractors in visual environments, thereby improving sample efficiency in learning. Despite attempts to characterize the trade-offs and con-

---

Published in Transactions on Machine Learning Research (11/2022)
vergence properties of practical iesimulation-baseed RL algorithms (e.g., Kemertas & Aumentado-Armsttoon (2021)), PI via bisimulation is still poorly understood.
In this paper we first generalize the definition of bisimulation metrics via p- Wasserstein metrics and Sinkhorn distances, and prove their existence for this more general family. This generalization adds theoretical jus- tification to a prior practical modification (Zhang et al., 2021), lifts an assumption on theoretical results concerning VFA via p- Wasserstein bisimulation metrics (Kemertas & Aumentado-Armstroomn 2021), connects recently proposed metric by Castro et al. (2021) to standard bisimulation metries and allows for fast com- putation. We then describe API procedure, which approximates л --biiimulation metric at each iteration, and performs state aggregation under it before policy evaluation (PE) and approximate greedy improvement (GI) steps. To make the procedure more efficient, we motivate the use of conservative policy updates, and show that adopting such updates strikes a better trade-off between performance and computational com- plexity than the naive version. We then conduct thorough empirical analysis of our theoretical findings characterize trade-offs posod by various algorithm design choices in terms of asymptotic performance, rate of performance improvement, representation capacity and wall-clock time.
2 Background
2.1 Setting
R,,)) the state and action spaces, transition kernel, reward function and a discount factor y E 1). For case of analysis, we assume that the state space S is compact in Ferns et al. (2011). An agent selects an action, a, A at each discrete time-step according to stationary policy (a,]s:)) The MDP transitions to the next state according to transition distribution P(s (t, az). The distribution over next states when actions to policy π is denoted (=((++1(ss) With an abuse of notation, we write x(s)), P(st, az) and Pa (s:) for these conditional distributions when appropriate. The agent collects a scalar reward rz = R(s,, a:) from the environment, which is computed via a bounded reward function, R : S x A [0, 1]. The reward range is selected to simplify analysis, although our theoretical results can be extended to arbitrary bounded reward ranges with ease. The expected immediate reward from choosing an action according to policy in state s is denoted by R2 (s) = (a)a(s) R(s, a)). The agent's discounted return in given episode is G Eizon're We denote by B(X) the set of real-valued bounded functions over X and write V E B(S) for the value function of a policy π, i.e., the lixed point of the Bellman operator Tz B(S) + B(S), given by the shorthand notation V = Rx + YPvV. Similarly, V denotes the optimal value function, or the fixed- fxed-point of the Bollman optimality operator T : B(S)= > B(S), where TV = sup T,V, the supremum taken over the set of stationary policies II. For given function J, ||/ denoles the supremuu (uniform) norm, i.e., sUPredom(f) [f(). We write [f Ex= for a distribution f supported on dom(f).
Consider a discounted Markov Decision Process (MDP) given by a tuple,
selected according
Here, we are interested in state similarity (pseudo) metrics? d: S x S + oo) to be used to directly ag- gregate S or constrain representations of its elements to save space and memory, and to promote efficient learning (e.g., via distraction invariance). In particular, given a state similarity metric and threshold 2e, one can derive a state abstraction function & S S + that satisfies:
((s,) = ((s)) = + d(s,, 8,) S 2e.
(1)
This abstraction & maps a ground MDP (S. R,7) to its abstract version (5, R, 7), where P and R are defined as per-partition weighted averages. Tn partieular, let Bx = (z E (<{)) = (x2)) be the set states that are in the same partition as 8, Given an arbitrary non-negative measure g that assigns
1 All finite discrete spaces compact. continuous space is compact if and only if it. is totally bounded and complete. For brevity, we drop "pseudo" in the following.
2

---

Published in Transactions on Machine Learning Research (11/2022)
positive measure {(Bb > 0 to all partitions (s(s), write (Li et al., 2006; Ferns al., 2011):
1
R({((), = E(Ba(8)) ze)
R(z, a))5)))
(2)
(()))) == (()) (e))(s)
Next, we discuss bisimulation metrics, which provide guarantecs in approximating value functions over the ground MDP using value functions over abstract MDPs derived via (1). Further background and references on state aggregation methods are provided Appendix B.
2.2 Bisimulation Metrics for Continuous MDPs
To provide VFA guarantees, Ferns et al. (2011) defined the following bisimulation metric for continuous MDPs as a weighted sum of the difference between immediate rewards obtained from respective states and a futurc-looking recursive term based on the 1-Wasserstein distance (sce (8) with p 1, = 0 for a definition).
Definition 2.1 (Bisimulation metric for continuous MDPs, Thm. 3.12 of (Ferns et al., 2011)). Let met(S)
be the set of bounded pseudo-metrics over a compact S. Given en E (0,00) and er E (0, 1), the following mapping F; met(S)) + met(S) has a unique fixed-point d' called the bisimulation metric:
F(d)(s;, max en c R(s,, a) R(s, a)l c2 a), P(s),)) aEA
(3)
The existence proof applies compact state spaces via the Banach fixed-point theorem (Ferns et al., 2011). A special case of this metric for finite MDPs was also outlined previously by Ferns al. (2004). Ferns et al. (2011) showed that this formulation ensures connection to optimal value functions. In particular, whenever er 7, V is CR -1 -ippschitz under the bisimulation metric, i.c., cnlV"(s;) - V*)))) s (s; The Lipschitz continuity of V with respect to d' results in the VFA guarantee that given a state abstraction & derived via d' as in (1), whenever or E [7, 1):
2x
I Vallo S cn(1-7)²
(4)
where (s(s) (*((s)). In words, whenever the bisimulation metric places as much weight on future distances as the value function places on future rewards, e-aggregation" under the bisimulation metric yields abstract MDP, which has an optimal value function that is close to that of the ground MDP (Ferns et al., 2011). Thus, given knowledge of the bisimulation metric, one can reduce an MDP with a possibly continuous state space to a finite MDP, which can be solved easily via regular (exact) PI, and have confidence that the solution is approximately optimal with worst-case error given as a linear function of the aggregation radius e, which determines the granularity of the partitioning. Given that exact PI for finite MDPs converges in O [S|| log( )) steps (Scherrer, 2013), if substantial reductions in the size of the state space are possible (e.g,, due to the presence of distractors) such that [S] > |6], one can pre-compute bisimulation- based abstractions to find a near-optimal policy much more quickly. However, computing the metric itself exactly can be costly; for example, fixed-point iteration requires Of log(E) log(er) | (s)) steps in the worst- case to find an approximate bisimulation metric d such that - I E (Ferns et al., 2006). Assuming that & can be computed at low cost, a naive combination of bisimulation-basee by PI over the reduced MDP yiclds a complexity of o log(E)
1->
partitioning followed | |S|+ + |S||A|]
1-y log(z"+)). which need not be superior to directly applying Pl on a finite ground MDP. Further, fixed-point iteration cannot be used trivially over continuous state spaces so that function approximation ncods to be adopted. Hence, fast approximations of bisimulation metrics are necessary in practice to amortize the cost of metric learning and enable usage in continuous MDPs or large finite MDPs. Indeed, in Sec. 3.1 we consider fast approximation of Wasserstein distances, which is major bottleneck that prior work attempted to overcome or circumvent via assumptions (Ferns et al., 2006; Castro, 2020; Zhang et al., 2021; Castro et al., 2021).
log(er)
3 An e-aggreagated state space any partitioning that permits a maximum partition radius of e under metric
3

---

Published in Transactions on Machine Learning Research (11/2022)
2.3 n-bisimulation Metrics
While bisimulation metrics are useful for approximating V of a large MDP, they can be difficult to compute for large (e.g., continuous) action spaces due to the max operation in (3). Secondly, the max operator is inherently pessimistic in assigning a notion of similarity to states. Castro (2020) highlighted these issues and proposed r-bisimulation metrics to address them.
Definition 2.2 (r-bisimulation metric (Castro, 2020)). Given fixed policy the following mapping F: met(S) + met(S) has a unique fixed-point di called the T- r-bisimulation metric.*
(x), 8,) (s.)) (s + (cWW)())(P(())))PP())
(5)
An approach to learning di via stochastic approximation with replay buffer samples was presented; the approach reduces the complexity of metric learning by factor of |A] for finite MDPs. Castro (2020) also showed that the value function V of a policy is similarly 1-Lipschitz under the r-bisimulation metrie when Recently, Kemertas & Aumentado- Arritttdno (2021) assumed that Fr has unique fixed-point if defined via an arbitrary p- Wasscssstnn metric with 2 1 instead of the 1- I-Wasserstein metric specifically. Then, given an abstraction derived via de for any er E [7, 1) and 2 1,
CR 1, i.., [V*(s,) - (Tx)))] S (st,
I 1o I cR(1-7)*
(6)
where V= Rr + 7,, VT. Similarly to (2), R and P5 were defined as per- per-partition weighted averages of R2 and P respectively (Kemertas & Aumentado-Armstrongg 2021). In the next section, we use (6) to construct API algorithms with performance bounds.
3 Theoretical Analysis
In this section, we first prove that bisimulation metrics can be defined via a more general class of statistical distances including p- p-Wassorstein metrics and Sinkhorn distances (Cuturi, 2013), which can be used to compule upper bounds on the I-Wasserstein metric at improved complexity. Based on these results, we will derive a feasible API procedure with bounded error to optimality. The procedure performs alternating updates a sequence of policies ne and approximations of corresponding sequence of metries di.- Unlike Zhang et al. (2021), we do not assume a continuously improving policy to argue for convergence. Rather, we leave the possibility of policy oscillation open (unlike exact PI, approximate PI is not guaranteed to converge (Bertsekas & Tsitsiklis, 1996)), but provide asymptotic bounds on optimality. Next we show that restricting the size of policy updates renders such procodures more stable, making a case for the use of conservative policy updates in the context of bisimulation. algorithm that bounds the policy update size, and consequently enjoys better performance bounds than the naive API algorithm. We conclude the section by discussing the connections between our theoretical setting and practical algorithms used for larger-scale problems. All proofs are relegated to the Appendix for space.
To further this point, we outline an API(a)
3.1 On the Use of Optimal Transport for Bisimulation Metrics
In prior theoretical results, bisimulation metrics were defined via the 1-Wasserstein metric (iee. the Kan- torovich metric) (Ferns et al., 2004; 2011; Castro, 2020). p-Wassorstcin distance computation between a pair of distributions over a finite space S has worst-case complexity ( log S)) (Orlin, 1988). This makes the usage of the 1- J-Wasserstein metric a major obstacle for practical use since for a single fixed-point update it is computed |S| and |S|2 times for (3) and (5) respectively. To cireumvent this problem in empirical studies, Castro (2020) assumed deterministic dynamics.. 5 Similarly, Zhang el al. (2021) assumed the dy- namics can be modelled as Gaussians over latent space and successfully used 2- 2-Wasserstein metric to exploit the closed-form of the W2 distance between Gaussians (Olkin & Pukelsheim, 1982), albeit without
*Castro (2020) originally defined the metric with en = and eT 7
5he Wasserstein distance between two delta distributions simply the distance between the two points (Villani, 2008).
4

---

Published in Transactions on Machine Learning Research (11/2022)
theoretical justification. Here, we show that p- t-Wassesstein distances can indeed be used safely and thereby lift. the assumption made by Kemertas & Aumentado-
(2021) to prove (6) for arbitrary p 2 1.
We further show that Sinkhorn distances, which bound Wasserstein distances above via entropic regulariza- tion, can also be used. The practical advantages of using Sinkhorn distances are three-fold: (i) owing to a strictly convex optimization objective, the Sinkhorn-Knopp algorithm (Sinkhorn & Knopp, 1967) can be used to compute them in O([S] log (S]) time (Altschuler et al., 2017; Dvurechensky et al., 2018), (ii) un- like standard Wasserstein distance solvers this computation can be massively parallelized on GPUs (Cuturi, 2013), and (iii) between fixed-point iterations of Fx one can easily save Sinkhorn potentials to warm-start the Sinkhorn-Knopp algorithm at an overall memory cost of ((S))). Now, we define primal and dual Sinkhorn distances with 2 1 in preparation of a generalized definition of bisimulation metrics.
Definition 3.1 ((p. C)- and (p, AJ-Sinkhorn distances). Let d X' x X + [0, oo) be a distance function and Ω the set of all joint distributions over X' x X' with marginals μn, 1/2 E Pp(X), where Pp(X) denotes the set of probability measures with bounded moments of order p on X. Given the product of marginals μ1 @ p2 (Genevay et al., 2016) and p 2 1,5 2 O, we call the following primal form (p. ()-Sinkhorn distances:
1 ).
(1)((((1, U2) min |dlpp where Q(() fw E DKL(W p1 @ P2) wED(()
(7)
The dual form is given by the Lagrangian of (7) with X 2 0:
p (d)( = |dd|ww-, where w' = arg min Id|p - AH(Ww,, EEn
(8)
where H denotes Shannon entropy. To each ( and pair of distributions (MI, 122 corresponds a X such that (d) p2) = (d) (Cuturi, 2013). While x= 0 recovers p- p-asssesttein distances a special case where S is sufficiently small, X 0 renders the objective of the dual form strictly convex. Consequently, when computing (d)((, one can use the Sinkhorn-Knopp algorithm, which converges in fewer iterations for higher A (Cuturi, 2013), albeit at the expense of weaker upper bounds on W (p(d)(A1. (2).
Lemma 3.2 (A (p. S)-Sinhhorn distance bound). Given metrics d and d', for all p 2 1 and < 0,
I (d)(()p1, p2) (5(d")(H1, S ||d- d'lloo
(9)
Theorem 3.3 ((p, ()-Sinkhorn bisimulation metrics). Let er E 10, 1), cR E [0, oc), p 2 1 and Ç ( 0. The
mappings F, F,F=: met(()) - met(S) each have unique fired-points:
F(d) (s:, sy) = max cxl R(s a) - R(s,, a)l + () a
(10)
Fa(d) 8,) = cn RT - R2 (s,) + cr. Wc
(11)
Whenever CT 7, (4) and (6) hold for all p 2 1 and Ç 2 0 for siced-points d' and di respectively.
The existence and uniqueness proof follows from Lemma 3.2 and the Banach fixed-point theorem. We note the following relationship between bisimulation metrics that use different values (p. C)- Remark 3.4. Given metrics di and dī defined via (1), and S2), (pI, (1) = + df
That is, e-aggregation of S under di is finer-grained than under di. Thus any speedups obtained via p 1 or X >> 0 come at the expense of possibly less efficient discretizations (larger ($]), although one still enjoys the same VFA bounds given in (4) and (6) for the same c. Intcrestingly, 2021) as a special case of (p. ()-Sinkhorn bisimulation metrics; when and (- oo, the optimal transport plan w" + jn @ #22 and the (p. ()-Sinkhorn distance becomes the expected distance over la & μ2z This was precisely the distance used by MICo to replace the costly 1-Wasserstein distance, 6 Hence, the more general form (10-11) with < 2 O establishes a continmum of metrics that spans bisimulation metrics and MICo at its two extremes. Similarly to Cuturi (2013), we provide theoretical results for the primal Sinkhorn distance Wd)d), but for empirical analysis in See. we use the dual distance Wx with a fixed À rather than optimize the dual variable À for a fixed ç. In particular, we investigate the quality of metrics with varying p and X, and how their differences may influence API algorithms that rely on said metrics for VFA.
recover MICo (Castro et al.,
Thhi distance measure also known the Eakassyk-Kaann Karmowski distance (Fukasvyk, 2004; Castro al., 2021).
5

---

Published in Transactions on Machine Learning Research (11/2022)
3.2 Approximate Policy Iteration with T-- n-bisimulation
Now that we approxinate bisimulation metries more elliciently using Sinkhorn distances, we introduce feasible API procedure with a-bisimulation metrics. Using (6), we will derive error bounds on optimality. We write Imprrm/meroooee to indicate an approximate greedy update with respoct to a function V E (S), which yields a policy Tg over S such that |[T V TV 56
Theorem 3.5 (API with π bisimulation). Let CR = 1, or y and {Tk be a sequence of policies generated with the following updates per step, where dg = 0 E met((S) and & 2 0 and n E N4 are algorithm porometers. Let Cn = 7" /(1 - y); and consider for any p 2 1 and ç 2
dr. - nx
(do)
(12)
8, 4 + HardAggregation(S. :))
(13)
1 + PolicyEvaluation(5, nx)
(14)
Th+1 f- Greedyymmprvvmment
(15)
and V B(S) is the composition of Te and kk. If the sequence { lKEN converges to policy म, we have
8
+ 2y(2 + ca)
| 1o I
(16)
1 1-7
(1 7)
Otherwise, it has the following limiting bound
27(2e + cn) lim - 1o S (1 (1- 7)- + k+00
(17)
(1 7]3
Here HargAggrenntion yields partitioning S of S under drz with partition radius at most (see Appendix D.2 for pseudocode of an implementation for finite S). As e e O, policy evaluation becomes increasingly accurate. The number of metric learning updates also provides trade-off between run-time and policy performance guarantees. Larger implies more accurate approxinations of di, due to (12). This translates to a better bound on the worst-case error on V due to the cn term in (16-17). Note that metric learning errors, as well as errors due to stochastic approximation of R or inexact environment dynamics can be absorbed in E; see Lemma A.9 in Appendix A for a decomposition error terms.
For ease of analysis, this procedure naively learns the approximate metric dr, from scratch after each policy update (see (12)). In practice, we may wish to warm-start metric learning with updates day + =- (dax..) to approximate d=, in fewer itcrations n, or we may be learning a paramotrized metric via gradient descent as in the DBC algorithm (Zhang et al., 2021). To understand the tradeoff of such metric updates, we next derive a bound on how much the n-bisimulation metric changes when the underlying policy is changed.
Lemma 3.6 (Comparing r-bisimulation metrics of different policies). Let n, a be a pair of policies and di di. corresponding π r-bisimulation metrics given by p E [1, oo) and X 0. The difference between di and dr is bounded by Diy (Mt, x') supees DTv(TT(S), n' (s)), the worst-cuse total varialion dislance of w and m':
-|ا - d; V
2CR
Div (T)
(18)
(1 )2
Here, (18) guarantees that small policy updates lead to small changes the r-bisimulation metric. Thus, we conjecture that restricting the policy update size should keep the metric learning objec- tive stable and result in a better performance guarantee when warm-starting is used for faster metric learning. Indeed, inspired by Scherrer (2014), we write an API(a) procedure, which constrains pol- icy updates such that (T TR) S a, Vk E N. Given such updates, we are guaranteed to have l|d; dz, o1 S 20ga //1  or)² by (18), which can be leveraged ensure that warm-starting metric learning updates provides a better asymptotic bound than (17) under some conditions. Before that, we pause for another lemma, which generalizes Propositions 2.4.3 and 2.4.4 of Bertsekas (2018a).

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma 3.7 (Generalized API(a) bounds). Let V B(S) and policies n, nt' , satisfy the following:
V Vl S ôpF
|T V - TV x 2 ÓGI
x' =agg + (1 - T,
where E [0. Then,
dcr + 270PF
| - -V S <1- - +a
(19)
1 1-7
Nerl, consider an API(a) algorithm that generales sequence of policies {Te)NEN via functions (VilkEN with policy evaluation error ||VTH Villx S òPE,K, approzimate greedy updates with error T V&- 1o S 6GL, and policy updates Th+1 t- atggk + (1 TT. For any a E (0,
lim sump 5GI, + 2YδPE,
lim k+000
1o
(20)
71-
For a = 1, (19) recovers Proposition 2.4.4 of Bertsekas (2018a) as a special case. (20) follows by setting W' = Th+1, π = Th (19) and taking a limit superior on both sides; it proves that the same asymptotic bound as Proposition 2.4.3 of Bertsekas (2018a) holds for API(a) with arbitrary a E (0, 1]. Furthermore, it makes explicit that the oscillation amplitude due to PE and GI errors is modulated by
Thcorem 3.8 (API(a) with r-bisimulation). Under the same conventions as Thm. 3.5, let
n log( / /lo((?) and Cn (1 + 7)en. Given (a - 2.) ()))) for some a (0, 1], X 0
and any p E [1, o0):
dx. < F(n) ( (dmz-1)
(21)
5, Φ3 < Hard Aggregation(S. dry,, 6)
(22)
5T Bvalainval ( Tk)
(23)
Tg + GroedyImprovement 0o ,8)
(24)
Wk+1 (1 T& arg.
(25)
The sequence {NEEKE has the following limiting bound,
27(2c ac,)
lim limsupl/V*
Vo y1- (1 713
(26)
k-:00
As expected, by exploiting the induced stability of the sequence (diz hREN via small a, we obtain better asymptotic bound for the same as compared to Thm. 3.5 (since S 1). The trade-off here is that setting a too small can slow down policy improvement and require more policy updates to attain the asymptotic bound. In particular, the number of steps k necessary to attain a fixed worst-case error bound scales as 1/a due to the contraction rate a + ary seen in (19). Note that a = would amount to no policy update and is therefore ruled out by assumption: a E (0, 1]. We omit the convergence case here, although may be possible to obtain bound that scales similarly to (16) by following Proposition 2.4.5 of Bertsekas (2018a).7
The bounds here are expressed in terms of the sup-norm for simplicity and represent the worst stronger bounds in terms of Lp norms can be derived following prior work, e.g., Munos (2003); Farahmand et al. (2010). Indeed, as noted by Bertsekas (2011), the limiting bounds in (17) and (26) can be conservative and quickly attained in practice. Nevertheless, they provide insight about co-learning bisimulation metrics and policies when one does not assume a continuuusly improving policy. In Section 4, we validate this point empirically with an implementation of the procedures described in Thms. 3.5 and 3.8.
However
Bertsekas & Tsitsiklis (1996) note that convergence quite uncommon unless approximation errors are extremely small.
7

---

Published in Transactions on Machine Learning Research (11/2022)
120 V116 VM
19 52 (115519)
Number Nans under
M127
140
ARR2TT)
23"
301
Skrgs 201 soard
Number of Nomn under
60-
46-
100 385 30
10 312
Figure 1: Ablation of a for the algorithm analyzed in Thm. 3.8 for two MDPs (top and bottom rows). (Left) While the algorithm reaches a similar performance range for all a, we observe more oscillatory behavior for higher values of a, which aligns with the ordering of asymptotic worst-case performance (limit superior) predicted by (26). The trade-off of reduced rate of improvement is also seen clearly. (Middle) The metric learned by lower a better approximates the value difference AV*(s, 8') - (V*(s) V=((s') both in terms of final error and variance in the limit. (Right) All < 1 shown here converge to (near- (near-)optinn joptimal partitioning of S with [S] m, but a 1 unable to find the optimal partitioning and has 4 oscillating for both MDPs.
3.3 Bridging Theory and Practice for Co-learning Policies and Bisimulation Metrics
Recall that. Zhang el al. (2021) incorporated r-bisimulation metrics into the Soft actor-critic (SAC) algorithm (Haarnoja et al., 2018) via an auxiliary loss, which encourages the neural state representations o(s) used by critic and (optionally) actor networks to respect an approximation dz of dž computed with replay buffer samples and learned dynamics, i.e., [[)(s;) - d(s,))l )l z (s,, 85). Such latent representations were shown to promote distraction invariance for contimuuu control tasks, which in turn improves sample efficiency and performance under heavy distraction over various representation learning baselines (Zhang al., 2021), as well as the vanilla SAC algorithm (Kemertas Aumentado- Armstrong, 2021). Similarly, MICo learned (in value-based framework) state encoder that respects another metric defined via Ezy [d(21, x2)] instead of W1 (d) P2) for fast compulation (Castro el al., 2021), which we connected to (1, -SSinkhoo distances in Sec. 3.1 by taking a limit Ç ( co. Here, we describe how the algorithm given in Thm. 3.8 maps onto actor-critic approaches used in applications.
The n-step fixed fixed-point update given in (21) is feasible for sufficiently small finite S, but not for large or continuous S. Thus DBC computes the fixed-point target for batch of states a continnous setting, where dr. (s; 8z) = (s:) - Φu (s,)]l and a sequence of fixed-point updates replaced by gradient update dt+1 + Φb + (ox) with step-size for loss,
((b)) = E [ān (s,, (s,)s) R2, -.( 2
where the expectation estimated with replay buffer samples and P is latent Gaussian model over o space.
For VFA, use HardAggregation operation which explicitly computes Š and aggregation function t as in (22). For finite MDPs, & is represented as an [S] x [S] matrix with onc-hot encoded columns, that (23) is performed via value iteration over R₂ and Px easily with matrix operations. The use of
8

---

Published in Transactions on Machine Learning Research (11/2022)
122 V110 V014
H927
AF12-1
A11--1
0Pfol a m0a0
Wi.0. & moae
201
10
CRd 20 STaRE
Figure 2: Comparing IV V aloc using API, APT(a) and APT(ax) on the first MDP with [28, 7,1] (left-to-right). See text.
(22-23) enables theoretical analysis via (6). On the other hand, practical approaches for continuous MDPs such as DBC learn neural critic of the form Vo(o(s)) with SGD, where o(s) is trained to respect the bisimulation metric as described above. Hence, by construction we have (*)()s)) = (d((s)) whenever (s:)) = (83) such that d= 8,) S 2e In contrast, in actor-critic based continuous control one softly promotes Vo())s:)) = Vo(o(s;)) for small d= = [|)(s;) - Q(s;))1 via an architectural constraint on the critic.
Lastly, the operation GreedyImprovemeen (V 5) in (24) can be viewed as combination of an exact update 7 + GreeedyeTpppa Improddyymmoreemennt""" ,0) in the finite space S followed by a lifting of this quantized policy to a policy Fg over possibly continuous S with some error 5 2 O. For practical continuous control, one noisily updates the parameters và of an actor network Ty with SGD to maximize values predicted by the bisimulation- constrained critic Voog. Computing an a-mixture of policies as in (25) is trivial for finite MDPs as it amounts to a simple interpolation of probability vectors over the action space. However, iterative mixing of neural policies as in (25) over contimuus MDPs is non-trivial. Hence, we focus on finite MDPs in the next section for controlled empirical analysis of the theoretical results presented here.
4 Empirical Analysis
In this section, we conduct experiments to empirically investigate the practical implications of the theoretical results in Sec. 3. To this end, we consider a discounted problem involving [S] states and m equivalence classes (ECs) denoted B; where i E [I...., m] and each EC contains the same number of states [S]/m /m. At each step, agent decides between two actions ag and a1 taking dg in B, transitions the agent to Bi+1, while aı transitions the agent to Bi (both with probability 1). Only when the agent takes dg in Bm does it obtain a reward of 1 and taking ag keeps the agent in B,, then. Hence, the agent is required to take at least m times consecutively to collect rewards after laking an once. When constructing P, we sample uniformly from the random seed generates an MDP with a different P, but they all map to the same reduced MDP. We also consider a second MDP with dense rewards inspired by Example 6.4 of Bertsekas & Tsitsiklis (1996). This time, the agent stays in the same ECC if it takes an rather than being transitioned to B1- Once the agent reaches Bm, it stays there forever regardless of which action it takes. Rewards for when the agent takes ag are defined recursively as = T++1 = +r,+e, e, where we set e == 1-7 so that R E [0, 1]. We also consider a third class of MDPs in Appendix F and obtain similar results to those presented here.
to determine the transition probabilities to states in each EC, Therefore, each
1-y
In the experiments outlined here, we choose |S] = 200, m = 20 and 7 = 0.9. Unless otherwise stated, we use use p = x = 1 and n = (09(117//lo///) be terminated carly at given step A: if (++1 perturb action probabilities of the ground-truth greedy policy with Gaussian noise and renormalize to form a distribution. A heuristic search of the noise variance ensures ||T,, V - -VVll E [0.05, 0.1] so that 8 < 0.1. In all cases, we initialize To to be the maximum-cntropy policy. Our source code will be open-sourced for reproducibility. We base our Sinkhorn-Knopp implementation on the Python Optimal Transport package (Flamary et al., 2021). All figures present results over 10 seeds with shaded areas showing standard error.
as in Thm. 3.8 (n 28 for 7 = 0.9). However, metric learning can
(d)- (d))))((d))))))))))))))))))))))) (2))= (d) (f < 10-3 To simulate noisy greedy updates, we
9

---

Published in Transactions on Machine Learning Research (11/2022)
ACh22
Number tats (8) under
19
M000
14800
16-1
33
101
37
10
33'
MIX VIXV"55- VmGl
Number of part Nans (5) uncer
2
111
0.3
3.7
3.7
3.55
175
2.00 1060
2 2.00 2-200-1000 1000
2-200100C
30-
32
10
31
3P
120 317
31
201
Figure 3: Similar to Fig. 1, but varying À for = 1 and E = 0.1 (top), and p for x = 0.1 and E = 0.25 (bottom) on the first MDP. See text.
API, API(a) and API(a)). We begin our analysis by testing the algorithm in Thm. 3.8 with varying a. The results shown in Fig. 1 confirm the key insights that emerged from the analysis in Sec. 3.2: (i) lower a makes progress more slowly, but is more stable and has better asymptotic worst-case performance, (ii) lower a better exploits warm-starting of metric lcarning to learn a higher quality metric, which in turn better approximales the value difference AV 8') = [V*(s) - (*('') (recall that. the true metric dz satisfies (**(s) I di (s, s') for on = 1, see also A Appendix E), (iii) a higher quality metric makes for a better partitioning based on it so that all settings with a < 1 recover the m = 20 ECs of the MDPs, while a = 1 does not. Note that we use == 0.1 for the first MDP and e = 0.04 for the second.
Next, we compare the algorithm in Thm. 3.8 to its naive version described in Thm. 3.5 for various settings of the number of fixed-point iterations n. We add a new variant called API(ar) to the comparison based on the observation that we can leverage the high rate of improvement of a high a in early phases of learning and the improved stability of low a in the limit by scheduling ag to decay gradually to a limiting a. Indeed, given ag + a the same asymptotic bound in (26) holds. In Fig. 2, we show that the naive algorithm behaves similarly to API(1.0) for n large enough. However, for smaller n the naive algorithm fails (cf. (16- 17)), while the warm-start algorithm succeeds. Secondly, Fig. shows that given a decay schedule such as 0g max(2-0. k=00)), we are able to obtain better tradc-off in terms of rate of improvement and stability than either of API(1.0) and API(2-0) 9). We note that lower n does not seem to compromise the warm-start algorithm stability, but only slightly slows down policy improvement in terms of time-steps h for a good trade-off on wall-clock time (as fixed-point updates Fr comprise the main bottleneck on run-time). Lastly, we repeated the same experiment with 7 = 0.99 and did not observe any qualitative differences.
(p. A)-Sinkhorn distances. Here, our main goal to investigate the results provided by Thm. 3.3 and Remark 3.4 in Sec. 3.1. As noted in Sec. 3.1, we use the dual Sinkhorn distance with a fixed X 0 for ease of computation and omit the optimization of the dual variable X for a fixed Ç. However, we note the monotonic relationship between À and Ç. In Fig. 3, we ablate À and p to show how they influence learning for an (P((a) algorithm. We use the API(ox) variant described above with ag- max(0.01, k-0.8) as it strikes a better trade-off between rate of improvement and asymptotic stability than the fixed-a variant. Recall that all settings of (p. () enjoy the same bound (6) as stated in Thm. 3.3, and consequently their usage in API also yields the same asymptotic performance
Thm. 3.8. In the left-most column of Fig. 3, we observe near-identica behavior in terms of optimality error [V*-V=* not just asymptotically, but for all k regardless of the choice of (p, A); i.e., learning dynamics are almost. identical. However, the quality of the
10

---

Published in Transactions on Machine Learning Research (11/2022)
V1 V-
122 V
311
11-
30100
(1800
(18C
337
101
37
101
31"
301
10
GR 20th STaRE
Nerra ised Mutual information
Nermstized Hutual informatio
Nerraaized Mitusl Informacion
A-30
A=22
12P
33F 307
312
31
Figure 4: Varying À with umperturbed, lightly perturbed and heavily perturbed P (left-to-right) when Gaggregationn is replaced by 30-medioids partitioning. (Top) Performance gap between different À settings widens with more stochastic P. (Bottom) Quality of the learned metric as measured by normalized mutual information (NMI) of labels found by m-medioids with ground-truth EC labels of the unperturbed MDP.
metric decreases with increasing p and À in terms of its ability to approximate the value difference between pair of states (see Remark 3.4). As a result, given a fixed e one obtains a less efficient discretization (finer- grained partitioning) of the state space. The output of bisimulation-based RI. algorithms is not only a policy optimized to solve a certain task, but also an efficient state encoder (or aggregator) that ignores functionally- irrelevant aspects of the environment state; the experiments here show that while all of these metrics (when learned with the same number of fixed-point iterations) follow a nearly identical policy optimization path, the choice of Ap defines trade-off between time and space complexity for hard-nggrogation with Φ and possibly time complexity and encoder quality for representation learning with state encoders d.
Aggregation on a space budget. In Figs. 1 and 3, we observe that the algorithm often computes a fine- grained partitioning (iS) close to |S| = 200) carly on given a fixed c. We inquire whether this costly phase is necessary to find the optimal policy in m-bisimmultioon-baseed API. Secondly, we also observed finer-grained partitioning with increasing A. We thus inquire whether the metric learned by MTCo (A -> oc) still captures the same geometric information about the state space but only on different scale, or it actually loses information about state similarities due to a weaker upper bound AVT. To investigate these questions, we test a variant of the algorithm; we replace e-aggregation as in (22) with partitioning around medioids (PAM) with a fixed number of 30 partitions (Kaufman & Rousseeuw, 1990). Thirdly, in Appendix C, we identify a potential shortcoming of the Sinkhorn distance: guided by information-theorede intuition, we find that the Sinkhorn distance tends to compute a weaker upper bound on the Wasserstein distance when the distributions being compared have higher entropy. We thus consider MDPs with varying degrees of stochasticity in P: in particular, we perturb each transition matrix P(..a) from the first MDP, which is deterministic, by mixing it with randomly sampled transition matrices (each row sampled uniformly from the (($()-)-simplex) with mixture weights 0.05 and 0.5. Conclusions from Fig. are threefold. (i) The algorithm makes similar progress towards solving the task given a partition budget 50% above m, i.c., it does not strictly require too many partitions early on to make progress later. (ii) We confirm that metrics with smaller À yield a more informative partitioning, and observe correlation between the quality of the metric and performance. In other words, if representation capacity allocated to Ob and V is constrained, lower X produces better results at the expense of some added computation time (more Sinkhorn- Knopp iterations). (iii) The Sinkhorn distance offers better complexity-performant trade-off for more deterministic MDPs.
11

---

Published in Transactions on Machine Learning Research (11/2022)
103
206
600 1000
200
800
1000
Figure 5: Better runtime with lower (Left) and higher À with decaying ag as before (Right) on an NVIDIA GeForce GTX 1080 GPU.
Runtime measurements. In Sec. 3.1, we discussed how one can warm-start the Sinkhorn-Knopp al- gorithm with Sinkhorn potentials of previous metrics at some memory cost (see Appendix D.1 for de- (ails). A second advantage involves the use conservative policy updates. Intuitively, when Th, Ps, and the ground metric dRy, do not change much over time-steps k, the Sinkhorn potentials corresponding to W (da, Pa. should not either. In light of Lemma 3.6, suspect that with conservative policy updates, the initial guess provided to the Sinkhorn-Knopp algorithm might be closer to the true solution when conservative policy updates are employed, which may result in faster convergence. In Fig. 5, we mea- sure the wall-clock time per iteration of the API(a) algorithm to validate this hypothesis. Secondly, we noted in Sec. 3.1 that greater À requires fewer steps for Sunkhorn-Knopp to converge; this is also demonstrated in Fig. 5. However, the cost of small À is eventually amortized by the warm-start strategy as the metric converges (after 300 steps). Note that for X + oo, we have closed-form for finite spaces (Cuturi, 2013):
lim (2) = lim (d)(,nn, = =1 A
6000
where D is distance matrix with Dij = d(x;; ky), and μ1 and μ2 are probability vectors. Hence, in this case one bypasses Baakhorn-Knopp entirely. The computation of the metric (s))) (s'(')) for all state pairs can be easily parallelized for finite MDPs; all pairwise distances can be computed as PPDPT so that the case À + xc can be taken as a best-case run-time benchmark for our implementation.
5 Conclusion
In this work, we analyzed the use of bisimulation metrics in approximate policy itcration to bridge the gap between theory and practice. We first generalized bisimulation metrics to ()Sinkhonr distances where p 2 and < 2 0. The p-Wasserstein generalization confirmed the theoretical results on VFA of Kemertas & numentado-Armstree Wasserstein metrics for fast computation as in Zhang al. (2021). Sinkhorn distances enabled GPU-based fast approximation of upper bounds p- paaassesteiin bisimulation metrics with better time complexity than prior work (Ferns et al., 2004), and established a theoretical formalism for a more general family of metrics encompassing standard bisimulation metrics and MICo (Castro et al., 2021). We further conducted a theoretical analysis of API procedures that use a bisimulation based discretization of the state space for VFA. The analysis indicated that conservative updates may benefit such procedures since a rapidly changing policy makes for rapidly changing metric learning objective. Indeed, we showed that conservative updates enable warm-starting of metric learning iterations with significantly better speedup-performance trade-offs. To validate our theoretical findings and investigate trade-offs, implemented the theoretically-grounii API(a) algorithm, which mimics the actor-critic based applications of bisimulation-liko metrics for continuous control (Zhang et al., 2021; Kemertas & Munentado--Ammstroonn an ablation analysis of algorithm parameters, and also showed empirically that decaying policy update sizes may strike better tradc-offs between asymptotic performance, stability and rate of improvement. Further, in our controlled setting we showed that metric learning speedups are gained by a trade-off in the quality of the learned metric and space complexity of corresponding state abstractions. Whenever VFA capacity (as
(2021) given in (6) and added theoretical justification to the use of 2-
2021; Castro el al., 2021). We provided
12

---

Published in Transactions on Machine Learning Research (11/2022)
measured here by the number of allowed partitions) is sufficient, the policy performance for the task at hand remains unaffected by the use of weaker metries; however, capacity limitations may result in performance degradation as was shown in Fig. 4. Furthermore, we presented evidence that the Sinkhorn distance may offer a better trade-off under more deterministic transitions. While we focused on thcorctical analysis this work and limited our empirical analysis to finite MDPs, future work may consider practical approaches to implementing bisimulation- basod actor-critic algorithms with conservative policy updates, and sample-base approximation of the Sinkhorn distance between continuous distributions for continuous control.
Acknowledgementts. We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
References
David Abel, David Hershkowitz, and Michael Littman. Near optimal behavior via approximate state ab- straction. In International Conference on Machine Learning, pp. 2915 2923. PMLR, 2016.
Jason Altschuler, Jonathan Niles Niles-Woed, and Philippe Rigollct. Near-linca time approximation algorithms for optimal transport via sinkhorn iteration. Advances neural information processing systems, 30, 2017.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
John Baras and Vivek S Borkar. learning algorithm for markov decision processes with adaptive state aggregation. In Proceedings of the 39th IEEE Conference on Decision and Control (Cat. No. 00CH87187), volume 4, pp. 3351 3356. IEEE, 2000.
D. P. Bertsekas and J. N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific, Belmont, MA, 1996.
Dimitri Bertsekas. Abstract dynamic programming. Athena Scientific, 2018a.
Dimitri P Bertsekas. Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applicalions, 9(3):310-335 2011.
Dimitri Bertsekas. Feature- aggregation and deep reinforcement learning: A survey and some new implementations. TEEE/CAA Journal of Automatica Sinica, 6(1):1-31, 2018b.
Dimitri P. Bertsekas. Feature-based aggregation and deep reinforcement learning: survey and some new implementations. IEEE CAA J. Autom. Sinica, 6(1):1-31, 2019. doi: 10.1099/AAS URL
J109//AS... 2018.751122.
D.P. Bertsekas and D.A. Castanon. Adaptive aggregation methods for infinite horizon dynamic programming.
IEFF Transactions on Automatic Control, 34(6):589 598, 1989. doi: 10.1109/9. 1111999992227777
Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic Markov decision processes. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 34, pp. 10069-10076, 2020.
Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland. MICo: Improved represen- talions via sampling-based state similarity for Markov decision processes. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: /ttpss//openrevier wttparrrwwiiieeee/ouuuuuuue wwwt/forummdiieeeoooooooo ddw.rrummmi.uuPppmm0
Guanting Chen, Johann Demetrio Gaebler, Matt Peng, Chunlin Sun, and Yinyu Ye. An adaptive state aggregation algorithm for markov decision processes. arXiv preprint arXt::107.11105 2021.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances neural information processing systems, 26, 2013.
13

---

Published in Transactions on Machine Learning Research (11/2022)
Thomas Dean and Robert Givan. Model minimization in markov decision processes. In AAAI, pp. 106-111, 1997.
Thomas Dean, Robert Givan, and Sonia Leach. Model reduction techniques for computing approximately optimal solutions for markov decision processes. In Proceedings of the Thirteenth Conference on Uncer- tainty in Artificial Intelligence, UAr97, pp. 124-131, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. ISBN 1558604855.
Yaqi Duan, Tracy Ke, and Mengdi Wang. State aggregation learning from markov transition data. Advances Neural Information Processing Systems, 32, 2019.
Pavel Dvurechensky, Alexander Gasnikov, and Alexey Kroshnin. Computational optimal transport: Com- plexity by accelerated gradient descent is better than by sinkhorn's algorithm. In International conference on machine learning, pp. 1367 1376. PMLR, 2018
Amir-massoud Farahmand, Rémi Munos, and Csaba Szepesvári. Error propagation for approximate policy and value iteratioon In Proceedings of the 23rd International Conference on Neural Information Processing Systems Volume 1, 10, pp. 568-576, Red Hook, NY, USA, 2010. Curran Associates Inc.
Norm Ferns, Prakash Panangaden, and Doina Precup. Metries for finite Markov decision processes. In Pro- ceedings of the 20th Conference on Uncertainty in Artificial Intelligence, UAI '04, pp. 162 169, Arlington, Virginia, USA, 2004. AUAI Press. ISBN 0974903906.
Norm Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden. Methods for computing state similarity in markov decision processes. In Proceedings of the Twenty-Second Conference on Un- certainly Artificial Intelligence, UAT'06, pp. 174-181 Arlington, Virginia, USA, 2006. AUAT Press. ISBN 0974903922.
Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous Markov decision processes. STAM J. Compul., 40(6):1662 1714, December 2011. ISSN 0097-5397. doi: 10.1137/10080088X. URL https:///oi...... http:///oo..r////.../ 113...101771108A..11
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Cham- bon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. Pot: Python optimal trans- port. J. Mach. Learn. Res., 22(78):1-8, 2021.
Bennett L Fox. Discretizing dynamic programs. Journal of Optimization Theory and Applications, 11(3): 228 234, 1973.
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large-scale optimal transport. Advances in newral information processing systems, 29, 2016.
Alison L. Gibbs and Francis Edward Su. On choosing and bounding probability metrics. International
Statistical Review, 70(3):419 435, 2002. doi: https://doi.org/ 10111111j..1111553222222.. 1751-5823 2002. tb00178.
URL
https:://onlinelibrayy wwweeeewwrrrrriieeee...........e
wiley. wwwo/////aa//////eeeoooaooaaseet 10.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in markov
decision processes. Artificial Intelligence, 147(1-2):163 223, 2003.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement. learning with a stochastic actor. In International Conference on Machine Learning, pp. 1861-1870. PMLR, 2018
Jesse Hostetler, Alan Fern, and Tom Dietterich. State aggregation in monte carlo tree search. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1), Jun. 2014. doi: 10.1609/aaa wwtp://aaaaa....00eee.. v2811.9066. URL https://ojs.. aaai. org/index. http////AAaatriiie///e//////////
Nicholas K Jong and Peter Stone. State abstraction discovery from irrelevant state variables. In IJCAI, volume 8, pp. 752-757, 2005.
14

---

Published in Transactions on Machine Learning Research (11/2022)
Leonard Kaufman and Peter J Roussceuw. Partitioning around medoids (program pam). Finding groups in data: introduction to cluster analysis, 344:68-133 125, 1990.
Mete Kemertas and Tristan Aduances in Newral Information Processing Systems (NeurIPS), 2021.
CranentadoAAmmtroonn Towards robust bisimulation metric learning. In
Charline Le Lan, Mare G. Bellemare, and Pablo Samuel Castro. Metrics and continuity in reinforcement learning. In Thirty-Fifth AAAT Conference on Artificial Intelligenne, AAAT 2021, pp. 8261-8269. AAAT Press, 2021. URL https:/ //jss. aaai. org/index, www.ddeppp//////aaaaaaaaeeeeeeee hhtp:///A///aatttcaaaeeeee//////
Lihong Li, Thomas J Walsh, and Michael I. Littman. Towards a unified theory of state abstraction for MDPs. ISAIM, 4:5, 2006.
Szymon Lukaszyk. A new concept of probability metric and its applications in approximation of scattered data sels. Compulational mechamics, (3(4):299-300) 2004.
Andrew Kachites McCallum. Reinforcement learning with selective perception and hidden state. University of Rochester, 1996.
Roy Mendelssohn. An iterative aggregation procedure for markov decision processes. Operations Research, 30(1):62-77) 73, 1982.
Rémi Munos. Error bounds for approximate policy iteration. In JCML, volume 3, pp. 560-567, 2003.
Ingram Olkin and Friedrich Pukelsheim. The distance between two random vectors with given dispersion matrices. Linear Algebra and its Applications, 48:257-2633 1982.
James Orlin. A faster strongly polynomial minimum cost flow algorithm. In Proceedings of the Twenlieth annual ACM symposium Theory of Computing, pp. 377-387, 1988.
Ronald Ortner. Adaptive aggregation for reinforcement learning average reward markov decision processes. Annals of Operations Research, 208(1):321 336, 2013.
Bruno Scherrer. Improved and generalized upper bounds on the complexity of policy iteration. Adoances in Newral Information Processing Systems, 26, 2013.
Bruno Scherrer. Approximate policy iteration schemes: a comparison. In International Conference Machine Learning, pp. 1314 1322. PMLR, 2014.
Scan R Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Adaptive discretization for episodic reinforce- ment learning in metric spaces. Proceedings of the ACM on Measurement and Analysis of Compuling Systems, 3(3):1-44, 2019.
Satinder Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggre- gation. In G. Tesauro, D. Touretzky, and T. Leen (eds.), Advances in Neural Information Process- ing Systems, volume 7. MIT Press, 1995. URL pdf.
Richard Sinkhorn. Diagonal equivalence to matrices with prescribed row and column sums. The American Mathematical Monthly, 74(4):402-405, 1967.
Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343 348, 1967.
John N Tsitsiklis and Benjamin Van Roy. beature-based methods for large scale dynamic programming. Machine Learning, 22(1):59-9)) 94, 1996.
Benjamin Van Roy. Performance loss bounds for approximate value iteration with state aggregation. Moth- ematics of Operations Research, 31(2):234-22) 244, 2006.
Cédric Villani. Optimal transport: old and new volume 338. Springer Science & Business Media, 2008
15

---

Published in Transactions on Machine Learning Research (11/2022)
Ward Whitt. Approximations of dynamic programs, i. Mathematics of Operations Research, 3(3):231-245 1978.
Chao Yuan Wu, Manmatha, Alexander Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Proceedings of the IEEE international conference on computer vision, pp. 2840- 2848, 2017.
Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. In International Conference on Learning Represenlations, 2021. URL https: http://peeneeieeeeeeeeeeeeeeeeee wwtp:/.eeeeetoennne.e.ee.. 2FCDd=RRRERF.
16

---

Published in Transactions on Machine Learning Research (11/2022)
A Proofs and Additional Results
Lemma 3.2 (A (p. ()-Sinhhorn distance bound). Given metrics d and d', for all p 2 1 and ( 2 0,
(2) - W (d') (22 | S l|d dl' 20-
(9)
Proof. Let (2()) {w E Ω (KL || M1 H2) SC
W (d) u2)
P2)
= min |dd|p - W (11,,)))))))) wE(())
min ||d d' + d' d'ww - W (di, wE)(C)
S min (lld d' pmp. + [Iddllp..) wE((())
(since triangle inequality holds for all w e 9(())
S min (lld 11=0 + [|d'llpw)) - (d') w))l(()
(since |I.1|p.. S 11-11s0)
ld - d' + + min
||d"] (d'dd'
wE((())
||l d' |ox..
Lemma A.1 (Triangle inequality for WS(d)) (d)). Consider three probability measures μni P2; P3 E Pp(x).
(d) us) I (s(d)(p1, + (d))
(27)
Proof. For this proof, we use the Gluing Lemma (see Chapter of Villani (2008)) and Lemuna 1 of Cuturi (2013). Note that triangle inequality readily holds for (d)d) (Villani, 2008) and W (d) (Cuturi, 2013).
Let random variables (X1, X2) be the optimal coupling of (2) and (Zz, Za) the optimal cou- pling of (z). By the Gluing Lemma, there exist random variables (X, X4, such that wi2 = lawa( X3) law(X,, X2) and wag = law(X2, X3) = law( (a,,Z,,22 Zz), where wi2 E (()). Further- more, by Lemina of Cuturi (2013), (x), is coupling of (M1 ps) such that W13 = law law(X, (X1,X)) E (((). That is, wis also satisfies the entropic constraint, given by Ç and is therefore feasible.
(5))((L) pa) (3)((X (since the coupling Xx) is not necessarily optimal for (s))
[[[(X,, X3) + d(xg. (x)x))))11) xx)))1
(by triangle inequality since d is pseudo-metric)
$
(E))(X)
(by the Minkowski inequality)
= WS(d)(m) M2) + W (d) (s).
where the equality in the final step holds since the couplings (X) and X3) are optimal with respect to (H1, and Ps)) respectively by construction.
Corollary A.2 (Approximate metrics and approximate distributions). Consider distributions
M1, M1,21, E (x())) and a pair of metrics d, Due to Lemma 3.2 and Lemma A.1,
(2( (T. F221 S WS (1)) F.) + W$ (d) T22) + lld - d' loc.
(28)
17

---

Published in Transactions on Machine Learning Research (11/2022)
Proof.
W 5 - Tu2))
WS(d)(m), u2) - (5(d)(m1, 122 + WS(d)( (dy(d" (22)
WS(d)(m1, x2) - (z(d) Tb){
+ -
(triangle inequality)
Wy(d)(mr, M2) - (z m2)
+ l|d 10-dd d01100
(by Lemma 3.2)
Ws(d)(m1F1) ,1) + (d) 12) + W/ (d) 12) -11 + +lld +Ild-d'11 d'
(by Lemma A.1)
= () + W (d) (2)) + 1|d-
Theorem 3.3 ((p. S)-nkhhorn bisimulation metrics). Let or E (0, ca 10, p 1 and Ç 2 0. The
mappings F, Fx met(S) - met(S) each have unique fired-poinls:
((d) 85) = max cnl R(s:; a) - R(s,. a)l + (c), atA
(10)
(s) 8,) = cn Rx (sj(s)) + (()
(11)
Whenever er 2,,, (4) and (6) hold for all p and Ç 2 0 for fized- points d' and dž respectively.
Proof. Similarly to the proofs of Thm. 3.12 of Ferns et al. (2011) and Remark 1 of Kemertas & Aumentado- Armstrong (2021), it suffices to show that above fixed-point updates are contraction mappings. Then, we invoke the Banach fixed-point theorem to show the existence of a unique metric. Intuitively, applying the operator F on different metrics d, d' E met(S) should bring the metrics closer under the supremum (uniform) norm, such that lim F(²) (d) lim, (d'),, i.e., they converge to the same unique metric. Here, compactness of S implies that met(S) is complete such that the Banach fixed-point theorem can be applied (Ferns et al., 2011). Due to Lemma 3.2,
Fx (d)(ss.. 83) - Fx 8,) = (Wp(())( (((())))))(((((((((())))))))
S cr d - ao V(s,, S S.
Taking a supremum on the LHS over S x S, we obtain (dF (d) I crlld d' bloo i.e. Fr is a cy-contraction with respect to the sup-norm. Then, Fa has unique fixed-point due to the Banach-fixed point theorem. The same result readily applies to F as well.
We now prove (6) for Fr. First, note that by definition of the primal Sinkhorn distance in (7), we have for any p. d, f1,
S 2((2) S S(G)) = p (d) S W (d)(
Then, given fixed-point metrics di and d2 given by (p) and (p, S2), have SI S.S S2 d1 S d2. More generally, we have (PI,G1) I (P2, (2) = di S de Pi S P2 + Wn, (d)( S Wp, (2),, (Villani, 2008). But from Castro (2020) and Kemerlas & Aumentado- Armstrong (2021) we have for any n, cR|V"(s)- - VT(s')] & (s, for the special case when p= = 1 and Ç sufficiently small so that the constraint is satisfied for all w E and WS(d))(a, P2) = (ydd)((1, .2). Then, we have (pI, 3 (p2.Cz) = cR(V=(s) V=((')] s d1 S d2 so that all metrics defined by (p,C) provide an upper bound on en cn(V"(s) V*('') The result (6) follows immediately from Lipschitz continuity of Va with respect to of (see proof of Lemma 8 by Kemertas & AraennttddAAmstrong (2021)), which is true of all metrics given by (p, {): hence (6) holds for all (p, S). The same logic applies to F and V due to Ferns et al. (2011), so we skip the proof of (4) for brevity.
as noted in Remark 3.4 since
Definition A.3 (Total variation distance (Gibbs & Su, 2002)). The total variation distance between a pair of distributions pt, p2 over a measurable space X' is given by the following:
Drv(ui, U2) sup (m (A) (a)( ACX
(29)
1
/ [(x)) -M2(2r))d
max FEF
(30)
2
18

---

Published in Transactions on Machine Learning Research (11/2022)
where F= (f: - -R 1l < 1)). For discrete distributions, Drv(H1: 2 12ll11
Corollary A.4 (Total variation distance to mixture distribution). Given distributions μ4, #2 over mea- surable space X and scalar [].
Drv(uI - (1 + ap2) = aDIv((1,H2)
(31)
Proof. Follows immodiately from (30).
Lemma A.5 (Total variation distance between policies transition distributions). Consider pair of policies x and the dedecyddeennennt transition distributions Px(s), (s)
(iv(P - (s)
(32)
Proof. Let = (f: - R I 1 and g = {o A + R 1 S 1}. Using Definition A.3 of the
total variation distance,
Drv(P=(s), (s)
- -PP((((
max /Ef
2
1
I. f(6') / ((((ls,a)(((aa)) - x = dads'
max
2 Jer
/A - f(8')P('')) a)ds'd da
max TEJ
(by Fubini's theorem)
2
1
/ ((aas) - r'(als) S ((s)))(ss)) s, a)ds' da
2
fs,,a)
1
/ (T(als) - (alss)
-'alls))((aas)))
max #ES
a(s a)
da
2 A
=M(a)
( / (M(als)- x <a(ass g(a)da
$ max 2 DEG
DTv( (s)))
where we used the fact that |l < and || $ 1.
Lemma A.6 (Total variation distance between policies vs. immediate reward difference). Consider pair of policies n, xO and the policy-dependent reward functions Rx R,',
R (s)( s (
(33)
Proof.
RR (s) Rs)( / (T(ass) r'ass)) R(s) d)da
I (I(aas)) ( ra|ss) 2R(s, a) da
1 /
/ (I(a)s) r'(ass) (2R(s. a) 1)da
(since क and n' both integrate 1)
< Drv (s)) n' (s))
where the last inequality is due Definition A.3 and the fact that ||2R 1//0 S given R E [0. 1].
19

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma A.7 (Wasserstein distance of transition distributions under different policies). Given pair of policies x and the policy-dependenl transition distributions P= (s),
CR - (ylds))((())) - (T -
(34)
Proof. First, recall from (6.11) of (Villani, 2008) that the 1- I-Wasserstein distance under the indicator function 1/2 # x'] is equal to the total variation distance. Then,
W1 + x0) 21))(1,, min | + æ Illl DTv(U1,
min
|| + I Vp E [1, 00)
(since 1/2 + x'1 = 1 + x'pp)
wenl
min || + x 11 vp (0)
wenl
(7 # H2)), vp E (1)
which implics for all E (o)
+ xx))(,,, = (2y(
(35)
Next, note by Lemma 1 of Kemertas & Aumentado-Armsttongg (2021), all bisimulation metrics are bounded above by cn/( er) for E [o. 1].
W (P(d (x),))))))
-T) Cn Wp d= - CT)
(s),
1 cr
CR
CR
Wp(1[s (s),
1- cr
1 CT (Tv((r(s), (a)))
(due to (35))
CR 1- (
(by Lemma A.5)
Lemma 3.6 (Comparing r-bisimulation metrics of different policies). Let n. nt be a pair of policies and dz correspording π n-bisimulation metrics given by p E [1, oo) and x= 0. The difference between di and di is bownded by Diy (π, supses DTV(T((), T' (8)), the worsl-case lotal varialion dislance of a and n':
2CR
|| - df S (1-eT) cT
Diy (T,
(18)
Proof.
d (8i, 8j) - d. (81, 85)
cCR
RR (8.) - (xx)) (R,) Rx((8,)))
(P),,,,,))) (w.dd) Par,,,
< CR [x,(s)) R2 (s,)) - (st) R, (8,))
+ Cr (s)) (s)),
20

---

Published in Transactions on Machine Learning Research (11/2022)
( - (r [R((s,) Rsy() Drv (( + Drv (T(S)), ((()) 2
(by Lemma A.6)
S + Px 11d, dx
(due to Corollary A.2)
CR
DTV ( (())) + DTv क|
#) )) + errldd - 110
(due to Lemma A.7)
2CB DTV TT, c |d doo c- cT
Combining
and and rearranging:
(x 83) (s.
- (C T') + 2cTen DTV (T,, x²)² torldd dro
--cr
2CrCR
S 2222DVV(TTT T') + 1 1- Dig (T, n + cT|ld, 110
t (since Drv E [0,
2CR DTV (T, x²)² cTllda l
< 1 c- CT
Taking a supremum over S x S on the LHS and rearranging.
2CR
| dr 1o0 S (1 (1- or) D DTV (T, +')²
Note that stop i serves only to simplify the final expression, but yiclds a loose bound for p >> 1. Omitting one obtains better bound:
dd -
2CR 1ah-d.llor da S (1 cr)
(D
eT (T)))
- cr
As or + the second term dominates so that the loose bound tightens. Since er is typically set to and is close to practice, we use the simpler bound for convenience.
From Thm. 3.3 and the proof Lemma 8 Kemertas Aumentado- following bound on approximation error for Va given an approximation of the z-bisimulation metric.
Soaittaddd--m-stoonn Armstrong (2021), we have the
Lemma A.8 (Approximating V under metric learning error (Kemertas Aumentado Armstrong, 2021)). Let dn be an approzimation of di such that l|d; - dz lol < E. If state abstraction function $ is computed such that ((s)) d(s;) d= 85) < 2e, the following holds:
2x + E V Vo < ca(1 7)
(36)
The following exlends Thm. of Kemertas & Aumentado-Armstrnn (2021) to (p, <)-Sinkhorn distances. Lemma A.9 (Decomposition of error sources in VFA for (p, ()-Sinkhorn bisimulation metrics). Consider bounded approrimate reward function î and dynamics model P supported closed subset of S. For any 2 and 2 0, there erists unique metric d d_ such that
()) (..)) Rr - + (l) (.).
21

---

Published in Transactions on Machine Learning Research (11/2022)
Furthermore, aggregation vio learned approrimation dz of n, yields the following bound for any p 1:
1 || Vol 10c I cR(1->) 2c (2 Em + 1- CT
2CR ER + 2CT Ep) E
(37)
1-
where &m = 110 d x lz the metric learning error, ER R Rx the reward approrimation error, and Ep == supaes W$S (dP)) (#)) is the state transition model error.
Proof. Here, we use the following shorthand notation for the r-bisimulation distance between a pair of states: d= 85) = CR [ Re (dz) Pt).
First, note that the existence of d_ a, follows from Thm. of Kemertas Aumentado-Armss Armstrong (2021) and Lemma 3.2. Next, we apply the triangle inequality to the error on the true metric de:
| dz a0
1 ||dx d d, 11dx d_ 2lppo
(triangle inequality) (by definition of Em)
| d n
Fl +Em
Expanding I
1|d
plo0
sup {
cR [R2 - R211 - 1R R + (dx) Pb) - [
(P: .P)
S sup {
cn RRa R + RR R + or (w (P: Pt) Wglld s) P1)
is
< ECHER + sup
(dx) P!)) - W وم (P:: P()
(by definition of Eg)
i.
s ZCRER + CT sup
W (dz) (Pt, P:: + (s P4) + I| d x, m11))
(by Corollary A.2)
i
2CRRR + Ec + cr||d - d blo0.
(by definition of Ep)
Rearranging,
2CR En +
2er Ep.
||, d d,,51000 5
CT
1 cT
Plugging 1 back in,
2CR En
2CT Ep-
1|dz - 1=1100 S Em
1 Cr
CT
The result follows from Lemma A.8.
Now, we rephrase API bounds from Bertsekas (2018a) before proving Thm. 3.5.
Lemma A.10 (Propositions 2.4.3 and 2.4.5 of (Bertsekas, 2018a)). Consider an API algorithm that gener- ales policies (EE) and functions [Vi}ReN in B(S) with policy evaluation error V - V ll S ôèg and approzimate greedy updates with error 1[T Vv - TV S der. If the sequence converges to policy म,
der + 2YôPF.
||T- <
1-2 7
Otherwise, the sequence JREN has the limiting bound,
8G1 + 27ôPE (1 - 7)2
lim limsspplV 100 <
40
22

---

Published in Transactions on Machine Learning Research (11/2022)
Theorem 3.5 (API with πI n-bisimulation). Let cR or = and (TKRKEN be sequence of policies generated with the following updales per step, where do = 0 E met(S); and e 2 0 and n E N+ are algorithm parameters. Let Cn = /11""((1 (), and consider for any p 2 1 and Ç 2 0:
dz. - nr (do)
(12)
8, 4x f- Hard Hargaaggrggallon( dz,.,)
(13)
V* + PolicyEVvlluation(5, Tk))
(14)
Mk+1 + Groodylmprovvmment VTT 6),
(15)
and V B(S) is the composition of TTh and c. If the sequence {T teeN converges to policy we have
- - 10 1-7 + 2y(2 + ca)
(16)
71-
Otherwise, it has the following limiting bound,
27(2c en) (1 - (1
lim - 1lo S 10000
(1 71- +
(17)
Proof. First, we observe that,
|d dxe 1lo0
| Rk (do) - 1l0
et |ire (do) dolloo
(by the Banach fixed-point theorem and Thm. 3.3)
eT
c, Fr,, (do)l ll 00
(since do = 0)
cn sup Hxx (Bi) - Rr (8,) (.j
(since do = 0 + (d(do) = 0)
Cn, Vk N.
(since R E (0,
Then, by Lemma A.8,
T V. 11 5
+ On
vk. E N.
1 y
The result follows from Lemma A.10 with dG1 and ôPE
26+en. 1-7
To prove Thm. 3.8, we write an analogue of Lemma. A.10 that does not assume fixed bound on PE error, but sequence of policy evaluation errors ôPF, and greedy improvement errors δG1 that have finite limiting bounds. The following is slight variation of Lemma A.10, which is stronger as it considers asymptotic bounds on said errors rather than the maximum error over all k.
Lemma A.11 (A stronger API bound (Bertsekas, 2018a)). Consider API algorithm that generates policies [TEN and functions [VeJNeN in B(S) with policy evaluation error 1 V S ôpE. and approzimate greedy updates with error [ Vis - TVx S δGLL. The sequence {Ta]KEN has the limiting bound,
lim sup, SELA 27ōPE,
lim limsup/| Vo k-000
(1 7)
Proof. From Prop. 2.4.4 of (Bertsekas, 2018a), given V V 1loo S ōpE, and [[Trats Vv TV S &GL
| - V* 5 1o + SGT, + -278pF.
(38)
The result. follows by simply taking lim supp both sides.
23

---

Published in Transactions on Machine Learning Research (11/2022)
Lemma 3.7 (Generalized API(a) bounds). Let V B(S) and policies n. nt' , satisfy the following:
V Vll 1 6PF
|T , V - TV <c - 8GI
म' =at, + (1 - a)
where a E []. Then,
V - Vx 5 -1--0 a a>)ll=== -V + 8ci + 220PE
(19)
1-7
Nexl, consider an APl(a) algorithm that generales sequence of policies { via functions [Vi]keN with policy evaluation error ||V Villx òPE,k, approzimate greedy updates with ervor [T ka, V& - -Ve I &Gr, and policy updates T++1 t g + (1 - a For any E (0,
simsupk-ee ÓGI + 27ōPE. (1-
lim supll 10 S
(20)
k-000
Proof. Let deI + 2ydpE. First, we note that Tv.V aTxx V + (1 a)T,V V for all V E B(S), and prove the following:
(s) Vz (s)} $ ae
(39)
sES
1-7
V -
T V T.p Va
T, V² aT x V= - - a)
a(T,V* V Tx Vz + a1-a) VV
- Sa(T, V Tx V= + supa) - (s))
AES
aTT,V" - VVV + T.V - -T vT + (1- aup (s) - (s)
SES
S <a(1rr + TVV- - -T, yo + (1 - a) sup V*(()) yr (=(s)) (s)}
SES
<a(1ōPE TV Tx V=a) + (1 a sup V (8) V= (s))
(since TV 2 TvV V for all n.)
sES
a(TōPF + -TV - -T V + ng V T n V + (1 a) su (s) V- (s)}
SES
< a(TôrE + dGl + T- T yn ) + (1 - sup V (8) V' V~ (s)}
sES
a(7ôPE dei Tx V- Tx T + T V - TT V (1 at) sup (
(s) sup(
V (=)
eES
S a(22ppe + del + T V - T v= + (1 - sup V (8) - Vー V= (s)}
aES
ale + Tx, 4 - T V= + (1 a) sup (*) (s) Vー (s))
#ES
aa(e /sup V (s) V= (8)) + (1
supt (upp V= (s))
e5s
SES
ae + VV= (8) V= (s)).
sE3
24

---

Published in Transactions on Machine Learning Research (11/2022)
By taking supremum on the LHS and rearranging, obtain (39). Now, we prove (19).
V= = TV* Tx
TVV* aF',, V -11 a)T, V
= =a (TV* = - Tr, Vo +(1 a) (TV* - V
1
2
= -TV* - Tw, V + Ts V - -xx, Va
STV - TT,, V + ssup V
(V*(s) ssup(V
V= (s))
#ES
7ac
S TV Tu V* + 1-7
(due to (39)
-VV Tu V + Txy V Tx V yac
1 y
70E
S TVV T V + yOPF + 1 1-7 7
= TV - TV + TV - T, V + 70PE + 706
1-7
S S>llv* Vo +TV Txp , V 7OPE + yae
1-7
>/VV" - 1 + +VV - TV + TV - Tzy V TÔPF + 7
1-9 7
$ <>/l"* - 1o + 2225P + 5GI + qae
1-7
>>/l'* - V* 1000 E + 7ac
1-7
2 V V + F TTV='
< SI 1 x + V - -T,V*
||V - 100 + +T/ V - -T,V
< V| V + sup (s) V (s))
yae
100 + 1-7 < || V
(due to (39)
Combining the upper bounds of 1 and 2
v va s a <
V |00 + +
7aE
+ (1 (a-aa)(p) 200 (IV* V0 + yae
1-7)
1-7 7
( c+ 1 1-7)
ge
= -11 - 1o +
= =1 - a + an) - +
V*1
ae
1 7-7
which is equivalent to (19). Setting n' = - and म = u,; and taking a lim sup on both sides of (19):
Vo limsup dGL + 2yōPE
lim supps Vo < lim limmsup(1
k4300
k+0
1-7
lim òGLk + 275PE..
a(1 7) limsupll Vo < a 20000
1-?
lim lipsupp- 8G1k + 227PE,, (1 7
+ limsup/|V* 1o0 <
k0000
25

---

Published in Transactions on Machine Learning Research (11/2022)
Theorem 3.8 (API(a) with 7-bisimulation). Under the same conventions Thm. 3.5, let
> log( ( /og(?) and Ca (1 + 7) Given (a(1 G,)(1 7)/2)" for some a (0, X = 0
and any p E [1, o0):
dx. t F(n) (dmz-1)
(21)
S, 42 t Hard Aaareggggga,,, dr, c)
(22)
7T Ovalatevalu Tk)
(23)
7g -
4b
(24)
Wk+1 < (1- a) + agg.
(25)
The sequence {TAlKEN has the following limiting bound,
2y(2E + acn)
lim suppl// - 100 S 71-
(26)
(1-7)3
40000
Proof. First, note that by Corollary A.4, we have (T S a. Now, we define the sequence of metric learning errors {E JENN,
& = || - dral
|F(1)) (Tre dxg 11:00
S Cn F (dmx-1) drp-11 10x--1100 11:00
(by the Banach fixed-point theorem)
Cn (1F (Jma-)) - d 1loc + Id daa-illo)
(dra)))))) - d d 1lo t
Cn
Using shorthand notation d, cR CR Ril + (TW P!) for the r-bisimulation distance between pair of states (s,, 85), and noting cn = 1 by given,
sup
R
R
R
Rd tor cr W (Wp(dre.)) :(Pi, ,t.))
< sup (
| - Ri
++ 1
Ri +
R
(W Th. pi - (d(dFee))(P ( Pii Paa..))
< 2D (Tk, Tk-1) + or sup W, W (Pr p/ P(,)) Wp(dna- Pl. .)
(by Lemma A.6)
< 2a + or
W W Wp((fm-.)PP
T2 P(.) - ( T4-1 pi P
(since DiV ( S a)
in
2a + CT (y (P R Pt + W Wpldmm ((P/ Pha)) + Ild day lloo)
(by Cor. A.2)
2CT
2 +
D20 (TV TK-1) 1) + cr orlldmm- dre_allo
(by Lemma A.7)
--er
2crar
< 2n +
+cr Irl dra .1l
(since E [0, and D TR-1) a)
1-cT cr
2
< 1-
+ +TE
26

---

Published in Transactions on Machine Learning Research (11/2022)
Plugging back in,
2a
& S cn
+ +(1+ (1++T)) cT)
CT
ca
+ CnEk11
1- Cr
a (1 + er)6, < 1, Le., n > log( (oott / log(er); we take a limit superior to obtain:
2x Go
limsup& & S (1-ca)(1-- cr) k-+00
aCpp
where we have defined ā (1-2,)[1-rr)
2a
By Lemma A.8, we have,
2E acn
limsupllV** k-:00
V 0, 00 5 1-7
Then, (26) holds due to (20) of Lemma 3.7 with dGr, ö, Ak and âPE, = 1| VTT Vollle 1000
B Background: State Aggregation Methods
The idea of reducing a large-scale dynamic programming problem into a smaller one via abstractions (or partitions) has rich history going back many decades (Fox, 1973; Whitt, 1978; Mendelssohn, 1982; Bertsekas & Castanon, 1989; Singh et al., 1995; Dean & Givan, 1997; Dean et al., 1997). Broadly, state aggregation approaches in RL can be grouped into two categories: pre-specified and adaptive. Often, pre-specified approaches either compute an aggregation based on transition probabilities and reward functions as in bisimulation (Givan et al., 2003) or assume a priori knowledge about the environment (e.g., the optimal value function). For instance, given some known function f: S A R, instoad of (1) we may write:
((s)) = D(8)) + (f(s;, a) [(8j, a)l < Va E A,
(40)
which results in 7-abstractions of Abel et al. (2016). When f == Q' and = O, the resulting abstraction is called a "Q" -i"iirrelevance abstraction" under the unifying framework of Li et al. (2006). McCallum (1996)
introduced the Utile Distinction Test (in the context of partially observable MDPs), which aggregates states that have the same optimal action and the same stale-action value for said action. Hostetler et al. (2014) investigated similar, more general abstraction in the context of Monte Carlo Tree Search reduce the stochastic branching factor of large MDPs. Jong & Stone (2005) devised abstraction discovery approach based statistical hypothesis testing and policy relevance, illustrated its utility in knowledge transfer to different domains and discussed its connections to hierarchical RT, (i.e., temporal abstraction). Duan et al. (2019) developed a soft aggregation algorithm based on the spectral decomposition of a simulation-baser empirical transition matrix. Bertsekas (2018b) recently surveyed feature- ceature-based aggregation methods (for an early example, see Tsitsiklis & Van Roy (1996)) and discussed their use APT. Van Roy (2006) analyzed approximate value itcration (AVT) under state aggregation. In general, whenever VFA is done via picco-wisc constant function approximators, state aggregation is implicit among states that are assigned the same value.
More closely related to this work, adaptive approaches simultaneously improve policy and learn efficient abstraction that changes as the algorithm runs. A notable carly example is the work of Bertsckas & Castanon (1989), which adaplively aggregates slates to minimize the variation in Bellman residuals per partition. Baras & Borkar (2000) developed a simulation- based actor-critic approach that alternates between frequent updates a lincar approximation of the value function and infrequent updates to abstractions based on clustering the range of estimated values. Ortner (2013) developed an online aggregation algorithm based on the UCRL algorithm of Auer et. al. (2008) and provided regret analysis. The approach of Sinclair al. (2019)
27

---

Published in Transactions on Machine Learning Research (11/2022)
similarly motivated, but focused on Q-learning. Chen et al. (2021) recently proposed an aggregation-based AVT algorithm that combines infrequent Bellman updates over the ground space with frequent updates over a reduced space that is computed via value- based aggregation. Differently, our approach does not require any value iteration updates in the ground space, which may be contimuous.
C Sharpness of the Sinkhorn Distance as a Wasserstein Distance Upper Bound
The Sinkhorn distance forms an upper bound on the Wasserstein distance due to an imposed on the cost minimization problem. Guided by information-theoreti intuition, we perform empirical tests to investigate the quality of this upper bound as a function of the underlying marginal distributions (2), First, we highlight the intuition with the following lemma.
Lemma C.1 (A condition for equality of Wp and WÇ). Let H(H) denote the Shannon entropy of a random variable with lawo p. Under the some conventions (7),
minmmi((ii) H(p2)) = W (d)((1))))) Wp(d)(uu,
(41)
Proof. Consider joint distribution w with marginals μ1 and u2z Recall the following information iiformation-thhoretice inoqualities (Cover, 1999):
H(w)= S H(m1) + H(22)
(42)
H(w) 2 H((r)
(43)
By symmetry of (43),
max(H((n)), H(p2)) & H(w) S H(p)) + H(w2) max(H((n)), H(pz)) & H(w) S max(H((m1) H(p2)) + min(H(p11, H(uz)).
(44)
(45)
That is, the range of allowed entropy values for joint distribution w with marginals μr and μi2 is determined by the minimum entropy of the two distributions. For example, suppose Yr (xx,)= = 1 for some in a finite space and 0 elsewhere, so that H(41) 0. The feasible set of transport plans between μn and μ2 collapses to a single joint distribution that moves all the probability mass at x; to match the distribution of μ2. Indeod, in this case we have H(w) = H(m)) + H(w2) = H(12) with equality for both the lower and upper bounds shown in (45).
Now, consider the relative entropy-constrained set of joints P(()) from (7):
(KI,W |l di @ 22) S s(-1
-(WWw) + H(m)) H(p2) SC-
+ H(w) 2 H(m) + ((()))-(" + H(w) 2 max(H( H(r2)) + min(?((u1); H(w2)) 1-
Given the information-theorett lower bound in (45) that readily applies to all w E S2 we conclude that whenever ç-1 2 min(H(()1) H(Hz2) we have f 2()), which implics oquality between Wp and WC. p
As discussed in the proof above, the range of allowed entropy values H(w) shrinks with smaller minimum entropy min(H((pi) H(22)). H(z))) Consequently, as min(H((1), H(x2)) 0 we have Q(() + Q for all Ç due to (41). We suspect that the converse may be true; that with increasing min(H((m)) H(Hz)) the feasible set 2(C) might be smaller subset of Ω, which would imply that the quality of the Sinkhorn distance Wasserstein distance upper bound degrades. We perform empirical tests to compare the W distance to a stronger upper bound on the I-Wasserstein distance computed via a smaller X' = 0.02 < X. We randomly sample probability vectors μ1, H2 from the 31-simplex and ensure H(m1) S H(H22 where H(m)) takes values within 0.01 of those shown on the z-axis of Fig. 6. Similarly, H2 is sampled to evenly cover the range of allowed values H(pz) E 5)). To construct distance matrices, we sample 32 points uniformly on mx 32) dimensional spheres with radii 0.5 and take pairwise Euclidean distances. As seen in the
28

---

Published in Transactions on Machine Learning Research (11/2022)
Marginal Entropy Relative Error (A- 0.1,0' -,00007
Marginal Entropy Relative Breor (A- 3.0,A' 0.002
Marginal Entrapy vs. Relative Error IA a. 0.02
(140 -P5 (009
62-
16
23
20
45
16
24
3.8
40
13
20
miniillgl Maae)
miniHiig) Min!
mini2 Milyl
Marginal Entropy vs. Relative Error (A -.1.''-0.00 0.02
Marginal Entrapy vs. Relative Error (A 1.0.8 0.02
Marginal Entropy vs. Relative Error 1A ", 0.02
6.0
66
W0 1999
co0y) 199 yeey"
6.65
63-
0.0
28
A.
minthiaa MEAu)
mintHlja)) Mi0ul)
Marginal Entropy 0 0.021
Marginal Entropy
0.021
Marginal Entropy Error
8.10
102 100g
0.19
0.12
0.08
0.000
0.00-
[00)
0.15
649
600
0.000
6.00
min/Heual. Man1)
Miae)
Mbai)
Figure 6: Measurements of relative error against minimum marginal entropy with varying À E {0.1, 1, t0 (left-to-right) and ambient space dimuensionality mx E {2, 8, 32) (top-to-bottom) Each individual box corresponds to 1000 pairs of (2) with 20 and 50 samples of probability vectors bn and μ2.
bottom-left corner of all plots, we have strict equality Wi = WV for all settings with H(m1) as predicted by (41). Furthermore, we observe monotonic relationship between H(m) and the expected quality of weaker metrics W across all settings of and mx, the latter of which controls the distribution distance values.*
Implementation Details
D.1 Warm-starting Sinkhorn distance computation
Recall from Cuturi (2013) that by Sinkhorn's Theorem (Sinkhorn, 1967) the unique optimal transport plan w* for the reguaie-e problem for a finite space with e elements can be written in matrix form diag(u) ()digg))))) where u, TRC and K,j -dd(a,,,s) Then, one iteratively updates vectors and in alternation to satisfy the marginal constraints on and column sums. The standard implementation of this algorithm in the Python Optimal Transport package (Flamary et al., 2021) initializes u and v to be 1//6. In our case, the sequence of Sinkhorn problems being solved follow a structure: (i) for each of n fixed-point updates Fr (dz) we compute W (Txx) (s,))) for all stale pairs (8,, 8y), and (ii) after n updates, we update the policy æ. Since F. is contractive, the consecutive metrics approach one another as we apply the mapping Fg. Thus, the solutions shall also approach one another considering Lemma 3.2.
8The distribution pairwise distances for uniformly sampled points on a unit n-sphere approximately follows A( + (Wu al., 2017). case, the distribution becomes incressingly concentrated around v2/2 with increasing m.x
29

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm é-aggregation for finite 8
Distance matrix D E IR R|
Require:
aggregation threshold 6 2 0
num num_neighbours - D S
partitions +
assigned t zeros S))
while assigneddi [S] do
arg max, (ww.xunn.nniiihhburrr
Greedily select medioid index.
assigned[m] 4
members + argwhere, (Dmj S and not assigned(j)
partition + [m] members
> List concatenation. b All new members of the partition marked assigned. Assigned elements should not be selected as medioids. D Append partition to partitions.
jasigne|mmemberg
num num_ wwm_neigabbourrpprtttt.ooo -
partitions < partitions [partition]
end while
S + length(partitions) 4 < zeros([S] (1)
for j in [I,..., [8]] do
for i in partitions[j] do Ø + end for end for
return e (0, 131s1/3
A similar observation can be made about small policy updates, which likely change the fixed-point metric only slightly (e.g., see Lemma 3.6). Inspired by Ferns et al. (2006), we exploit this structure by saving the final vectors Ui and V,y for all state pairs (s), 8y) and initializing each run of the Sinkhorn- Knopp algorithm with the most recently saved (u:j. Dsy) for the corresponding pair states. This results in up to an order of magnitude improvement in wall-clock time as shown in Fig 5.
D.2 An algorithm for hard aggregation for finite S
Algorithm 1, we provide the simple greedy algorithm that we used for partitioning a finite space given pairwise distance matrix and a threshold c. The algorithm counts for each state the number c-close states and greedily assigns partition medioids based on this simple heuristie. Each partition contains medioid and its c-neighbours which have not been previonsly assigned another partition. While the algorithm itself is not necessarily optimal, we showed empirically in Figs. and 3 that with good enough metric it recovers the ground-truth partitions and is therefore sufficient for our purposes.
E Bisimulation Distance vs. Absolute Value Difference
In Figs. 1 and 3, we measured max.,5' [..(s) (') (V* - V*((')) over time-steps l as proxy for VFA capabilities of the running bisimulation metric. While the true r-bisimulation metric d; provably satisfies (V" s') = (V* 4d (s')) S (s, we only approximate with fixed-point updates after each policy update. As such, å may under-ostimate (s, s') especially early in training since we initialize do 0. In Fig. 7, we show box plots of (s, 8') - AV*(s, over time to investigate this behavior. In particular, run the API(ag) algorithm on the first MDP with X (0.25, 2.0, oo), n E (1,5),c 0.1 and max(0.01, A -0.8). We only run the algorithm for 200 steps here since the metric stabilizes by then. We observe that for 1, the approximate metric d, starts to over-estimate (V* 8') within the first 30 steps as the metric approaches the fixed-point metric d; In contrast, when = 5 single API step is sufficient for dz to exceed AV* (8, As expected, we find weaker upper bound AV*(s, (s, (s) with increasing X.
30

---

Published in Transactions on Machine Learning Research (11/2022)
A alra over AM
216.21 de%l.. 2 over stags
2 deft. 20 uvd All stapo
9U06a) AV Ou deat AP deass
1.5
40K 1000--0ML.1
1.00
0000
Figure Approximate bisimulation distance vs. the absolute value difference over time for n 1 (Top) and n 5 (Bottom) with varying À E (0.25, 2.0, оo) (left-to-right).
S.S.
Stute
Figure 8: Value functions for the first and second MDPs from Sec. (Left, Middle) and randomly gener- ated MDP from Appendix F (Right) after 1000 steps of training with X oo and 30-medioids partitioning.
F An Additional Class of MDPs
In this section, repeat some of the main experiments in Sec. 4 for new class of randomly generated MDPs. As before, have 20 equivalence classes (ECs) and 200 states. Each equivalence class B, is assigned an optimal action aj E A where [AI 10 and j = i % 10. Tf the agent takes the optimal action in B, the MDP transitions to B, with probability 1 - where
U(0, 0.25), except in Bm the agent stays in Bm with probability 1- Pm- With probability Ps, the agent transitions to a randomly selected EC other than B, and B4+1- Taking any of the non-optimal [A] actions transition the agent back to B₁ from any B, with probability As before, transition probabilitics from a state 8; to given EC are sampled uniformly from the ([8)/m- simmpex.. The agent collects unit reward only when it takes the optimal action in B
In Fig. 8, we illustrate the value functions corresponding to the MDPs analyzed in Sec. 4 and the MDP discussed here; the approach here with randomly sampled transitions results in irregular step sizes between ECs for V*, although value equivalence is preserved within each EC. The task is rendered more difficult since many states in different ECs have similar values and the importance of more precise metrics for VFA is highlighted. Indeed, we observe that æ significantly underperforms the optimal policy in this case and the bisimulation- based approximation Vi of ya has high error particularly for FCs with small value difference.
31

---

Published in Transactions on Machine Learning Research (11/2022)
Nerra Infermaten
Nerbbur of pe & under
PLAY y 115
Nerralloed Information
Number saritions E unnder
2-22
2--27
MCG
187
AP
Figure Ablations of a (Top) and A (Bottom) for the third class of MDPs introduced Appendix F.
Namna lard Marred vésemattrr
J=
64
127
100
Figure 10:
Ablation of X for the new class of MDPs in the limited representation capacity setting, where Algorithm 1 is replaced with 30-medioids partitioning.
In Fig. 9, ablate and À for this new class of MDPs and observe similar results to Sec. 4. Namely, we note belter asymplotic performance but slowed down progress with smaller a. While the setting X does not influence performance, lower X produces better metrics and a more efficient partitioning. Lastly, in Fig. 10, we repeat the experiment shown in Fig. where the number of allowed partitions is limited to 30. We again obtain qualitatively similar results with lower À producing a higher quality metric and better policy.
32


Reviews:
[{"review_id": "GLrq3jL9nd", "reviewer": "Reviewer_wUnf", "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\n- Overall the paper is very well structured. The writting is extremely clear the authors do a good job of explaining each step before diving into the mathematical details. The experiments are done rigorously and they accompany the algorithmic contributions well. Moreover, using conservative updates along with an analysis on different distance metrics is an important direction for improving practical algorithms, and the paper does a good job at making this connection clear.\n\nWeaknesses\n- Extensions to API($\\alpha$) seem straightforward, as do the convergence proofs for the Sinkhorn Bisimulation versions. Therefore, I would not cast the paper as doing something super novel. But maybe that's not the aim of the paper as well and I think that does come across well. More importantly, I would have liked to see the benefits of better distance metrics as well as conservative updates for neural network architectures, since a large portion of the paper is inspired by DBC and MiCO. \n\n*Just wanted to note that DBC has been recently shown to not reproducible in many recent papers, and seems to have very poor performance for most tasks. I note this only because the authors mention the connections to DBC quite often.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "This paper introduces a general family of bisimulation metrics, based on Sinkhorn distances. Sinkhorn distances generalize Wasserstein distances through entropy regularization, and come with certain benefits such as faster convergence. The paper then builds an approximate policy iteration algorithm that uses state aggregation based on the previously introduced bisimulation metrics. The authors then extend this algorithm to a conservative policy iteration variant, which is useful when warm starting the distance metrics. This is followed by empirical analyses on small, finite state MDPs (<500 states) to confirm the faster convergence benefits of using Sinkhorn distances as well as stability benefits offered by the conservative policy iteration version.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I would like to have seen some experiments on pixel-based domains with changes inspired by the different distance metrics and using conservative policy gradient algorithms such as TRPO/MDPO. Having said that, I think the paper in its current form is still complete and warrants a clear acceptance.", "broader_impact_concerns": "I do not think the paper's contributions directly cause any ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6xdP5CiaDk", "reviewer": "Reviewer_PeHo", "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:\n\nI find the conceptual contributions of the paper to be interesting, creative, and relevant to the community. The paper is very well-written and organized, giving clear explanations and detailed, yet easy-to-follow theoretical analysis. I read through most of the proofs and did not find any major issues; the paper extends and generalizes classical theory from the ADP literature (e.g., those found in Bertsekas textbooks) in an elegant fashion.\n\nWeaknesses:\n\n[1] There could be a discussion to other forms of adaptive aggregation that are not necessarily based on bisimulation. There was little discussion in this direction in the literature review and as a reader, I would’ve liked to get a better understanding of when to apply certain methods. A recent example is https://arxiv.org/abs/2107.11053.\n\n[2] The empirical results use \\gamma = 0.9. My guess is that the theoretical bounds become impractical as \\gamma -> 1 due to the (1-\\gamma)^(3 or 4) terms in the results, but it would be nice to know how the empirics change with high \\gamma.\n\n[3] There is little discussion on where/when to apply this algorithm vs other types of aggregation or approximate DP / RL approaches and there is no comparison to any baseline algorithms (with the exception of, perhaps, MICo). It makes it hard for the reader to gauge when this approach is practically useful. Note that I am not advocating for a gigantic empirical section with comparisons to everything, but there should at least be a few naive baselines.\n\n[4] Discussion on how to choose $n$ and the case of default API (n=0?). The practical question becomes: given a fixed amount of computation, how much effort should go toward the bisimulation part and how much effort toward the API part? One special case, at least for the finite state / action case, would be no aggregation and just applying default API.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "This paper makes two main conceptual contributions: \n\nFirst, the authors give a generalization of bisimulation metrics, which is defined using the 1-Wasserstein distance, to the cases of p-Wasserstein and Sinkhorn distances. The benefits for doing so are due to improved computational costs (S^2log(S) instead of S^3log(S)).\n\nSecond, the authors propose an approximate policy iteration (API) method that makes use of \\pi-bisimulation to conduct a form of adaptive state aggregation. The essence of the method is that on each iteration, it first uses the current policy \\pi_k to compute the \\pi_k-bisimulation (using n iterations to compute the fixed point), and then applies the evaluation and improvement steps on an aggregated state space implied by the bisimulation metric.\n\nThe other contributions are:\n\nAn extension of the new API algorithm that makes smaller / smoothed updates (specified using a parameter \\alpha). This is based on the API(\\alpha) algorithm from Bertsekas, 2018.\n\nEmpirical investigations: (1) of \\alpha, showing that setting it to a large value initially and then decreasing it with iteration is a promising strategy, (2) of the parameters used in the Sinkhorn distance, (3) walltimes for different values of \\alpha, resulting in the observation that smaller \\alpha means similar bisimulation metrics and therefore higher value to warm-starting.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "The numbers below reference the weaknesses section.\n\n[1] Critical\n[2] Would strengthen\n[3] Would strengthen\n[4] Would strengthen", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Lj3jOv0i8x", "reviewer": "Reviewer_7DzN", "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": "I found this paper to be very well-motivated and well-written. The authors are building on prior work in bisimulation-based metrics and nicely extend existing results in a more generalized manner. I particularly appreciated the finding that, under the Sinkhorn formulation with parameters $(p, \\zeta)$, one can recover bisimulation metrics with $(p, \\zeta) = (1, 0)$ and MICo with $(p, \\zeta) = (1, \\infty)$.\n\nIn general, I found the discussion around their theoretical results very useful, and helped highlight their significance.\n\nI found the empirical investigations well-structured, and effective at validating the insights from the theoretical sections.\n\nI found little to fault, but here are a few minor suggestions:\n\n1. It would be nice to use hyperref throughout so that the reader can click through the citations and equation/figure references.\n2. Remove the period after \"_compact_\" in the the third line of section 2.1\n3. In section 3 when discussing \"policy oscillation\", this recent work could be of interest: https://arxiv.org/abs/2206.00730\n4. Minor nit in page 8, where DBC and MICo are listed as \"such actor-critic approaches\": neither are limited to actor-critic methods and can be applied to value-based methods (in fact, most of MICo's experiments were on value-based methods).\n5. It would be useful to specify what is being measured in each row in Figures 2 and 3.\n6. The first sentece of section 4 would read better as \"In this section, we conduct experiments to _empirically_ investigate the ... results in Sec. 3.\"\n7. In section 4 I would choose a different word than \"booted\", which sounds too informal. Just \"transition\" maybe?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "This paper reformulates bisimulation and $\\pi$-bisimulation metrics in a more general form via Sinkhorn distances. The authors demonstrate that this reformulation recovers traditional bisimulation metrics as well as a recent behavioural metric (MICo, from Castro et al., 2021) as extreme points of one of the parameters for Sinkhorn distances.\n\nUsing this more general form, the authors define an approximate policy iteration procedure which uses these metrics for state aggregation; they prove performance bounds, as well as convergence results when improving policies and metric approximations concurrently.\n\nFinally, the authors present empirical validations of their theoretical work on a series of controlled experiments.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "See suggestions above.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers vote for a clear accept, while any concerns with the original submission have been addressed in a revision in the meantime, so that I recommend to accept the paper in its current form. 
Decision: Accept (poster)