We humans have an innate understanding of the asymmetric progression of time, which we use to efficiently and safely perceive and manipulate our environment. Drawing inspiration from that, we approach the problem of learning an arrow of time in a Markov (Decision) Process. We illustrate how a learned arrow of time can capture salient information about the environment, which in turn can be used to measure reachability, detect side-effects and to obtain an intrinsic reward signal. Finally, we propose a simple yet effective algorithm to parameterize the problem at hand and learn an arrow of time with a function approximator (here, a deep neural network). Our empirical results span a selection of discrete and continuous environments, and demonstrate for a class of stochastic processes that the learned arrow of time agrees reasonably well with a well known notion of an arrow of time due to Jordan, Kinderlehrer, and Otto (1998).
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.