Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes that we learn the “arrow of time” for an MDP: that is, a function (called the h-potential) that tends to increase as the MDP steps forward. Such an arrow should automatically capture notions such as irreversibility, and so can be used to define a measure of reachability, which previous work has shown can be used to penalize the agent for causing negative side effects. In addition, it can be used as intrinsic motivation for the agent: in particular, the agent can be rewarded for trajectories that decrease the h-potential (i.e. are “like” going backwards in time, or reducing entropy), which is hard to do and should lead to interesting skills. They propose that we learn the arrow of time by optimizing a function to grow over time along trajectories take from a random policy. Experiments demonstrate that in simple environments the learned function has the properties we would expect it to given results from physics.

I am conflicted on this paper. I like the novelty of the suggestion; it is not something I would have expected to see in an ML paper. The discussion and experiments have convinced me that the idea is worth investigating: they show that the learned arrow of time approximately satisfies the properties we would expect, and demonstrate their two use cases in two simple environments: the intrinsic reward is used in a tomato-watering environment, while the side effect avoidance is shown in Sokoban (though the experiment only shows that the h-potential increases with irreversible actions -- it doesn’t actually use the h-potential to create an agent that reliably avoids irreversibly pushing boxes into corners). However, it’s not clear to me whether or not the method would scale to more complex environments, the current experiments are more like demonstrations (there are no baselines), and the paper is hard to understand without a background in physics. Overall, given the novelty of the suggestion, I lean towards a weak accept.

----

In your objective, you use an expectation over the timestep in the trajectory. Why not instead take an average over all the timesteps in the trajectory? This should be equivalent. (If trajectories are all the same length, you could also take a sum over the timesteps.) Similarly, in the algorithm, why do you sample from the dataset? It would likely be better to randomly shuffle the dataset (at the timestep level) once, and then iterate through the dataset computing gradient updates. (This is standard practice in supervised learning.)

----

When scaling the algorithm up to larger environments, you will likely run into the problem that uniform policies are often very bad at exploring the state space. Consider for example the Overcooked environment (https://bair.berkeley.edu/blog/2019/10/21/coordination/ ). The environment is not dissipative, so you’d expect the h-potential to be zero. However, uniform policies are extremely unlikely to ever deliver a soup (which requires several hierarchical actions), but sometimes will pick up an onion. If you don’t know about soup delivery, then picking up an onion looks irreversible, because there’s no way to get rid of it, and the h-potential will rise. I think it would significantly improve this paper to demonstrate a solution to this problem.

One possibility is to redefine the arrow of time to be with respect to some distribution over states: E_{s ~ p(s)} E_{a ~ Uniform(A)} E_{s’ ~ p(s’ | s, a)} [ h(s’) - h(s) | s ]. Initially, your distribution over states can be the initial state distribution. But then you can use the learned arrow of time as an intrinsic reward to find a policy that finds “interesting states”. In Overcooked, we would hope that this policy learns to pick up onions. Then, your new distribution over states can be the states reached in 0-20 timesteps when following the new policy, that is, you collect your dataset by running the “interesting” policy for some time, and then switch back to the uniformly random policy, and only use the states / actions collected during the uniform random policy as part of your dataset. Hopefully, this would include states where the onion is placed in a pot, and the h-potential would learn that placing an onion in a pot is “irreversible”. Then, another round of using the h-potential would lead to a policy that places onions in pots. Collecting data could then discover delivering soups, and so on.

----

In addition to experiments on larger environments, I would like to see better experiments for the two intended use cases. For example, can you use the learned arrow of time to solve the environments in (Krakovna et al), and how does it compare to relative reachability and its many variants? Similarly, how does your intrinsic reward compare to existing exploration methods (of which there are many, but consider count-based methods, curiosity (Pathak et al), random network distillation (Burda et al))?

----

(This section did not affect my assessment of the paper)
 
Have you considered finding theoretically what it means to take the difference between the h-potential of two states (i.e. your reachability measure)? I could imagine that the answer is something like “reachability(s, s’) is proportional to the log probability of reaching s’ from s when acting according to a uniformly random policy”. Perhaps this has to be normalized against the log probability of reaching other states from s. This would be very interesting as a potential definition of reachability.

----

There is a lot of jargon from physics that will not be familiar to the typical audience at ICLR (e.g. Hamiltonian, Liouville’s theorem, Maxwell’s demon, free energy functionals, etc.) I would recommend improving the clarity of the paper on this axis. There’s no particular need to name Maxwell’s demon prominently -- the exposition is sufficient by itself, perhaps Maxwell’s demon can be mentioned in a footnote. Consider adding a discussion of ergodicity (as applied to Markov chains / MDPs), which will be more familiar to the audience and serves a similar purpose as the discussion on Hamiltonian systems. Perhaps move the experiment with the free energy functional to the appendix, and move the experimental details for the other experiments from the appendix to the main paper.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: The paper draws on a wide range of ideas, and proposes novel perspectives on how these ideas might apply in RL.  In particular, the concept of reachability, reversability and dissipation are explored, with respect to properties of the underlying MDP that can be exploited.

I found many of the ideas thought-provoking. The paper is also well written and a pleasure to read.

But unfortunately the work falls short of its objective in the experiment section.  Not a single baseline is included.  I would expect to see comparison to a simple model-based method for all the experiments on p.7.   The main result for 7x7 2D world seems to be that the agent has learned to quantify irreversibility.  I would expect a simple statistical estimator over state transitions (using the same samples as the h-potential method) to be able to capture this as well.  The main result for Sokoban seems to be that the h-potential has detected side-effects of actions; again, why can’t a model estimator learn this?  Similarly in Mountain car, it seems possible to directly estimate the terrain from the data, without the h-potential. 

As a more minor concern, the fact that the method uses a batch of uniformly random state transitions (as per Sec.4), rather than randomly sampled trajectories is a definite concerned with respect to real-world application.

Minor comments:
-	Top of p.3: Can you give some intuition for h(), e.g. relation to entropy over trajectory.
-	Bottom of p.3: you use a random policy to sample trajectories. Is this simple to implement? Can you just sample random actions at each state, or do you need to sample over the space of all trajectories?
-	Footnote 2, p.4.  It would be interesting to expand on this point.

==============
Update post-rebuttal:
Indeed, my concern is that a simple T(s,a,s') estimator, using the same samples, could infer the same characteristics in each of the experiments (number of broken vases; effect of box pushing; terrain), and could then be used for model-based planning.
But I do appreciate the insights provided by connecting these through the broader notion of arrow of time developed in this paper, and its connection to reachability and safety.   Therefore I am raising my score to weak accept.
review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: This work proposes the h-potential, which is a solution to an objective that measures state-transition asymmetry in an MDP. Roughly speaking, in many situations some state transitions (s-->s’) are more probable than their converse (s’-->s), and if we have a function that assigns a higher value to a more probable transition (compared to its converse), then we can use it as a measure of the “reversibility” of that transition. This function can then be used, for example, as an intrinsic reward signal; indeed, there may be cases where state transitions should be avoided if they are not reversible. 

The authors tie these ideas into the notion of the arrow of time. They go on to explore the various nuances and subtleties of this measure, and demonstrate its behaviour empirically on a number of environments.

This paper was an absolute pleasure to read. The prose was clear, interesting, and nuanced. The authors anticipate many questions and do well to explain the various subtleties of their method. Overall the experiments are a nice demonstration of the presented ideas.

I am inclined to give this paper a high rating, as there was very little that I felt was “wrong” or inaccurate. But I must also admit that some of the theoretical components are beyond my expertise, and so I can only be moderately confident. I will defer to other reviewers and any online discussion on these more technical matters.

I have a few questions that I hope the authors can address.

1) The method depends on a random policy (or, more accurately, was empirically validated mainly using a random policy, aside from some very simple environments as far as I can see). Can the authors comment on the usefulness of this method for a non-random policy in more complicated environments? Do they have any experimental results showing the effect of incorporating this into an agent also receiving (and learning from) exogenous rewards in an environment such as Sokoban (as it’s used here already) or Atari? 

2) Related to the first point, how does this method scale to environments whose state-space can only be sparsely covered with a random policy? It seems in this case a task-relevant policy would be needed to explore more of the state-space, which would place pressure on the h-potential function approximator as it has to learn with sequentially correlated inputs. You can imagine something like an experience replay buffer being needed, but in any case, there are definitely unique challenges here not explored in the paper.

3) Can the authors comment on the notion of a function being statistically monotonic vs. deterministically so, and whether the arrow of time is classically considered the former or the latter? My reasoning for this question comes from a place where I’m questioning whether the motivation of the work can be simplified. The appeal to the arrow of time is nice and reads well, but it’s also the case that this work can simply be interpreted as “learned state transition reversibility”, with the links to the arrow of time being more of a point of discussion.

review_title: Official Blind Review #1

Meta-review: This paper develops the notion of the arrow of time in MDPs and explores how this might be useful in RL. All the reviewers found the paper thought provoking, well-written, and they believe the work could have significant impact. The paper does not fit the typical mold: it presents some ideas and uses illustrative experiments to suggest the potential utility of the arrow without nailing down a final algorithm or make a precise performance claim. Overall it is a solid paper, and the reviewers all agreed on acceptance.

There are certainly weaknesses in the work, and there is a bit of work to do to get this paper ready. R2 had a nice suggestion of a baseline based on simply learning a transition model (its described in the updated review)---please include it. The description of the experimental methodology is a bit of a mess. Most of the experiments in the paper do not clearly indicate how many runs were conducted or how errorbars where computed or what they represent.  It is likely that only a handful of runs were used, which is surprising given the size of some of the domains used. In many cases the figure caption does not even indicate which domain the data came from. All of this is dangerously close to criteria for rejection; please do better.

Readability is also known as empowerment and it would be good to discuss this connection. In general the paper was a bit light on connections outlining how information theory has been used in RL. I suggest you start here (http://www2.hawaii.edu/~sstill/StillPrecup2011.pdf) to improve this aspect. Finally, the paper has a very large appendix (~14 oages) with many many more experiments and theory. I am still not convinced that the balance is quite right. This is probably a journal or long arxiv paper. Maybe this paper should be thought of as a nectar version of a longer standalone arxiv paper.

Finally, relying on effectiveness of random exploration is no small thing and there is a long history in RL of ideas that would work well, given it is easy to gather data that accurately summarizes the dynamics of the world (e.g. proto-value, funcs). Many ideas are effective given this assumption. The paper should clearly and honestly discuss this assumption, and provide some arguments why there is hope.
Decision: Accept (Poster)