Beyond Prioritized Replay: Sampling States in Model-Based RL via Simulated Priorities
Authors: Jincheng Mei
Yangchen Pan
Martha White
Amir-massoud Farahmand
Hengshuai Yao
Venue:  (2021)
Keywords: Experience replay
prioritized sampling
model-based reinforcement learning
Dyna architecture

Abstract: The prioritized Experience Replay (ER) method has attracted great attention; however, there is little theoretical understanding of such prioritization strategy and why they help. In this work, we revisit prioritized ER and, in an ideal setting, show equivalence to minimizing cubic loss, providing theoretical insight into why it improves upon uniform sampling. This theoretical equivalence highlights two limitations of current prioritized experience replay methods: insufficient coverage of the sample space and outdated priorities of training samples. This motivates our model-based approach, which does not suffer from these limitations. Our key idea is to actively search for high priority states using gradient ascent. Under certain conditions, we prove that the hypothetical experiences generated from these states are sampled proportionally to approximately true priorities. We also characterize the distance between the sampling distribution of our method and the true prioritized sampling distribution. Our experiments on both benchmark and application-oriented domains show that our approach achieves superior performance over baselines. 

Under review as a conference paper at ICLR 2021
BEYOND PRIORITIZED REPLAY: SAMPLING STATES IN MODEL-BASED RL VIA SIMULATED PRIORITIES
Anonymous authors Paper under double-blind review
ABSTRACT
The prioritized Experience Replay (ER) method has attracted great attention; how- ever, there is little theoretical understanding of such prioritization strategy and why they help. In this work, revisit prioritized ER and, in an ideal setting, show equiv- alence to minimizing cubic loss, providing theoretical insight into why it improves upon uniform sampling. This theoretical equivalence highlights two limitations of current prioritized experience replay methods: insufficient coverage of the sample space and outdated priorities of training samples. This motivates our model-basee approach, which does not suffer from these limitations. Our key idea is to actively search for high priority states using gradient ascent. Under certain conditions, we prove that the hypothetical experiences generated from these states are sampled proportionally to approximately true priorities. We also characterize the distance between the sampling distribution of our method and the true prioritized sampling distribution. Our experiments on both benchmark and application -oriettt--eeeeedd domains show that our approach achieves superior performance over baselines.
INTRODUCTION
Using hypothetical experience simulated from an environment model can significantly improve sample efficiency of RL agents (Ha Schmidhuber, 2018: Holland et al., 2018: Pan et al., 2018; Janner et al., 2019; van Hasselt et al., 2019). Dyna (Sutton, 1991) is a classical MBRL architecture where the agent uses real experience to updates its policy as well as its reward and dynamics models. In-between taking actions, the agent can get hypothetical experience from the model to further improve the policy.
An important question for effective Dyna-style planning is search-control: from what states should the agent simulate hypothetical transitions? On each planning step in Dyna, the agent has to select a state and action from which to query the model for the next state and reward. This question, in fact, already arises in what is arguably the simplest variant of Dyna: Experience Replay (ER) (Lin, 1992). In ER, visited transitions are stored in a buffer and at each time step, mini-batch of experiences is sampled to update the value function. ER can be seen as an instance of Dyna, using (limited) non-parametric model given by the buffer (see Seijen & Sutton (2015) for deeper discussion). Performance can be significantly improved by sampling proportionally to priorities based on errors, as in prioritized ER (Schaul et al., 2016; de Bruin et al., 2018), as well as specialized sampling for the off-policy setting (Schlegel et al., 2019).
Search-control strategies in Dyna similarly often rely on using priorities, though they can be more flexible in leveraging the model rather than being limited to only retrieving visited experiences. For example, model enables the agent sweep backwards by generating predecessors, as in prioritized sweeping (Moore & Atkeson, 1993; Sutton et al., 2008; Pan et al., 2018 8; Corneil et al., 20.8). Other methods have tried alternatives to error-based prioritization, such as searching for states with high reward (Goyal et al., 2019), high value (Pan et al., 2019) or states that are difficult to learn (Pan et al., 2020). Another strategy is to directly generate hypothetical experiences from trajectory optimization algorithms (Gu et al., 2016). These methods are all supported by nice intuition, but as yet lack solid theoretical reasons for why they can improve sample efficiency.
In this work, provide new insights about how to choose the sampling distribution states from which we generate hypothetical experience. In particular, we theoretically motivate why error- based prioritization is effective, and provide mechanism to generate states according to more

---

Under review as a conference paper at ICLR 2021
accurate enror estimates. We first prove that l2 regression with error-based prioritized sampling is equivalent to minimizing a cubic objective with uniform sampling in an ideal setting. We then show that minimizing the cubic power objective has a faster convergence rate during early learning stage, providing theoretical motivation for error-based prioritization. The theoretical understanding illuminates two issues of prioritized ER: insufficient sample space coverage and outdated priorities. To overcome the limitations, we propose a search-control strategy in Dyna that leverages model to simulate errors and find states with high expected error. Finally, we demonstrate the efficacy of our method on various benchmark domains and an autonomous driving application.
2 PROBLEM FORMULATION
We formalize the problem Markov Decision Process (MDP), tuple (S, R. including state space S, action space A, probability transition kernel P, reward function R, and discount rate y [0, 1]. At each environment time step t, RL agent observes state st S, and takes an action Ge E A. The environment transitions to the next state 81+1 ~ P(- at), and emits a scalar
reward signal rz+1 R(s; at; 8t+1). A policy is a mapping S A [0, 1] that determines the probability of choosing an action at given state.
Algorithm 1 HC-Dyna: Generic framework
The agent's objective is to find opti- mal policy. A popular algorithm is Q- learning (Watkins & Dayan, 1992), where parameterized action-values Qe are updated using = + aõ, VoQo(sE, at) for step- size a with TD-error 6, det r1+1 + Qp(s,, The policy is defined by acting greedily w.r.t. these action-values. ER is critical when using neural networks to estimate Qe, as used in DQN (Mnih et al., 2015). both to stabilize and speed up learning. MBRL has the poten- tial to provide even further sample efficiency improvements.
Input: hill climbing crit. h S ++ I. batch-size b Initialize empty search-control queue Bsc empty ER buffer Ber; initialize policy and model for ( = 1.2,... do
Add (st, dts 1,+1, T(+1) to B
while within some budget time steps do
y ea Q0($1+1,a'
$ < + aa v.h(s) //hill climbing
Add into Bsc.
for n times do
B 0
for b/2 times do Baci on-policy action a
Sample Sample s', r P(s.a)
B B (s, a. s',))) Sample b/2 experiences from Ber, add to B Update policy on the mixed mini-batch B
We build on the Dyna formalism (Sutton, 1991) for MBRL, and more specifically the recently proposed HC-Dyna (Pan et al., 2019)
as shown in Algorithm 1. HC-Dyna provides particular approach to hearch-control-i of generating states or state-action pairs from which to query the model to get next states and rewards (i.e. hypothetical experiences). It is characterized the fact that it generates states by hill climbing on some criterion function h(-). The term Hill Climbing (HC) is used for generality the vanilla gradient ascent procedure is modified to resolve certain challenges (Pan et al., 2019). Two particular choices have been proposed for h(-)) the value function v(s) from Pan al. (2019) and the gradient magnitude (Vvu(s)) from Pan et al. (2020). The former is used as measure of the utility of visiting state and the latter is considered as a measure of value approximation difficulty. The hypothetical experience is obtained by first selecting state s, then typically selecting the action according to the current policy, and then querying the model to get next state s' and reward r.
mechanism
These hypothetical transitions are treated just like real transitions. For this reason, HC-Dyna combines both real experience and hypothetical experience into mini-batch updates. These updates, performed before taking the next action, are called planning updates, as they improve the action- estimates and so the policy-usie using a model.
However, it should be noted that there are several limitations to the two previous works. First, the HC method proposed by Pan et al. (2019) is mostly supported by intuitions, without any theoretical justification to use the stochastic gradient ascent trajectories for search-control. Second, the HC on gradient norm and Hessian norm of the learned value function Pan et al. (2020) is supported by some suggestive theoretical evidence, but it suffers from great computation cost and zero gradient due to the high order differentiation (i.c.. V. (s)))] as suggested by the authors. This paper will introduce novel HC search-control method motivated by overcoming the limitations of the
2

---

Under review as a conference paper at ICLR 2021
prioritized ER method, which has stronger theoretical support than the work by Pan et al. (2019) and improved computational cost comparing with the existed work by Pan et al. (2020).
A DEEPER LOOK AT ERROR -BASED PRIORITIZED SAMPLING
In this section, we provide theoretical motivation for error-based prioritized sampling. We show that prioritized sampling can be reformulated as optimizing a cubic power objective with uniform sampling. We prove that optimizing the cubic objective provides a faster convergence rate during early learning. Based on these results, we highlight that prioritized ER has two limitations I) outdated priorities and 2) insufficient coverage of the sample space. This motivates our method in the next section to address the two limitations.
3.1 PRIORITIZED SAMPLING AS A CUBIC OBJECTIVE
In the 12 regression, we minimize the mean squared error ming 2n (i=((o(x;)) - y:) for training set T [3i, V:) )== and function approximator fo, such a neural network. In error-based prioritized sampling, we define the priority of a sample (x, E T as (ff(()) - y/; the probability of drawing sample (x, y) E T is typically q(2, y; 0) (.f( y/. We employ the following form to compute the probabilities:
(z) -
g( ys
del
E (o(;)) V/l
We can show equivalence between the gradients of the squared objective with this prioritization and the cubic power objective J. >i=1 [f(();) ) y:13. See Appendix A.3 for the proof.
Theorem 1. For constant determined by 0, T. have
B(r.)))-miiform(() [Ve(133)(fe(z) - y (B(z.)))(a..;)))
(o(L/2) (
y)
This simple theorem provides an intuitive reason for why prioritized sampling can help improve sample efficiency: the gradient direction of cubic function is sharper than that of the square function when the error is relatively large (Figure 1). Theorem further characterizes the difference between the convergence rates by optimizing the mean square error and the cubic power objective, providing solid motivation for using error-based prioritized sampling.
Theorem 2 (Fast early learning). Consider the following two objectives: (2 y) def
f (x y)² and
Ez(2, 3) def 3 |r -x-v"* yla. Denote 8, def D yl. and 8, def E v). Define the functional gradient flow updates on these two objectives:
dx, dt
dl (x: u)²}
dā.
d13 3/2 |0x y13}
1)
(2)
dr.
dt
dā:,
Given error threshold e 2 0, define the hitting time t. min, ft: 6, S c) and ie =
mini (t: 8, - e).
For any initial function value 2o s.t. do > 1, Beo E (0, such that Ve > co. to te
Proof. Please see Appendix A.4. Given the same and the same initial value of x. first we derive 7 In { do & (1-1)
) Then we analyze the condition to when t, 2 fer i.e.
minimizing the square error is slower than minimizing the cubic error.
The above theorem says that when the initial error relatively large, it faster to get to a certain low emor point with the cubic objective. We can test this in simulation, with the following minimization problems: min x² and min,2ox². We use the hitting time formulae f, = 1 In E f. =
(: 5o derived in the proof, to compute the hitting time ratio &o under different initial values to and final error value In Figure (d)) time for the cubic loss to reach a certain Ie with various To values.
see that it usually takes significantly shorter
Finding the exact value of ep would require a definition of ordering on complex plane, which leads cn Wilog 1/a-1/ and W.-) is Wright Omega function, then we have t.. Our theorem statement sufficient for the purpose of characterizing convergence rate.
3

---

Under review as a conference paper at ICLR 2021
16.
25
hn Ixp
23
2|
5'
No 0.5
4=20
3/x/
hitting ratio
No
15
13-
hitting time ratio
No- 10
5-
-1 0
-2 (b) |derivativol
(a) cubic V.S. square
(c) uo v.s. hitting time
(d) 24 V.S. hitting time
Figure I: (a) show cubic v.s. square function. (b) shows their absolute derivatives. (c) shows the hitting time ratio v.s. initial value zu under different target value xı. (d) shows the ratio v.s. the target ar; to reach under different za. Note that a ratio larger than 1 indicates a longer time to reach the given Ty for the square loss.
Implications of the above theory. The equivalence from Theorem inspires us to identify two limitations of the current prioritized ER method: 1) The equivalence requires the priorities of all samples to get updated after the training parameters get updated at each time step. 2) The equivalence requires the prioritized sampling distribution to be calculated on the whole training set; in an online RL setting, at the current time step t, we only have visited samples. These visited samples provide biased training
w.r.f. current policy which likely does not reasonably cover the state space. We will present our approach to overcome the limitations in Section 4. In the next section, we will empirically verify our theoretical findings.
3.2 EMPIRICAL DEMONSTRATION
In this section, we empirically show: 1) the practical performance of the cubic objective; 2) the importance of having sufficient sample space coverage and of updating the priorities of all the training samples; and 3) the reasons for why we should not directly use high power objective in general. We refer readers to A.6 for missing details and to A.7 for additional experiments.
We conduct experiments on supervised learning task. We generate a training set 7. = 4000 by uniformly sampling E [- 2] and adding zero-mean Gaussian noise with standard deviation a to the target (z) values, where fam(()) = sin (8TZ) if x E [-2, 0) and fain (2) = sin sin(T2) if not poiss-contaminated Pan et al. (2020) show that the high frequency region [-2, 0) is the main source of prediction error. Hence we expect prioritized sampling to make clear difference in terms of sample efficiency on this dataset.
2). The testing set contains 1k samples and the targets
We compare the following algorithms. L2: the 12 regression with uniformly sampling from T. Full-PrioritizedL2: the la regression with prioritized sampling according to the distribution defined in equation 1, the priorities of all samples in the training set are updated after each mini-batch update. Prioritized 22: the only difference with Full-Prioritizedl.2 is that only the priorities of those training examples sampled in the mini- batih are updated at each iteration, the rest of the training samples use the original priorities. This resembles the approach taken by vanilla Prioritized ER in the RL setting (Schaul et al., 2016). Cubic: minimizing the cubic objective with uniformly sampling. Power4: ming" n Σー (fo (ax)) y1 with uniformly sampling. We include it to show that there almost gain and potential harm by using higher powers.
We use 32 x 32 tanh layers for all algorithms and optimize the learning rate from the range {0.01, 0.001, 0.0001). Figure (a)-(d) shows the learning curves in terms of testing error of all the above algorithms with various settings.? We identify five important observations: 1) with a small mini-batch size 128, there is significant difference between Pull-PrioritizedL22 and Cubic; 2) with increased mini-batch size, although all algorithms perform better, Cubic achieves largest improvement and its behavior tends approximate the prioritized sampling algorithm; 3) as shown in Figure 2 (a), the prioritized sampling does not show advantage when the training set is small; 4) Prioritized l2 without updating all priorities can be significantly worse than vanilla l2 regression (uniform sampling); 5) when increasing the noise standard deviation a from 0.1 to 0.5, all algorithms perform worse and the objectives with higher power get more hurt.
The importance of sample space coverage. Observation 1) and 2) show that high power objective has to use much larger mini-batch size achieve comparable performance with the la with
We show the testing error as it is the primary concern. The training error has similar comparative performance and is presented in Appendix 3, where also include additional results with different settings.
4

---

Under review as a conference paper at ICLR 2021
04
Ront
6.56
0.5
sparod
Ful ProfftbeoL2
IQUaTed
0.4
anangge
Cabb
Aoveet
0.3
033
0.2
92-
0.2
03
2.0 0:25 030 0.
180
02
02
04
19
1e5
165
1e5
(n) 8 128, small
(b) 128,
o
0.1
[6) 512, o 0.1
(d) 512, 0 0.5
(c)
Mountain Car
Testing RMSE v.s. number of mini-batch updates. (a)(b)(e)d)) show the learning curves with different mini batch size b or Guassian noises variance added to the training targets. (a) using σ 0.1 and smaller training set (solid line for [T] 800, dotted line for [7] 1600) than others but has the same testing set size. (e) shows the a corresponding experiment in RL setting on the classical mountain car domain. The results are averaged over 50 random seeds on (a)-(d) and 30 on (c). The shade indicates standard error.
Figure 2:
prioritized sampling. possible reason is that prioritized sampling allows us to immediately get many samples from those high error region. Uniformly sampling, on the other hand, can get fewer of those samples with a limited mini-batch size. This motivates us to test prioritized sampling with a small training set where both algorithms get fewer samples. Figure 2(a) together with (b) indicate that prioritized sampling needs sufficient samples across the sample space to maintain advantage. This requirement is intuitive but it illuminates serious limitation of prioritized ER in RL: only those visited real experiences from the ER buffer can get sampled. If the state space is large, the ER buffer likely contains only small subset of the state space, indicating very small training set.
Thorough priority updating. Observation 4) highlights the importance of using an up-to-date sampling distribution each time step. Outdated priorities change the sampling distribution in an unpredictable manner and the learning performance can degrade. We further verify this phenomenon on the classical Mountain Car domain (Sutton & Barto, 2018; Brockman et al., 2016). Figure 2(e) shows the evaluation learning curves of different variants of Deep Q networks (DQN) corresponding the supervised learning algorithms. We use small 16 x 16 ReLu NN as the Q-function. We expect that small NN should highlight the issue of priority updating: every mini-batch update potentially perturbs the values of many other states. Hence is likely that many experiences in the ER buffer have the wrong priorities without thorough priority updating. We do indeed find this to be the case, with nall-PrioritizeERR performing significantly better.
Regarding high power objectives. As we discussed above, observation 1) and 2) tell us that that high power objective likely requires a large mini-batci size. Ideally, it would use a batch algorithm, i.c the whole training set, for the improved convergence rate to manifest. This requirement makes the algorithm not scalable to larger training dataset. Observation 5) indicates another reason for why high power objective should not be preferred: it augments the effect of noise added to the target variables. In Figure 2(d), the Power4 objective suffers most from the increased target noise.
4 ADDRESSING THE LIMITATIONS PRIORITIZED REPLAY: ACQUIRING SAMPLES VIA SIMULATED PRIORITIES ON CONTINUOUS DOMAINS
In this section, we propose a method mitigate the limitations of the conventional prioritized ER method mentioned in the above section. We start by the following theorem. We denote FdT rss, as the transition probability given policy π.
: S R be differentiable value function under policy parameterized by 0. Define: v(s) del E, (6', (1o) + r (s'; 0)}, and
Theorem 3. Sampling method. Given the state s E S. let o" (::6:
denote the TD error as 5(s, y; 0;) del y(s) v(s; Given some initial state sy S, define the state sequence {st} } as the one generated by state updating rule s;+1 + S, + aa V, log (5(s,, v(s)); 9.) X,, where On is sufficiently small stepsize and X, is a Gaussian random variable with some constant variance. Then the sequence {st) converges to the distribution p(*) x 1ō(s, s()))
The proof is a direct consequence of the convergent behavior of Langevin dynamics stochastic differential equation (SDE) (Roberts, 1996; Welling & Tch, 201 1; Zhang et al., 2017). We include brief discussion and background knowledge in the Appendix A.2.
"The stepsize and variance affects the temperature parameter. We avoid introducing too much notation here and simply treat the two haper-parameters in the implementation. We fix one setting across experiments.
5

---

Under review as a conference paper at ICLR 2021
In practice, can compute the state value estimate by u(s) max, Qss, a: 0t) suggested by Pan et al. (2019). In the case that a true environment model is not available, we have to compute an estimate (ss) of y(s) by learned model. Then at each time step t, states approximately following the distribution p(s) xx [6(s, v())) can be generated by
aa V log (5) )) max Q(,, a; 0,)1 + X,
(3)
where X is Gaussian random variable with zero-mean and some small variance. In the implementa- tion, observing that a, is small, we consider (ss) as constant given a state s without backpropagating through it. We provide an upper bound in the below theorem for the difference between the sampling distribution acquired by the true model and the learned model. We denote the transition probability distribution under policy π and the true model as (r, s'|s). and the learned model as P (r, s'|s). Let p(s) and p(s) be the convergent distributions described in Theorem 3 by using the true and learned models respectively. Let (:v(;.)) be the total variation distance between the two probability distributions. Define
(()) del (6s, (()))((())))))) ú(s) def (0(s, Z del J u(s)ds,
[ u(s)ds.
2 def JoES
JEES
Then we have the following bound. Please see Appendix A.5 for the proof and further interpretations.
Theorem 4. Assume: 1) the reward magnitude is bounded |r| S Rman and define Vmaa del Raux:
2) the largest model error for single state is some small value: 6s del max, der (1m)),((((11)))
and the total model ervor is bounded, i.e. = -Sess e, < cc. Then vs E S,,p((s) - p(s) S
min( Ym (p(s)c+e,)
2
Algorithmic details. We present our algorithm called Dyna-TI (Temporal Difference error) in the Algorithm in Appendix A.6. Our algorithm follows Algorithm 1, particularly, we choose the function h(s) def log (ū(s) max, Q(s, 0,)1, i.c. run the updating rule 3 to generate states.
Empirical verification of sampling distribution. We validate the efficacy of our sampling method by empirically examining the distance between the sampling distribution acquired by our gradient ascent rule in equation 3 (denoted as (-)) and the desired distribution computed by thorough priority updating p" (-) of all states under the current parameter the GridWorld domain (Pan et al., 2019) (Figure 3(a)), where the probability density can be conveniently approximated by discretization. We record the distance change when we train our Algorithm The distance between the sampling distribution fo Prioritized ER (denoted as P2(-)) is also included for comparison. All those distributions are computed by normalizing visitation counts on the discretized 50 50 GridWorld. We compute the distances of p1, P2 to p" by two sensible weighting schemes: 1) on-policy weighting: 2500 d= (s;))p((s;) D" (s,)), E (1, where dt is approximated by uniformly sample 3k states 2n=1
from recency buffer; 2) uniform weighting: 2500 > j= [p:(s;) p" (s;)), E {1,2}. All details are in Appendix A.6
2500
Figure (())() shows that algorithm Dyna-TD, either with true online learned model, maintains a significantly closer distance to the desired sampling distribution p" than PrioritizedER under both weighting schemes. Furthermore, despite the mismatch between implementation and our above Theorem 3-namely that Dyna-TD may not run enough gradient steps to reach stationary distribution-the induced sampling distribution is quite close to the one by running long gradient steps (Dyna-TD-Long) which we expect to reach stationary behavior. This indicates that the we can reduce the time cost by lowering the number of gradient steps, while keep the sampling distribution similar. In Figure 3(d), we further verify that given the same time budget, our algorithm achieves better performance, despite the fact that DQN and PrioritizedER are able to process many more samples. This makes the additional time spent scarch-control worth it.
Sample space coverage. To further illuminate that our method indeed enables a broader coverage of the model-free ER method, we visualize the DQN's ER state distributions trained with and without prioritization respectively and our algorithm'' 's search-control queue state distribution. Figure 4 shows that there is significant difference between ER's and our queue's 's distributions. Specifically, conchhl queue distribution looks more uniformly distributed across the whole state space with slightly higher density in the middle. This concentration corresponds to Figure from the work

---

Under review as a conference paper at ICLR 2021
6,025
0.0016
G
Dyna-TD Dyna: TD Long
Distence actual dscrisution to deeribution (20runs)
Dillance
500
Dyna-TD Prorkizedt Dyna-TD-Long
sctual
samptigg
1000
to desinca
(20nunst
ProfttZeER
Dyna-TD
6,000
0.0014
time stops
time stops
computation time cent coccnddie (d) timee cost V.5. performanzce
(s) GridWorkd
(b) ot-policy weightinng
(c) unilorm weighting
Figure 3: (a) shows the WridWorld taken from Pan et al. (2019). The state space is = [0, 1]2. and the agent starts from the left bottom and should learn take action from A = {up, down, right, left) to reach the right function of training steps. The dashed
top within few steps as possible. (b) shows the distance change line corresponds to our algorithm with online learned model. The corresponding evaluation learning curve in the Figure 5(c). (d) shows the policy evaluation performance as a function running time (seconds). All results are averaged over 20 random seeds and the shade indicates standard error.
by Pan et al. (2020), as the agent must learn to pass the small hole (i.e., bottleneck region) to get to the goal area. The significantly broader coverage our search-control queue distribution possibly explains the superior performance of our algorithm in Figure 5 (c)(d).
queue ER bulfer
0.8
0.8
0.6
0.6
0.4
0.4
0.2
(a) DQN buffer
(b) DQN Prioritized ER buffer
(c) DQN-TD scarch-control queue
Figure 4: (a) (b) shows the ER buffer state distributions trained by regular ER and prioritized ER respectively. (c) shows search-control queue state distribution our Dyna-TD algorithm after training for same number of environment time steps. It can be seen that our algorithm has a much broader coverage of the sample space.
EXPERIMENTS
In this section, we empirically show that our algorithm achieves stable and consistent performance across different settings. We first show the overall comparative performance on various benchmark domains. We then show that algorithm Dyna-TD is more robust to environment noise than PrioritizedER. Last, we demonstrate the practical utility of our algorithm on an autonomous driving vehicle application. Note that Dyna-TD uses the same hill climbing parameter settings across all benchmark domains. We refer readers to the Appendix A.6 for any missing details.
Baselines. We include the following baseline competitors. ER is DQN with regular ER buffer without prioritized sampling. PrioritizedER uses priority queue to store visited experiences and each experience is sampled proportionally its TD error magnitude. Note that, as per the original paper (Schaul et al.. 2016), after each mini-batch update, only the priorities of those samples in the Dyna-Value ing on value function to acquire states to populate the search-control queue. Uyna-Frequency (Pan al., 2020) the Dyna variant which performs hill climbing on the norm of the gradient of the value function to acquire states to populate the search-control queue.
mini-batch are updated. Dyna- Value (Pan et al., 2019) the Dyna variant which performs hill climb-
Overall Performance. Figure shows the overall performance of different algorithms on Acrobot, CartPole. GridWorld (Figure 3(a)) and MazeGridWorld (Figure 5(g)). Our key observations are: 1)
Dyna- Value or Dyma-Frequenae may converge to sub-optimal policy when using a large number of planning steps; 2) "yna-Frequenne has clearly inconsistent performance across different domains; 3) our algorithm performs the best in most cases: even with an online learned model, our algorithm outperforms others most of the tasks.
7

---

Under review as a conference paper at ICLR 2021
30
-102
-500
Iveng: (2orrs))
Pridr
-1000
Dyna Froquency
Dyna-Vatue
-1502
-1500
Dyna TD
400
400
-2000
bime stops Acrobot, 10
time steps
l0
Jime steps
time steps
(b) Acrobot,
GridWorld, 10
(d) GridWorld,
30
Ratur HL s
-100
420
400
300
Averae
200
202
colect
100
-1750
2000
Dyne-T
(c) CartPole, 10
(() CartPole, 30
(B) MazcCridWorld
(h) MazeGW, n2 30
Figure 5: Evaluation leamingg curves benchmark domains with planning updates 10, 30. The dashed line denotes Dyna-TD with an online learned model. results are averaged over 20 random seeds. Figure(g) shows MazeGridWorld(GGW taken from Pan et al. (2020) and the learning curves are in (h). On MazeGW, we do not show model-free baselines as it is reported that model-free free basclines do significantly worse than Dyna variants (Pan et al., 2020). We do reproduce the result of Dyna- Frequency from that paper.
-100
9co-
-900
Avcrage per Gamuno -130
-1000
-1000
-1550
1500
11300
2000
2000
Gin steps
time stops
Lime staps
Tim stups
(a) plan steps 10,
(b) plan steps 10,
0.
(c) plan stops 30,
(d) plan steps 30, 0.1
Figure 6: Evaluation learning curves on Mountain Car with different number of planning updates and different reward noise variance. At each time step, the reward is sampled from the Gaussian N(-1, a = 0 indicates deterministic reward. All results averaged over 20 random seeds.
Our interpretations of those observations are as follows. First, we can think about the case where some states have high value but low TD error. Dyna- Value may still frequently generate those states; this can waste samples and even incur sampling distribution bias, which can lead to sub-optimal policy. This sub-optimality can be clearly observed on Acrobot, GridWorld and MazeGridWorld, Similar reasoning applies original paper Pan et al. (2020), the gradient or Hessian norm have very different numerical scales and highly depend the choice of the function approximator algorithm requires finely tuned parameter settings, as the testing domain is varied, which possibly explains its inconsistent performances across domains. Third, notice that even though each algorithm runs the same number of planning steps, the model-based algorithms perform significantly better. This provides evidence for the benefits of leveraging the generalization power of the learned value function and a model. In contrast, model-free methods can only utilize visited states.
Frena-FFreenc.. Second, for Dyna-Frequeet Frequency, indicated by the
domain. This indicates that the
Robustness to Noise. As corresponding experiment the supervised learning setting in Section we show that our algorithm is more robust to increased noise variance than PrioritizedER. Figure shows the evaluation learning curves on Mountain Car with planning steps 10, 30 and reward noise standard deviation {0, 0.1) We would like to identify three key observations. First, our algo- rithm's relative performance to PrioritizedER resembles the null-PrioritizedL22 to PrioritizedL.2 from the supervised learning setting, as Full-Prioritizes 2 is more robust to target noise than PrioritizedL2. Second, our algorithm achieves almost the same performance as Dyna- gyna--Frquency which is claimed to be robust to noise by Pan al. (2020). Last, observed other environments, usually all algorithms can benefit from the increased number of planning steps; however, PrioritizedER and ER clearly degrade when using more planning steps with noise present.
8

---

Under review as a conference paper at ICLR 2021
Practical Utility in Autonomous Driving Application. We study the practical utility of our method in an autonomous driving application (Leurent, 2018) with an online learned model. As shown in Figure (a), we test the roundabout-vV domain, where the agent (i.e. the green car) should learn to go through a roundabout without collisions while maintaining as high speed as possible. We would like emphasize that there significantly lower number of car crashes with the policy learned by our algorithm on both domains as we show in Figure 7(b). This coincides with our intuition. The crash should incur high temporal difference error and our method of actively searching such states by gradient ascent. This ensures the agent gets sufficient training in this states during the planning stage, so that it learns to avoid them.
Figure
shows the round- about domain, where C R (b) shows the corresponding eval- uation learning curves in terms of number of crashes
PriottizedER Dyna TD
Cumulathv
Car (50runs)
function driving time steps. The results are averaged over 50 random seeds. lea The shade indicates standard error.
0.5
100
15
Driving time steps
(a) roundabout-v)
(b) Num. of crashes
DISCUSSION
In this work, we provide theoretical justification for why prioritized ER can help improve sample efficiency. We identify crucial factors for it to be effective: sample space coverage and thorough priority updating. We then propose to sample states by Langevin dynamics and conduct experiments to show our method's efficacy. There are several interesting directions for future work. One is to study the effects of model error on sample efficiency with our search control strategy. Another is to apply method with feature-to cectuure-tofffattee fe-tuue model, which can improve our method's scalability. On the theory side, our cubic objective explains the original TD-error based prioritized ER (Schaul al., 2016). However, there other types of choices beyond TD-error based prioritization, such as distribution location or reward-based prioritization (Lambert et al., 2020). Whether these alternative prioritizations can also be formulated surrogate objectives are interesting future directions. In a concurrent work, Fujimoto et al. (2020) established an equivalence between loss functions and sampling distributions, which bears similarities to our Theorem 1. However, it is not clear if similar optimization benefits shown in our Theorem 2 are enjoyed by more general loss functions and sampling distributions, which requires further investigations.
REFERENCES
Abadi, M., Agarwal, A., Barham, P., Brevdo, E.,, Chen, Z., and et al. TensorFlow: Large-scale machine learning on heterogenenus systems. Software available from tensorflow.org. 2015.
Brockman, G., Cheung, V., Pettersson, L., Schneider, Schulman, Tang, J., and Zaremba, W. OpenAl Gym. arXiv:1606.01540. 2016.
Chiang, T.-S., Hwang, C.-R., and Sheu, S. Diffusion for global optimization in R". SIAM Journal Control and Optimization, pp. 737-753, 1987.
Corneil, D. S., Gerstner, W. and Brea, J. Efficient model- deep reinforcement learning with variational state tabulation. In International Conference Machine Learning, pp. (049-1058, 2018.
de Bruin, T., Kober, J., Tuyls, K., and Babuska, R. Experience selection in deep reinforcement learning for control. Journal of Machine Learning Research, 2018.
Durmus, Moulines, E. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probabiliiy, pp. 1551-1587, 2017.
Fanace-T, H. and Gama, J. Event labeling combining ensemble detectors and background knowledge. Progress in Artificial Intelligence, pp. 1-15, 2013.
Fujimoto, S., Meger, D., and Precup. D. An equivalence between loss functions and non-uniform sampling in experience replay. Advances in Neural Information Processing Systems, 33, 2020.

---

Under review as a conference paper at ICLR 2021
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, 2010.
Goyal, A.. Brakel, P., Fedus. W., Singhal, S., Lillicrap. Levine, S., Larochelle, and Bengio, Recall traces: Backtracking models efficient reinforcement learning. International Conference on Learning Representations, 2019.
Gu, S., Lillicrap, T. P.. Sutskever, L., and Levine, S. Continuous Deep Q-Learinn with Model-based Acceleration. In International Conference on Machine Learning, pp. 2829-2838, 2016.
Ha, D. and Schmidhuber, J. Recurrent world models facilitate policy evolution. Advances in Neural Information Processing Systems, pp. 2450-2450655 2-6024462, 2018.
Holland, G. Z., Talvitie, E., and Bowling, M. The effect of planning shape dyna-style planning in high- dimensional state spaces. CoRR, abs/1806.01888 818.0008., 2018.
Janner, M., J., Zhang, M., and Levine, S. When to trust your model: Model-based policy optimization. Advances Neural Information Processing Systems, pp. 12519-1222 12530, 2019.
Kingma, D. and Ba, J. Adam: A method for stochastic optimization. International Conference on Learning Representations, 12 2014.
Lambert, N., Amos, B., Yadan, O., and Calandra, R. Ohjective mismatch in model-based reinforcement learning. arXiv preprint 200tv:2002.0452.. 2020.
Leurent, E. An environment for autonomous driving highway-ent env, 2018
Leurent, E., Blanco. Y., Etimov, D., and Maillard, O. Approximate robust control of uncertain dynamical systems. CoRR, 0tss/1903.00220 2019.
Lin, L.-J. Self-Improving Reactive Agents Based On Reinforcement Learning, Planning and Teaching. Machine Learning, 1992.
Mnih. V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J.. Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. Human-level control through deep reinforcement learning. Nature, 2015.
Moore, A. W. and Atkeson, C. G. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning. pp. 103-130, 1993.
Pan. Y.. Zaheer, M., White, A., Patterson, A., and White, M. Organizing experience: a deeper look at replay mechanisms for sample- planning in continuous state domains. In International Joint Conference on Artificial Intelligence, pp. 4794-4800, 2018
Pan, Y., Yao, H., Farahmand, A.m.., and White, M. Hill climbing on value estimates for scarch control in dyna.
In International Joint Conference Artificial Intelligence, 2019.
Pan, Y., Mei, J., and massoud Farahmand, A. Frequency-based search-control in dyna. In International Conference on Learning Representations, 2020.
Roberts, Gareth O.and Tweedie, R. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, pp. 341-363, 1996.
Schaul, T.. Quan, J., Antonoglou, I., and Silver, D. Prioritized Experience Replay. International Conference on Learning Representations, 2016.
Schlegel, M., Chung, W., Graves, D., Qian, J., and White, M. Importance resampling for off-policy prediction. Advances in Neural Information Processing Systems 32, pp. 1799-1880 1809, 2019.
Sutton, R. S. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. In MI. 1990.
Sutton, R. S. Integrated modeling and control based reinforcement learning and dynamic programming. In Advances Neural Information Processing Systems, 1991.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
10

---

Under review as a conference paper at ICLR 2021
Sutton, R. S.. Szepesvári, C., Geramifard, A., and Bowling. M. Dyna-style planning with linear function approximation and prioritized sweeping. In UAI, pp. 528-536, 2008.
parametric models in reinforcement learning? In Advances Neural Information Processing Systems, pp. 14322-14337 2019.
Hasselt, H. P.. Hessel, M., and Aslanides, J. When
Seijen, H. and Sutton, R. A deeper look planning learning from replay. International Conference on Machine Learning, pp. 2314-2322, 2015.
Watkins, J. C. H. and Dayan, P. Q-learning. Machine Learning, pp. 279-292, 1992.
Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient Langevin dynamics. In International Conference on Machine Learning, pp. 681-688, 2011.
Zhang, Y., Liang, P., and Charikar, M. A bitting time analysis of stochastic gradient langevin dynamics. In Conference on Learning Theory, pp. 1980-2022, 2017.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
In Section A.I, we introduce some background in Dyna architecture. We briefly discuss Langevin dynamics and its computation cost in our case in Section A.2. We then provide the full proof of Theorem 2 in Section A.4. We present the proof for Theorem in Section A.5. Details for reproducible research are in Section A.6. We provide supplementary experimental results in Section A.7.
A.1 BACKGROUND IN DYNA
Dyna integrates model-free and model-based policy updates in an online RL setting (Sutton, 1990). As shown in Algorithm 2. at each time step, Dyna agent uses the real experience to learn a model and performs model-free policy update. During the planning stage, simulated experiences are acquired from the model to further improve the policy. It should be noted that the concept of planning refers to any computational process which leverages a model to improve policy, according to Sutton & Barto (2018). The mechanism of generating states or state-action pairs from which to query the model is called search-control, which of critical importance to the sample efficiency. There are abundant existing works (Moore & Atkeson, 1993; Sutton et al., 2008; Gu et al., 2016; Pan et al., 2018: Corneil et al., 2018; Goyal et al., 2019; Janner et al., 2019; Pan et al., 2019) report different level of sample efficiency improvements by using different way of generating hypothetical experiences during the planning stage.
Algorithm 2 Tabular Dyna
Initialize Q(s, a); initialize model M(s, a). V(s,a) E x A while true do
observe 8, take action by c-greedy w.r.t Qss,)
execute a, observe reward and next State Q-learning update for ((s, a)
update model M(s, a) (i.e. by counting) store (s, a)) into search-control queue for i=1:d do
sample (š, ā) from search-control queue
(3', RR) + ((5 a) simulated transition
Q-learning update for Q(3, â) // planning update
A.2 DISCUSSION ON THE LANGEVIN DYNAMICS
Define a SDE: dt())= = df + V2dB,, where B, E Rd is d-dimensional Brownian motion and U is a continuous differentiable function. It turns out that the Langevin diffusion (Wi)220 converges to unique invariant distribution p(x) x exp (Uxx) (Chiang et al., 1987). By applying the Euler-Maruyama discretization scheme to the SDE, we acquire the discretized version Yk+1 Y2 + 0 VU(Y)) + 22a++1 7 where (Zx) is an i.i.d. sequence of standard d- dimensional Gaussian random vectors and (ax)221 is sequence of step sizes. It has been proved that the limiting distribution of the sequence (Yı)a21 converges to the invariant distribution of the underlying SDE Roberts (1996): Durmus & Moulines (2017). As result, considering U (-) as 8(-). Y as s completes the proof for Theorem 3.
Computational time cost. It should be noted that the Langevin Dynamics Monte Carlo method we used for generating states does introduce additional computation time cost. However, in the main body of the paper, we already show that the time cost worths 3(d).
In theory, the computational time is reasonably small. Although each gradient ascent step takes one backpropagation, this backpropagation is w.r.t. a single state, not mini-batch. Let the mini-batch size of updating DQN be b. and the number of gradient steps be k. If we assume one mini-batch update takes Occ), then the time cost of Dyna-TD TD is (kc/b)). We would like to highlight that, though our approach incur higher computational cost, but is able use fewer samples (i.e. fewer physical interactions with real environment) to achieve better performance. The cost of physical interactions could be higher in practical situations. When really needed, there are intuitive engineering tricks to reduce the computational cost. For example, we can learn low dimensional embedding first and
12

---

Under review as a conference paper at ICLR 2021
build model in such space; and then the gradient ascent can be done w.r.. the feature instead of the raw input/observation itself. To further save time, we can also sacrifice bit the accuracy and do the gradient ascent every certain number of time steps to lower down the amortized cost. Reducing time cost not our current focus.
A.3 PROOF FOR THEOREM 1
Theorem 1. For a constant determined by 0, T, we have
- yl (B( [VV// -
Proof.
The proof is very intuitive. The expected gradient of the uniform sampling method is
1
[o( Vo(o(()) -y:)²
i=1
(aau)aalaaue)) - y) Σ
(z,, 0) Vo(o -1)²
1=1
(fo(o)) U Vo(oo() - y)²
Σ 2
i=1 (x;z Yo
n
E (or y/
Σ 12 1=
(fo V/
Setting c Σn [f((x))-d completes the proof.
A.4 PROOF FOR THEOREM 2
Theorem 2. Consider the following two objectives: (2 v) del |x - y Denote & def |x, - y/. and 8, def j y/- Define the functional gradient flow updates on
2 (x-y)²² and (s y) def
these two objectives:
dx. dt
d (x: ")²} dz, dx,
dlt jāt - 21
(4)
dt
dē,
Given error threshold e 2 O, define the hitting time t. del min; 6, S E} and is del min (t: S c). For any initial function value 2o s.t. 50 1, 3eo (0, 1) such that Ve co, te 2 te
Proof. For the gradient flow update on the la objective, we have,
d8 (2l(x.
dlz(zz,)) v)
dōg dx.
(5)
dt
dô:
dx, dt
òe sgn(x; - y) [-n (It - y)]
òz sgn(X: - y) [-n -gnlsgn(z 3) 8c]
(7)
57 - (z
(8)
which implies,
d(lnn (2(xe,
de2(x1, v)
-2
(9)
(2( dt
Taking integral, we have,
In f2 v) - In (2(x0))) = -2
(10)
which is equivalent (letting e),
t- der 1
In (2(00))) 1
do
1
6g
In
In
(11)
2n
(z(
17
8
7
13

---

Under review as a conference paper at ICLR 2021
On the other hand, for the gradient flow update the ls objective, we have,
dlz(01. 4)
dls(Er. v)
dō,
(12)
dt
dōg
dī: dt
88 sgn (it y) [-n -1 8, sgn(a - w)
(13)
-n 8 = -33 11 (fz(āzz v))
(14)
which implies,
di d(((((a,,)))}}
1 (Es( v))=
$. dlz(Er, 33 -77.
(15)
dt
dt
Taking integral, we have, which is equivalent to (letting 6; = c),
(Ca(5r,)))) k)) - (ls( 1)) 1)) 3 17
-7-
(16)
del
())( (E3(@u. 8))
1
(1
(17)
33 7
82
c
80
Then we have,
dg
1
te
(18)
1
6
60
In
In
(19)
60
80
Define the function (xx In x x is continuous and maxa;0 fxx f(1) -1 We
have lim f(xx = lim / (xx = xc, and f(-) is monotonically increasing for x E (0, 1] and
monotonically decreasing for x E (1, 20).
Given & > I, we have (0o) < f(1) = 1. Using the intermediate value theorem for f(-) on (0, 1]. we have Jeo 1, such that f(co) f(6o). Since f(-) is monotonically increasing on (0, 1] and
monotonically decreasing on (1, oo), for any E [Eo: do). we have f(e) 2 fōo)). Hence we have,
1 if(c) - [(66)) 2 O.
te ie
17
Remark 1. Figure 8 shows the function f(x) In - O. Fix arbitrary x' >> 1, there will be another root 6o s.t. f(En) = f(x).. However, there is no real-valued solution for eg. The solution Wllo 1/6, 11/6-118----1 mijj where W--) is Wright Omega function. Hence, finding the
in C is cu exact value of eg would require a definition of ordering on complex plane. Our current theorem statement is sufficient for the purpose of characterizing convergence rate. The theorem states that there always exists some desired low error level < 1, minimizing the square loss converges slower than the cubic loss.
A.5 PROOF FOR THEOREM 4
We now provide the error bound for Theorem 4. We denote the transition probability distribution under policy with the true model as (r, s' s'|s); denote that with the learned model as p= sss).. Let p(s) and p(s) be the convergent distributions described Theorem 3 by using true model and learned model respectively. Let d,.(:,)) be the total variation distance between two probability
distributions. Define u(s) 18(s, y(s)),, ū(s) 18(s, ((s)) Z Sees u(s)ds, S i(s)ds. Then we have the following bound.
'Note that 60 by the design of using gradient descent updating rule. If the two are equal, = fz = 0 holds trivially.
14

---

Under review as a conference paper at ICLR 2021
-1
-2
-4
f(x) In 1
5
Figure The function f(x) = In 1
21 2 > 0. The function reaches maximum at x =
Theorem 4. Assume:
the reward magnitude is bounded [r] I Rmar and define Vmaz del Rmax 2)
1-7
the largest model error for a single state is some small value: 6, max, der (-|s), P. (-1s)) and the total model error is bounded, i.e. e def SSeS Edds < co. Then
vs E S, p(s) - p(s) I min( V Vana (p(s)c +
Vinaz (p(s)c co)
2
Z
Proof. First, we bound the estimated temporal difference error. Fix an arbitrary state E S, it is sufficient the consider the case u(s) i(s), then
(u(s) - ū(s){ u(s) - i(s) =B(ns/)aptl (r + (00 (s')] E E + 70 (s')l (o+ (P" (5', r(s) - (5 (d(srss))dd'
Rmax Rmmay / (PT(s' pT r(s))ds''r
{(mmox + Y
SVmandeo (PT ((()), S Vinasts
Now, we show that 7 - 21 S Vmaae.
2 - 2 = /f u(s)ds - - ū(s)ds) = =1 =1/r (u(s) -((s))))
WES
/ e,ds = Vimane
< lu(s) - -i(s)ldss S Viman
SES
JEE
Consider the case p(s) p(s) first.
p(s) - {(s) = u(s) a(s)
7 2
u(>)
u(s)
Vmazts u(8) u(x) + Zmaazts
Z
Ză
u(s) V maaz ZVmaaee
Vmaaz (p(s)e + Ca)
75
2
15

---

Under review as a conference paper at ICLR 2021
Mcanwhile, below inequality should also hold:
p(s) f(()) = u(s))
i(s)
ū(s) + Vmants
i({))
Z Z
Z
2
a(s) - Z + ZV Vmmazts
Vmaz (f(s)c c.)
zZ
Z
Because both the two inequalities must hold, when p(s) p(()) > 0, we have:
p(s) p(s) S min( Vmaz (p(s)c + (x) Vmaz (f()) cc)
2
Z
It turns out that the bound is the same when p(s) S ((s). This completes the proof.
Remark. This bound actually indicates that (p(s) p(s) should be small, Because if p(s) 5 is much larger Di, then we may expect the second term the min function would be chosen. During early learning, although the model error can be large, but 2, Z should be also very large. The total model error is scaled by p(s) or ((s) and it should be small. We may expect nice approximation even when the model is not that perfectly learned.
A.6 REPRODUCIBLE RESEARCH
Our implementations are based on tensorflow with version 1.13.0 (Abadi et al., 2015). We use Adam optimizer (Kingma & Ba, 2014) for all experiments.
A.6.1 REPRODUCE EXPERIMENTS BEFORE SECTION
Supervised learning experiment. For the supervised learning experiment shown in section 3, we use 32 32 tanh units neural network, with learning rate swept from {0.01, 0.001, 0.0001, 0.00001) for all algorithms. We compute the constant e as specified in the Theorem 1 at each time step for Cubic loss. We compute the testing error every 500 iterations/mini-batch updates and evaluation learning curves are plotted by averaging 50 random seeds. For each random seed, we randomly split the dataset testing set and training set and the testing has 1k data points. Note that the testing set is not noise-contaminated.
Reinforcement Learning experiments in Section 3. We use particularly small neural network 16 x 16 to highlight the issue of incomplete priority updating. Intuitively, large neural network may be able to memorize each state's 's value and thus updating one state's value less likely to affect others. We choose a small neural network, in which case complete priority updating for all states should be very important, We set the maximum ER buffer size as 10k and mini-batch size as 32. The learning rate is 0.001 and the target network is updated every 1k steps.
Distribution distance computation in Section 4. We now introduce the implementation details for Figure The distance is estimated by the following steps. First, order compute the desired sampling distribution, we discretize the domain into 50 x 50 grids and calculate the absolute TD error of each grid (represented by the left bottom vertex coordinates) by using the true environment model and the current learned Q function. We then normalize these priorities to get probability distribution p". Note that this distribution considered as the desired one since we have access to all states across the state space with priorities computed by current Q-function at each time step. Second, we estimate our sampling distribution by randomly sampling 3k states from search-control queue and count the number of states falling into each discretized grid and normalize these counts to get P1. Third, for comparison, we estimate the sampling distribution of the conventional prioritized ER (Schaul al., 2016) by sampling 3k states from the prioritized ER buffer and count the states falling into each grid and compute its corresponding distribution p2 by normalizing the counts. Then we compute the distances of P1-P2 p" by two weighting schemes: 1) on-policy weighting: 2250 di (s)))p((s;) p" (s,) e 21, where d" is approximated by uniformly sample 3k states from a recency buffer and normalizing their visitation counts the discretized GridWorld; 2) uniform weighting: 2500 Σ (p<(s;) -pp (s))), E (1, We examine the two weighting schemes because of two considerations: for the on-policy weighting, concern about the asymptotic convergent
16

---

Under review as a conference paper at ICLR 2021
behavior and want to down-weight those states with relatively high TD error but get rarely visited as the policy gets close to optimal; uniform weighting makes more sense during early learning stage, where we consider all states are equally important and want the agents to sufficiently explore the whole state space.
A.6.2 REPRODUCE EXPERIMENTS IN SECTION 5
For our algorithm, the pseudo-code with concrete parameter settings is presented in Algorithm 4.
Common settings. For all domains other than roundabout-vO, we use 32 x 32 neural network with ReLu hidden umits except the Dyma-Frequency which uses tanh units as suggested by the author (Pan et al., 2020). $ Except the output layer parameters which were initialized from a uniform distribution [-0.003, 0.003], all other parameters are initialized using Xavier initialization (Glorot & Bengio, 2010). We use mini-batch size b = 32 and maximum ER buffer size 50k. All algorithms use target network moving frequency 1000 and we sweep learning rate from {0.001, 0.0001 We use warm up steps = 5000 (i.e. random action is taken in the first 5k time steps) to populate the ER buffer before learning starts. We keep exploration noise as 0.1 without decaying.
able to keep the same parameter setting across all benchmark domains: aa = 0.1, c = 20 and learning rate 0.001. For all Dyna variants, we fetch the same number of states (m 20) from hill climbing (i.e. search-control process) as Dyna-TD TD does, and use c = 0.1 and set the maximum number of gradient step as k = 100 unless otherwise specified.
Meta-parameter settings. For algorithm Dyna-TD,
Our Prioritized ER is implemented as the proportional version with sum tree data structure. To ensure fair comparison, since all model-based methods are using mixed mini-batch of samples, we use prioritized ER without importance ratio but half of mini-batch samples are uniformly sampled from the ER buffer as strategy for bias correction. For Dyna- Dyna-Value and Dyna-Frequenge we use the setting as described by the original papers.
For the purpose of learning an environment model, we use 64 64 ReLu units neural network to predict s' and reward given state-action pair 8, and we use mini-batch size 128 and learning rate 0.0001 to minimize the mean squared error objective for training the environment model.
Environment-specffe settings. All of the environments are from OpenAl (Brockman et al., 2016) except that: 1) the GridWorld envirnoment taken from Pan et al. (2019) and the MazeGridWorld from Pan et al. (2020); 2) Roundabout-v0) is from Leurent et al. (2019). For all OpenAl environments, we use the default setting except on Mountain Car where we set the episodic length limit to 2k. The GridWorld has state space S = [0, 1J2 and each episode starts from the left bottom and the goal area is at the top right (0.95, 1.0]². There is a wall in the middle with a hole to allow the agent to pass. MazeGridWorld is more complicated version where the state and action spaces are the same as GridWorld, but there are two walls in the middle and it takes a long time for model-free methods to be successful, On the this domain, we use the same setting as the original paper for all Dyna variants. We use exactly the same setting as described above except that we change the Q network size to 64 x 64 ReLu units, and number of search-control samples is m 50 as used by the original paper. We refer readers to the original paper (Pan et al., 2020) for more details.
On roundabout-v0 domain, we use 64 64 ReLu units for all algorithms and set mini- size as 64. For Dyna-TD, we start using the model after 5k steps and set m = 100, a, = 1.0, k = 500 and we do search-control every 10 environment time steps reduce computational cost. To alleviate the effect of model error, we use only 16 out of 64 samples from the search-control queue in a mini-batch.
A.7 ADDITIONAL EXPERIMENTS
The main purpose of the additional experiments here is to strengthen our claims from Section
Learning curve in terms of training error corresponding to Figure 2. In Section 3. we show the learning curve in terms of testing error. We now show training error to closely match our theoretical result 1. As a supplement, we include the learning curve in terms of testing error in Figure 9.
'Not that this is one of its disadvantages: the search- control of Dyna-Frreuence Frequency requires the computation of Hessianngradienn product and it is empirically observed that the Hessian is frequently zero when using ReI.u as hidden units (Pan al., 2020).
17

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Dyna-TD
Input: mt number of states fetch through search-control: Bac: empty search-control queue; Ber: ER buffer; Ea: threshold for accepting a state; initialize Q-network Qo
for t 1,2....00 do
Observe (st, ae, 1441:Pe41. and add it to Ber
Hill climbing on absolute TD enror
Sample from B 0, +-
while c < m do
ÿ 4 s'rpb s,a) |r max. Qo(s',a)
Update s by rule equation 3
if is out of the state space then
Sample from B +- restart continue
if ssssll2/vdd ca then // d is the number of state variables, i.c. S c Rd Add into Bsc, 8, c+
I/ planning updates for n times do
Sample mixed mini-batch with half samples from Ba and half from Ber Update Q Q-newwork parameters by using the mixed mini-batch
0.5
0.5
0.7
PrioritizedL2
Full PrioritizedL2
Boot squared
Roo sauared ems
d
Cubic
Power4
over
ever
over
0.1 20000
40000
60000 80000
100000
9.1
20000
40000
60000 800c0 100000
0.5 20000
40000 60000 80000 100000
() 128, o 0.1
(b) = 512, = 0.1
(c) 512, 0.5
Figure 9: (igure(a)(bic)) show the training RMSE function number of mini-batch updates with diffcrent mini-batch sizes or Guassian noises with different added to the training targets. The results are averaged over 50 random seeds. The standard error is small enough to get ignored.
Learning curve with a larger neural network on the sin dataset. We try to eliminate the effect of neural network size. Hence we use a larger neural network size (128 x 128 tanh units) on the same sin dataset. As one increase the mini-batch size from 128 to 512, the high power objective versions still moves closer to FullPrioritizedl.,,
from Figure 10, FullPrioritizedL2 still performs the best and when
saw in Figure 2.
Learning curve with on a real-world dataset. To illustrate the generality of our Theorem 1, we also conduct tests on frequently cited regression Bike sharing dataset Fanaee-T & Gama (2013). The data preprocessing is as follows. We remove attributes: date, index, year, weather situation 4, weekday 7, registered, casual. We use one-hot encoding for all categorical variables. We scale the target to [o, 1] and scale it back when computing training eтrоrs. We use a 64 x 64 ReLu units neural network with mini-batch size 128 and learning rate 0.0001 for training.
It should be noted that the behavior of Cubic is consistent on the previous sin example and on this real world dataset: it gets closer to FullPrioritizedl.22 as we increase the mini-batch size. Another observation is that the Power4 objective is highly variant on this domain, because the real world data should noisy and the high order objective suffers. This observation corresponds to what we observed in Section 3. 1, where we show that high power objective is sensitive to the noise.
18

---

Under review as a conference paper at ICLR 2021
Algorithm 4 Dyna-TD TD with implementation details
Input or notations: = 20: number search-control states to acquire by hill climbing, ks = 100: the budget of maximum number of hill climbing steps; p 0.5: percentage of samples from search-control queue, d C TR:;; empty search-control queue Bgc and ER buffer Ber
empirical covariance matrix: Dg +
Mas 0 E 1d 14, 0 Rd (auxiliary variables for computing empirical covariance matrix,
sample average will be maintained for Pes Ma)
n, +- count for parameter updating times, 4- 1000 target network updating frequency <a <- 0: threshold for accepting state
Initialize Q network Qe and target Q network Qe
for & = 2, do
Observe (s, a, s', r) and add it to Ber Mas (ta(t=1)+s8 M/s (,(t-1)+e
Σ, + Poo Hap
6a c (1-3)cc B||s' a|12 for 3 0.001 // Hill climbing on absolute TD error
Sample from Ber, c 0, 8, 0
while
and < ki do // since environment is deterministic, the environment model becomes Dirac-delta distribu- tion and we denote it deterministic function M S A S R s' r < a)
ÿ + max, Qo(s', a) // add a smooth constant 10-5 inside the logarithm
s + + Ota V. log(bý - max, Q 0,), + 10-5) NNNx0(NXON,, N(0,0.01..)
if is out the state space then
// restart hill climbing
Sample from B S continue
if ||
1 s||2/Vd ca then Add into Bse, 3 s.c
i 1+11
for times do
Sample a mixed mini-batch with proportion p from Bsc and from B Update parameters 0 (i.e. DQN update) with b
nh +- 11, +1 if mod(n, (n, 0 then
Qo f- Q9
19

---

Under review as a conference paper at ICLR 2021
0.50
0.50
0.50
PrioritizedL2
Rest squared error over
Full-Prioritized12
Roct neat
Roo
mea
Cubic
erro
cmor
Power4
ever
oven
15cnursl
20000 40000 60000
80000 100000
20000 40000
60000
80000 100000
20000
40000 60000 80000 100000
(a) 128, a = 0.1
(b) b b= 512, 0.1
(c) 512, 0 = 0.5
L2
PrioritizedL2
Full Paloriiriiti
mean
squared
squar
squar
Cubic
avenged (50eams)
avcraged
avcraged
Powerd
(steure)
(strure)
100000
(d) b = 128, o = 0.1
(e) b = 512, a 0.1
(f) = 512, 0.5
Figure 10: (ig)re(a)())c) show the testing RMSE as a function of number of mini-batch updates with different mini-batch sizes or Guassian noises with different added to the training targets. (f) show the training RMSE. The results averaged over 50 random sceds. The standard error small enough get ignored. Note that the target variable the testing
poise-contaminated.
PrioritizedL2
Full Prioritized22
Rest mean emar over
Best mean wrter (zceuns)
Cabic
10-
10-
10000 20000
30000 40000 50000
10000 20000 30030 40000 50000
128
(b) b 512
Figure 11: (i))) show training RMSE as function number of mini miti-batch updates on Bike sharing dataset. The results are averaged over random seeds. The shade indicates standard error.
20


Reviews:
[{"review_id": "stdGmEWAYU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "\n##########################################################################\n \nSummary:\n\nThe paper proposes a new way of prioritization in experience replay and Dyna-style planning methods. In particular, it proposes to exploit a learned model to actively search for states with high expected errors. The states are then prioritized proportional to the expected errors. The authors motivate the approach by a theoretical/empirical observation that the prioritized optimization of L2 loss is equivalent to the direct optimization of cubic loss. More specifically they tackle (1) outdated priorities of training samples, (2) insufficient coverage of the sample space; which are identified as the main shortcomings of previously explored prioritization methods. \n\n##########################################################################\n\nReasons for score: \n\nOverall, I vote for borderline acceptance. I like the idea of exploiting a learned model to better prioritize the samples for planning. The experiments make a compelling case for a full update of the sampling priorities over partial updates and that Dyna-TD approximates a sample from the full distribution better. However, experiments fail to show how exactly insufficient coverage of the sample space is being tackled. Moreover, the empirical results in real domains fail to show a significant performance increase over Dyna-freq when a learned model is used. Assuming access to the real model for updating the priorities may not be fair to other approaches when the metric in question is the sample efficiency. Hopefully, the authors can address my concern in the rebuttal period. \n \n##########################################################################\n \nPros: \n\n1. The paper tackles one of the fundamental issues of training any RL agent - sampling mechanisms from the experience replays. For me, the problem itself is real and practical.  \n2. The proposed Dyna-TD prioritization scheme is novel such that it actively searches for states with a high expected error.  It is more compute efficient than updating priorities for all samples in an experience replay while maintaining a close approximation to the same. Moreover, it also provides a sampling method for sampling imaginary transitions from the model using the same method. \n3. This paper provides comprehensive experiments, including theoretical analysis to show the effectiveness of the proposed framework. The proposed method outperforms previous prioritization methods with access to the real model and  is still comparable to the baselines with the learned online model; \n \n##########################################################################\n \nCons:  \n\n1. Although the proposed method provides several ablation studies, I still suggest the authors conduct the following ablation studies to enhance the quality of the paper: \n\n(a) How does Dyna-TD compare with Full update variants of Dyna-Value and Dyna-Freq prioritization mechanisms. \n\n(b) Addition of Dyna-TD and Dyna-Freq methods for the Car Roundabout domain.  \n\n2. It is not clearly evident how insufficient coverage of sample space affects the learning process, and how Dyna-TD is specifically tackling this over Dyna-value or Dyna-Freq.\n \n3. The use of a real model for prioritization is not fair when compared with baseline approaches that are not allowed to use the real model for search control.  \n\n##########################################################################\n \nQuestions during the rebuttal period: \n \nPlease address and clarify the cons above \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4DH5pcC3NxF", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "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": "\nPaper Summary:\n\nThis paper provides an update to a specific variant of model-based RL, Dyna-HC. \nDyna is a relatively old MBRL algorithm combining model-learning and model-free policy updates by leveraging the model as a simulator.\nThe paper shows how prioritized sampling from an experience replay buffer mirrors a cubic loss function and uses this insight to show prioritized state selection for simulated policy rollouts via hill climbing (gradient ascent).\n\n-----\n\nReview summary: \nIncremental update to Dyna formulation in a busy paper that is hard to place in the literature.\nOverall, the paper supports it's claims well, but it does not fit itself into the broader picture well. HC-Dyna is very recent work with only one small difference. The authors need to better motivate the work and draw clear boundaries to what was done in the past for it to be suitable for publication.\n\n---- \nComments:\n1) The authors make some loose claims about model-based reinforcement learning. For example, the first sentence of the intro says MBRL \"can significantly improve sample efficiency\" but does not say what sample efficiency is being improved relative to. This is repeated in the last sentence of paragraph two of 2 Problem Formulation.\n\n2) It should be said, this paper is well-written at a low-level. I found relatively few sentences confusing and few typos.\n\n3) The results in Figure 5 do show a continued improvement of the Dynamics approach on more complex tasks. This is promising. It would be interesting to include other baselines in such a well-known task (such as cartpole). A reward of 500 in cartpole is strange, in my reading it generally maxes out at 200. \n3b) why was the episodic limit of mountain car increased to 2k? From what is it increased?\n\n4) In A.6.2 Reproduce - Common Settings, there is a lengthy list of training details. Were these required for performance? \n\n5) in \"regarding high power objectives\" the authors say that the high objective requires a larger mini-batch, which is a weakness. Can this be partially mitigated by a bigger learning step in practice, because as the batch gets closer to the whole dataset, there is less noise and risk of taking bad gradient steps? Could this partially account for the difference in computation cost?\n\n6) The algorithmic details in the paper should likely replace the algorithm provided \"HC-dyna: generic framework,\" especially considering HC-dyna is very new and most readers are likely to be unfamiliar, I am not sure it gains much. Moving important content like this to the appendix is not desirable.\n\n7) Figure 3d is very interesting and appreciated. Would like to see more RL papers do this. The numerical evaluation is relatively well done.\n\n-----\nConcerns:\n\n1) This paper lacks context into the field and motivation for why I should care. This is highlighted by ending with a discussion section (which is mostly just a short summary and a future work section). Way conclusions should the reader draw? \n1a) The title and introduction lead the reader to think there may be more comments on the broader area of MBRL. I understand that new experiments broadly are out of the scope of this paper with length considerations, but it would help the paper flow if there are intuitions for why this matters broadly. \n\n2) This paper heavily relies on previous knowledge of Pan et. Al 2018 and 2019. Most of the content seems to be reviewing these papers, and I do not think the introduction did enough on differentiating them. This paper is well constructed, but these unclear boundaries make it difficult to accept for publication. \n\n3) The section on PRIORITIZED SAMPLING AS A CUBIC OBJECTIVE does not seem particularly well motivated. Are there other types of prioritization than error-based prioritization. What of distribution location prioritization or reward-based prioritization as discussed in section 5 of this paper https://arxiv.org/pdf/2002.04523.pdf.\n3a) Such error-based prioritization weights the learning on low-accuracy training points, but model accuracy does not guarantee reward. \n3b) I do not find figure 1 insightful. This space could be better allocated to improve the flow, motivation, and conclusions of the paper. \n\n\n----- \nMinor Comments:\n1) There are only a few typos\n1a) first sentence of introduction \"environment model\" should either be hyphenated or environmental model\n1b) \"there is as yet\" is wordy and seemingly lacking punctuation. \n1c) \"while keep the sampling distribution similar\" at the end of section 4\n2) in the empirical demonstration, paragraph 4, the authors say the learning rate is from the range {0.01,  0.001, 0.0001}, is this from a set? Is there any further optimization?\n3) Figure 3c) is not mentioned in the caption.\n\n----\nPost discussion.\nAfter reading some of the author responses I have decided not to update my score. I think the paper needs a bigger revision and more results to be above the acceptance threshold.", "extra_scores": {}, "extra_text": {}}, {"review_id": "3sCiLaviXi", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Summary:\n\nThis paper investigates the search-control problem in Dyna-style reinforcement learning algorithms. They first provide a theoretical justification behind the error-based prioritization and propose a new sampling method based on gradient ascent of which optimization results are equivalent to samples drawn from the priority distribution. The suggested prioritization method is examined in various domains, namely, GridWorld, AcroBot, CartPole, MazeGridWorld, and roundabout-v0, and it shows a better sample efficiency in most domains.\n\nStrength:\n\n(+) The suggested method is based on the theoretical justification.\n\n(+) The analysis of the out-dated priority is interesting and provides a better understanding of priority-based RL algorithms.\n\n(+) The experimental results comparing the proposed Dyna-TD with other Dyna-variants corresponds to the theoretic justification they provided.\n\nConcerns:\n\n(-) While the authors provide a justification for the error-based prioritization in which the prioritization with l2-loss is equivalent to a cubic loss with uniform sampling, the motivation behind the error-based prioritization is rather weak. Specifically, in Theorem 2, it is stated that the cubic loss function provides fast early learning, but in Section 3.2, the opposite results are shown in which cubic or quadratic loss function is worse than Full-PrioritizedL2. What makes the specific form of error-based prioritization (absolute error normalized by the sum of the errors) best for learning?\n\n(-) Related to the concern above, it is unclear how well Theorem 2 holds with parametric function approximation. The gap between Full-PrioritizedL2 and Cubic, which is theoretically equivalent, represents this problem. Where does the gap come from and why does the large batch size partially address this? At a glance, assuming that SGD finds the global optimum, the error should be the same for l2, l3, l4 when the optimization converges.\n\n(-) It is a valid point that Dyna-TD addresses the insufficient sample space coverage problem of the ER methods and its variants via model M. However when the model has to be trained online, it is unclear whether the advantage still exists since the error of the model could hurt the hill-climbing process and the bootstrapped target value is more likely wrong. More thorough experiment results can alleviate this concern; how does the average return for the roundabout-v0 look like?; how well does other Dyna-variants algorithm work for the roundabout-v0 and MazeGW?; how about ER-based algorithms for MazeGW?; and most interestingly, how well does the algorithm work for environments having complex dynamics, such as atari-games? (less complex environments than the games would be also fine)\n\nTypo:\n\n(-) Missing parenthesis at the end of Theorem 3.\n\n----------------\nPost discussion comment:\n\nI have decided not to update my score. While the theoretical analysis is interesting, I am not fully convinced about the utility of the proposed algorithm. It would be useful to have more experiments in the widely used benchmark such as atari or have better motivation explaining why faster convergence would help in the RL context as it would in supervised learning.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: # Quality: 
While the paper presents an interesting approach, Reviewer 2 raised relevant questions about the assumption of the theoretical justification that needs to be thoroughly addressed.
Moreover, as noted by Reviewer4, the quality of the paper would also benefit from a more clear connection to existing model-based reinforcement learning literature, besides [Pan et al.]. For example, how much of the proposed approach and results can be applied in other algorithms?

# Clarity: 
While the paper is generally well written and only minor suggestions from the reviewers should be implemented.

# Originality:
The proposed approach is a small but novel improvement over existing algorithms (to the best of the reviewers and my knowledge).

# Significance of this work: 
The paper deal with a relevant and timely topic. However, it is currently very difficult to gauge the significance of this work, and it unclear if the results can be extended beyond toy benchmarks and to other RL algorithms. Several reviewers suggested additional experiments to strengthen the paper.

# Overall:
This paper deal with an interesting topic and presents new interesting results. However, the current manuscript is just below the acceptance threshold. Extending the experimental evaluation and improving the clarity of the paper would crucially increase the quality of the paper.

Decision: Reject