Policy path programming
Authors: Daniel McNamee
Venue:  (2020)
Keywords: markov decision process
planning
hierarchical
reinforcement learning

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.

Under review as a conference paper at ICLR 2020
POLICY PATH PROGRAMMING
Anonymous authors Paper under double-blind review
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 informa- tion over all states 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 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 shown that intuitive hierarchical reasoning is emergent within the associated policy optimization dynamics.
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 propagate reward information across 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 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 core component of recent state-of the-art art game playing agents (Silver al., 2016). Model-based policy search (Deisenroth & Rasmussen| 2011 (Abdolmaleki et al. 2015)) and gradient methods (Sutton 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 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 policy (Sutton & Barto Puterrma) 1994). In this study, we introduce policy path programming (3P) which, given an environment model, normatively improves policies in manner sensitive 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 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- Gibbss 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 (Nchhu et al.) 2017). Furthermore, several studies have successfully used the relative entropy penalty to impose 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 compute this gradient exactly based consideration of

---

Under review as a conference paper at ICLR 2020
the distribution of all possible paths that the currently estimated policy will generate. Therefore, express the MDP objective as a "sum-over-pathh" 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 state-action pair (Fig. [ as Is the standard perspective in reinforcement learning
in discrete MDPs, but complete state-action sequences paths (Fig. [ The entropy-regulariie cumulative reward objective can be re-written in terms paths and path policy can be expressed an assignment of probability to each path individually (see Section [ 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 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 variety of domains and analyze the resulting policy optimization dynamics. We conclude with a discussion in Section 5
BACKGROUND AND NOTATION
A
B
State-action representation
Path representation
TT1
W24
2
T
C
D
Full-width, one-step backups
Full-width, full-depth backups
Figure 1: A. State-action representation of 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.
We develop the path programming formalism the context of stochastic environmental dynamics.
A state-space X' is composed of states X' and the policy Taa (44) describes the probability of selecting action in state s,. The reward associated with transitioning from state 8; to state sy after selecting action 0, is denoted R(s,, $;) Rayk- Bold-typed notation, E S. A, and u U denotes sequences states E S, actions a E A. and state-action combinations u (s a,) E U respectively. The action set A is the union of the sets of actions available each state A = Use
2

---

Under review as a conference paper at ICLR 2020
A valid state-action sequence : (.... St, a,, S1+1, a(+1....) is referred to state-action path. The path probability p(u) is defined as the joint distribution over states s and actions a
puu) = II 1=0
p( St (a s.) p(s s. as)as
(1)
where
π T(als) = II <(al)s))
p(st s. == I |(
(2)
t=0
The environment dynamics expressed in the function p(sk|ss, ag) which denotes the probability of transitioning to state 85 after selecting action aj in state 85. The MDP objective as a sum-over-paths (Kappen 2005 Theodorou al., 2013 is
π
arg max (R(u))p
R(u)
Σ R(s a Sc+1)
(3)
where the angled brackets ()p denote the expectation operation over the path density The form of the MDP objective in [euuation3expressssss sequential decision-making problem the determination a single decision but over paths. From this point of view, the max operation in Eqn. 3 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. DD). In contrast, policy iteration algorithms use full-widthe one-step backups (Fig. [C). This full-depth, full-width max operation is intractable since it requires search over possible paths and so we relax this problem using entropy regularization.
In the engropy--reularrzzed reinforcement learning framework (Levine 2018)
policy description length penalty for each path u weighted by temperature parameter is added the MDP objective
(Eqn. 3). The relative entropy regularizer DKL[Tl|r measures policy complexity the deviation
from prior (possibly non-uniform) policy π (Todoroy. 2007 Kappen et al., 2012 Theodorou
et al. 2013). In this case, the policy description length penalty is -7 log (a]s) and the resulting
entropy-regularize transition rewards Jijk J(s, aj. sk), path rewards (u), and policy objective T [ are then
Jisk
Risk- r log Tiy + +log my
x
J(u) Σ t=
J(a,, Sc,
R(u) T log T (als)) + 7 log n (als)
R(u) T rlogp(u) T log p (u)
J[m] = (J(u)),
DD (u)e RR(u)
(4)
where we have made use of the compressed notation mij a(asls)) and p")
p(st a)T
From an informmtion-thhoreee point of view, the optimal policy "¹ which maximizes T J[m]] gives the best trade-off between maximizing reward and minimizing policy encoding costs. An implica- tion of the description length penalty that encoding deterministic transitions is infinitely costly [log TTaas) (s]s) - -oo as ( - 0] and therefore the optimal policy will be stochastic. Taking the temperature parameter to zero т - recovers the standard MDP problem of identifying 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 KL-control (Kappen et al. (2012) or linearly- (Todorov] (007)) Furthermore, our analysis can be applied to MDPs with absorbing states. Thus, path programming be applied to broad class of MDPs.
Markov decision processes
3

---

Under review as a conference paper at ICLR 2020
3 POLICY PATH PROGRAMMING IN DISCRETE MARKOV DECISION PROCESSES
The policy objective function (Eqn. can be re-expressed as
J
Σ
II
(TajPisk) me)(()
Σ nijk(U) Risk 7 (log vaj - log +by)
uell 8t.84, ES A.E.;
$6,8ESS a,E.A
s.t. Tij >
0
ss, E E. EA:
Σ Tiz=1 =1 4 0,EA
(5)
where we have expressed the objective (Eqn. in terms of counters niya(() which quantify the number of times that sı is occupied after selecting action aj in state s; on path We reparametrize the policy parameters Tij in terms of natural parameters AG in exponential model Try An (Nagaoka 2005). These natural parameters are examples of action preferences reinforcement learning parlance Suttonn & Barto 2018) and take any negative real value. Substituting Agj = log Tij.
J[A]
Σ Cnl(
Σ (u) S a,EA;
(lu)(Ras)) (Riza - TAi + =Ali))
uES
Anfu)) Expiogine Ammas(()) = Exinng (u) 6 C-n(u)
e Empoyie Cisenisu(u)
(6)
where Cigk == Pijk and AG == log mij has been analogously substituted, and n is a tensor with components Miyk and [A] = Aij have been used for the event counters and action preferences respectively. Considering the set of probabilities family [Nagaoka 2005), the vector n of transition counters (u) constitutes a sufficient statistic for the path u. Given that the policy transition probabilities Tij = e are drawn from the action preferences A, TR. via an exponential transformation, we are guaranteed that < mi S 1 for all state-action combinations.
parametrized by A as an exponential
In order ensure that n' always forms probability distribution at every state, we eliminate redundant action preference at each state. This is accomplished by defining arbitrary transition probability each state in terms
probabilities alternative transitions at that state. index this dependent action preference using an subscript in Aa, in order to distinguish it from the independent action preferences which will be directly modified during policy optimization. We define i the action index of arbitrary action available in state s,. Under the local policy normalization constraint, the action preferences are equivalently constrained via
Asi.. = log (1-
1-
Σ
eni )
aiw FajEE
3.1
PATH GRADIENT CALCULATION
The goal is to iteratively update the action preferences A' cchracterizing the current policy by gradient descent
1+1 A' [A]]
where I is the Fisher information of the path probability density which naturalizes the gradient, and a the stepsize. The partial derivatives underpinning the path policy gradient are derived using Corollary B.3. Corollary B.2.1 which can be found in Section of the Supplementary Material (SM).
In particular, these action preferences converge to optimal advantage values Levvie 2018
4

---

Under review as a conference paper at ICLR 2020
Theorem 3.1. The policy path gradient in the exponential parametrization is defined by the partial derivatives
DA J[A]
Σ
CCieet Ans New Cil Jul
R.
where Cij.ul == (m)((u)nu())) are state-action correlation functions and Ju (8i, ag s4) p(salsraa))
Proof.
DA., J(A] DA.,
Σ p(u)
Luek
Σ well
[a p(u)
J(u) + Σ p(u) [
wed
Σ
[a puu) J(u)
(= Corollary B.3.1
uetd
Σ uet/
[p(u)
[nl (u) eA, Ani niw (u)] J(u)
(# Corollary B.2.1
Σ
{p(u) (m)((u) Ans Ady-Auuhh Auw niw (u)
Twim (u) Jkim
a.AA
Σ
(mg(u)) en An (neiw (u)Mkim (w)) Jaim
9L.8m. E.AA
Σ
[Cij.t - Ass A Cis PremmJklm
Sk.8m ES wEAA
Σ
[Coj.Kt Ais Asin kil Jkl
A.A.A
A closed-form expression for the state-action correlations Cıj.ki 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).

---

Under review as a conference paper at ICLR 2020
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. iis:
m = Ais
T = Σ
Pap' Vst, Sg E X
arEA
D = [I XT) -1
Big = [PD' (kj)A
C ji Darethissskjj + Eis Do DonEinuj cdise
Ig = Cis,al Mar - Ci ei Niw Cis + Migy Aag New -Abew
C Chiss kku
J RRI -AAfs + +
A!J' + Alj +
Σ
[mmas]
Σ NONTEE
Cli.ae (oii-Min Clas Citw f'tl Jāa]
(10)
EX
Att1 Aw
=
log
1
Σ
t++l e
Piu #sJEN
where is a free parameter controlling the agent's "foresight" or how far into the future it can "see". 3P requires that 0λ < 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 y 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 n². The initialization of action preferences 44 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 a 0.001 (chosen such that 3P tracked the policy evolution at high precision for the purposes of visualization), and the temperature 7 = 1 (taking the natural default parameter). In future work, we will explore the implications of reducing À simulate planner with short "foresight" and using the path Hessian optimize a. 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. 10p has several intuitive properties. For each state, it backups rewards from all other states based all future paths thus implementing full--eeph, full-width update from a dynamic programming point of view (Sutton Barto 2018). The matrix D the successor representation (Dayan 1993). An entry Dij counts the expected number of times that state 8j will be occupied after starting from state 8;. Therefore the counter correlations C, which is quadratic average in successor representations, reflect the rate of co-occurrence of pairs of state-actions under the policy-generater path distribution. This enables the algorithm to understand the correlative structure of state occupations under the current policy. For example, a temporally remote action 8t + z₁ has high reward JE and if there is a high counter correlation Cij.At between a local action 8; - Sj and the remote action (over all horizons), then the reward J&r 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 Ci. associated with the dependent action preference. That is, if the action 5; - Ii. is also strongly correlated with s - Ii then the backup to Ag is attenuated since the unique contribution of s; 83 in generating $ .z, 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.

---

Under review as a conference paper at ICLR 2020
4 SIMULATIONS
We simulate path programming (Eqn. 10 in a variety of simple reinforcement learning environments in order gain insight into the dynamies 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 nO and the prior policy n". We compute this policy divergence measure PD locally at each state x E X::
PD(x; () DKL. [
(11)
Policy divergence quantifies the degree to which the algorithm is modifying the local policy each state as a function of planning time. The second measure is the difference between the expected number of times state will be occupied under the currently optimized policy versus the prior policy. Specifically, the counter difference measure CD is
CD( == Do= - De=
(12)
where To 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:
PD( PD(x,t) max, PD(r,t)
CD f)
CD(x, == max, CD(2, t)
(13)
4.2 EXPERIMENTS
We implement path programming in decision trees (Fig. 2 and Fig. SI 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. A 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 transit to state G and then choose 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 divergence PD at the goal state (Fig. 3 and the fact that the policy divergence velocity peaks for the goal state before all others (Fig, BP). 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. 3). 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,
Here,, present normalized policy divergence curves to facilitate comparisons across states. The equivalent
unnormalized curves may he found in the Fig. S2 SM.
7

---

Under review as a conference paper at ICLR 2020
State-space
State function
Time derivative
V VV
divergence
40
-200
Counter difference
20
Policy
-50
-300
-10
0.0
1.0
0.2
Time
Time
Time
Figure 2: Decision tree with added decision complexity, Panels in Fig. divergence at state 2 is observed (as compared to Fig. ST
higher local policy
State-space graph
Normalized state function
Normalized time derivative
Polay diergence
0.8
0.8
0.5
0.4
0.0
3000
Counter difference
0.5
Palicy value
2000
0.0
-0.5
-0.5
-1.0
-1.0
Time
Time
Time
Figure 3: Path programming the optimal policy in the Tower 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 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 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.
function of planning time. Time-to-max policy divergence
we present the results of path programming under an alternative scenario whereby the agent reset back 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 the goal state G in the southeast room (panel A). It can do so via path through the other
8

---

Under review as a conference paper at ICLR 2020
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 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 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.
A
Slate-space
State function
Time derivalive
1.2
1.0
1.0
Policy dieergence
0.0
0.6
0.2
0.0
0.0
150
100
Counter differenze
100
Polcy velue
W
10
8
-50
-100
2 Time
0
3
Time
Time
Figure 4: Path programming the optimal policy in grid world with wormhole. Panels in Fig. 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.
DISCUSSION
We introduced novel natural gradient procedure sensitive to the on-policy path density. the environmental model is known, then this gradient can be computed in analytically. As policy iteration procedure, policy path programming implements full-depth, full-width backups in contrast to other dynamic programming methods (operating tabular representations) which use one-step, full-width backups (Sutton Barto 2018). In previous work, natural policy gradient and actor-critic Bagnell
methods (Kakade 20gilBa & Schneider 2003 Peters et al.) 2005) have modified standard policy search methods using Fisher information matrices in order to perform policy updates in manner that sensitive the KL-divergence between old and local policies average each state. However, the definition the natural path gradient used in these studies diverges from that elucidated here in 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 the state-space. Indeed, in the action preference parametrization used here, the time-asymptotic Fisher information matrix will be diagonal. Though this time-asymptotie method the only way to define a convergent metric for infinite horizon MDPs, it is not necessary for discounted (or episodic) MDPs 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.

---

Under review as a conference paper at ICLR 2020
Policy path programming may be leveraged 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 [Ctj,8 A Ais Ci... kt] Jh (Bqn. 10) may form an alternative, potentially more stable, objective for reinforcement learning based path consistency (Nachum al. 2017) since they will equal zero only at the globally optimal policy. Furthermore, the state-action counter correlation functions Cij.Al 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 (200T). Indeed, algorithms already designed 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 policy, path gradients enable one to immediately improve policy. In this respect, path programming reflects a shift from a representation learning strategy based on policy evaluation (Dayan 1993) 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.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Abbas Abdolmalcki, Rudolf Lioutikov, Jan R Peters, Nuno Lau, Luis Pualo Reis, and Gerhard Neumann. Model-based relative entropy stochastic search. Advances in Neural Information Processing Systems, pp. 3523-3523, 2015.
Zafarali Ahmed, Nicolas Le Roux, Mohammad Norouzi, and Dale Schuurmans. Understanding the impact of entropy on policy optimization. arXiv, pp. 181 881..12214: 2018.
Mohammad Gheshlaghi Azar, Vicenç Gómez, and Hilbert J Kappen. Dynamic policy programming.
Journal of Machine Learning Research, 13(Nov):3207-3245 2012.
J Andrew Bagnell and Jeff Schneider. Covariant policy search. 2003.
André Barreto, Rémi Munos, Tom Schaul, and David Silver. Successor features for transfer in reinforcement learning. arXiv, pp. 1-13, 2016.
Richard Bellman. The theory of dynamic programming. Bull. Amer. Math. Soc., 60(6):503-515, 1954.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation.
Neural Computation, 5:613-624, 1993.
Mare Deisenroth and Carl E Rasmussen. Pilco: A model-based and data-efficient approach policy
search. ICML, pp. 465-472, 2011.
Sham M Kakade. natural policy gradient. Advances in Neural Information Processing Systems:
1531-1538, 2001.
HJ Kappen. Path integrals and symmetry breaking for optimal control theory. Journal of Statistical
Mechanics: Theory and Experiment, 2005:21, 2005.
Hilbert J. Kappen, Vicenç Gómez, and Manfred Opper. Optimal control as a graphical model
inference problem. Machine Learning, 87:159-182, 2012.
John G. Kemeny and J. Laurie Snell. Finite Markov Chains. Springer-Vene Verlag, 1983.
Sergey Levine. Reinforcement learning and control probabilistic inference: Tutorial and review. 2018.
Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. pp. 1-21, 2017.
Hiroshi Nagaoka. The exponential family of markov chains and its information geometry. Proc. of the 28th Symposium on Information Theory and Its Applications, 2005 pp. 601-604, 2005.
Jan Peters, Sethu Vijayakumar, and Stefan Schaal. Natural actor-critic. European Conference on Machine Learning:280-2911 2005.
ML Puterman. Markov decision processes. John Wiley & Sons, New Jersey, 1994,
John Schulman, Sergey Levine, Philipp Moritz, Michael I. Jordan, and Pieter Abbeel. Trust region policy optimization. 2015.
D Silver, A Huang, CJ Maddison, A Guez, Sifre, G van den Driessche, J Schrittwieser, I Antonoglou, Panneershelvam, M Lanctot, S Dieleman, D Grewe, J Nham, N Kalchbrenner, Sutskever, Lillicrap. M Leach, K Kavukcuoglu, Graepel, and D Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484 Richard Sutton and Andrew Barto. Reinforcement Learning: An Introduction. MIT Press, 2018. Richard S. Sutton. Integrated architectures for learning, planning, and reacting based on approximat- ing dynamic programming. ICML, pp. 216 224, 1990.
2016.
Richard S. Sutton, David Mcallester, Satinder Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. Advances Neural Information Processing Systems 12, pp. 1057-1063, 1999.
Evangelos Theodorou, Krishnamurthy Dvijotham, and Emo Todorov. From information thcoretic dualities to path integral and kullback leibler control: continuous and discrete time formulations. 2013.
Emanuel Todorov. soleall markov decision problems, Advances in Neural Information
Processing Systems, 19: 19:1366-1376 2007.
11

---

Under review as a conference paper at ICLR 2020
Appendix
CONTENTS
Extended simulations and analysis
13
Decision trees
13
A.2 Tower of Hanoi
14
Room world
15
B
Policy path programming in the exponential parametrization
16
I Preliminary calculations
16
B.2
Fisher information
17
B.3
Initialization
18
12

---

Under review as a conference paper at ICLR 2020
A EXTENDED SIMULATIONS AND ANALYSIS
A.1 DECISION TREES
In Fig. ST (main text), and Fig. 2
we apply path programming series of decision trees of increasing complexity. The agent acquires reward of 10 points on arrival at the goal state G and is then teleported back the start state in order to play again.
State
State function
Time derivative
2.0
Pollcy dieergence
1.0
0.5
Counter difference
40
-100
20
Polcy
-200
-20
0.0
0.2
0.4
0.8
1.0
0.0
0.4 0.6 Time
1.0
0.
0.8
0.8
Time
Time
Figure $1: 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 the optimal path highlighted in blue. Edge thickness reflects the optimal policy. According 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 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.
13

---

Under review as a conference paper at ICLR 2020
A.2
TOWER OF HANOI
Normalized per state acoss lime
Stdt Nascion
Timee derustion
Stnte furrdinn
Time deriortie
1.0
1.0
0.6
0.6
0.
0.2
02
Courte Shoolg
1600
0.00
0.30
+0.70
-1.00
-1.00
0.0
Tinm
Dotlennch
Stacroddu
2.5
Sort
Doa modue
8.0
Oool
Di modile
Figure S2: Tower of Hanoi with the option to remain at a state. Panels as in Fig. We present extended set of results. Panels C, D, G, and H have already been displayed in Fig. A, B, E, and F show their unnormalized counterparts.
while panels
Normulizad per atade across Ims
Saate landion
Tiree derivelve
Stale funstion
Time dativtive
3.
04
0.
08
0.3
03
0.2
0.2
0.2
1.00
1.00
Counter Preeoo
0.00
0.30
-0.00
-0.5
1.00
Time
Sotlerock
Statrottuo
2.5
Sart
Goe modus
5.0
Gaal
Other module
7.5
Figure S3: Tower of Hanoi with forced resets on arrival at the goal. Instead of having the option remain goal state, consider alternative scenario in which the agent 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 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).
14

---

Under review as a conference paper at ICLR 2020
A.3
ROOM WORLD
State
Time derivalive
0.8
0.5
Pollc divergenoe
0.6
0.3
0.2
0.1
-20
7.5
-40
2.
2
-60
Policy
Counter
0.0
-80
-25
-100
-5.0
2 Time
3
3
Time
Time
Figure S4: Path programming the optimal policy in a grid world without a wormhole. Panels in Fig. Dotted lines with short dashes correspond 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.
15

---

Under review as a conference paper at ICLR 2020
B POLICY PATH PROGRAMMING IN THE EXPONENTIAL PARAMETRIZATION
We derive results which are used to compute the gradient of J [T] (Eqn. with respect to the parameters Ar log Øsj in the main text.
B.1 PRELIMINARY CALCULATIONS
In this section, we record several complementary calculations.
Proposition B.I. The partial derivative aA,, Au of an independent action preference Au with respect another independent action preference Ais
A,, Au óáddu == deg
(14)
The partial derivative AA., Akk, of dependent action preference Ask. with respect an independent action preference Ar is Oa, ARe_
-ôse Ars
Anhw
(15)
Proof. Eqn. 14 follows by definition. For Eqn. action preferences
15 we recall the constraint equation for dependent
Σ Axk ]
)
DA., Akku
DA.,
log
1
new #atEA,
eARi
8sk [-EAks]]
Aa:EAu
=
-dse
Ans
Astw
(16)
Proposition B.2. The partial derivatives of the log path density log puu) and log path policy log (u) with respect to action preference Aij is
Oa [log p(u)] = BAi [log [
(17)
= miz(u) e Ais Aew niw (u)
(18)
Proof.
Oa., log ((u)
OA [log (aas)) + log log ptppp(s1111) ssa)
Or A nuj)
Aumi((u) Akk men (u) }
Oai
Σ
Σ
ELES
Okk Ea
Σ
(dA, And (ul + (dA,, ABtw mek
SLES
Chw Aa.EA
mu)(u)
A.s Aiiw Nisu Miiw (u)
(19)
based the results in Prop. B.1
16

---

Under review as a conference paper at ICLR 2020
Corollary B.2.1.
The partial derivative of the path density p(u) with respect action preference
Asj is
DA. log)(u) = p(u) [nz)(u) Ass-Ar new (u))
(20)
Proof. Using the log-derivative trick AA p(u) = p(u)OA,, [og).
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:
Σp(u) [a., log p(u] 0 nct
(21)
Proof. Proving for log puu)
eAis edin new (w)
p Sa,, logp(u)) ue4
Σp(u p(u) may(u)
ueu
eAi eAoo
= (ni)(u))p
(Neew (w)
Cij e A Cii.
(22)
The two-point state counter correlations Cij can be expressed in terms of the successor representation D and policy Fay ens Cij Asg Therefore, continue
P(u) [Dars logp(u)) = -Doa + Ae New Dose Ane ueu
-ooee Doie
(23)
Corollary B.3.1. The partial derivative of the regularized path reward term (u) with respect to Ai
DA., (u) -Tni (u) + Thi (u)e As Ana
(24)
and its path-expectation is for all action preferences.
Proof. Since Ju) - [log ग. (()))
B.2 FISHER INFORMATION
State transition occupations are 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 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 into the natural path gradient pulled back to transition space. In order to make this gradient ascent natural in the space transitions, we pre-multiply the gradient by the inverse Fisher information --1 (Kakade 2001) which relates the policy densities in path space and transition
17

---

Under review as a conference paper at ICLR 2020
space The Fisher information matrix Z has components
Zij,81 = (aos log p(u) na log log)()))),
= ([ii(u)) Ans An new nsw (w)) [mei(u)= - e Aus Annw nak (u))) >
= (mig (Mi)(u)m((u)), - CAI-AAR (ujjku (u)) +
-E Aiiw (nad(u) (u (u)) A New Au A (nei (u)Tek) (u)) eAis-Ari AAii Chi + eus - -Ake Cite kkk
- CiJ,8t -Gy.M Auk Cig kkw
(25)
where have used Prop.
B.2 The Fisher information I depends 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 x0 can be set to any stochastic policy with corresponding initial action preferences
A
= T log Téj
U
(26)
Assuming that T0 is initialized at the random policy, have
0
(27)
AA
A = -T log |.A.
(28)
for all states s; E and actions a, E A,
18


Reviews:
[{"review_id": "rygNnxhncS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 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.\n\n The paper considers a setting which is quite well-studied as there exist efficient solvers for optimizing the KL regularized RL (including policy-gradient variants). Why the proposed approach is better than those already existed in the literature? What is the outstanding problem in the literature of KL-regularized RL that this work tries to address? I couldn’t find a satisfying argument with respect to these questions in the current submission.    In the absence of any theoretical or empirical result to justify the merits of the proposed algorithm the contribution of this paper to the literature is not clear. Also it is not clear how this approach can scale up to anything beyond the finite state-action  problems as it relies on knowing quantities like state-action transitions and the inverse of state transition matrix which in practice is quite difficult to estimate. I recommend the authors to rethink their approach from the point of view of whether  It provides solution to some open problems in RL/control or it advances the-state-of-the-art. If this is the case, the paper needs to provide theoretical/empirical evidence to back up its claim. Unfortunately the current submission does not satisfy these requirements.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and 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": "ryer2GGXqB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 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.\nThe 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.\nThe 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. \n", "extra_scores": {"experience_assessment": "I do not know much about 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 did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "rJg_CgCUYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 presents a reinforcement learning method that exploits the full-depth backup. The policy update based on the full-depth backup is derived for entropy-regularized MDP. The state-action correlation function is introduced and the Fisher information matrix is computed with it. The proposed method is evaluated on tasks with discrete states and actions.\n\nI understand the concept of using the full path for updating the policy, but I do not see significant novelty of the proposed method from the current manuscript. The proposed method looks equivalent to the natural policy gradient with full-depth backup for entropy-regularized MDP, which is a special case of existing methods. \n\nMy concern is that the scalability of the proposed method. The use of the full-depth backup should suffer from the large variance, and I think the proposed method will not work on tasks with the high-dimensional state space. \nThe evaluation is limited to tasks of which the state space is small, and the proposed method is not compared with existing methods.\n\nDue to the unclear novelty and limited empirical results, I give weak reject to the paper in the current form.\n\nI request authors to answer the following questions to improve the clarity.\n\n- Is the proposed method equivalent to use the natural policy gradient with the full-depth backup for a softmax energy-based policy? If they are different, what it the crucial difference?\n\n- I think that the variance of the estimation of the gradient is large when using the full-depth back up. I'm curious about the performance of the proposed method in high-dimensional tasks. However, the evaluation is very limited to simple tasks in which the state space is relatively small compared with tasks commonly used in deep RL papers.\nDoes the proposed method scale to more complex tasks, such as Atari games?\n\n- When using the n-step TD learning, increasing n does not always improve the performance, and n should be set to an intermediate value\nWhat is the motivation of using the full paths for updating the policy? Does the proposed method outperform existing methods? Especially, the comparison with natural policy gradient methods is necessary to show the benefit of the proposed algorithm.\n\nMinor comments:\n\n- In page 2, \"A state-space \\mathcal{X} is composed of states x \\in \\mathcal{X}\" <- Authors may want to replace x with s in this sentence.\n - In page 6, \"0\\lambda < 1\" I think that \"<\" is missing between \"0\" and \"\\lambda\"\n- In page 6, some variables are explained after Equation (10). However, it took me a while to find \"lambda\" in Equation (10), since Equation (10) has 9 lines and many terms. I think the description in page 6 can be improved. For example, I recommend to use \"\\exp\" instead of \"e^\" for readability.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and 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": "SkxEoyMAYr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 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.\n\nMy personal issues are with these experiments. First, I would like to see better comparisons between this method and existing policy iteration methods. I don't have a good sense in which one would choose to use this algorithm over any baseline methods. Is it faster in any sense? Does it produce better policies during certain games? For the experiments themselves, I don't see much clarification of what the various graphs even show. More effort should have been spent analyzing these. \n\nI come away from this work not fully appreciating the impact it is trying to sell me on. I also think the discussion section should have been more fleshed out.", "extra_scores": {"experience_assessment": "I do not know much about 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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers were not convinced about the significance of this work. There is no empirical or theoretical result justifying why this method has advantages over the existing methods. The reviewers also raised concerns related to the scalability of the proposal. Since none of the reviewers were enthusiastic about the paper, including the expert ones, I cannot recommend acceptance of this work.
Decision: Reject