A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
Authors: Zhenyu Tao
Wei Xu
Xiaohu You
Venue: NeurIPS 2025 poster ()
Keywords: Markov decision process
reinforcement learning
bisimulation metric
Primary area: reinforcement_learning
TL;DR: Established a generalized BSM of state similarity between MDPs, backed by rigorously proved properties, which is applied to derive improved theoretical guarantees for policy transfer, state aggregation, and sampling-based estimation in MDPs.

Abstract: The bisimulation metric (BSM) is a powerful tool for computing state similarities within a Markov decision process (MDP), revealing that states closer in BSM have more similar optimal value functions. While BSM has been successfully utilized in reinforcement learning (RL) for tasks like state representation learning and policy exploration, its application to multiple-MDP scenarios, such as policy transfer, remains challenging. Prior work has attempted to generalize BSM to pairs of MDPs, but a lack of rigorous analysis of its mathematical properties has limited further theoretical progress. In this work, we formally establish a generalized bisimulation metric (GBSM) between pairs of MDPs, which is rigorously proven with the three fundamental properties: GBSM symmetry, inter-MDP triangle inequality, and the distance bound on identical states. Leveraging these properties, we theoretically analyse policy transfer, state aggregation, and sampling-based estimation in MDPs, obtaining explicit bounds that are strictly tighter than those derived from the standard BSM. Additionally, GBSM provides a closed-form sample complexity for estimation, improving upon existing asymptotic results based on BSM. Numerical results validate our theoretical findings and demonstrate the effectiveness of GBSM in multi-MDP scenarios.

A Generalized Bisimulation Metric of State Similarity between Markov Decision Processes: From Theoretical Propositions to Applications
Zhenyu Tao, Wei Xu, Xiaohu You Southeast University
Purple Mountain Laboratories (zhenyu_tao, wxu, xhyu] eseu. edu. on
Abstract
The bisimulation metric (BSM) is a powerful tool for computing state similarities within Markov decision process (MDP), revealing that states closer BSM have more similar optimal value functions. While BSM has been successfully utilized in reinforcement learning (RL. for tasks like state representation learning and policy exploration, its application to multiple-MDP scenarios, such as policy transfer, remains challenging. Prior work has attempted to generalize BSM to pairs of MDPs, but lack of rigorous analysis of its mathematical properties has limited further theoretical progress. In this work, we formally establish a generalized bisimulation metric (GBSM) between pairs of MDPs, which is rigorously proven with the three fundamental properties: GBSM symmetry, inter-MDP triangle inequality, and the distance bound on identical state spaces. Leveraging these properties, we theoretically analyse policy transfer, state aggregation, and sampling- estimation in MDPs, obtaining explicit bounds that strictly tighter than those derived from the standard BSM. Additionally, GBSM provides a closed-form sample complexity for estimation, improving upon existing asymptotic results based on BSM. Numerical results validate our theoretical findings and demonstrate the effectiveness of GBSM in multi-MDP scenarios.
Introduction
Markov decision processes (MDPs) serve as foundational framework for modeling decision-maker making problems in Reinforcement Learning (RL) M To enable efficient analysis of MDPs. Ferns al. 2 proposed the bisimulation metric (BSM) based on the Wasserstein distance, also known as the Sentorovicc-Rubinssee metric, quantify state similarity in aelicy-ineeeeneent manner. BSM provides theoretical guarantees that states closer under this metric exhibit more similar optimal value functions. Meanwhile, BSM a pseudometric
satisfying: (1) Symmetry: d(s, s') d(s',s), (2) Triangle inequality: d(s, s') < d(s 8") d(s" s'), and (3) Indiscernibility of identicals: 8 s' s'= 8/) = 0. These three properties, combined with BSM's measuring capability on optimal value functions, have driven its applications across diverse RL applications. It has been successfully employed in state aggregation
[4,5), 5), representation learning 6 7l. policy exploration [8] 91, goal-
conditioned RL [10,, safe RL [11]. etc.
However, since BSM is inherently defined over a single MDP, its application to theoretical anal- yses involving multiple MDPs faces notable obstacles. For instance, Phillips [12] applied BSM to policy transfer by constructing a disjoint union of the source and target MDPs' state spaces. While this allows inter-MDP comparisons through BSM, the disjoint union enforces zero transi- tion probabilities between states across the two MDPs. Consequently, this method fixes the total variation distance between their transition probabilities at one, hindering further simplifications and
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

analysis. It necessitates iterative calculation of distances across the entire state space, leading to prohibitive computational costs in deep RL tasks as noted in [T] Also, in order to compute state similarities in continuous or large-space discrete MDPs, Ferns et al. [1]] proposed a state similarity approximation method through state aggregation and sampling-basd
estimation. Although they proved the convergence of approximated state similarities to actual ones by leveraging properties of BSM and the Wasserstein distance, their approach only derived a fairly loose approximation error bound and failed to obtain explicit sample complexity (i.e., the lower bound on the number of samples required to achieve the specified level of accuracy) for the estimation error. Specifically, the estimation error bound (see Eq. 7.1 in [14) depends on the former aggregation process, resulting in an asymptotic sample complexity rather than a closed-form expression. In addition, for representation learning, Zhang et al. [6] and Kemertas and Aumentado-Ammstrong Armstrong [15] leveraged BSM to establish value function approximation bounds under optimal and non-optimal policies, respectively. However, BSM-based analysis between the original and aggregated MDPs results in loose bounds, particularly
with large discount factors.
Several works have attempted to extend the definition of BSM for evaluating similarity between multiple MDPs [6-18]. Notably, when extended to multi-MDP scenarios, this modified version of BSM loses its pseudometric properties, as s and s' in d(s, s') represent states in different MDPs. To the best of our knowledge, prior works have typically extended the single-MDP formulation to two MDPs, without rigorously retaining the metric properties. Specifically. Castro and Precup [66] utilized its evaluation capability on optimal value functions to analyze policy transfer. Due to the lack of metric properties, the derived theoretical performance bound is limited to transferring the optimal policy within the source MDP, as it can only reflect the effect of one-step action rather than the long-term impact of the transferred policy (see Theorem 5 in [16).. While Song al. 117 successfully employed such a modified BSM in assessing MDP similarities and improving the long-term reward in policy transfer, their investigation focused on empirical validation rather than in-depth theoretical analysis. Furthermore, a comprehensive survey on various state similarity measures between MDPs [8], which highlighted the modified BSM an effective approach, also emphasized the limited theoretical guarantees in current methodologies. This raises the following two questions:
Q1. Does the modified BSM possess any metric properties when computing state similarities between multiple MDPs, akin to the pseudometric properties of BSM within a single MDP?
Q2. If so, how can these properties facilitate the theoretical analysis involving multiple MDPs?
To answer Q1, we present a formal definition for the modified BSM in multi-MDP scenarios, which we refer to generalized BSM (GBSM), and rigorously establish three metric properties that align with the pseudometric properties of BSM. These properties are summarized as (1) GBSM symmetry, (2) inter-MDP triangle inequality, and (3) the distance bound on identical state spaces. To answer Q2. we upply GBSM in the theoretical analyses of policy transfer, state aggregation, and sampling- -bsed estimation of MDPs, yielding explicit bounds for policy transfer performance, aggregation error, and estimation error, respectively. Notably, when the compared MDPs are identical, the error bound of GBSM reduces to the error bound of BSM for a single MDP We prove that the GBSM-deriver bound is strictly tighter than the bound directly obtained from BSM, along with an explicit and closed-form sample complexity for approximation that advances beyond the asymptotic results of [4]. Numerical results corroborate our theoretical findings.
2 Background
Before describing the details of our contributions, we give a brief review of the required background in reinforcement learning and the bisimulation metric.
Reinforcement Learning We consider an MDP AS, defined by finite state space S, a finite action space A, transition probability ()))s, (a E A. {3 E S, and denotes the next state), reward function R(s, a). and discount factor y. Policies (T-ss) are mappings from states to distributions over actions, inducing a value function recursively defined by V*(s) := Exoxx(-e)) [R(s, a) + 7BBa-p(-la.a) [V* (s)]] .. In RI,, we are concerned with finding the optimal policy nt = arg max, V",, which induces the optimal value function denoted by V*.

---

Bisimulation Metric Different definitions of BSM exist in the literature 2 4 14 In this paper, we adopt the formulation from setting the weighting constant its maximum value c 7. The BSM is then defined as:
(s, s') max (|((s. R(s', + P() a); Vs, E S.
(1)
Here, Wi is the I-Wasserstein distance, measuring the minimal transportation cost between distri- butions P(-|s, a) to P(-|s'. a), with d² as the cost function. Ferns et al. [2] showed that this metric consistently bounds differences in the optimal value function, i.c., (V)))) V*((') S (s,
3 Generalized Bisimulation Metric
We now present formal definition of the proposed GBSM and derive its key metric properties. Definition 3.1 (Generalized bisimulation metric), Given two MDPs M1 (S1. 11, R1, n) and
M2 = (S2, A, P2, R2, 7), the GBSM between any state S1 and any state E S2 is defined as:
di(s M2) = max {[Ri
(8, a) R2(s', a)l + (Pr P2(-16' a); ) (2)
For notational simplicity, we use 2 s') to denote ([(s (s. (2)), where the superscript 1-2 indicates the direction of GBSM from Mi to MM. Before proving the existence GBSM, we first introduce the Wasserstein distance [1]], which is defined through the following primal linear program (LP):
Wi(P,Q;d) min Σ S11
Σ
(Sal
Nigd (s1,
j=1
(3)
1 ~ (s.), Vi Σ Sil
subject
A = Q(ss) Vj; 2 0, Vi,j.
Here, P and Q are distributions on S and S2, respectively, and 8; E E1,5; S2. represents the minimum transportation cost from P to Q under cost function d S1 S2 R4, and is equivalent to the following dual LP according to the Kantorovich duality [20]
1811 max Σ PsP(ss) Σ S> a.
Wi(PQQ:d)
(s)(s
(4)
subject to 14 - Ug S d(s,, 8,), Vi
Then the existence of such d satisfying Eq. is established by the following theorem.
Theorem 3.2 (Existence and convergence of GBSM). Let d be constant zero function and define
d2.2 (s, max [R, R2(s', a)l WF (1)s. P2(15'
a) d2 ()) neN (5)
Then d=.2 converges to the fixed point 2 uniformly with co. Let R max,, (s, R2(s', a)), and the convergence of dl.2 to d satisfies
d 2 8') 2 S R/
6
Proof Sketch. The existence of d is established through the fixed-point theorem 21 and the definition of the Wasserstein distance, similar to the proof of BSM in (2). The convergence is proved via the LP and induction. (See Appendix A for the complete proof.)
Similar BSM, which evaluates the state similarity through the optimal value function, GBSM naturally bounds differences in the optimal value function between two MDPs.
Theorem 3.3 (Optimal value difference bound between MDPs). Let V and V denote the optimal value functions in Mi and M2, respectively. Then the GBSM provides an upper bound for the difference between the optimal values for any state pair (8, 8') E S1 x Sz:
(V](ss) Vg (s.
3

---

Proof Sketch. We first construct a recursive form of the optimal value function by (() = max, (R(s,a)+ + (( [v(=-1) (8)] }. with base case (s) = 0 and lim,- (s)
V The proof proceeds by induction on n. The key insight is that (sx)) Sil and
(Sal (st)) k- form feasible, but not necessarily the optimal, solution to the dual LP in for Wi (PI( P2 a); d), (See Appendix B for the complete proof.)
Now, we start to establish the three fundamental metric properties of GBSM, which we term GBSM symmetry, inter-MDP triangle inequality, and the distance bound on identical state spaces. These properties are designed to align with pseudometric properties of BSM, including symmetry, triangle inequality, and indiscemibilitty of identical.
Theorem 3.4 (GBSM symmetry). Let dl-2 be the GBSM from MI to M2, and de-1 be the GBSM in the opposite direction, then we have
(8, (5', v (8,8') E x S2.
(8)
Proof. This property can be readily proved through induction. We have [R a) (2(s',a))
[R2(s'. a) R1 (s. a)l for the base case. With the assumption of d, s",'" ( s), we
have W1 (-
P2(1s', db?? = Wi (P2(-1s', a), F1(-|s, a); de:l). and from (5) we have
( 1++1 (s,8) 8) = det ()..)) It is therefore concluded that d,,2(s, 8') = (s',8) for all n E N
and (s, s') E S1 x S2. Taking n + do yields the desired result.
Theorem 3.5 (Inter-MDP triangle inequality of GBSM). Given MDPs M1 = (SI. R1.7),
M₂ = (S2, A. P2, R2, ?), and M3 = (Sa. A. P3 R3, 7). GBSMs between the three MDPs satisfy
2s s') S (s , v (s,s', s''s',s") S₁ x S2 x Sz.
(9)
Here, the GBSM between any two MDPs can be arbitrarily reversed according to its symmetry.
Proof. First, we need to prove the transitive property of inequality on the Wasserstein distance, that is, the Wasserstein distance between the three distributions follows W (IPP!, p2; d <W (IP [p: dd33)- Wi (P= d8-2) if (9) holds, where pl,, p2, and pd denote arbitrary distributions on S,, S2, and Sa.
Let (st, SJ. 5k) S x S2 x Sz. Define 1.3 the optimal transportation plan for Wi (IP) P33 d 1.3 = (s:) and [ A = (sx)- L
in primal LP with elements 2 satisfying 1
Similarly define X for WIPP3, ..::pdd 22 with elements X Construct X 1,3.22 with elements X 1.3.2
satisfying Σ == A
|22 1.3.2
X and DSS 1.3.2
Such a A 1.3.2 does exist according to the
Gluing Lemma in 22
Then, note that
|Sal
|Sal
133,2
Σ
[Ssl
N.K = P((s)):
N=
Sal
1,3,2 L.k.
1sl
3,2 Ak.j
= (s)),
thus Σ Sal A 1,3,2 is feasible, but not necessarily the optimal, solution to the primal LP in (3) for k=1
(P p². 2). Consequently, we have
Wi (PP, p2; 222)
<
151
S2l
Ssl
N,kij
1.3,2
1- (s),
k=1
(a)
Σ i=1
18
S21
1aal
113,2
( sk) + d 2 8;))
X.kkj
k=1
Σ
18,1
Sal
1.3 (s sk))
Sal 1Sal No 2-2 2=2 8,) (5k
1=1
A=1
Wi (P..
(P
+ W1 (P3) 22; 2
(10)
Here, step (a) stems from the assumption on d. We have now established the transitivity of the inter-MDP triangle inequality on the Wasserstein distance.

---

Armed with (0)), we are ready to prove the inter-MDP triangle inequality of the GBSM through induction. For the base case,
(s, S max, (s, - (((ssaa)Ra(s",,,
[Ra(s" (a)(sss")=)))))) Ra(s'a)))
I max (R Rs ._") a)ه} + max [a(s"" .a) R2(s', a)]l}
(s, d (s", s'), A s 5)) E S1 S2 Ss.
By the induction hypothesis, we assume that for an arbitrary n E N,
(s, S dh (s, + 2 5), V (s, , 8") E S x S2 x S3.
The induction follows
1 8')5 max () Rs a) +
R2(8',0 a)) + (Ps(+|s", P2( a): })
(,W((F((Hss.))
S max
- (((" [10 :)
+ [|
R2 ( 77 (P P2 a): }
=d (s. (s. d (s" , 5) A (s,s',"'") S x S2 x S3.
Here, the first inequality follows from (10) i... the transitivity of the inequality. Now we have (s, & (s, s") + (s" s')
for all n E N. Taking n - 20, we establish the inter-MDP
triangle inequality of GBSM.
Since the identical states only exist within the same state space, we establish the distance bound only when Mi and MM share the same state space S. This property is formulated as follows: Theorem 3.6 (Distance bound on identical state spaces). When M1 and M2 share the same S.
1 max [I[((..)) R2( RR 1-7 TV (Pi a) PP((-1s (a)(lss a)) }. (11)
max d (s,8)) S T- 8.0.
where TV represents the total variation distance defined by TV(P, = E.es Q())
Proof. Consider a special transportation plan between distributions P and Q. This plan preserves all s. The remaining mass, where P(s) > Qss). is distributed to states where P(s) < (()). Then the total mass to be transported is quantified by the total variation distance, where the transportation cost with the cost function d is bounded by a d(s, s'). The shared mass is given by 1 - TV(P, Q), with the cost bounded by max, d(s, s). While this plan adheres to the definition of Wasserstein distance, it can hardly be optimal. Then we have
mass shared between P and Q, defined as min P(s), Q(5) for all
(P d) S TV(P, Q) max., d(s, + (1- max, d(s 8). According to its recursive definition, GBSM is a mapping bounded by [0, R/(1 7)], then max, d² (s, 8)$ max {s a) - R2(8, a)l + TPVV a), P2 a)) max,,5' d² (x,(6s))))
(12)
+ {(1 - TV a), P2(1,))),,,,).). a))) max, dl (s,
RR <max { (s) a) 7 (P
} +7 max d (s,
5,a
Rearranging the inequality yields the desired result.
A direct consequence of Theorem 3.6 is that if M1=Ma, where R1 = Ro and P1 =P, the right-hand side of the inequality becomes zero. It indicates that
d s) = M1), (s, M1)) = 0, Vs e St,
(13)
confirming the indiscernibility of identicals of GBSM when the compared objects -state-MDP
pairs) are genuinely identical. We denote the maximization term max.{/ (8, a) - R2 a)l +
xft r-y (V( (-1s, a), (P2(-1s,a)) in Theorem 3.6 as dit s) in the following.
We now have formal definition of GBSM and have rigorously proved the metric properties. Notably, when all compared MDPs are identical, GBSM reduces to the standard BSM. this case, the three fundamental properties of GBSM reduce to the corresponding pscudometric properties of BSM.
5

---

4 Applications of GBSM in Multi-MDP Analysis
To demonstrate the effectiveness of GBSM in multi-MDP scenarios, we apply it to theoretical analyses of policy transfer, state aggregation, and sampling-base estimation of MDPs.
4.1 Performance Bound of Policy Transfer Using GBSM
Using GBSM, we analyze policy transfer from source MDP M₁ target MDP MM and derive a theoretical performance bound for the transferred policy. This bound takes the form of a regret (defined as the expected discounted reward loss incurred by following the transferred policy instead of the optimal one [23]). Specifically, it is a weighted sum of the GBSM between the two MDPs and the regret within the source MDP itself, formulated by the following-
Theorem 4.1 (Regret bound on policy transfer). Consider transferring a policy n. from Mi to M2. The transferred policy acts as (slf((s)) for s' E S2, where f S2 - S1 a mapping from target states to source states. The regret of a in M2 is bounded by
2 max d E'E
1 1+
(z) Vz E88
max
d (f(s')
max (V) VV') (14)
1
aESi
Proof Sketch. The proof of is similar to the proof in and is conducted by replacing the BSM by GBSM. (See Appendix for the complete proof.)
Special cases of Theorem 4.1 yield the following refined bounds:
Corollary 4.2 (Optimal mapping for policy transfer). When f(s) arg minges, d' (s,s(s,
vs' E Sz. the bound rightens to:
2 max min d (s, s'E sES;
1+7
max ESS
[V') (s)) 1-7
+
max (s VT] (15)
1-7 sES1
Corollary 4.3 (Policy transfer with identical state space). When M1 and M2 share the same state space S and f(s = 8, we have
2
1+7
max
2
S
max (s, 8)
max (s) VT
(16)
(1 11-73 7)2
EES
1 7
eES
Proof Sketch. This corollary utilizes the distance bound on identical state spaces in Theorem 3.6
In contrast to the approach of 12 which constructs disjoint union state space for analysis, we provide a similar theoretical bound by directly analyzing the relationship between the source and target MDPs. This method avoids constant total variation distance, thereby enabling simplifications such as the bound based on d/v. as well as the approximation method the following section. Meanwhile, calculating BSM on the disjoint union of two MDPs renders significant computational complexity scaling with +S2 In contrast, our GBSM is directly computing between Mj and M2, with reduced complexity scaling with |
4.2 Approximation Methods and Corresponding Error Bounds
When the state space extensive and actual transition probabilities are inaccessible, approxima- tion methods are necessary for the efficient computation of state similarities. In the single MDP scenario, Ferns al. [4 proposed state similarity approximation (SSA) method based on state aggregation and sampling-based estimation. Let U C S be a set of selected representative states, [+]: + Z an aggregation mapping, = max.es (d (s, [s])] the maximum aggregation distance, and K the number of samples used to empirically estimate each transition probability. The SSA error satisfies
27(2 + 7)
2y
max (s, dr ((s),, 8,6'
max Wi (-)) (I(I)) a.s
a);
1 1
1-
(17)
Here, di denotes the BSM on the approximated MDP, P] denotes the transition probability between aggregated states, and [PP] represents its empirical counterparts estimated from K samples.

---

However, the BSM-based aggregation enror bound (2 (1) is fairly loose, while the sample complexity for the estimation error is limited asymptotic expressions.
Beyond approximating state similarities, it is crucial to quantify the difference between optimal value functions within the original MDPs and their approximated counterparts in aggregated MDPs. Using a BSM-based analysis, Zhang et al. [6] established a value function approximation (VFA) bound on this difference, given by 2ō 25/(1 (1 - 7), but it also suffers from looseness when ry becomes large.
To address this, we apply the GBSM to directly compute state similarities between the original MDPs and their aggregated/estimated counterparts. Beyond extending the approach in [14] to the multi-MDP setting, our GBSM -baded analysis yields significantly tighter approximation bounds for both SSA and VFA, and provides explicit and closed-fome expression for the sample complexity.
4.2.1 State Aggregation
Given the previously defined S, U. and [.]. the aggregated state space [S] is defined such that the reward function and transition probability of each state are replaced by those of its representative state, given by R(s. a) R([s), a) and (( 8, a) = (-|[[s), a) for all & E S. The aggregated transition prob- ability is defined as [F][s'|s, = E.' " P(s"|s, a). Note that [P) (8, a) O when s' $ U.
With this construction, we define the aggregated MDP for MI as Ma ([S) A, [P R1, 7). First, we obtain the VFA bound directly from GBSM.
Theorem 4.4 (VFA error bound). Given MDP M1 and its aggregated counterpart Mij. the VFA bound is given by
max (+) (6) where max d=)) 8) and ō max,es, d' (s, [s])
(6) S 01 S 501/(1 ()).
(18)
Proof. The first inequality is direct consequence of Theorem 3.3 For the second one, We construct
an intermediate MDP defined by Mi ([Si), A, Pl, R1, 7) and prove (ss = d² (s,
for all s E S₁ through induction. For the base case, d d:ss:-0) (s, s) = max. R ([s], a) R1 ([s). =
By the induction hypothesis, we assume that d (s 1 for any n, then ( (P(()Iss, a), [P](-Iss. d )
|her-(l) n+1 (s, max, {IRi -
S max Exes, ((315), (s))
ses,
The inequality here follows from a transportation plan that moves the mass from each to its representative state [5]. Note that the reward function and transition probability of each state are the same as its representative states in M Mi thus d, s1
1/ss-111/ (er-P)((,, [3]) = - ([$), [5]) 0, and thereby (3,
d (s,, s) O. Now we have established d! (s, s) 0 for all E N and S1- Taking n + oc, we have d' s) = 0, Vs E Sj. Using the inter-MDP triangle inequality in Theorem 3.5 we derive d (ss) s) = d d''t" s) for s E S1.
we have d 1
Next, we prove the inequality between o, and ,, For representative states s, E 24 S S1, we have d=111s1 (Su, s.) = max. {1R (su, a) Rí (s., a) + (IP- a), (P(-|ss,0) d d max, (Wi a). P( Su, a): 111))
Sy {Σ
P( (( ' (8, K)}
EES
Symax, d1
max, d== [s)).
Here, the first inequality follows from straightforward transportation plan that keeps all the mass at its position. The last equality is because and [s] share the same reward function and transition probability in M Then, according to the inter-MDP triangle inequality in Theorem 3.5 we have
d (s, [s]) < dz [s)] + d ([s), [s]) < d [s]) + max, dd11 (s, [s]) Taking the maximum of both sides, rearranging the inequality, and combining the established sl s) = d' (s, s), we have
6 = max, dl (s,,) 8) = max, d (s, 8) = max, d' (s, [s])
-7) = max, ds < max, d (s, [s)) (1-)
(s)/s/(11111 (s, 7) = -01((1 (11--))
7

---

demonstrating significant tightness compared to the BSM-based bound 251/(1 -7) in 6
Then the aggregation error bound for SSA established as follows.
Theorem 4.5 (SSA aggregation error bound). Given MDPs Mi, M2 and their aggregated counterparts (22. the SSA error bound is given by
max,,a' (s. s') - d (s. s') o 02 (ō) + 32) 7).
(19)
Proof. This theorem is easily derived by combining Theorem 3.5 and Theorem 4.4
When the compared MDPs identical, i.e., M2 MM (S, A, R,y): Theorem 4.5 reduces to the aggregation error bound in the singleMMDP scenario as
max,,s' (s. d d (s. s - 201 S 2 - 7),
indicating significant tightness of the GBSM-based bound 20 compared to the BSM-based one 25, (2 + (1 7) 14..
4.2.2 Sampling-base based Estimation
To estimate probability distribution P through statistical sampling, we define the empirical distribu-
are K independent tion based on K samples as P(x)= & Σm 6x. (z), where (X1, (X1.X,, , },
points sampled from P and 5 denotes the Dirac measure at X; such that dx, (x) otherwise. Then the empirical MDP for Mi is constructed by sampling K points for each Pi (- a).
if x = X, and
defined by M; AS,, 7) The estimation Theorem 4.6 (SSA estimation error bound), Given MDPs M,, M2 and their empirically estimated counterparts Mi the SSA error bound is given by
bound is derived as follows.
5 (d' (s, s') d (s, s')l S max, dl (s, s) + max, ( (''ss')
(20)
To reach ervor less than with a probability of a. the sample complexity is given by
K 1n(an(2/2) 72 1/.
(21)
2c 7)
for each state-action pair in Mi (where S.|=|Si)) and M2 (where [8.| (82))
Proof. Inequality 200 is easily obtained from Theorem 3.5 In terms of the sample complexity, we derive the following using Theorem 3.6
(d. (s,2
max
R
maax, (P PI (P) + maxy
(1 - (1-
RR
ses EEEs,
a) max
Σ
P P2(5)5/ P2 (3) ())
maxx 5,a
2(1 77)
s'aa
SES,
To ensure the estimation error remains below e, we require (P] a) - P (3)s, a) < <0 أااي) and
S
[5]s, a) - (5) s, a)) I <(1 ({1,)²
R Next, by applying the Hoeffding's 's inequality 24 that defined
by Pr(l - P(s) 2 e) 2e 2k.² we derive the desired sample complexity.
When the compared MDPs are identical, the estimation SSA bound in Theorem 4.6 reduces to 2 max, (s, for BSM. We now prove the tightness of this new sampling error bound compared 2y to the existing bound E max,,* Wi (P(-ls, a), P(-l((,, a); dd ) in [1]. According to the transitive
property of inequality on the Wasserstein distance defined in (10). we have
d' (s,))) = -PP a), F(-1s,)); d
S WWP a), P( a);; + Wi (P((1s, a), P(-ls,a)dd")
S (P)ss, a): d + d (s,
8

---

Taking the maximum of both sides and rearranging the inequality yields
max, d' d' (s, 8) < 24 m Wi Wi s. a), PP-|s a); d) (/11
Since di-1 A d', we have now proved the tightness of the new sampling emorr bound compared to the one derived from BSM in [4]
Furthermore, in case the approximation combines both state aggregation and sampling- based estima- tion, where the approximated MDP is defined as MMi [[Si], A, [P R), we have
m |d (s. d (s, s') 2 max, d (s, s) max, d' s, s) + max, d (s, s)
via the inter-MDDP triangle inequality. It enables decoupled analysis of error, and thus results in an explicit and closed-formed sample complexity, i.c.. K 2 - ln(a/2) 2<-[1-7]+ for an error below e with probability of 1 - a, where U/ is the set of representative states.
5 Extensions to BSM variants
The proposed GBSM framework is readily extendable to numerous variants of BSM to enhance its applicability, such as lax BSM 25 and on-policy BSM (26).
Lax GBSM enables the computation of state similarities between MDPs with different action spaces. To relax GBSM to lax GBSM, we first adapt (2) to
5(d)((s, (s' (s', = (1(s, - + P2)(1sss
(22)
and define the lax function as Fix (dx(()ss = Xy; 8(d),, where X. = {(s, a)la E A1). X² {(s'''')))e
0 and q Flu (dll2n (s, s'), dlsr, converges to a similar fixed point dl-2 that satisfies (s)
A22, and H is the Hausdorff metric. Iterating from d (s,
(3')' < d:-2 (s. 8") in Theorem 3.3 Next, the symmetry (Theorem 3.4 and triangle inequality (Theorem 3.5) can be readily established for d=.2 For MDPs sharing same S and A, we have 1 S dl-2 <d (1 - 7) (Theorem 3.6). Since these fundamental metric properties hold, the bounds for state aggregation (Theorem 4.5 and estimation (Theorem 4.6) also follow directly. For policy transfer, a similar regret bound (replacing d²=2 in Theorem J. d(a)) can be established by defining an additional action mapping g : Ai + A for transfer. Due to the introduction of max-min term via Hausdorff metric, the lax GBSM-basee --ssed transfer bound requires an assumption on this action mapping, i... g(a) = arg ming' ((f(s'). a), (s', a'): dluz)) for each s' and a. See Appendix D for the proof.
On-policy GBSM computes state similaritics between MDPs under non-optimal policies. To achieve this, rewrite (2) to
(23)
where (s) = Eg (alss) (1 a) and PPT (5]s) = Σ. (ials) a). V3 E S₁ represent the expected reward and transition probabilities for non-optimal policy x in M₁, with corresponding terms RJ and Px defined similarly for M2. Our theoretical properties are also preserved in this
setting: the value difference bound in Theorem 3.3 now applies the on-policy value function
by (s) V2T (s')l (s, Then metric properties Theorem 3.4 and 3.5 follow directly,
and (x, s') ) is bounded by an on-policy TV-based metric d+ a (8, 8.8 = [ (8) (s)) R2 (s)
dit 1-y TV (-Is), PT (+))s) as the Theorem 3.6 for on on-policy GBSM. As a direct consequence, we Vi (s) I max, 1-111 (s, S max, (s, [s)) 7), tighter bound for VFA with non-optimal policy compared with the existing result 2d (s. [s))/(1 - 7) in 15 See Appendix B for the proof.
have max,
Numerical Results
In this section, we empirically validate the theoretical results derived from GBSM. To this end, we construct MDPs with randomly generated reward functions and transition probabilities, along with their aggregated and estimated counterparts. Specifically, we use random Garnet MDPs with

---

SEA indtraaan
(a) Policy transfer
(b) SSA (aggregation)
(c) SSA (estimation)
(d) VFA
Figure Experiments on random Garnet MDPs.
|8| = 20, |A|| 5, and 50% branching factor. In the aggregated MDPs, the reward functions and transition probabilities for half of the states are replaced by those of their representative states, while the estimated MDPs are established by introducing a Gaussian noise with standard deviation ranging from 0.1 to 0.3 to the transition probabilities.
To demonstrate the application of policy transfer between MDPs, calculate the bound in Theo- rem 4.1 and the existing measure between MDPs in [17], and calculate the ground-trune regret by computing the precise value functions under tabular Q-learning setting. Then, we calculate the aggre- gation and estimation SSA bounds using BSM and GBSM, respectively. The BSM-hased SSA bounds computed via (17). Since the estimation error bound in (17) depends the aggregation process, we decouple the two for clearer analysis. Specifically, the BSM-haased aggregation SSA bound is given by 2ō, (2+7)/(1-7), and the estimation SSA bound is 2x_ max W, (11sss, a), IP(-|s, a); d 14). T-q
The GBSM-based SSA bounds follow from Theorem 4.5 (aggregation) and Theorem 4.6 (estimation). For VFA bounds comparison, we employ the GBSM- bound Theorem 4.4
a.d and compare with the BSM-based bound 2/1/(1 - 7) in 6 We also compare them with the ground-truth error values to assess their tightness.
We conduct 100 independent experiments for each y E experiment index of 100 independent trials, while the y-axis plots the values of ground-truth error and BS-base bounds in each trial. Figure shows that the empirical metric in [7 fails to bound the transfer regret, while our GBSM-based bound is consistently effective. In terms of the SSA and VFA error, as depicted in Figure lb Ic and Id the bounds based on GBSM are significantly tighter than those derived from BSM, which corroborates our theoretical findings and highlights the effectiveness of GBSM in multi-MDP analysis. Complete results are provided in Appendix
The x-axis represents the
7 Conslusion
Application and limitation The first application is the sim-to-real policy transfer, where GBSM can be calculated between the simulated MDP and real-world MDP to predict transferred performance and serve as metric for improving the simulation environment. Meanwhile, the approximation methods could be employed to address the inaccessibility of precise transition probabilities and reward functions in the real world. Another potential application is in multi-task RL, where GBSM can coordinate policy optimization across different MDPs, cluster similar tasks for efficient training, and mitigate gradient interference issues. The limitation mainly lies in the discounted reward formulation in GBSM. In real-world tasks, the goal is typically to maximize the long-term average reward. However, most of the theoretical results in this paper are divided by 1-7, and taking to would yield an infinite result. Investigating metrics tailored for the average-reward MDP is important and promising direction for future research.
Discussion In this paper, we have formally introduced GBSM and established its fundamental theoretical properties, including GBSM symmetry, inter-MDP triangle incquality, and distance bound on identical state spaces. Leveraging these properties, provide tighter bounds for policy transfer, state aggregation, and sampling-bass based estimation of MDPs, compared to the ones derived from BSM. To our knowledge, this is the first rigorous theoretical investigation of GBSM beyond simple definitional adaptation. We believe this work introduces a valuable new tool for multi-MDP analysis.
10

---

References
[1] Richard S Sutton, Andrew G Barto, et al. Reinforcement learning: An introduction. MIT press, Cambridge, MA, USA, 1998.
[2] Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In Proceedings of the 20th Conference Uncertainty in Artificial Intelligence, UAI '04, page 162-169, Arlington, Virginia, USA, 2004, AUAI Press. ISBN 0974903906.
[3] Lothar Collatz. Functional analysis and numerical mathematics. Academic Press, 2014.
[4] Norm Ferns, Pablo Samuel Castro, Doina Precup, and Prakash Panangaden. Methods for computing state similarity in markov decision processes. In Proceedings of the Twenty-ecoond Conference on Uncertainty in Artificial Intelligence, UAI'06, page 174-181, Arlington, Virginia, USA, 2006. AUAI Press. ISBN 0974903922.
[5] Sherry Shanshan Ruan, Gheorghe Comanici, Prakash Panangaden, and Doina Precup. Repre- sentation discovery for mdps using bisimulation metrics. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI' 15, page 4202-4203. AAAI Press, 2015. ISBN 0262511290.
[6] Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Aus- tria, May 3-7, 2021. OpenReview.net, 2021. URL https://openreviiee hwwp:/nee/ooooee cost/forummid- 2FCwDKRREu,
[7] Hongyu Zang, Xin Li, Leiji Zhang. Yang Liu, Baigui Sun, Riashat Islam, Rémi Tachet des Combes, and Romain Laroche. Understanding and addressing the pitfalls of bisimulation-base representations offline reinforcement learning. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[8] Anirban Santara, Rishabh Madan, Pabitra Mitra, and Balaraman Ravindran. Extra: Transfer- guided exploration. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS '20, page 1987-1989, Richland, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9781450375184
[9] Yiming Wang, Ming Yang, Renzhi Dong, Binbin Sun, Furui Liu, and Leong Hou U. Efficient potential-based exploration reinforcement learning using inverse dynamic bisimulation metric. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[10] Philippe Hansen Esttruch, Amy Zhang, Ashvin Nair, Patrick Yin, and Sergey Levine. Bisimu- lation makes analogies goal-conditioned reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 8407-8426, Baltimore, Maryland, USA, 17-23 Jul 2022. PMLR.
mlr wwwpppeeeeeeeaaeeeeaeeee http://aannnenettsureeeeee2e2 estruch22a. html htt.e/accca.a.aarpooooooeeeeaaae
[11) Rongrong Wang, Yuhu Cheng, and Xuesong Wang. Constrained visual representation learn- ing with bisimulation metrics for safe reinforcement learning. IEEE Transactions on Image Processing, 14:379-393, 2025. doi: 10. 00.10999TI.2024:35237888
[12] Caitlin Phillips. Knowledge transfer in markov decision processes. Technical report, Technical report, McGill University, School of Computer Science, 2006.
[13] Matthew E Taylor and Peter Stone. Transfer learning for reinforcement learning domains: survey, Journal of Machine Learning Research, 10(7), 2009.
[14] Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous markov decision processes. SIAM Journal Computing, 4066):1662-1114, 201

---

[15] Mete Kemertas and Tristan Aumentado- Amanttaand-Amstonng.. Towards robust bisimulation metric learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN 9781713845393,
[16] Pablo Castro and Doina Precup. Using bisimulation for policy transfer in mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2010, pages 1065-1070, Atlanta, GA, Jul. 2010.
[17] Jinhua Song, Yang Gao, Hao Wang, and Bo An. Measuring the distance between finite markov decision processes. In Proceedings of the 2016 International Conference on Aulonomous Agents & Multiagent Systems, AAMAS '1, page 468-476, Richland, SC, 2016. International Foundation for Autonomous Agents and Multiagent Systems.
[18] Javier García, Álvaro Visús, and Fernando Fernández. A taxonomy for similarity metrics between markov decision processes. Machine Learning, 1 11(11))41774247, 2022.
[19] Cédric Villani. Topics in Optimal Transportation, volume 58. American Mathematical Soc., 2021.
[20] Leonid Vasilevich Kantorovich and SG Rubinshtein. On space of totally additive functions. Vestnik of the St. Petersburg University: Mathematics, 13(7)522-59, 1958.
[21] Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285-309, June 1955.
[22] Cédric Villani et al. Optimal Transport: Old and New, volume 338. Springer, 2009.
[23] Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey, Journal of artificial intelligence research, 4:237-285, 1996.
[24] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. The collected works of Wassily Hoeffding, pages 409,426, 1994.
[25] Jonathan J. Taylor, Doina Precup, and Prakash Panangaden. Bounding performance loss in approximate mdp homomorphisms. Neural Information Processing Systems, NIPS 08, page 1649-1656, Red Hook, NY, USA, 2008. Curran Associates Inc. ISBN 9781 605609492.
Proceedings of the 22nd International Conference on
[26] Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06): 10069-10076, Apr. 2020. doi: 1..16699aaivvv4i00 66644 URL https://ojs. aaai. org/
index. wndex.ppp/maee /atp/AAAI/aaa wwt.A////...teteeeeeeeeeeeee 6564
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper contains everything that is covered in the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the need to develop further theory, algorithms, and implementations for scenarios involving multiple MDPs in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification:
All the proof' for results are included in the main text and appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theory paper that only involves very simple numerical computations.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
14

---

Answer: [NA]
Justification: This is theory paper that only involves very simple numerical computations, and there is no training data or training/evaluation codes.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
//nips. //nips.cc/ppl wwcppbblc/guuiicuccccccccoeooopp /eeggudddsseCeebbbinninn
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer:[NA]
Justification:
There is no training or test in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[NA]
Justification: This is theory paper that only involves very simple numerical computations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
15

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: This is theory paper that only involves very simple numerical computations.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
The research conducted in the paper conforms with the NeurIPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
To our knowledge, this theory paper has no positive/negative social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
18

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
19

---

A Proof of Theorem 3.2
This section provides a detailed proof of the existence and convergence of GBSM.
A.1 The Existence of d!-2
To prove the existence of d²=2, we introduce the Knaster-Tarski fixed-point theorem. Let (X, 3) denote partial order, which means certain pairs of elements within the X' are comparable under the homogeneous relation < [2I]. If this partial order has least upper bounds and greatest lower bounds for its arbitrary subsets, called complete lattice. The Knaster-Tarski fixed-point theorem asserts that for continuous function on complete lattice, the iterative application of this function to the least element of the lattice converges to fixed point ã, which satisfies I = f()). Formally, the theorem is stated as follows.
Lemma A.1 (Knaster-Tarwee fixed-point theorem (1)). If the partial order (X, 3) is complete lattice and] f: X -> X' a continuous function. Then, f has a least fixed point, given by
fix(f) Line ((r))
(24)
where To is the least element of X, Ll denotes the least upper bound, (zo) ((f(n-1)(x)) and (zo) = f(r)). Here, the continuity of f is defined such that for any increasing sequence {2n} in X, satisfies
f (LLEN {xn) () = LnnN {f (xa))-
(25)
Let D denote the set of all cost functions, which are defined as maps that satisfy S x S2 - [0, -- Equip D with the usual pointwise ordering: Consider two cost function, say d and d' E D, denote S d' if and only if dl(s, (() S d' (8, 8') for any & E S1 and s' E S2. Then D forms a complete lattice with the least element dz i.e., the constant zero function. Given & and s', we regard the recursive definition in (5) as a function of d and accordingly define F: D D by
F sd) = max (
Ra a() + W (1s, (ass,))))
(26)
Utilizing the Knaster- Tarski fixed-point theorem, the existence of d² is achieved if the continuity of F holds on D.
D - D by We first prove the continuity of the second term in F. Define Fw, :
Fw, (d (..
(27)
Lemma A.2. Fw; is continuous on D.
Proof. We follow the definition of continuity defined in Lemma A.1 Let E S1 and E S2. Regard Fw: (st, Sy; d) function of d. Without loss of generality, we denote probability distributions
(-P(, a), P2 (2(((s,,,)) })} as {P. P} for brevity, and let S p', {p. o'} } E D. Considering the optimal
solution (H,v) for Wi (P. I.P.C. Q: p) in the dual LP in (4) have
p: - v, S p(s,, S p' (s,, 8j), i.j.
(28)
which is derived from the pointwise ordering in D. Here, for the other Wi Q;P'), {u, v) is feasible, though not necessarily optimal, solution to the dual LP in 4 Thus, we have
Wi Wi Q:p) E (P(s)) Σ Szl -1300000
S W.(.QQP)) Vp
(29)
By such a monotonicity, we have (P.QQ::)) S (P. LiENNi. H), Vp {pn} for any increas- ing sequence (pn) on D. This further implies that Linen (W, (P, Qi P;p,)) Wi (..).
We use the primal IPP for the other side. Let A denote the optimal solution in 33) for (P, which also satisfies the conditions for W, (P, Q; UnE (pEN(,.)) H). Define ex Une
20

---

Sy), then "i 2 0 and lim E = 0 due to the monotonicity of the increasing sequence of {.r). Then, we have
(2)
1811
Szl
5
Nr.
LnEN(
i=1
j=1
|11|
Szl
(nsp((ss E
16
1S2 Nig
j==
j=1
|S|
-WI(P. Qa))) + ددي= Eh
S UnEN (Wi(P, Qi Pa)) + max)
(30)
1
Here, step (a) follows from the fact that A" is the optimal solution for Wi WP Pm)
rather than Wi(P, Q; UnEN {p Taking - x., we have (Wi (P,Q; Pm)) 2
Wi(P, Qi JneN (P.)). H). Following from the above two inequalities from both directions, it is readily to get Un Px)] = Wi(P, Qi Unewlen)) }). Thus, for any i and
Fw, ( [LEN {pa} s/s 8,)
W1 (Fi (-1s;, a), P2(-1s3, a); (PEN
UnNN (Wi (-)(s) a), UnEN (Fw, (Pn 8t 8,) }. Now that the continuity of Fw, in (2 on D is established.
(31)
Armed with Lemma A.2 are ready to establish the continuity of F as follows.
Lemma A.3. F continuous on D.
Proof. Considering an arbitrary increasing sequence {pn} on D, for any i and j. we have F (U s;) max {| (5t, a) - R2(s,, a)l + w (Pi(+)s, a), P2 a)
max (1 a) - R2(s,, a) + 7 (
UREN { max (|Ri(s R2(s), + w (I)
a = UnEN {F(pn) si, 8;)}.
(32)
Now that the existence of d1-2 is established by using Lemma A.1 and Lemma A.3
A.2
The Convergence of d1-2 to d--2
Due to the continuity of and using the induction starting from d²² < d.2 {dh: forms an
increasing sequence on D. Given that d=-2 Unen ((x) we have d 2 dl-2 for any n. Also,
d (si, 83) = max R (si, a) - Re(ss, a)) + >W, (-1s, a), a))
< R max (8,,
1.j
max maxfdd2 (d 6J
8,) < R R/(1-1)) 7), 4 (s,, 8;)
E S1 x S2.
(33)
We begin with a simple inequality for the Wasserstein distance before proving the convergence of GBSM. Let X" denote the optimal solution for (P,,, Q; (2,)), then for any d
W1 (P,P.CC Q: 2-2 - Σ |sil
|8al
2-2 (s),
1=1
j=1
Σ Sil
Xi. (d)
(sin 83) - d) (st, + (1,2(s))))))
i=1
j=1
I max
(d (s) (s))
(s W (P, (P.Q; 1.2)
(34)
fj
21

---

The first inequality follows from the fact that X" is the optimal solution for (I(P, (PPQQ;d,) d.))) rather than Wi (P, Q: d' 2.
Now we employ the mathematical induction. For the base case, we have
d (s, s') - ss,
= -max {1Ri (s,a) R2 a)] + w a), P2(1))))))
o);
- max [| - R2(s',a) .))}
max (1 - R2(s', a)]} ymax (W1 (2)(11 a); d)
-max ([ a) (2(5)
= max {Wi (P1() (-)())))). PP +))
max {d (s,))) RR/(1 7), A (8, E x S2.
(35)
By the induction hypothesis, we assume that for an arbitrary n,
(s, = 7), A (8, E E S².
(36)
Then we have
d' (s,55)))) (5,5'
max
[[22 a) Rs wWi (...)
-max - (H a):
I max (12223300-266660000-000000200202
= =7 max [M[.1100FPP((3322020000000000000
(a)
I mmx
mmx (s (3. { Wi (
5,5"
Wi (Pi(()s,0),P2((115.00 2
y max
(s. 2 2 - R/ (1 7), v (s,5') S1 S2.
(37)
5,5²
Here, step (a) for all n E N.
uses
34
Following from
35
37 d d (s, 80) < <7 7) holds
B Proof of Theorem 3.3
This proves the optimal value difference bound between MDPs by induction. For the hase case, we have
I - 1/ (s)) mmx Rı a) max a2)
S max (1(s,, a
2 (si, 8j), A (5), S S2.
(38)
By the induction hypothesis, we assume that for arbitrary n.
vy(") (m) (s:) - (s,) < (1 (s:) 12 (s))
< d2 8,), v (8), E S x Sz.
(39)
22

---

Then the induction follows
vy - 1/2 22(a
(s:)
(83)
max RI(s), a) +2 Σ
|i:l
Pi P1(sk(s; a (1("
k=1
SSal
-max Re(sj, a) +
P2 Pa(8xl18j. (8a)
k=1
I max {|
1811 P(sk/(s; V) (8h)
Ri ()) a) +
k=1
18a1
(2(8). a) +
P2( 83, V22 (8k)
k=1
1si
1Sa
< max (1)s)) R2(s), a) +7
Σ
Pi (s a) (sx) (a(sklsj,a)V3" (8z)
A=1
max { [|i Ra(ss, + +wW
(Pi(118,, a), P2(1s),;
d (st, 8j); V (81;8)) E Ei x S2.
(40)
Here, steps (a) follows from the fact that (V (sk)
8-1 and (V/2*) (sx)) |52 form a feasible, but not
|ii
k-1
necessarily the optimal, solution to the dual L. in (4) for W1 (PI (- (-18,, a). P2 (2( dt?).
Now from 38
(40), we have (s) Vi (s') < d, (s, A ss.
S S2, Vn N.
Taking n oo yields the desired result.
C Proof of Theorem 4.1
This section provides detailed proof of the regret bound for policy transferred from Mi to Ma. By the triangle inequality, for any state 8j E S2 and s; = f(s,) E S1, we have
IV22 (s;) V22 (sj)l < (s;) - Vy' (s:)) + [v+(ss) - (s"(s:) + [V]((;) (1,(), (41)
Within the right-hand side of this inequality, the first summation term [V) (s,) - (s:) is upper
bounded by 2 85,, 83) according to Theorem 3.3 and [V]*(s;) Vi (s;) is upper bounded by
max,es, (s) - VT (s)]. For the last term, we have
|VT (s:) V22 (s,)]
A
Σ (als:)
asi, +
Σ Pi (sx a)V
LA
T(al{(8))) R2(s), +
Ps P2 85 (V (8k)
k=1
1S1l
1Sg Pi (i (V
(als:)
(oskn))R2(03,,) +y
Pe(Sxls, (xx)) (2)
A=1
IA
18 Pi Pr P.
S
(1(s), R2(s,, [R((s,o)-R((S,)0)+
<
Taass:)
P (s(sslsj.aa (sx
Am
|A|
[s1 ((ssulsi. -V(s)))
+
T(a|s;)
Σ
a=1
|A]
S P2(suls).o)(VV](e) V (sx))
+ 7
x(a(s;)
23

---

151
< max
Ri(os,a) Ra(sj; a)
PP (1 a) (
(P(su]ss, (V) ()Vi
+ max (s) (T) +
( +ymax =ES.
max
V22 (8)
#ES.
max [1t (3;, a) - [2(3) 1 (P (-1s;, a), P2(-1s;, }
+ y max (s) (8) + x
+y
max (s) (8)
BES.
=ES.
sES: = d (st,
max [V V1" (s)] + max (2((s) V22 (s)]-
(42)
SES2
Here, step (a)
stems from the fact that, according to Theorem 3.3
(Vi (sx))
and
(Vg (sx)) [ form a feasible, but not necessarily the optimal, solution to the dual LP in for Wi (+1s, a), P2(-1sj, a); 2 Combining the above inequalities on all three summation terms in and taking the maximum of both sides, we have
max d' (''()()), + max (V) VT E'ES2
max S'ES2
EE
1st term
2nd term
max d' d'2(s(s),,)) max e'Ea
Vi(s) VT + max
V22 V25 (s')
aESi
d'ES,
3rd term
< max d (f)). + (1+ max (s) - -1 (s) max S'882
Vi2 (s') 1/2 (6')
(43)
.E82
sES:
Rearranging the inequality yields the desired result.
D Proofs of Lax GBSM-based transfer bound
To prove the policy transfer bound based on lax GBSM, apart from the state mapping f S2 + S1. we need to define an additional action mapping g : A1 - A2 for policy transfer between different action spaces. Then, we have
Vy" (sy)
> Aul
(R)) + Σ
Sil
(8 (st))
k=1
[( + Σ S5
Aul
ol))
(T(a)s)) Ro Ra(),,
+7 E 1S P((6olss.))V7((s)
Σ 18.
k=1
Ail
-2((,,,(a))
|Si
(1 V - Σ |52l k=1 P2(81 (())
+
k=
a(alsi)) Σ
|S
Pi(ss(s (VT (sx))
k=1
T(alss)) Σ
16a1
(st))
k=1
< max atdi
|R (8t. a) - R2 (2)(5)
|1
() a) Σ |5p
+
k= (i
k=1
+ max
(i((s) - (s) +
max sES,
VV (s) - (s)(
SES,
24

---

max min [[ a) - + ()) a'); d';; (, rEA1 e'E,2
+ max (s) (s)
max [22 (s)
#ESt
2 1 (X
+ m (i((s)
max .ES:
- (s) + max (2((s) - (s)
= - (81, 83) max EE
VV (8) (+)] +
max V/ .E
1/2 (+)
Due to the introduction of max-min term via Hausdorff metric, step (a) requires that action mapping satisfies g(a) = arg ming 6((f('), a), (s',a'; d for each s' and a.
E Proofs of on-policy GBSM-based Bound
Theorem E.1 (On-policy GBSM optimal value difference bound). Let V and Vi denote the value functions with policy x in M1 and M2. respectively. Then on-policy GBSM provides an upper bound for the difference between the value functions for any state pair (s, s') E S1 x Sz:
(+) - V (5') - (s,5))
(44)
Proof. For the base case, have
V1 (s:) 122. (8,) = d:00 (8;, (5) = 0, 4 (81, E x S2.
(45)
By the induction hypothesis, we assume that for an arbitrary n.
[V (s.) V22 (ir(m) S d (s..s)) A (5), E S1 S2.
(46)
The induction follows
(T (8:) V22 (1+11+ (8))
SS
|S21 P (s 1s,) (x) (s))
=| (s:) +
PT (sx(ss:)) (sx) (s) +
k=
|
[S2]
$ [{;)) R)
+ +7|
Σ PT (sk(ss) (m) (sk)
P (5 (sx)
km
$ [| (s:) Rs,) + W (+T(sss d;
_ (st, 3T), (s, 83) S1 x Sz.
(47)
Taking n + 0o yields the desired result. Theorem E.2 (VEA error bound with non-optimal policy).
max VT - Vi (s) < max d (s,s) S max [s) -7)
(48)
Proof. The first inequality follows directly from Theorem E. while the second is established using derivation analogous the proof of Theorem 4.4
F Additional Numerical Results
25

---

Kcaen 2011
28
Dalks 20010
Dake
51
Eeparmmnne (,-2))
Inpertment (ym
(a) 0.1
(b) 0.2
(c) 0.3
Figure Experiments on random Garnet MDPs (policy transfer, 7 = 0.1 to 0.3)
4.
Paaee 1D1
25
Tair
01-
30
40
Expritvess(05)
Oxpetticre ()-11))
(a) 0.4
(b) 0.5
(c) 7 0.6
Figure Experiments on random Gareet MDPs (policy transfer, 7 = 0.6).
Ceiicheed Theeeh
4-
0-
20
20
Expattsant 11-1
Expaizant (L.1
(a) 0.7
(b) 0.8
(c) 0.9
Figure Experiments on random Garnet MDPs (policy transfer, ? = 0.7 to 0.9).
2.5
0.33
605
3.0
21
Eapermeens ()-1111)
Expertronns (om 4421
Inserteents (Pm133)
(a) 0.1
(b) 0.2
(c) 0.3
Figure 5: Experiments on random Garnet MDPs (SSA with aggregation, 7 = 0.1 to3)).
26

---

10
10/lonudd tound [1[4]]
16
2030oned [[[4]
aSHored in
33A (eamppronn
(eamppiiee) 1..0
10
60
logenmerrs..mm
lnpertment
(a) 0.4
(b) 0.5
(c) 0.6
Figure 6: Experiments on random Garnet MDPs (SSA with aggregation, 7 = 0.4 to to
0-
20
10
20
60
Experteens ())8)
Depattvves (p-1.))
(a) 0.7
(b) 0.8
(c) 0.9
Figure 7: Experiments on random Garnet MDPs (SSA aggregation, ? = 0.7 0.9).
brund [14]
38N--woo bwaed
607
0700
0.36-
Couard
0.25
0.5
0.20
3.100
0.15
607
8.655
601
6005
160
Esperasena 2.11
Expertment (pm1)2))
(a) 0.1
(b) 0.2
(c) 0.3
Figure Experiments on random Garnet MDPs (SSA with estimation, 7 = 0.1 to 0.3).
300 (ontration
(osizention)
2.8
500
0.4
00
08
140
Eogernerns:: (144
Expertoons 0451
lnserreenna (66)
(a) 0.4
(b)
0.5
(c) 0.6
Figure 9: Experiments on random Garnet MDPs (SSA with aggregation, 7 = 0.6)
27

---

2.0
2004omes (H4)
Belohams (14)
pol-huet trard [14]
1.50
cour (osizziiin)))
1.25
0.75
0:00
6.00
Eapermenss (22))
Dxperteen (ym0))
Depenmennt (y
(a) 0.7
(b) 0.8
(c) 0.9
Figure 10: Experiments on random Garnet MDPs (SSA with aggregation, 7 = 0.7 to 0.9).
3.75
Culld Ausd
28-
3.50
V2A
6.75
4.50
03-
025
30
40
Dxpirimence (1
Esprrteei (-
(a)
0.1
(b) 0.2
(c) 0.3
Figure 11: Experiments on random Garett MDPs (VFA, y t. 0.3).
35-
26
VEL
V75A
40
Experimante Cpm
Experteens Correeeee.ceeta 051
Depenmenn ()-12.5)
(a) 0.4
(b) 0.5
(c) = 0.6
Figure 12: Experiments on random Garet MDPs (VFA, y = 0. 0.6).
25-
VIK-200
10
20
20
40
20
60
(1677
Expertions (1-163)
Ixporttins (p-1)
(a)
0.7
(b)
0.8
(c) 0.9
Figure 13: Experiments on random Garnet MDPs (VFA, 7 0.7
28


Reviews:
[{"review_id": "PcfmUFyycU", "reviewer": "Reviewer_xZ9L", "summary": "This paper considers the question of formalizing a bisimulation distance between distinct MDPs, with possibly different state spaces. They begin by introducing a desirable fixed-point formulation for such a distance, and proving its existence using the Knaster-Tarski fixed point theorem. They then provide a number of theoretical properties on the distance, such as its relationship to optimal value differences between the MDPs, as well as regret bounds on policy transfer. They next consider its sample complexity, and provide sample complexity results on how many samples are needed in the empirical MDP. They then compare it empirically to standard bisimulation acrossa a task of randomly-generated MDPs.", "questions": "- Can you elaborate more on the construction of the MDPs for the experiments? (Are they Garnet-style, what is the state space, how different are the state spaces of the pairs, etc). \n- What is the x-axis in the experiments? What is the y-axis as well (seems to be incorrectly labelled \"values\")?\n- Why do you allow for different state spaces but require the same action space? Can this be relaxed?\n- Is it possible to perform any experiments on more interesting MDPs?", "limitations": "yes", "rating": 2, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- The paper has a high level of theoretical rigour, with each result carefully proven. \n- The paper is clearly written.\n\n---\n**Weaknesses**\n- The variant of the bisimulation metric used is the original (which takes $\\max$ over actions), which has been shown to have a number of drawbacks (lack of connection to non-optimal policies, biased estimation, etc). I think that these issues will only be exacerbated in the cross-MDP setting, and that the resulting metric would be vacuous. I think the paper can be strengthened greatly by either (i) generalizing the provided results to one of the relaxations of the original bisimulation metric, or (ii) evaluating the metric across a pair of two small-scale, interpretable MDPs and demonstrate non-trivial bounds. \n- Although it is clearly written and correct, the theoretical results all lack some novelty. In particular, to my knowledge, every proven result has a very similar equivalent in literature. \n- The theory is set up to require that both MDPs have the same action space, even though their state spaces are allowed to differ. I think that arguably different action spaces is a more realistic setting, and should be relatively easy to adapt to (as done in lax bisimulation metrics), if the authors agree.\n- The empirical evaluation is very limited: they are currently only done on randomly-generated MDPs. The results themselves are difficult to interpret currently, as for example it is not stated what the x-axis represents.", "was_revised": true, "final_justification": "After reading the authors' rebuttal, discussing with the authors, and reading the other reviewers' discussions with the authors, I am inclined to maintain my current score of a reject. Although the other reviewers viewed the paper relatively positively, I still believe that the paper does not provide sufficient novelty for submission at NeurIPS.", "rebuttal": "Thank you for your constructive comments, please see responses to your questions below.\n\n> W.1 The variant … takes max over actions … non-trivial bounds.\n> \n\n> W.3 The theory … same action space …\n> \n\n> Q.3 Why … Can this be relaxed?\n> \n\nYes, although current GBSM is designed for shared action space, it can be readily relaxed to different action spaces.\n\n**1. Consideration behind same action space.** The initial motivation of this work is to establish a theory for policy transfer between different MDPs, where action spaces often remain consistent in practical applications, such as games (e.g., 'up, down, left, right' controls in PAC-Man across different maps) and sim-to-real problems (e.g., consistent vehicle control commands for autonomous driving under varying road conditions). Therefore, we employ BSM rather than its lax counterparts as the base of our extension.\n\n**2. Lax GBSM.** To relax GBSM to lax GBSM, we first adapt (2) in our paper to \n\n$\\delta (d)((s,a), (s',a'))=|R_1(s,a)-R_2(s',a')| +\\gamma W_1(\\mathbb{P}_1(\\cdot|s,a), \\mathbb{P}_2(\\cdot|s',a') ;d),$\n\nand define the lax function as\n\n$F_\\text{lax}(d|s,s')=H(X_s,X'\\_{s'};\\delta (d)),$\n\nwhere $X_s=\\\\{(s,a)|a\\in\\mathcal{A}\\_1\\\\}$ , $X'\\_{s'}=\\\\{(s',a')|a'\\in\\mathcal{A}\\_2\\\\}$, and $H$ is the Hausdorff metric defined as $H(X,Y;d)=\\max(\\sup_{x\\in X} \\inf_{y\\in Y}d(x,y),\\sup_{y \\in Y}\\inf_{x\\in X}d(x,y))$. Iterating from $d_0^{1-2}(s,s')=0,\\ F_\\text{lax}$ has a similar fixed point $d_\\text{lax}^{1-2}$ that satisfies\n\n$|V^\\*\\_1(s)-V^\\*\\_2(s')|\\leq d_\\text{lax}^{1-2}(s,s')\\ \\text{(Thm. 3.3)}.$\n\nThe proof is similar to the proof of lax BSM in (Taylor et al., 2008). Building from Thm. 3.3 and property of Wasserstein distance, the symmetry (Thm. 3.4) and triangle inequality (Thm. 3.5) can be readily established for $d_\\text{lax}^{1-2}$. Regarding Thm. 3.6, for MDPs sharing same $\\mathcal{S}$ and $\\mathcal{A}$, the Hausdorff metric in $d_\\text{lax}^{1-2}$ involves a max-min term $\\max_a \\min_{a'}$, while its counterpart in original $d^{1-2}$ is a max term $\\max_{a,a'=a}$. Thus we have $d_\\text{lax}^{1-2}\\leq d^{1-2} \\leq d_\\text{TV}^{1-2}$. Since these fundamental metric properties hold, the bounds for state aggregation (Thm. 4.4) and estimation (Thm. 4.5) also follow directly. \n\nFor policy transfer, a similar regret bound (replacing $d^{1-2}(f(s'),s')$ in Thm. 4.1 by $d_\\text{lax}^{1-2}(f(s'),s')$) can be established by defining an additional action mapping $g:\\mathcal{A}\\_1\\rightarrow\\mathcal{A}\\_2$ for transfer. Due to the max-min structure of the Hausdorff metric, the derivation for lax GBSM-based transfer bound relies on the assumption of an optimal action mapping, i.e., $g(a) = \\arg \\min_{a'} \\delta ((f(s'),a), (s',a');d^{1-2}_\\text{lax})$ for each $s'$ and $a$.\n\n**3.Evaluation across interpretable MDPs.**  For your concern on evaluation across a pair of two small-scale MDPs, we have added a new numerical experiment to calculate the GBSM-based bound and the precise transfer regret $V_2^\\*-V_2^\\pi$ under tabular Q-learning setting. \n\nThank you for your constructive suggestions which significantly improve the applicability of our theory, and we believe these adaptations directly address your concerns. We would add a detailed discussion of lax GBSM, its requirements, and additional experimental results to our paper. Considering the limitation on characters, we could provide the detailed derivation and experimental data (calculated bound and corresponding transfer regret) in the discussion phase if necessary. \n\n> W.2 Although it is clearly written … equivalent in literature.\n> \n\nThank you for your comment regarding the novelty. \n\n**1. Rigorously established bound beyond empirical evaluation.** While the idea of using BSM to evaluate similarity between MDPs was similarly proposed in (Song et al., 2016), their work was limited to an empirical evaluation via Hausdorff distance, that is, $H(\\mathcal{S}\\_1,\\mathcal{S}\\_2;d)$. They demonstrate a positive correlation between their measure and the transfer regret, without providing any provable bounds on policy transfer. Our GBSM framework makes it possible to theoretically analyze their measure, revealing that it is a simplified version of our transfer regret bound, corresponding to the first term in our Cor. 4.2 (without coefficient $\\frac{1}{1-\\gamma}$) and is only applicable to the ideal scenario of transferring the optimal source policy (eliminating the second term in Cor. 4.2) via an optimal state mapping (ensuring the max-min term). In contrast, our GBSM provides a rigorous performance bound for arbitrary policy and state mapping (Thm. 4.1). We also verify the measure from (Song et al., 2016) in the interpretable evaluation mentioned above. The results show that it fails to bound the regret, whereas our GBSM bound is consistently effective. As highlighted in a recent survey (García et al., 2022), for existing similarity metrics between MDPs, \"there are no theoretical guarantees that the most similar MDP is similar enough to produce a positive transfer.\" Our work provides a rigorous solution to this open problem.\n\n**2.Tightened bound from $\\frac{2\\sigma (2+\\gamma)}{1-\\gamma}$ to $\\frac{2\\sigma}{1-\\gamma}$ and closed-form sample complexity.** In terms of aggregation and estimation, existing theoretical analyses, such as (Ferns et al., 2011), have primarily focused on the single-MDP setting. Our GBSM not only extends these results to the multi-MDP context but also yields stronger results for the single-MDP case as a direct consequence of our framework. Specifically, our analysis tightens the state aggregation error bound from the existing $\\frac{2\\sigma (2+\\gamma)}{1-\\gamma}$ to $\\frac{2\\sigma}{1-\\gamma}$ (Thm. 4.4) and critically, provides a closed-form sample complexity K for estimation (Thm. 4.5), improving upon the prior asymptotic results.\n\n**3. Decoupled error analysis.** Above advancement stems from the core metric properties we establish for GBSM, particularly the inter-MDP triangle inequality. Compared to (Ferns et al. 2011, p. 1701), which necessitates a joint analysis on combined aggregation and estimation error and results in looser bounds and asymptotic complexity, our GBSM property permits a decoupled analysis of different error sources. For example, we can decouple the approximation error $|d^{1-1}-d^{\\hat{[1]}-\\hat{[1]}}|\\leq 2d^{1-\\hat{[1]}}$ (continuous MDP → aggregated+estimated MDP) into separated aggregation error $2d^{1-[1]}$ (continuous MDP → aggregated MDP) and estimation error $2d^{[1]-\\hat{[1]}}$ (aggregated MDP → aggregated+estimated MDP). \n\nWe would improve related description to highlight our contribution and novelty.\n\n> W.4 The results themselves are difficult to interpret …\n> \n\n> Q.1 Can you elaborate more on the construction …\n> \n\n> Q.2 What is the x-axis …\n> \n\nWe thank the reviewer for highlighting the need for clarity. The experiments indeed use random Garnet-style MDPs with $|\\mathcal{S}| = 20, |\\mathcal{A}| = 5$,  and a 50% branching factor. In the aggregation experiments, half of the states are aggregated to a representative state. In the estimation experiments, we introduce a Gaussian noise with a standard deviation ranging from 0.1 to 0.3 into the transition probabilities. For plots, the x-axis represents the experiment index of 100 independent trials. Taking aggregation experiment as an example, the y-axis plots the following three values: the ground-truth aggregation error ($\\max|d^{1-1}-d^{[1]-[1]}(s,s)|$, shown as grey dots); GBSM-based theoretical error bound ($2\\max d^{1-1_{[\\mathcal{S}]}}$, blue dots); and the existing BSM-based bound ( $\\frac{2\\sigma (2+\\gamma)}{1-\\gamma}$, red dots). We would extend the current descriptions on coordinates in line 287 to improve the clarity of our results.\n\n> W.4 The empirical evaluation is very limited …\n> \n\n> Q.4 Is it possible to perform any experiments on more interesting MDPs?\n> \n\nWe have extended our experiment to a real-world scenario by applying the GBSM to a Digital Twin (DT)-driven DRL task for dynamic resource allocation in a real-world 5G wireless network testbed. In this experiment, the real-world network to be optimized serves as the target MDP, while DTs, as its virtual replicas, function as multiple source MDPs. A DRL policy is trained in each DT and tested for performance in the real network. We employ the proposed aggregation and estimation method to calculate GBSM in real-world, and compare it with policy transfer performance (Detailed in the response to W.2 of reviewer BQkW). Our findings reveal a strong linear correlation between the GBSM distance and the worst-case deployment performance of the policy trained in the DT, not only validating GBSM's predictive capability on transfer regret in a real-world environment but also confirming its aggregation and estimation efficacy in scenarios beyond randomly-generated MDPs. We will incorporate the full results from this real-world experiment into the revised paper, including numerical comparison, a photograph of the Open 5G testbed and corresponding citation (currently omitted to ensure anonymity). While we cannot include plots in rebuttal, we would be happy to provide the raw data (calculated GBSM and corresponding real-world deployment performance) during the discussion period. \n\n# References\n\n[1] Taylor J, Precup D, Panagaden P. Bounding performance loss in approximate MDP homomorphisms. Advances in Neural Information Processing Systems, 2008, 21.\n\n[2] Song J, Gao Y, Wang H, et al. Measuring the distance between finite markov decision processes Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. 2016: 468-476. \n\n[3] García J, Visús Á, Fernández F. A taxonomy for similarity metrics between markov decision processes. Machine Learning, 2022, 111(11): 4217-4247.\n\n[4] Ferns N, Panangaden P, Precup D. Bisimulation metrics for continuous Markov decision processes. SIAM Journal on Computing, 2011, 40(6): 1662-1714."}, {"review_id": "xSc0Vh9dwW", "reviewer": "Reviewer_YrnY", "summary": "This paper studies the Generalized Bisimulation Metric (GBSM) as a distance measure across multiple MDPs. Specifically, it proves that GBSM has pseudo metric property by showing symmetry, the triangle inequality, and a zero distance for identical states. Then, leveraging these properties, this paper analyzes policy transfer, state aggregation, and sampling-based estimation. Numerical experiments on a toy example further demonstrate GBSM’s advantages over the classical bisimulation metric.", "questions": "Could GBSM be extended to continuous-state MDPs or to the average-reward setting?\n\nCould GBSM be incorporated into Value Iteration or policy gradient methods?\n\nWere any critical obstacles or techniques involved in proving the theorems?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\nThis paper first establishes that the Generalized Bisimulation Metric (GBSM) satisfies some metric axioms, marking a solid theoretical advance. The presentation is clear and well structured, and the toy experiments illustrate effectiveness of GBSM. Overall, the work offers a meaningful contribution to the reinforcement learning theory literature.\n\nWeaknesses:\nI did not find major shortcomings. However, the extent of its theoretical novelty remains unclear. Frankly, although I appreciate the usefulness of GBSM, I’m not convinced the contribution is strong enough for acceptance at this conference.", "was_revised": true, "final_justification": "I am satisfied with the response and have no unresolved issues other than the novelty of the contribution, as noted in the rebuttal. Consistent with my original review, since the strengths slightly outweigh the weaknesses, I will maintain my score.", "rebuttal": "Thank you for your positive review and helpful comments! please see responses to your questions below.\n\n> W.1 I did not find major shortcomings. However, the extent of its theoretical novelty …\n> \n\nThank you for your comment regarding the novelty. \n\n**1. Rigorously established bound beyond empirical evaluation.** While the idea of using BSM to evaluate similarity between MDPs was similarly proposed in (Song et al., 2016), their work was limited to an empirical evaluation, which only demonstrates a positive correlation between their measure and the transfer regret, without providing any provable bounds on policy transfer. In contrast, our GBSM provides a rigorous performance bound for arbitrary policy. As highlighted in a recent survey (García et al., 2022), for existing similarity metrics between MDPs, \"there are no theoretical guarantees that the most similar MDP is similar enough to produce a positive transfer.\" Our work provides a rigorous solution to this open problem.\n\n**2.Tightened bound from** $\\frac{2\\sigma (2+\\gamma)}{1-\\gamma}$ to $\\frac{2\\sigma}{1-\\gamma}$  **and explicit sample complexity.** In terms of aggregation and estimation, existing theoretical analyses, such as (Ferns et al., 2011), have primarily focused on the single-MDP setting. Our GBSM not only extends these results to the multi-MDP context but also yields stronger results for the single-MDP case as a direct consequence of our framework. Specifically, our analysis tightens the state aggregation error bound from the existing $\\frac{2\\sigma (2+\\gamma)}{1-\\gamma}$ to $\\frac{2\\sigma}{1-\\gamma}$ (Thm. 4.4) and critically, provides a closed-form sample complexity K for estimation (Thm. 4.5), improving upon the prior asymptotic results.\n\n**3. Decoupled error analysis.** Above advancement stems from the core metric properties we establish for GBSM, particularly the inter-MDP triangle inequality. Compared to (Ferns et al. 2011, p. 1701), which necessitates a joint analysis on combined aggregation and estimation error and results in looser bounds and asymptotic complexity, our GBSM property permits a decoupled analysis of different error sources. For example, we can decouple the approximation error $|d^{1-1}-d^{\\hat{[1]}-\\hat{[1]}}|\\leq 2d^{1-\\hat{[1]}}$ (continuous MDP → aggregated+estimated MDP) into separated aggregation error $2d^{1-[1]}$ (continuous MDP → aggregated MDP) and estimation error $2d^{[1]-\\hat{[1]}}$ (aggregated MDP → aggregated+estimated MDP). \n\n**4. Real world efficacy.** As suggested by reviewer BQkW, to demonstrate the real-world efficacy of GBSM, we have conducted an extra real-world experiment involving a Digital Twin (DT)-driven DRL task for dynamic resource allocation in a real 5G wireless network (Detailed in the response to W.2 of reviewer BQkW).\n\n> Q.1 Could GBSM be extended to continuous-state ...\n> \n\nYes, GBSM, as well as all its metric properties and bounds, **could be extended to continuous MDP**, formulated as follows:\n\nLet $\\mathcal{M}\\_1=\\langle\\mathcal{S}\\_1,\\Sigma_1,\\mathcal{A},\\mathbb{P}_1,R_1,\\gamma\\rangle$ be a continuous MDP, where $\\mathcal{S}\\_1$ is a Polish space equipped with its Borel $\\sigma$-algebra $\\Sigma_1$, $(\\mathcal{S}\\_1,\\Sigma_1)$ is a measurable space, $\\mathcal{A}$ is a finite set of functions, $\\mathbb{P}\\_1$ is a labeled stochastic transition kernel, where $\\mathbb{P}_1(\\cdot|s,a):\\Sigma_1\\rightarrow[0,1]$ is a probability measure for each $(s,a)$, $R\\_1: \\mathcal{S}\\_1\\times \\mathcal{A}\\rightarrow\\mathbb{R}\\_+$ is a measurable reward function, and $\\gamma$ is the discount factor. Similarly let $\\mathcal{M}\\_2=\\langle\\mathcal{S}\\_2,\\Sigma_2,\\mathcal{A},\\mathbb{P}_2,R_2,\\gamma\\rangle$. Define\n\n$$F(d|s,s')=\\max_{a} \\\\{|R_1(s,a)-R_2(s',a)|+\\gamma W_1(\\mathbb{P}_1(\\cdot|s,a), \\mathbb{P}_2(\\cdot|s',a);d )\\\\}$$\n\nThen $F$ has a unique fixed point $d^{1-2}:\\mathcal{S}\\_1\\times\\mathcal{S}\\_2\\rightarrow[0,\\bar{R}/(1-\\gamma)]$ and $|V^\\*\\_1(s)-V^\\*\\_2(s')|\\leq {d}^{1-2}(s,s')$  (Thm. 3.3). The proof is analogous to the one for BSM in continuous MDP, detailed in Section 3.1 of (Ferns et al., 2011). Building from Thm. 3.3 and property of Wasserstein distance, the metric properties (Thms. 3.4, 3.5, 3.6) can be readily established. Since these fundamental metric properties hold, the error bounds (Thms. 4.1, 4.4, 4.5) also follow directly.\n\nThe aggregation method in Thm. 4.4 facilitate the practical calculation of GBSM on continuous MDPs. Let $[\\cdot]$ denote a state aggregation mapping such that $d^{1-1}(s, [s])\\leq\\sigma_1$ and $d^{2-2}(s', [s'])\\leq\\sigma_2$ for every $s\\in\\mathcal{S}\\_1,s'\\in\\mathcal{S}\\_2$, then we have \n\n$\\quad \\max_{s\\in\\mathcal{S}\\_1,s'\\in\\mathcal{S}\\_2}|d^{1-2}(s,s')-d^{[1]-[2]}(s,s')|$\n\n$\\leq  \\max_{s\\in\\mathcal{S}\\_1}d^{1-1_{[\\mathcal{S}]}}(s,s)+\\max_{s'\\in\\mathcal{S}\\_2}d^{2-2_{[\\mathcal{S}]}}(s',s')$\n\n$\\leq \\frac{1}{1-\\gamma} (\\max_{s\\in\\mathcal{S}\\_1}d^{1-1}(s,[s]) + \\max_{s'\\in\\mathcal{S}\\_2}d^{2-2}(s',[s'])) \\leq \\frac{\\sigma_1+\\sigma_2}{1-\\gamma}$\n\nas the error bound for calculating GBSM on aggregated(discretized) MDPs.\n\nHowever, the GBSM, at least in its current formulation, is not compatible with average-reward setting. Considering that most of theoretical results in this paper are divided by $1-\\gamma$, taking $\\gamma$ to 1 yields an infinite result. We will discuss this limitation in our paper, and investigate a metric tailored for the average-reward Bellman equation in our future work.\n\n> Q.2 Could GBSM be incorporated into Value Iteration or policy gradient …\n> \nGBSM can be incorporated into value iteration by providing a principled mechanism for state abstraction. The core idea is to perform value iteration on a smaller aggregated $\\mathcal{M}\\_{[1]}$ and use its value function as an approximation for the original $\\mathcal{M}\\_1$. Unlike standard BSM, which requires merging both MDPs into a disjoint union, GBSM's inter-MDP triangle inequality allows for a more direct analysis of the approximation error by giving $|V_1^\\*(s)-V_{[1]}^\\*(s)|\\leq d^{1-[1]}(s,s)\\leq\\frac{\\sigma_1}{1-\\gamma}$ where $\\sigma_1$ is the aggregation threshold that satisfies $d^{1-1}(s, [s])\\leq\\sigma_1$ for all $s$. Also, when exact transition probabilities or rewards are not accessible, the value iteration needs to be performed on both aggregated and estimated $\\mathcal{M}\\_{\\hat{[1]}}$. Then the approximation error is bounded by $|V_1^\\*(s)-V_{\\hat{[1]}}^\\*(s)|\\leq d^{1-\\hat{[1]}}(s,s) \\leq d^{1-{[1]}}(s,s)+d^{{[1]}-\\hat{[1]}}(s,s)\\leq\\frac{\\sigma_1}{1-\\gamma}+d^{[1]-\\hat{[1]}}(s,s)$, where the latter term for estimation error could be reduced below $\\epsilon$ with a sample complexity $-\\ln(\\alpha/2) \\frac{\\gamma^2\\bar{R}^2|[\\mathcal{S}\\_1]|^2}{2\\epsilon^2(1-\\gamma)^4}$. This property enables an efficient analysis of combined error during value iteration. Meanwhile, since GBSM evaluates similarities between states across multiple MDPs, it could easily facilitate transfer of value functions/networks.\n\nFor policy gradient methods, especially in multi-task settings, GBSM can coordinate policy optimization across diverse environments, mitigating gradient interference issues. For example, GBSM can be used in clustering of tasks for more efficient training. Also, it can enhance gradient surgery methods by enabling a distinction: when tasks are truly divergent (high GBSM), surgery is necessary to prevent destructive interference. Conversely, when tasks are similar (low GBSM), gradient conflicts are more likely attributable to stochastic sampling noise, where intervention would be counterproductive. This GBSM-informed approach allows for more stable and efficient multi-task policy optimization.\n\n> Q.3 Were any critical obstacles ..\n> \n\nA critical obstacle was **overcoming the limitations of prior formulations for state similarity**. Initially, we devised a metric similar to the one in Song et al. (2016), defining a distance $d(s, s')$ where the former $s$ and the latter $s'$ were fixed to states from $\\mathcal{M}\\_1$ and $\\mathcal{M}\\_2$, respectively. This fixed definition prevented the establishment of crucial metric properties. For instance, symmetry was not guaranteed, as $d(s_i, s_j)$ and $d(s_j, s_i)$ are different combinations of probabilities and rewards (e.g., $\\mathbb{P}_1(s_i),\\mathbb{P}_2(s_j)$ vs. $\\mathbb{P}_1(s_j),\\mathbb{P}_2(s_i)$), and the triangle inequality becomes loose and less useful, derived as $d(s_i, s_j)\\leq d(s_i,s_k)+d(s_k,s_k)+d(s_k,s_j)$. \n\n**We redefine the metric on arbitrary state-MDP pairs**, i.e., $d((s,\\mathcal{M}\\_1),(s',\\mathcal{M}\\_2))$, concisely written as $d^{1-2}(s,s')$ in our paper. This generalization was the cornerstone to establish the fundamental properties of GBSM. In establishing the inter-MDP triangle inequality (Theorem 3.5), we could not directly adapt existing proofs for BSM, as our metric is no longer a pseudometric defined on a single state space. We addressed this by introducing an extra MDP $\\mathcal{M}\\_3$, employing the Gluing Lemma to construct a joint transportation plan, which was essential for induction-based proof. Similarly, deriving the TV-based distance bound (Theorem 3.6) was non-trivial because the self-distance $d^{1-2}(s,s)$ is not necessarily zero in multi-MDP setting. We overcame this by constructing a specialized transportation plan to carefully bound the transportation cost. Once these foundational properties were proven, the derivations of subsequent theoretical bounds were derived more directly.\n\n# References\n\n[1] García J, Visús Á, Fernández F. A taxonomy for similarity metrics between markov decision processes. Machine Learning, 2022, 111(11): 4217-4247.\n\n[2] Ferns N, Panangaden P, Precup D. Bisimulation metrics for continuous Markov decision processes. SIAM Journal on Computing, 2011, 40(6): 1662-1714.\n\n[3] Song J, Gao Y, Wang H, et al. Measuring the distance between finite markov decision processes Proceedings of the 2016 international conference on autonomous agents & multiagent systems. 2016: 468-476."}, {"review_id": "k9DQjBJZwY", "reviewer": "Reviewer_BQkW", "summary": "This paper proposes a generalized bisimulation metric (GBSM) to measure state similarities across multiple Markov Decision Processes (MDPs) and rigorously establishes its fundamental metric properties, including symmetry, inter-MDP triangle inequality, and the distance bound on identical states. The paper applies GBSM to policy transfer, state aggregation, and sampling-based estimation, deriving explicit theoretical bounds for policy transfer performance, aggregation error, and estimation error. It also demonstrates that the error bounds of GBSM are significantly tighter than those of the standard BSM. Furthermore, the paper introduces a closed-form sample complexity approximation method, improving upon existing asymptotic results based on BSM, and supports its theoretical findings with numerical experiments.", "questions": "Although the proposed GBSM framework demonstrates strong theoretical guarantees and significant improvements over baseline methods, certain aspects of its practicality and design motivations are not clearly articulated. The reliance on exact transition probabilities and reward functions, which are often impractical in real-world RL settings, raises concerns about its scalability and applicability. Additionally, the numerical experiments, conducted solely on synthetic MDPs, do not sufficiently demonstrate the method's efficacy in complex, real-world tasks. While the paper provides rigorous theoretical foundations, the lack of clarity in these aspects may confuse readers and limit the perceived utility of the method.\nGiven these issues, I am inclined to suggest a \"Borderline\" decision. However, I am open to revising my score if the authors address these concerns by providing clearer justifications, exploring practical approximations, and validating the method on more realistic benchmarks.", "limitations": "yes", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Leverages Wasserstein distances and existing MDP structures in a zero-shot manner, requiring no additional data collection or model training while maintaining rigorous theoretical guarantees.\n2.GBSM achieves significantly tighter theoretical bounds in policy transfer (regret bound reduced by 1-γ), state aggregation (error bound compressed to1\\/(1-γ) of BSM baselines), and sampling estimation (closed-form sample complexity K), with experimental validation showing 60-80% improvement over existing methods.\n3.The paper presents a rigorous and comprehensive theoretical framework for the GBSM, defining it clearly, proving key properties (e.g., symmetry, triangle inequality, distance bounds), and establishing convergence using fixed-point theory.\n\nWeakness:\nmajor concern：\n1. GBSM relies on exact transition probabilities P and reward functions R across MDPs (Eq. 2), which are often impractical to obtain in real-world RL settings. Many applications, such as robotics and healthcare, involve stochastic dynamics that are challenging to model accurately. Additionally, the computation of the Wasserstein distance over entire state spaces introduces significant computational overhead, particularly in high-dimensional environments, thereby limiting the scalability of GBSM. Exploring approaches to approximate P and R, or employing scalable approximations of Wasserstein distance, could address these limitations and improve the applicability of GBSM in real-world scenarios.\n2. The numerical validation in Section 5 relies solely on synthetic MDPs with random perturbations. Could the authors clarify whether these experiments sufficiently capture the complexity of real-world RL tasks? Would testing on standard benchmarks help demonstrate the applicability of GBSM in practical scenarios? Additionally, the aggregation and estimation simulations appear to simplify the complexity of real distribution shifts. Could the authors comment on the potential limitations this might impose on the generalizability of the results?", "was_revised": true, "final_justification": "We acknowledge that we are not domain experts in this specific area, and therefore our ability to provide an in-depth technical assessment is limited. Given this, we suggest that the final decision should primarily follow the evaluations and recommendations from other reviewers with stronger expertise in this field.", "rebuttal": "Thank you for your positive review and helpful comments! please see responses to your questions below.\n\n> W.1 GBSM relies on exact transition probabilities … involve stochastic dynamics that are challenging to model accurately.\n> \n\nWe acknowledge that obtaining exact transition probabilities and reward functions is often impractical in real-world applications. \n\nOur paper formally **addresses the issue of unknown transition probabilities in Theorem 4.5**. We show that one can construct an empirical MDP $M_{\\hat{1}} = \\langle \\mathcal{S}\\_1, \\mathcal{A}, \\hat{\\mathbb{P}}\\_1, R_1, \\gamma\\rangle$ and a similar $M_{\\hat{2}}$ by estimating the transition probabilities $\\hat{\\mathbb{P}}\\_1,\\hat{\\mathbb{P}}\\_2$ from collected real experience $(s_t,a,s_{t+1},r)$. Theorem 4.5 establishes a formal error bound on the deviation of the GBSM computed on this empirical MDP from the true GBSM, as well as a closed-form sample complexity to reduce this error below a given $\\epsilon$. \n\nOur GBSM theoretical framework can also **address the case of inaccessible reward functions**, as you mentioned. Consider an MDP $M_{\\tilde{1}} = \\langle \\mathcal{S}\\_1, \\mathcal{A}, \\hat{\\mathbb{P}}\\_1, \\hat{R}\\_1, \\gamma\\rangle$ with both estimated rewards and probabilities, the estimation error regarding $M_{\\tilde{1}}$ can be decomposed using the inter-MDP triangle inequality as \n\n$d^{1-\\tilde{1}}(s,s)\\leq d^{1-\\hat{1}}(s,s)+d^{\\hat{1}-\\tilde{1}}(s,s)\\leq \\frac{\\gamma \\bar{R}}{(1-\\gamma)^2} \\max_a\\text{TV}\\big(\\mathbb{P}\\_1(\\cdot|s,a), \\hat{\\mathbb{P}}\\_1(\\cdot|s,a) \\big)+\\frac{1}{1-\\gamma} \\max_a|R_1(s,a)-\\hat{R}\\_1(s,a)|$\n\nThe first term is precisely the bound for probability estimation error in Theorem 4.5. The second term, which represents the reward estimation error, is derived using Theorem 3.6, and has a sample complexity of $-\\ln(\\alpha/2) \\frac{|\\triangle R_1|^2}{2\\epsilon^2(1-\\gamma)^2}$ where $\\triangle R_1$ is the maximum possible span of the reward function for any state-action pair.\n\n> W.1 Additionally, the computation over entire state spaces introduces significant computational overhead…\n> \n\nTo address the computational overhead of calculating the Wasserstein distance across extensive state spaces, we can leverage the state aggregation method detailed in Theorem 4.4. It enables computing GBSM on small subsets of entire state spaces. By defining aggregation mappings $[\\cdot]:\\mathcal{S}\\_1\\rightarrow\\mathcal{U}\\_1$ and $[\\cdot]:\\mathcal{S}\\_2\\rightarrow\\mathcal{U}\\_2$ with aggregation thresholds where $\\max_{s\\in\\mathcal{S}\\_1}d^{1-1}(s, [s])\\leq\\sigma_1$ and $\\max_{s'\\in\\mathcal{S}\\_2}d^{2-2}(s', [s'])\\leq\\sigma_2$, we can bound the approximation error by\n\n$\\quad \\max_{s\\in\\mathcal{S}\\_1,s'\\in\\mathcal{S}\\_2}|d^{\\textnormal{1-2}}(s,s')-d^{[1]\\textnormal{-}[2]}(s,s')|$\n\n$\\leq  \\max_{s\\in\\mathcal{S}\\_1}d^{1-1_{[\\mathcal{S}]}}(s,s)+\\max_{s'\\in\\mathcal{S}\\_2}d^{2-2_{[\\mathcal{S}]}}(s',s')$\n\n$\\leq \\frac{1}{1-\\gamma} (\\max_{s\\in\\mathcal{S}\\_1} d^{1-1}(s,[s]) + \\max_{s'\\in\\mathcal{S}\\_2} d^{2-2}(s',[s'])) \\leq \\frac{\\sigma_1+\\sigma_2}{1-\\gamma}.$\n\nThe analysis shows that the error between the true GBSM and the GBSM computed on the aggregated spaces is bounded by $\\frac{\\sigma_1+\\sigma_2}{1-\\gamma}$. We will update Theorem 4.4 to include this explicit bound, clarifying the effectiveness of state aggregation for making GBSM scalable in high-dimensional environments.\n\nMeanwhile, there are well-established methods for efficiently approximating Wasserstein distance on large state spaces, such as the Hungarian algorithm-based approximation method [1] and the sliced Wasserstein distance method [2].\n\n> W.2 The numerical validation in Section 5 relies solely on synthetic MDPs with random perturbations…\n> \n\nTo demonstrate the real-world efficacy of our work, we have extended our validation to a **real-world scenario** involving a Digital Twin (DT)-driven DRL task for dynamic resource allocation in a real-world 5G wireless network testbed. In this setting, the real-world network serves as the target MDP, while its virtual replicas, i.e., DTs, act as source MDPs. These DTs are designed to capture the real-world dynamics in user traffic (transition probabilities) and sum throughput after resource allocation (rewards). We trained DRL policies within each DT and evaluated their transfer performance on the real-world network. \n\nCrucially, we employed our proposed aggregation and estimation techniques to compute the GBSM distance in a real-world scenario, quantitatively assessing the fidelity of each DT. This practical calculation procedure involves three key stages:\n\n1. **Empirical Model Construction**: The process begins by constructing an empirical model of the real network from a dataset $\\mathcal{D}$ with collected $(s_t, a, s_{t+1}, r)$ tuples. To ensure reliable estimation, a representative state set, $\\mathcal{U}\\_\\text{real} \\subseteq \\mathcal{S}\\_\\text{real}$, is identified based on data availability (i.e., states for which the number of samples exceeds a threshold). The empirical transition probabilities $\\hat{\\mathbb{P}}\\_\\text{real}$ and rewards $\\hat{R}\\_\\text{real}$ are then estimated from the collected data.\n2. **Closed State Set Formulation:** A key prerequisite for the iterative calculation of GBSM is the use of a closed state set, where for any state within the set, all reachable next states are also contained within it. It is formalized by: $\\forall a\\in\\mathcal{A}, \\forall s\\in \\mathcal{U}$, if $\\mathbb{P}(s'|s,a) > 0$, then  $s'\\in \\mathcal{U}$. By filtering the collected data, we first construct a closed representative state set $\\mathcal{U}\\_\\text{real}$ in the real MDP. Since the DT is a fully-known simulation model, we initialize the DT's representative set as  $\\mathcal{U}\\_\\text{DT} \\gets \\mathcal{U}\\_\\text{real}$ and iteratively expand it by adding any states that are reachable from the current $\\mathcal{U}\\_\\text{DT}$ until no new states can be added. This ensures a well-defined, closed state space for both real and DT MDPs.\n3. **Iterative GBSM Computation**: With the two approximated MDPs defined on closed sets  $\\mathcal{U}\\_\\text{real}$ *a*nd $\\mathcal{U}\\_\\text{DT}$, the GBSM is computed iteratively according to Theorem 3.2 until convergence.\n\nOur findings reveal a strong linear correlation between the calculated GBSM distance and the worst-case deployment performance of the transferred policy. This result not only validates GBSM's predictive capability on transfer regret in a real-world environment but also confirms its aggregation and estimation efficacy in scenarios beyond randomly-generated MDPs. We will incorporate the full results from this real-world experiment into the revised paper, including numerical comparison, a photograph of the Open 5G testbed and corresponding citation (currently omitted to ensure anonymity). While we cannot include plots in rebuttal, we would be happy to provide the raw data (calculated GBSM and corresponding real-world deployment performance) during the discussion period. \n\n# References\n\n[1] Lahn N, Raghvendra S, Saarinen E, et al. Scalable Approximation Algorithms for $p$-Wasserstein Distance and Its Variants. Forty-second International Conference on Machine Learning. 2025\n\n[2] Kolouri S, Rohde G K, Hoffmann H. Sliced wasserstein distance for learning gaussian mixture models. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018: 3427-3436."}, {"review_id": "LIHOO9AW7O", "reviewer": "Reviewer_QJ7u", "summary": "This paper rigorously introduces a definition for Generalized Bisimulation Metric (GBSM). The authors establish the existence and convergence of this metric and prove two fundamental properties analogous to those of standard BSM: symmetry and an inter-MDP triangle inequality. While not proving that the distance between identical states is zero, they provide an upper bound. The utility of GBSM is demonstrated through theoretical analyses of policy transfer, state aggregation, and sampling-based estimation, showing tighter error bounds compared to traditional BSM. Few numerical experiments validate these theoretical improvements and conclude the paper.", "questions": "Given my low confidence in assessing this paper, my questions are focused on clarifying points of potential misunderstanding.\n\n- In line 25, the triangle inequality appears to be defined with an equal sign. I assume this is a typo and should be \"less than or equal to\".\n\n- In line 166, the paper states it has \"rigorously proved the metric properties\". Given that the distance between identical states is only shown to be bounded - and not strictly zero - is using the word \"metric\" not an abuse of language?\n\n- In Theorem 3.6, a cost is defined for the shared value between distributions. Could you clarify the justification for this? My understanding is that the 1-Wasserstein distance should primarily concern the cost of moving the probability mass that is not shared.\n\n- The theoretical results are strong, but the conclusion is brief. Could you please expand on the potential impact this work could have on the field? Furthermore, how do your experimental findings relate to or advance the previous experimental work by Song et al. (2016)?", "limitations": "Limitations are not clearly stated. As previously mentioned, I encourage the authors to expand their conclusion.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "STRENGTHS:\n\n- The paper successfully defines GBSM and formally proves its existence and convergence.\n\n- The work provides complete proofs for the symmetry and inter-MDP triangle inequality properties of GBSM, filling a critical gap in multi-MDP analysis.\n\n- The authors derive explicit and tighter error bounds on policy transfer (Theorem 4.1), state aggregation (Theorem 4.4), and sampling-based estimation (Theorem 4.5) compared to BSM.\nThe theoretical claims are  validated through numerical experiments that directly compare the bounds derived from GBSM with BSM and the ground truth.\n\nWEAKNESSES:\n\n- The authors claim to have proven the pseudometric properties of GBSM, but a key property - that the distance of a state to itself is zero - is not established. They only provide an upper bound.\n\n- The paper mentions in the introduction the prior work of Song et al. (2016), which already demonstrated the utility of GBSM experimentally. However, the current paper's numerical results are never contextualized by or compared with these previous findings.\n\n- The MDPs used for the numerical experiments in Section 5 are not defined, making the results difficult to interpret and impossible to reproduce. The authors answered \"NA\" to the checklist question about experimental details, but this information is essential for a complete submission.\n\n- The paper does not clearly articulate the broader impact or potential consequences of the work. The conclusion would benefit from an expanded discussion of the work's limitations and its potential applications.", "was_revised": true, "final_justification": "The authors addressed all my questions, so I will keep my positive rating.", "rebuttal": "Thank you for your positive review and helpful comments! Please see responses to your questions below.\n\n> Q.1 In line 25, the triangle inequality …\n> \n\nThank you for identifying this typographical error, and it will be corrected in the revised manuscript.\n\n> W.1 The authors claim to have proven … They only provide an upper bound.\n> \n\n> Q.2  .. and not strictly zero … an abuse of language?\n> \n\nDifferent from BSM $d^\\sim(s,s')$ that defined for states within a single state space, our GBSM are defined for **arbitrary state-MDP pairs**, i.e., $d((s,\\mathcal{M}\\_1),(s',\\mathcal{M}\\_2))$, concisely written as $d^{1-2}(s,s')$ in our paper. In this context, a state $s\\in\\mathcal{S}$ within MDP $\\mathcal{M}\\_1$ is a fundamentally different object from the same state $s$ within another MDP $\\mathcal{M}\\_2$ with distinct P and R, even if they share the same state space. The non-zero distance $d((s,\\mathcal{M}\\_1),(s,\\mathcal{M}\\_2))$ is a precise measure of the behavioral dissimilarity arising from the different transitions where $\\mathbb{P}\\_1(s) \\neq \\mathbb{P}\\_2(s)$ and reward functions where $R_1(s) \\neq R_2(s)$. The truly \"identical” states appear when $\\mathcal{M}\\_1=\\mathcal{M}\\_2$, and we have the according zero-distance property as $d^{1-1}(s,s)=0$ through Theorem 3.6. Thus it is not an abuse of language. We will modify current “Distance bound on identical states” to “Distance bound on identical state spaces”, and describe the precise conditions where zero-distance is achieved. \n\n> Q.3 In Theorem 3.6, a cost is defined …\n> \n\nSimilarly, your understanding is correct for standard metrics where the cost of transporting mass from a location to itself would be zero, and we only need to consider the mass that is not shared. However, in our proposed GBSM framework, there exists a non-zero cost for shared mass between $(s,\\mathcal{M}\\_1)$ and $(s,\\mathcal{M}\\_2)$. Specifically, as we clarified in our previous response,  $d^{1−2}(s,s)$ is not necessarily zero because it quantifies the inherent difference between a state $s$ in $\\mathcal{M}\\_1$ and the same state $s$ within a different $\\mathcal{M}\\_2$, reflecting the inherent discrepancy in the rewards and transition dynamics across the two different MDPs.\n\nTherefore, in the transportation plan used to derive the bound in Theorem 3.6, preserving the shared probability between $(s, \\mathcal{M}\\_1)$ and $(s, \\mathcal{M}\\_2)$ would still undertake a non-zero cost of $d^{1−2}(s,s)$. The term $(1-\\text{TV}(P,Q))\\max_s{d}^{1-2}(s,s)$ in our proof is the upper bound for this part of cost in the transportation plan. It represents the maximum cost associated with distributions that are already aligned but exist in two fundamentally different MDPs.\n\n> W.2 The paper mentions in the introduction the prior work of…\n> \n\n> Q.4 How do your experimental findings relate to …\n> \n\nThank you for highlighting the need for comparison. While the idea of using BSM to evaluate similarity between MDPs was similarly proposed in (Song et al., 2016), their work was limited to **empirical evaluation** via Hausdorff distance, that is, $H(\\mathcal{S}\\_1,\\mathcal{S}\\_2;d)$.  They demonstrate a positive correlation between their measure and the transfer regret, without providing any provable bounds on policy transfer. Our GBSM framework makes it possible to theoretically analyze their measure, revealing that it is a simplified version of our transfer regret bound, corresponding to the first term in our Corollary 4.2 (without coefficient $\\frac{1}{1-\\gamma}$) and is only applicable to the ideal scenario of transferring the optimal source policy via the optimal source policy (eliminating the second term in Corollary 4.2) via an optimal state mapping (ensuring the max-min term from $H$). In contrast, our GBSM provides a **rigorous performance bound** for arbitrary policy and state mapping (Theorem 4.1).\n\nTo demonstrate this crucial difference, we have added a new numerical experiment to compare our GBSM-based transfer regret bound with the measure from Song et al. (2016) and the actual regret. The results show that the measure in Song et al. (2016) fails to bound the regret, whereas our GBSM-based bound is consistently effective.\n\n> W.3 The MDPs used for the numerical experiments …\n> \n\nThank you for pointing out this clarity issue. Current experiments use random Garnet-style MDPs with $|\\mathcal{S}| = 20, |\\mathcal{A}| = 5$,  and a 50% branching factor. In the aggregation experiments, half of the states are aggregated to a representative state. In the estimation experiments, we introduce a Gaussian noise with a standard deviation ranging from 0.1 to 0.3 into the transition probabilities. We would extend the current descriptions to improve the clarity of numerical experiments.\n\n> W.4 The paper does not clearly articulate the broader impact … limitations and applications.\n> \n\n> Q.4 Could you please expand on the potential impact …\n> \n\nThe first and foremost application is the **sim-to-real policy transfer**, where GBSM can be calculated between the simulated MDP and real-world MDP to predict transferred performance and serve as a metric for improving the simulation environment. To demonstrate the real-world efficacy, we have extended our validation to a real-world scenario involving a Digital Twin (DT)-driven DRL task for dynamic resource allocation in a real 5G network testbed (Detailed in the response to reviewer BQkW).\n\nThe second potential application is in **multi-task RL**, where GBSM can coordinate policy optimization across diverse environments, mitigating gradient interference issues. For example, GBSM can be used in clustering of tasks for more efficient training. Also, it can enhance gradient surgery methods by enabling a distinction: when tasks are truly divergent (high GBSM), surgery is necessary to prevent destructive interference. Conversely, when tasks are similar (low GBSM), gradient conflicts are more likely attributable to stochastic sampling noise, where intervention would be counterproductive. This GBSM-informed approach allows for more stable and efficient multi-task policy optimization.\n\nThe limitation mainly lies in the **discounted reward formulation**. In real-world RL, the goal is typically to maximize the long-term average reward. However, the GBSM, at least in its current formulation, is not compatible with average-reward setting. Considering that most of theoretical results in this paper are divided by $1-\\gamma$, taking $\\gamma$ to 1 yields an infinite result. We will discuss this limitation in our paper, and investigate a metric tailored for the average-reward Bellman equation in our future work."}]

Author rebuttal:

Meta-review: The paper generalizes the bisimulation metric (BSM) from a metric on the states of an MDP to a metric between the states of two MDPs, hence extending BSM to multi-MDP scenario.
The paper proves several properties of this generalized BSM, including relating the difference between the optimal value of two MDPs to their generalized BSM metric (Theorem 3.3), performance bound on policy transfer between MDPs (Theorem 4.1), and a sampling-based estimation of the error between the actual metric between two MDPs and the one learned using samples (Theorem 4.5). The paper provides some simple empirical illustrations too.

We have one accept (5), two borderline accepts (4), and one reject (2). The positive reviewers have low confidence (2 or 1), and the negative reviewer has high confidence (4).

All reviewers believe that the theory of this work is solid and rigorous. The main negative issues, raised by Reviewer xZ9L, are that (1) theoretical work are straightforward adaptation of existing results and (2) the suitability of the variant of BSM that is generalized.

Regarding point (2): The authors have provided the sketch of how different variants of BSM (lax bisumulation and on-policy bisimulation) can be generalized. 

Regarding the novelty (point 1), the main issue is not whether the results are already existing or not, as the previous similar theoretical results are for a single MDP and these results are for multi-MDP after all. The issue is whether the generalization of the existing results from a single MDP to multi-MDP case is easy or requires sophisticated mathematical techniques. I do not comment on the required level of sophistication, as I have not read the proofs. My stance, however, is that the more important point is the novelty of the problem setting, and not the novelty of the mathematical techniques required to prove results for the new problem setting. Since the problem setting is novel (metric between two MDPs), the paper does not lack novelty.

Overall, this is a reasonably good paper and should be accepted, despite its relatively lower average score. I ask the authors to consider the comments of all reviewers to improve their work. Specifically, I ask them to fully develop the proof of generalization of other notions of BSM. I also encourage them to include more practically "interesting" experiments to showcase the usefulness of their framework.
Decision: Accept (poster)