Title: No title found

Abstract: We develop a normative theory of hierarchical model-based policy optimization for Markov decision processes resulting in a full-depth, full-width policy iteration algorithm. This method performs policy updates which integrate reward information over all states at all horizons simultaneously thus sequentially maximizing the expected reward obtained per algorithmic iteration. Effectively, policy path programming ascends the expected cumulative reward gradient in the space of policies defined over all state-space paths. An exact formula is derived which finitely parametrizes these path gradients in terms of action preferences. Policy path gradients can be directly computed using an internal model thus obviating the need to sample paths in order to optimize in depth. They are quadratic in successor representation entries and afford natural generalizations to higher-order gradient techniques. In simulations, it is shown that intuitive hierarchical reasoning is emergent within the associated policy optimization dynamics.

1. INTRODUCTION:

Reinforcement learning algorithms can leverage internal models of environment dynamics to facilitate the development of good control policies (Sutton & Barto, 2018) . Dynamic programming methods iteratively implement one-step, full-width backups in order to propagate reward information across a state-space representation and then use this information to perform policy updates (Bellman, 1954) . Stochastic approximations of this approach underpin a wide range of model-free reinforcement learning algorithms which can be enhanced by the ability to query samples from an "internal" environment model as in the DYNA architecture (Sutton, 1990) . State-space search strategies apply heuristic principles to efficiently sample multi-step paths from internal models and have formed a core component of recent state-of-the-art game playing agents (Silver et al., 2016) . Model-based policy search (Deisenroth & Rasmussen, 2011; Abdolmaleki et al., 2015) and gradient methods (Sutton et al., 1999) require sampled paths to approximate policy gradients based on either pure Monte Carlo estimation or by integrating long-run value estimates. All such methods rely on alternating between simulating paths over various horizons and then using this information to improve the policy either directly or indirectly by backing up value estimates and then inferring a policy (Sutton & Barto, 2018; Puterman, 1994) . In this study, we introduce policy path programming (3P) which, given an environment model, normatively improves policies in a manner sensitive to the distribution of all future paths without requiring multi-step simulations. In particular, path programming follows the unique trajectory through policy space which iteratively maximizes the expected cumulative reward obtained. We develop 3P for entropy-regularized discounted Markov decision processes (Levine, 2018) .

In the entropy-regularized MDP framework, a policy complexity penalty is added to the expected cumulative reward objective (Levine, 2018) (see Section 2 for details). Entropy regularization has several implications which have been investigated previously. The entropy penalty forces policies to be stochastic thereby naturally integrating an exploratory drive into the policy optimization process (Ahmed et al., 2018) . In particular, the optimal policy can be immediately derived using calculus of variations as a Boltzmann-Gibbs distribution and reveals a path-based consistency law relating optimal value estimates and optimal policy probabilities which can be exploited to form a learning objective (Nachum et al., 2017) . Furthermore, several studies have successfully used the relative entropy penalty to impose a conservative policy "trust region" to constrain policy updates thereby reducing erroneous policy steps due to the high variance in gradient estimation (Azar et al., 2012; Schulman et al., 2015) . With this setup, we seek to compute this gradient exactly based on a consideration of the distribution of all possible paths that the currently estimated policy will generate. Therefore, we express the MDP objective as a "sum-over-paths" and develop our model in this representation.

In the sum-over-paths formalism (Kappen, 2005; Theodorou et al., 2013) , the central object of interest is not a state-action pair (Fig. 1A ), as is the standard perspective in reinforcement learning in discrete MDPs, but complete state-action sequences or paths (Fig. 1B ). The entropy-regularized cumulative reward objective can be re-written in terms of paths and a path policy can be expressed as an assignment of a probability to each path individually (see Section 3 for details). Gradient ascent in the space of policies over paths integrates information over all possible future paths in expectation at every step. 3P is defined as the gradient ascent algorithm which performs policy updates with respect to this path gradient. As a policy iteration method, we show that this is analogous to full-depth, full-width backups. Furthermore, we describe the associated natural path gradient which is fundamentally distinct from previous natural gradient techniques which utilize the asymptotic time limit of local, state-specific, natural policy gradients (Kakade, 2001; Peters et al., 2005) . In Section 2, we summarize the mathematical framework of entropy-regularized MDPs from the path-based perspective and define our notation. In Section 3, we derive policy path programming. In Section 4, we apply the algorithm in state-spaces drawn from a variety of domains and analyze the resulting policy optimization dynamics. We conclude with a discussion in Section 5. Full-width, one-step backups Full-width, full-depth backups We develop the path programming formalism in the context of stochastic environmental dynamics. A state-space X is composed of states x ∈ X and the policy π(a j |s i ) describes the probability of selecting action a j in state s i . (2)

2. BACKGROUND AND NOTATION:

The environment dynamics are expressed in the function p(s k |s i , a j ) which denotes the probability of transitioning to state s k after selecting action a j in state s i . The MDP objective as a sum-over-paths (Kappen, 2005; Theodorou et al., 2013) is

EQUATION

where the angled brackets • p denote the expectation operation over the path density p. The form of the MDP objective in Equation 3 expresses a sequential decision-making problem as the determination a single decision but over paths. From this point of view, the max operation in Eqn. 3 is a full-width, full-depth policy iteration which converges in one step. We use the term full-depth because the paths incorporate information over all horizons (thus deep in time) and the term full-width because the max operation considers all paths (Fig. 1D ). In contrast, policy iteration algorithms use full-width, one-step backups (Fig. 1C ). This full-depth, full-width max operation is intractable since it requires a search over all possible paths and so we relax this problem using entropy regularization.

In the entropy-regularized reinforcement learning framework (Levine, 2018) , a policy description length penalty for each path u weighted by a temperature parameter τ is added to the MDP objective (Eqn. 3). The relative entropy regularizer D KL [π||π 0 ] measures policy complexity as the deviation from a prior (possibly non-uniform) policy π 0 (Todorov, 2007; Kappen et al., 2012; Theodorou et al., 2013) . In this case, the policy description length penalty is -τ log π(a|s) π 0 (a|s) and the resulting entropy-regularized transition rewards J ijk := J(s i , a j , s k ), path rewards J(u), and policy objective J [π] are then

EQUATION

)

where we have made use of the compressed notation π ij ≡ π(a j |s i ) and p 0 (u) := p(s +1 |s, a)π 0 (a|s).

From an information-theoretic point of view, the optimal policy π * which maximizes J [π] gives the best trade-off between maximizing reward and minimizing policy encoding costs. An implication of the description length penalty is that encoding deterministic transitions is infinitely costly [log π(a|s) → -∞ as π(a|s) → 0] and therefore the optimal policy will be stochastic. Taking the temperature parameter to zero τ → 0 recovers the standard MDP problem of identifying a deterministic policy in pursuit of maximum expected cumulative reward.

In the main text, policy path programming (3P) is developed for entropy-regularized MDPs with stochastic environment dynamics. It is straightforward to derive analogous update equations in the presence of deterministic environmental transitions which correspond to the subset of control problems known as KL-control (Kappen et al., 2012) or linearly-solvable Markov decision processes (Todorov, 2007) ). Furthermore, our analysis can be applied to MDPs with absorbing states. Thus, path programming can be applied to a broad class of MDPs.

3. POLICY PATH PROGRAMMING IN DISCRETE MARKOV DECISION PROCESSES:

The policy objective function (Eqn. 4) can be re-expressed as

EQUATION

where we have expressed the objective (Eqn. 4) in terms of counters n ijk (u) which quantify the number of times that s k is occupied after selecting action a j in state s i on path u. We reparametrize the policy parameters π ij in terms of natural parameters A ij in an exponential model π ij := e Aij (Nagaoka, 2005) . These natural parameters are examples of action preferences in reinforcement learning parlance1 (Sutton & Barto, 2018) and can take any negative real value. Substituting

EQUATION

where C ijk := log p ijk and A 0 ij := log π 0 ij has been analogously substituted, and n is a tensor with components n ijk and [A] ij := A ij have been used for the event counters and action preferences respectively. Considering the set of probabilities e (A+C)•n(u) parametrized by A as an exponential family (Nagaoka, 2005) , the vector n of transition counters n ijk (u) constitutes a sufficient statistic for the path u. Given that the policy transition probabilities π ij = e Aij are drawn from the action preferences A ij ∈ R -via an exponential transformation, we are guaranteed that 0 < π ij ≤ 1 for all state-action combinations.

In order to ensure that π t always forms a probability distribution at every state, we eliminate a redundant action preference at each state. This is accomplished by defining an arbitrary transition probability at each state in terms of the probabilities of alternative transitions at that state. We index this dependent action preference using an ω subscript as in A iiω in order to distinguish it from the independent action preferences which will be directly modified during policy optimization. We define i ω as the action index of an arbitrary action available in state s i . Under the local policy normalization constraint, the action preferences are equivalently constrained via

A iiω = log   1 - ai ω =aj ∈Ai e Aij   . (7) 3.1 PATH GRADIENT CALCULATION

The goal is to iteratively update the action preferences A t characterizing the current policy by gradient descent

EQUATION

)

where I is the Fisher information of the path probability density which naturalizes the gradient, and α is the stepsize. The partial derivatives underpinning the path policy gradient are derived using Corollary B.3.1 and Corollary B.2.1 which can be found in Section B of the Supplementary Material (SM).

Theorem 3.1. The policy path gradient in the exponential parametrization is defined by the partial derivatives

∂ Aij J [A] = s k ∈S a l ∈A k C ij,kl -e Aij -Aii ω C iiω,kl J kl (9)

where C ij,kl := n ij (u)n kl (u) p are state-action correlation functions and J kl := J(s i , a j , s k ) p(s k |si,aj ) .

Proof.

∂ Aij J [A] = ∂ Aij u∈U p(u)J(u) = u∈U ∂ Aij p(u) J(u) + u∈U p(u) ∂ Aij J(u) = u∈U ∂ Aij p(u) J(u) (⇐ Corollary B.3.1) = u∈U p(u) n ij (u) -e Aij -Aii ω n iiω (u) J(u) (⇐ Corollary B.2.1) = u∈U p(u) n ij (u) -e Aij -Aii ω n iiω (u)     s k ,sm∈S a l ∈A k n klm (u)J klm     = s k ,sm∈S a l ∈A k n ij (u)n klm (u) p -e Aij -Aii ω n iiω (u)n klm (u) p J klm = s k ,sm∈S a l ∈A k C ij,kl -e Aij -Aii ω C iiω,kl p klm J klm = s k ∈S a l ∈A k C ij,kl -e Aij -Aii ω C iiω,kl J kl .

A closed-form expression for the state-action correlations C ij,kl is derived using Markov chain theory (Kemeny & Snell, 1983) . The Fisher information I with respect to the path density is calculated in Section B.2 (SM).

3.2. ALGORITHM SUMMARY AND INTUITION:

Based on these derivations, the policy path programming algorithm in the exponential parametrization which implements the updates in Eqn. 8 is:

π t ij := e A t ij T t ij := a i ∈Ai π t ii p ii j ∀s i , s j ∈ X D t ij = (I -λT ) -1 ij E t (ij)k := P D t (ij)k C t ij,kl = D t 0i e A t ij δ ik δ jl + D t 0i E t (ij)k + D t 0k E t (kl)i e A t ij e A t kl I t ij,kl = C t ij,kl -e A t kl -A t kkω C t ij,kkω -e A t ij -A t iiω C t kl,iiω + e A t ij +A t kl -A t iiω -A t kkω C t iiω,kkω J t kl = R kl -τ A t kl + τ A 0 kl A t+1 ij ← A t ij + α xm,xn∈X I t mn,ij -1    s k ,x l ∈X C t ij,kl -e A t ij -A t iiω C t iiω,kl J t kl    (10) A t+1 iiω = log   1 - xi ω =sj ∈Xi e A t+1 ij   .

where λ is a free parameter controlling the agent's "foresight" or how far into the future it can "see". 3P requires that 0λ < 1 in order to ensure that the components of the path gradient expression converge to finite quantities. This parameter can also be conceptualized as a standard reward discount parameter γ as in discounted MDPs. Note that the regularized transition reward J, transient transition matrix T , successor representation D, Fisher information I, and counter correlations C, all depend on the current policy estimate π t . The initialization of action preferences A 0 ij is discussed in the SM (subsection B.3). In all simulations, we fix the foresight λ = 0.99 (thus simulating an "expert" planner with "deep" foresight), the stepsize α = 0.001 (chosen such that 3P tracked the policy evolution at high precision for the purposes of visualization), and the temperature τ = 1 (taking the natural default parameter). In future work, we will explore the implications of reducing λ to simulate a planner with short "foresight" and using the path Hessian to optimize α. The temperature τ controls the policy stochasticity which has been explored previously in model-free (Ahmed et al., 2018) and model-based (Azar et al., 2012) reinforcement learning.

The path gradient (Eqn. 10) has several intuitive properties. For each state, it backups rewards from all other states based on all future paths thus implementing a full-depth, full-width update from a dynamic programming point of view (Sutton & Barto, 2018) . The matrix D is the successor representation (Dayan, 1993 ). An entry D ij counts the expected number of times that state s j will be occupied after starting from state s i . Therefore the counter correlations C, which is quadratic in successor representations, reflect the rate of co-occurrence of pairs of state-actions on average under the policy-generated path distribution. This enables the algorithm to understand the correlative structure of state occupations under the current policy. For example, if a temporally remote action s k → x l has high reward J kl and if there is a high counter correlation C ij,kl between a local action s i → s j and the remote action (over all horizons), then the reward J kl associated with the remote action will be weighted heavily in the path gradient and added to the local action preference A ij . The magnitude of this backup is explicitly normalized with respect to a baseline counter correlation C iiω,kl associated with the dependent action preference. That is, if the action s i → x iω is also strongly correlated with s k → x l then the backup to A ij is attenuated since the unique contribution of s i → s j in generating s k → x l is diminished. Using such attributional logic, path programming updates action preferences based on the degree to which a state-action independently leads to rewarding state-space paths over all depths.

4. SIMULATIONS:

We simulate path programming (Eqn. 10) in a variety of simple reinforcement learning environments in order to gain insight into the dynamics of the policy iteration process.

4.1. ANALYSIS:

After running policy path programming until convergence, its dynamics are interrogated using two measures. The first measure is the KL-divergence between the policy densities at each iteration π t and the prior policy π 0 . We compute this policy divergence measure PD locally at each state x ∈ X :

EQUATION

Policy divergence quantifies the degree to which the algorithm is modifying the local policy at each state as a function of planning time. The second measure is the difference between the expected number of times a state will be occupied under the currently optimized policy versus the prior policy. Specifically, the counter difference measure CD is

EQUATION

)

where x 0 is the initial state. Counter differences shows how path programming prioritizes the occupation of states in time. We study these measures as well as their time derivatives in their original form as well as after max-normalizing per state in order to facilitate comparisons across states:

EQUATION

4.2. EXPERIMENTS:

We implement path programming in decision trees (Fig. 2 and Fig. S1 , SM), the Tower of Hanoi problem (Fig. 3 and Fig. S2 , SM), and four-room grid worlds with and without a wormhole (Fig. 4 and Fig. S4 , SM). The decision tree example shows how path programming optimizes with respect to the path structure of the environment, the Tower of Hanoi example highlights its intuitive hierarchical qualities, and, in the grid worlds, the capacity of 3P to radically alter its dynamics in response to the state-space modifications is observed.

In the decision tree environments, 3P implements a backward induction strategy from the terminal goal node to the initial state along the optimal path. Path programming increases the probability of the agent moving along the optimal path only and leaves all other paths untouched throughout the policy optimization process. The added decision complexity at state 2 Fig. 2A is reflected in the total policy divergence at that state and consequently the time-to-peak as compared to the other states along the optimal path.

In our Tower of Hanoi simulation (Fig. 3 ), the agent is endowed with the ability to remain at a state thus the optimal policy is to transit to state G and then choose to remain there (since it can then accumulate a reward on every time step). When path programming, the agent prioritizes the adaptation of its policy so that it remains at the goal state. This can be observed in the relatively rapid policy divergence2 PD at the goal state (Fig. 3B ) and the fact that the policy divergence velocity peaks for the goal state before all others (Fig. 3D ). The second highest priority is assigned to bottleneck states along the optimal path. The optimization of the local policy at the start state is deferred to last. Through the counter difference measure CD, we can observe how path programming increases the occupation density of all states in the same cluster as the goal state (in blue) before subsequently reducing the occupation density of non-goal states in the goal cluster (Fig. 3E ). These non-monotonic counter difference trajectories suggest that path programming treats all blue states as a single unit initially before refining its planning strategy to distinguish individual states within the goal cluster.

Increasing the resolution at which it distinguishes states over time as well as prioritizing local policy adaptations starting with the goal state through the bottleneck states and ending with the start state, suggests that path programming is sensitive to the hierarchical structure of the state-space. In the SM, Figure 2 : Decision tree with added decision complexity. Panels as in Fig. 3 . A higher local policy divergence at state 2 is observed (as compared to Fig. S1 ). we present the results of path programming under an alternative scenario whereby the agent is reset back to the start state on arrival at the goal (Fig. S3 , SM).

In the room world simulation (Fig. 4 ), the agent must navigate from the start state S in the northwest room to the goal state G in the southeast room (panel A). It can do so via a path through the other rooms or, for the shortest route, step through the "wormhole" W from the northwest room directly to the southeast room. We compare policy path programming in this scenario against the same scenario but with the wormhole removed (Fig. S4 , SM). Despite the relatively minor modification to the transition structure of the state-space, policy path programming restructures its processing with the key distinction being that policy path programming prioritizes the wormhole at the earliest stages of processing. Specifically, the policy at the wormhole entrance initially diverges most rapidly from its prior policy (Fig. 4B , red line, long dashes) is due to the steepest acceleration in PD (Fig. 4C ).

Conversely, the wormhole exit is prioritized based on the counter difference measure CD (Fig. 4E , blue line, long dashes). This shows that path programming begins with policy improvements which ensure that the agent makes use of the wormhole. 

5. DISCUSSION:

We introduced a novel natural gradient procedure sensitive to the on-policy path density. If the environmental model is known, then this gradient can be computed in analytically. As a policy iteration procedure, policy path programming implements full-depth, full-width backups in contrast to other dynamic programming methods (operating on tabular representations) which use one-step, full-width backups (Sutton & Barto, 2018) . In previous work, natural policy gradient and actor-critic methods (Kakade, 2001; Bagnell & Schneider, 2003; Peters et al., 2005) have modified standard policy search methods using Fisher information matrices in order to perform policy updates in a manner that is sensitive to the KL-divergence between old and new local policies on average at each state. However, the definition of the natural path gradient used in these studies diverges from that elucidated here in a crucial way. They define the Fisher information matrix asymptotically in time which converges to the average of the local natural policy gradients at each state weighted by the induced stationary state distribution. This implies that these Fisher information matrices do not relate the parametrization of the policy gradient across time as in our method and thus is agnostic to the structure of the state-space. Indeed, in the action preference parametrization used here, the time-asymptotic Fisher information matrix will be diagonal. Though this time-asymptotic method is the only way to define a convergent metric for infinite horizon MDPs, it is not necessary for discounted (or episodic) MDPs as revealed in this study. The specific natural path gradient introduced here results in a hierarchical model-based policy optimization which, we suggest, may serve as a normative process model of optimal planning.

Policy path programming may be leveraged as a theoretic tool for analyzing the hierarchical structure of policy space since functional relationships between actions over all spatiotemporal scales are explicitly embedded within policy path gradients. This can be observed in the policy optimization dynamics generated by policy path programming. In the classic hierarchical tasks simulated here, path programming implicitly prioritizes policy improvements at critical bottleneck states, the evolution of occupation densities over states are dynamically clustered then distinguished (Fig. 3 ), and the policy evolution can be restructured in order to take advantage of shortcuts when available at the earliest stages of processing (Fig. 4 ). Whereas these effects manifest the output of path programming, it may be informative to explore the internal dynamical structure of path programming by analyzing how the counter correlation functions evolve over time.

As with other dynamic programming methods, path programming does not scale however it may provide some insights for developing novel scalable algorithms. For example, the path gradient components C ij,kl -e Aij -Aii ω C iiω,kl J t kl (Eqn. 10) may form an alternative, potentially more stable, objective for reinforcement learning based on path consistency (Nachum et al., 2017) since they will equal zero only at the globally optimal policy. Furthermore, the state-action counter correlation functions C ij,kl may integrated with function approximation methods in order to derive value representations which linearize the natural path gradient in a manner analogous to asymptotic natural gradient methods Kakade (2001) . Indeed, algorithms already designed to learn function approximators based on the successor representation could be adapted to this purpose (Barreto et al., 2016) . While the successor representation facilitates the rapid evaluation of a policy, path gradients enable one to immediately improve a policy. In this respect, path programming reflects a shift from a representation learning strategy based on policy evaluation (Dayan, 1993) to one based on policy improvement. Importantly, policy path gradients exhibit the key successor representation property of decoupling the environment representation from the reward function and thus the same correlation functions can be flexibly transferred across tasks.

A EXTENDED SIMULATIONS AND ANALYSIS:

A.1 DECISION TREES In Fig. S1 (main text), and Fig. 2 , we apply path programming to a series of decision trees of increasing complexity. The agent acquires a reward of 10 points on arrival at the goal state G and is then teleported back to the start state S in order to play again.

Figure S1 : Breadth two, depth three decision tree. Panels as in Fig. 3 . A. The state-space graph of a breadth two, depth three decision tree. States on the optimal path are highlighted in blue. Edge thickness reflects the optimal policy. According to the normalized policy divergences PD, path programming prioritizes policy optimization in state 4, then state 2, and then the start state S. This is reminiscent of a backward induction strategy. The counter differences CD shows that path programming smoothly increases the probability that the agent will occupy the optimal path at the expense of all other paths. Figure S3 : Tower of Hanoi with forced resets on arrival at the goal. Instead of having the option to remain at a goal state, we consider an alternative scenario in which the agent is automatically transported back to the initial state on after arriving at the goal. The path gradient dynamics are broadly similar and retain their hierarchical characteristics however the prominence of the goal state is diminished both in terms of policy divergence (since the agent no longer has any choice at the goal state) and counter difference (since they goal state can no longer be repeatedly exploited for reward). 

B POLICY PATH PROGRAMMING IN THE EXPONENTIAL PARAMETRIZATION:

We derive results which are used to compute the gradient of J [π] (Eqn. 6) with respect to the parameters A ij = log π ij in the main text.

B.1 PRELIMINARY CALCULATIONS:

In this section, we record several complementary calculations.

Proposition B.1. The partial derivative ∂ Aij A kl of an independent action preference A kl with respect to another independent action preference A ij is

EQUATION

The partial derivative ∂ Aij A kkω of a dependent action preference A kkω with respect to an independent action preference A ij is

EQUATION

Proof. Eqn. 14 follows by definition. For Eqn. 15, we recall the constraint equation for dependent action preferences 

∂ Aij A kkω = ∂ Aij   log   1 - a kω =a l ∈A k e A kl

EQUATION

)

and its path-expectation is zero for all action preferences.

Proof. Since ∂ Aij J(u) = -∂ Aij [log π(u)].

B.2 FISHER INFORMATION:

State transition occupations are not independent. Modifying one transition occupation probability under the policy π may change the occupation probability of another transition. This is in contrast to the expected reward objective in path space where policy modifications are independent along each path dimension (apart from an overall normalization factor). In order to identify a policy gradient in transition space with independent gradient components, we will transform the gradient derived in Section 3 into the natural path gradient pulled back to transition space. In order to make this gradient ascent natural in the space of transitions, we pre-multiply the gradient by the inverse Fisher information I -1 (Kakade, 2001) which relates the policy densities in path space π and transition

:

In particular, these action preferences converge to optimal advantage values(Levine,

2018).

Here, we present normalized policy divergence curves to facilitate comparisons across states. The equivalent unnormalized curves may be found in the Fig.S2, SM.

Figures and Tables:

Figure 1: A. State-action representation of a simple state-space with recurrency and terminal states. B. A path space representation of the same state-space. C. A backup diagram(Sutton & Barto, 2018) where each full-width, one-step backup is color-coded by state. D. A backup diagram of the full-width, full-depth backups performed by policy path programming.

Figure 3: Path programming the optimal policy in the Tower of Hanoi game. A. Tower of Hanoi state-space graph. B-C. Normalized policy divergence PD and its time derivative for each state. The color of the curve indicates which state it corresponds to in panel A. Dotted lines correspond to bottleneck states marked + in panel A. Lines for states which are not along the optimal path are plotted transparently. D. Policy value as a function of planning time. Time-to-max policy divergence velocities (i.e. the peaks of the curves in panel C) are dotted along the policy value curve for states along the optimal path. E-F. Normalized counter difference CD and its time derivative.

Figure 4: Path programming the optimal policy in a grid world with a wormhole. Panels as in Fig. 3. Dotted lines with short dashes correspond to bottleneck states marked + in panel A. Dotted lines with long dashes correspond to wormhole states marked W in panel A. The darkness of the state coloring reflects state occupation density under the optimal policy.

Figure S2: Tower of Hanoi with the option to remain at a state. Panels as in Fig. 3. We present an extended set of results. Panels C, D, G, and H have already been displayed in Fig. 3 while panels A, B, E, and F show their unnormalized counterparts.

Figure S4: Path programming the optimal policy in a grid world without a wormhole. Panels as in Fig. 3. Dotted lines with short dashes correspond to bottleneck states marked + in panel A. Dotted lines with long dashes correspond to wormhole states marked W in panel A. Darker state colors indicate higher densities of state occupation under the optimal policy.

ik -e A kj = -δ ik e A kj -A kkω .(16)Proposition B.2. The partial derivatives of the log path density log p(u) and log path policy log π(u) with respect to action preference A ij is∂ Aij [log p(u)] = ∂ Aij [log π(u)] (17) = n ij (u) -e Aij -Aii ω n iiω (u) . Aij log p(u) = ∂ Aij log π(a|s) + log p(s +1 |s, a) = ∂ Aij [A • n(u)] kω =a l ∈A k A kl n kl (u) + A kkω n kkω (u) kω =a l ∈A k ∂ Aij A kl n kl (u) + ∂ Aij A kkω n kkω (u)   = n ij (u) -e Aij -Aii ω n iiω (u)(19)based on the results in Prop. B.1.Corollary B.2.1. The partial derivative of the path density p(u) with respect to action preferenceA ij is ∂ Aij log p(u) = p(u) n ij (u) -e Aij -Aii ω n iiω (u) . (20)Proof. Using the log-derivative trick∂ Aij p(u) = p(u)∂ Aij [log p(u)].Proposition B.3. The path-expectation of the partial derivatives of log p(u) and log π(u) with respect to an action preference is zero:u∈U p(u) ∂ Aij log p(u) = 0 . (21)Proof. Proving for log p(u)u∈U p(u) ∂ Aij log p(u) = u∈U p(u) n ij (u) -e Aij e Aii ω n iiω (u) = n ij (u) p -e Aij e Aii ω n iiω (u) p = C ij -e Aij -Aii ω C iiω .(22)The two-point state counter correlations C ij can be expressed in terms of the successor representation D and policy π ij = e Aij as C ij = D 0i e Aij . Therefore, we continue u∈U p(u) ∂ Aij log p(u) = -τ D 0i e Aij + τ e Aij -Aii ω D 0i e Aii ω = -τ D 0i e Aij + τ D 0i e Aij = 0 . (23) Corollary B.3.1. The partial derivative of the regularized path reward term J(u) with respect to A ij is

The action set A is the union of the sets of actions available at each state A = ∪ si∈S A i .A valid state-action sequence u := (. . . , s t , a t , s t+1 , a t+1 , . . .) is referred to as a state-action path.

Table content: <table><tr><td colspan="3">The path probability p(u) is defined as the joint distribution over states s and actions a</td></tr><tr><td colspan="2">∞</td><td/></tr><tr><td>p(u) :=</td><td colspan="2">p(s t+1 |s t , a t )π(a t |s t ) = p(s +1 |s, a)π(a|s)</td><td>(1)</td></tr><tr><td colspan="2">t=0</td><td/></tr><tr><td>where</td><td/><td/></tr><tr><td>∞</td><td>∞</td><td/></tr><tr><td>π(a|s) :=</td><td>π(a t |s t ) , p(s +1 |s, a) :=</td><td>p(s t+1 |s</td></tr><tr><td>t=0</td><td>t=0</td><td/></tr></table>

Peer review (iclr2020):
The paper considers the problem of entropy-regularized discounted Markov decision processes with discrete state space. Instead of working on the parameter space of policy (pi_ij), the paper has proposed to reparametrize with natural parameters (A_ij). The reparameterization trick helps to learn the natural parameters using the natural gradient method. The writing is easy to follow. However, it is not clear what is the benefit of learning policy using path representation compared with other methods in the literature. The paper does not clearly state the motivation of the proposed method. The experimental section presents the convergence of the proposed methods in 3 small problems including decision trees of four levels, the tower of Hanoi problem, and four-room grid worlds. The experiment setting is very simple with a small number of states in the policy. It is not clear how the proposed method is able to scale up the size of state space. Besides, there is no baseline method in the literature to be presented to compare with the proposed method.