Year: 2019

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 BACKGROUND AND NOTATION
text: A B
Path representation
State-action representation
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 π(aj |si) describes the probability of selecting action aj in state si. The reward associated with transitioning from state si to state sk after selecting action aj is denoted R(si, aj , sk) ≡ Rijk. Bold-typed notation, s ∈ S, a ∈ A, and u ∈ U denotes sequences of states s ∈ S, actions a ∈ A, and state-action combinations u ≡ (su, au) ∈ U respectively. The action set A is the union of the sets of actions available at each state A = ∪si∈SAi.
A valid state-action sequence u := (. . . , st,at, st+1,at+1, . . .) is referred to as a state-action path. The path probability p(u) is defined as the joint distribution over states s and actions a
p(u) := ∞∏ t=0 p(st+1|st,at)π(at|st) = p(s+1|s,a)π(a|s) (1)
where
π(a|s) := ∞∏ t=0 π(at|st) , p(s+1|s,a) := ∞∏ t=0 p(st+1|st,at) . (2)
The environment dynamics are expressed in the function p(sk|si, aj) which denotes the probability of transitioning to state sk after selecting action aj in state si. The MDP objective as a sum-over-paths (Kappen, 2005; Theodorou et al., 2013) is
π∗ := argmax π 〈R(u)〉p
R(u) = ∞∑ t=0 R(st,at, st+1) (3)
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 DKL[π||π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 Jijk := J(si, aj , sk), path rewards J(u), and policy objective J [π] are then
Jijk := Rijk − τ log πij + τ log π0ij
J(u) := ∞∑ t=0 J(at, st, st+1)
= R(u)− τ logπ(a|s) + τ logπ0(a|s) = R(u)− τ logp(u) + τ logp0(u)
J [π] = 〈J(u)〉p = −τDKL [ p(u)||p0(u)eτ −1R(u) ] . (4)
where we have made use of the compressed notation πij ≡ π(aj |si) and p0(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.

heading: 3 POLICY PATH PROGRAMMING IN DISCRETE MARKOV DECISION PROCESSES
text: The policy objective function (Eqn. 4) can be re-expressed as
J [π] = ∑ u∈U ∏ si,sk∈S aj∈Ai (πijpijk) nijk(u)  ∑ si,sk∈S aj∈Ai nijk(u) [ Rijk − τ ( log πij − log π0ij )] s.t. πij > 0 ∀si ∈ S, aj ∈ Ai ,
∑ aj∈A πij = 1 ∀si ∈ S (5)
where we have expressed the objective (Eqn. 4) in terms of counters nijk(u) which quantify the number of times that sk is occupied after selecting action aj in state si on path u. We reparametrize the policy parameters πij in terms of natural parameters Aij in an exponential model πij := eAij (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 Aij := log πij ,
J [A] = ∑ u∈S eA·n(u)+C·n(u)  ∑ si,sk∈X aj∈Ai nijk(u) ( Rijk − τAij + τA0ij ) eA·n(u) = e ∑ si,aj,sk Aijnijk(u) = e ∑ si,aj Aijnij(u)
eC·n(u) = e ∑ si,aj,sk Cijknijk(u) (6)
where Cijk := log pijk and A0ij := log π 0 ij has been analogously substituted, and n is a tensor with components nijk and [A]ij := Aij 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 nijk(u) constitutes a sufficient statistic for the path u. Given that the policy transition probabilities πij = eAij are drawn from the action preferences Aij ∈ 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 Aiiω 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 si. Under the local policy normalization constraint, the action preferences are equivalently constrained via
Aiiω = log 1− ∑ aiω 6=aj∈Ai eAij  . (7)

heading: 3.1 PATH GRADIENT CALCULATION
text: The goal is to iteratively update the action preferences At characterizing the current policy by gradient descent
At+1 ← At + αI−1∇AJ [ At ]
(8)
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).
1In particular, these action preferences converge to optimal advantage values (Levine, 2018).
Theorem 3.1. The policy path gradient in the exponential parametrization is defined by the partial derivatives
∂AijJ [A] = ∑ sk∈S al∈Ak [ Cij,kl − eAij−Aiiω Ciiω,kl ] Jkl (9)
where Cij,kl := 〈nij(u)nkl(u)〉p are state-action correlation functions and Jkl := 〈J(si, aj , sk)〉p(sk|si,aj).

heading: Proof.
text: ∂AijJ [A] = ∂Aij [∑ u∈U p(u)J(u) ] = ∑ u∈U [ ∂Aijp(u) ] J(u) + ∑ u∈U p(u) [ ∂AijJ(u)
] = ∑ u∈U [ ∂Aijp(u) ] J(u) (⇐ Corollary B.3.1)
= ∑ u∈U [ p(u) [ nij(u)− eAij−Aiiωniiω (u) ]] J(u) (⇐ Corollary B.2.1) = ∑ u∈U { p(u) [ nij(u)− eAij−Aiiωniiω (u) ]} ∑ sk,sm∈S al∈Ak nklm(u)Jklm
 =
∑ sk,sm∈S al∈Ak [ 〈nij(u)nklm(u)〉p − e Aij−Aiiω 〈niiω (u)nklm(u)〉p ] Jklm
= ∑
sk,sm∈S al∈Ak
[ Cij,kl − eAij−Aiiω Ciiω,kl ] pklmJklm
= ∑ sk∈S al∈Ak [ Cij,kl − eAij−Aiiω Ciiω,kl ] Jkl .
A closed-form expression for the state-action correlations Cij,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).

heading: 3.2 ALGORITHM SUMMARY AND INTUITION
text: Based on these derivations, the policy path programming algorithm in the exponential parametrization which implements the updates in Eqn. 8 is:
πtij := e Atij T tij := ∑
ai′∈Ai
πtii′pii′j ∀si, sj ∈ X
Dtij = [ (I − λT )−1 ] ij
Et(ij)k := [ PDt ] (ij)k
Ctij,kl = Dt0ieA t ijδikδjl + [ Dt0iE t (ij)k +D t 0kE t (kl)i ] eA t ijeA t kl
Itij,kl = Ctij,kl − eA t kl−A t kkω Ctij,kkω − e Atij−A t iiω Ctkl,iiω + e Atij+A t kl−A t iiω −Atkkω Ctiiω,kkω
J tkl = Rkl − τAtkl + τA0kl
At+1ij ← A t ij + α ∑ xm,xn∈X [ Itmn,ij ]−1 ∑ sk,xl∈X [ Ctij,kl − eA t ij−A t iiω Ctiiω,kl ] J tkl  (10) At+1iiω = log 1− ∑ xiω 6=sj∈Xi eA 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 A0ij 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 Dij counts the expected number of times that state sj will be occupied after starting from state si. 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 sk → xl has high reward Jkl and if there is a high counter correlation Cij,kl between a local action si → sj and the remote action (over all horizons), then the reward Jkl associated with the remote action will be weighted heavily in the path gradient and added to the local action preference Aij . The magnitude of this backup is explicitly normalized with respect to a baseline counter correlation Ciiω,kl associated with the dependent action preference. That is, if the action si → xiω is also strongly correlated with sk → xl then the backup to Aij is attenuated since the unique contribution of si → sj in generating sk → xl 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.

heading: 4 SIMULATIONS
text: 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.

heading: 4.1 ANALYSIS
text: 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 :
PD(x, t) := DKL [ πtx·||π0x· ] (11)
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
CD(x, t) := Dt0x −D00x . (12)
where x0 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:
P̃D(x, t) := PD(x, t)
maxt PD(x, t) , C̃D(x, t) :=
CD(x, t)
maxt |CD(x, t)| . (13)

heading: 4.2 EXPERIMENTS
text: 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 P̃D 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 C̃D, 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,
2Here, we present normalized policy divergence curves to facilitate comparisons across states. The equivalent unnormalized curves may be found in the Fig. S2, SM.
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.

heading: 5 DISCUSSION
text: 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 [ Cij,kl − eAij−Aiiω Ciiω,kl ] J tkl (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 Cij,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.

heading: Appendix

heading: CONTENTS

heading: A Extended simulations and analysis 13
text: A.1 Decision trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
A.2 Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.3 Room world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

heading: B Policy path programming in the exponential parametrization 16
text: B.1 Preliminary calculations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
B.2 Fisher information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
B.3 Initialization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

heading: A EXTENDED SIMULATIONS AND ANALYSIS

heading: A.1 DECISION TREES
text: 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 P̃D, 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 C̃D shows that path programming smoothly increases the probability that the agent will occupy the optimal path at the expense of all other paths.

heading: A.2 TOWER OF HANOI
text: 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 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).

heading: A.3 ROOM WORLD
text: 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.

heading: B POLICY PATH PROGRAMMING IN THE EXPONENTIAL PARAMETRIZATION
text: We derive results which are used to compute the gradient of J [π] (Eqn. 6) with respect to the parameters Aij = log πij in the main text.

heading: B.1 PRELIMINARY CALCULATIONS
text: In this section, we record several complementary calculations.
Proposition B.1. The partial derivative ∂AijAkl of an independent action preferenceAkl with respect to another independent action preference Aij is
∂AijAkl = δikδkl := δij,kl . (14)
The partial derivative ∂AijAkkω of a dependent action preferenceAkkω with respect to an independent action preference Aij is
∂AijAkkω = −δikeAkj−Akkω . (15)
Proof. Eqn. 14 follows by definition. For Eqn. 15, we recall the constraint equation for dependent action preferences
∂AijAkkω = ∂Aij
log 1− ∑
akω 6=al∈Ak
eAkl  =
1− ∑ akω 6=al∈Ak eAkl −1 δik [−eAkj ] = −δikeAkj−Akkω . (16)
Proposition B.2. The partial derivatives of the log path density logp(u) and log path policy logπ(u) with respect to action preference Aij is
∂Aij [logp(u)] = ∂Aij [logπ(u)] (17)
= nij(u)− eAij−Aiiωniiω (u) . (18)

heading: Proof.
text: ∂Aij logp(u) = ∂Aij [ logπ(a|s) + logp(s+1|s,a) ] = ∂Aij [A · n(u)]
= ∂Aij ∑ sk∈S  ∑ akω 6=al∈Ak Aklnkl(u) +Akkωnkkω (u)  =
∑ sk∈S  ∑ akω 6=al∈Ak ( ∂AijAkl ) nkl(u) + ( ∂AijAkkω ) nkkω (u)  = nij(u)− eAij−Aiiωniiω (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 preference Aij is
∂Aij logp(u) = p(u) [ nij(u)− eAij−Aiiωniiω (u) ] . (20)
Proof. Using the log-derivative trick ∂Aijp(u) = p(u)∂Aij [logp(u)].
Proposition B.3. The path-expectation of the partial derivatives of logp(u) and logπ(u) with respect to an action preference is zero:∑
u∈U p(u)
[ ∂Aij logp(u) ] = 0 . (21)
Proof. Proving for logp(u)∑ u∈U p(u) [ ∂Aij logp(u) ] = ∑ u∈U p(u) [ nij(u)− eAij eAiiω niiω (u) ]
= 〈nij(u)〉p − eAij
eAiiω 〈niiω (u)〉p
= Cij − eAij−Aiiω Ciiω . (22)
The two-point state counter correlations Cij can be expressed in terms of the successor representation D and policy πij = eAij as Cij = D0ieAij . Therefore, we continue∑
u∈U p(u)
[ ∂Aij logp(u) ] = −τD0ieAij + τeAij−AiiωD0ieAiiω
= −τD0ieAij + τD0ieAij
= 0 . (23)
Corollary B.3.1. The partial derivative of the regularized path reward term J(u) with respect to Aij is
∂AijJ(u) = −τnij(u) + τniiω (u)eAij−Aiiω . (24)
and its path-expectation is zero for all action preferences.
Proof. Since ∂AijJ(u) = −∂Aij [logπ(u)].

heading: B.2 FISHER INFORMATION
text: 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
space π. The Fisher information matrix I has components Iij,kl := 〈[ ∂Aij logp(u) ] [∂Akl logp(u)] 〉 p
= 〈[ nij(u)− eAij−Aiiωniiω (u) ] [ nkl(u)− eAkl−Akkωnkkω (u) ]〉 p = 〈nij(u)nkl(u)〉π − e Akl−Akkω 〈nij(u)nkkω (u)〉p +
−eAij−Aiiω 〈nkl(u)niiω (u)〉p + e Aij−Aiiω eAkl−Akkω 〈niiω (u)nkkω (u)〉p
= Cij,kl − eAkl−Akkω Cij,kkω − eAij−Aiiω Ckl,iiω + eAij+Akl−Aiiω−Akkω Ciiω,kkω . (25)
where we have used Prop. B.2. The Fisher information I depends on the counter correlation functions C. The counter correlation functions can be derived using Markov chain theory (Kemeny & Snell, 1983).
B.3 INITIALIZATION
The prior policy π0 can be set to any stochastic policy with corresponding initial action preferences
A0ij = τ log π 0 ij . (26)
Assuming that π0 is initialized at the random policy, we have
π0ij = 1
|Ai| (27)
A0ij = −τ log |Ai| (28)
for all states si ∈ S and actions aj ∈ Ai.

Review summaries:
This work proposes a policy iteration algorithm that implements full-depth, full-width backups in contrast to one-step, full-width methods. The authors go over existing algorithms and talks a bit how their proposal conceptually differs in how it performs said backups. They provide a bit of intuition to help explain their algorithm's derivation. Finally, they provide a few experiments showing that their algorithm works.

The paper considers the problem of finding the optimal policy in the Markovian decision Processes, where a KL policy regularizer is added to the objective function. Instead of the closed form solution which leads  to the KL-regularized Bellman equation the paper proposes to use an incremental gradient ascent algorithm. The paper recommends an iterative policy gradient scheme to  optimize this  objective function. There exists a substantial literature on the subject of KL-regularized RL as well as using the  policy gradient algorithms  to optimize this objective function using policy gradient schemes (See all variants of KL(entropy)-constraint actor-critic or reinforce algorithms, e.g. A2C, IMPALA,...). Unfortunately the paper doesn’t provide any comparison with those methods. In the absence of those comparisons the significance of this work to the literature of RL is not clear, as it is not solving an open problem which hasn't addressed before, neither it  provides theoretical/empirical evidence that it has advanced the start-of-the-art in terms of providing a more efficient solution.