Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes Adversarial Intrinsic Motivation (AIM), a state distribution matching algorithm for goal-conditioned reinforcement learning. State distribution matching is an effective approach to imitation learning where the target distribution is yielded by the expert behavior. However, it is unclear how to apply it to goal-conditioned RL because the target distribution is unachievable - it puts all mass on the goal states and none on the trajectories leading to them. This paper proposes to use Wasserstein-1 distance as the distance measure between the agent's state visiting distribution and the goal distribution. To measure the distance between two states, the authors propose a quasimetric specific to MDPs - the time-step metric. The authors then prove that the policy that minimizes the Wasserstein-1 distance between the agent's state visiting distribution and the goal distribution under the time-step metric also minimizes the steps needed to achieve the goal. Empirical results show that AIM can provide dense and effective reward signals to the agent so that it learns better than using only the sparse reward of achieving the goal. When combined with Hindsight Experience Replay (HER), AIM outperforms the sparse goal-achieving rewards in a goal-conditioned RL setup and approaches the performance of a near-oracle hand-designed reward signal.
main_review: Overall this paper is well written and easy to follow. The idea of using Wasserstein-1 distance to measure the distance between the state visiting distribution and the unachievable goal distribution makes sense. The theoretical analysis provides insight into the solution found by minimizing the Wasserstein-1 distance. The experiments successfully demonstrate the merits of AIM. I especially like the thorough analysis in the experiment section where the authors provide detailed explanations to both the successful cases and the failed cases.

I do have one suggestion regarding the experiment. One natural baseline I can think of is to combine GAIL with HER in the goal-conditioned setup where the trajectories leading to the hindsight goals are treated as expert trajectories. So far I do not see an obvious reason why AIM would be better than this baseline. Thus I think this can be a strong baseline to compare against.
limitations_and_societal_impact: The main contribution of this paper is theoretical and the experiments are mostly for illustration purposes. I do not see any potential negative societal impacts of this paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a method that uses the Wasserstein-1 distance between policy State distributions in order to provide additional reward and intrinsic motivation for learning policies. The method comes up with an approximation for being able to compute and use the Wasserstein one distance that can work in some practical settings. The method in the paper is used to improve the learning performance on a collection of 2d navitaion tasks and fetching tasks.

Pros
The paper does propose an interesting way to be able to efficiently estimate the Wasserstein-1 distance that can be used to compute policies state visitation distributions distance.
The method is shown to accelerate learning on some example environments.

Cons
It's not entirely clear how to place this paper. The paper is proposing an intrinsic motivation method but the actual objective or method in the paper is a better way to estimate the Wasserstein-1 distance and how it can be used to match Target distributions as in a type of imitation learning. So then either the paper should have better comparisons and experiments that compare to other imitation learning methods that are also used to learn distance based metrics. Or if the paper is thoroughly proposing an intrinsic motivation method then the paper should discuss and compare to recent state-of-the-art intrinsic motivation methods like ICM or RND or even SMiRL.




Reference:
[1] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell.   Curiosity-driven Exploration by Self-498supervised Prediction. 2017
[2] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random networkdistillation.ICLR, 2018b
[3] G. Berseth,  D. Geng,  C. M. Devin,  N. Rhinehart,  C. Finn,  D. Jayaraman,  and S. Levine.377{SM}irl: Surprise minimizing reinforcement learning in unstable environments. InInternational378Conference on Learning Representations, 2021.

main_review: 

Additional comments on the paper:
- The work in this paper sounds very familiar to the state space covering paper [4] that also trained an objective function in order to have an agent minimize the distance between a type of distribution but in that case, the distribution was covering the entire State space.
- Section 2.1 is outlining previous methods and intrinsic motivation and ends with a sentence saying that the Wasserstein distance has been used before as a valid reward for imitation learning. This is making it sound like the use of this metric that's proposed in the paper is already been done in two previous works. It would be helpful if the authors could clarify these points by noting the differences between the new proposed method and those previous works.
- As the authors note, the Wasserstein distance may be more informative when distributions are disjoint, theoretically. It will be very important to be able to show in the paper that in practice the method proposed can perform much better than previous works [4] in this area that's solving a very similar problem. It would also be helpful to back up the claim online 97 stating that AIM might induce a form of directed exploration.
- In terms of the focus on the type of problems in the paper, it would be very helpful to understand the reasoning why problems on unrealizable target distributions that cannot be completely matched. Is this a common challenge in reinforcement learning that needs to be addressed and if it is addressed will assist in solving a number of problems that the community is interested in?
- The experiments in the paper describe how aim May speed up learning a policy towards a single goal. This makes one wonder whether or not the method in the paper can also speed up learning towards multiple goals and whether or not the single goal chosen has any particular biased towards the way AIM works. Were multiple goals evaluated in each of the environments in the experiments?
- It's not completely clear how figure 2 is showing that AIM enables the agent to reach the goal and learn the required policy quickly. To understand if it's learning a policy quickly it will need to be compared to some other method that is also plotting these types of details and state visitation distribution. It is hard to tell if the visualization for figure two really indicates how or what the agent has learned and what it should follow in order to help it get to the Target better. It almost seems like figure two a to a has learned a better State visitation distribution that will lead it more quickly to the goal?
- The results in figure 3 appear to be rather similar. Most of the methods seem to have very similar performance with the exception of reward plus HER. It would be beneficial to have results on additional environments to help readers understand what type of environments AIM will work best on. There are also comparisons to other aiAIM like methods that include RND [2] that would be helpful to compare to to make sure AIM is an improvement over the current state of the art.

If these issues area addressed I would consider updating my score.


[4] Lee, L., Eysenbach, B., Parisotto, E., Xing, E., Levine, S., & Salakhutdinov, R. (2019). Efficient exploration via state marginal matching. arXiv preprint arXiv:1906.05274.

--------- Post author response ----- 
I have updated my score to reflect clarifications from the authors.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proposes a method for goal-conditioned RL. The main idea is to learn a function that looks like a value-function and then use that value function as a reward function for RL. This method is motivated as minimizing a certain Wasserstein distance. Empirically, the proposed method outperforms goal-conditioned RL applied to sparse reward functions, and performs roughly on par with goal-conditioned RL with dense rewards. In effect, it seems like this learned value function can serve the role of the dense reward function.
main_review: **Originality**: The method proposed in this paper can be broken down into two main ideas: (1) a new method for learning a value-function-like term, and (2) a method for using that value function.

The first idea is (to the best of my knowledge) novel and fairly clever. The idea is to formulate goal-conditioned RL as minimizing a Wasserstein-1 distance between the state marginal distribution and some "target" distribution centered at the goal (sometimes a Dirac, sometimes a Gaussian). The Wasserstein-1 distance requires defining an underlying metric; the paper proposes to use the shortest path distance as a (quasi-)metric. Cleverly, the paper shows how the dual form of the Wasserstein allows one to estimate the Wasserstein distance without being about the compute the shortest path distance (which, in general, is as difficulty as solving the goal-conditioned RL problem).

The second idea (using a value-function like term) is not novel. While the paper does not claim this to be a contribution, I'd recommend citing some prior work that employs the same idea (e.g., see [Hartikainen '19, Tian '20] or other prior work on using terminal value functions).

**Quality**:

While I'm not an expert on the Wasserstein distance, the derivation of the proposed method seems correct to me. However, the resulting method for learning the value function (Eq. 8) is almost exactly the same as standard temporal difference learning, which is *already* used by standard goal-conditioned RL methods. Precisely, temporal difference learning with the -1/0 reward can equivalently be viewed as solving a constrained optimization problem where (1) the goal state has value 0, (2) the difference between the values of consecutive states is less than 1, and (3) the value of all states is minimized. I suspect that Eq. 8 is equivalent to some linear-program formulation of the RL problem (see the Puterman MDP book). In summary, the resulting method bears a very close resemblance to (1) learning a value function and (2) using that value function as a reward function. This connection is useful because it not only explains what the "adversarial intrinsic motivation function" is (a value function, up to an additive constant), but also offers a potentially better way to learn it (using Monte Carlo regression instead of TD learning). I would highly encourage the authors to compare against this baseline (both with a value function learned via MC regression as in Eq. 3 of [Hartikainen '19]) and via TD learning (similar to Eq. 8 of this paper)).

Notwithstanding the results of this experiment, the idea that TD learning is equivalent to minimizing a Wasserstein-1 distance seems pretty cool! I'm not sure how this can be made into a practically useful insight.

Some additional comments about the analysis:
* It could be worth noting that the proposed objective is actually quite similar to C-learning [Eysenbach '20]. While C-learning minimizes a KL divergence with the goal distribution, the proposed method minimizes a Wasserstein-1 distance. After mentioning this connection, the authors could bring up the point about KL divergences not being informative for distributions with disjoint suppoer (perhaps adding another sentence (e.g., similar to the W-GAN paper) to build intuition.
* While the proposed method is derived for discrete-state MDPs, it is later applied to continuous state MDPs. I'd recommend including a sentence to explain that these experiments do not match theory (e.g., "Our experiments on simulated robotics tasks highlight that the method continues to work, even in settings with continuous states and actions, where our theory does not apply.").
* The discussion of variance in Sec 5.1 is reminiscent of risk-sensitive control (e.g., [Mihatsch '02]). This raises the question: if risk-sensitivity (i.e., minimizing variance) is important, why don't we just use a standard risk-sensitive objective (e.g., $\min \log E[T]$)?

A few questions for the authors:
1. In the robotic control tasks, it seems like the dense reward (a negative L2 distance) is equivalent to using the log probability of the target density (a Gaussian) as the reward. How is this different from what DiscoRL [Nasiriany '20] does. (If so, I'd recommend highlighting this connection, as it makes the comparison with dense rewards seems less like an "oracle" experiment and more like a prior method.)
2. Can the Wasserstein distance (Eq. 2) be expressed in terms of the expected time to reach the goal, or the probability of reaching the goal (i.e., without the bounds discussed in Sec 5.1)? Such a connection would help me gain intuition for exactly what the proposed method is optimizing.
3. If the optimal transport plan/coupling (L155) where known, are the clear ways that one could use it? Would it correspond to the optimal policy?


**Clarity**:

Generally, the paper was clearly written. For me, the most confusing part was the discussion of the Wasserstein metric. I think the confusion was in introducing the notion that the Wasserstein metric requires defining another metric function. I was also confused about whether the choice of this metric function was a design decision or was motivated by theory. Please see the minor comments at the end of the review.

**Significance**:

The idea that temporal difference learning is (approximately?) minimizing a Wasserstein metric seems potentially impactful, even if it doesn't immediately provide better algorithms for goal-conditioned RL. I don't think the actual method proposed will be impactful because (1) it seems nearly the same as prior methods that use a value function as a reward function, (2) the connection between the function $f(s)$ and standard quantities in RL (e.g., value functions) is unclear (but this could be easily corrected), and (3) the proposed method barely outperforms a simple baseline that uses a negative L2 distance as a reward function.

Minor comments:
* L59 - L60 -- If the policy minimizing the expected number of steps, then wouldn't such a policy also be optimal for stochastic dynamics?
* L69 - L70 -- This is a great introduction sentence!
* L87 -- Perhaps also discuss [Hartikainen '19].
* L120, L121 -- I was initially a bit confused what the notation "$\rho: \Delta (S)$" and "$\sigma: \Delta (G)$" meant.
* L129 -- I'd recommend stating $r(\bar{s}) = 1$ in math, too.
* L135 -- The three expectations could be combined into a single expectation.
* L184 "Definition 1" -- I found this definition pretty confusing, and would recommend cutting it and directly defining $d(s, s_g)$ using the equation after L193.
* L193 -- This equation raises an obvious question: Why not just use $T$ as a reward function? This question is only answered much later. I would recommend answering it immediately after defining $T$.
* L164 - L197 -- None of this material is novel. I'd recommend moving it to a new paragraph in Section 3.1 and just citing [Kaelbling '93].
* Eq 3 -- This idea is really clever! I'd highly recommend adding a few more sentences (and perhaps an illustration) to explain it.
* L207 - L208 -- I found this sentence confusing.
* L212 -- The importance of Proposition 1 is a bit unclear. I'd recommend moving it to Sec 5 (which focuses on analysis) and providing examples of settings where the inequalty is and is not tight.
* Sec. 5.1 -- The importance of this section is a bit unclear to me. The result I was expecting was that minimizing the proposed Wasserstein metric corresponds to minimizing expected hitting time. Unless the analysis shows this, I'd recommend moving all of Sec. 5.1 to the appendix.
* L240 "Adversarial Intrinsic Motivation" -- I found the term "intrinsic motivation" a bit confusing because it's often used in settings without clear objectives (in contrast, this paper is optimizing a very well defined objective). I'd recommend renaming it something like "Learning a Value Function to Minimize the Wasserstein-1 Distance".
* L244 "even if the ground metric" -- This point seems really important! I'd recommend bringing it up (or at least foreshadowing it) when "T" is first defined in L193.
* Fig 3: Please make this figure colorblind friendly.

-----------------------------
**Review decision**: Overall, I really like the idea of viewing goal-conditioned RL as a distribution matching problem and the idea of using Wasserstein duality to learn a value function. The paper clearly shows that this perspective yields good results on goal-conditioned RL problems. My main concern with the paper is its relationship with prior work, both empirically and theoretically. Empirically, it seems like the proposed method does not perform as well as "HER + dense", which I understand to be an instance of prior work [Disco RL applied to a Gaussian target distribution]. I would also recommend comparing against a baseline that learns a value function (either via TD learning or MC regression, as explained above) and uses that value function as a reward function. Theoretically, I'd highly recommend examining and explaining the connection between the adversarial function $f$ and temporal difference learning. Given these concerns, I vote to reject the paper.

**Update after discussion**: The additional experiments and clarifications provided during the rebuttal period have addressed by concerns, and I have changed my vote to "accept".


limitations_and_societal_impact: The paper discusses limitations and potential broader impacts in the concluding section. I found this section a bit vague, and think it could be shortened and made more concise.
review_title: null

Meta-review: This paper presents an elegant idea and a fine investigation -- an important contribution to the community. After clarifications made by the authors, all reviewers agreed that this paper should be accepted. 
When preparing the final version, please make sure to address the reviewers' feedback.
Decision: Accept (Poster)