Provable Causal State Representation under Asynchronous Diffusion Model for POMDPs

Weakness 1: We would like to express our sincere gratitude for your valuable comments.

In Assumption 2, we assume the existence of a lower bound for the Holder continuous function to ensure the stability and validity of the density function. In practice, this assumption can be satisfied using methods, such as data normalization and function regularization. A similar lower-bound assumption was adopted and discussed in Ref. [1].

Regarding Assumption 3, we apologize for any confusion caused by the definitions in Definition 2 and Assumption 3.

• In Definition 2, we define a metric to measure the difference between the causal state extracted from observations and the true state underlying POMDPs. To clarify this, we have added the phrase "for any pair of state and observation $\{\mathbf{s}_t \in \mathcal{S}, \mathbf{o}_t \in \mathcal{O}\}$" to the revised version.

• Assumption 3 refers to a common premise in the study of bisimulation metrics (see Ref. [2]), that is, the existence and uniqueness of the bisimulation metric for any pair of states. In other words, for any pair of states $(\mathbf{s}_i, \mathbf{s}_j)$, there exists a unique bisimulation metric to measure their similarity. In particular, we assume the existence of a unique bisimulation metric for $p$-Wasserstein metrics to facilitate analyzing value function approximation (VFA). In Remark 1, we validate Assumption 3 when $p=1$, with the proof proved in Appendix B 3.1. More general cases with $p>1$ will be studied in our future research, only after which Assumption 3, while it is reasonable and widely adopted, can be stated as an appropriate theorem.

As suggested, we have also clarified in the revised version that Assumption 3 does not restrict the state, action, or observation spaces to be finite (or any other conditions).

Weakness 2: We express our heartfelt gratitude for your feedback. We would like to clarify that we account for initialization error, score estimation error, and discretization error in our analysis of the diffusion model (like the existing studies).

Specifically, in Appendix B2.3, we decompose the distribution estimation error into these three components (see Eq. (33)) and provide individual bounds for each of the three components. By appropriately setting the early-stopping step $k_0$ and the total diffusion model's step $K$, we can simplify the results, as presented in Theorem 3.

To address this confusion, we have added the following clarification in the revised version:

"Under Assumption 2, we can measure the asynchronous diffusion model's distribution estimation by considering the initialization error, score estimation error, and discretization error, and provide the sample complexity bounds for each of the three errors using the Wasserstein-1 distance."

Weakness 3: Sincere thanks to you for this valuable suggestion. We have added clarifying remarks following each theorem in the revised version, as follows.

• Theorem 1: "In this sense, the bisimulation metric in (12) represents the upper bound of the value gap."

• Theorem 2: "By Theorem 2, we can quantify the upper bound of the value gap under arbitrary model errors. This can be extended to different probability density estimation models to establish specific convergence properties. The theorem facilitates analyzing the impact of the proposed asynchronous diffusion model on the value gap."

• Theorem 3: "As $n\rightarrow\infty$, the distribution estimation measured by Wasserstein-1 distance converges, i.e., $\mathbb{E}_ {\{{\mathbf{x}_ t,\hat{\mathbf{s}}_ {t}, \mathbf{a}_ t}\}_ {t=1}^{n}}$ W_ 1(p(\mathbf{x}_ t|\hat{\mathbf{s}}_ {t}, \mathbf{a}_ t), \hat{p}({\mathbf{x}}_ t^{k_0}|\hat{\mathbf{s}}_ {t}, \mathbf{a}_ t)) $\to 0$, corroborating the effective distribution estimation capability offered by the proposed asynchronous diffusion model."

• Theorem 4: "As $n \to \infty$, the estimated causal state $\widetilde{V}^\pi( \zeta( \mathbf{s} ) )$ in (15) converges to within $2\hat{\epsilon}$-neighborhood of the ground-truth causal state $V^\pi(\mathbf{s})$, i.e., the neighborhood region of the ground-truth causal state $V^\pi(\mathbf{s})$ with the radius of $\hat{\epsilon}$."

Reference

[1]. Fu, Hengyu, et al. "Unveil conditional diffusion models with classifier-free guidance: A sharp statistical theory." arXiv preprint arXiv:2403.11968 (2024).

[2]. Kemertas, Mete, and Tristan Aumentado-Armstrong. "Towards robust bisimulation metric learning." Advances in Neural Information Processing Systems 34 (2021): 4764-4777.

Weakness 4: Sincere thanks to the reviewer for providing this insightful feedback.

• Regarding the convergence:

As $n \to \infty$, the estimated causal state $\widetilde{V}^\pi( \zeta( \mathbf{s} ) )$ in Eq. (15) converges to within $2\hat{\epsilon}$-neighborhood of the ground-truth causal state $V^\pi(\mathbf{s})$, i.e., the neighborhood region of the ground-truth causal state $V^\pi(\mathbf{s})$ with the radius of $\hat{\epsilon}$, where $\hat{\epsilon}$ depends on the nature of the environment.

Specifically, the term $\mathcal{O}(\mathrm{poly}(n, d_s))$ on the RHS of Eq. (15) was introduced by the use of the RNN model for bisimulation metric learning. Its convergence has already been proved in Ref. [5].

To evaluate the convergence of the term $\mathcal{O}\left(n^{-\frac{b}{2d_s+d_a+2b}} (\log n)^{\max(\frac{19}{2},\frac{b+2}{2})} \right)$ on the RHS of Eq. (15) is, in essence, to analyze the convergence of $\lim_{n \to \infty} \frac{\ln^{c_1} n}{n^{c_2}}$ with $c_1 = \max(\frac{19}{2},\frac{b+2}{2})>0$ and $c_2=\frac{b}{2d_s+d_a+2b}>0$. By applying L'Hôpital's rule, it follows that $\lim_{n \to \infty} \frac{\ln^{c_1} n}{n^{c_2}} = \lim_{n \to \infty} \frac{c_1\ln n}{n\times c_2 n^{c_2-1}} = \lim_{n \to \infty} \frac{c_1\ln n}{c_2 n^{c_2}} = \lim_{n \to \infty} \frac{c_1}{n\times c_2^2n^{c_2-1}} = \lim_{n \to \infty} \frac{c_1}{c_2^2n^{c_2}} = 0$. As a result, the term $\mathcal{O}\left(n^{-\frac{b}{2d_s+d_a+2b}} (\log n)^{\max(\frac{19}{2},\frac{b+2}{2})} \right)$ on the RHS of Eq. (15) converge to zero.

As a consequence, the RHS of Eq. (15) converges to $2\hat{\epsilon}$. When $\hat{\epsilon}$ is sufficiently small, the RHS of Eq. (15) vanishes, i.e., converging to zero, as $n\rightarrow\infty$.

In response to this comment, we have added this explanation of Theorem 4 to the revised version as

"As $n \to \infty$, the estimated causal state $\widetilde{V}^\pi( \zeta( \mathbf{s} ) )$ in (15) converges to within $2\hat{\epsilon}$-neighborhood of the ground-truth causal state $V^\pi(\mathbf{s})$, i.e., the neighborhood region of the ground-truth causal state $V^\pi(\mathbf{s})$ with the radius of $\hat{\epsilon}$."

• Regarding the analysis of gradient descent (GD):

First of all, we analyze the upper bound of the value gap under arbitrary model approximation errors (as discussed in Theorem 2), which does not involve gradient descent. Subsequently, we measure the exact approximation errors of $\mathcal{E}_ \zeta$, $\mathcal{E}_ \phi$, and $\mathcal{E}_ \theta$.

In the case of $\mathcal{E}_ \zeta$, we utilize an RNN model to learn the bisimulation metric and apply the existing results in Ref. [5] to establish the convergence analysis of our proposed algorithm (as described in Theorem 4). The convergence analysis of RNNs by Allen-Zhu et al. in Ref. [5] has already captured gradient descent.

In the case of $\mathcal{E}_ \phi$ and $\mathcal{E}_ \theta$, we examine the approximation error of the asynchronous diffusion model (as shown in Theorem 3), which indeed needs to consider gradient descent. Nevertheless, our work builds on the conclusions of Ref. [6]. In particular, Fu et al. in Ref. [6] analytically established the convergence of the classical classifier-free diffusion model under neural network approximation and proved the error of distribution approximation can converge to zero. This is given as Lemma 12 in our paper and used for our analysis of the approximation errors in the asynchronous diffusion model.

As a result, Theorem 4 rigorously asserts the convergence of our proposed algorithm.

Reference

[1]. Sangiorgi, Davide. Introduction to bisimulation and coinduction. Cambridge University Press, 2011.

[2]. Van der Schaft, A. J. "Equivalence of dynamical systems by bisimulation." IEEE transactions on automatic control 49.12 (2004): 2160-2172.

[3]. Hansen-Estruch, Philippe, et al. "Bisimulation makes analogies in goal-conditioned reinforcement learning." International Conference on Machine Learning. PMLR, 2022.

[4]. Sutton, Richard S., and Andrew G. Barto. "Reinforcement learning: an introduction, 2nd edn. Adaptive computation and machine learning." (2018).

[5]. Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. "On the convergence rate of training recurrent neural networks." Advances in neural information processing systems 32 (2019).

[6]. Fu, Hengyu, et al. "Unveil conditional diffusion models with classifier-free guidance: A sharp statistical theory." arXiv preprint arXiv:2403.11968 (2024).

Weakness 1: As an important concept in theoretical computational science, bisimulation is a method for identifying equivalent spaces under a given transition. For basic information about the definition of bisimulation, please refer to Ref. [1-3].

Under MDP, bisimulation provides a framework to measure the equivalence of states based on their behavioral similarity. Specifically, bisimulation requires that if two states $\mathbf{s}_i$ and $\mathbf{s}_j$ are bisimilar, executing the same action $\mathbf{a}$ from these states should lead to statistically indistinguishable next-state distributions and reward distributions. This ensures that the dynamics of the system do not differentiate between $\mathbf{s}_i$ and $\mathbf{s}_j$, making them interchangeable in terms of their future trajectories.

In reinforcement learning, the joint distribution $p(\mathbf{s}_ {t+1}, r_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ describes the transition dynamics and reward generation when action $\mathbf{a}_ {t}$ is taken in state $\mathbf{s}_ {t}$. The joint distribution $p(\mathbf{s}_ {t+1}, r_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ still governs the system's behavior. This joint distribution can be decomposed into the state transition probability $p(\mathbf{s}_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ and reward distribution $p(r_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ due to the previously rigorously proved independence of the future state $\mathbf{s}_ {t+1}$ and the reward $r_ {t+1}$ conditioned on the current state $\mathbf{s}_ {t}$ and action $\mathbf{a}_ {t}$ (See Ref. [4] for details).

However, direct access to the underlying states is unavailable in POMDPs; instead, only the observations $\mathbf{o}_ {t}$ are accessible. Since $\mathbf{o}_ {t}$ reacts to $\mathbf{s}_ {t}$, we can establish the equivalence of states and observations even under partial observability. The combination of the state transition probability and reward distribution serves as a foundation for defining bisimulation in POMDPs, establishing a metric for state similarity.

In the revised version, we have revised Definition 1 and added the following explanation: "Based on the environment's dynamics $P(\mathbf{s}_ {t+1}, r_ {t+1}|\mathbf{s}_ t, \mathbf{a}_ t)$, the similarity between environments can be expressed by the similarity between their state transition and reward functions."

Weakness 2: Sincere thanks for your insightful comment. We have rewritten Definition 2 and Assumption 3 in the revised version to help readers interpret the bisimulation metric.

For Definition 2, we define the bisimulation metric between the causal state extracted from observations and the true state underlying the POMDPs. To clarify this, we have added the phrase "for any pair of state and observation $\{\mathbf{s}_ t \in \mathcal{S}, \mathbf{o}_ t \in \mathcal{O}\}$" in the revised version.

For Assumption 3, we establish the existence and uniqueness of the bisimulation metric between any two states. Accordingly, we have included "$\forall (\mathbf{s}_i, \mathbf{s}_j) \in \mathcal{S} \times \mathcal{S}$" in the revised version.

Weakness 3: We apologize for this typo, where $\zeta$ was used to denote two different models. We have clarified this in the revised version by using $\phi$ to indicate the reward noise model and $\zeta$ to denote the bisimulation model.

Reference

[1]. Li, Jonathan, and Andrew Barron. "Mixture density estimation." Advances in neural information processing systems 12 (1999).

[2]. Chen, Zhichao, et al. "Rethinking the Diffusion Models for Missing Data Imputation: A Gradient Flow Perspective." The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.

[3]. Chen, Haoxuan, et al. "Accelerating Diffusion Models with Parallel Sampling: Inference at Sub-Linear Time Complexity." The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.

[4]. Eysenbach, Ben, Russ R. Salakhutdinov, and Sergey Levine. "Search on the replay buffer: Bridging planning and reinforcement learning." Advances in neural information processing systems 32 (2019).

[5]. Kemertas, Mete, and Tristan Aumentado-Armstrong. "Towards robust bisimulation metric learning." Advances in Neural Information Processing Systems 34 (2021): 4764-4777.

Q5: We have now clarified in the revised version that $n$ denotes the number of samples used in training, which is now defined in line 266 of the revised version (original manuscript, line 278). $\hat{\mathbf{s}}_ {t+1}$ represents the causal state obtained after denoising and extracting the causal information from the observation at time $t+1$, which is defined in line 205 of the revised version (original manuscript, line 212). Moreover, $r_{t+1}$ denotes the reward received at time $t+1$, which is now defined in line 140 of the revised version (original manuscript, line 134).

Q6: We would like to clarify that the purpose of line 7 in Algorithm 1 is to sample a batch of transitions from the replay buffer for the training of reinforcement learning. As a key feature of standard reinforcement learning, the replay buffer reduces correlations among samples and improves training efficiency, as described in Ref. [4]. The sampled transitions are used to evaluate the losses in Eqs. (7), (8), and (10), followed by gradient descent to optimize the model.

Q7: Sincere thanks for this astute comment. As pointed out in this comment, the diffusion models remove noises, i.e., denoising. This is achieved by fitting the conditional probability distributions for the transition dynamics and rewards distribution (see Eqs. (1b) and (1c)) and then applying the distributions to estimate current causal states from the perturbed sample $(\mathbf{o}_ t, \mathbf{a}_ t, r_ {t+1}, \mathbf{o}_ {t+1})$. The diffusion models can effectively denoise states when the proposed asynchronous diffusion model fits the conditional probability distribution reasonably well in Eq. (1c).

Q8: Intuitively, Assumption 3 refers to a common premise in the study of bisimulation metrics (e.g., see Ref. [5] and references therein), that is, the existence and uniqueness of the bisimulation metric for any pair of states. In other words, for any pair of states $(\mathbf{s}_i, \mathbf{s}_j)$, there exists a unique bisimulation metric to measure their similarity. Under this assumption, it becomes possible to use a model (e.g., the RNN model described in Theorem 4) to learn the bisimulation metric. In response to this suggestion, we have added the intuitive explanation of Assumption 3 in the revised version as

"To generalize the VFA bound, we assume the existence and uniqueness of $p$-Wasserstein bisimulation metric for any pair of states to measure their similarity."

As also suggested, we have clarified "$\forall(\mathbf{s}_i, \mathbf{s}_j) \in \mathcal{S} \times \mathcal{S}$" in the revised version of Assumption 3.

Q9: We express our heartfelt gratitude for this astute and inspirational comment. As pointed out in this comment, if we choose $c_T \approx 0$ and $c_R \approx 0$, then the right-hand side (RHS) of Eq. (13) is indeed equal to zero. Since the left-hand side (LHS) of Eq. (13) is the product of $c_R$ and the value gap with $c_R \approx 0$, the LHS of Eq. (13) is also zero, even though the value gap in the LHS of Eq. (13) is not necessarily zero. As a result, Theorem 1 still holds when $c_T \approx 0$ and $c_R \approx 0$.

On the other hand, we are interested in the boundedness and the upper bound of the value gap. In Theorem 2, we further derive the upper bound of the value gap by explicitly imposing the condition that $c_T$ and $c_R$ are non-zero. This is because the bisimulation metric would be invariably zero and become useless, if $c_T$ and $c_R$ are zero. Nevertheless, even if $c_T \approx 0$ and $c_R \approx 0$, the value gap derived in Theorem 2 remains finite since the reward defined is bounded by $[0, 1]$ (revised version, line 140). In other words, the value gap is always bounded under the bisimulation metric.

Q10: Sincere thanks for your insightful question. As clarified in the revised version, $P(\hat{\mathbf{s}}_t|\mathbf{o}_t)$ represents the process of extracting denoised causal states from noisy observations, which can be divided into denoising and causal state extraction, and computed by the proposed asynchronous diffusion model and an RNN model, respectively.

The denoising is achieved using a diffusion model, where we design a novel asynchronous diffusion model to effectively denoise perturbed observations. By contrast, the causal state extraction does not impose restrictions on the model used for fitting and extracting causal states. In Theorem 4, we employ an RNN model to learn the bisimulation metric for extracting causal states. Together, these two components jointly realize $P(\hat{s}_t|o_t)$.

To classify this, we have added the following explanation in Appendix A: "It should be noted that the asynchronous diffusion model algorithm denoises observations, which are then input into the bisimulation metric learning model to extract causal states."

Weakness 1: Sincere thanks for this insightful and inspirational comment. As pointed out in this comment, our current paper focuses on Gaussian noise for the reason that Gaussian noise is the most widely observed and considered in the literature. The consideration of Gaussian noise facilitates our analysis, helps shed insights, and can serve as a foundation for various noise distributions.

While specific results or resultant mathematic expressions relying on the specific noise distribution could change under different noise distributions, the derivation steps and methodology developed in this paper would remain invariant under different noise distributions. Moreover, the Gaussian Mixture Model (GMM), created by superimposing Gaussian distributions, has demonstrated an excellent ability to approximate any target distribution (See Ref. [1] for details). In this sense, our consideration of Gaussian noise has the potential to be extended to accommodate any distribution.

In terms of other types of partial observability (such as missing data), we would like to note that missing data imputation could be potentially solved by the diffusion model (See Ref. [2] for details). However, the detailed analysis of this lies beyond the scope of our study.

Weakness 2: Thank you for your feedback regarding the computation cost. We would clarify that our proposed CSR-ADM framework involves primarily three computational components, i.e., denoising and fitting conditional probability distributions using the asynchronous diffusion model, learning the bisimulation metric through models such as RNNs or MLPs, and reinforcement learning decision-making. The additional computational cost of CSR-ADM compared to traditional reinforcement learning stems from the asynchronous diffusion model in the first computational component.

Due to the introduction of noise intensity, the loss function Eq. (5) of the asynchronous diffusion model is twice that of a standard diffusion model, thereby doubling the associated computational cost. In Ref. [3], the computational cost of the diffusion model is $\widetilde{\mathcal{O}}(\mathrm{poly} \log d)$, where $d$ is the dimension of the input data. As a result, the computational cost of the causal state representation in our proposed CSR-ADM algorithm is $\widetilde{\mathcal{O}}(\mathrm{poly} \log \max\{|\mathcal{A}|, |\mathcal{O}|\})$, where $|\mathcal{A}|$ and $|\mathcal{O}|$ are the dimensions of the action and observation spaces, respectively.

In the revised version, we have included the following analysis of computational cost in Section 4:

"We evaluate the additional computational cost of the CSR-ADM compared to typical RL algorithms. Chen et al. (2024) analyzed the computational cost of a diffusion model to be $\widetilde{\mathcal{O}}(\mathrm{poly} \log d)$, where $d$ is the dimension of the input data. Considering our definition of noise intensity, the loss function of the asynchronous diffusion model (see Eq. (5)) is twice that of a standard diffusion model, directly doubling the computational cost. Therefore, the computational cost of the causal state representation is $\widetilde{\mathcal{O}}(\mathrm{poly} \log \max\{|\mathcal{A}|, |\mathcal{O}|\})$ in CSR-ADM."

Q1: Thank you for providing your insightful feedback. As clarified in the revised version, we make no assumptions about the dynamics of the environment; in other words, the state space, action space, and observation space can be either continuous or discrete. Similarly, the functions $f$, $g$, and $h$ can be either continuous and discrete. As also clarified in the revised version, two distinct states may produce the same observation due to the presence of noise.

Q2: We apologize for the confusion caused by this denoise definition. In the revised version, we define $f$ as a $b$-Hölder norm function and $F$ as the observation function.

Q3: We are extremely sorry for this typo. As classified in the revised version, $\zeta$ denotes the bisimulation model (see Algorithm 1, line 2), which be interpreted as the function that denoises observations and extracts causal states (original manuscript, line 234; revised version, line 213). Moreover, the term "noisy model" has been corrected to "$p(\mathbf{x}^k | \mathbf{x})$'' to avoid confusion in the revised version (original manuscript, line 269; revised version, line 256).

Q4: We apologize for this typo. We have corrected the typo in the revised version of Eqs. (7) and (8) and Algo. 1.

Q7*: Thank you so much for your very careful review and intriguing comment. After carefully considering your comments, we confirm that our asynchronous diffusion model only removes noise. Specifically, given the perturbed and partially obstructed observation $\mathbf{o}_ {t+1}$, the problem of interest is to uncover the underlying causal state $\mathbf{s}_ {t+1}$ by leveraging the learning experience from the past state $\mathbf{s}_ {t}$ and action $\mathbf{a}_ {t}$. In essence, this is a denoising process.

We have realized that our previous response to your previous question Q7 was inaccurate and misleading. We have now updated that response. Moreover, we have made the following modifications in the revised manuscript to ensure consistency:

Line 206: "Specifically, we design an asynchronous diffusion model to simultaneously denoise the states and rewards through the environment dynamics estimation";

Line 211: "The objective of the asynchronous diffusion model is to derive $P(\hat{\mathbf{s}}_ {t+1}\mid \hat{\mathbf{s}}_ {t}, \mathbf{a}_ t)$ and $P(\widehat{r}_ {t+1}\mid \hat{\mathbf{s}}_ {t}, \mathbf{a}_ t)$ from perturbed sample $(\mathbf{o}_ t, \mathbf{a}_ t, r_ {t+1}, \mathbf{o}_ {t+1})$, where $\hat{\mathbf{s}}_ {t}$ and $\hat{\mathbf{s}}_ {t+1}$ denote the causal states estimated under denoised observations, and $\widehat{r}_ {t+1}$ represents the denoised reward at time $t+1$";

Line 221: "Compute the (approximate) denoised causal state $\hat{\mathbf{s}}_t$ from $\mathbf{o}_t$ using observation denoise model $\theta$ and bisimulation model $\zeta$";

Line 234: "To obtain the denoised causal state $\hat{\mathbf{s}}_ {t+1}$, we use $r_ {t+1}$ and $\tilde{\mathbf{s}}_ {t+1} = \zeta(\mathbf{o}_ {t+1})$ as part of the inputs to the asynchronous diffusion model, along with $\hat{\mathbf{s}}_ {t}$ and $\mathbf{o}_ {t}$, where $\tilde{\mathbf{s}}_ {t+1}$ represents the causal state with noise".

We hope these revisions address the inconsistencies and provide a clearer explanation. Thank you for pointing this out.

Q9*: Sincere thanks for this very insightful and intriguing comment. As clarified in the revised version, we set $c_ {\mathrm{T}}$ and $c_ {\mathrm{R}}$ to be non-zero in Assumption 3, due to the fact that both the state transition probability and reward distribution are indispensable for establishing the equivalence between any two causal states and, subsequently, for establishing a metric for state bisimilarity.

On the one hand, the joint distribution $p(\mathbf{s}_ {t+1}, r_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ describes the transition dynamics and reward generation when action $\mathbf{a}_ {t}$ is taken in state $\mathbf{s}_ {t}$. It governs the system's behavior. The joint distribution $p(\mathbf{s}_ {t+1}, r_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ can be decomposed into the state transition probability $p(\mathbf{s}_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ and reward distribution $p(r_ {t+1} \mid \mathbf{s}_ {t}, \mathbf{a}_ {t})$ due to the previously rigorously proved independence of the future state $\mathbf{s}_ {t+1}$ and the reward $r_ {t+1}$ conditioned on the current state $\mathbf{s}_ {t}$ and action $\mathbf{a}_ {t}$ (See Ref. [1] for details). It is crucial to ensure the equivalence of two causal states in both state transition probabilities and reward distributions to satisfy the requirements of bisimulation.

On the other hand, we use the $p$-Wasserstein distance to quantify the differences between two bisimilar states by measuring their differences in both state transition probabilities and reward distributions. If $c_ {\mathrm{R}} \approx 1$, the constraint $c_ {\mathrm{R}} + c_ {\mathrm{T}} < 1$ (needed to guarantee bounded difference between value functions of causal states under the bisimulation metric, as formally established in Theorem 1) implies that $c_ {\mathrm{T}} \approx 0$. In this case, the bisimulation metric fails to capture the impact of state transition probabilities on the equivalence relationship of the two states. This would invalidate the definition of bisimulation.

To clarify this, we have highlighted the permissible ranges of $c_ {\mathrm{T}}$ and $c_ {\mathrm{R}}$ (neither of them can take the values of 0 or 1) in Assumption 3 and Theorem 1 in the revised version.

Reference

[1]. Sutton, Richard S., and Andrew G. Barto. "Reinforcement learning: an introduction, 2nd edn. Adaptive computation and machine learning." (2018).

We express our heartfelt gratitude for your feedback.

• As suggested, we have clarified in the revised version that a POMDP with perturbed inputs stands for a Markov decision process (MDP) with only partially observable, perturbed states (due to partial obstruction and noises/perturbation of the observation). By contrast, standard POMDPs do not require observations to be noisy or perturbed, as discussed in Ref. [1-3].

• Sincere thanks for pointing out a typo in Eq. (1a). As pointed out by the reviewer, the observation $\mathbf{o}_ {t}$ depends solely on the state $\mathbf{s}_ t$ at each time step $t$. In response to this comment, we have corrected Eq. (1a) to "$\mathbf{o}_ {t} = F\left(\mathbf{s}_ {t}, \mathbf{e}_ {t}\right) \iff P\left(\mathbf{o}_ {t}\mid \mathbf{s}_ {t}\right)$" in the revised version.

• We apologize for double-defining $\zeta$ to denote two different models in the previously submitted version. In the revised version, we have now used $\phi$ to indicate the reward noise model and $\zeta$ to denote the bisimulation model.

Once again, we sincerely appreciate your approval and valuable comments.

Reference

[1]. Barenboim, Moran, and Vadim Indelman. "Online POMDP planning with anytime deterministic guarantees." Advances in Neural Information Processing Systems 36 (2024).

[2]. Lev-Yehudi, Idan, Moran Barenboim, and Vadim Indelman. "Simplifying complex observation models in continuous POMDP planning with probabilistic guarantees and practice." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. No. 18. 2024.

[3]. Singh, Gautam, et al. "Structured world belief for reinforcement learning in POMDP." International Conference on Machine Learning. PMLR, 2021.