Policy Tree Network
Authors: Zac Wellmer
Sepanta Zeighami
James Kwok
Venue:  (2020)
Keywords: Reinforcement Learning

Abstract: Decision-time planning policies with implicit dynamics models have been shown to work in discrete action spaces with Q learning. However, decision-time planning with implicit dynamics models in continuous action space has proven to be a difficult problem. Recent work in Reinforcement Learning has allowed for implicit model based approaches to be extended to Policy Gradient methods. In this work we propose Policy Tree Network (PTN). Policy Tree Network lies at the intersection of Model-Based Reinforcement Learning and Model-Free Reinforcement Learning. Policy Tree Network is a novel approach which, for the first time, demonstrates how to leverage an implicit model to perform decision-time planning with Policy Gradient methods in continuous action spaces. This work is empirically justified on 8 standard MuJoCo environments so that it can easily be compared with similar work done in this area. Additionally, we offer a lower bound on the worst case change in the mean of the policy when tree planning is used and theoretically justify our design choices.

Under review as a conference paper at ICLR 2020
POLICY TREE NETWORK
Anonymous authors Paper under double-blind review
ABSTRACT
Decision-time planning policies with implicit dynamics models have been shown to work in discrete action spaces with Q learning. However, decision-time plan- ning with implicit dynamics models in continuous action space has proven be a difficult problem. Recent work in Reinforcement Learning has allowed for im- plicit model based approaches be extended Policy Gradient methods. In this work we propose Policy Tree Network (PTN). Policy Tree Network lies at the intersection of Model-Based Reinforcement Learning and Model-Free Rein- forcement Learning. Policy Tree Network is a novel approach which, for the first time, demonstrates how leverage implicit model perform decision-time planning with Policy Gradient methods in continuous action spaces. This work is empirically justified on 8 standard MuloCo environments that it can easily be compared with similar work done in this area. Additionally, we offer a lower bound the worst case change in the mean of the policy when tree planning is used and theoretically justify our design choices.
INTRODUCTION
Reinforcement Learning (RL), the study of learning what to do. Learning what to do given situation to maximize reward signals. Generally speaking. Reinforeement Learning problems are approached from either a Model-Free or Model-Basse Based perspective. A Model-Free approach builds policy through interacting with the environment and uses the acquired experience to improve the policy. A Model-Based approach builds a dynamics model the environment and uses this improve policy in number of ways. Such as planning, exploration, and even training on imagined data (Sutton| 1990, Ha & Schmidhuber] 2018). Model-Free Reinforcement Learning generally offers superior final performance. However, in exchange for strong final performance a large number of samples are required. Model-Based Reinforcement Learning offers better sample complexity but comes at the cost of weaker final policy. In light of this, recent research (Wellmer & Kwok, 2019 Silver al. 2016 Farquhar et al. 2017 Oh al. 2017) has been focused on mixing both Model-Free and Model-Based Reinforcement Learning.
Model-Based Reinforcement Learning can be broken down further into categories (Wellmer & Kwok] 2019). The first is explicit dynamics models. Explicit dynamics models are when the observations directly being reconstructed. The second is implicit dynamics models. Implicit dynamics models are when the dynamics model learned indirectly. Some examples this could be through predicting future rewards, values, policies or other auxiliary signals.
The work we present here, Policy Tree Network, lies at the intersection of Model-Free and Model- Based Reinforcement Learning. Our work builds off the work done by Wellmer & Kwok (2019), where they showed how to build an implicit dynamics model for Policy Gradient methods contin- uous action space. Policy Tree Network takes this few steps further by showing how to leverage the implicit dynamics model for decision-time planning.
Our empirical results are on eight MuJoCo (Todorov et al. 2012) environments. In our experiments validate the decision-time planning scheme that introduce. Lastly we show Policy Tree Network outperforms the model-free baseline (Schulman et al., 2017) and the mixed model-free model-based baseline (Wellmer & Kwok 2019).

---

Under review as a conference paper at ICLR 2020
2 RELATED WORKS
Value Prediction Network (VPN) (Oh et al. 2017) offers an approach building and leveraging an implicit dynamics model in discrete action space. The implicit dynamics model is constructed with overshooting objectíves which predict future rewards and value estimates. At behavior time, a Q tree is expanded and actions are selected according to e-gredy of the backed-up Q estimates. Decision-tine planning is trivial in this case since the action space is discrete. When the action space discrete it's possible to try all possibilities.
TreeQN and ATreeC offer policy gradient and Q-learning approach building impleit dynamics models in discrete action spaces. TreeQN (Farquhar al. (017) is similar VPN except the authors claim that VPN has an issue since the policy being trained is different than the policy actually being used. In light of this, TreeQN directly optimizes the backed-up Q estimates as opposed to indirectly (as is done in VPN). Additionally, TreeQN uses overshooting reward estimates as an auxiliary objective.
ATreeC (Farquhar et al. 2017) takes a similar approach to TreeQN except instead of a Q-learning approach ATreeC uses a policy gradient approach. We note that even though ATreeC uses policy gradient approach it still does not work with continuous action spaces. Crucially, ATreeC optimizes the backed-up "Q" estimates to function logits for a multinomial distribution. Because of this, the backed-up "Q" values in this case can be thought of as pseudo Q values.
Policy Prediction Network (PPN) WWelmer & Kwok, 2019) is approach to building implicit dynamics models with policy gradient methods. This was the first work to show how build an implicit dynamics model in continuous action spaces. This was done by introducing overshooting objectives and a clipping scheme designed for overshooting objectives. The training algorithm is located in Section A.2
d-1 (c) + aoch" + +ar
C. Ld
C max( -ratio rra ACTT) anH
(2)
6 = max( Reti), (0i,olip - Reti)²)
(3)
C = max((Fi, - -((4)) (Pi.a - -T(+4)
(4)
Where Ci"", Ci and C. are the policy, value, and reward losses grounded time / predicting i steps into the future. Additionally, subscript 0 refers to estimates from the latest model parameters, H is policy entropy, AGAE is the generalized advantage estimate (Schulman et al., 2016). is reward target, f is a predicted reward, é is a predicted value, and It is a boot-strapped n-step return target. The coefficients are clipped estimates are used to stay near estimates from old parameters(e") and are further defined in Section along with the definition of the importance sampling ratio.
used to trade off importance of objectives. The
The short coming of PPN that it did not lend itself well to leveraging the implicit dynamics model to perform decision-time planning and thus used the model-free policy to sample actions. Additionally, it does not make use of the function, a separate measure of how "good" an action at given state, discussed in Section
3 POLICY TREE NETWORK
Policy Tree Network uses a combination of model-free and model-based techniques. Policy Tree Network builds off the PPN (Wellmer & Kwok 2019) approach to learning an implicit-model. Ac- tions during behavior time are chosen by model-free policy. Learning is done with model-based approach that follows the behavior policy's rollout trajectory. However, the test policy follows a model-based approach. An implicit transition model is embedded into the architecture. Through overshooting objectives, a dynamics model is learned and the collection of forward predictions offer the benefit of additional signal in the gradient updates.
2

---

Under review as a conference paper at ICLR 2020
Our novel contribution in this works is decision-time planning algorithm that allows to leverage the implicit dynamics model. The decision-time planning algorithm is based on building a tree of possible future values, actions, states, and rewards and then performing a tree backup algorithm we introduce. In previous works was not possible to directly leverage the implicit model for decision time planning with policy gradient methods in continuous action space. Our empirical results in Section I demonstrate the advantage of PTN over the model-free baseline (PPO) and the mixed model-free& & model- podel--basd baseline (PPN).
3.1
LEARNING
Policy Tree Network is trained over a collection of overshooting objectives. We follow an identical clipping approach (Section A3.) 3 to the one found in PPN. Targets used for training are computed exactly the same way as in PPN. More explicitly,
aspect of training depends on the decision-time planning algorithm described later in Section [.2]] While this might be desirable, we describe why it is difficult in A. We additionally introduce term / Hafner et al. (2018) used to trade off im- portance of short and long-term predictions. Lastly, for simplicity we drop the extra value loss term found in PPN (Equation leaving us with the following: L, = Σn= B.CC."" + +a, a,C, + a, a."""" Where L, L and L."" (equations
2 are the policy, value, and reward losses grounded at time predicting steps into the future.
The implicit dynamics model is jointly learned from the objectives in L, whenever i >> 0. When
i = estimates are not required to pass through the transition network. In Section A.2 we show
the training algorithms for PPO (Schulman et al. 2017), PPN (Wellmer & Kwok 2019) and PTN which are quite similar.
PPN Wellmer & Kwok 2019) was shown to have returns drastically differ between training depth values. The point of 3 is to stabilize returns over different choices of training depth (Section A.6
3.2 DECISION-TIME PLANNING
Including branching in PTN is appealing because it would allow for decision time planning. Further- more, this appears to be a simple task since transition model is already being learned. However, because the decision-time planning policy is difficult to directly measure with a PDF (Section A. resort performing decision-time planning exclusively evaluation time.
Traditionally, at every state, the next action in a state is either determined by a policy, æ, learned usually based policy gradient method, an action value function Q that induces a policy that takes actions with the largest Q value. However, in PTN, we have access to independently learned policy and Q functions There are three ways of using æ and Q to create the final policy, TF.
1. setting `e = π as done in PPN, (Wellmer & Kwok 2019). which ignores the Q function.
2. setting TF argmax Q, called Q-bckkup which ignores
3. setting T = [TT, Q), called --Q-backup, for some function f.
As (1) was described in PPN will further dig into the details of (2) in Section 3.2.1 and (3) in Section 3.2.2 Methods discussed in this section do not impact the learning procedure discussed in Section 3.1 and are only used for decision- time planning at evaluation time.
We use tree planning method which expands tree up to a depth d expanding branches each depth and collecting reward, policy, and value predictions along the way. Tree expansion is done by recursively calling the core module (frore) with b action samples and the abstract state. The action being passed to the core module could be sampled from uniform distribution or the policy (((a)))))) )), where 5/1 represents the predicted abstract-state steps into the future with branch according to parameters O. We show that if the correlation between and Q is positive, sampling л will be more suitable and Section 4.2 shows that they are in fact positively correlated in practice. Candidate actions represent branches in the tree. Then the predicted estimates are backed-up with a TD-A scheme (Sutton) 1988 Suttonn& & Barto 2018 Farquhar al. 2017) to assign a Q value to each branch as described in Algorithm
by independent we mean 5 is not just policy induced by selecting max of Q
"ween =
3

---

Under review as a conference paper at ICLR 2020
2d.0
2d.
gd. bd 1.
gd.
10000
$t 0
t,0
+
foore
fgore
f
$1.0 $
$ 11,6 0,0
mewarr
1,0
foore
foor
puxus
V
20. r,
fa fencode
Core
Figure 1: Predict policies, rewards, ab- stract states, and the value of the abstract states (Wellmer & Kwok 2019).
Figure 2: PTN Expansion, a, r, v outputs from feure are omitted for simplicity
When performing decision-time planning, the action associated with the max backed-up Q-value is taken. This policy is referred to as T where 0' denotes which parameters were used in the tree.
3.2. Q BACKUP
Given an abstract state fene fe and an action a, the backed-up Q-value calculated from d-step planning is defined as:
(5) ('(s) = (1 [10000000 N)e + Amax, (s,
if = d if < d (6)
asssa)= =
where s'= (8, (), 10= (s), and r (s)
In Q backup. the final policy, Ty. aims at selecting an action that maximizes the action value func- tion, QO. However, Q" is a combination of neural networks and finding arg max, Q" is difficult problem. We use our tree expansion achieve this. With expansion, at each depth we sam- ple b actions based on π and choose the one with maximum Q++1 to estimate arg max, Qi+1 in equation 6
Intuitively, if x and Q are positively correlated, sampling from π allows us to find actions with higher Q compared with sampling from uniform distribution, because, for state and an action a, larger [[ass) value would suggest larger (s,, a). This the subject of the following lemma. Note that, for given state s, the covariance between π ([ss) and Q(X, s) over bounded action space is defined as covp (T( (X]s), Q(X, s)) where X is a random variable with distribution U, the uniform distribution over the action space. and Q are positively correlated if covy( (x()s)) s)) is positive. Proof of the lemma can be found in the appendix.
Lemma 1. Ex~- Ex=x[Q(X, x)] > Ex-D Exxxr(((X,.. s)] if covv (x(((s), Q(X,))) > 0.
Section 4.2 shows that the correlation between т and Q" is in fact positive in practice. Therefore, sampling actions according to is justified.
Since sampling is done based on æ, our final policy Ty now depends on и as well as Q Next we investigate the relationship between TF, π and Q". Consider the abstract state = 8,,0
.0.0
Recall
that (a, s) is an action value function calculated based on the tree expansion and backup. Q" uses sampling, is probabilistic, and is a function of fcore, X, and d. Action selection is done by sampling X, ~ π for 1 < < b and selecting arg max; Q s). Thus, for action a, cumulative density function (cdf) of TF (als) is given by __ (2)s))d Pr(arg max, (X,, S a).
Intuitively, the branching factor b can be thought of as interpolating how much confidence we have in ı and reward, value and transition networks (which make up )"); low b signifies confidence in and larger b signifies more confidence in reward, value and transition networks. As b increases TF becomes less dependant on æ. When b goes to infinity, Re only depends on reward, value and transition networks and not л. To investigate the maximum possible difference between mean of and FF all Q" functions we provide the next theorem. The theorem is provided in one dimensional action space for better illustration, but the argument can be extended to higher dimensions. Proof of the theorem
be found in the appendix.
Theorem 1. Let pr be the mean of actions selected based on FF and a the mean and standard deviation of octions selected based on In the worst-case over all possible Q" functions, [リ-μr
4

---

Under review as a conference paper at ICLR 2020
Algorithm T.. ==...expand(s)) i)
2d.0
cd.6 7.6
2d.6 0,0
initialize 6. +,, for
do
a[s] x(s]
r( = (s. (b))
b'b] (bb))
8 5] (8'(i)
dthn
QuI Veen + + +'Di) ab]]++
+1.0
c1.0
2.9
Q tmp oxpundd (b. 11,++1)
Qli (+5)+ 7(0 x)0([]] maxy Q.3mp) sia a[sl[*)
(9, 9..)
31-3
return Q
Figure 3: PTN Backup
Figure 4: pseudo-code for 7-Q expansion and backup algo- rithm. Where the Q returned a dimensional vector.
bla - =0{2){ (ndk(a)) (2 where erfe is the complementary error function and & is the p.d.f of standard normal distribution. Setting b - 2, we get the looser bound | p.l 2 V in the worst- case.
The bound is a lower bound on the worst-case and it shows that jr can move least as far V from μ.. In other words, there exist Qo functions for which the difference between mean of Ty and at least a Observe that the bound decreases as a decreases, which intuitively makes sense VR since with lower o,, it takes more number samples to obtain an action further away from j..
The bound above sheds light on one of the downsides of this approach. The final policy TF can become significantly different from ग, depending on QO and a, even when = 2 and as b grows it becomes only reliant on Q (Section A.5 shows the numerical value of the bound for several b values). Although Section 4.2 shows empirically that and Qº are on average correlated, there can be states where they are not. In such a scenario, Q backup may rely too heavily on Q?.
We previously mentioned that can be seen as confidence parameter, adjusting how much we rely on x and the networks that make up Q". Nevertheless, it does not remedy the above mentioned problem. This is for reasons, one is that b only takes discrete values. We mentioned above that b = 2 may shift the policy by too much, but we cannot reduce any more without exclusively relying on æ. Secondly, choosing b for given confidence level is difficult problem, even if discrete confidence parameter sufficient. This is because b has a complicated relationship with TF, π and involving integrals. Thus, it is not clear that, for instance, if we have equal confidence in Q and x, what the value of b should be.
3.2.2 π T-Q BACKUP
Motivated by the issues discussed in section 3.2.1 a Q-function Q. we want our final policy Fr to depend on Q and и based on how much confidence have in each. If we have equal confidence in both Q and π, then we would like Rr be function depending on π and Q equally. One way to achieve this is using geometric mean of π and Q as an indicator of how good an action is That is, we would like to select an action such that V x Q maximized (note that if we have reasons to believe π or Q provide better estimates, we can take the weighted geometric mean).
we introduce π-Q backup. Given a policy x and
The backup procedure is defined as mentioned in Section 3.2. however, given an abstract state ff fon((x) and an action a, the backed-up Q-value calculated from d-step planning is defined as: if i = d ( A)e + A Amxx Q if < d are directly being optimized, they only used for decision-time planning. Notice how estimates are scaled by likelihood of the action being sampled from æ. This removes the previously mentioned issue of selected actions longer depending on æ. It's interesting to note that in this case when b = oo the policy is deterministic.
a'(s,a)= ( + (7) V((s) {
(8)
Note that neither Q' or V in Equations 5 6
valued Q exists in the tree backup. modify the geometric mean by adding [min(Q) + 5 to the estimates. 8 positive small non-zero term which can be optimized Habib (0122)
When negative
5

---

Under review as a conference paper at ICLR 2020
This does not manifest itself an issue because the decision-time planning policy isn it't used the behavior policy so we are less concerned about exploration.
Note that we still need to estimate maxa Qi+1 in equation We take similar approach to Q- backup mentioned in Section 3.2.1 since и and vTQ are expected to he correlated. Furthermore, regarding the use of geometric mean, we note that it is more meaningful than the arithmetic mean in this scenario as the values may be of different scales and that preserves proportional change as opposed to absolute change.
In Section 4.3 We will empirically explore both approaches backup. The T-Q backup is shown in Algorithm Though we note that if the scaling Q estimates by я and the square root are dropped it would reduce the max Q-backup algorithm described in Section 3.2.1
4 EXPERIMENTS
Our experiments seek to answer the following questions: (1) Is correlation between я and Q pos- itive? (2) What style of backup performs better: a standard Q-value backup or policy weighted Q-value backup and how does branching effect the returns of the decision-tinn time planning policy? (3) Does PTN outperform the baselines?
4.1 EXPERIMENTAL SETUP
Preprocessing in experiments done similarly that of PPO (Schulman et al. 2017) and identical to the preprocessing in PPN (Wellmer & Kwok 2019). All models, PPO2, PPN, and PTN were implemented in Pytorch (Paszke et al.) (017). The parameters (0) updated with the Adam optimizer (Kingma & Ba. 2014). All the experiments are run for million time steps unless otherwise noted.
Our PPO2 implementation uses the same hyperparameters as the baselines implementation (Dhari- wal et al. 2017): 3 fully connected layers with 128 hidden units and tanh activations for the policy. 3 fully connected layers 128 hidden units and tanh activations for the critic. The largest difference in our PPO2 implementation is that we do not perform orthogonal initialization.
Our PTN implementation uses similar hyperparameters (identical to PPN): fully connected layers with 128 hidden units and tanh activations for the embedding. 2 fully connected residual layers with 128 hidden units, tanh activations, and unit length projections of the abstract-state (Farquhar al. 2017) for the transition module. fully connected layer with 128 hidden units for the policy mean. I fully connected layer with 1 128 hidden units for the value. 1 fully connected layer with 128 hidden units for the reward. In practice we use Huber losses instead of L2 losses, as was done in related implicit model based works (Oh et al. (017).
We set 30 = and 3>0 = Values used for branching and depth are explicitly stated corre- sponding experiments. We test on the 8 standard OpenAl MuloCo environments (Tooorov et al.) 2012 Brockman et al.) (016)): Hopper, Walker2d, Swimmer, HalfCheetah, InvertedPendulum, In- vertedDouhlePenddulum Humanoid, and Ant.
4.2 CORRELATION
sample correlation mean
sample correlation variance
Hopper-v2
0,937
0.018
Walker2d-v2
0,971
0.017
Swimmer-v2
0,945
0.016
HalfCheetah-v2
0,968
0.018
InvertedPendulum--22
0.969
0.008
InvertedDoubheeendtlum- Humanoid-v2
0.971
0.005
0.934
0.022
Ant-v2
0.972
0.019
Table 1: Summary of correlation between Q and n.
In this experiment we empirically measure the correlation between π and ( d = 1). Positive correlation empirically justifies the of lemma that sampling from offers better approach to

---

Under review as a conference paper at ICLR 2020
maximizing the backup objective (for both Q backup and T backup) opposed to uniform sam- pling. To measure correlation we first train a PPN policy for 200 thousand time-steps on the MuJoCo environments. Next we collect trajectories over 10 thousand timesteps. Then at each observation we uniformly sample 100 actions and compute the corresponding Q-values and corresponding PDF points from æ. This gives us 10 thousand estimates of correlation. From here we fit normal distribution to the correlation results and report them in Table 3
Positive correlation tells us that sampling according to π will better maximize aF than a uniform sample over actions. This empirically justifies our approach performing tree expansion.
4.3 BRANCHING BACKUP
PIN T backup
PIN Q Bockup
b-3
Нopper
22968
27814
39K13
30R33
21359
17830
[AOEX
10034
403
357.8
306.7
244.1
343.9
431.9
423,5
398. I
Walker2d
3:42.7
30803
4189.1
1253.
33815
3539.7
3160.
2722.8
295.5
355.9
517.6
1033.0
Swimmer
102.1 1
+
1056
+
1066
-
107.5
89.5
88.6
+
84.5
-
75.5
28.4
29.2
29.2
29.2
35.1
34,4
32,0
30,9
HaltChoeiah
45550
3435.
3501.7
3526.3
3467.7
649.1
6388
742.4
748.2
734.5
Inverted//emdllum
10000
10000
10000
10000
995.2
998.7
998.5
998.2
0,0
0.0
0.0
0.0
9.6
2.6
28
6301.4
9367.6
9336.9
6286.6
9288.3
9139.7
1929,4
299.8
02
0.1
308.4
64.5
225.1
1498.2
Ast
17303
210M3
21832
1570.
1946.4
2087.1
2078.5
2013.3
225.7
329.7
324.8
371.3
266.1
202.7
197.5
279.1
Hamanoid
933.1
957.3
919.2
280.7
355.6
410.5
366.3
432.9
449.2
345.9
272.9
Table 2: branching and backup experiment where d and 0.95
In this section we explore the impact of using planning as the test policy and which backup scheme captures the highest returns. We consider PTN trained with depth equal to and we evaluate both backup procedures found Section 3.2
As we can see in Table 2 nearly all environment suffer from an increased branching factor when using Q backup. None the environments show clear trend that increasing the branching benefits returns. In fact, both Hopper and Walker2d environments show the opposite, as b increases returns decrease, Intuitively this makes sense, as b increases to infinity the action taken no longer relies on the policy ı but instead relies entirely on the Q backup from reward and value predictions.
When the backup scheme takes into account the likelihood of an action coming from the policy, it is no longer true that as b increases to infinity the action selected by decision-time planning is independent from the policy. As we can see in Table 2 every environment benefits from increasing branching used in decision-time planning when the backup scheme is π F-Q backup discussed in Section 3.2.2 Comparing Q-backup and π- n-Q-backup in Table it's obvious see that the policy weighted Q backup offers much more robust returns.
Now clearly that decision-ting planning is indeed helpful. Furthermore, now know that T-Q backup offers a reliable approach. Going forward we will ask if it's possible learn from this decision-time planning policy.
4.4 BASELINE COMPARISON
To test model, chose to benchmark against PPO2 and PPN on eight MuJoCo (?) environ- ments. We include our = 2 b = 5 model in our baseline comparison. However, we note that is possible that other configurations perform better on some environments.
As can be seen in Figure 5 we find that PTN finds better if not comparable policy in all of the environments. PTN has large performance gains over PPO's model-free approach, even though PTN's implicit planning module only looks a short distance into the future.
Environments with larger meaningful observation spaces, such as Humanoid, we suspect could ben- efit from bigger latent space. In Humanoid, the latent space (128) is far smaller than the observa- tion dimensions (376) and makes learning a useful implicit transition model infeasible. Given more compute would explore increasing the latent space.

---

Under review as a conference paper at ICLR 2020
Hopperwu2
Walker26-12
d-2 (sseda-d)
d-2 (weadien))
2030
1,40
2010
1000
1050
300
0-
Swimmer-y2 V2
kdfchestah-v2
P702
RO2
120
P7N di2 (keeda-S)
PRN 2-22 (saaden5)
1010
0-
409030
1002030
t0ka Umeskapa
tetal mmsstaga
InvertesPene.dum-v9
1200
5 (1
PTN di2 (ssedam5)
1974 ded Saordoon
0000
500
220
0000
800
200
2000
200002
400000
600000
200030
3300000
200000
420000
6000000
000020
2800000
lotal Binakapa
Blumanelt--22
Ant-2
PTN ded bis (lesdan)))
PTN dizz bed (seadam-)
[seeds-11)
Connda-
2002000 QUTATO0 GERIORR
2000000
800030
600000
Woo00s
10107200
Figure 5: Results on million step MuloCo benchmark. Dark lines represent the mean return and the shaded region is standard deviation above and below the mean.
5 CONCLUSION
In this work we present for the first time an approach to decision-time planning for implicit dynamics models in continuous action space. We provide a theoretical justifications for our design choices and show strong empirical results which are improvements over previous related work. In future work we would like investigate distilling the tree policy into the model-free policy, find better sampling procedure for expansion, and incorporate research from recurrent networks to avoid issues with vanishing and exploding gradients in the implicit dynamics model.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606. 01116666601140 01540, 2016.
Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford,
John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov. Openai baselines. https:
7/github. com www.m//pppaaaaaeeiiieeen.e Lines 2017.
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. Treeqn and atreec: Differentiable tree planning for deep reinforcement learning. CoRR, abs 11417, URL
http://arxiv.org/
11417
David Ha and Jürgen Schmidhuber. Recurrent world models facilitate policy evolution. In Advances in Neural Information Processing Systems, pp. 2455 2455-2467, 2018.
Elsayed AE Habib. Geometric mean for negative and zero values. International Journal of Research and Reviews in Applied Sciences, 11(3):419-33 2012.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamies for planning from pixels. arXiv preprint 2018.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Junhyuk Oh, Satinder Singh, and Honglak Lee. Value prediction network. CoRR, abs/1707.00499 2017. URL/attp://aaxi wttp///////////cocc///// 03497
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vetio,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. Proceedings of the International Conference on Learning Representations (ICLR), 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/1 abs/1707.00347, 2017. URL http://arxiv. org/ abs/
7707.06347
David Silver, Hado van Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac-Amold, David P. Reichert, Neil C. Rabinowitz, André Barreto, and Thomas Degris. The predictron: End-to-end learning and planning. CoRR, abs/1612.08810, 2016. URL http://
arxiv. www.:rrggabb... abs 1111.111.1.. 08810
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3
(1):9 14:9444,1 1988.
Richard S Sutton. Integrated architectures for learning, planning, and reacting based on approxi- mating dynamic programming. In Machine Learning Proceedings 1990. pp. 216-224. Elsevier, 1990.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on, pp. 5026- 5033. IEEE, 2012.
Zac Wellmer and James Kwok. Policy prediction network: Model-free behavior policy with model- based learning in continuous action space. In European Conference on Machine Learning and Knowledge Discovery in Databases. Springer. 2019.

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 DECISION- TIME PLANNING AS THE BEHAVIOR POLICY
Including branching in Policy Tree Network's behavior policy is appealing because it would allow for directly optimizing the test policy we intend to use and appears to be simple since an implicit transition model is already learned. However, as we will soon see this is not the case.
natural first thought is just to recursively sample т times up to a depth d, perform a backup on the expanded tree, and then take the action associated with the maximal base branch. This is the approach described Section 3.2
However, this can not be used as the behavior policy because you are changing the distribution of how rollout actions are chosen is not equal to T used to do importance sampling in the policy gradient loss. When = 1 then begin to rely the reward and value network
way that difficult directly measure. The rollout policy тe' ,F
Torr ,F is the same as TTr. However soon as to help decide which actions to take.
The previously mentioned issues can be avoided if _ is not used the behavior policy. Instead with decision-time planning we can only use _ as our test policy. Interestingly, there is no guarantee that this should work because the policy we are optimizing for (Te) is not the same the test policy. We note that a theoretical issue does arise when using T as the test policy. The fū network parameters are trained to predict the value for policy war not T However, in practice this turns out not to be a large issue.
A.2 PPN TRAINING ALGORITHM
Algorithm Policy Prediction (PtN)rk(PPN) (Wellmer & Kwok 2019)
Initialize parameters 0
0' = A
for iteration=1, 2, do
Run policy Th. in environment for time steps
Compute advantage estimates AÇAE , AGAE for epoch= 1.... K do
Shuffle n samples into mini-batches of size M S n for each mini-batch do the set of samples selected for the mini-batch Lmb
T3 L Lt Optimize Lmb W.r.t. 0
0 0=
PPO, PPN, and PTN use similar training algorithms, the main difference stems from how L, defined. Where in Algorithm 2 time steps are used to collect trajectories, K is the number of epochs, M mini-batch size, and 7 represents the randomly sampled time steps specific mini- batch.
A.3 CLIPPING
Ta oc+ s 8%
ratio;
To (a = a++ils 3441,07
ratio
clip(ratio c, 1 E),
= clip(ti, - 0 vitiorr -c,() 00-1.0''
P Rcpip clip(F(.. Fo Plt,0r EE,E) +0 ftts,0r
During training we follow the grounded clipping approach shown in PPN Wellmer & K Kwok] 2019). The clipped estimates are defined above. Where is a hyperparameter that defines the size of the clipping region. Clipping all the network heads turns out to be imperative to the learning pro- cess (Wellmer & Kwok 2019).
10

---

Under review as a conference paper at ICLR 2020
A.4 PROOFS
Proof of Lemmaa
Note that ( Q(x,)(()))))))))),))))))())))Q s)) = Eu [ s) (X|s]]
Eu(Q(X, s)) (x [s)] Let R be bounded action space. By definition, the covariance equals Rre Izen (Q(r,)) (zl(s) Ey [Q(X, s)] area(M] SeER (ar)s), where SeeR ग (2]ss) = and
Jaen (Q((( [x( The result follows because the covariance positive.
Proof of Theorem ! We prove this by showing the existence of Qo functions for which the inequal- ities holds. We drop from notation for convenience and write Q(a, s) Q(a) and r[als) as π (a).
Let XF decreasing as a increases. Then f Tr Pr(Xr S c) Pr(3i, X; S c)=1 - Pr(v,, X,
i.e., XF arg max; (X,), where X; Consider (a) that is strictly
arfel /202
c). Since X,'s are i.i.d, Pr(v,, Xi > c) = -Pr(X > c)o =
(setting X X1).
Therefore, (F() b( orfo V2o?
b-1 (c)..
crfel b-1
Then pr = D el
/20?
x (c)dc.. Substitute == 02 + na, we have
2
erfe( b-1 o(z)dz + bμ
erfe v2 b- o(2)dz
HF = bo
2(
-00
2
2
where,
erfe( 22 v2
erfe v3
b-1 6(2)dz 1e(
bμ
2
-00
=0 -0(--1)
and when
(2)o
00
2(
erfo(
/2
(2)-1 o(=)dz = 22
erfe
)0(2)
erf(2)
2
2
4/T
Observe that b 1 arfel 6-1
6(2)d2 = 1, which gives the first bound.
Setting b = 2, we have that μf 4 - V + - VF
A similar argument but setting Q" be strictly increasing function in gives the inequality for when μp is larger than n..
A.5 NUMERICAL EVALUATION OF BOUND IN THEOREM II
Fig. 6 shows the numerical values for the bound in Theorem for several branching values. Note that the bound becomes larger than when 4. This means that when b the difference between the mean of ny and л can become larger than one standard deviation of n, which is a significant difference.
A.6 LEARNING MODIFICATIONS
Notice that these returns are worse than PTN(wwth decision-time planning) shown in Figure This shows performance benefits from the modifications shown in Section 3.x(e (3). The point of
11

---

Under review as a conference paper at ICLR 2020
122
Word-ccae lawer bound (tmee
0.
0.0
Figure 6: Numerical evaluation of bound in Theorem 1 for various branching values
train depth =5
train depth 10
PTN
PPN
PTN
PPN
Hopper-v2
1944.0 258.5
2191.6 183.3
1672.7 + 457.5
1752.3 + 625,4
Walker2d-v2
2936.9 + 893.2
2808.4 + 647.3
3054.8 + 434.0
2565.9 + 327.99
Swimmer-v2
89.4 35.3
73.3 + 34.5
80.3 35.7
57.5 + 30.3
HalfCheetah-v2
3439.8 + 698.6
3410.5 + 840.9
3638.9 + 545.2
3632.8 + 819.0
InvertedPendulum--2
971.7 + 56.5
979.6 25.7
1000.0 = 0.0
1000.0 = 0.0
InverteDDoubeeeodduuum-22
4332.6 + 192.9
3344.5 = 234.4
4360.2 = 145.1
3186.8 = 87.7
Table 3: Returns from PTN(no :p//decision-ime planning) and PPN using only the model-free policies
3(found in PTN but not PPN) is to stabilize returns over different values of training depth. In PPN, Wellmer Kwok 2019) showed that optimal depth highly dependent on the environment and returns can drastically differ. While the modifications certainly do not entirely fix this, we find that mitigates large differences in returns from different training depths.
12


Reviews:
[{"review_id": "rkehqpXRtS", "reviewer": "AnonReviewer2", "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 proposes a modification to Policy Prediction Networks (PPN) in which the learned transition-, reward- and value function models are used at test-time in a planning procedure. \nA second contribution is the \"pi-Q-backup\" which uses the geometric mean of both the policy and the value function as maximisation target of the planning step.\n\n Overall, I find the idea interesting and the experimental evaluations promising. However, I am voting for \"weak reject\" for the reasons outlined below. If some (or all) of them are address, I'd be happy to raise my score. \n\n- I found the paper hard to understand. In particular, the algorithm PPN on which this work is build is not explained at all, requiring the reader to read the original PPN paper. Including a description of PPN, including it's main features, would greatly help the paper. Second, I am still not sure I correctly undestand when each component is used. As I currently understand it, the main usage of the model during training time is to compute the Advantages in equation (2)? Or are those computed based on rollouts? If so, where is the model actually being used during training?\n- Figure 1 is taken directly from the PPN paper without any reference or citation (as far as I can tell).\n- For the comparison in Figure 5, it would be great if PPN could also be tested with the newly introduced parameter \\beta_i. At the moment, it is hard to tell whether the performance gains are due to \\beta or due to the proposed planning scheme.\n- I'm confused about Theorem 1: Wouldn't we want an upper bound on the difference of means?  Also, what does 'worst-case' mean? Is that for the 'worst' Q-function we could choose? \n\nEdit:\nThank you for your comments and updated manuscript.\n\nI think the writing has improved significantly, but could still be further improved and clarified. In particular, the question of how the model and other components at various points in time could be made more obvious. I found the authors' response to R3 here helpful as well. \nAt least for me some of the confusion arises not due to the complexity of the proposed approach, but just because combining real and 'simulated' transitions can be used and mixed in so many different ways that it's important to be clear about it. Also, at least personally, I found the explanation \"Learning is done with a model-based approach that follows the behaviour policy’s rollout trajectory. However, the test policy follows a model-based approach\" still not very helpful. \nOverall, I think the presentation is on a good way but needs some more work.\n\nWith that being said and now having a better understanding of the algorithm I think this is very interesting work. However, I share R1's concerns about the computation of the \\pi-Q backup, in particular that it seems arbitrary and doesn't handle negative values. I'm also not convinced that adding |min(Q)| is a good solutions as a) we don't always have access to that value and b) If I'm not wrong, than \\pi_F is not invariant under a shift of Q. \nI'm wondering why the authors decided to take the geometric mean instead of following the more typically used approach of using exp(Q/Temperature)*pi to combine Q-function and a policy distribution (see e.g. the \"Control as Inference\" literature, the \"Maximum a Posteriori Policy Optimisation\" or \"Soft Actor Critic\" algorithms, in particular the \"Soft Value functions\". I think this should at the very least be an ablation study, and could be even performing better and at the very least be robust to negative values.\n\nOverall, I think this is very interesting work and could become a very strong paper, but I will remain to recommend a \"weak reject\" because I think it needs some more work to get there. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1e8BP_aYB", "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 Policy Tree Network, a novel approach to use an implicit dynamics model to perform decision-time planning in continuous action spaces. The experiments show that the proposed method performs better than the underlying model-free RL algorithm in standard MuJoCo environments. \n\nThe writing quality is low and I don't understand the proposed method, especially the backed-up Q-value. The notation is also confusing. It seems to me that pi(a|s) is the density of action a, so what does sqrt(value * density) mean? What if the value is negative? \n\nBesides, I have some questions.\n1. Figure 1 looks the same as Figure 1 in https://arxiv.org/pdf/1909.07373.pdf, but I don't find any reference in the paper. Could you please state the difference between two figures, or explain why you want to put this figure here without any description or reference? \n2. How is PTN compared to model-based RL algorithms? The only baseline here is PPO, which is model-free. More importantly, note that the policy in PPO is stochastic, so how is PTN compared to the deterministic policy? \n3. How is the proposed pi-Q-backup method compared to classical control method, e.g. MPC? Does the proposed planning algorithm work for model-free algorithms? \n4. As this paper talks about planning with implicit dynamics models, how is the proposed method compared with explicit dynamics models? \n\nMinor comments:\n1. In Algorithm 1 Line 11, could you please check the brackets? \n2. Page 4, \"Thus, cumulative density function (cdf) of pi_F is given by ...\": Could you please check the correctness of the equation? \n3. What does \"worst-case\" in Theorem 1 mean? \n4. How is correlation in Table 2 calculated? \n5. In Algorithm 1, is the return value a scalar or a vector? \n6. The paper states that \"Intuitively, the branching factor b can be thought of as interpolating how much confidence we have in pi and Q0\". One can have infinite b but sample a uniformly to optimize Q (and then pi_F becomes maxQ policy), so I don't think b can be simply characterized as the confidence. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hyg-1926Yr", "reviewer": "AnonReviewer3", "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": "This paper claims to present a method for combining model based and model free approaches. The paper I find very poorly written hence my certainty about understanding the method cannot be very high. In training the method seems to build up a backup tree using transition operators and a policy and using them as targets for learning. In training it is not quite as clear what they are doing. The paper seems novel and sensible and has some experimental results that are not trivial but the writing is so difficult to follow that it makes it impossible for me to assess the contributions and even check correctness. I also think that readers would find it too difficult to understand as well. This is making a complete rewrite mandatory. I have added some initial pointers that would help making this more readable but implementing these would only allow us to assess what is being done rather than guarantee acceptance. \n\nSince the rebuttal is not intended as a deadline extension I recommend rejecting this paper!\n\nMajor points:\n* I find the related work quite badly written. There is content but what the reader cares about it situating the paper in the landscape of existing methods. There is none of that here: why do we care in this work about PPO and not say Q(\\lambda). It should build up the components that were existing in the literature not just present some other methods. It needs to tell us roughly what is similar in this work to what was previously existing (roughly at least).\n* If PPN is so central it has to be presented before PTN and notation should be introduced there. Introducing formulas without explaining notation like eq (1-4) serves only to alienate the reader and the (well-intentioned) reviewer.\n* Please separately present how inference works and present the learning all in one place instead of losses in 3.1 and how to construct targets spread out until 3.2.2\n* The fact that you need so many \"note that \" should be a red flag that the writing is not right (12 times).\n* The algorithm was the most useful thing in the paper but even there it should be much clearer e.g. what is Q, how come we can write Q[j] = in consecutive lines. The second one should probably be Q[j] +=. I can't be sure because everything else is so hard to track.\n* To me if you have a network that takes in previous step and action and produces a latent next step that is an explicit transition model. How is it not ?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The consensus amongst the reviewers is that the paper discusses an interesting idea and shows significant promise, but that the presentation of the initial submission was not of a publishable standard. While some of the issues were clarified during discussion, the reviewers agree that the paper lacks polish and is therefore not ready. While I think Reviewer #3 is overly strict in sticking to a 1, as it is the nature of ICLR to allow papers to be improved through the discussion, in the absence of any of the reviewers being ready to champion the paper, I cannot recommend acceptance. I however have no doubt that with further work on the presentation of what sounds like a potentially fascinating contribution to the field, the paper will stand a chance at acceptance at a future conference.
Decision: Reject