Episodic Novelty Through Temporal Distance

Thank you for your positive recommendation of our work and your insightful comments. We greatly appreciate your thoughtful review. Below, we address each of your concerns in detail.

Q1: Detailed discussion on the successor distance and its assumptions.

A: Your perspective is insightful. If a state $y$ is unreachable from state $x$ (e.g., $x$ is an absorbing state), then $p^{\pi}(s_f=y|s_0=x)=0$. According to our definition, the successor distance would be infinite in this case, i.e., $d_{\text{SD}}^{\pi}(x,y)=\infty$. This highlights a theoretical limitation of the successor distance concept, as it assumes we're dealing with ergodic MDP problems. We've acknowledged this limitation in the conclusion section of our paper.

Q2: More insights on the parametrization of the energy function.

A: We decompose the energy function into a potential function and a distance function to ensure that, theoretically, the optimal solution of the learned distance function aligns with the temporal distance (successor distance) as shown in Proposition 3. Removing the potential function would violate this principle. In practice, we draw inspiration from CRL research[1], which has explored various energy function forms, including cosine similarity[2], dot product[3], negative L1 and L2 distance[4], and quasimetrics[5,6]. For our method ETD, we primarily consider four energy function forms: Cosine, L2, MRN (which omits the potential), and MRN-POT (which we used in this study).

We conducted ablation experiments in a 17x17 SpiralMaze (Figure 13). Results show that the cosine energy function struggled to distinguish distant states effectively. The L2 and MRN functions yielded similar outcomes, while MRN-POT demonstrated the best performance, aligning with our theoretical predictions.

Further ablation experiments in Miniworld-ObstructedMaze-1Q corroborate that decomposing the energy function into potential and asymmetric distance forms can achieve superior performance.

[1] Bortkiewicz, Michał, et al. "Accelerating Goal-Conditioned RL Algorithms and Research." arXiv preprint arXiv:2408.11052 (2024).

[2] Chen, Ting, et al. "A simple framework for contrastive learning of visual representations." International conference on machine learning. PMLR, 2020.

[3] Radford, Alec, et al. "Learning transferable visual models from natural language supervision." International conference on machine learning. PMLR, 2021.

[4] Hu, Tianyang, et al. "Your contrastive learning is secretly doing stochastic neighbor embedding." arXiv preprint arXiv:2205.14814 (2022).

[5] Myers, Vivek, et al. "Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making." arXiv preprint arXiv:2406.17098 (2024).

[6] Wang, Tongzhou, et al. "Optimal goal-reaching reinforcement learning via quasimetric learning." International Conference on Machine Learning. PMLR, 2023.

Q3: Detailed discussion on the infoNCE loss.

A: Theoretically, using symmetric InfoNCE loss yields an optimal solution where the denominator depends solely on $y$. This allows our distance function's optimal solution to recover the successor distance. In contrast, using standard InfoNCE loss results in an optimal solution with a denominator of the form $C(x)p_{s_f}(y)$[7]. In practice, however, the performance difference between the two is minimal. Please see our experiments in Appendix B.2 (Figures 13 and 14).

[7] Eysenbach, Benjamin, et al. "Contrastive learning as goal-conditioned reinforcement learning." Advances in Neural Information Processing Systems 35 (2022): 35603-35620.

Q3: Please test the performance of ETD on continuous control tasks.

Thank you for your suggestion. We'd like to clarify several key points:

• The scale of state spaces is not directly related to whether action spaces are discrete or continuous. Instead, it's determined by the dimensionality of the state input (e.g. vector or image). In fact, the noisy-TV problem and image-based observations are major reasons why count-based methods don't work well.

• The difficulty of exploration tasks is also not directly related to whether action spaces are discrete or continuous. For instance, in MiniGrid-OMFull, training PPO for 1e7 steps still yields zero cumulative reward. Conversely, in many Meta-World tasks, PPO can achieve optimal performance in just 1e6 steps.

• We acknowledge that continuous action tasks have many real-world applications. However, as baseline methods (RND, NovelD, NGU, E3B, DEIR) for sparse reward CMDP problems primarily focus on discrete control tasks and haven't been implemented for continuous control tasks, we aligned our experiments accordingly.

• To our knowledge, the continuous control tasks mentioned by the reviewer aren't primarily designed for sparse reward exploration problems, and our baseline methods haven't been tested on these tasks. For instance, Meta-World uses dense rewards. Even if we zero out step-wise rewards and only keep terminal success signals, PPO can still learn some tasks within 1e6 steps. For more complex tasks, all current intrinsic motivation methods struggle to complete them. Nevertheless, we did as the Reviewer suggested, selecting tasks from DMC, Meta-World, and MuJoCo “Cheetah-Vel-Sparse” to test ETD and baseline methods in continuous control problems. Results can be found in Appendix B.2.

DMC Experiments (Figure 12): We selected three tasks with relatively sparse rewards from the DMC environment: "Acrobot-swingup_sparse", "Hopper-hop", and "Cartpole-swingup_sparse". Our results demonstrate that ETD consistently performs well, showing significant improvements over PPO. We also reproduced two baselines that excelled in discrete tasks—NovelD and E3B—but found they couldn't maintain consistent performance across all three continuous control tasks.

Meta-World Experiments (Figure 13): Meta-World environments typically use dense rewards. We modified these to provide rewards only when tasks succeed. We tested on "Reach," "Hammer," and "Button Press" tasks, finding that PPO without intrinsic rewards performed well. This suggests that Meta-World tasks may not be ideal benchmarks for exploration problems. To our knowledge, intrinsic motivation methods haven't been extensively tested on Meta-World, making it less suitable for comparing exploration-based methods.

MuJoCo Cheetah-Vel-Sparse Experiments (Figure 14): We couldn't find an official implementation of "Cheetah-Vel-Sparse," and to our knowledge, exploration-based methods haven't been tested in this scenario. However, following the reviewer's suggestion, we modified the Mujoco HalfCheetah environment's forward reward function to provide rewards only when the target velocity is reached. Our experiments revealed that PPO already performs well in this task. Adding intrinsic motivation methods didn't significantly improve performance, likely due to the low exploration difficulty. These environments require relatively low exploration capabilities, do not necessitate intrinsic motivation methods, and are unsuitable as benchmarks for comparing exploration methods.

We sincerely thank you for your valuable time, constructive criticism, and insightful suggestions to help improve the quality of our paper. In response to your questions and concerns, we have made the following revisions and clarifications.

Q1: Relationship with “Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making” and our contribution.

A: The core intuition behind our method is that providing an intrinsic reward to the agent enhances exploration in sparse reward settings. While existing count-based and similarity-based methods have limitations, using temporal distance addresses both noisy-TV problems and state similarity issues that satisfy the triangle inequality. This is crucial for the Contextual MDP (CMDP) problems with high-dimensional (image) observations that we focus on.

In learning temporal distance, we drew inspiration from "Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making" (CMD). However, extending this concept to CMDP problems is non-trivial for several reasons:

1. Problem Settings: CMD primarily targets on Goal-conditioned RL (GCRL) problems, whereas our method (ETD) addresses sparse reward CMDP problems.
2. Policy Learning: CMD's policy minimizes the temporal distance between the current state and the goal directly. In contrast, our method uses this distance as an intrinsic reward to encourage PPO exploration, effectively maximizing the temporal distance between the current state and the episodic history.
3. Definition of Successor Distance: CMD's definition of successor distance is independent of $\pi$, whereas our successor distance is dependent on $\pi$ and learned in an on-policy manner. We also provide proof that our on-policy form of successor distance still satisfies the quasimetric property, which differs from the original paper.
4. Code Implementation: We integrated CMD's temporal distance learning with existing CMDP baseline methods and have made our code publicly available on https://anonymous.4open.science/r/ETD to ensure reproducibility.

Furthermore, we conducted comprehensive experiments to validate ETD's performance (Section 5) and performed ablation studies on the aggregate function, asymmetric/symmetric distance function, and the effectiveness of temporal distance itself (Section 5.3).

Q2: Please provide code.

A: We have released the code and ensure that all experimental results can be reproduced, see https://anonymous.4open.science/r/ETD.

Dear reviewer akpb,

We have updated our experiments in DMC, Meta-World, and MuJoCo “Cheetah-Vel-Sparse” in Appendix B.2. We also made our code publicly available on https://anonymous.4open.science/r/ETD. We are wondering if our response and revision have cleared your concerns. We would appreciate it if you could kindly let us know whether you have any other questions. We are looking forward to comments that can further improve our current manuscript. Thanks!

Best regards,

The Authors

Thank you for your strong support in recognizing the novelty of our work. We're also grateful for your insightful comments and questions, which we'll address point-by-point below.

Q1: Violation of MDP assumption under the definition of episodic intrinsic reward.

A: Exploration methods primarily aim to reward previously unvisited states, which necessitates remembering already visited ones. Consequently, the definition of intrinsic rewards inherently violates the Markov property. For instance, count-based methods maintain a buffer for historically visited states, resulting in a non-Markovian learned policy. In fact, learning non-Markovian policies is quite common in RL. Policy networks often integrate RNNs to enhance memory capabilities in sequential decision-making problems[1,2]. These RNNs inherently contain information about historical states, further departing from the Markov assumption.

[1] Chen, Lili, et al. "Decision transformer: Reinforcement learning via sequence modeling." Advances in neural information processing systems 34 (2021): 15084-15097.

[2] Bakker, Bram. "Reinforcement learning with long short-term memory." Advances in neural information processing systems 14 (2001).

Q2: Detailed explanations about the temporal distance learning method.

A: Thank you for your suggestions, which have helped us improve our manuscript. We've revised the method section, highlighting modifications in blue for clarity. We'll address your three concerns as follows:

• Relationship between Contrastive Learning and Successor Distance: We use contrastive learning to estimate the successor distance, following prior work[3]. Consider the joint distribution $p\_\gamma^\pi\left({s}\_{f}=y \mid {s}\_0=x\right)$ over two states $(x,y)$. Let $p\_s(x)$ be the marginal state distribution and $p\_{s_f}(y)=\int\_{s} p\_s(x) p\_\gamma^\pi\left({s}\_{f}=y \mid {s}\_0=x\right)$ be the corresponding marginal distribution over future states. The energy function $f\_{\theta}(x,y)$ assigns higher values to $(x, y)$ tuples from the joint distribution and lower values to those sampled independently from marginal distributions. In practice, we sample state pairs from trajectories as \left\\{ x_i, y_i | x_i=s_t, y_i=s_{t+\Delta}, \Delta \sim \text{Geom} (1-\gamma) \right\\}_{i=1}^B, where $(x\_i, y\_i)$ are positive samples and $(x\_i, y\_j)\_{i\neq j}$ are negative samples (Figure 3). With a sufficiently large batch size B, the optimal solution $f\_{\theta^*}$ based on symmetric InfoNCE loss satisfies $f\_{\theta^*}(x,y) = \log \left( \frac{p^\pi\_\gamma(s^f = y | s\_0 = x)}{C \cdot p\_{s_f}(y)} \right)$. Then we can derive $d^{\pi}\_{\text{SD}}(x, y) = f\_{\theta^*}(y,y) - f\_{\theta^*}(x,y)$.
• Decomposition of Energy Function: While the above method derives the successor distance from contrastive learning results, it doesn't guarantee the triangle inequality and other quasimetric properties due to training errors. To ensure $d^{\pi}\_{\text{SD}}(x, y)$ satisfies these properties at the network structure level, we leverage the fact that the optimal solution $f\_{\theta^*}$ can be decomposed into a potential function (dependent only on the future state) minus the successor distance function (Equation 11, Appendix A). Following prior work[3], we parameterize $f\_{\theta^*}$ as a potential net and a quasimetric net: $f\_{\theta=(\phi,\psi)}(x,y) = c\_{\psi}(y)- d_{\phi}(x,y)$. This approach allows us to learn the successor distance directly while optimizing the contrastive learning loss. After training, we discard $c\_{\psi(y)}$ and use $d\_{\phi}(x,y)$ as our temporal distance.
• Reason for choosing Symmetric InfoNCE Loss: Theoretically, using symmetric InfoNCE loss yields an optimal solution where the denominator depends solely on $y$, whereas standard InfoNCE loss results in a denominator of the form $C(x)p\_{s_f}(y)$[4]. In practice, however, the performance difference between the two is minimal, as demonstrated in our experiments in Appendix B.2 (Figures 13 and 14).

[3] Myers, Vivek, et al. "Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making." arXiv preprint arXiv:2406.17098 (2024).

[4] Eysenbach, Benjamin, et al. "Contrastive learning as goal-conditioned reinforcement learning." Advances in Neural Information Processing Systems 35 (2022): 35603-35620.

Q3: More complex example to illustrate ETD’s strengths.

A: We've included a more complex maze example in Appendix B.3. Figure 16 showcases the results, demonstrating that our method ETD successfully learns temporal distances aligning with the ground truth. In contrast, the other two methods struggle to learn a valid distance in this more challenging environment.

Q4: What is the best practice of choosing the $\beta$?

A: $\beta$ is a common hyperparameter for methods based on intrinsic rewards, defined as $r_t=r_t^e + \beta b_t$. We summarize the forms of $b_t$ for recent intrinsic motivation methods in Table 1. The selection of $\beta$ is task-specific, typically chosen from several candidate values (1e-2, 1e-3, 5e-3, 1e-4). In our experiments, we found $\beta$=1e-2 to be generally suitable for MiniGrid, Crafter, and MiniWorld tasks. We provide candidate $\beta$ values for our method and all baseline methods in Tables 2–10, labeled as "intrinsic reward coef". In practice, we normalized intrinsic rewards for all methods by subtracting the mean and dividing by the standard deviation. This ensures that the scale of intrinsic rewards doesn't vary significantly across different tasks. Consequently, we recommend using 1e-2 as a default value for $\beta$ when tackling new tasks.

Thank you for your thoughtful review and insightful questions. We appreciate the time and effort you've put into evaluating our work. Your feedback has been valuable in helping us improve our paper and consider new directions for future research. We'll address each of your questions in detail below.

Q1: Consider combining temporal distance with (extrinsic) reward-based similarity.

A: Combining temporal distance with reward-based similarity is an interesting idea. However, our tasks primarily focus on exploration in sparse-reward environments. In these settings, most states yield no rewards, making reward-based similarity calculations unreliable. Nonetheless, this approach could be valuable in other contexts—such as learning generalizable representations, as in the paper you referenced. We appreciate the suggestion and will explore this direction in our future work.

Q2: Experiments on continuous action spaces.

A: Thank you for your suggestion. Indeed, ETD can be straightforwardly extended to continuous action spaces. We initially focused on discrete action spaces because exploration-based baseline methods are primarily tested in discrete environments, and we wanted to align with them. Following the reviewer's recommendation, we conducted additional experiments in the following two continuous control tasks.

• DMC Experiments (Figure 12): We conducted experiments on three tasks from the DMC environment with relatively sparse rewards: "Acrobot-swingup_sparse", "Hopper-hop", and "Cartpole-swingup_sparse". Our results suggest that ETD consistently performs well, showing significant improvements over PPO. We also implemented two baselines that excelled in discrete tasks—NovelD and E3B—but found they couldn't maintain consistent performance across all three tasks.

• Meta-World Experiments (Figure 13): Tasks in Meta-World environments, which primarily involve robotics manipulation (similar to Fetch as the reviewer mentioned), typically use dense rewards. We modified these to provide rewards only upon task completion. Our experiments on "Reach," "Hammer," and "Button Press" tasks showed that PPO without intrinsic rewards performed adequately. This result suggests that Meta-World tasks may not be the most suitable benchmarks for exploration problems.

Q3: Why combined ETD with PPO instead of off-policy algorithms?

A: We selected PPO primarily because it serves as the foundation for most prior intrinsic reward methods, enabling straightforward comparisons. Moreover, PPO supports high parallelization of environments, which improves time efficiency. It is also robust to hyperparameters, allowing us to focus on enhancing the exploration mechanism.

Dear reviewer uqHy,

We have updated our experiments in continuous action space in Appendix B.2. We are wondering if our response and revision have cleared your concerns. We would appreciate it if you could kindly let us know whether you have any other questions. We are looking forward to comments that can further improve our current manuscript. Thanks!

Best regards,

The Authors