Episodic Novelty Through Temporal Distance

Authors: Yuhua Jiang, Qihan Liu, Yiqin Yang, Xiaoteng Ma, Dianyu Zhong, Hao Hu, Jun Yang, Bin Liang, Bo XU, Chongjie Zhang, Qianchuan Zhao
Primary area: reinforcement learning
Keywords: Reinforcement Learning

Abstract:
Exploration in sparse reward environments remains a significant challenge in reinforcement learning, particularly in Contextual Markov Decision Processes (CMDPs), where environments differ across episodes. Existing episodic intrinsic motivation methods for CMDPs primarily rely on count-based approaches, which are ineffective in large state spaces, or on similarity-based methods that lack appropriate metrics for state comparison. To address these shortcomings, we propose Episodic Novelty Through Temporal Distance (ETD), a novel approach that introduces temporal distance as a robust metric for state similarity and intrinsic reward computation. By employing contrastive learning, ETD accurately estimates temporal distances and derives intrinsic rewards based on the novelty of states within the current episode. Extensive experiments on various benchmark tasks demonstrate that ETD significantly outperforms state-of-the-art methods, highlighting its effectiveness in enhancing exploration in sparse reward CMDPs.

Decision: accept (poster)
Reviewer scores: 8, 6, 8, 5

Reviews and discussion:
<thread>
creation date:
1730604023523

thread_type:
official_review

<thread_object>
creator: reviewer_akpb

<content>
summary:
This paper addresses the challenge of exploration in sparse reward environments within Contextual Markov Decision Processes (CMDPs), where environments vary between episodes. The authors propose Episodic Novelty Through Temporal Distance (ETD), a method that leverages temporal distance as a metric for state similarity and intrinsic reward computation. Using contrastive learning, ETD estimates temporal distances to assign intrinsic rewards based on the novelty of states within an episode. Experimental results on diverse benchmark tasks show that ETD outperforms state-of-the-art methods, enhancing exploration in sparse reward CMDPs. The paper is well-structured and detailed, and the ETD method is well-described.

strengths:
The paper compares the proposed method with various existing approaches (including DEIR, NovelD, E3B, EC, NGU, RND, and the Count-based method), covering many classical and common algorithms in the exploration field. By testing these methods across multiple benchmark environments, the paper demonstrates the advantages of the ETD method in sparse reward and high-dimensional pixel environments, validating its applicability across different exploration demands and tasks.

weaknesses:
1. The core approach of ETD primarily builds upon the main idea of "Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making," using contrastive learning to estimate temporal distance. It lacks substantial algorithmic innovation.
The innovation of the ETD (Episodic Temporal Distance) method primarily lies in its approach to learning temporal distances. However, this method closely follows key aspects of the referenced work, "Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making," in several crucial areas:
1) Discounted State Occupancy Measure: In the ETD method, the discounted state occupancy measure p^\pi_\gamma(s_f = y | s_0 = x) is used to estimate the transition probability from state x to y . The formula is as follows: p^\pi_\gamma(s_f = y | s_0 = x) = (1 - \gamma) \sum_{k=0}^{\infty} \gamma^k p^\pi(s_k = y | s_0 = x) This formula originates from "Learning Temporal Distances," where the discounted state occupancy measure p^{\pi}_{\gamma} is defined as the discounted distribution over future states s^{+} : p^{\pi}_{\gamma}(s^{+} = s' | s_0 = s) = (1 - \gamma) \sum_{k=0}^{\infty} \gamma^k p^{\pi}(s_k = s' | s_0 = s)
2) Successor Distance: The successor distance formula used in ETD is also directly derived from the referenced work, "Learning Temporal Distances."
3) Loss Function: Both works adopt a symmetrized InfoNCE loss function to train the model through contrastive learning, which is a critical component of the approach.
4) Energy Function: The energy function utilized in ETD, f_{\theta = (\phi, \psi)}(x, y) = c_{\psi}(y) - d_{\phi}(x, y) , is also sourced from "Learning Temporal Distances," where it is presented as: f_{\phi, \psi}(s, a, g) = c_{\psi}(g) - d_{\phi}(s, a, g)


2. Experiments are conducted solely on discrete control tasks, with no tests on continuous control tasks (e.g., robot control tasks in Meta-World and Mujoco). State spaces in discrete control tasks are relatively small, allowing agents to explore enough states within a shorter timeframe. In contrast, continuous control tasks present larger state spaces and greater exploration challenges, making it essential to validate the method’s effectiveness in these scenarios. Given that many real-world tasks involve continuous control, this omission limits the method's persuasiveness for broader application scenarios.
3. The absence of publicly available code restricts the ability to independently verify the method's effectiveness.

questions:
1. Please test the performance of ETD on continuous control tasks.
To evaluate the ETD method in continuous control tasks, the authors could consider tasks in environments such as Meta-World (or Panda-Gym) and Mujoco. Examples of basic tasks include "Push," "Reach," and "Pick-Place" in Meta-World (or Panda-Gym), which offer high environmental complexity and sparse reward settings, making them suitable for assessing ETD's exploratory capabilities. Additionally, Mujoco environments like "Cheetah-Vel-Sparse," which have high-dimensional state spaces, could further validate ETD’s performance in high-dimensional continuous spaces. By plotting and comparing learning curves across environments—such as average episode rewards or success rates over training steps—the authors could demonstrate whether ETD converges faster or more stably in sparse reward continuous control tasks compared to other methods.

2. Please provide code.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730635143175

thread_type:
official_review

<thread_object>
creator: reviewer_tisq

<content>
summary:
The paper presents a new intrinsic reward for novelty-based reinforcement learning. The intrinsic reward is based on the estimated temporal distance between two states, which estimates the probability that one state can be reached from another state in multiple time steps. Here, discounting is used to give preference for shorter transitions. The temporal distance is learned by a contrastive loss based on the infoNCE loss. The algorithm is compared against several baseline methods on a wide variety of discrete action exploration tasks and shows promising performance.

strengths:
- A well motivated new intrinsic reward signal for RL
- The concept is simple and provides a strong performance
- Exhaustive evaluations, good comparisons the baseline methods as well as nice ablations
- Good insights why baseline methods fail

weaknesses:
the paper is already of high quality and I could not find major weaknesses. Minor weaknesses are given in the questions section.

questions:
- a more detailed discussion on the successor distance and its assumptions would be insightful. E.g., what happens if the MDP does not allow for loops (which is the case we have to deal with real dynamics, e.g. velocities). Then this distance would be infinite, wouldnt it?
- More insights on the parametrization of the energy function. Why do we need separate networks for  the potential and the assymetric distance? Could we also ablate removing the potential here?
- Why do we need to "symmetrize" the infoNCE loss? Does this imply that transitions are "invertible"? Also here, a ablation and more discussion would be nice.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730715081550

thread_type:
official_review

<thread_object>
creator: reviewer_gftv

<content>
summary:
This paper presents a novel reinforcement learning approach to measure similarities between visited states, using the resulting state distances as a reward bonus to encourage exploration in tasks with sparse rewards. The methodology is technically sound, and the results are promising.

strengths:
- The paper is well-written, with a clear and cohesive narrative. Most technical details are effectively conveyed through illustrative figures and results from intuitive toy tasks.
- The experimental tasks are appropriately chosen, providing sufficient complexity to evaluate the approach.
- The experimental results, along with ablation studies, clearly demonstrate the advantages of the proposed method over other baselines.
- The paper offers a comprehensive analysis and comparison of different technical approaches used by the proposed method and baseline methods, providing valuable insights for readers.

weaknesses:
## MDP assumption
The definition of the intrinsic bonus reward violates the MDP assumption. In section 2, the total reward $r(s_t, a_t, s_{t+1})$ is a decomposed as the environment reward $r_t^e$ plus the weighted bonus $\beta b_t$. However, $b_t$ is a function that depends on the visited states within the episode, which disrupts the definition of total reward and violates the MDP assumption. In this case, the visited states influences the intrinsic reward, potentially harming the policy built upon MDP, as the actions are solely selected by $\pi(a_t|s_t)$ without knowledge of the states' visiting history. Consequently, the same action $a_t$ may yield completely different rewards $r_{t+1}$, depending on whether the $s_{t+1}$ has been visited in the history or not. I believe this is a critical technical issue in this paper, and should be explained thoroughly. At the same time, do other related works using reward bonuses also encounter the same issue?

## Unclear content
The content between lines 186 and 208 is challenging to follow. I suggest the authors restructure this section, providing additional explanations and intuitions. Specifically:
- The meaning of the sentence, "Contrastive learning can estimate the successor distance when positive samples are drawn from the discounted state occupancy measure," is unclear. What does it mean to draw samples from a measure?
- The motivation for using the energy function and its decomposition into the potential net and quasimetric net in practice is unclear. What is this energy function, and why is it applied here?
- The rationale behind using the infoNCE loss also needs further explanation.

## Minor issues
- The SpiralMaze in Figure 2 appears to have a linear structure, which may not effectively demonstrate ETD's advantage in distance learning. A more complex example could better illustrate the method's strengths.
- What is the best practice of choosing the $\beta$? I think it depends on the specific task and is therefore a HP.
- Line 188, there should be a $ds$ in the integral.

questions:
Please address the issues listed in the weaknesses section.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731133364502

thread_type:
official_review

<thread_object>
creator: reviewer_uqhy

<content>
summary:
This paper introduces Episodic Novelty through Temporal Distance (ETD), a new approach for exploration in Contextual Markov Decision Processes (CMDPs) with sparse rewards. ETD uses temporal distance as a metric for state similarity to compute intrinsic rewards, encouraging agents to explore states that are temporally distant from their episodic history. The authors employ contrastive learning to design a quasimetric that estimates episodic temporal distances. They evaluate  ETD when combined with PPO on various CMDP benchmarks, i.e., MiniGrid, and Crafter (pixel-based observations), and MiniWorld (pixel-based observations).

strengths:
1. The paper introduces a novel method to use temporal distance as a (quasi)metric for state similarity.
2. The paper conducts extensive experiments across multiple CMDP environments, comparing ETD to several baseline methods.
3. ETD + PPO demonstrates robust performance improvements, especially in challenging sparse reward scenarios.
4. Results on extensive experiments across multiple CMDP environments, comparing ETD to several baseline methods have been reported.
5. The paper is well-structured, with clear explanations of the motivation, methods, and results.

weaknesses:
1. The proposed ETD doesn’t take into consideration extrinsic rewards to compute similarity. Intuitively, states with similar rewards could be considered similar in terms of the task objective [1].
2. The approach has been primarily tested on discrete action spaces, and its effectiveness in continuous action domains such as MuJoCo [2], DeepMind Control Suite [3], or Fetch [4] environments remains unexplored.

[1] Agarwal, Rishabh, et. al. “Contrastive behavioral similarity embeddings for generalization in reinforcement learning.” arXiv preprint arXiv:2101.05265 (2021).

[2] https://gymnasium.farama.org/environments/mujoco/

[3] Tassa, Yuval, et al. "Deepmind control suite." arXiv preprint arXiv:1801.00690 (2018).

[4] Plappert, Matthias, et al. "Multi-goal reinforcement learning: Challenging robotics environments and request for research." arXiv preprint arXiv:1802.09464 (2018).

questions:
1. Could the authors shed light on why PPO, an on-policy algorithm, was chosen to be combined with ETD instead of off-policy algorithms such as DQN or SAC? Prior work has used off-policy algorithms extensively for sparse-reward tasks [2] [3].
2. Is ETD straightforward to be extended to continuous action spaces? If so, did the authors run any experiments? If not, what could be possible bottlenecks?
3. Did the authors consider combining temporal distance with reward-based similarity, or explore weighting the temporal distance based on extrinsic rewards? Are there any potential trade-offs or challenges in incorporating extrinsic rewards into the similarity metric that the authors anticipate?

[2] Andrychowicz, Marcin, et al. "Hindsight experience replay." Advances in neural information processing systems 30 (2017).

[3] Co-Reyes, John D., et al. "Evolving reinforcement learning algorithms." arXiv preprint arXiv:2101.03958 (2021).
</content>
</thread_object>

</thread>
<thread>
creation date:
1733139054472

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Rebuttal Summary

comment:
We sincerely thank all reviewers for their thorough review and valuable feedback. Here are the key concerns we have addressed:

- **Additional Experiments:**
    - **Continuous action space experiments:** Following suggestions from Reviewers `uqHy` and `akpb`, we tested our method (ETD) across DMC, Meta-World, and MuJoCo environments. Our results show improved exploration in sparse reward settings with continuous actions, though with smaller improvements than in discrete action environments, as these environments were not specifically designed for exploration tasks.
    - **Ablation studies:** Our experiments on ETD's energy function and loss function components confirm that our design choices are more suitable.
    - **More Complex example:** We demonstrated ETD's superior ability to learn ground-truth distances compared to similarity measures used in other intrinsic motivation approaches.
- **Detailed Explanations:**
    - **Method:** We enhanced the clarity of our Method section and addressed questions from Reviewers `gFtv`, `TiSQ`, and `akpb` regarding the energy function, loss function, and other technical details.
    - **Implementation:** We explained our choice of PPO over off-policy algorithms, our rationale for not considering reward-based state similarity measurements,, and our preferred selection for hyperparameter $\beta$.
- **Reproducibility and Limitations:**
    - **Code Release:** Our code is available at [https://anonymous.4open.science/r/ETD](https://anonymous.4open.science/r/ETD/README.md), with full result reproducibility.
    - **Limitations:** We acknowledge that current intrinsic reward-based methods violate the Markov assumption, creating additional challenges. Our successor distance definition also requires the ergodic MDP assumption. We thank Reviewers `gFtv` and `TiSQ` for identifying these limitations, which we will address in future work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**Summary**: The paper introduces Episodic Novelty Through Temporal Distance (ETD), a novel exploration method for Contextual Markov Decision Processes (CMDPs) with sparse rewards. ETD uses temporal distance as a state similarity measure, computed via contrastive learning, to encourage exploration of states that are temporally distant from the episodic history. The method is evaluated on benchmarks like MiniGrid, Crafter, and MiniWorld, showing superior performance over state-of-the-art intrinsic reward methods.

**Strengths**:
- The contributions in the paper are novel. Both reviewers `uqHy` and `gFtv` highlight the paper's key innovation—using temporal distance as a similarity metric—which improves upon previous count-based and similarity-based methods.
- The paper presents comprehensive experiments. `uqHy` mentions the variety of CMDP benchmarks (e.g., MiniGrid, Crafter, MiniWorld), while `gFtv` acknowledges the inclusion of challenging environments. All reviewers commend the ablation studies and comparisons to baselines, which provide deeper insights into the method's performance.
- The method displays significant performance improvements over SotA, particularly in noisy environments, where count-based methods fail.
- The paper is well-written. Reviewers find the writing clear, with a cohesive narrative and intuitive explanations, though some sections required clarification.

**Weaknesses**:
- Limited generalization to continuous action spaces: `uqHy` initially criticized the lack of evaluations on continuous action spaces. In response, the authors provided additional experiments on DMC and Meta-World environments, showing some performance gains compared to baselines but smaller than those on discrete tasks.
- Violation of the Markov assumption: `gFtv` points out that the intrinsic reward depends on the history of visited states, violating the Markov property. While the authors acknowledged this as a common limitation of intrinsic motivation methods, it remains a conceptual issue and limitation of the method.

**Recommendation**: Overall, reviewers agree that the paper is novel, well-executed, and presents valuable contributions to exploration in RL. However, some concerns remain about the generalization to continuous action spaces and the theoretical implications of violating the Markov property. As such, my decision is to accept the paper as a poster.