Understanding and Addressing the Pitfalls of Bisimulation-based Representations in Offline Reinforcement Learning
Authors: Hongyu Zang
Xin Li
Leiji Zhang
Yang Liu
Baigui Sun
Riashat Islam
Remi Tachet des Combes
Romain Laroche
Venue: NeurIPS 2023 poster (2023)
Keywords: Bisimulation metrics
Reinforcement Learning
Representation Learning
Offline RL
TL;DR: Bisimulation-based state representation learning has shown to be inefficient in Offline RL settings,

Abstract: While bisimulation-based approaches hold promise for learning robust state representations for Reinforcement Learning (RL) tasks,  their efficacy in offline RL tasks has not been up to par. In some instances, their performance has even significantly underperformed alternative methods. We aim to understand why bisimulation methods succeed in online settings, but falter in offline tasks. Our analysis reveals that missing transitions in the dataset are particularly harmful to the bisimulation principle, leading to ineffective estimation. We also shed light on the critical role of reward scaling in bounding the scale of bisimulation measurements and of the value error they induce. Based on these findings, we propose to apply the expectile operator for representation learning to our offline RL setting, which helps to prevent overfitting to incomplete data. Meanwhile, by introducing an appropriate reward scaling strategy, we avoid the risk of feature collapse in representation space. We implement these recommendations on two state-of-the-art bisimulation-based algorithms, MICo and SimSR, and demonstrate performance gains on two benchmark suites: D4RL and Visual D4RL. Codes are provided at \url{https://github.com/zanghyu/Offline_Bisimulation}.

Understanding and Addressing the Pitfalls of Bisimulation-based Representations in Offline Reinforcement Learning
Hongyu Zang', Xin Leiji Zhang', Yang Liu", Baigui Sun', Riashat Islam',
Rémi Tachet des Combes' Romain Laroche
Beijing Institute of Technology. China Alibaba Group, China
3 McGill University, Mila, Quebec AI Institute. Canada Wayve, UK
b edu. cn
bai261666, baw.bauui..bgglllaabbbaaaaaae riashat.. www.ammmmmm..mmilii.....a Tremi.tachet. romain aawaarrohheeaaallaalaaa
Abstract
While bisimulation baasullatoon-bused approaches hold promise for learning robust state repre- sentations for Reinforcement Learning (RL) tasks, their efficacy in offline RI tasks has not been up to par. In some instances, their performance has even significantly underperformed alternative methods. We aim to understand why bisimulation methods succeed in online settings, but falter in offline tasks. Our analysis reveals that missing transitions in the dataset are particularly harmful to the bisimulation principle, leading to ineffective estimation. We also shed light the critical role reward scaling in bounding the scale of bisimulation measurements and of the value error they induce. Based on these findings, propose apply the expectile operator for representation learning to our offline RL setting, which helps prevent overfitting to incomplete data. Mcanwhile, by introducing appropriate reward scaling strategy, we avoid the risk of feature collapse in rep- resentation space. We implement these recommendations bisimulation-baase algorithms, MICo and SimSR, and demonstrate performance gains benchmark suites: D4RL and Visual D4RL. Codes are provided at https:/ //gggtthbb..../ comm/anggyuu/Offlinn Bis iiisimulaionn
two state-of-the-art
Introduction
Reinforcement learning (RL) algorithms often require significant amount of data to achieve optimal performance [40, 48, 22]. In scenarios where collecting data is costly or impractical, Offline RL methods offer an attractive alternative by learning effective policies from previously collected data [29, 43, 32, 35, 16, 24]. However, capturing the complex structure of the environment from limited data remains challenge for Offline RL [4]. This involves pre-training the state representation offline data and then learning the policy upon the fixed representations [51, 47, 41, 53]. Though driven by various motivations, previous methods can be mainly categorized into classes: i) implicitly shaping the agent's representation of the environment via prediction and control of some aspects of the environment through auxiliary tasks e.g., maximizing the diversity of visited states [34, 10), exploring attentive contrastive learning on sub-trajectories [51], or capturing temporal information about the environment [47]: ii) utilizing behavioral metrics, such bisimulation metries [11, 13, 5]. to capture complex structure in the environment by measuring the similarity of behavior on the
"Corresoondence Xin Li.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

representations [52, 7]. The former methods have proven their effectiveness theoretically and empirically in Offline settings [41, 47, 51], while the adaptability of the latter approaches in the context of limited datasets remains unclear. This paper tackles this question.
Bisimulation-baser approaches, their name suggests, utilize the bisimulation metrics update operator to construct an auxiliary loss and learn robust state representations. These representations encapsulate the behavioral similarities between states by considering the difference between their rewards and dynamics. While the learned representations possess several desirable properties, such as smoothness [19], visual invariance [54, 1, 52], and task adaptation [56, 37, 46, 8], bisimulation-bast objectives in most approaches are required to be coupled with the policy improvement procedure [54, 6, 52]. In Offline RL, pretraining state representations via bisimulation-bast based methods is supposed to be cast as a special case of on-policy bisimulation metric learning where the behavior policy is fixed so that good performance should ensue. However, multiple recent studies [51, 21J suggest that bisimulation-basee bbased algorithms yield significantly poorer results on Offline tasks compared to variety of (self- Jsppervised objectives.
In this work, we highlight problems with using the bisimulation principle as an objective in Offline settings. We aim provide a theoretical understanding of the performance gap in bisimulation-bast approaches between online and offline settings:" wwhy do bisimulation approaches perform well in Online RL tasks but tend to fail in Offline RL ones?" By establishing a connection between the Bellman and bisimulation operators, we uncover that missing transitions, which often occur in Offline settings, can cause the bisimulation principle be compromised. This means that the bisimulation estimator can be ineffective in finite datasets. Moreover, we notice that the scale of the reward impacts the upper bounds of both the bisimulation measurement fixed point and the value error. This scaling term, if not properly handled, can potentially lead to representation collapse.
To alleviate the aforementioned issues, we propose to learn state representations based on the expectile operator: With this asymmetric operator predicting expectiles of the representation distribution, we can achieve balance between the behavior measurement and the greedy assignment of the measurement over the dataset. This results in form of regularization over the bisimulation measurement, thus preventing overfitting to the incomplete data, and implicitly avoiding -futt---isttitttion estimation errors. Besides, by considering the specific properties of different bisimulation measurements, we investigate the representation collapse issue for the ones that are instantiated with bounded distances (e.g., cosine distance) and propose way to scale rewards that reduces collapse. We integrate these improvements mainly on two bisimulation- based baselines, MICo [7] and SimSk [52], and show the effectiveness of the proposed modifications.
The primary contributions of this work are as follows:
We investigate the potential harm of directly applying the bisimulation principle in Offline settings, prove that the bisimulation estimator can be ineffective in finite datasets, and emphasize the essential role of reward scaling.
We propose theoretically motivated modifications on two representative bisimulation- baselines, including an expectile-baie -ased operator and a tailored reward scaling strategy. These proposed changes are designed to address the challenges encountered when applying the bisimulation principle in offline settings.
We demonstrate the superior performance approach yields through an empirical study on two benchmark suites, D4RL [15] and Visual D4RL [35].
2 Related Work
State representation learning in Offfine RL Pretraining representations has been recently studied in Offline RL settings, where several studies presented its effectiveness [3, 47, 41, 25]. In this paradigm, we learn state representations on pre-collected datasets before value estimation or policy improvement steps are run. The learned representation can then be used for subsequent policy learning, either online or offline. Some typical auxiliary tasks for pretraining state representations include capturing the dynamical [42] and temporal [47] information of the environment, exploring
"Since some bisimulation based approaches do not exactly use metrics but instead of pseudometrics, diffuse metrics or else, will use the term "measurement" in the following.

---

attentive contrastive learning on sub uub-trajectories [51], or improving policy performance by applying data augmentations techniques to the pixel-based inputs [9, 35].
Bisimulation- based methods The pioneer works by [20, 33] aim to overcome the curse of dimen- sionality by defining equivalence relations between states to reduce system complexity. However, these approaches are impractical as they usually demand an exact match of transition distributions. To address this issue, [12, 14] propose a bisimulation metric to aggregate similar states. This metric quantifies the similarity between two states and serves as distance measure to allow efficient state aggregation. Unfortunately, it remains computationally expensive as it requires full enumeration of states. Later, [5] devise an on-policy bisimulation metric for policy evaluation, providing scalable method for computing state similarity. Building upon this, [54] develop a metric to learn state representations by modeling the latent dynamic transition as Gaussian. [6] further investigate the independent couple sampling strategy to reduce the computational complexity of representation learning, whereas [52] propose to learn state representations built on the cosine distance alleviate representation collapse issue. Despite the promising results obtained, one of the major remaining challenges in this paradigm is its dependency on coupling state representation learning with policy training. This is not always suitable for Offline settings, given that obtaining on-policy reward and transition differences is infeasible due to our inability gather additional angnn-envirrommnt interactions. To adapt disimulation-basse the policy over the dataset as a specific behavior policy, and then apply the bisimulation principle on it to learn state representations in a pretraining stage, thus disentangling policy training from bisimulation-basse learning. Notably, although there exist recent studies [51, 42] investigating the potential of bisimulation-based methods to pretrain state representations, it has not yielded satisfactory results yet [51].
approaches to Offline settings, one solution is to consider
3 Preliminaries
3.1
Offline RL
We consider the standard Markov decision process (MDP) framework, in which the environment is given by a tuple M = AS,A, T, r, 7), with state space S, action space A. transition function that decides the next state s' ~ T[ a). reward function r(s, a) bounded by [Aimn- Rmax]. and discount factor E [0, 1). The agent in state & E S selects an action E A according to its policy, mapping T T--ss). We make use of the state value function (=((s = EM,, 150=0 7"r (st, ax) So = s] to describe the long term discounted reward of policy π starting at state s. In the sequel, we use T and r denote T(-|s, a) and r(s, a). respectively. In Offline RL, we are given a fixed dataset of environment interactions that include N transition samples, i.e. D = (s;, dis 8/, re) J We assume that the dataset D is composed of trajectories generated i.i.d. under the control of behavior policy ng. whose state occupancy is denoted by (s))))
states probability distribution over actions:
3.2 Bisimulation-basel Update Operator
The concept of bisimulation is used to establish equivalence relations on states. This is done recur- sively by considering two states as equivalent if they have the same distribution over state transitions and the same immediate reward [30, 20]. Since bisimulation considers worst-case differences between states, it commonly results in "pessimistic" outcomes. To address this limitation, the r-bisimulation metric was proposed in [5]. This new metric only considers actions induced by given policy π rather than all actions when measuring the behavior distance between states:
Theorem 1. [5] Let M. be the set of all measurements on S. Define F= M. - M by
F"( = 1r,, -r,,1 + WW(())
T T55)
where 81, 8j E ESS, - EoEA (alss)r =T,== क (als;)) and W(g) is the Wasserstein distance with cost function 9 between distributions. Then F" has least fixed point gE, and 9% is π r-bisimulation metric.
Although it is feasible to compute the behavior difference measurement g², by applying the operator F iteratively (which is guaranteed to converge to a fixed point since Jrd is a contraction), this approach comes at high computational complexity due to the Wasserstein distance on the right-hand
3

---

side of the equation. To tackle this issue, MICo [6] proposed using an independent couple sampling strategy instead of optimizing the overall coupling the distributions T, and T. resulting a novel measurement to evaluate the difference between states. Additionally, SimSR [52] further explored the potentiality of combining the cosine distance with bisimulation-bent based measurements to learn state representations. Both works can be generalized as:
F" 85) lr:. r, + BRGTT
|G" (5/ (G' 8/1
(2)
and F has a least fixed point G The instantiation of G varies in different approaches [6, 52]. For example, in SimSR [52], the cosine distance is used to instantiate G on the embedding space, and the dynamics difference is computed by the cosine distance between the next-state pair (s',, s)) sampled from a transition model of the environment. A more detailed description can be found in Appendix C.
The
Lemma 2. [6] (Lifted MDP) The Disimulation-basee update operator F" for M is the Bellman evaluation operator for a specific lifted MDP.
Due to this interpretation of the bisimulation based update operator the Bellman evaluation operator lifted MDP, we can derive certain conclusions about bisimulation by drawing inspiration from policy evaluation methods. In the next section, we will borrow analytical ideas from [17] to prove that the bisimulation- objective may be ineffective for finite datasets. We summarize all notations in Appendix A and provide all proofs in Appendix D.
4 Ineffective Bisimulation Estimators in Finite Datasets
The high-level idea of bisimulation- based state representation learning is to learn state embeddings such that when states projected onto the embedding space, their behavioral similarity is maintained. We denote our parameterized state encoder by Φ S + R" and a distance D(: .) in the embedding space Rn by G 85) = (s((s)) ((s))) For instance, D(:-)) may be the Eukaszyk-Karmonk distance [6] or the cosine distance [52]. To avoid unnecessary confusion, we defer implementation details to Section
When considering bisimulation-basse state representations, the goal is to acquire stable state repre- sentations under policy ı via the measurement G The primary focus is usually to minimize a loss over the bisimulation error, denoted by Ag. which measures the distance between the approximation G and the fixed point G
A (3), = IG - G (8i, 8;)l
However, since the fixed point GT is unobtainable without full knowledge of the underlying MDP, this approximation eтror is often unknown. Recall that in Lemma 2, we have shown that we can connect bisimulation- based update operator to lifted MDP. Taking inspiration from Bellman evaluation for the value function, we define the bisimulation Bellman residual oz. as:
(5), (st, (,) GF,,,
Then, we can connect the bisimulation Bellman residual with the bisimulation error by the following:
Theorem 3. (Bisimulation error upper-bound). Let (s(() denote the stationary distribution over states, let (-(-)) denote the joint distribution over synchronized pairs of states (s,, 8;) sampled independently from (.).)). For any state pair (s,, S x S, the bisimulation error Ag (S1, 85) can be upper-bounded by sum of expected bisimulation Bellman residuals ax
A 83)
- B ( (=)(),,)))
T-
Thereafter, the bisimulation Bellman residual used as a surrogate objective to approximate the fixed point G. when learning our state representation. Indeed, the minimization of the bisimulation Bellman residual objective over all pairs (s/, x4) ~ M4 leads to the minimization of the corresponding bisimulation error. This ensures that if the expected on-policy bisimulation Bellman residual (i.e.,
For readability, will conflate the notations T and GT (Ir, y). they the same if not specified
4

---

Egl and we will use the term "expected bisimulation residual" in following) minimization objective is zero, then the bisimulation error must be zero for the state pairs under the same policy. However, when the dataset is limited, rather than an infinite transition set covering the whole MDP, minimizing the expected bisimulation residual will no longer be sufficient to guarantee a zero bisimulation error.
Proposition 4. (The expected bisimulation residual is not sufficient over incomplete datasets). If there exists states si and s not contained in dataset 'D where the occupancy par (s 0z) > O and ue (s(3 [8. az) > 0 for some (ss: Sy) ~ Ha. then there exists a bisimulation measurement Gy and a constant C > 0 such that
For all ($i, 53) E D, the bisimulation Bellman residual eg (5,,, = O.
There exists (8i, 85) D, such that the bisimulation error (81, C.
As example, if we only have (s,, ag: si) and (5j, ag.7, st) in dataset, where both rewards equal to zero for state 8; and 5,, and if we choose (3)) C, and G7 (5) = C,C then the bisimulation Bellman residual is (5 x2) O, while the bisimulation error A = (* - 0 = C' is strictly positive. Note that this failure case does not involve modifying the environment in an extremely adversarial manner, it simply occurs when are required to estimate the representation of states with subsequent states that are missing from the dataset. Since the distance between the missing states can be arbitrarily large they are out-of-distribution, directly minimizing the Bellman bisimulation error could achieve the minimal Bellman bisimulation error over the dataset, while not necessarily improving the state representation.
In the context of Offline RL, since the dataset is finite, bisimulation based representation learning pretraining process over the behavior policy ng of the dataset D.
ought to be conceptualized However, the failure case above indicates that applying the bisimulation operator J and minimizing the associated Bellman bisimulation error does not necessarily ensure the sufficiency of the learned representation for downstream tasks. Ideally, if we had access to the fixed- point measurement then could directly minimize the error between the approximation G and the fixed-point However, given the static and incomplete nature of the dataset, acquiring the fixed-point explicitly is not feasible. From another perspective, the failure stems from out-of-distribution estimation errors. Assuming we could estimate the bisimulation exclusively with in-sample learning, this issue could be intuitively mitigated. As such, resort expectile regression regularizer, allowing us to circumvent the need for out-of-sample/ / unseen state pairs.
5 Method
In this section, we describe how we adapt existing bisimulation- based representation approaches to offline RL. We use the expectile-based operator to learn state representations that optimize the behavior measurement over the dataset, while avoiding overfitting to the incomplete data. In addition, we analyze the impact of reward scaling and propose as a consequence to normalize the reward difference in the bisimulation Bellman residual in order to satisfy the specific nature of different instantiations of the bisimulation measurement while keeping a lower value error. The psdudo-code of our method is shown in Algorithms in Appendix B.
5.1 Expectile- Bisimulation Operator
The efficacy of expectile regression in achieving in in-sample learning has already been demonstrated in previous research [28, 36). Consequently, we will first describe our proposed expectile-based operator, and subsequently show how expectile regression can effectively address the aforementioned challenge. Specifically, we consider the update operator as follows:
(3)) == arg min Eg, G7
wny (lr (-Ia)) [ + (1 (1-7)l (1=))
(6)
= E
AANT [Ir(s; az) - r(yj, az) + G (6/ (/) - (s),
target G
5

---

where è is the estimated one- bisimulation Bellman residual, x3 is the behavior policy, Gā is the target encoder, updated using an exponential moving average, and [+++ = max(", 0). Since the expectile operator in Equation 6 does not have a closed-form solution, practice, we minimize through gradient descent steps:
6% (ss: 83) t GO (s;, -
[+( + (1-
(7)
where is the step size. The fixed-point of the measurement obtained using this expectile- based operator is denoted as Gy. Although the utilization of the expectile statistics is well established, its application for estimating bisimulation measurement is not particularly intuitive. In the following, we will show how expectile-based operator can be helpful in addressing the aforementioned issue. First, it is worth noting that when 1/2, this operator becomes the bisimulation expectation of the behavior policy, i.e., Eyg [3] Next, we shall consider how this operator performs when r - 1. We show that under certain assumptions, our method indeed approximates an "optimal" measurement in terms of the given dataset. We first prove technical lemma stating that the update operator still a contraction, and then prove lemma relating different expectiles, finally we derive our main result regarding the "optimality" of our method.
Lemma For any E [0, 1), FF a "tr conttraccton, where "rr 1-22 min {T, 7) 1. Lemma 6. For any T, (0,1) with r' 2 t, and for all 81,85 E S and any a, we have G+ G
Theorem 7. In deterministic MDP and fixed finite dataset, we have:
lim G-(8i,8;) m-1
max a, S.L. Kgla;
G ((s))))))) (8).
(8)
where G (sss, ai), ($j, ())) is a fxxe-poont measurement constrained to the dataset and defined on the state-action space S A
(()),,))) - (r() r(8),
BB 1 S
max d'A.a at mata [ (1)))))
Intuitively, G~ az), ($3, az)) (z)) can be interpreted as state-action value function Q(5, ā) in lifted MDP M, and G_(,6,, 85) as a state value function (8).. We defer the detailed explanation to Appendix E.
1, we are effectively approximating the maximum (_((s, ((), (s,, a,)) over actions a'. , from the dataset. When set 1, the expectile- based bisimulation operator achieves fully in-sample learning: we only consider state pairs that have corresponding actions in the dataset. For instance, only when have (s',, E D and (s/, af)) D, can we apply the measurement of G As such, by manipulating т, we balance a trade-off between minimizing the expected bisimulation residual (for 0.5) and evaluating G ((s,(((,))))))) a,), (s,, az)) solely on the dataset (for T = 1), thereby sidestepping the failure case outlined in Proposition in an implicit manner.
Theorem 7 illustrates that, as T
5.2 Reward Scaling
Most previous works [5, 54, 6, 52] have overlooked the impact of reward scaling in the bisimulation operator. To demonstrate its importance, investigate a more general form of the bisimulation operator in Equation 2, given as:
G(s,,,)) = 17, -ral + Ch ET
(9)
We then can derive the following:
G GZ 83) F= 83) = Cr 1r,, - r., +c B (1/, xf)]
< C, (Amax Rmii)) Cb E3 (5(,,
(10)
Cr (Rmax
Raii) Cs max G% (5/, $/).

---

LAVIS
202
Effecivv Dinersionz
259
10-
393
6.-
-22
2r:51
-392
350
3800 1030
3009 1750 2009
Figure I: The effectiveness of Reward Scaling (RS) in SimSR on helfchheeaal-mddiu---xperrrrrr with results averaged on 3 random seeds. (Left) Effective Dimension [53] comparison: without RS. there is a significant reduction in the effective dimension, accompanied by marked increase in instability as training progresses. (Right) Numerical value comparison of estimated bisimulation Bellman residual: é is persistently greater than 0 in the absence of RS, which indicates that target G is invariably larger than Gg, suggesting that Gg does not achieve steady convergence.
Adopting the conventional settings of G. 1 and C = 7 as suggested in [6, 52], could possibly result relatively large upper bound of G between states. This due to the common practice of setting at 0.99. However, when bisimulation operators are instantiated with bounded distances, c.g., cosine distance, such a setting may be unsuitable. Therefore, it becomes important to tighten the upper bound.
Accordingly, we have (88, S Ge-(Rums- -
I-cs
Besides, we can also derive the value bound between the ground truth value function and the approximated value function:
Theorem 8. ( (Value bound based on on-policy bisimulation measurements in terms of approximation error). Given an MDP M constructed by aggregating states in w-neighborhood, and an encoder that maps from states in the original MDP M to these clusters, the value functions for the two MDPs are bounded
2w + Å (6 (o()))
(s) V"
(11)
c,(1 (1-1))
where Â = |10 - G% is the approximation error.
In essence, Equation 10 and Theorem 8 reveal that: (i) there is positive correlation between the reward scale o, and the upper bound of the fixed-point G and (ii) larger reward scale c, facilitates a more accurate approximation of the value function 1 (Ø(s)) to its ground-truth value V* (s). It is important to note that c, also impacts the value of Á, as depicted in Figure 7(Right)*. Therefore, it is crucial to first ensure the alignment with the instantiation of the bisimulation measurement, and then choose the largest possible e, to minimize the value eтrоr. For instance, as the SimSR operator [52] uses the cosine distance, C 7 is predetermined. We should thus e, E [0. 1 7 and apply min-max normalization to the reward function. This can make G < 1 and therefore be consistent with the maximum value of of the cosine distance. To achieve a tighter bound in Equation 1, we should then maximize the reward scale, setting to 1 Figure 7 illustrates the effectiveness of this reward scaling.
Experiments
6.1 Performance Comparison in D4RL Benchmark
Implementation Details We analyze our proposed method on the D4RL benchmark [15] of OpenAI gym MuloCo tasks [50] which includes a variety of datasets that have been commonly used in the
DDespite Figure 7Right) depicting the approximate residual è, we have drawn connection between eg and Ag in the Appendix, which reflect the possible situations for Å.

---

SimSR
MiCo
MICO+EBS
teSbcibaseline)
walker2d expert-222
hoppet-oxper.422
haltchoetah-opeetty2
144
walker/d-
hopper-medium-nn
halfcheotah mallthostah-mddduu-xxprtr
Cumulative Returns
15
r2
hopper replay
halfcheetah medium roplay
10
4
walker2d medium
hoppermedium-v2
Dalicheetah-medlmme
Timesteps
Figure 2: Performance comparison on 12 D4RL tasks over 10 seeds with one standard error shaded in the default setting. For every seed, the average return is computed every 10,000 training steps, averaging over 10 episodes. The horizontal axis indicates the number of transitions trained on. The vertical axis indicates the normalized average return.
SimBRt
MSRR-RS-EED
SiniER RS-EBS
Smi5R-RS
0.000
HICO-EBS
HIGa
MiCo
WICo+EBS
0.035
0.010
0.005
0.000
520
600
No Nomalizee 5co 15
Figure 3: Bootstrapping distributions for uncertainty in IQM (Le. inter-quartile mean) measurement on D4RL tasks (left) and visual D4RL tasks (right), following from the performance criterion in [2].
Offline RI. community. To illustrate the effectiveness of our method, we implement it on top of two bisimulation- baseed approaches, MICo [6] and SimSR [52]. It is worth noting that there two versions of SimSR depending on its use of a latent dynamics model: SimSR basic follows the dynamics that the environment provides, and SimSR full constructs latent dynamics for sampling successive latent states. We opt for SimSR_baa basic as our backbone, as it exhibits superior and more stable performance in the D4RL benchmark tasks compared to SimSR full. Additionally, explore the impact of bisimulation based representation learning on the downstream performance of policy learning, we build these approaches on top of the Offline RL method TD3BC [16]. We examine three environments: halfcheetah, hopper, and walker2d, with four datasets task: expert, medium- experr, medium-replay, and medium. We first pretrain the encoder during 100% timesteps, then freeze it, pass the raw state through the frozen encoder to obtain the representations that serve input for the Offline RI. algorithm. Further details on the experiment setup are included Appendix F.
Analysis Figure illustrates the performance of two approaches and their variants in the D4RI. tasks. We EBS to represent the scheme of employing the expectile-basee operator, while RS

---

denotes the reward scaling scheme. The latter includes both min- max reward normalization and penalization coefficient with (1-7) in the bisimulation operator. As discussed in Section 5.2, the role of reward scaling varies depending on the specific instantiation of GP. We observe that without RS, SimSR almost fails in every dataset, which aligns with our understanding of the critical role reward scaling plays. The results also illustrate that EBS effectively enhances the downstream performance of the policy for both SimSR and MICo. It is noteworthy that in this experiment, we set = 0.6 for the expectile in SimSR and 0.7 in MICo across all datasets, demonstrating the robustness of this hyperparameter. Regarding SimSR, when RS is applied (SimSR+RS), the performance is comparable to the TD3BC baseline, while the incorporation of the expectile-basse operator (SimSRRRS+EBB) further enhances final performance and sample efficiency. Besides, we additionally present the IQM normalized return of all variants in Figure 3. illustrating our performance gains over the backbones. Further, we have also constructed an ablation study to investigate the impact of different settings of t, the results show that suitable expectile is crucial for control tasks. We present the corresponding results in Appendix E.
6.2 Performance Comparison in V-D4RL Benchmark
Implementation details We also evaluate our method on a visual observation setting of DM- Control suite (DMC) tasks, V-D4RL benchmark [35]. Similar to the previous experiment, we add the proposed schemes on top of MICo and SimSR. In the experiments, we notice that the
Chact opont
with wiR
314
latent dynamics modeling can help to boost
corvaatee hama
performance for the visual setting, hence we use SimSR full the backbone. Addition- ally, we also notice that MICo often gives really poor performance in the V-D4RL benchmark, while adding latent dynamics alleviates the is- sue. Therefore, boost MICo with explicit dynamics modeling for a fair comparison. To compare the performance with the other rep- resentation approaches, we include 4 competi- tive representation learning approaches for Of- fline RI., including DRIML [38], HOMER [39],
18
12
with
430
Figure 4: Performance comparison on V-D4RL benchmark.
CURL [3]], and Inverse model [44]. Detailed descriptions of these approaches can be found in Appendix G.
Analysis We evaluate all aforementioned approaches by integrating the pre-trained encoder from each into an Offline RL method DrQ+BC [35], which combines data augmentation techniques with TD3BC. The results in Table I and Figure 4 illustrate the effectiveness of our proposed method, the numerical improvements are underlined with red upward arrows. Compared the other baselines, while SimSR+RS+EBS does not achieve the highest score in all datasets, it achieves the best overall performance. Besides, our modifications on MICo and SimSR consistently show significant improvements. This indicates that our proposed method is not only applicable to raw-state inputs but also compatible with pixel-based observations.
7 Discussion
Limitations and Future Work While remains constant in our D4RL experiments, optimal performance may arise under different settings, contingent on the specific attributes of the dataset. Therefore, to yield the best outcomes, one might need to set various value. However, this process could consume substantial computational resources. Another area of potential study involves evaluating the effectiveness of our approach in off-policy settings, given that off-policy settings may also lead to similar failure cases.
identify the most suitable
'Since MICo does not necessitate a particular upper bound, RS may be harmful to its performance. Our experiments have substantiated this observation, leading exclude the MICo+RS results from Figure 2.

---

Table Performance comparison with several other baselines on V-D4RL benchmark, averaged on
random seeds.
Dataset
CURL
DRIMLC
HOMER
ICM
MICo MICO+EBS
SimSR SinSK=RS+EBS
cheetah-run run-aahh-u---aee medium
392
524
475
365
177 477 (
391 + 491( 100)
walker-walk-meddie
444
480K /37)
cheetah-run medium renemtau---mmdium replay
271
395
306
251
335 -357
374 462( (82()88)
walker-walk-meen mulk-medium-replly
265
235
283
167
207 -240
197 - 240X /43)
chectal- medium expert
348
383
280
481 (/25)
547(
729
399
781
606
586 386-+355/"44)
755 845( 90)
cheetah-run-exxerr
200
310
218
237
308 -331
409 - 454( 45)
walker expert
- (277))
-
total
3426
3118
3114
2715
3253 5381
3507 7 4043 ( 536)
Conclusion In this work, we highlight the effectiveness of the bisimulation operator over incomplete datasets and emphasize the crucial role of reward scaling in Offline settings. By employing the expectile operator in bisimulation, we manage to strike balance between behavior measurement and greedy assignment of the measurement over datasets. We also propose reward scaling strategy to reduce the risk of representation collapse in specific bisimulation-based measurements. Empirical studies show the effectiveness of our proposed modifications.
Acknowledgments
This work partially supported by the NSFC under Grants 92270125 and 62276024, well the National Key R&D Program of China under Grant F0.2022YFC3300101.
10

---

References
[1] Rishabh Agarwal, Marlos C. Machado, Pablo Samuel Castro, and Marc G. Bellemare. Con- trastive behavioral similarity embeddings for generalization in reinforcement learning, In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May
3-7, 2021. OpenReview.net, 2021.
[2] Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C. Courville, and Marc G. Bellemare. Deep reinforcement learning the edge of the statistical precipice. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 29304 29320, 2021.
[3] Sanjeev Arora, Simon S. Du, Sham M. Kakade, Yuping Luo, and Nikunj Saunshi. Provable representation learning for imitation learning via bi-level optimization. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 367-376. PMLR, 2020.
[4] David Brandfonbrener, Rémi Tachet des Combes, and Romain Laroche. Incorporating explicit uncertainty estimates into deep offline reinforcement learning- In Proceedings of the 5th Multidisciplinary Conference on Reinforcement Learning and Decision Making (RIDM), 2022.
[5] Pablo Samuel Castro. Scalable methods for computing state similarity in deterministic markoy decision processes. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages (0069-10076. AAAI Press, 2020.
[6] Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland. Mico: Im- proved representations via sampling-basee state similarity for markov decision processes. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Anmual Confer- ence on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 301 10-33-01 2021.
[7] Pablo Samuel Castro, Tyler Kastner, Prakash Panangaden, and Mark Rowland. Mico: Learning improved representations via sampling-bast based state similarity for markov decision processes. CoRR, abs/2106.08229, 2021.
[8] Pablo Samuel Castro and Doina Precup. Using bisimulation for policy transfer in mdps. In Maria Fox and David Poole, editors, Proceedings the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 1 11-15, 2010. AAAI Press, 2010.
[9] Xin Chen, Sam Toyer, Cody Wild, Scott Emmons, Ian Fischer, Kuang- Lee, Neel Alex, Steven H Wang, Ping Luo, Stuart Russell, Pieter Abbeel, and Rohin Shah. An empirical investigation of representation learning for imitation. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
[10] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[11] Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In Deborah L. McGuinness and George Ferguson, editors, Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29, 2004, San Jose, California, USA, pages 550-951. AAAI Press / The MIT Press, 2004.
[12] Norm Ferns, Prakash Panangaden, and Doina Precup. Metrics for finite markov decision processes. In David Maxwell Chickering and Joseph Y. Halpern, editors, UAI '04, Proceedings of the 20th Conference in Uncertainty Artificial Intelligence, Barff, Canada, July 7-11, 2004, pages 162-169. AUAI Press, 2004.

---

[13] Norm Ferns, Prakash Panangaden, and Doina Precup. Bisimulation metrics for continuous markov decision processes. SIAM J. Comput. 4066):1662-1714 2011.
[14] Norman Ferns and Doina Precup. Bisimulation metrics are optimal value functions. In Nevin L. Zhang and Jin Tian, editors, Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence, UAI 2014, Quebec City, Quebec, Canada, July 23-27, 2014, pages 210-219. AUAI Press, 2014.
[15] Justin Fu, Aviral Kumar, Ofr Nachum, George Tucker, and Sergey Levine. D4RL: datasets for deep data-driven reinforcement learning. CoRR, abs/2004.07219. 2020.
[16] Scott Fujimoto and Shixiang Shane Gu. minimalist approach to offline reinforcement learning. In Advances Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 20132-20145, 2021.
[17] Scott Fujimoto, David Meger, Doina Precup, Ofrr Nachum, and Shixiang Shane Gu. Why should I trust you, bellman? the bellman error is a poor replacement for value error. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 6918 8884943. PMLR, 2022.
[18] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1582-1591. PMLR, 2018.
[19] Carles Gelada, Saurahh Kumar, Jacob Buckman, Ofir Nachum, and Marc G. Bellemare. Deep- mdp: Learning continuous latent space models for representation learning. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pages 2170-2179, PMLR, 2019.
[20] Robert Givan, Thomas L.. Dean, and Matthew Greig. Equivalence notions and model minimiza- tion markov decision processes. Artif. Intell., 147(1-2)::63322 2003.
[21] Pengjie Gu, Mengchen Zhao, Chen Chen, Dong Li, Jianye Hao, and Bo An. Learning pseudometric-based action representations for offline reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, edi- tors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 7902-7918. PMLR, 2022.
[22] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässsan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 1856-1865, PMLR, 2018
[23] Philippe Hansen-Estruch. Estruch, Amy Zhang, Ashvin Nair, Patrick Yin, and Sergey Levine. Bisimu- lation makes analogies in condiiondi reinforcement learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Muchine Learning Reseurch, pages 8407-8426. PMLR, 2022.
[24] Zhang- Wei Hong, Rémi Tachet des Combes, Pulkit Agrawal, and Romain Laroche. Harnessing mixed offline reinforcement learning datasets via trajectory weighting. In Proceedings of the 11th International Conference on Learning Representations (ICLR), 2023.
[25] Riashat Islam, Manan Tomar, Alex Lamb, Yonathan Efroni, Hongyu Zang, Aniket Didolkar, Dipendra Misra, Xin Li, Harm van Seijen, Remi Tachet des Combes, and John Langford. Agent-controller representations: Principled offline rl with rich exogenous information, 2022.
12

---

[26] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Claude Sammut and Achim Hoffmann, editors, Machine Learning, Proceedings of the Nineleenth International Conference (ICMI. 2002), University of New South Wales, Sydney, Australia, July 8- 12, 2002, pages 267-274. Morgan Kaufmann, 2002.
[27] Mete Kemertas and Tristan Aomtenttdo-Armstronn Towards robust bisimulation metric learn- ing. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jen- nifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 4764-4777, 2021.
[28] Iyy Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learning. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event April 25-29, 2022. OpenReview.net, 2022.
[29] Sascha Lange, Thomas Gabel, and Martin A. Riedmiller. Batch reinforcement learning. In Marco A. Wiering and Martijn van Otterlo, editors, Reinforcement Learning, volume 12 of Adaptation, Learning, and Optimization, pages 45-73. Springer, 2012.
[30] Kim Guldstrand Larsen and Arne Skou. Bisimulation through probabilistic testing. In Confer- ence Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, Austin, Texas, USA, January 11-13, 1989, pages 344-352. ACM Press, 1989.
[31] Michael Laskin, Aravind Srinivas, and Pieter Abbeel. CURL: contrastive unsupervised repre- sentations for reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 5639-5650, PMLR, 2020.
[32] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. CoRR, abs/2005.01643, 2020.
[33] Lihong Li, Thomas J. Walsh, and Michael L. Littman. Towards unified theory of state abstraction for mdps. In International Symposium on Artificial Intelligence and Mathematics, ISAIM 2006, Fort Lauderdale. Florida, USA, January 4-6, 2006, 2006.
[34] Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wort- man Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Confer- ence on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 18459-18473 2021.
[35] Cong Lu, Philip J. Ball, Tim G. J. Rudner, Jack Parker-Holder, Michael A. Osborne, and Yee Whye Teh. Challenges and opportunities in offline reinforcement learning from visual observations. CoRR, abs/2206.04779, 2022.
[36] Xiaoteng Ma, Yiqin Yang, Hao Hu, Jun Yang, Chongjie Zhang, Qianchuan Zhao, Bin Liang, and Qihan Liu. Offline reinforcement learning with value-based episodic memory. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022.
[37] Bogdan Mazoure, Ahmed M. Ahmed, R. Devon Hjelm, Andrey Kolobov, and Patrick MacAlpine. Cross-trajectory representation learning for zero-shot generalization in RL. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net. 2022.
[38] Bogdan Mazoure, Remi Tachet des Combes, Thang Doan, Philip Bachman, and R. Devon Hjelm. Deep reinforcement and infomax learning. Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 62, 2020, virtual, 2020.
13

---

[39] Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, and John Langford. Kinematic state abstraction and provably efficient rich- acchobbervatton reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6961-6971. PMLRR, 2020.
[40] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nat., 518(7540):529-533 533, 2015.
[41] Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6- 14, 2021, virtual, pages 30100-30112 2021.
[42] Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. CoRR, abs/2105. 102s/2215..2222,, 2021.
[43] Kimia Nadjahi Romain Laroche*, and Rémi Tachet des Combes. Safe policy improvement with soft baseline bootstrapping. In Proceedings of the 17th European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), 2019.
[44] Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven ex- ploration by self superviee prediction. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2778 2787. PMLR, 2017.
[45] Vitchyr Pong, Ashvin Nair, Murtaza Dalal, and Steven Lin. Rlkit, 2020.
[46] Anirban Santara, Rishabh Madan, Pabitra Mitra, and Balaraman Ravindran. Extra: Transfer- guided exploration. In Amal El Fallah Seghrouchni, Gita Sukthankar, Bo An, and Neil Yorke- Smith, editors, Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, AAMAS '20, Auckland, New Zealand, May 9-13, 2020, pages 1987-1989. International Foundation for Autonomous Agents and Multiagent Systems, 2020.
[47] Max Schwarzer, Nitarshan Rajkumar, Michael Noukhovitch, Ankesh Anand, Laurent Charlin, R. Devon Hjelm, Philip Bachman, and Aaron C. Courville. Pretraining representations for data-efficient reinforcement learning. In Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 26686-16699, 2021.
[48] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of go without human knowledge. Nat., 550(7676)):54--35, 2017.
[49] Adam Stooke, Kimin Lee, Pieter Abbeel, and Michael Laskin. Decoupling representation learning from reinforcement learning. In Marina Mcila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9870-9879, PMLR, 2021.
[50] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: physics engine for model-based control. In 2012 IEEE/RS International Conference on Intelligent Robots and Systems, IROS 2012, pages 5026-5033. IEEE, 2012.
[51] Mengjiao Yang and Ofir Nachum. Representation matters: Offline pretraining for sequential decision making. In Proceedings of the 38th International Conference Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 Proceedings of Machine Learning Research, pages 11784-1121 11794, PMLR, 2021.
14

---

[52] Hongyu Zang, Xin Li, and Mingzhong Wang. Simsr: Simple cestance-bassee state representations for deep reinforcement learning. In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, ThirrtyFourihh Conference
Innovafive Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 8997-9005. AAAI Press, 2022.
[53] Hongyu Zang, Xin Li, Jie Yu, Chen Liu, Riashat Islam, Remi Tachet des Combes, and Romain Laroche. Behavior prior representation learning for offline reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
[54] Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May
3-7, 2021. OpenReview.net, 2021.
[55] Amy Zhang, Shagun Sodhani, Khimya Khetarpal. and Joelle Pineau. Multi-task reinforcement learning as a hidden-parameter block MDP. CoRR, abs/2007.07206 2020.
[56] Amy Zhang, Shagun Sodhani, Khimya Khetarpal, and Joelle Pineau. Learning robust state abstractions for hidden-parand parameter block mdps. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
15

---

Appendix
Contents
A Notation
17
Algorithm
17
C Technical backgrounds
18
Bisimulation metric
18
C.2 MICo distance
19
C,3 SimSR operator
19
C.4 Lifted MDP
19
C.5 Expectile Regression
20
D Proof
20
Connection between bisimulation error and bisimulation Bellman residual
20
D.2 Thoerem 3
22
D.3 Proposition 4
22
D.4 Lemma 5
23
D.5 Lemma 6
24
D.6 Theorem 7
25
D.7 Theorem 8
25
Understanding of Theorem 7
26
F
Additional Experiments
27
E.1
Ablation Study Value of Expectile
27
F2 Ablation Study Effectiveness of Reward Scaling
27
F33 Case Study MICo
28
Additional Related Works
28
H
Additional Discussion
29
The severity of the proposed problem
H.2 Suitability of different techniques
29
Empirical estimation of bisimulation error
30
16

---

A
Notation
Table 2 summarizes our notation.
Table 2: Table of Notation.
Notation
Meaning
Notation
Meaning
M
MDP
M
Lifted MDP (juxilisry MDP)
8
Sible sjuce
A
action spice
7
transition Function
rewand function
discount
policy agent
V*(e)
state value function given policy e
cataset
Fa
behavior policy
Pole)
state occupancy of the dataset
co-policy bisimulation operalor
s2.
--bisimulaaiion metric
D(--)
specilic distance
GZ
lixed point MICo and SimSR
static encuder
parameiarized bisimulation messurement
Ag
bisintolation ctror
<3
bisimulation Belliann residual the distribution over pairs of states
psfe)
stationary distribution over states on policy
expected on-policy bisinulation Bellisn residual
behavior bisimulation openater
expeetílc term
discount fistor with expectile
behavior bisimulation operator with expectile
estimated one-step residual
G3
bisimulation measurement parameterizee by larget encuder (4)
meseurereent state-action space
G (Ai, di, 05.05)
maximum measurement constrained to datsset
seale term of reward in bisimulation
0
soale term trancition in bisimolarion
((((())
value
state
distance bound of appregating neighbor
A
approximation of bisimulation mensurement
B
Algorithm
We provide the algorithm in Algorithm and pytorch-like implementation build top of SimSR in Algorithm 2.
Algorithm 1 Proposed Implementation
1: Stage Preprocessing:
2: Min-Max reward normalization; Frue Tuiio
3: Stage 2 Pretraining the encoder:
4: Initialize encoder parameter é, expectile r, learning rate a, discount factor 7
5: for each gradient step do
6: Apply reward scaling when computing é
= (1 7)) 0z) F( F(3), &. (sh,
(12)
7: Update encoder d:
- Φ -
[r[]] + (1- (1-1))1- []]
(13)
8:
end for
9:
Stage 3 Training value function and policy network:
10: Initialize value function parameter th, policy network parameter 8, learning rate Xy and Ax-
11: for each gradient step do
12:
Sample tuple (s, a, 8', FF from dataset
13:
Encode the states to representation space: 2 = 0(8), x' = =(s0))
14:
Update value function with (z, a, F')::
1 = のे Av (v)
(14)
15: Update policy network with (z, a, F')):
0 = Aa (o)+
(15)
16: end for
17

---

Algorithm 2 SimSR+RS+EBS Pseudocode, PyTorch-like
class RepleyBuufer((bjeet)
def (self))
self www..aaaooooollllaaaataaa
rowrr__omaallllttonnccl
r_nax self-resard.max]
(seaf. r_min) (r_nax r_min)
compute_distancee
featuree_b)
similarity mantariitymmtrri torch.natuul (1eatures,, Ieaturea_b.I)
die 1-similarityyaaaaa
return die
losattil,,lossddff,,, expactile):
weight torch. ubere 6, expectile, (1 expectile))
raturn vaight (diff
encoder: encoder network, the output is 12-normalized
mip, same encoder, updated by discount: discount factor $'gannaš
slope: expectile Shtau8
def saauute_eb____eee wow.l (encoder, target_ancoden uepla__buffer batch_size, diacount, slope): observation,
revard, discount, next_obnervation replay_ sample sample
batch tuples from replay buffer
batent_state encader(asservatten))
target_encoder (pext_erpeet__bbeee (bborttobborvtttoon
r. r_diff = (1 discount) * torch abs (reward. revard)
next_diff compute_distance www.dddistttnaaeee dbattnncelatent_nnxx:
lstent_next_etate)
z_diff compute_divg distoddddtteeeeteeeee (latett__attttssttttee latent_ssatte) bisimilerity r_diff discount next_diff
eacoder_lose - expectile. Leciiiee_leee(CC encoder_ sonder_loss..ne (ean) return encoder_loss
s_diff, slope)
C Technical backgrounds
C.1 Bisimulation metric
Bisimulation measures equivalence relations on MDPs with a recursive form: two states are deemed equivalent if they share the equivalent distributions over the next equivalent states and they have same immediate reward [30, 20]. However, since bisimulation considers equivalence for all actions, including bad ones, it commonly results in "pessimistic" outcomes. Instead, [5] developed π bisimullation which removes the requirement of considering each action and only needs to consider the actions induced by policy
Definition 9. [5] Given an MDP M, equivalence relation E C S x S is a rTbisimulation relation if whenever (s, u) E. the following properties hold:
1. r(s, r
2. VC E EEE T(Css T(C[u, T)
where Sgr is the state space partitioned into equivalence classes defined by E Two states S are --bisimilar there exists n-bisimulation relation E such that (s. u) ET.
However, 7-bisimulation is still too stringent to be applied at scale as r-bisimulation relation emphasizes the equivalence is binary property: either two states are equivalent not, thus becoming too sensitive to perturbations in the numerical values of the model parameters. The problem becomes even more prominent when deep frameworks are applied.
Thereafter, they proposed a и r-bisimulation metric to leverage the absolute value between the immedi- ate rewards w.r.t two states and the 1- Wasserstein distance (W,) between the transition distributions conditioned on the two states and the policy æ to formulate such measurement:
Theorem 10. Define J M. Mi by F (d) u) |Rg Ry + T.) then J has
least fixed point d=, and d% is r-bisimulation metric.
18

---

Although the Wasserstein distance is powerful metric to calculate the distance between two probability distributions, requires enumerate states which is impossible in RL tasks of continuous state space. Various extensions have been proposed [54, 6, 52] to reduce the computational complexity. DBC [54] extend bisimulation metries to learn state representation, via minimizing the fi-norm distance of representations and the bisimulation metrics, meanwhile modeling the latent dynamics as Gaussian and utilizing W2 distance to compute it, which can be formulated as a closed- form result. However, DBC has several issues like loss function mismatch and specific requirements for Gaussian modeling, which limits its application and performance.
C.2 MICo distance
MICo distance [6], tackles the above issue by restricting the coupling class to the independent coupling to avoid intractable Wasserstein distance computation. The MICo operator and its associated theoretical guarantee are given as:
Theorem 11. [6] Given policy n. MICo distance J is defined as:
(5), Irs, -rāj BBe 1 (U)))
(16)
has a fixed point U
By considering the Wasserstein distance in the definition of bisimulation metries can be upper- bounded by taking restricted class couplings of the transition distributions. MICo restricts the coupling class precisely to the singleton containing the independent coupling, utilizing the Indepen- dent Couple sampling strategy to bypass the computation of the Wasserstein distance. However, MICo distance U requires to be a MikaszykkKKrrowsss metric, which does not satisfy the identity of indiscernibles. As a result, the approximated distance on the learned embedding space based on Lukaszyk-Karmows k-KKrmowski metric to measure the distance between dynamics, may suffer from the violation issue the identity indiscernibles.
the MICo distance, which involves a Lukaszyk-
C.3 SimSR operator
To avoid the potential representation collapse, SimSR [52] develop more concise update operator to learn state representation more effectively. Coupling with cosine distance, SimSR defines its operator as:
Theorem 12. [52] Given a policy æ, Simple State Representation (SimSR) is updated as:
F cos (ig 5j) = Ir". - -ra 1 + 7 (5,,()),8))
(17)
has the same fixed point MICo.
Further, considering the latent dynamics can be beneficial to representation learning, they additionally develop a form of operator including dynamies modeling:
Theorem 13. [52] Given a policy π,, and a latent dynamics model T, SimSR is updated as
F Focos((s, 35) =|r - -r", 1 T x o1
cost (2/12//22 2/)].
(18)
oce,)
If latent dynamics specified, F has fixed point.
When considering MICo distance and the basic version SimSR, we can notice that they have similar recursive iteration formulation. And therefore both works can be generalized under:
F Gd (si, 85) = Ir - r. + 71 Ei [G (G' (5,,,,)).
(19)
while the instantiation of G varies in these two approaches.
C.4 Lifted MDP
The connection between bisimulation-basee operators and lifted MDP can referred [6]. We provide the corresponding Lemma here for reference.
19

---

Lemma 2. (Lifted MDP) The bisimulation-basel update operator F for M. is the Bellman evaluation operator for a specific lifted MDP.
Proof. Given the MDP specified by the tuple (S,A, T, R), we construct a lifted MDP (5, R). by taking the state space to be S = S², the action space to be À = AA, the transition dynamics to ( (s()Ts; (s)) for all (st, sy), (5/ s() E S², a,,a A. and the action- independent rewards to be Rg = R(s,.,)) = lr - x for all 8,, E S. The
be given by [ (3')
) ((s),
(s..85)
Bellman evaluation operator J for this lifted MDP at discount rate y under the policy ((ā|s) = ग [a, 1 8,) = T ((.lss))((y)le is given by (for all G E R and (3,,8) E 8 x S):
(F) Rs + y Σ ((5)
FEŠ
(817))) = R( +7 Σ
Taune ((6) (a)) 8,),,
1r +7 E (4)
(1) -F OFM
(o(,0))ES²
C,5 Expectile Regression
Expectile regression, a method in statistics, is an extension of quantile regression that provides a more detailed analysis of distribution's 's tail. This technique aims to estimate the expectiles of conditional distribution, which are like per- centiles but with respect to the mean, not the median. In essence, expectile regression can help capture the structure of data variability and analyze extreme observations a more precise manner than quantile regression. The (0, 1) expectile of some random variable is defined a solution to the asymmetric least squares problem:
Expectiic los difirent
-101 405
-091
-20
1.0
Figure 5: The asymmetric squared loss used for expectile regression. Larger gives more weight to positive differences.
arg minEE x [1 (x m,)], my
(20)
where LT(x)= = | 1(u < 0)|u². That is, for r > 0.5, this asymmetric loss function downweights the contributions of values smaller than m, while giving more weights to shows the illustration of this asymmetric loss. More detailed descriptions can be found in [28, 36].
larger values. Figure 5
D Proof
D.1
Connection between bisimulation error and bisimulation Bellman residual
In this section, we will revise some definitions a bit for obtaining the equivalence between bisimulation error and bisimulation Bellman residual. We first define bisimulation error Ag that measure the distance of the approximation G to the fixed point G as:
= (5)()1,8)) (5(,
(21)
And define bisimulation Bellman residual c7 as:
G -FF
(22)
Notably, this is slightly different from the notation in Section 4 given the fact that we do not apply absolute value here. Then, we can have the following theorems.
20

---

Theorem 14. (The bisimulation Bellman residual can be defined as function of the bisimulation error)
(8 85) = (8),) BB
(23)
Proof. This follows directly from the bisimulation update operator:
(5) G7) 83) F* 83) (5) 5 83) (= + (8()),88))
(24)
(5())1))) - B. (
kf-
Theorem 15. (The bisimulation error can be defined as function of the bisimulation Bellman residual). For any state pair (8,,8) 8;) E S, the approximation ervor A (8i, 85) can be defined as a function of the Bellman bisimulation error EΦ
(5))))
E B
(25)
Proof. Our proof follows similar steps to the proof of Lemma 6.1 in [26] and Theorem 1 in [17]. First by definition:
s3(s G% (5),) G. (s):
(26)
GT 83) Cg(ss, 83) - (3)
Then we can decompose the error:
Ags 8,) = (s.. - (s, sy)
= Ggi -
|r - rzg
+ B
NTT
G (s(, +/31
|r r
E
-T=
(3% 8/))
27(66, 8811
=
GZ, -
|nT - rzgl
+ 7
BB
(5% 8311
+ 7 E STT
[A [5]]
TT~
sf-
(A Es) 83) + 2
(27)
By considering the operator G as the Bellman evaluation operator for the lifted MDP (See Section C.4). we can rewrite the formula as:
A (G)) (T) [A(("))
(28)
Then we can treat A as a value function and < (ō) as reward, we can see that:
A5(Z)
E ET [<)("")
(29)
1
Then we can obtain
(8(8)18))
E Pe [.3(sl.
(30)
1-
21

---

D.2 Thoerem 3
Theorem 3. (Bisimulation error upper-bound). Let pa denote the stationary distribution over states, let (-((,-) denote the joint distribution synchronized pairs of states (8i, 8y) sampled independently from ).). For any state pair (8r,8g) E S x S. the bisimulation error A (8i, 85) can be upper- bounde by a sum of expected bisimulation Bellman residuals eg:
(s,, 8,) S B(snes)> [c] ()).
(31)
Proof. We start from Equation 25 in Section D.I.
1
B Beliesiio (c(()),
(3; 1 [B (cT(s).))))
(32)
1 B Bell,e))mm ||c](66, s)]l
Then when we define bisimulation error (3,,, 8,) = [Ag(s,,)) s5)l and bisimulation Bellman residual (14, xf) = (5/, K4)l, we have
A (5(s))))) 5z) S 1- 1 E ( [c](((,,5))]
(33)
D.3 Proposition
Proposition 4. (The expected bisimulation residual is not sufficient over incomplete datasets). If there exists states a and s'y not contained in dataset D, where the occupancy (Ar [ a.) > 0 and fa (s') (5]1,,aa)) > 0 for some 8; "D,8 DD then there exists a bisimulation measurement and such that
For all (6:, 85) E D, the bisimulation Bellman residual c% (6;, 85) = 0.
There exists S5) E D, such that the bisimulation error A (S(, = C.
Proof. This is a direct consequence of Theorem 15. Let D' contain the set of state pairs (s/, s/) not contained in the dataset D, where the next-state pair occupancy Ha (s% st (/s, a, 8j az) 0. Let Dunique the set of unique state pairs in D. follows that
1 γ
A7 84)
E
Bishaai (E)(s).
Σ
Mr((s/, 8/)1 as, a5, 85, 8,)++))
(34)
Σ
Recall that ())))) 17 83) - MEEANT [ sy)l and there exists at least one a,
G(st,8;). such that (81, E D'. Since the sets D and D' are distinct, it follows that there exists measurement G such that (3))))))) 0 for all (8,, 8,) E D. but
1- Elg,sya ux(s,, s/180 a, 8y, (7),, = C.
1
22

---

D.4
Lemma 5
Lemma 5, For any T E [0. F7, F7 is a -y-cortraction, where "r = - 2a(11 m) {T, 1 - 7}.
Proof. Note that Fi/22 is the standard bisimulation operator for of which the fixed point is G To keep the notation succinct, will replace G with G. For any G1, G2,
F Gr 8,) G2
= =Gi(s,; 8,) +aB* - (G2(s,, 85) + [b")
(1 (G - G2(t,, + aB= [11 -1)1r r, + Gi((4.8) - - -1111)1r, - -
(35)
(1 () - G2($).83))
+ aBx -2((s,,,
(1 a)llG1 G2llo + ag||G1 62
(1 a[1->))]|G - G2ll
When 7 + ! 2. we introduce two more operators to simplify the analysis:
(F)G))(s 85) G(st, 85) + [² (F"G))(st, 85) = ((s,,8)) [0]
(36)
Now we show that both operators meet the Banach-fixed point theorem (e.g. - ||G - G2lloo). For any G₁, G2:
1 G2
(FI (FF
= G2 + [+ - [6,|+]
(37)
= G1 + [6:]+ (G2 + [5,1+)]
The relationship between G1 + [6,]+ and G2 + [6,]] exists in four cases:
6, 7 0, 6, 2 0, then
G1 + [+++ (G2 +
Gz($
(38)
6, < 0.000 63 < 0. then
G [8:]+ - (G2 + (6,]+) = Gi (81,8))) G2(81,
(39)
0: 2 0. 83 < 0, then
G + [ōi]+ - (G2 + (ō,]+)
= (1 - 7)(r - r3g + 7 (8%, 8/) - G2(8i, 85)
(40)
< (1 7)lr -r,,1-1,000 1 84) - (11-7)1r7 - rg GG 8f))
(s,,(s - G2(5), s5)),,
where the inequality comes from G2 83) (1 7)k -rū, 77G2(5(,
6, < 0, 0g 2 0, then
G + [0,]+ (G2 + (6,1-)
Gi 87) ((1 7)1r -rg G2(14, ())
(41)
S Gi 8)) G2(8),8));
where the inequality comes from (2()), $ (1 >>),, -r,, + 7722(66))))
23

---

As result, we have (FT 83) - (FF. 1 [G G2lloo. Combine F. and F we can rewrite J7 as:
83) -20 = (1 -
(1 [0- 22( - ||
2a
(42)
What's more
FiG((s, 83) G(st,88) + [B
-((s), 3/) + ( -aa((ss)))))
(43)
(1 -a))a +
When 7 > 1.4 for any G₁ and G2:
(F) 85) (F) 8y) = -11-2a)
G2(5),
+ 2 +2d1--11(FFF//):::)-000000111113
= -1-2x - 2(1 22) r) 83) - --------22011-11(((0------------ - (2) 21
- -2a -1 -201-22(((77])6:::))0[6666666660
(1 - 2
- 2(1 21) (ss,)) - &2(
+ + r) [[]]) - (s)(s
-2011 - 2r) 8,) 8))ll
(1 2a(1 - (1 - ())]](((sss))) - G2(8;,
(44)
When 2.2 for any G1 and Gz:
(F) 85) (F7
= (1 - 2a) (st, - G2(s)) ( ( +2000077(00(((()))))00000-0/
(1 2a 2T(1 2a) +od1--11(((FGGGGss:s))00CC1011
+ + - (F
- < - 2a - - 2a)) (2(5),)))1
+ a(1 - ()) - 62)ss,
+ +aa(1 - 27 ())) - G2(81,
8,)1
(1 - 2--2a(1 20r(1- -2((5 8;) oc.
(45)
D.5
Lemma
Lemma 6. For any T E [0, with r' 2 and for all 8;,8, E S and any a, we have G, 2 Gr.
Proof. We denote G., is the fixed point of applying the operator Fp,, and G, is the fixed point of applying the operator F,. Based on Equation 6, we have:
F, - &,,,,,
= (1 -1- (1-20))((s,55) 2n F G(o;, 8;) + 2a(1 - ('(
((1 2a)G(s; s3) + 22TFF 83) + +2a G(s. (46)
-2(77' - () CF( F_ sz))
20(7'-7)E"" []]+ [0] 20 0.
Therefore G,, > Gr.
24

---

D.6 Theorem 7
Theorem 7. In deterministic MDP and finite dataset, we have:
lim G+(si. T-
max
G² (1s;,) (8j. az)).
(47)
a,EA, KL Kgla (0p
where G (ss, an); (8j, az)) is fixed-point measurement constrained the dataset and defined on state-action space x A as
(s)
max df st (x00 6,)20
G2((s,, (6f).
(48)
Proof. First, we can easily proof that (8i, ais 8j, az) is fixed point. Define the corresponding operator of G is F*, know that F is contraction. Then, have
Corollary 16. For any T, 8,,85 S we have
G,(s,, 8,)
max
(s))
(49)
AAEAEE S.L. (.)
Proof. The proof follows from the observation that convex combination is smaller than maximum.
Besides, we also have
Lemma 17. Let X a real-valued random variable with a bounded support and supremum of the support is x², Then,
lim my
Proof. Same the Lemma in [28]. One can show that expectiles of random variable have the same supremum x². Moreover, for ti and 72 such that Tı < T2, we get mr S Myg. Therefore, the limit follows from the properties of bounded monotonically non-decreasing functions.
Combining Corollary 16 and Lemma 17, we can obtain the above.
D.7 Theorem
Theorem 8. (Value bound based on on-policy bisimulation measurements in terms of encoder error). Given MDP M constructed by aggregating states in w-neighborhood, and an encoder & that maps from states in the original MDP M to these clusters, the value functions for the two MDPs are bounded as
S 2w + A Va (xi))
v
(8:) (8:)
(50)
c, 7))
where â = ||. loo is the approximation error.
Proof. Let the reward function be bounded as R [0, []. à: + 3. and d(s;) ((3;) + (r 8z) lō(x;) o(s;)) 2w, conduct aggregat MDP M = (Š, RR. Let be
25

---

measure on S. Following Lemma 8 in [27], we have that:
/ CR (s))"()))-(()))
(=))))i(((())) $ {(0(s)) =EA(s)
+ (1 (1->)
/ (5'5ss TT"h (s'1z))
V* (11() Cr
de(z) + >11 - -Vx1
1 y-7
AEES
G (8) + + - zEO(s)
{()(8)
(51)
Thus, taking the supremum on the LHS, we have:
(1 (1-1) V (s:) (s:)
-x (o(s)))
$ / (s,))d(((()
G
E(o(s))
=Ep(s)
() + +I - -G7ll
E(o(s))
(52)
=Ed(#)
cF
(2w + Å)dE(=)
E(o(s))
#Ed(s)
(2w + D).
Therefore,
S 2w +
V= (8:) - -- (Q
(53)
(1(1-))
E Understanding of Theorem
Theorem 7. In deterministic MDP and fixed finite dataset, we have:
lim G- 8z) T+1
max A.E,EE S.L. (s (00
(())
(54)
where G ((s,, ax), (8j. a))) is a fixed-point measurement constrained the dataset and defined on the sate-action space S x A as
G G: a.). = (r(s..)) r(5),
max dEAcee meta (300
(55)
Given the MDP specified by the tuple (S, T, R), we construct a lifted MDP (8, A, Rt,, by taking the state space be S S², the action space be A = .A2, the transition dynamics to be given by (3') = T(o.s))) ((s), 8))) = To: (s/)TT) (s')) for all (st, s5), (5%, (%) E S a, aj E A. and the action independent rewards to be Rū Risc.ss) In r,,1 for all 81, 8,,8, E S. The
Bellman evaluation operator f for this lifted MDP at discount rate y under the policy ă (ā(s) (a,, ay1s,, 8,) (T) is given by (for all G s and (s,, 8,) S S):
(3) = Rs,a +y Σ (3')
max (3' a
(56)
26

---

Though similar, Equation 55 has more constraints as it requires the possibility of (s( and ( ({) are larger than zero in the dataset. such, we may also change the Equation 56 to:
(F) = Ra,a +
(s')
a'))
E,A
(57)
SE
(a
This is, indeed, equivalent the in-sample-style Q function [28]. Intuitively. G Gi (s). az))
can be interpreted as the optimal state-action value function (* a) in a lifted MDP M. Then G ((s,( (s), (1s,,,))) a,)) is the state-action value function (s, a) that associated with policy æ, and G~(s,,s) 8y) as state value function ($)). And therefore, we can connect our expectile- based bisimulation operator to the lifted MDP, where we can use the conventional analytics tools in RL analyze bisimulation operators.
Additional Experiments
F1
Ablation Study Value of Expectile
+-0.3
0.5
T- 0.7
T=0.4
expert
22
halfcheetah expert
15
4
20
walker2d medium expert
hopper medium expertiv2
halfchestah medium expert
Cumulative Returns
karrdd22 mwdium replay
hopper medium replay V2
halfcheetah medium replay
walker2d medium-22
medgum-m
hallchettahmmedimm2
Timesteps
Figure 6: Performance comparison on 12 D4RL. tasks over 10 seeds with one standard error shaded the default setting.
Here we present the ablation study of setting different expectile 7 E 0.4.00.4..... 0.73 in Figure investigate the effect of the critical hyper-parameter in EBS. The experimental results demonstrate that the final performance gradually improves with larger r. Notably, the most superior performance achieved when equals 0.6. However, when further increases to 0.7, the agent's performance suffers a sharp decline. We hypothesize that this could be due to the value function possibly exploding when is set larger values, subsequently leading poorer performance outcomes. This as expected since the over-large leads to the overestimation error caused by neural networks. The experimental results demonstrate that we can balance a trade-off between minimizing the expected bisimulation residual and evaluating "optimal" measurement solely on the dataset by choosing suitable
F.2 Ablation Study Effectiveness of Reward Scaling
In the experiment, we set 7 as 0.99 and e, will be 7 = 0.01 accordingly in RS. In this ablation experiment, considered different combinations of min-max normalization/saadariiiaz and
27

---

canuratvve Rourrs
Figure 7: Ablation studies 6 D4RL tasks 3 seeds with standard error shaded.
Cumuiitee Reuume
Timestoos
Figure Ablation studies on D4RL tasks over seeds on MICo.
various value of c, (including 1, 0.1, 0.01, and 0.001). The results in Figure 7 are consistent with our analysis in Section 5.2. The last two show better gains. As RS has tighter bounds, it excels in most datasets, validating our theory.
F33
Case Study on MICo
As we illustrate in Section 5.2 and Section 6, Results in Figure show that an unsuitable reward scaling dramatically decreases the performance while applying EBS will increase the performance in many datasets.
G Additional Related Works
Here present brief introduction of all the baselines used in the experiments:
TD3BC [16] add behavior cloning term to regularize the policy of the TD3 [18] algorithm, achieves a state-of-the-arr performance Offline settings.
DrQ+BC [35] combining data augmentation techniques with the TD3+BC method, which applies TD3 in the offline setting with regularizing behavioral-cloning term to the policy loss. The policy objective is: म = argmax [AQ(s, 7 (x)) - (IT())
DRIML [38] and HOMER [39] (Time Contrastive methods) learn representations which can discriminate between adjacent observations in rollout and pairs of random observations.
28

---

CURL [31] (Augmentation Contrastive method) learns representation that is invariant to class of data augmentations while being different across random example pairs.
Inverse Model [44] (One-Step Inverse Models) predict the action taken conditioned on the previous and resulting observations.
H
Additional Discussion
H.1 The severity of the proposed problem
How do bisimulation-baser objectives perform in other (online or goal-conditione)) settings? Various methods, such as DBC [54], MICo [6], SimSR [52], and PSE [1], have consistently demon- strated positive results in online settings, regardless of the presence of distractors. This evidence supports the efficacy of bisimulation techniques in online settings. Additionally, GCB [23] ex- celled in goal-conditioned environments, ExTra [46] showcased the power of bisimulation metric in exploration, and HiP-BMDP [55] successfully incorporated bisimulation into multi-task settings, highlighting its superior performance, all mostly in online settings too, with little work in offline RL. These studies suggest that when tailored to specific environments, bisimulation methods can excel. Despite these works, bisimulation methods have had little success when extended to offline settings, and our motivation is to tackle this problem.
While bisimulation objectives used in the offline setting are directly affected by missing tran- sitions, many other representation objectives may not. When referring to state representation learning, using bisimulation in offline settings presents challenges due to the two issues we outlined: the presence of missing transitions and inappropriate reward scales. Concurrently, there exists other representation objectives, like CURL [31], ATC [49], which focus on pairs of states without the explicit necessity for transition information. As consequence, they do not explicitly require account- ing for missing transitions or reward scaling in their objectives. This absence of direct influence sets methods. Yet, consider that bisimulation-
them apart from bisimulation-bnn have a theoretical edge and have proven effective online settings, Thus, we deem that our work is impactful in that delivers proof that bisimulation can be successful offline.
techniques
Compounded effect for bisimulation principle in offline settings. In online scenarios, state representations and policies are updated concurrently, while in offline settings, state representation is pre-trained before policy learning, with the two phases completely decoupled. Errors during representation learning offline settings can have a compounded effect on policy learning, leading to significant issues. This is the reason that missing transitions is particularly harmful to the bisimulation principle in offline settings. Although reward scales affect bisimulation universally, as offline settings require pretraining state embedding, any major discrepancy between this fixed representation and the policy parameter space can further undermine the learning process. Hence, the proposed solutions hold promise for enhancing bisimulation's 's efficiency in offline settings.
H.2
Suitability of different techniques
We provide EBS as a general method, which is applicable to all bisimulation- based objectives, given that they all adhere to the foundational principle of bisimulation. This principle revolves around the contraction mapping properties similar to the value iteration. Whenever there's 's an intent to employ bisimulation in offline scenarios, with aim to reduce the Bellman residual for approximating the fixed point, the outlined challenge emerges. Consequently, EBS holds the potential to enhance any bisimulation-based method, regardless of the distance they use.
EBS
In essence, the given theoretical analysis is applicable across all Disimulation-bassee objectives. However, the precise settings for hinge on the foundational distance. For instance, SimSR uses the cosine distance which has definitive bounds. As result, we need to infer the ideal setting from Equation and Theorem In contrast, the MICo-like distance and DBC employ L-K distance and L1 distance respectively, having bounds ranging from Consequently, they can adapt to more value settings. We propose our approach as a general method/principle employ a novel bisimulation metric or distance, especially in the context of offline RL.
RS
29

---

Table 3: The exact values of bisimulation eтror and bisimulation bellman residual
Transition number
100
500
1000
2000
Bisimulation error
0.2792
0.2891
0.2880
0.2915
Bisimulation Bellman residual
0.003
0.0009
0.0032
0.0016
I Empirical estimation of bisimulation error
In this section, we would like to conduct a toy experiment to empirically show that the bisimulation error could possibly be larger than bisimulation bellman residual in fixed/finite datasets.
Data collection To collect the evaluation dataset, we utilize TD3 [18] (a deterministic algorithm) instead of SAC [22] to avoid stochasticity. Firstly, train TD3 agent using the rikit [45] codebase until convergence. Then, we collect 10k transitions and select specific transitions (such as 10, 100, 1000, 5000...) from these 10k transitions with uniform probability form the evaluation dataset D. For determining termination, we follow the settings described in [18] and [22], considering a state terminal only if termination occurs before 1000 timesteps. If termination occurs before 1000 timesteps, we set 7
0; otherwise, we set 0.99.
Computation Given evaluation dataset D, the bisimulation Bellman residual cs computed by [D] Σ (er,)) (G& (y)) - (s), - (s), ag) + GGo (5))) and the bisim- ulation error Ag is computed by 1 ((s...)>D (Go (5) - G. (s,, s,))² where G. denotes the corresponding fixed point measurement. Since directly computing G. is challenging, we compute |V* (s²) " (sy)] instead, as they should be equal when considering the measurement the fixed point and the transition is deterministic. To compute (*(s). we reset the MuJoCo environment to the specific state s; and ran the policy for 1000 timesteps. Since the environment and policy are deterministic, single trajectory is sufficient to estimate the true value.
The results presented in Table 3, which indicates that the bisimulation error finite datasets is
indeed larger than the bisimulation bellman residual.
30


Reviews:
[{"review_id": "Mn9LccNZ2m", "reviewer": "Reviewer_vGKe", "summary": "Summary\n-------\n\nThis submission\\'s goal is to understand why bisimulation methods\nsuffers in the offline RL setting. The authors go on to propose two\nmethods that help learn a better bisimulation metric, that result in\nrepresentations that more faithfully capture state abstractions from\noffline datasets. The two methods are 1) (EBS) an expectile operator\nthat regularizes the learned state representation to in-sample learning\nand 2) (RS) a reward scaling where they tune the hyperparameter on the\nreward difference (with theory for further motivation). Experiments are\nconducted in offline RL using D4RL with either states or pixel-based\nobservations. The empirical results provide some evidence that RS+EBS\nimprove the learned bisimulation metric, and hence the state\nrepresentation.\n\nDecision\n--------\n\nThe theoretical results, at the intersection of bisimulation and offline\nRL theory, is interesting and novel. Besides the theory, however, I\nremain unconvinced by the empirical evidence and the severity of the\nproposed problem. As a result, I lean towards rejection. In the D4RL\nexperiments, it does not seem that there is a benefit to using the\nbisimulation metric at all. While there is a purported benefit in the\nvisual domain, it is not clear that this is due to RS+EBS or the fact\nthat there are two additional tunable hyperparameters. Moreover, the two\nmethods do not really address a novel problem. Missing transitions, and\nEBS, is an issue for offline RL in general, not necessarily isolated to the bisimulation metrics. Whereas the\nreward scale is an issue with the bisimulation metric, and not necessarily isolated to the offline RL setting.\nSo, while I like the spirit of the paper, I do not find the empirical evidence\nconvincing.", "questions": "Detailed Comments & Questions\n-----------------\n\n-   Line 38: \\\"objectives in most approaches are required to be coupled\n    with the policy improvement procedure\\\" What about their approaches\n    require coupling with the policy improvement procedure and why is\n    this important? Is this because they are using a $π^*$-bisimulation?\n\n-   Line 39-43: The point you are making here is that bisimulation\n    metrics do not work well in offline RL. The points about special\n    cases of online RL seem unrelated and are distracting from this main\n    point. Moreover, reference \\[19\\] provides no empirical evidence for\n    or against bisimulation metrics in offline RL. Moreover, the\n    empirical evidence in \\[42\\] suggests that all methods do worse in\n    the offline RL setting, and does not seem to suggest that\n    bisimulation in particular suffers in the offline setting.\n\n-   Line 48: The problem of missing transitions is an inherent problem\n    to all offline RL methods.\n\n-   Line 50: The problem of reward scale seems unrelated to offline RL?\n\n-   Lien 55: \\\"we can achieve a balance between the behavior measurement\n    and the greedy assignment of the measurement over the dataset.\\\" I\n    do not understand this statement. Are you claiming that the\n    expectile operator balances a type of exploration-exploitation\n    trade-off? If so, it is not clear how or why.\n\n-   Line 244: \\\"Most previous works \\[4, 45, 5, 43\\] have overlooked the\n    impact of reward scaling in the bisimulation\\\" The DBC paper in\n    reference 45 does in fact have a hyperparameter for reward scaling.\n    I think this sentence needs more qualification, because most\n    combined losses include a hyperparameter for tuning their relative\n    importance.\n\n-   Line 248: I have a hard time interpreting the conclusion based off\n    of the inequality following (10). The result is an upperbound on the\n    fixed point and both $c_k$ and $c_r$ are free variables on the right\n    hand of the inequality. But, what does this inequality tells us\n    about the trade-off of setting, for example, $c_k = 0$ thus\n    upperbounding the fixed point by 0? Different settings of $c_k$ and\n    $c_r$ lead to different fixed points, $G^\\pi_\\tilde$. By using this\n    inequality to set an upperbound on the distance, you are also\n    biasing the metric. For example, for smaller $c_k$, you are\n    considering states similar if the resulting immediate behavior is\n    similar and putting less weight on differences in long-term\n    behavior.\n\n-   \\\" However, when bisimulation operators are instantiated with\n    bounded distances, e.g., cosine distance, such a setting may be\n    unsuitable.\\\" I don\\'t see why this is inherently undesirable. The\n    bisimulation distance aggregates the cosine distance across a\n    trajectory via the bellman recursion. I do not see why they need to\n    have the same upper bound. What you are attempting here seems like,\n    in an RL analogy, putting the rewards and the value on the same\n    scale.\n\n-   \\\"with the maximum value of 1 of the cosine distance. To achieve a\n    tighter bound in Equation11, we should then maximize the reward\n    scale, setting cr to 1 − γ.\\\" I do not think that c~r~ is a free\n    parameter that can be chosen to tighten the bound. This is because\n    $c_r$ also determines the fixed point of the bisimulation metric and\n    the learned representation. But, accepting your result for the\n    moment, I do not see why you set $c_r$ to be $1-\\gamma$ and not some\n    arbitrarily large number.\n\n-   Analysis of Figure 2: I am not sure what to take away from these\n    results. Does the TD3BC baseline use any of the learned\n    representations, or is it trained from scratch from the raw state?\n    The goal of the paper is understanding and addressing the pitfalls\n    of bisimulation representations in offline RL. But, these result\n    suggest that bisimulation representations are neither needed nor\n    helpful for the downstream task. The motivation is undermined: even\n    if bisimulation representations are augmented with your suggested\n    changes (expectiles + reward scaling), we get roughly the same\n    performance as not using any bisimulation at all.\n\n-   MICo + RS: what does it mean that MICo does not necessitate an\n    upper-bound?\n\n-   Table 1: The results are not entirely convincing because the\n    pixel-based offline RL experiments are known to have high variance.\n    Without reporting confidence intervals, and by uisng only 3 seeds, I\n    do not find this evaluation convincing.\n\n-   Ablation: The reward scale coefficient, while motivated by theory,\n    is not ablated.\n\nMinor Comments\n--------------\n\n-   Line 32: No question has been posed yet, so it is not clear what\n    question this paper is answering. A question does occur a few\n    paragraphs down, so maybe this statement is an artifact?\n-   Figure 2: Some lines are dashed while others are not, and this is\n    not indicated in the legend.", "limitations": "The authors outline limitations in the expectile operator hyperparameter. Further, I see no potential negative societal concerns.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Strengths\n---------\n\n-   Interesting theoretical insights, combining 1) bisimulation theory\n    which casts a metric as a fixed point in a lifted MDP and 2) offline\n    RL theory which shows limitations of RL algorithms on limited\n    datasets.\n-   Presentation and initial motivation of the problem, bisimulation in\n    the offline setting, is clear. There is value in understanding the\n    role of bisimulation metrics, especially in the case of offline RL\n    where the learned representation is known to be important for\n    transfer.", "weaknesses": "Weaknesses\n----------\n\n-   While motivation is initially clear, it seems ultimately misguided.\n    The results in the reference (\\[42\\] in paper, Yang and\n    Nachum, 2021) does not suggest that bisimulation is particularly\n    poor in the offline setting. The bisimulation results are also poor\n    in the online setting, and the paper continues to show that several\n    methods perform worse in the offline setting, which is unsurprising.\n-   The two methods used to improve bisimulation in the offline setting\n    are either not unique to issue with bisimulation (missing\n    transitions) or not seemingly relevant to the offline setting\n    (reward scaling). Both of these methods do seemingly help improve\n    learning the bisimulation metric, but the empirical results are not\n    convincing that this is helpful over the baselines.\n-   Empirical results on D4RL are not entirely convincing, and the\n    reasons for excluding MICo+RS are not clear. The results in the\n    pixel-based D4RL, while seemingly an improvement on average, are\n    difficult to evaluate without confidence intervals and with only 3\n    runs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and feedback on our paper.  We have included new experimental results and some general discussion, please refer to our generic response and uploaded file to address these points. \n\n## The severity of the proposed problem\n\nOur study focuses on offline state representation learning, instead of offline RL algorithms or offline policy optimization per se. In this paradigm, policy improvement is achieved on top of the learned representation space, and using bisimulation methods to learn representations. Thereby, missing transitions can impact both offline RL algorithms and the bisimulation objective, causing compounding errors. In contrast, other representation objectives [A,B] are not affected by missing transitions since their objective do not explicitly depend on the transitions and underlying dynamics, for which other objectives have so far been shown to be beneficial in offline settings, unlike bisimulation. This is the primary contribution of our work.\n\n In addition, reward scaling is a crucial concern in the bisimulation principle, where a severe discrepancy may occur between the parameter space of the representation and the policy due to the cumulative effect, intensifying representation collapse in offline environments. In contrast, bisimulation objectives have been shown to be effective for online environments, therefore we take motivation from past works to adapt bisimulation methods to be effective for offline RL. \n\nAdditionally, TD3+BC has been shown to be an effective algorithm for rapid convergence and performance in offline RL already; in datasets where TD3+BC struggles to converge, we particularly show the significance of our methodology to be more palpable. Experimental results show that our method converges faster, leading to improved results, on almost 8 out of 12 datasets on standard benchmark settings. \n\n[A]: Mengjiao Yang, Ofir Nachum. Representation Matters: Offline Pretraining for Sequential Decision Making. ICML 2021\n\n[B]: Max Schwarzer, et al. Pretraining Representations for Data-Efficient Reinforcement Learning. NeurIPS 2021\n\n## Detailed questions\n\nDue to the character limits, we answer per questions below:\n\n- In online settings, most approaches use $\\pi$-bisimulation as opposed to $\\pi^*$-bisimulation, considering that we cannot ascertain $\\pi^*$ during policy improvement. Theoretically, employing bisimulation as a representation objective in online settings mandates iterating bisimulation objectives until they converge to their fixed point at each singular policy $\\pi$ during policy iteration. However, this is computationally inefficient. A more comprehensive analysis is available in Appendix A of the DBC paper.\n\n- (Follow above) Conversely, in offline settings, the behavior policy of the offline dataset is generally considered a fixed one. This is the primary distinction between online and offline settings for bisimulation. Consequently, superior performance in online settings should intuitively lead to similar results in offline settings. Paper [42] empirically substantiated the subpar performance of bisimulation in offline settings, and Paper [19] provided a clear corresponding explanation in Section 2.\n\n- We are concerned more with representation learning here instead of offline RL methods themselves. Please refer to the general response.\n\n- In general response.\n\n- No, the expectile operator strikes a balance between behavior and optimality, not exploration-exploitation. We have furnished a background description and insight into utilizing the expectile operator in Appendix C.5.\n\n-  We revise our description to ensure clarity and accuracy. Our objective is to provide theoretical guidance on adjusting reward scaling, rather than introducing a new hyperparameter. While it is true that many combined losses include a hyperparameter to balance their relative importance, our focus is distinct. We aim to guide the balance between immediate similarity and long-term similarity, considering the properties of the associated distance. \n\n- Indeed, a smaller $c_k$ will attribute lesser weight to variations in long-term behavior. When $c_k$ is set to zero, we formulate bisimulation purely via immediate reward, signifying the most greedy way to learn representation. This is precisely why we retain $c_k$ as fixed at $\\gamma$, aligning with the settings in value iteration.\n\n- This does not exactly parallel the occurrences for rewards and value. When we aggregate bounded distances such as cosine distance, the precise result we obtain is $cos(\\phi(x),\\phi(y)) \\in [-1,1]$. This indicates that we cannot procure any value outside this boundary, with the upper limit being inaccessible. When considering reward and value, we seldom utilize cosine distance to approximate the value (we scarcely employ tanh activation for value networks either).\n\n- Please refer to the above response and Line 260-270 in our main paper. \n\n- The others please refer to the general response.\n"}, {"review_id": "uC90yBrPnF", "reviewer": "Reviewer_aN21", "summary": "This paper addresses the problem of bisimulation-based representations in offline reinforcement learning tasks, which are less effective than alternative methods. To address this issue, the paper proposes a tailored reward scaling strategy and an auxiliary loss function based on bisimulation metrics to learn robust state representations. The experiments show that the proposed method outperforms existing methods on a range of locomotion tasks in the DeepMind Control Suite. Ablation studies suggest that the proposed reward scaling strategy and bisimulation-based loss function are critical to the performance of the method. Overall, I believe this work makes a valuable contribution to the field of reinforcement learning by improving the effectiveness of bisimulation-based representations in offline RL tasks.", "questions": "See above", "limitations": "See above", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "**Motivation and intuition**\n- The motivation for addressing the pitfalls of bisimulation-based representations in offline reinforcement learning is convincing. The authors clearly explain the challenges faced by bisimulation-based approaches in offline RL tasks and the need for solutions to improve their performance. Their analysis reveals that missing transitions in the dataset, which often occur in offline settings, are particularly harmful to the bisimulation principle\n\n**Novelty**\n- The idea of utilizing expectile operators to prevent overfitting to incomplete data is intuitive and convincing, which is theoretically supported by the paper's analysis. This paper presents an effective way to implement this idea, which has not been explored in previous works.\n\n**Technical contribution**\n- The proposed solutions, an expectile-based operator and a tailored reward scaling strategy, for addressing the pitfalls of bisimulation-based representations in offline RL tasks seem compelling, especially when dealing with limited datasets. The authors provide a thorough analysis of the performance gains achieved by their proposed solutions in various benchmark suites.\n\n**Clarity**\n- The overall writing is clear and well-organized. The authors utilize figures well to illustrate the ideas, and Figure 1 clearly shows the results with and without reward scaling. \n- The paper gives clear descriptions in both theoretical and intuitive ways. The notations, formulations, and theorems are well-explained in the appendix, making it easy for readers to follow the technical details.\n\n**Experimental results**\n- The experimental results are impressive and demonstrate the effectiveness of the proposed framework in improving the performance of bisimulation-based approaches in offline RL tasks. The authors provide clear visualizations of the results, and Figure 3 particularly provides a clear comparison of the performance gains achieved by the proposed framework over the two state-of-the-art bisimulation-based algorithms, MICo and SimSR.\n\n**Reproducibility**\n- The code is provided, which helps understand the details of the proposed framework.\n- Given the clear description in the main paper and the details provided in the appendix, I believe reproducing the results is possible. ", "weaknesses": "**Ablation study**\nThe proposed framework comprises two components: an expectile-based operator and a tailored reward scaling strategy. Conducting an ablation study to verify the proposed methods to some naive ones would be good. Take the tailored reward scaling strategy for example, one possible naive reward scaling strategy could be to multiply the reward signal by a constant factor, such as 0.1 or 10, and observe the effect on the performance of the bisimulation-based RL algorithm. Another possible method could be to clip the reward signal to a certain range, such as [-1, 1], and observe the effect on the performance.\n\n**Limitation**\nI notice that the authors say that Since MICo does not necessitate a particular upper bound, RS may harm its performance, leading them to exclude the MICo+RS results from the main experiments. It would be good to elaborate more on when the two methods, an expectile-based operator and a tailored reward scaling strategy, can help improve the performance of given algorithms.\n\n**Experiment setup**\n I think that adding manipulation and navigation environments to the experimental evaluation of the proposed method would be a valuable addition to the paper. While the locomotion environments used in the current evaluation provide a good testbed for evaluating the proposed method, it would be beneficial to evaluate the method in a broader range of environments to better understand its generalizability and effectiveness across different types of tasks instead of only evaluating on locomotion environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and favorable assessment of our work! We appreciate the time and effort you have put into evaluating our work. Based on your feedback, we included additional rebuttal experiments, on benchmark D4RL tasks and on visual image-based offline tasks, to demonstrate the significance of our approach (please see attached rebuttal pdf). We also prefer a more in-depth discussion regarding the aptness of the techniques we have proposed. Please refer to our generic response for all reviewers to address these points. We proceed with our response to each concern as follows:\n\n- **Question: Conducting an ablation study to verify the proposed methods to some naive ones would be good. Take the tailored reward scaling strategy for example, one possible naive reward scaling strategy could be to multiply the reward signal by a constant factor…**\n\n- **Response**: Thanks for your suggestion!  We concur that an extensive ablation analysis would indeed enrich our work significantly. We have incorporated an ablation study of the reward scaling strategy in the attached PDF file. In brief, as deliberated in Lines 260-270 of our paper, only when we employ min-max normalization and set $c_r\\in[0,1-\\gamma]$, can we guarantee alignment and attain commendable performance; the other combinations of reward scaling strategy invariably fall short across all datasets. Please refer to the general response for more details.\n\n- **Question: It would be good to elaborate more on when the two methods, an expectile-based operator and a tailored reward scaling strategy, can help improve the performance of given algorithms.**\n\n- **Response**: Thanks for your insightful suggestion. We have provided a general response discussing the suitability of different techniques, and we will also add the corresponding descriptions in the revision. Briefly, the theoretical analysis of both techniques is suitable for all bisimulation-based objectives, but their practical applications may vary. Specifically, the Expectile-Based Scaling (EBS) can be applied to any bisimulation objectives when we consider using the bisimulation principle in offline settings. As for Reward Scaling (RS), we only need to consider it when the distance used in bisimulation is tightly bounded. For example, the range of L1/L2 distance and MICo-like distance (diffuse metric) is $[0,+\\infty]$, the range of cosine distance is $[-1,1]$. Therefore, bisimulation with L1/L2/MICo, which fall into the former category, do not need to use RS; bisimulation with cosine distance or some similar distance, which fall into the latter category, do require RS. We hope this clarifies any confusion, and we are happy to provide further explanation if needed.\n\n- **Question: adding manipulation and navigation environments to the experimental evaluation of the proposed method would be a valuable addition to the paper.**\n\n- **Response**: We fully agree with your suggestion that including experiments in manipulation and navigation environments would indeed strengthen the generalizability and robustness of our research. However, given the limited time window of the current rebuttal stage and our computational resources, we have prioritized completing some other experimental supplements first. For instance, we have focused on conducting the ablation study on reward scaling in d4rl tasks and running experiments with more seeds in the vd4rl tasks. Regarding the navigation tasks and other experiments,  accomplishing them necessitates more time. We plan to explore these experiments later and conduct an evaluation on larger-scale datasets to provide more robust evidence of the potential of the bisimulation method. \n\nOnce again, we appreciate the insightful comments and are grateful for the opportunity to improve the quality of our work. If you have any further suggestions or guidance, we would be more than happy to incorporate them into our work.\n"}, {"review_id": "6wSSWbCIet", "reviewer": "Reviewer_LXid", "summary": "This paper focuses on understanding and ameliorating the relatively poor performance of bisimulation-based representations in offline RL. The authors identify two main issues: overfitting to incomplete data and reward scaling. When the offline dataset is missing states, the representation that’s learned may not actually reflect the true bisimulation metric of the underlying MDP even if the associated Bellman residual over the dataset is zero. Their approach is to regularize learning with expectile regression to avoid overfitting to the incomplete data. With regards to reward scaling, the authors show that a larger reward scale can produce a more accurate approximation of the value function. Experiments are carried out on continuous control tasks with both proprioceptive and visual inputs. ", "questions": "- Can the authors provide learning curves + IQM analysis for the V-D4RL experiment? \n\n- Could the authors run experiments with MICo + RS (and MICo + RS + EBS) as well? If RS is not applicable to MICo for some reason, could the authors add a note either in the appendix or main text explaining why? ", "limitations": "The authors do an adequate job acknowledging the limitations of their approach, but perhaps more discussion would be helpful in the appendix. I don’t see any direct negative societal implications of this work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The theoretical analysis seems carefully done and gives useful, practical insights, and the connection of the bisimulation update operator to policy evaluation is interesting. \n\n- The careful evaluation of the proposed approach in the D4RL experiments is fairly convincing that the modifications proposed by the authors produce some improvement in performance. ", "weaknesses": "- In the D4RL results, SimSR + RS + EBS only clearly outperforms the other approaches on 3, possibly 4, of the 12 settings. \n\n- It would be helpful to have either more qualitative analysis of the existing experiments or a toy experiment to provide intuition as to the resulting behavioral differences and success/failure cases induced by the authors’ approach rather than just performance plots. \n\n- Running the V-D4RL benchmark over only 3 seeds seems rather low, and no measures of variance are provided. This stands in contrast to the D4RL results, for which not only full learning curves with error shading are shown, but also IQM measurements. \n\n- More discussion (possibly in the appendix) regarding the variation in performance across different datasets would be helpful.\n\n- Clarity could be improved in some areas, particularly in providing more background to the introduction of the expectile-based operator how it aids in in-sample learning / prevents overfitting to incomplete data. More precise language would also be helpful in the reward scaling section.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and feedback on our paper. We have included new experimental results and some general discussion, please refer to our generic response and uploaded file to address these points.\n\n- **Question: In the D4RL results, SimSR + RS + EBS only clearly outperforms the other approaches on 3, possibly 4, of the 12 settings.**\n\n- **Response**: Our proposed methods RS and EBS are essential for SimSR to achieve success on all datasets. By incorporating RS+EBS, the agent pretrained with SimSR demonstrates superior performance. Additionally, EBS significantly improves MICo's performance on 7 out of 12 datasets, providing strong evidence supporting our analysis. Considering that TD3+BC is already recognized for its rapid convergence and superior performance, it is expected that enhancements may not be substantial on simple datasets. In RL, sample efficiency and convergence rate are crucial. Faster convergence holds more practical significance and is preferred by the community, even if two algorithms have similar performance. This is particularly important due to the extensive training iterations required in RL. Our methodology becomes even more evident in datasets where TD3+BC struggles to converge. We observe that our method converges more rapidly on 8 out of 12 datasets, as evident from the performance curve.\n\n- **Question: It would be helpful to have either more qualitative analysis of the existing experiments or a toy experiment to provide intuition rather than performance plots.**\n\n- **Response**: We have provided examples for each case in Lines 180-188 and Figure 1 respectively.  To illustrate the failure case of missing transitions, we consider a scenario where only (s_i, a_i, r, s′_i) and (s_j, a_j, r, s′_j) are present in the dataset, with both rewards equal to zero. The bisimulation Bellman residual could be zero, but the bisimulation error could still be positive in this case. Failure cases like this can be found in many instances. To highlight the importance of selecting a suitable reward scale, we analyze the upper bound of the cosine-based bisimulation - SimSR. We also demonstrate that without a proper scale of reward, the effective dimension of the state feature will dramatically decrease, as shown in Figure 1 Left. These examples aim to provide an intuitive understanding of our proposed techniques. It is possible that the reviewer did not notice these descriptions due to the way we presented. We will consider adjusting the structure to make them more prominent.\n\n\n- **Question: Running the V-D4RL benchmark over only 3 seeds seems rather low, and no measures of variance are provided. This stands in contrast to the D4RL results, for which not only full learning curves with error shading are shown, but also IQM measurements. Providing learning curves + IQM analysis for the V-D4RL experiment.**\n\n- **Response**: Thanks, we provided a more comprehensive performance comparison on the V-D4RL benchmark in the uploaded file, which is averaged over 10 seeds with one standard error shaded. We have also included IQM measurements among these datasets to demonstrate their effectiveness. These results can be found in Figure 3 and Figure 4 in the attached PDF file. We believe these additional experiments will help address concerns regarding the reliability of our method.\n\n- **Question: More discussion (possibly in the appendix) regarding the variation in performance across different datasets would be helpful.**\n\n- **Response**: Thank you for your suggestion. We will add these in revisions. Different datasets inherently possess unique characteristics, leading to variations in performance [A]. All 12 tasks in Figure 2 are considered somewhat relevant, with each column representing a specific task domain and each row representing the form of data collection. Due to variations in data quality and task nature, it is normal for algorithms to exhibit performance differences across these datasets. More details can be found in [B].\n\n[A]: Schweighofer K, Hofmarcher M, Dinu M C, et al. Understanding the effects of dataset characteristics on offline reinforcement learning[C]//Deep RL Workshop NeurIPS 2021. 2021.\n\n[B]: Fu J, Kumar A, Nachum O, et al. D4rl: Datasets for deep data-driven reinforcement learning[J]. arXiv preprint arXiv:2004.07219, 2020.\n\n- **Question: Clarity could be improved in some areas, particularly in providing more background to the introduction of the expectile-based operator how it aids in in-sample learning / prevents overfitting to incomplete data. More precise language would also be helpful in the reward scaling section.** \n\n- **Response**: Thanks, we will provide more relevant background information and descriptions to help readers follow the technical details more easily in revisions. \n\n- **Question: Could the authors run experiments with MICo + RS (and MICo + RS + EBS) as well? If RS is not applicable to MICo for some reason, could the authors add a note either in the appendix or main text explaining why?**\n\n- **Response**: We have additionally added the corresponding results in Figure 2 in uploaded pdf file, the detailed explanation can be found in general response. We also provided a discussion of the suitability of our proposed techniques in general response. We hope these results/discussions can satisfy reviewer’s concerns.\n"}, {"review_id": "j1sLS3tXTH", "reviewer": "Reviewer_KC23", "summary": "The paper discusses the pitfall of bisimulation-based methods in offline RL. It identifies missing transitions in the finite dataset as a significant problem for bisimulation-based methods, leading to ineffective estimation. The paper also highlights the importance of reward scaling in bounded cosine distance method.\n\nTo address these issues, the paper proposes using the expectile operator for the measurement learning in offline RL, as expectile operator helps prevent overfitting to incomplete data. Additionally, the paper analyzes the upper bound of metric w.r.t. the reward scale and proposes a reward scaling strategy to reduce representation collapse.", "questions": "1. Lemma 5 and 6 require a citation to [4].\n1. How does the value of $c_r$ affect the value bound according to Theorem 8 and Theorem 15?\n1. How is Eq. (29) derived from Eq. (28) in Theorem 15 in the Supplementary Material?\n1. It is confusing that the main text defines $\\Delta$ and $\\epsilon$ as absolute values, while the supplementary material defines them as differences. The authors should use different notations (rather than the same $\\Delta$ and $\\epsilon$) in the supplementary material. \n1. What is the value of $\\tau$ in Table 1?\n1. Some implementation details are missing, including the learning rate and network architecture.\n\n-----\nReference\n\n[4] Ma et al. Offline Reinforcement Learning with Value-based Episodic Memory. ICLR 2022.", "limitations": "The authors should clarify the motivation of expectile operator and refine the theoretical analysis with cosine distance.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper establishes a connection between the Bellman and bisimulation operators to understand the gap for bisimulation-based approaches in online and offline RL settings. It defines the bisimulation Bellman residual and the bisimulation error and analyzes the gap of between minimizing them. \n\nThis paper also analyzes the bounds of the bimiluation-based metric and how the reward scaling affects the cosine distance. It demonstrates that setting the reward coefficient to $1-\\gamma$ improves performance compared to using SimSR.", "weaknesses": "The motivation for utilizing the expectile operator could be explained more clearly. While expectile regression is applicable to both online [1] and offline RL, its relevance to addressing Proposition 4 and preventing overfitting in the offline RL setting requires further elaboration.\n\nThe authors propose reward scaling as a solution to mitigate the limitation imposed by the cosine distance, which has a range of [0, 2]. This range imposes an upper bound on the value of $c_r$. However, Theorem 8 suggests that a larger value of $c_r$ leads to a more accurate approximation of the value function. An alternative approach to overcome the limitations of the cosine distance would be to use other distance metrics such as L1 or L2 distance. Hence, it would be beneficial for the authors to clarify the rationale behind selecting cosine distance over these alternatives.\n\nIn the comparison experiments between SimSR+RS(+EBS) and MICo(+EBS), it is possible that RS improves performance due to the numerical stability of neural networks. By upper bounding the range of $G$ to [0, 1], which can be stably predicted by neural networks, RS might contribute to the observed performance enhancement.\n\nThe bisimulation Bellman residual $\\epsilon_{\\phi}^{\\pi}$ may not be minimized to zero if $G_{\\phi}^{\\pi}$ is a cosine distance. Consider the case of $s_i = s_j$. $G_{\\phi}^{\\pi}(s_i, s_j) = 0$ because it is cosine distance. However, $FG_{\\phi}^{\\pi}(s_i, s_j)$ is a Łukaszyk–Karmowski distance because  $\\gamma  E_{s^{\\prime}_i, s^{\\prime}_j} G_\\phi^\\pi(s^{\\prime}_i, s^{\\prime}_j)$ \n\nis a Łukaszyk–Karmowski distance as $s^{\\prime}_i$ and $s^{\\prime}_j$ are sampled [2],\n\n and $|r_i^{\\pi} - r_j^{\\pi}|$ is untractable and usually alternated to $E_{r_i, r_j}|r_i - r_j|$, which is again a Łukaszyk–Karmowski distance[3]. Therefore, $FG_{\\phi}^{\\pi}(s_i, s_j) \\geq G_{\\phi}^{\\pi}(s_i, s_j)$ if $s_i = s_j$, the equality is taken only if $G_{\\phi}^{\\pi}(s^{\\prime}_i, s^{\\prime}_j) = 0$ for all $s^{\\prime}_i$ and $s^{\\prime}_j$ and \n\n$r_i = r_j$ for all $r_i$ and $r_j$. This can destroy the Proposition 4 because not all $\\epsilon_{\\phi}^{\\pi}$ is zero. However, MICo distance does not meet this issue.\n\n------\nReference\n\n[1] Rowland et al. Statistics and Samples in Distributional Reinforcement Learning. ICML 2019.\n\n[2] Castro et al. MICo: Improved representations via sampling-based state similarity for Markov decision processes. NeurIPS 2021.\n\n[3] Chen et al. Learning Representations via a Robust Behavioral Metric for Deep Reinforcement Learning. NeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and feedback on our paper. We have included new experimental results and some general discussion, please refer to our generic response and uploaded file to address these points.\n\n- **Question: While expectile regression is applicable to both online [1] and offline RL, its relevance to addressing Proposition 4 and preventing overfitting in the offline RL setting requires further elaboration.**\n\n- **Response**: An intuitive explanation is that when considering the on-policy settings, i.e., bisimulation Bellman residuals and bisimulation error are both coupled with policy $\\pi$, thereby Theorem 3 can be derived. This is to say that if we can access the optimal policy $\\pi^*$ and we apply bisimulation on it, the problem mentioned in Proposition 4 naturally does not exist. However, in practice, it is actually impossible to obtain bisimulation corresponding to the optimal when the dataset is fixed. Therefore, we can only use expectile to strike a balance between behavior and optimal, to alleviate this problem.\n\n- **Question: It would be beneficial for the authors to clarify the rationale behind selecting cosine distance over these alternatives.**\n\n- **Response**: We wish to gently draw the reviewer's attention to the fact that the selection of cosine distance was specified in SimSR[1] instead of ours. The rationale behind their selection likely stems from cosine distance having zero self-distance and being suitable for constructing a unit hypersphere. Notably, in contrast, our proposed methodology does not require a specific distance. In our experiments, we also applied EBS on MICo and showed its superiority. For a more comprehensive explanation of the suitability of techniques we have presented, please refer to the general response.\n\n- **Question: In the comparison experiments between SimSR+RS(+EBS) and MICo(+EBS), it is possible that RS improves performance due to the numerical stability of neural networks.**\n\n- **Response**: To verify the effectiveness of RS, we additionally construct an ablation study, which consists of several different combinations to reward scaling strategy. Please refer to Figure 1 in our uploaded pdf file and our general response for detailed explanations.\n\n- **Question: The bisimulation Bellman residual may not be minimized to zero if $G^\\pi_\\phi$ is a cosine distance, This can destroy the Proposition 4 because not all $\\epsilon^\\pi_\\phi$  is zero. However, MICo distance does not meet this issue.**\n\n- **Response**: We perceive the possibility that the reviewer might postulate that the MICo distance is impervious to the issue elucidated in Proposition 4. It's important to note, however, that Proposition 4 doesn't purport that the bisimulation Bellman residual will invariably minimize to zero. Rather, it describes a scenario wherein even with the bisimulation Bellman residual at its nadir - zero, there might yet be pairs of states manifesting a bisimulation error that is non-zero. This scenario is entirely unconnected with the distance upon which bisimulation objectives are contingent.\n \n- **Question: Lemma 5 and 6 require a citation to [4].**\n\n- **Response**: Thanks for the suggestion! We will add the citations in the revision.\n\n- **Question: How does the value of c_r affect the value bound according to Theorem 8 and Theorem 15?**\n\n- **Response**: In relation to Theorem 8, as $c_r$ inhabits the denominator of the right-hand side of Equation 11, an enlargement in the magnitude of $c_r$ will precipitate a diminution in the value boundary. Conversely, in Theorem 15, given that $c_r$ solely influences the reward's scale without contributing to Equation 27's derivation, we remain capable of formulating an equation akin to Equation 30. The sole alteration would be the incorporation of the coefficient $c_r$ within the confines of the expectation.\n\n- **Question: How is Eq. (29) derived from Eq. (28) in Theorem 15 in the Supplementary Material?**\n\n- **Response**: Assuming we interpret $\\Delta_{\\phi}^{\\tilde{\\pi}}(\\tilde{x})$ as a value function and $\\epsilon_{\\phi}^{\\tilde{\\pi}}(\\tilde{x})$ as reward, then Equation 28 can be re-written as $V(s)=\\sum\\gamma \\mathbb{E}_{s'\\sim P^{\\pi}}[r(s')]=\\frac{1}{1-\\gamma}\\mathbb{E}_{s'\\sim P^{\\pi}}[r(s')]$.  Consequently, Equation 29 can be deduced in concordance with this formulation.\n\n- **Question: It is confusing that the main text defines $\\Delta$ and $\\epsilon$ as absolute values, while the supplementary material defines them as differences. The authors should use different notations (rather than the same $\\Delta$ and $\\epsilon$) in the supplementary material.**\n\n- **Response**: Our motivation stems from the pursuit of preserving succinctness and autonomy in the primary manuscript's notation. Nonetheless, during the appendix's proofing process, we encounter stages necessitating the consideration of forms devoid of absolute values. We will contemplate amending the symbols within the appendix to enhance lucidity when revisions to the manuscript become feasible.\n\n- **Question: What is the value of tau in Table 1?**\n\n- **Response**: The value of $\\tau$ is 0.6 for SimSR, and $\\tau$ is 0.7 for MICo for all datasets in V-D4RL datasets, we will add this in revision.\n\n- **Question: Some implementation details are missing, including the learning rate and network architecture.**\n\n- **Response**: For d4rl tasks, we employ an Adam optimizer with learning rate of 3e-4, and an identical encoder, i.e., a 4-layer MLP activated by ReLU, succeeded by another linear layer. For v-d4rl tasks, we employ an Adam optimizer with learning rate of 1e-4, and an identical encoder, i.e., four convolutional layers activated by ReLU, succeeded by another linear layer. We will include the corresponding descriptions in revision.\n"}, {"review_id": "s7zKerGE8N", "reviewer": "Reviewer_ndNc", "summary": "The paper investigates why bisimulation-based methods, which are known to work well in the online setting, fail in the offline case. It hypothesizes that missing transitions and reward scaling issues are a source of this failure, and proposes a way to mitigate these issues. It includes experiments on various benchmarking tasks. ", "questions": "1. I’d point authors to this new paper by the MICO authors: https://openreview.net/forum?id=nHfPXl1ly7 to see how their approach fits in with this kernel-based bisimulation approach.\n2. How do reward normalization schemes impact the results? For example, subtracting min and dividing by max-min (where min/max are the min/max rewards in the dataset), or 0/1 mean/std normalization etc? Are these beneficial when computing the bisimulation metric?\n3. Why is the Effective Dimension a good metric in the offline RL case (Figure 1)? The paper just plots the results without justifying the usage. I ask this by considering other offline RL metrics for representations such as distribution shift and coverage [1, 2] in terms of the state-action feature representations.\n4. From the experiments, it appears that MICO and SimSR were applied as-is. I wonder if it would be useful to apply an off-policy version of say MICO by either sampling from the policy getting trained or using some version of importance sampling?\n5. It would be interesting to include some preliminary results in the appendix on off-policy evaluation (not just control) (keep the main results in tact; I am referring more to an exploratory analysis for the appendix).\n6. How is maximization and subject-to constraints (eqn 8) satisfied in continuous action setting?\n\n[1] Instabilities of Offline RL with Pre-Trained Neural Representation. Wang et al.\n\n[2] Learning Bellman Complete Representations for Offline Policy Evaluation. Chang et al.\n", "limitations": "See above.\n\nN/A societal impact.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. According to me, this is an important problem to solve. Recently bisimulation-based representation learning methods have become popular but have focused mostly on the online setting. The insights from this paper are illuminating, especially Theorem 3 and Proposition 4.\n2. I like that they considered the MICO distance since unlike other metrics, MICO is a diffuse metric and has additional complications due to the non-zero self-distances.\n", "weaknesses": "It appears that the approach is limited to a single and known behavior policy. I wonder how this could be used in the multiple and unknown behavior policy setting, which is starting to become a more popular setting in offline RL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and feedback on our paper. We have included new experimental results and some general discussion, please refer to our generic response and uploaded file to address these points.\n\n- **Question: It appears that the approach is limited to a single and known behavior policy. I wonder how this could be used in the multiple and unknown behavior policy setting, which is starting to become a more popular setting in offline RL.**\n\n- **Response**: First, we want to clarify that we do not have access to the behavior policy that was used to collect data. Second, a recent paper [A] proves under mild conditions, that the dataset’s transitions distribution (aka the occupancy measure) obtained from multiple behavior policies can be replicated with a single Markovian behavior policy. This theoretical result rigorously allows any Offline RL algorithm to pretend that the dataset has been generated with the equivalent single Markovian behavior policy and thus the multiplicity (and non-stationarity) of the behavior policy does not present any additional challenge to the Offline RL task.\n\n[A] Laroche, R. and Tachet Des Combes, R. On the Occupancy Measure of Non-Markovian Policies in Continuous MDPs. ICML, 2023.\n\n- **Question: I’d point authors to this new paper by the MICO authors to see how their approach fits in with this kernel-based bisimulation approach.**\n\n- **Response**: Thanks the reviewer for bringing this work to our attention. In the general response, we delve into the suitability of the two techniques we've proposed. The kernel-based bisimulation approach, dubbed KSMe, which adheres to the bisimulation principle, could inherently reap benefits from the EBS technique when applied in offline scenarios. Given that $supp(\\mathcal{R})\\in[-1,1]$ and $k_1(x, y)=1-\\frac{1}{2}\\left|r_x^\\pi-r_y^\\pi\\right|$, the immediate similarity is constrained within the interval $[0,1]$. Importantly, the kernel isn't subjected to a specific bound, thus nullifying the need to contemplate the RS technique (aligning with the relationship between KSMe and MICo as elucidated in the said paper - an issue that MICo bypasses as well). Furthermore, it preemptively processes the scale of the rewards prior to considering the bisimulation operator, thus mirroring an insight our paper provides, which is, the significance of a well-scaled reward.\n\n- **Question: How do reward normalization schemes impact the results? For example, subtracting min and dividing by max-min (where min/max are the min/max rewards in the dataset), or 0/1 mean/std normalization etc? Are these beneficial when computing the bisimulation metric?**\n\n- **Response**: This is a good question. To delve deeper into the relevance of the reward scaling technique, we have incorporated an ablation study. In a nutshell, the 0/1 mean/std normalization (referred to as \"standardization\" in the attached document) does not deliver favorable empirical outcomes. We have furnished the corresponding findings in Figure 1 of the uploaded pdf file and a detailed account in the general response. \n\n- **Question: Why is the Effective Dimension a good metric in the offline RL case (Figure 1)? The paper just plots the results without justifying the usage. I ask this by considering other offline RL metrics for representations such as distribution shift and coverage [1, 2] in terms of the state-action feature representations.**\n\n- **Response**: Thanks for bringing these measurements to our attention. Indeed, the foundational concepts guiding these methodologies bear striking resemblance, as all emanate from feature reachability or the rank covariance of the feature. They are unified in their aspiration to gauge the efficacy of representations, and our choice of one over the other for evaluation was largely discretionary. \n\n- **Question: From the experiments, it appears that MICO and SimSR were applied as-is. I wonder if it would be useful to apply an off-policy version of say MICO by either sampling from the policy getting trained or using some version of importance sampling? It would be interesting to include some preliminary results in the appendix on off-policy evaluation**\n\n- **Response**: Thank you for this insightful suggestion! The question of how importance sampling techniques (such as per-decision importance sampling) fare with MICo and SimSR indeed makes for an engaging question. Theoretically, using importance sampling as an illustration, it can be implemented for off-policy value estimation. However, the instability of importance sampling for long horizons is a recognized challenge. Given that bisimulation measurements bear relevance to the value function in some regard, we anticipate that this approach will grapple with analogous challenges within the bisimulation principle. It's worth noting, though, that despite conventional importance sampling's potential limitations, recent works in off-policy evaluation have emerged to mitigate these concerns. This constitutes a promising avenue of research, and we may well explore the integration and adaptation of these advancements within the context of bisimulation in offline scenarios. We intend to contemplate including a discussion and analysis of related works in the appendix. Once more, we extend our sincere gratitude to the reviewer for these invaluable recommendations.\n\n- **Question: How is maximization and subject-to-constraints (eqn 8) satisfied in continuous action setting?**\n\n- **Response**: The maximization operation in Equation 8 only occurs when $\\tau=1$, and it represents solely a theoretical determination. In practical application, we in fact employ Equation 6, and as a result, the maximization operation does not participate in concrete implementations.\n"}, {"review_id": "zlTxI7CkrG", "reviewer": "Reviewer_BVFy", "summary": "Bisimulation methods tend to fail when applied to offline RL. The authors performed a bisimulation error analysis and concluded that missing transitions, inevitable when training with a fixed offline dataset, lead to inaccurate metric predictions. Therefore, training policies based on the representation learned with inaccurate predictions will perform poorly. The paper proposes a $\\tau$-expectile-based bisimulation operator to overcome this challenge. This operator achieves fully in-sample learning in the limit $\\tau\\to 1$. The authors also note that reward scaling is crucial when the underlying state-space metric is bounded. Experiments conducted on state-based and pixel-based offline RL problems show that both expectile-based bisimulation operator and reward scaling have a significant impact on the final quality of the learned representation.", "questions": "Is the proposed algorithm also effective in the online RL setting? Also, it would be helpful for the readers if the paper introduces the definition of $G^\\pi$ and a *lifted MDP* before mentioning them in equation (2) and line 139, respectively.", "limitations": "The authors have adequately addressed the limitations of their work, and I do not believe this work will have a potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The authors mathematically analyzed the properties of the original bisimulation operator and the novel expectile-based bisimulation operator. The mathematical techniques used in the proofs and the careful analysis of the error bounds will be very helpful to other researchers trying to work on applying bisimulation-metric-based representation learning to offline RL. The expectile-based based bisimulation operator the authors proposed is also interesting and effective under various settings, as the experimental results reveal. Finally, the paper is overall well-written and easy to understand.", "weaknesses": "It is doubtful that learning a bisimulation operator in the offline setting generally fails because of the reasons the paper presents. To facilitate learning by diversifying trajectories, a lot of RL environments impose a limit on the episode length. An environment with a time limit of $T$ should have states that an agent can arrive within $T+1$ timesteps but not in $T$ timesteps. Those states satisfy the conditions of Proposition 4, which means learning a bisimulation operator will fail. This is not the case.\n\nAlso, according to line 238, unlike the original bisimulation operator, learning the expectile-based bisimulation operator will succeed because we only consider state pairs with corresponding actions in the dataset. Suppose this is the reason why learning an expectile-based bisimulation operator succeeds. Then why not just omit the last and the second-last states of each trajectory in the dataset during training while using the original bisimulation operator? Then the next-state pairs of every state-pairs left will have corresponding actions in the dataset. It is hard to imagine such a simple solution will work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review and feedback on our paper. We have included new experimental results and some general discussion, please refer to our generic response and uploaded file to address these points.\n\n- **Question: It is doubtful that learning a bisimulation operator in the offline setting generally fails because of the reasons the paper presents. To facilitate learning by diversifying trajectories, a lot of RL environments impose a limit on the episode length. An environment with a time limit of T should have stated that an agent can arrive within T+1 timesteps but not in T timesteps. Those states satisfy the conditions of Proposition 4, which means learning a bisimulation operator will fail. This is not the case.**\n\n- **Response**: While it is true that many RL environments truncate the episode length (for example, some tasks in Mujoco may have a maximum length of 500), this chiefly pertains to pragmatic considerations surrounding sample efficiency. Primarily, within the Preliminaries, we emphasized that our framework is predicated on an infinite horizon, thus necessitating the discount factor gamma (in contrast, the finite horizon scenario does not require the gamma factor, a distinction that sets it apart from our problem formulation). Secondly, the predicament articulated in Proposition 4 is unaffected by the length of trajectories or the truncation of episodes. At its core, whenever the bisimulation Bellman residual is employed as a surrogate objective in an offline setting, this dilemma surfaces. This arises from the reality that as long as the dataset remains incomplete, the relationship between $\\epsilon_{\\phi}^{\\pi}$ and $\\Delta^{\\pi}_{\\phi}$ does not strictly hold.\n\n- **Question: According to line 238, unlike the original bisimulation operator, learning the expectile-based bisimulation operator will succeed because we only consider state pairs with corresponding actions in the dataset. Suppose this is the reason why learning an expectile-based bisimulation operator succeeds. Then why not just omit the last and the second-last states of each trajectory in the dataset during training while using the original bisimulation operator? Then the next-state pairs of every state-pairs left will have corresponding actions in the dataset. It is hard to imagine such a simple solution will work.**\n\n- **Response**: We may not have entirely understood the reviewer's question. Even if we exclude the last and second-to-last states, the third-to-last states remain. For these particular states, we must still compute $\\hat{\\epsilon}$, necessitating the sampling of subsequent states. Since we have already dispensed with the second-to-last states, this calculation falls outside the confines of the dataset.\n\n- **Question: Is the proposed algorithm also effective in the online RL setting? Also, it would be helpful for the readers if the paper introduces the definition of G^\\pi  and a lifted MDP before mentioning them in equation (2) and line 139, respectively.**\n\n- **Response**: Theoretically, as long as the dataset is incomplete, this issue will arise. Specifically, in on-policy settings, the expected bisimulation residual proves adequate for learning representations (as established in Theorem 3); conversely, in off-policy settings, it serves as a deficient estimator, as the missing transitions disrupts the relationship between $\\epsilon_{\\phi}^{\\pi}$ and $\\Delta^{\\pi}_{\\phi}$ (as outlined in Proposition 4), though it is marginally better than offline settings. \nThanks for the recommendation, and we will contemplate reorganizing the structure of the relevant paragraph to enhance its readability and coherence.\n"}]

Author rebuttal:
# General response

## 1.The severity of the proposed problem

### How do bisimulation-based objectives perform in other (online or goal-conditioned) settings?

- Various methods, such as DBC[48], MICo[6], SimSR[46], and PSE[A], have consistently demonstrated positive results in online settings, regardless of the presence of distractors. This evidence supports the efficacy of bisimulation techniques in online settings. Additionally, GCB[B] excelled in goal-conditioned environments, ExTra[C] showcased the power of bisimulation metric in exploration, and HiP-BMDP[D] successfully incorporated bisimulation into multi-task settings, highlighting its superior performance, all mostly in online settings too, with little work in offline RL. These studies suggest that when tailored to specific environments, bisimulation methods can excel. Despite these works, bisimulation methods have had little success when extended to offline settings, and our motivation is to tackle this problem.

### While bisimulation objectives used in the offline setting are directly affected by missing transitions, many other representation objectives may not. 

- When referring to state representation learning, using bisimulation in offline settings presents challenges due to the two issues we outlined in Line 48-52 in our original submission: the presence of missing transitions and inappropriate reward scales. Concurrently, there exists other representation objectives, like CURL[28], ATC[E], which focus on pairs of states without the explicit necessity for transition information. As a consequence, they do not explicitly require accounting for missing transitions or reward scaling in their objectives. This absence of direct influence sets them apart from bisimulation-based methods. Yet, we consider that bisimulation-based techniques have a theoretical edge and have proven effective in online settings, Thus, we deem that our work is impactful in that it delivers a proof that bisimulation can be successful offline.  

[A]: Rishabh Agarwal, et al. Contrastive Behavioral Similarity Embeddings for Generalization in Reinforcement Learning. ICLR 2021

[B]: Philippe Hansen-Estruch, et al. Bisimulation Makes Analogies in Goal-Conditioned Reinforcement Learning. ICML 2022

[C]: Anirban Santara, et al. ExTra: Transfer-guided Exploration. AAMAS 2020

[D]: Amy Zhang, et al. Multi-Task Reinforcement Learning as a Hidden-Parameter Block MDP. Arxiv 2020.

[E]: Stooke, Adam, et al. Decoupling representation learning from reinforcement learning. ICML 2021.

### Compounded effect for bisimulation principle in offline settings

- In online scenarios, state representations and policies are updated concurrently, while in offline settings, state representation is pre-trained before policy learning, with the two phases completely decoupled. Errors during representation learning in offline settings can have a compounded effect on policy learning, leading to significant issues. This is the reason that missing transitions is particularly harmful to the bisimulation principle in offline settings. Although reward scales affect bisimulation universally, as offline settings require pretraining state embedding, any major discrepancy between this fixed representation and the policy parameter space can further undermine the learning process. Hence, the proposed solutions hold promise for enhancing bisimulation's efficiency in offline settings.


## 2.Suitability of different techniques

- For RS: In essence, the given theoretical analysis is applicable across all bisimulation-based objectives. However, the precise settings for $c_r$ hinge on the foundational distance. For instance, SimSR uses the cosine distance which has definitive bounds. As a result, we need to infer the ideal setting from Equation 10 and Theorem 8. In contrast, the MICo-like distance and DBC employ L-K distance and L1 distance respectively, having bounds ranging from $[0,+\infty]$. Consequently, they can adapt to more value settings. We propose our approach as a general method/principle to employ a novel bisimulation metric or distance, especially in the context of offline RL. 

- For EBS: We provide EBS as a general method, which is applicable to all bisimulation-based objectives, given that they all adhere to the foundational principle of bisimulation. This principle revolves around the contraction mapping properties similar to the value iteration. Whenever there's an intent to employ bisimulation in offline scenarios, with an aim to reduce the Bellman residual for approximating the fixed point, the outlined challenge emerges. Consequently, EBS holds the potential to enhance any bisimulation-based method, regardless of the distance they use.

## 3.New experiments results

### MICo+RS and MICo+RS+EBS results

- Please see Figure 2 in rebuttal pdf.  We provide the results of MICo+RS on the D4RL benchmark, as new experiments for the rebuttal. 

### Ablations for RS 

- In our work, reward scaling comprises two components: i) min-max normalization, and ii) the determination of $c_r$ as $1-\gamma$. To substantiate the efficacy of our proposed methodology, we considered different combinations of min-max normalization/standardization and various value of $c_r$ (including 1, 0.1, 0.01, and 0.001). The results provided empirical validation of our theoretical exploration.

### Visual-D4RL results update
- In the original submission, the methodologies' performance as previously reported in Table 1 omitted variance. We provide additional results in pdf, showing performance curves averaged over 10 different random seeds, and standard error (shared), accompanied by the IQM metric aggregating overall statistical properties. Results in Figures 3 and 4 show consistency with our empirical performance in Table 1. The results depicted in Figure 3 and Figure 4 in the uploaded PDF file show consistency with the empirical performance in Table 1 in our original submission for image-based settings.

Meta-review: ### Summary
This paper investigates the limitations of bisimulation based approaches in offline Reinforcement Learning (RL) tasks, where they tend to underperform compared to alternative methods. The authors identify two main challenges: missing transitions in the dataset and reward scaling. Missing transitions can lead to inaccurate estimation of bisimulation metrics and poor state representations. To address this challenge, the paper proposes using the expectile operator for representation learning, which helps prevent overfitting incomplete data. Furthermore, the paper emphasizes the importance of reward scaling in controlling the scale of bisimulation measurements and value errors. To mitigate this issue, the authors introduce a reward scaling strategy. These proposed techniques are applied to two state-of-the-art bisimulation-based algorithms, MICo and SimSR, and evaluated on benchmark suites (D4RL and Visual D4RL), demonstrating performance improvements. Overall, the paper aims to understand why bisimulation methods excel in online settings but struggle in offline RL tasks, offering solutions that enhance the robustness and effectiveness of bisimulation-based representations in offline learning scenarios.

### Decision

The paper is well-written and overall the reviewers were positive about the approach. The paper is well-written and easy to follow. The results on offline RL experiments are quite good. Therefore, I recommend this paper for acceptance.

For the camera-ready I would recommend authors to address the concerns raised by the reviewers with all the additional results presented during the rebuttal.
Decision: Accept (poster)