Learning the Arrow of Time for Problems in Reinforcement Learning
Authors: Nasim Rahaman
Steffen Wolf
Anirudh Goyal
Roman Remme
Yoshua Bengio
Venue:  (2020)
Keywords: Arrow of Time
Reinforcement Learning
AI-Safety

Abstract: 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). 

Published as a conference paper at ICLR 2020
LEARNING THE ARROW OF TIME FOR PROBLEMS IN REINFORCEMENT LEARNING
Nasim Rahaman 1,2,3 Steffen Wolf' Anirudh Goyal
Roman Remme'
Yoshua Bengio
1 Image Analysis and Learning Suprecht-Karl-UUnivee Heidelberg
"Max-Planck Institute for Intelligent Systems, Tübingen
3 Mila, Montréal
*CIFAR Senior Fellow
5 Canada CIFAR Al Chair
ABSTRACT
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, 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, propose simple yet effective algorithm parameterize the problem at hand and learn an arrow of time with a function approximator (here, a deep neural network). Our empirical results span 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).
INTRODUCTION
The asymmetric progression of time has profound effect on how we, as agents, perceive, process and manipulate our environment. Given sequence of observations of our familiar surroundings (e.g. as video frames), we possess the innate ability to predict whether the said observations are ordered correctly. We use this ability not just to perceive, but also to act: for instance, we know to be cautious about dropping a vase, guided by the intuition that the act of breaking a vase cannot be undone. This profound intuition reflects some fundamental properties of the world in which we dwell, and this work we ask whether and how these properties can be exploited to learn a representation that functionally mimics our understanding of the asymmetric nature of time.
The term Arrow of Time was coined by the British astronomer Eddington (9929) to denote this inherent asymmetry, which he attributed the non-decreasing nature of the total thermodynamic entropy of an isolated system, as required by the second law of thermodynamics. Since then, the notion of arrow of time has been formalized and explored in various contexts, spanning not only physics, but also algorithmic information theory (Zurek) 1989). causal inference (Janzing et al. 2016) and time-series analysis (Janzing 20T0 Bauer al. 2016).
Broadly, an arrow of time can be thought of as function that monotonously increases as a system evolves in time. Expectedly, the notion of irreversibility plays central role the discourse. sta- tistical physics. it is posited that the arTow of time (i.c. entropy production) is driven by irreversible processes (Prigogine 1978 Seifert 2012). To understand how a notion of an arrow of time can be useful in the reinforcement learning context, consider the example of cleaning robot tasked with moving a box across a room (Amodei et al. (0166). The optimal way of successfully completing the task might involve the robot doing something disruptive, like knocking vase over (Fig Now on the one hand, such disruptions or side-effects - might be difficult to recover from. In the extreme case, they might be virtually irreversible say when the vase is broken. On the other hand, inre- versibility implies that states with a larger number of broken vases tend to occur in the future, and one should therefore expect an arrow of time (as scalar function of the state) assign larger values

---

Published as a conference paper at ICLR 2020
Figure I: The agent (in orange) is tasked with reaching its goal, the checkered flag (middle frame). It may take the shorter path (right frame), which entails breaking the vases in its way, it may prefer the safer path (left frame) which longer but keeps the vases intact. The former path irreveriibl,, and the initial state unreachable from final state (red arrow). On the contrary, the latter path completely reversible, and the initial state remains reachable from the final state. Now, an arrow of time (pink) measures the disorder, which might help safe agent decide which path to take.
to states with larger number of broken vases. An arrow of time should therefore quantify the amount of disorder in the environment, analogous the entropy for isolated thermodynamical systems.
Now, one possible application could be to detect and preempt such side-effects, for instance by penalizing policies that significantly increment the arrow of time by executing difficult-t--revens' transitions. But the utility of an arrow of time is more general: it serves as a directed measure of reachability. This can be seen by observing that it is more difficult to obtain order from disorder: it is, after all, difficult to reach state with vase intact from one with it broken, rather than vice versa. In this sense, we may say that state relatively unreachable from another state if an arrow of time assigns a lower value to the former. Further, directed measure of reachability afforded by an arrow of time can be utilized for deriving an intrinsic reward signal to enable agents to learn complex skills in the absence of external rewards. To see how, consider that an agent tasked with reversing the arrow of time (by creating order from disorder) must in general learn complex skills to achieve its goal. Indeed, gluing together broken vase will require the agent to learn an array of complex planning and motor skills, which is the ultimate goal of such intrinsic rewards.
In summary, contributions the following. (a) We propose simple objective to learn row of time for a Markov (Decision) Process in a self-supervised manner, i.e. entirely from sampled environment trajectories and without external rewards. We call the resulting function (acting on the state) the h-potential, and demonstrate its utility and caveats for a selection of discrete and contin- uous environments. Moreover, we compare the learned h-potential to the free-energy functional of stochastic processes- - the latter being a well-known notion of an arrow of time (Jordan et al.) 1998). While there exist prior work on detecting the arrow of time in videos (Pickup et al.] 2014] Wei al,, 2018) and time- series data (Peters et al.] 22099; Bauer et al. 2016). we believe our work to be the first towards measuring it in the context of reinforcement learning. (b) We critically and transparently discuss the conceptually rich subtleties that arise before an arrow of time can be practically useful in the RL context. (c) We expose how the notions of reachability, safety and curiosity can be unified under the common framework afforded by learned arrow of time.
2 THE h-POTENTIAL
Motivated by the preceding discussion, our goal to learn function that quantifies the amount of disorder in given environment state, where we say that irreversible state transitions increase disorder. In this sense, we seek a function (of the state) that constant expectation along fully reversible state transitions, but increase in expectation along state transitions that are less reversible. To that end, we begin by formally introducing this function, which we call the h-potential, as the solution to functional optimization problem. Subsequently, critically discuss few conceptual roadblocks that must be cleared before such a function can be useful the RL setting.
2.1 FORMALISM
Consider Markov Decision Process (a MDP, i.e. environment), and let S and A be its state and action spaces respectively. A policy æ is a mapping from the state space to the space of distributions over actions. Given state E S sampled from some initial state distribution Po. we may sample
2

---

Published as a conference paper at ICLR 2020
an action E A from the policy a[als), which in turn can be used to sample another state s' E S from the environment dynamics p(s' a. s). Iterating N more times for a fixed n, one obtains a sequence of states (Sp, ... Sts ..., 8x ). which is realization of the Markov chain (a trajectory) with transition probabilities P= (8 (8c) = Eas p(8++1 18t, a) a)r((a(s)) We may now define a function
h S R as the solution to the following functional objective:
In [b] (B.-U((O....NII))) Bess (+(411))))) h()))l+)) + XT
1i = arg max Jx [7c] (1)
where U(A) is the uniform distribution over any set A, A, Bs, Bec is the expectation over all state transitions, a scalar coefficient and T(A] is regularizing term that prevents h from diverging within finite domain. In words: the first term the right hand side of the first equation above encourages hgg to increase in expectation along the sampled trajectories, whereas the second term controls this increase; the two terms are balanced with coefficient A. Informally: if state transition 8 + s' is fully reversible, the probability of sampling it equals that of sampling the corresponding reverse transition, s' -> s. For such transitions, the pressure on h to increase along the forward transition (s + s') is compensated by the counter-pressure for it to increase along the reverse transition (s' + s), or equivalently, decrease along the forward transition. Along such transitions, we should therefore expect 7 to remain constant (in expectation). Accordingly, if the forward transition were to be more likely (i.e. if the transition is not fully reversible), we should expect h to increase (in expectation) in order to satisfy its objective.
The regularizer T must be chosen to suit the problem at hand, and different choices result in solutions that have different characteristic[] Possible choices for 'I include (any combination of) the negative of L2 norm -11/l12. and/or the following trajectory regularizer:
Thh- EE.. E,, Il [1((s++1) - 11ss
(2)
Intuitively: while the solution h is required to increase in expectation along trajectories, the trajec- tory regularizer acts an contrastive term by penalizing h, for changing at all.
With some effort, the problem defined in Eqn ! can be approached analytically for toy Markov chains (interested readers may refer to App A for technical discussion). However, such analytical treatment becomes infeasible for more complex and larger-scale environments with unknown tran- will cast the functional optimization problem
sition probabilities. To tackle such environments, in Equ to an optimization problem over the parameters of a deep neural network and solve it for a variety of discrete and continuous environments.
2.2 SUBTLETIES
In this section, we discuss two conceptually rich subtleties that determine the conditions under which the learned arrow of time (h-potential) can be useful in practice.
The Role of a Policy. The first subtlety is rooted in the observation that the trajectories (sa, .... $y) are collected by a given but arbitrary policy. However, there may exist policies for which the re- sulting arrow of time unnatural, perhaps even misleading. Consider for instance the actions of practitioner of Kintsugi, the ancient Japanese art of repairing broken pottery. The corresponding policy? Daiihy cause the environment to transition from a state where the vase broken to one where it is not. If we learn the f-- h--otennial on such trajectories, it might be the case that counter our in- tuition, states with larger number of broken vases are assigned smaller values (and the vice versa). Now, one may choose to resolve this conundrum by defining:
Jhh = (n
where II is the set of all policies defined on S, and U (II) denotes a uniform distribution over II. The resulting function h- arg max{ - XT [h]} would characterize the arrow of time with respect to all possible policies, and one would expect that for vast majority of such policies, the transition from broken vase to intact vase is rather unlikely and/or requires highly specialized policies.
I "This not unlike the case for linear regression: for instance, using Lasso instead of ridge-regression will generally yield solutions that have different properties. "his analogous Maxwell's demon in classical thermodynamics.
3

---

Published as a conference paper at ICLR 2020
Unfortunately, determining ht' is not feasible for most interesting applications, given the outer pectation over all possible policies. As a compromise, we use (uniformly) random actions to gather trajectories. The simplicity of the corresponding random policy justifies its adoption, since one would expect a policy resembling (say) a Kintsugi artist to be rather complex and not implementable with random actions. In this sense, ensure that the learned arrow of time characterizes the un- derlying dynamics of the environment, and not the peculiarities of a particular agen(") The price we pay the lack of adequate exploration in complex enough environments, although this problem plagues most model-basee reinforcement learning approache (cf. |Ha & Schmidhuber (2018)). In the following, we assume π to be uniformly random and use h interchangeably with h.
[
Dissipative Environments. the arrow of time is informative. To illustrate the matter, consider the class of system a typical instance of which could be a billiard ball moving on a frictionless arena and bouncing (elastically) off the edges (Bunimovich] 2007). The state space comprises the ball's velocity and its position constrained to billiard table (without holes!), where the ball is initialized at random position on the table. For such a system, it can be seen by time-reversal symmetry that when averaged over large number of trajectories, the state transition s' + s. In this case, recall that the arrow of time is expected to remain constant. A similar argument can be made for systems that identically follow closed trajectories in their respective state space (e.g. a frictionless and undriven pendulum). It follows that the /1-potential must remain constant along the trajectory and that the arrow of time is uninformative. However, for so-called dissipative systems, the notion of an arrow of time is pronounced and well studied (Willems 1972. Prigogine 1978).
The second subtlety concerns what we require of environments in which
s' is just as likely as the reverse transition
In MDPs, dissipative behaviour may arise in situations where certain transitions are irreversible by design (e.g. bricks disappearing in Atari Breakout), or due to partial observability, e.g. for damped pendulum, the state space does not track the microscopic processes that give rise to friction [ Therefore, central premise underlying the practical utility of learning the arrow of time is that the considered MDP is indeed dissipative, which we shall assume in the following; in See 5 (Fig 5b). will empirically investigate the case where this assumption is violated.
3 APPLICATIONS WITH RELATED WORK
In this section, we discuss a few applications of the arrow of time, and illustrate how the /t-potentil provides a common framework to unify the notions of reachability, safety and curiosity.
3.1 MEASURING REACHABILITY
Given two states 8 and 8 in S, the reachability of s' from 8 measures how difficult it is for an agent state s reach state 8'. The prospect of learning reachability from frae-transition trajectories has been explored: in Savinov et al. (2018). the approach taken involves learning a logistic regressor network g" : S x S + [0, 1] to predict the probability of states s' and s being reachable one another within certain number of steps (of a random policy), in which case g(s, s') ~ 1. However, the model g not directed: it does not learn whether
more likely to follow s, or the vice versa. Instead, our proposal is to derive a directed measure of reachability from l-potential by defining function 1) : S S - IR such that 17,, 8') = 77(s + 8') == h(s²)= - hss), where 1/(8- - 8') measures the reachability of state s' from state This inductive bias on 17 (in form of a functional constraint) induces the following useful propertics.
First, consider the case where the transition between states and s' is fully reversible, i.c. when state s is exactly as reachable from state s' as is s' from s; we denote such transitions with s ++ s'. Now, in expectation, we obtain that h(s') h(s) and consequently, 77s - s') ry(s' + s) 0. But if instead the state s' is more likely to follow state s than the vice versa (in expectation over trajectories), we say s' is more reachable from s than the vice versa. It follows in expectation that
'What we do is similar (in spirit) to inverse reinforcement learning the reward function maximized by a random policy (instead of an expert policy), cf. Ng & Russell (2000).
*While this is fundamental problem (Appl C.3). powerful methods for off- policy learning exist (sce Munos
al. (2016) and references therein); however, a full analysis is beyond the scope of the current work.
Precisely: Hamiltonian systems where Liouville's 's theorem holds and the Hamiltonian is time-independent.
In particular, abserve that dissipative system may or may not he ergodic.
4

---

Published as a conference paper at ICLR 2020
h(s') h(s), and consequently, n7ss - 8 > 0. Now the inductive bias on yf as a difference of h-potentials automatically implies 17(55' + s) = (7 - s') < O.
Second, observe that the reachability measure implemented by is additive by construction: given a trajectory 5o + $1 - $2, we have that 17 - 522 = 5 + 51) + ( + 82). As a special case, if we have that 8o ++ $1 and 81 82 -i.e. if (550 - 81) nys1 + 82) = 0- it identically
follows that Sn <> $2, i.e. 17(50 + $2) = O. In this case, the inductive bias enables v) to generalize to the transition so ++ 82 even if never explicitly sampled by the policy.
Third, v allows for a soft measure of reachability. It measures not only whether a state s is reachable from another state 8, but also quantifies how reachable the former is from the latter. As example, consider a trajectory $o 7 $1 + + $100. where the agent breaks one vase at every state transition. If the h-potential increases in constant increments for every vase broken (which we confirm it does in Se we obtain due to the inductive bias that 17(so - $100) = 100 (780 + 81). This behaviour sought-after in the context of AI-Safety (Krakovna et al. 2018 Leike et al. 2017).
Nonetheless, one should be careful when interpreting 1). While the above implies that 17(5' + 5) = 11s - s') if the transition between states and is fully reversible, the converse can only be guaranteed if the Markov process admits trajectory between and s' in either direction, i.e. if there exists a trajectory that visits both s and s' (in any order). Observe that this condition much weaker than ergodicity, which requires that the Markov process admit trajectory from any given state to all other states s', In fact, the discrete environments we investigate in Sec 5 are non-ergodic.
3.2 DETECTING AND PENALIZING SIDE EFFECTS FOR SAFE EXPLORATION
The problem of detecting and avoiding side-effects is well known and crucially important for safe exploration (Moldovan & Abbeel 2012 Eysenbach et al.. 2017 Krakovna al., 2018 Armstrong & Levinstein (017). Broadly, the problem involves detecting and avoiding state transitions that permanently and irreversibly damage the agent the environment (Leike et al.) (017). As such, it is fundamentally related to reachability, as in the agent is prohibited from taking actions that drastically reduce the reachability between the resulting state and some predefined safe state. In Eysenbach it al.] (2017), the authors learn a reset policy responsible for resetting the environment to some iniiill state after the agent has completed its trajectory. The resulting value function of the reset policy indicates when the actual (forward) policy executes an irreversible state transition, but at the cost of the added complexity of training a reset policy. In contrast, Krakovna et al. (2018) propose to attack the problem by measuring reachability relative to safe baseline policy- namely by evaluating the reduction in reachability of all environment states from the current state with respect to that from baseline state, where the latter is defined as the state that system would have (counterfactually) been in had the agent acted according to the corresponding baseline policy. However, determining the counterfactual baseline state requires a causal model of the environment, which cannot always assumed to be known.
We propose directly the reachability measure n) defined in Section 3.1 to derive reward term for safe-exploration. Let r. be some external reward at time-step t. The augmented reward is given by:
A r. 8 B max maxx(n(s-11 s.).0}
(4)
where 9 is a scaling coefficient. In practice, one may replace 17 with (n)). where is monotonically increasing transfer function (c.g. a step function). Intuitively, transitions s - s' that are less reversible cause the h-potential to increase, and the resulting reachability measure 17(s - s') is positive in expectation. This incurs a penalty (due to the negative sign), which is reflected in the value function of the agent. Conversely, transitions that are reversible should have the property that v1ss s²) = 0 (also in expectation), thereby incurring no penalty.
3.3 REWARDING CURIOUS BEUIVIIOR
In most reinforcement learning applications, the reward function is assumed to be given; however, shaping a good reward function can often prove to be a challenging endeavour. It is in this context that the notion of curiosity comes to play important role (Schmidhuber 2010 Chentanez et al. 2003 Pathak et al.) 2017] Burda et al., 2018 (Savinov et al.) 2018). One typical approach towards encouraging curious behaviour is to seek novel states that surprise the agent (Schmidhuber 2010
5

---

Published as a conference paper at ICLR 2020
Pathak al. 2017 Burda et al., 2018) and use the error in the agent's prediction of future states is used as a curiosity reward. This approach is however known to be susceptible to the so-called noisy-TV problem, wherein an uninteresting source of entropy like noisy-TV can induce large curiosity bonus because the agent cannot predict its future state, [Savinov et al. (2018) propose to circumvent the noisy-TVV problem by defining novelty in terms of (undirected) reachability, wherein states that are easily reachable from the current state are considered less novel.
The h-potential and the corresponding reachability measure Y/ affords another way of defining curiosity reward. Say an agent's policy samples a trajectory from state to s'. Now, recall that 7(s + s') takes positive value if state s' is reachable from (with respect to simple reference policy); we therefore encourage the agent policy to sample trajectories where the 17(s + s') is negative, i.e. where s' is less reachable from 8. doing so, we encourage the agent to seek states that are otherwise difficult to reach just by chance, and possibly learn useful skills in the process. In other words, we reward the agent for reversing the arrow of time (recall that r7(s -> 8') < implies h(s') h(s)). The general form of the corresponding reward is given by:
f (1 + 8t)
(5)
While the above is independent of the external reward function defined by the environment, the lat- ter might often align with the former: in many environments, the task at hand is reach the least reachable state. This is readily recognized in classical control tasks like Pendulum, Cartpole and Mountain-Car, where the goal state often the least reachable. However, if the environment' 's spec- ified task requires the agent to inadvertently execute irreversible trajectories, it is possible that our proposed reward is less applicable. Furthermore, while the proposed curiosity reward encourages the agent to reach for difficulttt--reach states, it need not provide an incentive to seek out diverse states. In other words: an agent optimizing the proposed reward may seek out the most sefficult-to-raaee states, but ignore other interesting but less difficult-o-reaach states in the process (cf. App
To summarize, we used the h-potential to define a directed measure of reachability (Sec (Sec..1). which then naturally lead to two applications. In the first (Sec 3.2), we obtained a safety penalty by essen- tially discouraging the agent from increasing the h-potential by executing difficult-to-reverse transi- tions. In the second (Sec 3.3), argued that encouraging the agent to decrease the h-potential can provide an useful curiosity (intrinsic) reward signal in the absence of external rewards. In this sense, have illustrated how the framework of learned arrow of time (i.e. the /--ptential) unifies the notions of reachability, safety, and curiosity.
4 ALGORITHM
In Sec [ we proposed a general functional objective, and defined the h-potential as the solution to the corresponding functional optimization problem. While the problem could be approached analytically with some effort for certain toy Markov chains (see App A). complex environments with unspecified dynamics require fundamentally different approach. We therefore convert the functional optimization problem in Eqn [ (right) to one over the parameters O of a deep neural network he to obtain the following surrogate problem:
f = arg max
[E 8
Easrale (80(1))))) - (s))) + Xh
(6)
where π is a reference policy, i.c. uniform random, and we denote the solution hgg by h. To train the network, the expectations are replaced by their sample estimates. As for the regularizer, recall that its purpose was to prevent h from diverging within finite domain this can be achieved by a loss term T (like the trajectory regularizer in Eqn 2 or by training constraint like early stopping.
The training algorithm is rather straightforward and can be summarized as follows (please refer to App B for the full algorithm). We first use an offline reference policy (uniform random, in our experiments) to sample trajectories from the environment. Next, we sample a batch of uniformly random state transitions and evaluate the objective in Eqn 6 (by replacing expectations by their sample estimates). We regularize the either by adding the trajectory regularizer to the objective or by using early stopping to terminate the training after a fixed number of iterations. Finally, optimize the parameters 0 of hi maximize the objective hand.

---

Published as a conference paper at ICLR 2020
35,000
15
[Potental Difference
25.000
20000
I-Potential
15,000
10000
5.00
MMM
60 <[Timestep]
120
50
100
350
200
250
Timestap
The potential difference (i.c, change in potential) between consecutive states along a trajec- tory the Vaseworld (2D world) environment. The dashed vertical lines denote when vase is broken. Gist: the le-pttnniall increases step-wise when the agent irreversibly breaks a vase (corresponding to the spikes), but remains constant as it reversibly moves about. Further, the spikes all of roughly the same height, indicating that the h-potential has learned to measure inreersiiilitty by counting the number of de- stroyed vases.
Figure 2:
Figure 3: The h-potential along a trajectory from a random policy, annotated with the corresponding state images the Sokoban (2D world) environment. white sprite corresponds to the agent, orange to a wall, blue to a box and green to a goal. Gist: the h- potential increases sharply as the agent pushes a box against the wall. While it may decrease for given trajectory (in this because the agent manages move a box away from wall), increases in ex- pectation over all trajectories (cf. Fig 14in Appendix
5 EXPERIMENTS
In this section, we empirically investigate the h-potential that we obtain with the training procedure described in the previous section. First, we show in a 2D-world environment that the h-potential learns measure reachability. Second, we show that the ht-otential can be used to detect side- effects in the challenging game of Sokoban (Leike et al. 2017). Third, we show on the game of Mountain Car with Friction that the h-potential can learn capture sailent features of the environ- ment, which can be used to formulate an intrinsic reward. We also demonstrate how the h-potential fails if the environment is not dissipative, i.e. if the friction is turned off. Finally, show for par- ticle undergoing Brownian motion under a potential that in expectation over states, the h-potential agrees reasonably well with the Free Energy functional, wherein the latter is known to be an arrow we show results on three additional environments.
of time (Jordan et al. 1998). Moreover in App C
Measuring Irreversibility. The environment con- sidered is 7 x 7 2D world, where cells can be oc- cupied by the agent, the goal and/or vase (their respective positions are randomly sampled in each episode). If the agent enters a cell with a vase in it, the vase disappears without compromising the agent. In Fig2] we plot the change in h-potential (recall that nss 8t++) h(8--)) h(s))) find that the breaking of a vase (irreversible) corresponds to the fi-potential increasing
Putentaai at Zere Valocity!
22.5
Negettiv
-1.
20.5
[Negative -Rte- 1=00
15.0
00.6
32.5
20.0
steps of roughly constant size (observe that the spikes attain similar heights), whereas the agent moving around (reversible) does not result in it increasing. This indicates that the h h-potential has learned to quantify irreversibility in- stead of merely detecting it by counting the number of broken vases. In App C.I.I (a) we further inves- and
-1.23
-1.00
-0.75
-0.30
-0.25
0.00
0.23
0.50
Postion
Figure 4: The h-potential (for Mountain Car) zero-velncity plotted against position. Also plot- ted (orange) is the height profile of the mountain. Gist: the ft-potential approximately recovers the heigght-rofiie of the mountain with just trajecto- ries from a random policy.
tigate the effect of adding cemporally-correlatte TV (uncorrelated) noise to the state and find that the f h-potennial is fairly robust to the latter but might get distracted by the former and (b) verify that agent trained with the safety penalty in Eqn breaks fewer vases (than without).
Detecting Side-Effects. Sokoban ("warehouse- keeperr)) is challenging puzzle video game, where an agent must push a number of boxes to set goal locations placed on a map. The agent may only push boxes (and not pull), rendering certain moves irreversible for instance, when box is pushed

---

Published as a conference paper at ICLR 2020
-2.8
0.06
6.330
5.25
0.04
-8.4
0.04
Valecit
-14.0
Velocity
3.15
0.00
0.00
2.11
-002
19.6
-0.02
-0.44
22.4
-0.04
25.2
-1.05
-0.00
28.0
-0.06
-2.10
-1.00
0.00
0.50
-1.00 -0.7 -0.25 0.25
Position
(a) With friction.
(b) Without friction.
Figure 5: The h-potential as a function of state (position and velocity) for (continuous) Mountain Car with and without friction. The overlay shows random trajectories (emanating from the dots). Gist: with friction, we find that the state with largest h is one where the car is stationary at the bottom of the valley. Without friction, there dissipation and the oscillates up and down the valley. Consequently, observe that the h-potential constant (up-to edge effects) and thereby uninformative.
against wall. Morcover, the task of even determining whether move is inreversible might be non- trivial, making the problem good test-bed for detecting side-effects (Leike et al. 2017). In Fig 3 that the h-potential increases if box is pushed against wall (irreversible side-effect) but remains constant if the agent moves about (reversible, even when the agent pushes a box around), demonstrating that the h-potennial has indeed learned detect side-effects. For experimental details and additional plots, please refer to App C.I.3
Obtaining Intrinsic Reward and the Importance of Dissipativity. The environment considered shares its dynamics with the well known (continuous) Mountain environment (Sutton & Barto 201T) but with a crucial amendment: the car is subject to friction. Friction required make the environment dissipative and thereby induce an arrow of time (cf. Sec (22).. Moreover, we initialize the system in a mnnfform-randomly sampled state avoid exploration issues (ef. App C.3). In Fig see that the learned h--oteentil roughly recovers the terrain from random trajectories (i.c. without external rewards), which can now be used to obtain an intrinsic reward signal. Further, Fig 5b illustrates the importance of dissipation (in this case, induced via friction). Details in App
C.2.2
Comparison with the Free-Energy Functional. The setting considered is that of particle (a random-walker) undergoing Brownian motion un- der the influence of potential field (xx (where denotes the spatial position). We denote the proba- bility of finding the particle position x time t by p(x, t). Now, the dynamics of the corresponding uune-dependent random variable (i.e. stochastic pro- cess) X(t) is governed by the stochastic differential equation:
Free Energy
Value fLnearly Adjustod)
-0.030
M-Funciional
-0.035
-0.640
-0.050
-0.055
-0.88c
-0.085
20
[[Timestep]
dX(t) = -V + /28-IdW (7)
The mue arrow of time (the Free- Energy functional, in bluc) plotted against the learned arrow of time (the H H-ffunciional, i.e. the negative spatial expectation of the l--potential; plotted orange) after linear scaling and shifting. Gist: we find the H ffunctionnl to in good (al- beit not perfect) agreement with the Free-Energy functional, where the latter is known notion of arrow of time.
Figure 6:
where W(t) is the standard Wiener process (i.e. dW(t) white-noise) and 8-1 is temperature pa-
rameter. The Free-Energy functional F' is now de- fined
F[p(,,t) t)] :x (x))
+3 + Ex) [log p(x,
where the first expectation of the RHS is the energy
functional, and the second expectation is the negative entropy. A celebrated result due to Jordan, Kinderlehrer, and Otto ( (1998) is that the Free-Energe is Lyapunov functional of the dynamics, i.c. it can only decrease with time, thereby defining notion an arrow of time. Now, to find out how well our learned arrow of time agrees with the Free-Energy functional, train it with realizations
8

---

Published as a conference paper at ICLR 2020
of the stochastic process ((t) in two-dimensions. O the Free-Energy functional F against linearly adjusted H -fnfcctiinal, defined as: H [p( - -Ex-pt- [/(x]] Indeed, we find that up to linear transform, the H functional (and the corresponding h-potential) agrees reasonably well with the true arrow of time given by the Free-Energy functional F. Crucially, the H-functional is also Lyapunov functional of the dynamics implying that in expectation over states, the h-potential functions as an arrow of time. Details can be found in A.p
CONCLUSION
In this work, we approached the problem of learning an arrow of time in Markov (Decision) Processes. We defined the arrow of time (h-potential) as a solution to an optimization problem and laid out the conceptual roadblocks that must be cleared before it can be useful in the RL context. But once these roadblocks have been cleared, we demonstrated how the notions of reachability, safety and curiosity can be bridged by common framework of a learned arrow of time. Finally, we empirically investigated the strengths and shortcomings of our method on a selection of discrete and continuous environments. Future work could draw connections to algorithmic independence of cause and mechanism (Janzing et al. 2016) and explore applications in causal inference (Janzing 2010 Peters al. 2017).
ACKNOWLEDGEMENTS
The authors would like to thank Min Lin for the initial discussions, Georgios Arvanitidis, Simon Ramstedt, Zaf Ahmed, Stefan Bauer and Maximilian Puelma Touzel for their valuable feedback on the draft.
REFERENCES
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Con- crete problems in ai safety. arXiv preprint 16060066006.6555,, 2016.
Ankesh Anand, Evan Racah, Sherjil Ozair, Yoshua Bengio, Marc-Alexandre Côté, and R Devon Hjelm. Unsupervised state representation learning in atari. arXiv preprint arXiv: 08226, 2019.
Anonymous, Nov 2019. [tt.:///w//gggeeeeeeeeee////ecea H1xTTMZN5H
Stuart Armstrong and Benjamin Levinstein. Low impact artificial intelligences. arXiv preprint 1705. 10720, 2017.
Stefan Bauer, Bernhard Schölkopf, and Jonas Peters. The arrow time in multivariate time series. In International Conference on Machine Learning, pp. 2043-2051, 2016.
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint 1606.0 2016.
L. Bunimovich. Dynamical billiards. Scholarpedia, 2(8):1813, 2007. doi: 10.4249/scholarpedia 1813. revision #91212.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity- driven learning. arXiv preprint arXiv: 100.:00888.0555... 2018.
Nuttapong Chentanez, Andrew G Barto, and Satinder P Singh. Intrinsically motivated reinforcement learning. In Advances in neural information processing systems, pp. 1281-1288, 2005.
Arthur Stanley Eddington. The nature of the physical world / by A.S. Eddington. Cambridge Uni- versity Press Cambridge, England, 1st ed, edition, 1929.
Benjamin Eysenbach, Shixiang Gu, Julian Ibarz, and Sergey Levine. Leave no trace: Learning to reset for safe and autonomous reinforcement learning. arXiv preprint arXiv: 1,006888, 2017.

---

Published as a conference paper at ICLR 2020
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: 1029, 2017.
Shuyang Gao, Greg Ver Steeg, and Aram Galstyan. Efficient estimation of mutual information for strongly dependent variables. In Artificial Intelligence and Statistics, pp. 277-286, 2015.
David Ha and Jürgen Schmidhuber. World models. arXiv preprint 18X3,v1800.111222 2018.
Dominik Janzing. On the entropy production of time series with unidirectional linearity. Journal of Statistical Physics, 138(4-5):767-779, 2010.
Dominik Janzing, Rafael Chaves, and Bernhard Schölkopf. Algorithmic independence of initial condition and dynamical law thermodynamics and causal inference. New Journal of Physics, 18(9):093052, 2016.
Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the fokker- planck equation. SIAM journal on mathematical analysis, 29(1):1-17, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980 2014.
LF Kozachenko and Nikolai N Leonenko. Sample estimate of the entropy of a random vector. Problemy Peredachi Informatsii, 23(2)99-16, 1987.
Victoria Krakovna, Laurent Orseau, Miljan Martic, and Shane Legg. Measuring and avoiding side effects using relative reachability, CoRR, abs/ 10s//100.01186, 2018. /Rt/att:://rxxi
abs/1806. 01186
Alexander Kraskov, Harald Stöghauer, and Peter Grassberger. Estimating mutual information. Phys- ical review E, 69(6):06613)) 138, 2004.
Tejas Kulkarni, Ankush Gupta, Catalin loneseu, Sehastian Borgeaud, Malcolm Reynolds, Andrew Zisserman, and Volodymyr Mnih. Unsupervised learning of object keypoints for perception and control. arXiv preprint arXiv:1906.11883, 2019.
Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A Ortega, Tom Everitt, Andrew Lefrancq. Lau- rent Orseau, and Shane Legg. Ai safety gridworlds. arXiv preprint arXiv:1711.09883 2017.
Teodor Mihai Moldovan and Pieter Abbeel. Safe exploration in markov decision processes. arXiv preprint arXiv: 225..4100 2012.
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare Bellemare. Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1054-1062, 2016.
Andrew Y Ng and Stuart Russell. Algorithms for inverse reinforcement learning. In Proc. 17th International Conf. on Machine Leurning. Citeseer, 2000.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In ICML, 2017.
Jonas Peters, Dominik Janzing, Arthur Gretton, and Bernhard Schölkopf. Detecting the direction of causal time series. In Proceedings of the 26th annual international conference on machine learning, pp. 801-808. ACM, 2009.
Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Elements of causal inference: foundations and learning algorithms. MIT press, 2017.
Lyndsey C Pickup, Zheng Pan, Donglai Wei, YiChang Shih, Changshui Zhang, Andrew Zisserman, Bernhard Scholkopf, and William Freeman. Seeing the arrow of time. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2035-2042, 2014.
Ilya Prigogine. Time, structure, and fluctuations. Science, 201(4358)777--885 1978.
10

---

Published as a conference paper at ICLR 2020
Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Mare Pollefeys. Timo- thy Lillicrap. and Sylvain Gelly. Episodic curiosity through reachability. arXiv preprint arX1v:1810.02224.2000 2018.
Abraham Savitzky and Marcel JE Golay, Smoothing and differentiation of data by simplified least squares procedures. Analytical chemistry, 36(8):1627-1639, 1964.
Jürgen Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation (1990-2010), IEEE Transactions on Autonomous Mental Development, 2(3):230- 247, 2010.
Max-Philipp B. Schrader.
gym-sokoban.
gym-sokoban] 2018.
Udo Seifert. Stochastic thermodynamies, fluctuation theorems and molecular machines. Reports progress in physics, 75(12):126001,2 2012.
Zhang Shangtong. Modularized implementation of deep rl algorithms in pytorch. https://
github. hww.a///haaaggttongggaan//eeeeee 2018.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2011.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Thirtieth AAAI Conference Artificial Intelligence, 2016.
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Van Hasselt, Mare Lanctot, and Nando De Freitas. Dueling network architectures for deep reinforcement learning. arXiv preprint 1rxXiv:151.06335 2015.
Donglai Wei, Joseph Lim, Andrew Zisserman, and William T Freeman. Learning and using the ar- row of time. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 8052-8060, 2018.
Jan Willems. Dissipative dynamical systems part i: General theory. Archive for rational mechanics and analysis, 45(5)332--351, 1972.
Wojeiech Zurek. Algorithmic randomness and physical entropy. Physical Review A, 40(8):4731, 1989.

---

Published as a conference paper at ICLR 2020
A THEORETICAL ANALYSIS
In this section, (a) we present a theoretical analysis of the optimization problem formulated in Equ | (b) analytically evaluate the result for few toy Markov processes to validate that the resulting solutions are indeed consistent with intuition and (c) highlight how the h-potential differs from forward state-action transition model. To simplify the exposition, we consider the discrete case where the state space S of the MDP is finite.
A.1 ANALYTICAL SOLUTION TO EQN AND APPLICATION TO TOY MARKOV CHAINS
Consider a discrete Markov chain with enumerable states 8; E S. At an arbitrary (but given) time- step let P p(s: s;) denote the probability that the Markov chain is in state 8;, and p' the corresponding vector (over states). With Ti we denote the probability of the Markov chain transitioning from state s; 8j under some policy π, i.e. Tij p = -8ylse si). One has the transition rule:
p p++1=p'7 p' p'=
where 7 is the t-th matrix power T. Now, let h; denote the value h2 takes at state s;, i.c. h; = hg (s;), and the corresponding vector (over states) becomes h. This reduces the expectation of the function (now a vector) w.r.t any state distribution (now also vector) p the scalar product h. In matrix notation, the optimization problem in Eqn simplifies to:
N-1 p'Th h + AT(h)
arg max h N
(10)
For certain T, the discrete problem in Eqn 10 can be handled analytically. We consider two can- didates for T. the first being the norm of h, and the second one being the norm of change in h, in expectation along trajectories.
Proposition 1. T() -(2N)- the solution to the optimization problem in Eqn 10 is given by:
h p T p
(11)
Proof. First, note that the objective in Eqn 10 becomes:
N Σ
1 p 'T p¹ h]] ||b|
[h
(12)
2.V
To solve the maximization problem, we must differentiate L w.r.. its argument h, and set the resulting expression zero. This yields:
N Σ (p' - p¹) -hh = 0
VnL
(13)
N
Now, the summation (over t) telescoping, and evaluates p N- p.. Substituting p N- with the corresponding expression from Eqn and solving for h, we obtain Eqn II
Proposition I Thas an interesting implication: if the Markov chain is initialized at equilibrium, i.c. if pd = PT, we obtain that 0 identically. Given the above, we may now consider as examples the following simple Markov chains.
12

---

Published as a conference paper at ICLR 2020
1 - a
81
1 a
Figure 7: The two-state Markov chain considered in Examples and
Example 1. Consider a Markov chain with two states and reversible transitions, parameterized by
E [0, 1] such that Ti1 = T21 1 - a and T12 = T22 = a (Fig If = (1/2, 1/2), one obtains:
h < (-
(14)
where 7 a - 1/2. To see how, consider that for all N > O, one obtains pOTN = az, ox)
Together with Proposition [ Eqn [g]]
The above example illustrates two things. On the one hand, if 1/2, one obtains Markov chain with perfect reversibility, i.. the transition $1 + 82 equally as likely as the transition 82 - $1- In this case, one indeed obtains h(s1) h(s2) O, mentioned above. On the other hand, if one sets a = 1, the transition from 82 > 81 is never sampled, and that from 81 -> 82 is irreversible; consequently, h(s2)) h(s1) takes the largest value possible. Now, while this aligns well with our intuition, the following example exposes a weakness of the L2-norm -oonmmpenaatyy used in Proposition
81
82
83
S1
Figure 8: The four-state Markov chain considered in Examples 2 and
Example Consider two Markov chains, both always initialized $1. For the first Markov chain, the dynamics admits the following transitions: - 82 - $3 + whereas for the second chain, one has 81 -> 83 _> 82 -> 84 (Fig (). Now, for both chains and N 2 4, it's easy to see that NN 1 i = 4, but O otherwise. From Eqn 11 one obtains:
h x (-1,0,0,1)
(15)
The solution for h given by Eqn 15 indeed increases (non-strictly) monotonously with timestep. However, obtain l((2) (s3a) O for both Markov chains. In particular, h does not increase between the 82 + 83 transition the former and the 83 + 82 transition both transitions are irreversible. is in general apparent from that the solution for h depends only on the initial and final state distribution, and not the intermediate trajectory.
latter, even though
Now, consider the following regularizer that penalizes not just the function norm, but the change in in expectation along trajectories:
T(h)
Σ (p)
(16)
2N
2N
where w is the relative weight of the L2 regularizer. This leads to the result:
Proposition 2. The solution to the optimization problem in Eqn 10 with the regularizer in Eqn the solution the following matrix-equation:
16 is
N
T (1++1- -T + wh OTN d
p
(17)
2
Proof. Analogous to Eqn we may write the objective Equ 10 as (by substituting Eqn
16 in
Equ 10):
N Σ
N-
c[b] = N
p'
Σ
(p'Th
h)²
1
(18)
2N
2N
1=0
0=
13

---

Published as a conference paper at ICLR 2020
Like in Proposition|
!
maximize it by setting the gradient of L w.r.t h to zero. This yields:
N- (D'
N-1
VnL = N
V
Σ
(p'Th-17 p' h)² wAh
=
(19)
0=
The first term in the RHS is again a telescoping sum; it evaluates to: pTT pd (cf. proof of Proposition The second term can be expressed as (with I as the identity matrix):
N-1
(p'Th p' h)² =
(T
(20)
2
2
E=
N-1
x
(21)
t=
N-1
A
P' hp T
(22)
where the last equality follows from Eqn 9 Substituting the above in Eqn 19 and rearranging terms
yields Eqn 17
While Eqn 17 does not yield an explicit expression for h, it is sufficient for analysing individual cases considered in Examples I [
Example 3. Consider the two-state Markov chain in Example (Fig and the associated transition
matrix T and initial state distribution pd = (1/2, 1/2). Using the regularization scheme in Equ 16
and the associated solution Equ 17 one obtains:
h (-7,))
(23)
where:
2a 1
(24)
A(4a² 4a + 2w + 1)
To obtain this resul f we use that T for t 1 and truncate the sum without loss of generality at N =
Like Example we observe h(s1) = h(x2) if a 1/2 for all > 0 (i.e. at equilibrium). In addition, if 2 2/2, it can be shown that h(s2) hsss) increases monotonously with and takes the largest possible value at a = 1. We therefore find that for the simple two-state Markov chain of Example [ the regularization in Eqn 16 indeed leads intuitive behaviour for the respective solution h. Now:
Example Consider the four-state Markov chain with transitions 81 + -2 - 54 (Fig and the corresponding transition matrix T, where Ti2 = T23 T3a = T4 = 1, Ti = 0 for all other i.j. Set pd = (1, 01 0, 0), i.e. the chain is always initialized at 81. Now, the summation over in
Eqn 17 can be truncated N without loss of generality (over N), given that 7 T for all
t t> 3. At w = O, one solution is:
h (/22,,-1/2,1/4 1/2,
(25)
Further, for all w O, one obtains h(s)) h(s2) h(ss)) h(s)), where the inequality is strict. This is unlike Eqn 15 where h(s2) h(s3), and consistent with the intuitive expectation that the arrow of time must increase along irreversible transitions.
A.2 THE h- P-TTENTTIAL VS. A FORWARD MODEL
Thus far, we have considered Markov chains, which relies a notion of transition matrix Tip specifying p(1 = 8y 8 = 8,). Now, the transition probabilities can also be expressed as:
p(3 (:) := p( = sy1s, =:) Σ p( = sy1s, s,, a = a)T(()ss)
(26)
Interested readers may refer the attached SymPy computation.
14

---

Published as a conference paper at ICLR 2020
where the variable is called the action, and p(s = syls; 84, de = a) is the action-condition one-step forward transition model, or simply a forward model. The distribution I (a]ss) is called the policy, and can characterize the behaviour of agent.
Now, given the forward model and a policy, one could define a possible measure of reversibility as:
p(s,(ss)
g(s; - ,,, = log s())(s))
(27)
Indeed, g(8; + 83) = O when p(8y(s:) = (0(8118)) i.e. when the probability of transitioning from state 8; state 8j equals that of transitioning from sj to 8i. Further, if the transition 8, 8. is
more likely than 8j + 8t under the model and the policy, then we have that p(8y|*)) > p((
and consequently, g(s; + 5;) > (and vice versa with and j swapped). This raises the question: can the quantity gs; + 83) replace h(s; + 8,) == h(s,) - h(s,)? To answer this, consider the following.
First, in non-ergodic processes, there may exist states s; and s, for which both quantities p(sy|s; and p(s) are zero. In the Markov process Figure 8 these could be states 85) (s1 $3) or (8;, 83) 84). In both cases, however, we have that y(:; - 85) is not defined. In fact, this applies to any functional form g might take (i.e. it need not take the one specified Eqn (2): as long g depends exclusively on p(s((s)) and p(s) (5))))), it is unable to differentiate between the two cases. This is quite unlike h, where we know from Example that h(s1 + 33) = and h(s1 + 84) = 3.
Second, to obtain the quantity p(sj(s;) required to evaluate g. we require marginalization over actions a. If discrete and the action space is small, this simple summation. However, for large or even continuous action spaces, this marginalization amounts an integral, which may not be tractable in practice.
It is therefore evident that the reversibility measure & obtained with one-step forward model need not be consistent over multiple steps, and in that it differs from the h-potential. One may address this by considering (in addition) r-step models p(st+r St, Gt. ac+1; -... (t+7-1)+ but to obtain p p()t-((1 (s)) one must marginalize over a;, 4t+1,,..., O which does not scale well with т. Nevertheless, in practice it might be possible to utilize the one-step model as a mean obtain the h-potential. This involves approximating the to analytically evaluate h or to train a parameteric approximation to h from trajectories sampled from the model in a manner analogous to DynaQ (Sutton & Barto 201T.
transition matrix T with a learned matrix T, which then be used
CONCLUSION
In conclusion, we find that the functional objective defined in Equ Sqn[man may indeed lead to analytical solutions that are consistent with the notion of an arrow of time in certain toy Markov chains, and highlight the subtleties involved in relying reversibility. However, in most interesting real world environments, the transition model T is not known and or the number of states is infeasibly large, rendering an analytic solution intractable. In such cases, as we see in Section 5) it is possible to parameterize h as a neural network and train the resulting model with stochastic gradient descent to optimize the functional objective defined in Eqn]
one-step forward model to obtain measure of
15

---

Published as a conference paper at ICLR 2020
B ALGORITHM
Algorithm Training the h-Potential
Require: Environment Env, random policy Ty. trajectory buffer B Require: Model h", regularizer T, optimizer.
1: for k I...M do
2: B [k, ]] < (s....., sN) Env[ay] {Sample a trajectory of length N with the random
policy and write to k-th position in the buffer.)
3: end for
4: loop
5: Sample trajectory index k ~ {l,..., M } and time-step t ~ (0,..., N - 1}. {In general, one may sample multiple k's and f's for larger mini-batch.}
6:
Fetch states < B [k, t and 8141 +- B [k, t + 1] from buffer.
7:
Compute loss as L(0) ( (s())
8:
if using trajectory regularizer then Compute regularizer term as [h (8(41) 1º (x,)) and add to I(0).. else
9:
10:
11:
Apply the regularizer as required. If carly-stopping, break out of the loop necessary. end if
12:
13:
Compute parameter gradients V(L(() and update parameters with the optimizer.
end loop
16

---

Published as a conference paper at ICLR 2020
25000
35000
[Potential Differencel
20000
32500
15000
30000
[Potential 065-5t-3
10000
27500
25000
5000
W
M
M
M
22500
20000
-5000
17500
1000
120
20
100
120
[TTimestep]
[[Timestep]
(a) TV-Noise
(b) Causal Noise
Figure 9: The potential difference 7 plotted along trajectorics, where the state-space is augmented with tem- porally uncorrelated (TV-) and correlated (causal) noise. The dashed vertical lines indicate time-steps where vase is broken. Gist: while method is fairly robust TV-noisc, it might get distracted by causal noise.
250000
250000
[Potential
450000
500000
-550000
-600000
550000
50
40
60
100
120
[Timestopl
-1000000 BOCOCO
-00000 400000 200000 h(S [Potential]
Figure 10: The h-ppotential along a trajectory sam- pled from a random policy. Gist: The l--potentill increases step-wise along the trajectory every time agent (irreversibly) breaks a vase. It remains constant as the agent (reversibly) moves about.
Figure 11: Histogram (over trajectories) of values taken by h at time-steps 0, = 32 and = T 128.
C EXPERIMENTAL DETAILS
All experiments were run workstation with 40 cores, 256 GB RAM and 2 nViidia GTX 1080Ti.
C.I DISCRETE ENVIRONMENTS
C.1.1 2D WORLD WITH VASES
The environment state comprises three 7 x 7 binary images (corresponding to agent, vases and goal), and the vases appear in different arrangement every time the environment is reset. The probability of sampling a vase at any given position is set to V/2.
We two-layer deep and 256-unit wide ReLU network parameterize the h-potential. It is trained on 4096 trajectories of length 128 for 10000 iterations of stochastic gradient descent with Adam optimizer (learning rate; 0.0001). The batch-size is set to 128, and use weight decay of 0,005 to regularize the model. We use a validation trajectory to generate the plots in Fig I0 and 2 Moreover, Fig [] shows histograms of the values taken by at various time-steps along the trajectory. We learn that i takes on larger values (on average) as increases.
To test the robustness of our method, we conduct experiments where the environment state aug- mented with one of: (a) 7 7 image with uniform- -radooly sampled pixel values (TV-noise) and (b) 7 image where every pixel takes the value 1/128, where the time-ster of the correspond-
RReall that the trajectory length is 128.
17

---

Published as a conference paper at ICLR 2020
Probability of Reaching the Goal
1.0
Mean Number of Vases Broken
3.0
2.8
0.8
0.4
0.2
1.8
Without h-Potential
1.6
Without h-Potential With hiPotential
With h:Pobential
1.4
50000
100000
150000
200000
250000
50000
100000
150000
200000
250000
Iterationn
Ittraaionns
(a) Probability of reaching the goal.
(b) Number of vases broken.
Figure 12:
Probability of reaching the goal and the expected number of vases broken, obtained over 100 eval- uation episodes (per step). Gist: while the safety Lagrangian results in fewer vases broken, the probability of reaching the goal state is compromised. This trade-off between safety and efficiency is expected (cf. Moolovan Abbeel 2012)).
ing state (Causal Noise). Fig 9a and 9b plot the corresponding = Ah. along randomly sampled trajectories.
Given a learned arrow time, we now present an experiment where we use it to derive a safe- exploration penalty (in addition to the environment reward). To that end, now consider the situation where the agent's policy is not random, but specialized to reach the goal state (from its current state). For both the baseline and the safe agents, every action is rewarded with the change in Manhattan norm of the agent's position to that of the goal i.c. an action that moves the agent closer the goal rewarded +1, one that moves farther away from the goal is penalized -1, and one that keeps the distance unchanged is neither penalized nor rewarded (0). Further, every step penalized by -0.1 (so as to keep the trajectories short), and exceeding the available time limit (30 steps) incurs termination penalty (-10). In addition, the reward function of the safe agent is augmented with the reachability, i.e. it takes the form described Eqn 4 We use B = and transfer function such that o (1)) = 0 0 < 5000 (cf. Fig 2 and otherwise.
The policy is parameterized by 3-layer deep 256-umit wide (fully connected) ReLU network and trained via Duelling Double Deep Q-Learning 19 (Van Hasselt et al. 2016 Wang al. 2015). The discount factor set to 0.99 and the target network is updated once every 200 iterations. For greedy policy, where is decayed linearly from 1 to 0.1 in the span
exploration, we use of the first 10000 iterations. The replay buffer stores 10000 experiences and the batch-size used is 10. Fig 12a 12a shows the probability of reaching the goal (in episode of 30 steps) over the iterations (sample size 100), whereas Fig 12b shows the expected number of vases broken per episode (over the same 100 episodes). Both curves are smoothed by a Savitzky- Golay filter (Savitzky Golay 1964) of order 3 and window-soe size 53 (the original. unsmoothed curves are shaded). As expected, we find that using the safety penalty does indeed result in fewer vases broken, but also makes the task of reaching the goal difficult (we do not ensure that the goal is reachable without breaking vases).
C.1.2 2D WORLD WITH DRYING TOMATOES
The environment considered comprises 7 x 2D world where each cell is initially occupied by watered tomato plan The agent waters the cell it occupies, restoring the moisture level of the plant in the said cell to 100%. However, for each step the agent does not water plant, it loses some moisture (by 2% of maximum in our experiments). If plant loses all moisture, it is considered dead and no amount of watering can resurrect The state-space comprises two 7 x images: the first image is indicator of the agent's position, whereas the pixel values of the second image quantifies the amount of moisture held by the plan at the corresponding location.
We adapt the implementation due Shangtong 2018
We draw inspiration from the watering environment described Leike et al. 2017 This is strong causal signal which may distract the model. We include it nonetheless to make the task challenging.
18

---

Published as a conference paper at ICLR 2020
1.4
-14
1.2
Reference Reward
-12
Intrinsic Reward
Reference Reward
0.4
0.2
0.2
0.0
Thiy W-
-..0
-0.2
-0.2
-0.4
0.44
[Timestee]
Figure 13: The intrinsic reward (Fgn 28) plotted against engineered reward, which in this case is the moisture gained by the tomato plant the agent just watered. Gist: the I--Potential captures useful information about the environment, which can then be utilized to define intrinsic rewards.
We show that it is possible to recover intrinsic reward signal that coincides well with one that one might engineer. that end, we parameterize the l--otential as a two-layer deep 256-unit wide ReLU network and train on 4096 trajectories (generated by random policy) of length 128 for 10000 iterations of Adam (learning rate: 0.0001). The batch-size is set to 128 and the model is regularized with the trajectory regularizer (A 0.5).
Unsurprisingly, we find that h increases as the plants lose moisture. But conversely, when the agent waters plant, it causes the h-potential to decrease by amount that strongly correlates with the amount of moisture the watered plant gains. This can be used to define dense reward signal for the agent:
fr -17 st) Running-Average,ful
(28)
where we use momentum of 0.95 to evaluate the running average.
In Fig 13
we plot for a random trajectory the intrinsic reward Å against reference reward, which in this case is the moisture gain of the plant the agent just watered. Further, we observe the reward function dropping significantly around 90-th iteration this precisely when all plants have died. This demonstrates that the h- h-potential can indeed be useful for defining intrinsic rewards.
1.1.3 SOKOBAN
5
h-Potential
-5
-10
-15
-20
100
200
300
400
500
Timestep
Figure 14: A--Poeential averaged 8000 trajectories, plotted against timestep i; shaded band shows the standard deviation. Gist: as required by objective (Eqn []. the h- h-Potential must increase in expectation along trajectories.
19

---

Published as a conference paper at ICLR 2020
F--i
(a) States
(b) States
Figure 15: Random samples from 200 transitions that cause the largest increase in the h-potential (out of sample size of 8000 transitions). The orange, white, blue and green sprites correspond wall, the agent, box and a goal marker respectively. Gist: pushing boxes against the wall increases the h-potennial.
The enviromment state comprises five 10 x 10 binary images, where the pixel value at each location indicates presence the agent, a box, goal, wall and empty space. The layout all sprites are randomized at each environment reset, under the constraint that the game is still solvable (Schrader) 2018). The ht-potential is parameterized by two-layer deep and 512-unit wide network, which is trained on 4096 trajectories of length 512 for 20000 steps of Adam (learning rate: 0.0001). The batch-size set to 256 and we use the trajectory regularizer (A = 0.05) to regularize our model.
C.1.4 CONVEYOR BELT ENVIRONMENT OF KRAKOVNA ET AL.
20188
Figure 16:
The initial state of the conveyor belt environment with an agent (orange robot), vase (blue) and conveyor belt (red arrows). The conveyor belt carries the vase rightwards. until it falls off and breaks.
The environment considered is 5 2D world (Fig 16 with an agent, conveyor belt and vase that is initially placed on the belt (this is the Vase enviroument in Krakovna et al. (2018)). If the agent passive (i.e. stays put, Fig 17b). the conveyor belt moves the vase one step to the right until it eventually falls off the belt and breaks. However, the intended behaviour of safe (good) agent (Fig 17ah is that removes the vase from the conveyor belt, preventing it from breaking. One may also have malicious agent (Fig 17c) that removes the vase from the belt (e.g. to collect reward) only to put back on again. In contrast, an inept agent (Fig 17d) may remove the vase from the belt but irreversibly push the reward that awarded by the h-potential to each these policies, which we label good, passive, maliciouy and inept.
corner (like in Sokoban). In the following, we investigate
20

---

Published as a conference paper at ICLR 2020
(a) Good Agent.
(b) Passive Agent.
(c) Malicious Agent.
(d) Inept Agent.
Illustration of the policies we to test the safety reward assigned by the h-potential. Gist: the good agent removes the vase from the vase and stays put. The passive policy stays put and does nothing as the vase falls off the belt. The malicious policy removes the vase from the belt (possibly to collect a reward) only to put it back on it again. The inept policy removes the vase from the belt, but pushes it to corner (the agent lacks the ability to pull back).
Figure 17:
To that end, gather 4096 random trajectories of length 64 each. The h--otenniall is parameterized by a 256-unit wide and 2-layer deep MI.P with ReLU activation, and trained with 80000 steps of stochastic gradient descent with Adam Kingma & Ba (0114). We use trajectory regularizer with A = 0.01 to regularize the model. The state space is a collection of 6 binary images of size 7 x 7, where in each image the truth value of pixel marks the presence of wall, empty space, belt, agent, vase and a broken vase in the corresponding location 12
As the model trains, we track the return awards the four policies mentioned above (to aid visualization, we normalize the rewards to have mean of zero) and plot the result in Fig 18 We find that the h--potential rewards the good policy, but penalizes the passive, malicious and inepr policies. This can be contrasted with the predefined safety performance measure, which assigns safety score of +500 to the good and inept agents, 0 to the malicious agent and -50 to the passive agen(") (larger score is safer). Our method therefore learns that pushing the vase to corner is no less irreversible than breaking it (malicious and passive) and penalizes the inept policy accordingly.
80
60
Relative Returns
40
Good Policy
Passive Policy
20
Malicious Policy
0
Inept Policy
-40
10000 20000 30000 40000 50000 60000 70000 80000 Iterations
The normalized returns awarded to the various policies discussed in text and illustrated in Fig 17 averaged over training runs (shaded bands are the standard deviations). Gist: the h-potential penalizes all irreversible behaviour, including the vase being pushed in to cornrr by the inept policy (in addition to falling off the belt due to passive and malicious policies).
Figure 18:
To conclude, we confirm that the safety reward extracted from the h--pttnniill enable agents avoid irreversible behaviour. However, while preventing the irreversible is safe in this context, it may not always be the case we point the reader to the Sushi environment in Krakovna et al. (2018) for an example
12 implementation in https: / ttt.ttt...uggggo////////
under
envi auvironments// wttpmmenns//oovvooo.to belt. .y.
13 We refer to the implementation in https: / thub. com deepmi heaamind/aa wwd/ai-saaftty-griideee
The object on the belt Sushi instead of vase, and the helt leads to hungry human.
21

---

Published as a conference paper at ICLR 2020
0.4
INegative at Velocity!
2.0
Angular Velocity
-04
2
-0.8
0
-12
1.0
-2.0
-2.4
-2.0
1
2
Angle
Angle [rad]
(a) Learned h-Potential as function state- space (0, (), Overlaid are trajectories from a random policy.
(b) Negative of the learned It-Potential fuunction of 0 when 0 = 0.
Figure 19: Gist: the learned h-Potential takes large values around (0, (0,0) = 0, since that where most trajectories terminate due to the effect of damping.
C.2 CONTINUOUS ENVIRONMENTS
C.2.1 UNDER-DAMPER PENDULUM
Under-damped Pendulum. The environment considered simulates an under-damped pendulum, where the state space comprises the angle 0 and angular velocity Ô of the pendulum. The dynamics are governed by the following differential equation where 7 is the (time-dependent) torque applied by the agent and m, 4, 9 are constants:
3g sin +
3r ml2
ab
(29)
21
We adapt the implementation in OpenAl Gym (Brockman et al. 2016 to add extra term al to the dynamics to simulate friction. In our experiments, we set g = 10, m = L, a = 0.1 and the torque is uniformly sampled iid. from the interval [-2, 2).
The h-Potential is parameterized by a two-layer 256-unit wide ReLU network, which is trained on 4096 trajectories of length 256 for 20000 steps of stochastic gradient descent with Adam (learning rate: 0.0001). The batch-size is set to 1024 and we use the trajectory regularizer with À 1 to regularize the network. Fig 19a plots the learned h-potential (trained with trajectory regularizer) function of the state (0,0) whereas Fig 19h shows the negative potential for all angles 0 at zero angular velocity, i.e. 0 = O. We indeed find that states in the vicinity of have larger h- potential, owing to the fact that all trajectories converge (0,0) = 0 for large due the dissipative action of friction.
C.2.2 CONTINUOUS MOUNTAIN CAR
The environmen 16
considered is a variation of Mountain Car (Sutoon & Barto 2011 where the state-space tuple (x) of the position and velocity of vehicle mountainous terrain. The action space is the interval [- 1, 1] and denotes the force f applied by the vehicle. The dynamics of the modified environment given by the following equation motion:
# Cf 0.0025 cos 3z at.
(30)
where Ç and constants set to 0.0015 and 0.1 respectively, and the velocity à is clamped to the interval [-0.07, 0.07]. Our modification is the last at term to simulate friction. Further, the initial state (x, &) is sampled uniformly from the state space S [-1.2, 0.6] [-0.07, 0.07). This
1 is commonly represented as (cos(f), sin( instead scalar. We adapt the implemetation due to Brockman et al. 2016 gi github. com cwtbo//acc//paaiicoocoomooaaaaa. /
available here:
gym anvs/classe control cont nuous mountain car.py
22

---

Published as a conference paper at ICLR 2020
potentially be avoided if an exploratory policy is used (instead of the random policy) to gather trajectories, but we leave this for future work.
The h--otenniaal is parameterized by two-layer 256-unit wide ReLU network, which is trained on 4096 trajectories of length 256 for 20000 steps stochastic gradient descent with Adam (learning rate: 0.0001). The batch-size is set to 1024 and the trajectory regularizer with À 1.
C.3 LEARNING THE /t- P-POONNTIAL. WHILE SIMULTANFOUSIY EXPLORING THE ENVIRONMENT
Recall that the policy we have thus-far used to gather the trajectories required to train the h-potential random (cf. Sec (.2)). While the use of random policies is ubiquitous in the model-based and
related literature (Ha Schmidhuber 2018 Savinov et al. 2018 Kulkarni al. 2019 Anand itt al,, 2019), it typically comes at price: namely, the lack of adequate exploration in complex enough environments (Ha & Schmidhuber 2018). In this section, we investigate possible strategies towards approaching this problem in the context of learning an h-potential. We stress that the results in this section are preliminary and the discussion below is intended to showcase the challenges that lie in the way; much more future work will be needed to holistically address this important issue in a principled manner.
To proceed, we consider again the environment of Mountain Car with Damping (cf. Sec and App C.2.2). but with the amendment that the car is initialized in the valley with zero velocity. We choose this task because it is small enough for fast iteration and easy visualization, yet it poses a difficult exploration problem for an appropriate choice of environment parameters given that the car may not climb far out of the valley by simply applying constant action. Likewise, random actions are not enough to adequately explore the state-space in order to learn the h-potential (Fig 20).
36
0.06
24
0.04
12
0
Velocity
-12
244
-0.02
36
-0.04
48
-0.06
60
11.00
-0.75 -0.50 0.25
0.00
0.25
0.50
Position
Random trajectories (white curves emanating from the dots) overlayed on the h-potential as function of state (position and velocity). Gist: the le-potential trained random trajectories fails to wholly characterize the dynamics considered environment. This due a lack of adequate exploration by the random policy.
Figure 20:
The approach we describe can be thought of as bootstrapping the h- h-potential by using an exploratory policy in tandem with random policy and trajectory buffer. The procedure (adapted from Anony- mous 2019) as following:
1. Initialize a trajectory buffer and fill with trajectories from a random policy (starting at the environment specified initial states, i.e. in the valley).
In particular, the friction parameter and the force Ç in Eqn 30 where the latter can be thought of as the power of the car. We use 0.1 and 0.0025, which assure ourselves is not enough for the car to reach the top of the mountain by applying constant action.
23

---

Published as a conference paper at ICLR 2020
25.6
18
0.06
192
0.04
9
-2.8
0.02
00
0.02
Velociy
Velocit
0.00
0.00
66.4
-27
-0.04
-36
-0.04
-19.2
-0.06
-45
-0.06
-32.0
-0.75
0.00
-1.00 -0.75 0..50 -0.25 0.00 0.25
0.50
Position
Position
(a) With exploration bias.
(b) With random rewards.
The /-potential as a function of state (position and velocity). The overlaid curves (in white, emanating from the dots) show samples from the trajectory buffer used to train the respective h-potential. Gist: find in Fig 21a that the exploration bias causes the h-potential to over-specialize state-space whilst ignoring the other. This by initializing random policy at states reached by exploratory policies trained to maximize random reward functions.
Figure 21:
one section of the contrasted with 2ig where the trajectories are gathered
2. Train (from scratch) the h-potential with transitions available in the trajectory buffer.
3. Train (from scratch) an exploratory policy to minimize the I-potential (cf. Sec 3.3
4. Use the exploratory policy to transition difficult-to-reace state.
5. Initialize the random policy at the said state, and use it gather more trajectories that randomly replace a fraction of the existing trajectories in the buffer.
6. Repeat steps
The trajectories gathered in step 5 are mixed with previously gathered trajectories to improve the stability of the training procedure. Moreover, note that the h-potential and the exploratory policies are reinitialized and trained from scratch at every iteration (step 6 to counteract the exploration- bias detailed below. Further, the exploratory policy is parameterized by NoisyNet (Fortunato) et al. 2017) to (locally) aid exploration.
Unfortunately, the above procedure runs the h-potential (in step 3 and the h-potential in turn adapts to the exploratory policy (in step 5 This circular adaptation, which we call the exploration bias, leads to the situation where the h- potential (correctly) learns that the mountain to the right is difficult to climb (Fig 21a positions
the problem that the exploratory policy adapts to
0.552,, whereas the mountain to the right left unexplored (because is initially assigned larger values). Consequently, the exploratory policy minimizing the h-potential will focus climbing the mountain to the right whilst ignoring the one to the left (cf. Fig 2Ia). which in results in more trajectories gathered for the right mountain (and none for the left).
To side-step the exploration bias, we resort to pre-populating the trajectory buffer with trajectories gathered by random policy initialized at states reached by exploratory policies trained on random reward potentials. Precisely, we replace the the h-potential by randomly initialized neural network, to train the exploratory policy, use the exploratory policy for a random number of steps to transition to a state, use that state as the initial state of random policy, gather trajectories to populate the buffer, and repeat a few times over in our experiments). The result is trajectory buffer that populated with a more diverse set of trajectories. The intuition behind this heuristic is that a random reward potential will attract the exploratory policy to random locations the state space, leading to more diverse set of trajectories. That said, we have not studied the efficiency of this strategy and its feasibility in other environments.
150.5 in experiments.
24

---

Published as a conference paper at ICLR 2020
2.0
1.5
35
1.0
105
0.5
114
0.0
175
-0.5
-20
245
-1.0
-88
-15
3315
-2.
-2.
-15
-1.0
0..5
0.0
0.5
1.5
2.0
Figure 22: Learned h- I-Potential as function of position x. Observe the qualitative similarity to the potential V/ defined in Equ 32
With the trajectory buffer pre- pre-populated, we train the h-potential to obtain the resul in Fig 21b which can be compared to Fig 5a
In conclusion, we presented a preliminary investigation of strategies towards attacking the explo- ration issues that may arise when training the h-potenntil (or model-based methods in general). Concretely, we formulated the strategy of bootstrapping (Anonymous) 2019). but found that it can be subject what called exploration bias. We side-stepped the exploration bias by using a pop- ulation of exploratory policies trained to maximize random reward functions, which lead to trajec- tories diverse enough to train the h--oteentia for the environment considered. We remain optimistic that a well-crafted algorithm combining bootstrapping with random rewards might be fruitful even complex environments, but leave thorough investigation to future work.
C.4 COMPARISON WITH THE EEEE-EEERRGY FUNCTIONAL.
The environment state at given time-step comprises two scalars, the x x1(() and x2(() coordinates of the particle's position x x()). Recall that the dynamics defined by:
<x(t) (X(( + (28-Idw
(31)
where X(t) is the stochastic process associated with the particle's position x(t). In our experiments, the potential is given by:
21
2
V (x)
(32)
20
40
which makes X()
dimensional Ornstein-Uhlenbeck process with temperature parameter /23--I set to 0.3. Further, Ex--pt..) [V] (in Eqn 8) is estimated via Monte-Carlo sampling, the differential entropy Ex=p(.r) [log p(-,t) via non-ooonnann pormmmrretr estimator (Kozachenko Leonenko 1987 Kraskov et al. 2004 Gao et al. 2015), and the linear transform coefficients for H via linear regression.
We train a two-layer deep, 512-unit wide network on 8092 trajectories of length 64 for 20000 steps of stochastic gradient descent with Adam (learning rate: 0.0001). The batch-size set 1024 and the network is regularized by weight decay (with coefficient 0.0005). Fig 22g222 shows the learned h-potential as a function of position x. Fig 6 compares the free-energy functional with the learnt arrow of time given by the linearly scaled H -fffucctioal. To obtain the linear scaling parameters for the H, we find parameters w and 6 such that Σ Ei [p(, t)] + Flp(-,+)]) is minimized (constraining w to be positive), i.c by solving a linear regression problem. Finally, Fig 22 plots h as a function of state x E 22, whereas Fig 6 shows that after appropriate (linear) scaling, the learned H largely agrees with the true F.
We tried refining the h-potential with few iterations of bootstrapping, but that did not significantly change the result.
25

---

Published as a conference paper at ICLR 2020
The linear adjustment is done to account for the arbitrary scaling of H and F; the crucial detail that H is also a Lyapunov functional of the dynamics, ie.. it decreases montonously with time. This arbitrariness results from various aspects. First, observe that while the dynamics in Equ 31 is invariant to a constant shift in potential V the Free Energy functional is not from Eqn g we that adding constant to the potential V results in the same constant being added to F (for all
t). This justifies adding a constant shift to H as appropriate. Moreover, the scale of h-potential is controlled by the regularizing coefficient A, which is arbitrary with respect to the scale of the Free Energy functional F.
26


Reviews:
[{"review_id": "H1xTTMZW5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI 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.\n\n----\n\nIn 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.)\n\n----\n\nWhen 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.\n\nOne 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.\n\n----\n\nIn 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))?\n\n----\n\n(This section did not affect my assessment of the paper)\n \nHave 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.\n\n----\n\nThere 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.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BygOxqxSYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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.\n\nThis 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.\n\nI 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.\n\nI have a few questions that I hope the authors can address.\n\n1) 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? \n\n2) 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.\n\n3) 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.\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJxZ6kgRKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nI found many of the ideas thought-provoking. The paper is also well written and a pleasure to read.\n\nBut 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. \n\nAs 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.\n\nMinor comments:\n-\tTop of p.3: Can you give some intuition for h(), e.g. relation to entropy over trajectory.\n-\tBottom 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?\n-\tFootnote 2, p.4.  It would be interesting to expand on this point.\n\n==============\nUpdate post-rebuttal:\nIndeed, 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.\nBut 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.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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)