Beyond Prioritized Replay: Sampling States in Model-Based Reinforcement Learning via Simulated Priorities
Authors: Yangchen Pan
Jincheng Mei
Amir-massoud Farahmand
Martha White
Hengshuai Yao
Mohsen Rohani
Jun Luo
Venue: ICLR 2022 Submitted (2022)
Keywords: experience replay
model-based reinforcement learning
sampling distribution
search-control
Dyna
stochastic gradient Langevin dynamics

Abstract: Prioritized Experience Replay (ER) has been empirically shown to improve sample efficiency across many domains and attracted great attention; however, there is little theoretical understanding of why such prioritized sampling helps and its limitations. In this work, we take a deep look at the prioritized ER. In a supervised learning setting, we show the equivalence between the error-based prioritized sampling method for mean squared error and uniform sampling for cubic power loss. We then provide theoretical insight into why it improves convergence rate upon uniform sampling during early learning. Based on the insight, we further point out two limitations of the prioritized ER method: 1) outdated priorities and 2) insufficient coverage of the sample space. To mitigate the limitations, we propose our model-based stochastic gradient Langevin dynamics sampling method. We show that our method does provide states distributed close to an ideal prioritized sampling distribution estimated by the brute-force method, which does not suffer from the two limitations. We conduct experiments on both discrete and continuous control problems to show our approach's efficacy and examine the practical implication of our method in an autonomous driving application. 

Under review as a conference paper at ICLR 2022
BEYOND PRIORITIZED REPLAY: SAMPLING STATES IN MODEL-BASED REINFORCEMENT LEARNING VIA SIM- ULATED PRIORITIES
Anonymous authors Paper under double-blind review
ABSTRACT
Prioritized Experience Replay (ER) has been empirically shown to improve sample efficiency across many domains and attracted great attention; however, there is little theoretical understanding of why such prioritized sampling helps and its limitations. In this work, we take deep look at the prioritized ER. supervised learning setting, we show the equivalence between the brsor prioritized sampling method for mean squared error and uniform sampling for cubic power loss. We then provide theoretical insight into why it improves convergence rate upon uniform sampling during early learning. Based on the insight, we further point out two limitations of the prioritized ER method: I) outdated priorities and 2) insufficient coverage of the sample space. To mitigate the limitations, we propose our model- based stochastic gradient Langevin dynamics sampling method. We show that our method does provide states distributed close to an idcal prioritized sampling distribution estimated by the brute-force method, which does suffer from the two limitations. We conduct experiments on both discrete and continuous control problems to show our approach's efficacy and examine the practical implication of our method in autonomous driving application.
INTRODUCTION
Experience Replay (ER) (Lin, 1992) has been popular method for training large-scale modern Reinforcement Learning (RL) systems (Degris et al., 2012; Adam & Busoniu, 2012; Mnih al., 2015a; Hessel et al., 2018; François-Lavet et al., 2018). In ER, visited experiences are stored in buffer, and at each time step, mini-batch of experiences is uniformly sampled update the training parameters in the value policy function. Such method is empirically shown to effectively stabilize the training and improve the sample efficiency of deep RL algorithms. Several follow-up works propose different variants to improve upon it (Schaul et al., 2016; Andrychowicz et al., 2017: Oh et al., 2018; de Bruin et al., 2018; Horgan et al., 2018; Zha et al., 2019; Novati & Koumoutsakos, 2019; Sun et al., 2020). The most relevant which attempts to improve the vanilla ER method by sampling those visited experiences proportional their absolute Temporal Difference (TD) errors. Empirically, it can significantly improve sample efficiency upon vanilla ER on many tested domains.
work is prioritized ER (Schaul al., 2016),
To gain intuitive understanding of why the prioritized ER method works, one may recall Model- Based RL (MBRL) methods (Kaelbling et al., 1996; Bertsekas, 2009; Sutton & Barto, 2018). ER can be thought of an instance of a classical model-based RL architecture- a (limited) non-parn -arammrmet model given by the buffer (van Seijen & Sutton, 2015; van Hasselt et al., 2019). A Dyna agent uses real experience to update its policy as well as its reward and dynamics model. In-between taking actions, the agent can get hypothetical experiences from the model to further improve the policy. Existing works show that smart ways of sampling those experiences can further improve sample efficiency of a MBRL agent (Sutton et al., 2008; Gu et al., 2016; Goyal et al., 2019; Holland et al., 2018; Pan et al., 2018; Corneil et al., 2018; Janner et al., 2019; Chelu et al., 2020). Particularly, prioritized sweeping (Moore & Atkeson, 1993) improves upon vanilla Dyna. The idea behind prioritized sweeping is quite intuitive: we should give high priority to states whose absolute TD errors large because they likely cause the most change in value estimates.
(Sutton, 1991), using

---

Under review as a conference paper at ICLR 2022
Hence, applying TD error- grror-based prioritized sampling to ER is natural idea in model-free RL setting.
This work provides theoretical insight into the prioritized ER's advantage and points out its two drawbacks: outdated prioritics and insufficient sample space coverage, which may significantly weaken its efficacy. To mitigate the two issues, we propose to leverage the flexibility of using an environment model to acquire hypothetical experiences by simulating priorities. Specifically, we bring in the Stochastic Gradient Langevin Dynamics (SGLD) sampling method to acquire states. We demonstrate that the hypothetical experiences generated by our method are distributed closer to the desired TD error- based sampling distribution, which does not suffer from the two drawbacks. Finally, we demonstrate the utility of our method on various benchmark discrete and continuous control domains and an autonomous driving application.
BACKGROUND
In this section, we firstly review basic concepts in RL. Then we briefly introduce the prioritized ER method, which will be examined in-depth in the next section. We conclude this section by discussing a classic MBRL architecture called Dyna (Sutton, 1991) and its recent variants, which are most relevant to our work.
Basic notations. We consider a discounted Markov Decision Process (MDP) framework (Szepesvári, 2010). A MDP can be denoted as tuple (S, A. PP, R, 7) including state space S, action space A, probability transition kernel IP, reward function R, and discount rate y E [o, 1J. At each environment time step I, an RL agent observes state 8, S, takes an action a E AA and moves to the next state 81+1 ~ P(|ss;, as). and receives a scalar reward signal T = R(s, a,, $t+1). A policy is a mapping S x A + [0, 1] that determines the probability of choosing action at given state.
popular algorithm to find an optimal policy is Q-learning (Watkins & Dayan, 1992). With function approximation, parameterized action-values Q9 updated using @ = + ad, QoQo(si, at) for stepsize a > 0 with TD-error 8, Tr+1 + max Qe (s(+111, a') Qo(se, at). The policy is defined by acting greedily w.r.t. these action-values.
ER methods. ER is critical when using neural networks to estimate Qe. as used in DQN (Mnih al., 2015b), both to stabilize and speed up learning. ER method uniformly samples a mini-batee of experiences from those visited ones in the form of (st, 0t, 8t+1, 1(+ to update neural network parameters. Prioritized ER (Schaul al., 2016) improves upon by prioritized sampling experiences, where the probability of sampling a certain experience is proportional to its TD error magnitude, i.e., p(5t, ae, S1+1, T+41) x |ōr]. However, the underlying theoretical mechanism behind this method is still not well understood.
MBRL. With a model, an agent has more flexibility to sample hypothetical experiences. We consider one-step model which maps a state-action pair its possible next state and reward: R. We build on the Dyna formalism (Sutton, 1991) for MBRL, and more
P : S x A + specifically, the recently proposed HC-Dyna (Pan et al., 2019) shown in Algorithm 1. HC- Dyna provides a special approach to Search-Control (SC)-the mechanism of generating states or state-action pairs from which query the model to get the next states and rewards. HC-Dyna's search-control mechanism generates states by Hill Climbing (HC) on some criterion function A(-). The term HC used for generality as the vanilla gradient ascent is modified resolve certain challenges (Pan et al., 2019).
The algorithmic framework maintains two buffers: the conventional ER buffer storing experiences (i.c.. an experience/transitio has the form of (st, a, st+1, r++1)) and a search-control queue stor- ing the states acquired by search-control mechanisms. At each time step 1, a real experience (St, Gt, S1+1, (++1) is collected and stored into ER buffer. Then the HC search-control process starts to collect states and store them into the search-control queue. A hypothetical experience obtained by first selecting a state from the search-control queue, then selecting the current policy, and then querying the model to get the next state s' and reward r to form an experience (s, a, S sr) These hypothetical transitions are combined with real experiences into single mini-batch to update the training parameters. The n updates, performed before taking the next action, called planning updates (Sutton& & Barto, 2018), 8), they improve the value/policy by using
action a according to
2

---

Under review as a conference paper at ICLR 2022
Algorithm 1 HC-Dyna: Generic framework
Input: Hill Climbing (HC) criterion function h S R. batch-size b; Initialize empty search- control queue Bae; empty ER buffer Ber; initialize policy and model P; HC stepsize on; mini- batch size b; environment P; mixing rate p decides the proportion of hypothetical experiences in mini-batch.
for ( = 1, .. do Add (st, (ee 8 r to Ber while within some budget time steps do
+ an V.h(s) // HC for search-control Add 8 into Bsc
If planning updates/steps
for times do
+ // initialize an empty mini-batch B for bp times do
Sample Bsc. on-policy action a Sample s' ~~~ P(s,a)
B (s.0, &.r))
Sample b(1 p) experiences from Ber, add to B
Update policy/value on mixed mini-batch
a model. The choice pairing states with on on-policy actions to form hypothetical experiences has been reported to be beneficial (Gu et al., 2016; Pan et al., 2018; Janner et al., 2019).
Two instances have been proposed for fu-)): the value function v(s) (Pan et al., 2019) and the gradient magnitude |/V (s)(l)) (Pan et al., 2020). The former is used as measure of the utility of state: doing HC on the learned value function should find high-value states without being constrained by the physical environment dynamics. The latter is considered difficulty, then doing HC provides additional states whose values are difficult to learn. The two suffer from several issues method motivated by overcoming the limitations of the prioritized ER.
measure of the value approximation
discuss in the Appendix A. This paper will introduce HC search-control
A DEEPER LOOK AT ERROR-BASER PRIORITIZED SAMPLING
In this section, we provide theoretical motivation error-based prioritized sampling by showing its equivalence to optimizing cubic power objective with uniform sampling in supervised learning setting. We prove that optimizing the cubic objective provides a faster convergence rate during early learning. Based on the insight, discuss two limitations of the prioritized ER: 1) outdated priorities and 2) insufficient coverage of the sample space. We then empirically study the such limitations.
3.1 THEORETICAL INSIGHT INTO ERROR-BASED BASED PRIORITIZED SAMPLING
In the la regression, minimize the mean squared error ming 2n Di=((f(xz)) )² for training set T { y:) P and function approximator fe, such as a neural network. In error-based prioritized sampling, we define the priority of sample (x, y) E T (ff(()) - y/: the probability of drawing a sample (x, y) E T is typically q(x, y. 0) x (fa(z) - yl. We employ the following form to compute the probability of point (I, v) T:
(fo(z) vl Σ [f((x;) -
q 9:0) def
We can show an equivalence between the gradients of the squared objective with this prioritization and the cubic power objective 1 for the proof.
3n I (fo(x:) - yal in the Theorem below. See Appendix A.3
Theorem 1. For constant c determined by 0, T. huve
vl We empirically verify this equivalence in the Appendix A.7. This simple theorem provides an intuitive reason for why prioritized sampling help improve sample efficiency: the gradient direction of
cE ( - = = (V()))))
3

---

Under review as a conference paper at ICLR 2022
the cubic function is sharper than that of the square function when the enror is relatively large (Figure 8). We refer readers to the work by Fujimoto et al. (2020) regarding more discussions about the equivalence between prioritized sampling and of uniform sampling. Our Theorem 2 further proves that optimizing the cubic power objective by gradient descent has faster convergence rate than the squared objective, and this provides solid motivation for using error-based prioritized sampling. See Appendix A.4 for a more detailed version of the theorem (which includes an additional conclusion) and its proof and empirical simulations.
Theorem (Fast early learning, concise version). Let n. be positive integer (ie., the number of training samples). Let Te, ãt I2 be the target estimates of all samples at time t, 2 O. Let (i [m]. [n]
{1,2, ..., n)) denote the ith element in the vector. We define the objectives:
(2(2, y) def Σ (z(1) v(1)), Ez(2, del
[x(i) v(i))²
The total absolute prediction errors:
81
del
86(1)
Σ (x((i) v()),
8, def
8,(1) Σ [i(()) y(1)l,
where y(i) E R is the training target for the ith training sample. generated by using l2 lg objectives respectively. That is, Vi [n].
Ler tattroo and fāete20 be
(i)
dl2(xr. v) dr)(1)
dīa(i) -1- dlz(āz. v) dā.
dt
dt
Given any 0 < < 60 = n i=1 50( define the following hitting time,
del
min 2 0: & S sch,
min(! _in(t
i, dal -
00 c...
Assume the same initializatton Ty Zg. We have the following conclusion. If there exists 8n E R and 0 < c S 8y such that
1
log (ōo/c)
(2)
d0(1)
6a
then we have t, 2 f., which means gradient descent using the cubic loss function will achieve the total absolute error threshold e faster than using the squared objective function.
This theorem illustrates that when the total loss of all training examples is greater than some threshold,
cubic power learns faster. For example, let the number of samples n = 1000, and each sample has initial loss do (i) = 2. Then & 2000. Setting c 570(.e., c(t) 0.57) satisfies the inequality (2). This implies using the cubic objective faster when reducing the total loss from 2000 to 570. Though it is not our focus here investigate the practical utility of the high power objectives, we include some empirical results and discuss the practical utilities of such objectives in Appendix A.6.
3.2 LIMITATIONS OF THE PRIORITIZED ER
Inspired by the above theorems, we now discuss two drawbacks of prioritized sampling: outdated priorities and insufficient sample space coverage. Then we empirically examine their importance and effects the next section.
The above two theorems show that the advantage of prioritized sampling comes from the faster convergence rate of cubic power objective during early learning. By Theorem 1, such advantage requires to update the priorities of all training samples by using the updated training parameters 0 at each time step. In RL, however, at the each time step f, the original prioritized ER method only updates the priorities of those experiences from the sampled mini-batel leaving the priorities of the rest of experiences unchanged (Schaul et al., 2016). We call this limitation outdated priorities. is typically infeasible to update the priorities of all experiences each time step.
In fact, in RL, "all training samples" in RL are restricted to those visited experiences in the ER buffer, which may only contain small subset of the whole state space, making the estimate of the prioritized
4

---

Under review as a conference paper at ICLR 2022
0.50
6-
Reot mean squared
250
0.40
Avergg
-500
0.30
averaged
S0runs
over
PriortbzedL2
12
Bonuns)
0.20
Full-Priontized12
0.13,0
0.25
0.50
0.75
1.00
0.00
0.25 0.50
1.00
2000
le5
time steps
(a) [7] = 4000
(b) [7] = 400
(c) Mountain Car.
Figure 1: Comparing L2 (black). Prioritized12 (red), and full-Prioritized122 (blue) in terms of testing RMSE v.s. number of mini-batch updates. (a)(b) show the results trained on a large and small training set, respectively. (c) shows the result of corresponding RL experiment on mountain car domain. We compare episodic return v.s, environment time steps for ER (black), PrioritizedER (red), and Full-PrioritizedEA (bluc). Results are averaged over 50 random seeds on (a), (b) and 30 on (c). The shade indicates standard emror.
sampling distribution inaccurate. There can be many reasons for the small coverage: the exploration is difficult, the state space is huge, or the memory resource of the buffer is quite limited, etc. We call this issue insufficient sample space coverage, which is also noted by Fedus et al. (2020).
Note that insufficient sample space coverage should not be considered equivalent to off-policy distribution issue. The latter refers to some old experiences in the ER buffer may be unlikely to appear under the current policy (Novati & Koumoutsakos, 2019; Zha al., 2019; Sun al., 2020; Oh et al., 2021). In contrast, the issue of insufficient sample space coverage can raise naturally. For example, the state space is large and an agent is only able to visit small subset of the state space during early learning stage. We visualize the state space coverage issue on RI. domain in Section 4.
3.3 NEGATIVE EFFECTS OF THE LIMITATIONS
In this section, we empirically show that the outdated priorities and insufficient sample space coverage significantly blur the advantage of the prioritized sampling method.
Experiment setup. We conduct experiments on a supervised learning task. We generate a training set T by uniformly sampling
[-2, 2] and adding zero-mean Gaussian noise with standard
deviation 0.5 to the target fsin(x) values. Define fain(x) def sin(8Tx) if x E [-2, and (2) sin( if a E [0. The testing set contains 1k samples where the targets are not coise-contaminated Previous work (Pan et al., 2020) show that the high frequency region [-2, 0] usually takes long time learn. Hence we expect error-based prioritized sampling to make clear difference in terms of sample efficiency on this dataset. We use 32 x 32 tanh layers neural network for all algorithms. We refer to Appendix A.8 for missing details and A.7 for additional experiments.
Naming of algorithms. L.2 the 12 regression with uniformly sampling from T. Sull-Prioritized1.. .2: the la regression with prioritized sampling according to the distribution defined in (1), the priorities of all samples in the training set are updated after each mini-batch update. PrioritizedL2: the only difference with cull-Prioritized122 is that only the priorities of those training examples sampled in the
updated at each iteration, the rest of the training samples the original priorities. This resembles the approach taken by the prioritized ER in RL (Schaul et al., 2016). We show the learning curves in Figure 1.
Outdated priorities. significantly worse than Pr.li Correspondingly, we further verify this phenomenon on the classical Mountain Car domain (Brockman et al., 2016). Figure ((c) shows the evaluation learning curves of different DQN variants in an RL setting. We use small 16 x 16 ReLu NN as the Q-function, which should highlight the issue of priority updating: every mini-batch update potentially perturbs the values of many other states. Hence many experiences in the ER buffer have the wrong priorities. Pull-PrioritizedER does perform significantly better.
Figure (a) shows that PrioritizedI.2 .2 without updating all priorities can be
Sample space coverage. To check the effect of insufficient sample space coverage, we examine how the relative performances of 1.2 and Full- hull-Prioitizzel122 change when we train them on smaller training dataset with only 400 examples as shown in Figure 1(b). The small training set has a small coverage of the sample space. Unsurprisingly, using small training set makes all algorithms perform worse; however, it significantly narrows the gap between Full- hull-Proorttized12 and L2. This indicates that prioritized sampling needs sufficient samples across the sample space to estimate the prioritized sampling distribution reasonably accurate We further verify the sample space coverage issue in prioritized ER on RL problem in the next section.
5

---

Under review as a conference paper at ICLR 2022
4 ADDRESSING THE LIMITATIONS
In this section, we propose a Stochastic Gradient Langevin Dynamics (SGLD) sampling method to mitigate the limitations of the prioritized ER method mentioned in the above section. Then empirically examine our sampling distribution. We also describe how our sampling method used for the search-control component in Dyna.
4.1 SAMPLING METHOD
SGLD sampling method. Let 0r (::0) : S r R be a differentiable value function under policy и parameterized by 0. For s E S, define yss) del ( + (s'; 0)]. and denote the TD
error as 8s, y; 9() del y(s) - v(s; 8.). Given some initial state 8o E S, let the state sequence {st} be the generated by updating rule 81+1 + 8; + a V.log (ō(s, ((s;);; 0e]] + X,, where as is stepsize and X; is a Gaussian random variable with some constant variance." Then {8;} converges to the distribution p(s) x [())] as 00. The proof is direct consequence of the convergent behavior of Langevin dynamics stochastic differential equation (SDE) (Roberts, 1996; Welling & Teh, 2011; : Zhang et al., 2017). We include a brief background knowledge in Appendix A.2.
should be noted that, this sampling method enables us to acquire states 1) whose absolute TD errors are estimated by using current parameter 0, and 2) that are not restricted those visited ones. We empirically verify the two points in Section 4.2.
Implementation. In practice, we can compute the state value estimate by v(s) max, Q(s,, a; 0.) as suggested by Pan et al. (2019). In the case that true environment model is not available, we compute an estimate (s)) of y(s) by a learned model. Then each time step t, states approximately following the distribution p () x (6(s, v(s)) can be generated by
Ob V log ((s) max ( az 0,)1 + X,
where X is a Gaussian random variable with zero-mean and some small variance. Observing that small, we consider (s) as a constant given state without backpropagating through it. Though this updating rule introduces bias due to the usage of a learned model, fortunately, the difference between the sampling distribution acquired by the true model and the learned model can be upper bounded as we show in Theorem 3 in Appendix A.5.
Algorithmic details. We present our algorithm called Dyna-TD in the Algorithm in Appendix A.8. Our algorithm follows Algorithm/ 1. Particularly, we choose the function h(s)) log [}(s) max, (8, a; 0.)l for HC search-control process, i.c., run the updating rule to generate states.
4.2 EMPIRICAL VERIFICATION OF TD ERROR-BASED SAMPLING METHOD
We visualize the distribution of the sampled states by our method and those from the buffer of the prioritized ER, verifying that our sampled states have an obviously larger coverage of the state space. We then empirically verify that our sampling distribution closer to a brute-force calculated prioritized sampling distribution-whise does not suffer from the two limitations- the prioritized ER method. Finally, we discuss concerns regarding computational cost. Please see Appendix A.8 for any missing details.
Large sample space coverage. During carly learning, we visualize 2k states sampled from 1) DQN's buffer trained by prioritized ER and 2) our algorithm Dyna-TD's Search-Contre (SC) queue on the continuous state GridWorld (Figure 2(a)). Figure 2 (b-c) visualize state distributions with different sampling methods via heatmap. Darker color indicates higher density. (b)(c) show that DQN's s ER buffer, no matter with or without prioritized sampling, does not cover well the top-left part and the right half part on the Gordd In contrast, Figure 2 (d) shows that states from our SC queue more diversely distributed on the square. These visualizations verify that our sampled states cover better the sample space than the prioritized ER does.
Sampling distribution is close to the ideal one. We denote our sampling distribution as p1 (-), the one acquired by conventional prioritized ER as pz(+), and the one computed by thorough priority
'The stepsize and variance affect the temperature parameter. We the two as hyper-parameters.

---

Under review as a conference paper at ICLR 2022
1/4
14
3.0
0,8
04
0.7
02
S
0.2
100
6.0
0.2
(a) GridWorld
(b) PER (uniform)
(c) PER (prioritized)
(d) Dyna- TD SC queue
Figure 2: (a) shows the WridWorld (Pan al., 2019). It has S [0, 1J AA {up, down, right, left). The agent starts from the left bottom and learn to reach the right top within as few steps as possible. (b) and (c) respectively show the state distributions with uniform and prioritized sampling methods from the ER buffer of prioritized ER. (d) shows the SC queue state distribution of our Dyna-TD.
0.823
0.0010
Dyna TD
betwoon
stlanc actua dxsnsusin
PrioriBsedER Dyna Long
actual
Dyna-TD
date buttinn
Prior izedtik
dst bution
Byna-TD-long
disrbbution (2mmm))
-1500
mier tieetttt
Dyne-TD
0.000
0.0004
-2000
3
time
1ol
(a) on-policy weighting
(b) uniform weighting
(c) time cost v.s. performance
Figure 3: (a)(b) show the distance change as a function of environment time steps for Dyna-TD (black). PrioritizedER (forest green), and Dyna-TD-Lon TD-Long (orange), with different weighting schemes. The dashed line corresponds to our algorithm with online learned model. The corresponding evaluation learning curve is the Figure 4(c). (d) shows the policy evaluation performance function of rumning time (in seconds) with ER(mageeta). results are averaged over 20 random seeds. The shade indicates standard error.
updating of enumerating all states in the state space as p-(-) (this one should be unrealistic in practice does not suffer from the two limitations we discussed). We
and we call it the ideal distribution approximate p" on the GridWorld domain, where the state visualize how well (-) and (-) can distributions can be conveniently estimated by discretizing the continuous state GridWorld to 50 50 one. We compute the distances of pl. P2 to p² by two sensible weighting schemes: 1) on-policy 2500 d (s))))) (s,)), {1,2], where d! is approximated by uniformly sample weighting: Σ y=
3k states from a recency buffer; 2) uniform weighting: 2500
2500 (p,(s)) - p" (sy)), e {1,2).
We plot the distances change when we train our Algorithm and the prioritized ER in Figure 3(a)(b). They show that the HC procedure in our algorithm Dyna-TD, either with model, produces a state distribution with significantly closer distance to the desired sampling dis- tribution p" than PrioritizedER under both weighting schemes. In contrast, the state distribution acquired from PrioritizedER, which suffers from the two limitations, is far away from p". It should also be noted that we include Dyna-TD-Longg, which runs a large number of HC steps so that its corresponding sampling distribution should be closer to stationary distribution. However, there is only tiny difference between the regular Dyna-TI and Dyna-TD-Long, implying that one can save computational cost by running fewer HC steps.
or an online learned
Computational cost. Let the mini-batch size be b, and the number of HC steps be knc. we assume one mini-batch update takes Oc)), then the time cost of our sampling is Olckre/be which reasonable. On the GridWorld, Figure 3(c) shows that given the same time budget, our algorithm achieves better performance. This makes the additional time spent on scarch-control worth it.
EXPERIMENTS
In this section, we design experiments to answer the following questions. (1) By mitigating the limitations of conventional prioritized ER method, can Dyna-TD outperform the prioritized ER under various planning budgets in different environments? (2) Can Dyna-TD TD outperforms the existing Dyna variants? (3) How effective is Dyna-TD TD under an online learned model, particularly for more realistic applications where actions are continuous, input dimensionality is higher?
Baselines. ER is DQN with a regular ER buffer without prioritized sampling. PrioritizedER the one by Schaul et al. (2016), which has the drawbacks discussed in paper. Dyna-Value (Pan
7

---

Under review as a conference paper at ICLR 2022
-50
-300
Averge
-198
-1ore
-1500
-200
Eyna
Dyna to
-2000
-2000
-00
stopo
Lame
204
Uma
304
Umm
144
(a) MountainCar, n 10 (b) MountainCar, n 30
(c) Acrobot, n 10
(d) Acrobot, 71 30
-200
-2000
3nd
(c) GridWorld, n = 10 (f) GridWorld, n = 30 gg) CartPolc, n 10
(h) CartPole, n 30
Figure 4: Episodic return environment time steps. We show evaluation learning curves of Dyna-TD (black), Dyna-Frequency (red), Dyna- (blue), PrioritizedER (forest green), and (maggett with planning updates n 10,30, 30. The dashed line denotes Dyna-TD with an online learned model. All results are averaged over 20 random seeds after smoothing over a window of size 30. The shade indicates standard error.
et al., 2019) is the Dyna variant which performs HC on the learned value function to acquire states to populate the SC queue. Dyna-Frequency (Pan et al., 2020) is the Dyna variant which performs HC on the norm of the gradient of the value function to acquire states to populate the SC queue. For fair comparison, at each environment time step, we stochastically sample the same number of mini-batches to train those model-free baselines as the number of planning updates in Dyna variants. We are able to fix the same HC hyper-parameter setting across all environments. Please see Appendix A.8 for any missing details.
Performances on benchmarks. Figure 4 shows the performances of different algorithms on Moun- tainCar, Acrobot, GridWorld (Figure 2(a)), and CartPole. On these small domains, we focus on studying our sampling distribution and hence we need to isolate the effect model errors (by using a true environment model). though include algorithm Dyna- TD with online learned model for curiosity. We have the following observations. First, our algorithm Dyna-TD consistently outperforms PrioritizedER across domains and planning updates. In contrast, the PrioritizedEER may not even outperform regular ER, as occurred in the previous supervised learning experiment. Second, Dyna-TD* -ynas performance significantly improves and even outperforms other Dyna variants when increasing the planning budget (i.e., planning updates n)) from 10 to 30. This validates the utility of those additional hypothetical experiences acquired by our sampling method. In contrast, both ER and PrioritizedER show limited gain when increasing the planning budget (i.e., number of mini-bated updates), which implies the limited utility those visited experiences. Third, Vyma-Value/Frequeng frequently converge to sub-optimal policy when using large number of planning updates, while Dyna-TD always finds a better one. It may be that the two Dyna variants frequently generate highh-value/frqquencyy states whose TD errors are low, which wastes samples and leads to serious distribution bias. Dyna-Frequency additionally suffers from explosive or zero gradients, and hence is sensitive hyper-parameters (Pan et al., 2020), which may explain its inconsistent performances.
demo for continuous control. We demonstrate that our approach can be applied for Mu- joco (Todorov al., 2012) continuous control problems with online learned model and still achieve superior performance. We use DDPG (Deep Deterministic Policy Gradient) (Lillicrap et al., 2016; Silver al., 2014) as example for inside our Dyna-TD, Let πं S + A be the actor,
then we set the HC function as h(s)) del log j Qo Tar (s)) where ğ is the TD target. Figure 5 (a)(b) shows the learning curves of DDPG trained with ER, PrioritizedER, and our Dyna-TD on Hopper and Walker2d respectively. Since other Dyna variants never show an advantage and are not relevant to the purpose of this experiment, we no longer include them. Dyna-TT shows quick iiiioooooeeee improvement as before. This indicates our sampled hypothetical experiences could be helpful for actor-critic algorithms that are known to be prone to local optimums. Additionally, we note again that ER outperforms PrioritizedER, occurred in the discrete control and supervised learning (PrioritizedL.2 is worse than L2) experiments.
Autonomous driving application. We study the practical utility of our method in relatively large autonomous driving application (Leurent, 2018 8) with an online learned model. We use the roundabout- vO domain (Figure 6 (a)). The agent learns to go through roundabout by lane change and longitude
8

---

Under review as a conference paper at ICLR 2022
2500
Dyna
2500
Bynw-
Figure 5: (a) (b) show episodic returns v.s. enviromment time steps of Dyna-TD (black) with on- line learned model, and other com- petitors on Hopper and Walker2d respectively. Results are averaged over 5 random seeds after smooth- ing over window of size 30. The shade indicates standard error.
2000
R
2000
1500
Dyna Frezusncy
1500
Frequency
Dyre-Vei
1000
1000
500
500
time steps
time steps
(a) Hopper-v2
(b) Walker2d-v2
12.
10
Pronttoadt
TD
humter
Aecropon
speed
022ura
PrieritizeERR
Dyna-
02
20 DrVing timte steps
60
0.4
08
241
Cime step4
dma stope
(a) roundabout
(b) Num of car crashes
(c) Avg. speed
(d) Episodic return
Figure 6: (a) shows the roundabout domain with S C R (b) shows crashes v.s. total driving time steps during policy evaluation. (c) shows the average speed per evaluation episode v.s. environment time steps. (d) shows the episodic return v.s. trained environment time steps. We show Dyna-TD (black) with online learned model, PrioritizedER (forest green), and ER (magenta). Results are averaged over 50 random seeds after smoothing over a window size 30. The shade indicates standard error.
control. The reward designed such that the car should go through the roundabout as fast as possible without collision. We observe that all algorithms perform similarly when evaluating algorithms by episodic return (Figure 6 (d)). In contrast, there is a significantly lower number of car crashes with the policy learned by our algorithm, as shown in Figure 6(b). Figure 6 (c) suggests that ER and PrioritizedER gain reward mainly due to fast speed which potentially incur more car crashes. The conventional prioritized ER method still incurs many crashes, which may indicate its prioritized sampling distribution does not provide enough crash experiences to learn.
6 DISCUSSION
We provide theoretical insight into the error-based prioritized sampling by establishing its equivalence to the uniform sampling for cubic power objective in supervised learning setting. Then we identify two drawbacks of prioritized ER: outdated priorities and insufficient sample space coverage. We mitigate the two limitations by SGLD sampling method with empirical verification. Our empirical results on both discrete and continuous control domains show the efficacy of our method.
There are several promising future directions. First, a natural follow-up question is how model should be learned to benefit our sampling method. Existing results show that learning a model while considering how to use it should make the policy robust model errors (Farahmand et al., 2017; Farahmand, 2018). Second, one may apply our approach with model in some latent space (Hamilton et al., 2014; Wahlström al., 2015; Ha Schmidhuber, 2018; Hafner al., 2019; Schrittwieser et al., 2020), which enables examining how ER is affected by boostrap return (Dalcy Amato, 2019), by buffer or mini-batch size (Zhang & Sutton, 2017; Liu & Zou, 2017). and by number of environment steps taken per gradient step (Fu et al., 2019; van Hasselt et al., 2018; Fedus et al., 2020). It is worth studying the theoretical implications of those design choices and their effects on prioritized ER's efficacy.
method to scale large domains. Third, since there existing works
Last, as our cubic objective explains only one version of the error-based prioritization, efforts should also be made theoretically interpret other prioritized sampling distributions, such distribution location or reward-based prioritization (Lambert et al., 2020). is interesting to explore whether these alternatives can also be formulated as surrogate objectives. Furthermore, a recent work by Fujimoto et al. (2020) establishes an equivalence between various prioritized sampling distributions and uniform sampling for different loss functions, which bears similarities to our Theorem study if those general loss functions have faster convergence rate as shown in our Theorem 2.
interesting to

---

Under review as a conference paper at ICLR 2022
7 ETHIC STATEMENT
This work is about the methodology of how to sample hypothetical experiences in model-based rein- forcement learning efficiently. The potential impact of this work is likely to be further improvement of sample efficiency of reinforcement learning methods, which should be generally beneficial to the reinforcement learning research community. We have considered specific applications practical scenarios as the goal of this work. Hence, it does not have any direct ethical consequences.
8 REPRODUCIBLE STATEMENT
We commit to ensuring that other researchers with reasonable background knowledge in our area reproduce theoretical and empirical results. We provide detailed theoretical derivation for our theorems and 2 in the Appendix, where there is a clear table of contents pointing to different concrete mathematical derivations for these theorems. We also provide sufficient experimental details to reproduce our empirical results in Appendix A.8. We will provide our repository upon acceptance or reviewer's request.
REFERENCES
Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., and et TensorFlow: Large-scale machine learning on heterogeneous systems. Software available from tensorflow.org, 2015.
Adam, S. and Busoniu, I.. Experience Replay for Real-Time Reinforcement Learning Control. Systems, 2012.
Andrychowicz, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Pieter Abbeel, O., and Zaremba, W. Hindsight experience replay. Advances in Neural Information Processing Systems, pp. 5048-504 5058, 2017.
Bertsekas, D. Neuro- Cauro-Dynamic Programming. Springer 2009.
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W.
OpenAl Gym. arXiv:1606.015.4 2016.
Chelu, V., Precup, D., and van Hasselt, H. Forethought and hindsight in credit assignment. Advances in Neural Information Processing Systems, 2020.
Chiang, T.-S., Hwang, C.-R., and Sheu, S. Diffusion for global optimization in R". SIAM Journal on Control and Optimization, pp. 737-753, 1987.
Corneil, D. S., Gerstner, W., and Brea, J. Efficient model-based deep reinforcement learning with variational state tabulation. In International Conference on Machine Learning, pp. 1049-1058, 2018.
Daley, B. and Amato, C. Reconciling lambda-returns with experience replay. Advances in Neural Information Processing Systems, pp. 1133-1142 2019.
de Bruin, T., Kober, J.. Tuyls, K., and Babuska, R. Experience selection in deep reinforcement learning for control. Journal of Machine Learning Research, 2018.
Degris, T., Pilarski, M., and Sutton, R. Model-free reinforcement learning with continuous action in practice. In Americun Control Conference (ACC), 2012.
Durmus, A. and Moulines, E. Nonasymptotic convergence analysis for the unadjusted Langevin algorithm. The Annals of Applied Probability, pp. 1551-1587, 2017.
Farahmand, A.mm. Iterative value-aware model learning. Advances in Neural Information Processing Systems, pp. 9072-9083 2018.
Farahmand, A.-M., Barreto, A., and Nikovski, D. Value-Aware Loss Function for Model-based Reinforcement Learning. International Conference on Artificial Intelligence and Statistics, pp. 1494, 2017.
10

---

Under review as a conference paper at ICLR 2022
Fedus, W., Ramachandran, P., Agarwal, R.,, Bengio, Y., Larochelle, H.,, Rowland, M., and Dabney, W. Revisiting fundamentals of experience replay. Interaational Conference on Machine Learning, pp- 3061-3071, 2020.
Frangois-Lavet, V., Henderson, P., Islam, R., Bellemare, M. G., and Pineau, An introduction to deep reinforcement learning. Foundations and Trends in Machine Learning, pp. 219-354, 2018.
Fu, J., Kumar, A., Soh, M., and Levine, S. Diagnosing bottlenecks in deep q-learning algorithms. International Conference on Machine Learning, pp. 2021-20300 2030, 2019.
Fujimoto, S., Meger, D., and Precup, D. An equivalence between loss functions and non-uniform sampling experience replay. Advances Neural Information Processing Systems, 2020.
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, 2010.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. International Conference on Learning Representations, 2015.
Goyal, A., Brakel, P., Fedus, W., Singhal, S., Lillicrap, T., Levine, S., Larochelle, H., and Bengio, Y. Recall traces: Backtracking models for efficient reinforcement learning. International Conference on Learning Representations, 2019.
Gu, S., Lillicrap, T. P., Sutskever. I., and Levine, S. Continuous Deep Q-Learning 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-2462, 2018.
Hafner, D., Lillicrap, T., Fischer, I,, Villegas, R., Ha, D., Lee, H., and Davidson, J. Learning latent dynamics for planning from pixels. International Conference on Machine Learning, pp. 2555-2565, 2019.
Hamilton, W. L., Fard, M. M., and Pineau, J. Efficient learning and planning with compressed predictive states. Journal of Machine Learning Research, 2014.
Hessel, M., Modayil, J., van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot,
B., Azar, M., and Silver, D. Rainbow: Combining improvements deep reinforcement learning. AAAI Conference on Artificial Intelligence, 2018.
Holland, G. 7., Talvitie, E., and Bowling, M. The effect of planning shape dyna-style planning in high-dimensional state spaces. CoRR, abs/ 00//1006..122,. 2018
Horgan, D., Quan, J., Budden, D., Barth-Maron, G., Hessel, M., van Hasselt, H., and Silver, D. Distributed prioritized experience replay. International Conference Learning Representations, 2018.
Huber, J. Robust estimation of a location parameter. Annals of Mathematical Statistics, pp. 73-101, 1964.
Janner, M., Fu, J., Zhang, M., and Levine, S. When to trust your model: Model-based policy optimization. Advances in Neural Information Processing Systems, pp. 12519-12530, 2019.
Kaelbling, L. P., Littman, M. L., and Moore, A. W. Reinforcement learning: survey. Journal of Artificial Intelligence Research, pp. 237-285, 1996.
Kingma, D. and Ba, Adam: A method for stochastic optimization. International Conference Learning Representations, 2014.
Lambert, N., Amos, B., Yadan, O., and Calandra, R. Objective mismatch in model-based reinforce- ment learning. arXiv preprint arXiv:2002.0452. 2020.
Leurent, An environment for autonomous driving decision maaiiiinnmmaing.... GitHub repository https: //gi thub. com/ htte://eeeeeeeeeeeee http:///llleeeeeteggaaaaaeeeeeee ghway-env, 2018.
11

---

Under review as a conference paper at ICLR 2022
Leurent, E., Blanco, Y., Efimov, D., and Maillard, O. Approximate robust control of uncertain dynamical systems. CoRR, 000/100000022, 2019.
Lillicrap, T. P., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. International Conference on Learning Representations, 2016.
Lin, L.-J. Self-Improving Reactive Agents Based On Reinforcement Learning, Planning and Teaching. Machine Learning, 1992.
Liu, R. and Zou, J. The effects of memory replay in reinforcement learning. Communication, Control, and Computing, 2017.
Conference on
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., and et al. Human-level control through deep reinforcement learning. Nature, 2015a.
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., Beattic, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg. S., and Hassabis, D. Human-leves control through deep reinforcement learning. Nature, 2015b.
Moore, A. W. and Atkeson, C. G. Prioritized sweeping: Reinforcement learning with less data and less time. Machine learning, pp. 103-130, 1993.
Novati, G. and Koumoutsakos, P. Remember and forget for experience replay. International Conference on Machine Learning, pp. 4851-4860, 2019.
Oh, J., Guo, Y., Singh, S., and Lee, H. Self-imitation learning. International Conference on Machine Learning, pp. 3878-38877 3887, 2018.
Oh, Y., Lee, K., Shin, J., Yang, E., and Hwang, S. J. Learning sample with local and global contexts in experience replay buffer. International Conference on Learning Representations, 2021.
Pan, Y., Zaheer, M., White, A., Patterson, A., and White, M. Organizing experience: a deeper look at replay mechanisms for sample-based planning in continuous state domains. In International Joint Conference Artificial Intelligence, pp. 4794-4800, 2018.
Pan, Y., Yao, H., Farahmand, A.mm., and White, M. Hill climbing on value estimates for search-control in dyna. International Joint Conference on Artificial Intelligence, 2019.
Pan, Y., J., and massoud Farahmand, A. Frequency-based search-control in dyna. In International Conference on Learning Representations, 2020.
Roberts, Gareth O.and Tweedie, R. L. 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. In International Conference Leurning Representations, 2016.
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D.,, Graepel, T., Lillicrap, T., and Silver, D. Mastering atari, go, chess and shogi by planning with a learned model. Nature, pp. 604-609, 2020.
Silver, D., Lever, G., Heess, N., Degris, T., Wierstra, D., and Riedmiller, M. Deterministic policy gradient algorithms, In International Conference on Machine Learning, pp. 1-387-1-395, 2014.
Sun, P., Zhou, W., and Li, H. Attentive experience replay. AAAI Conference Artificial Intelligence, pp. 5900-5907, 2020.
Sutton, R. S. Integrated architectures for learning, planning, and reacting based on approximating dynamic programming. Machine Learning, 1990.
Sutton, R. S. Integrated modeling and control based on reinforcement learning and dynamic program- ming. In Advances in Neural Information Processing Systems, 1991.
12

---

Under review as a conference paper at ICLR 2022
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
Sutton, R. S., Szepesvári, C., Geramifard, A., and Bowling, M. Dyna-style planning with linear func- tion approximation and prioritized sweeping. Conference on Uncertainty in Artificial Intelligence, pp. 528-536, 2008.
Szepesvári, Cs. Algorithms for Reinforcement Learning. Morgan Claypool Publishers, 2010.
Todorov, E.,, Erez. T., and Tassa, Y. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
van Hasselt, H., Doron, Y., Strub, F., Hessel, M., Sonnerat, N., and Modayil, J. Deep reinforcement learning and the deadly triad. Deep Reinforcement Learning Workshop at Advances in Neural Information Processing Systems, 2018.
van Hasselt, H. P.. Hessel, M., and Aslanides, J. When to use parametric models in reinforcement learning? Advances Neural Information Processing Systems, pp. 14322-14333, 2019.
van Seijen, H. and Sutton, R. deeper look at planning as learning from replay. In International Conference Machine Learning, pp. 2314 2314-2322, 2015.
Wahlström, N., Schön, T. B., and Deisenroth, M. P. From pixels to torques: Policy learning with deep dynamical models. Deep Learning Workshop at International Conference on Machine Learning, 2015.
Watkins, C. and Dayan, Q-learning. Machine Learning, pp. 279-292, 1992.
Welling, M. and Teh, Y. W. Bayesian learning stochastic gradient Langevin dynamics. In International Conference Machine Learning, pp. 681-688, 2011.
Zha, D., Lai, K.-H., Zhou, K., and Hu, X. Experience replay optimization. International Joint Conference on Artificial Intelligence, pp. 4243-4249, 2019.
Zhang, S. and Sutton, R. S. A Deeper Look at Experience Replay. Deep Reinforcement Learning Symposium Advances in Neural Information Processing Systems, 2017.
Zhang, Y., Liang, P., and Charikar, M. hitting time analysis of stochastic gradient langevin dynamics. Conference on Learning Theory, pp. 1980-2022, 2017.
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
The appendix includes the following contents:
1. Section A.1: background in Dyna architecture and two Dyna variants.
2. Section A.2: background of Langevin dynamics.
3. Section A.3; the full proof of Theorem 1.
4. Section A.4: the full proof of Theorem and its simulations.
5. Section A.5: the theorem characterizing the error bound between the sampling distribution estimated by using a true model and a learned model. It includes the the full proof.
6. Section A.6: a discussion and some empirical study of using high power objectives.
7. Section A.7: supplementary experimental results: training error results to check the negative effects of the limitations of prioritized sampling; results to verify the equivalence between prioritized sampling and cubic power; results/evaluation learning curve to supplement the autonomous driving application; results on MazeGridWorld from (Pan al., 2020).
8. Section A.8: details for reproducible research.
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 model and performs a 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, in Dyna, the concept of planning refers to any computational process which leverages a model to improve policy, according to Sutton & Barto (2018), Chapter 8. The mechanism of generating states or state-action pairs from which to query the model is called search-control which is of critical importance to improving sample efficiency. The below algorithm shows naive search-control strategy: simply use visited aatton pairs and store them into the search-control queue. During the planning stage, these pairs are uniformly sampled according to the original paper.
The recent works by Pan et al. (2019, 2020) propose two search-control strategies to generate states. The first one is to search high-value states actively, and the second one is to search states whose values are difficult to learn.
However, there are several limitations of the two previous works. First, they do not provide any theoretical justification to use the stochastic gradient ascent trajectories for search-control. Second, HC on gradient norm and Hessian norm of the learned value function (Pan et al., 2020) suffers from great computation cost and zero or explosive gradient due to the high order differentiation (i.e., V. V.Il (x)(s))) as suggested by the authors. When using ReLu as activation functions, such high order differentiation almost results in zero gradients. We empirically verified this phenomenon. And this phenomenon can also be verified by intuition from the work by Goodfellow et al. (2015), which suggests that ReLU neural networks are locally almost linear. Then it is not surprising have zero higher order derivatives. Third, the two methods are prone to result in sub-optimal policies: consider that the values of states are relatively well-learned and fixed, then value-based search-control (Dyna-Valae would still find those high-value states even though they might already have low TD error.
A.2 DISCUSSION ON THE LANGEVIN DYNAMICS MONTE CARLO METHOD
Theoretical mechanism. Define a SDE: dt (U(W))dt + V2dB,, where B, E Id is d-dimensional Brownian motion and U is a continuous differentiable function. turns out that the Langevin diffusion (Wt)220 converges to unique invariant distribution p(z) x exp (U())) (Chiang et al., 1987). By applying the Marcraaa discretization scheme to the SDE, we acquire the discretized version YR+1 Yx + 06++1 (U(Y)) + 220++ 12 where (Z+)az1 is an i..d. sequence of standard d-dimensional Gaussian random vectors and (ax) (2x))21 is a sequence of step sizes. It has been proved that the limiting distribution of the sequence (Yes )221 converges to the invariant distribution of the underlying SDE (Roberts, 1996; Durmus & Moulines, 2017). As result, considering U-) log (, Y as 8 justifies our SGLD sampling method..
14

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Tabular Dyna
Initialize Q(s, a); initialize model M(s, a), V(s,a) while true do
observe s, take action by e-greedy w.r. Q(s,)) execute a, observe reward R and next State s'
Q-learning update for Q(s, a)
update model MMs, a) (i.e. by counting) store (8.a) a.) into search-control queue // this a naive search-control strategy
for i=1:d do
sample (3, ā) from search-control queue
(3', + M(š, â) // simulated transition
Q-learning update for Q(5, ā) // planning updates/steps
A.3 PROOF FOR THEOREM 1
Theorem 1. For a constant e determined by 0, T, we have
1
0 Olf((x) -y
1
( - y)²
E
E
3
00
(2.))~g(a.x;9))
2
00
Proof. For the l.h.s,, we have,
0 (l)((a)) yl
E (un (T)
(4)
3
00
[lfo(x(i)) v(1)
(5)
3 n
00
1=1
(fo(z(0)) v(i)) v(i))2)
(6)
3 3.n
00
(Ua(((()) ( v(1))²)
1
(ff(x(()) - v()))
(7)
3
(ff((z) - y)²
00
lff(((()) - s(i) a (fo(z(()) 2
(8)
2.
00
On the other hand, for the r.h.s., we have,
0 (fo(z) -))
(9)
((.))))(().)0)))
00
i (fo(2()) 2())) v(0))
( v4:0)
(10)
00
fo(((1)) v(i) (fo(z(1)) 2()))
(11)
Σn ( 4/
2-
00
0lfo(a) y/
E (x:g))mnttfrmm()
(12)
ΣØ= (x,) Fز
3
09
Setting c >nn (or, val completes the proof.
15

---

Under review as a conference paper at ICLR 2022
A.4 PROOF FOR THEOREM 2
Theorem 2. Let n be a positive integer (i.e., the number of training samples). Let It, Tt. E R" be the (1, n.) denote the ith element
target estimates of all samples time Let (i) [m],[n] def
in the vector. We define the following notations.
1
(2(
Σ
(x(1)
(z(2, -(i))
Σ 2=1
[x( - v(t)
2
3
1=1
6, def Σ 61(1) Σ 20 (1) v(i)l.
8, def
81(1) Σ
(1)(1) y(o)l, 0, 2
where v(i) IR is the training target for the ith training sample. Let (#e)22 and fāit120 be generated by using l,, E3 objectives respectively. That is, Vi E [n],
dl2 v) (1) "I dre(1)
(i) dl
dlg(ā,. v)
1
(i)
Assume the same initialization which is the minimum time that the absolute error takes to be E(i).
.g. Then: (i) For all i = [n]. define the following hitting time,
(i) minft 2 0 (t) S <())),
E.(i) = min t 2 0 8,(1) S c(i))
min
Then, Vi [n] s.t. (1) 1. given an absolute error threshold e(i) 2 0, there exists co(i) E (0, 1), such that for all ((t) > (i), (i) (i).
(ii) Define the following quantity, for all 2 0.
def 1
1
H
(13)
(i( v()
Given any 0 < <
60 = Σi= (1). define the following hitting time, which is the minimum time that the total absolute error takes be S e,
del
min 2 & S c), i = 2 0: 82 c).
(14)
If there exists dg E IR and 0 < 80 such that the following holds,
log (5p/c)
Ho
(15)
80
then we have, f, 2 fz. which means gradient descent using the cubic loss function will achieve the total absolute error threshold e faster than using the square loss function.
Proof. First part. (i). For the &g loss function, for all i E [n] and t 2 O, we have,
ddc(i) dl
dd.(1)
dre(i)
(16)
do)(j) dt
di)
dx((i)
(1,
= 0 for all i i +j
(17)
(r,(1) dt
dr,(j)
(gn(xx(1) -v()) (-n) dlz(xe.))
(18)
(1)( v(1) dz,
- yy(1)
(19)
-n/2x()) v(i)l
(20)
11 (1)),
(21)
which implies that,
d(log 5,()
d5,
17-
(22)
dt
(i)
dt
16

---

Under review as a conference paper at ICLR 2022
Taking integral, we have,
log (1) - llg (8) -1
(23)
Let (e( = ( We have,
(n(()
(66 (o)
(e det log
8,(1)
=
log
E(i)
(24)
On the other hand, for the fa loss function, we have,
d(ox(1)=+)
n Σ dār(1) dt
dd-(1)-1 dār(()
(25)
dt
dd) dī,(1)
(26)
di)(i) dt
1 (i) dia(1) (1)z (i) dt
(27)
sgn (g - y(1) (-n) dls(ār. v)
(28)
(i)(1) - y(1))
dī,(1)
(1) - v(1)
((n) (E)(()) v(1))² sg)(( y((i}
(29)
(1) - (z)))
(30)
Taking integral, we have,
n t.
(31)
(i) (0(1)
Let (i) = e(i). We have,
def 1
1
1
(e(1)
(32)
7
(1) 81)
77
(1))
Then we have,
1
5u(i)
1
1
(1) - (.(1)
log
(33)
"
<(i)
7)
((i)
o0())
[ log
log (1) (o() )
1
(34)
e(i)
e(i)
According to mi) = (1), we have
6i(
x (1) v(0l
(35)
= (1) 5(0
(36)
(1).
(37)
Define the following function, for all O.
f(x) log 1
(38)
We have, the continuous function f monotonically increasing for x E (0, and monotoni-
cally decreasing for e (1, Also, note that, max²>0 f(x) = f(1) = -1, lim f(x) lim f(x) = -0.
Given (1) = (i) > 1. we have f()) < f(1) = -1. According to the intermediate value
theorem, there exists co(i) E (0, such that s(co(i)) f()((i)). Since s(-) is monotonically
17

---

Under review as a conference paper at ICLR 2022
increasing (0. 1] and monotonically decreasing on (1, for all c(t) [co(t), 6u (i)], we have f(e(i) 2 f()((i)) Therefore, we have,
t. (1) - (0( = - (f(((t) f(6o(1)) 2 0.
(39)
Second part. (ii). For the square loss function, we have, for all / 2 0,
Σ (i)
(40)
dt
dt
-1
(,(
(by eq. (16)
(41)
-1 8z,
(42)
which implies that,
d dlog 6t)
dō:
-7
(43)
dt
81 dt
Taking integral, we have,
log 6,
log 80 -17 -t.
(44)
Let 6, = c. We have,
te det
log
60 8,
=
log
ōu
(45)
17
After l. time, for all E [n]. we have,
Sg, (i) (1) expl -1 - te).
(46)
On the other hand, for the cubic loss function, have, for all / 0.
dH,
(()-(t)-1}
(47)
dt
n
dt
17.
(by eq. (25))
(48)
Taking integral, we have,
H, - HH-
(49)
which means given H value, we can calculate the hitting time as,
1 -
(50)
Now consider after t, time, using gradient descent with the square loss function we have &,, (1) 5o( exp(-7) (.) for all E [m], which corresponds to,
=
H
(51)
n
8r (i)
(by eq. (46))
(52)
5n(1)
Note that e(t) (1) by the design of using gradient descent updating rule. If the two equal, (x) = (i) holds trivially.
18

---

Under review as a conference paper at ICLR 2022
Therefore, the hitting time of using gradient descent with the cubic loss function to achieve the Hr," value is.
t.
[H - -HO')
(53)
1
n
1 12
(54)
" n 80(i) eepp -1 tc)
7
50(
1
(exp(n (e) 1) -Hp
(55)
"
(exp(1 (e) - 1) log (ōa/e)
(by eq. (15))
(56)
"
1
1
(ou
-1
log (ōo/c)
(57)
aa
"
60
log
(58)
π
ter
(by eq. (45))
(59)
finishing the proof.
Remark. Figure 7 shows the function f(x) In g. > 0. Fix arbitrary x' > 1, there will be another root to s.t. f(En)= = f(x'). However, there is no real-valued solution for Eg. The solution where (-)) is Wright Omega function. Hence, finding the
in C is 6D exact value of én 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.
Wllog 1/6p-
-4
fix)
Inf
-5
Figure 7: The function f(x) In
x 0. The function reaches maximum at æ 1.
Simulations. The theorem says that if we want to minimize our loss function to certain small nonzero error level, the cubic loss function offers faster convergence rate. Intuitively, cubic loss provides sharper gradient information when the loss is large as shown in Figure 8(a)(b.. Here we provides simulation. Consider the following minimization problems: min x² and min " We use the hitting time formulae 4 = 1 In { [2) 1 1 (t - 2 derived in the proof, to compute the hitting time ratio & under different initial values 2n and final error value In Figure 8(c)(d), can see that usually takes significantly shorter time for the cubic loss to reach certain x; with various initial values.
A.5 ERROR BOUND BETWEEN SAMPLING DISTRIBUTIONS
We now provide the error bound between the sampling distribution estimated by using a true model and a learned model. We denote the transition probability distribution under policy and the true model as pd (r. s'|s), and the learned model as p. s'()). Let p(s) and p(s) be the convergent distributions described in the above sampling method by using the true and learned models respectively. Let (t..) be the total variation distance between the two probability distributions.
19

---

Under review as a conference paper at ICLR 2022
28-
hp
ax?
2|
Ao 0.5
hp
1-
2.0
*F
3/x/?
hiting
time ratio
Ao 10 0
time
10
12
ratio
0
2
2
30
(a) cubic v.8. square
(b) |derivative
(c) M0 V.8. hitting time
(d) 21. V.S. hitting time
Figure 8: (a) show cubic v.s. square function. (b) shows their absolute derivatives. (c) shows the hitting time ratio initial value zo under different target value Hy. (d) shows the ratio v.s. the target it reach under different zq. Note that a ratio larger than 1 indicates longer time to reach given æ, for the square loss.
Define u(s) def the following bound.
((8) def 16(s, ((s))( del SoES u(s)ds, 2 det JaeS u(s)ds. Then have
Theorem 3. Assume: 1) the reward magniude is bounded |r| S Rmax and define Vinaa del Rmaz T- 2) the largest model error for a single state is es def max, deo (P (-1s), Pr (-|s) and the to- tal model error bounded, i.e. c
det Jees c, < co. Then Vs S,lp(s) p(s) S
min( Ymar (p())e+e,) Vmur Vmer (B())cte)))
7
Proof. First, we bound the estimated temporal difference error. Fix an arbitrary state S, it is sufficient the consider the case u(s) > i(s), then
lu(s) - i($) = u(s) - i(s)
70 (s')l = -B(r (r 70 (s')] }]] (r,e)) +70
-f (r+ (s)) (s', r(s) - P (s'rrls))dd' dr
<(moox + Y 11-1 / (P" PD r(s))dd''d dr
Rman
Vmmardeo (P (.18), (16)),p((((1)) S Vmazt.
Now, we show that Z - 21 S Vmann.
1 - 21 = /f u(s)ds -
[ a(s)ds) =1 =1/ (u(s) i(s))dss
J
< / lu(s) - ii(s)lds S Vmaa
/ e,ds= = Vmann
sES
JEE
Consider the case p(s) > p0x) first.
p(s) p(s) = u( ())
i(s)
Z 2
u(s)
u(s)
Vmazts
u(s)2 u(s) + ZV Vmaans
7
2
77
u( (s) V Vmaz + ZZV ZVmanc
Vmaa (p(s)c + cx)
z2
2
Meanwhile, below inequality should also hold:
p(s) p(s) u(s) a(s)
i(s) + VmarCs
a(s)
2
Z
ū(s) a(s)Z + 2V VVmazzs
Vmav (p()) s + Ea)
77
Z
20

---

Under review as a conference paper at ICLR 2022
0.2
0.2
Cubic
Power4
0
0,00
0.25
0.50
0.75
1.00
d.00
0.25
0.50
0.75
1,00
165
1e5
(a) = 0.1
(b) 0 = 0.5
Figure 9: (igure(a)(b) show the testing RMSE as a function of number of mini-batch updates with increasing noise standard deviation added to the training targets. We compare the performances of (magentaa L2 (black), Cubic (forest green). The results are averaged over 50 random seeds. The shade indicates standard error. Note that the testing set is not noise-contaminated.
Because both the two incqualities must hold, when p(s) p(s) > O, we have:
p(s) p(s) S min( Vmaz (p(s)c ()c + (x) Vmaa (f(s)c + c.)
2
Z
It turns that the bound the same when p(s) S p(s). This completes the proof.
A.6 HIGH POWER Loss FUNCTIONS
We would like to point out that directly using high power objective in general problems is unlikely to have an advantage.
First, notice that our convergence rate is characterized w.r.t. to the expected updating rule, not stochastic gradient updating rule. When using a stochastic sample to estimate the gradient, high power objectives outliers is also the motivation behind the Huber loss (Huber, 1964) which, in fact, uses low power error in most places so it can be less sensitive to outliers.
sensitive the outliers as they augment the effect of noise. Robustness to
We conduct experiments to examine the effect of noise on using high power objectives. We use the same dataset described in Section 3.3. We use training with 4k training examples. The naming rules are as follows. Cubic is minimizing the cubic objective (i.e. ming + >im [fo(x,) - yil () by uniformly sampling, and Power4 is ming (fo(x)) y:)² by uniformly sampling.
Figure (a) shows the learning curves of uniformly sampling for Cubic and for Power4 trained by adding noises with standard deviation a = 0.1, 0.5 respectively to the training targets. It is not surprising that all algorithms learn slower when we increase the noise variance added to the target variables. However, one can see that high power objectives is more sensitive to noise variance added to the targets than the regular L2: when a = 0.1, the higher power objectives perform better than regular L2: after increasing to 0.5, Cubic becomes almost the same L2, while Power4 becomes worse than L2.
Second, it should be noted that in theorem, do not characterize the convergence rate to the minimum; instead, we show the convergence rate to a certain low error solution, corresponding to early learning performance. In optimization literature, it is known that cubic power would converge slower to the minimizer as it has a relatively flat bottom. However, it may be an interesting future direction study how combine objectives with different powers that optimizing the hybrid objective leads to faster convergence rate to the optimum and is robust to outliers.
A.7 ADDITIONAL EXPERIMENTS
In this section, we include the following additional experimental results:
As a supplementary to Figure from Section 3.3, we show the learning performance measured by training emors show the negative effects of the two limitations.
21

---

Under review as a conference paper at ICLR 2022
0.70
0.70
Rost mean squared error averaged over 50runs
0.65
Priortized.2
0.60
Full-Prioritzzed2
0.50
0.4
0.00
0.25
0.50
0.75
1.00
0.00 00
0.75
1.00
1e5
(a) [7|
4000
(b) [T] = 400
Figure 10: Figure (a)()) show the training RMSE as a function of number of mini-batch updates with training set containing 4k examples and another containing 400 examples respectively. We compare the performances of 2 (blue), L2 (black). and PrioritizedL2 (red). The results are averaged over 50 random seeds. The shade indicates standard error.
0.70
0.7
0.50
0.50
0.40
0.55
0.0
$8.00 0.00
0.25
0.30
0.75
1.00
0.30 3.25 0.50
0.75
011
0.09
0.2
0.50
0.75
1.00
0.00
0.00
0.5
0.50
0.75
1
(a) b=128, 0.5
(b) b=512, 0.5
(c) b=128,
0.5
(d) b= 0.5
Figure 11: Figure(a)(b) show the training RMSE as a function of number of mini-batch updates with increasing mini-batch size Figure (c)(d) show the testing RMSE. We compare the performances of 2r1i-Prioit (blue), Cubic (forest green). As we increase the mini-batch size, the two performs more similar to each other. The results are averaged over 50 random seeds. The shade indicates standard error.
2. Empirical verification of Theorem 1 (prioritized sampling and uniform sampling on cubic power equivalence).
3. Results on GeizeGriWWoldd from Pan et al. (2020).
A.7.1 TRAINING ERROR CORRESPONDING TO FIGURE FROM SECTION 3.3
Note that our Theorem and 2 characterize the expected gradient calculated on the training set; hence it sufficient to examine the learning performances measured by training errors. However, the testing error is usually the primary concern, so we put the testing error in the main body. As sanity check, we also investigate the learning performances measured by training error and find that those algorithms behave similarly shown in Figure 10 where the algorithms training sets with decreasing training examples from (a) to (b). As we reduce the training set size, full-Prioritizedl.2 is closer L2. Furthermore, PrioritizedL.2 is always worse than Full-Prioritizedl.2 ..2. These observations show the negative effects resulting from the issues of outdated priorities and insufficient sample space coverage.
trained by using
A.7.2 EMPIRICAL VERIFICATION OF THEOREM
Theorem states that the expected gradient of doing prioritized sampling on mean squared error equal to the gradient of doing uniformly sampling cubic power loss. As result, expect that the learning performance on the training set (note that we calculate gradient by using training examples) should be similar when we large mini-batch update the estimate of the expectation terms become close.
We the same dataset described in Section 3.3 and keep using training size 4k. Figure 11(a)(b) shows that when we increase the mini-batch size, the two algorithms Full-Prioritized22 and Cubic becoming very close to each other, verifying our theorem.
22

---

Under review as a conference paper at ICLR 2022
Average Retum per H
G
-500
(20nuns)
1750
stops
(a) MazeGridWWoll
(b) MazeGW, n2 30
Figure 12: Figure(a) shows MazeGridWorld(GW) taken from Pan et al. (2020) and the learning curves in (b). We show evaluation learning curves of Dyna-TD (black), Dyna-Frequency (red), and Dyna- Dyna-Value (blue). The dashed line indicates Dyna- TD trained with an online learned model. All results averaged over 20 random seeds after smoothing over window of size 30. The shade indicates standard erro.
Note that our theorem characterizes the expected gradient calculated on the training set; hence is sufficient to examine the learning performances measured by training errors. However, usually, the testing error is the primary concern. For completeness, we also investigate the learning perfor- mances measured by testing error and find that the tested algorithms behave similarly shown in Figure (I(c)dd).
A.7.3 RESULTS ON MAZEGRIDWORI DOMAIN
In Figure 12, we demonstrate that our algorithm can work better than Dyna-Frequency on a Maze- GridWorld domain (Pan et al., 2020), where Dyna-Frequency was shown to be superior to Dyna- Value and model-free baselines. This result further confirms the usefulness of our sampling approach.
A.8
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.8.1 REPRODUCE EXPERIMENTS BEFORE SECTION
Supervised learning experiment. For the supervised learning experiment shown in section 3, we 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 as specified in the Theorem 1 at each time step for Cubic loss. We compute the testing error every 500 itcrations/mini-attee updates and our evaluation learning curves are plotted by averaging 50 random seeds. For each random seed, we randomly split the dataset testing set and training and the testing has 1k data points. Note that the testing set is not noise- catise-cottmmnated.
Reinforcement Learning experiments in Section 3. We use particularly small neural network 16 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 small neural network, 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 chosen from (0.0001, 0.001} and the target network 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 to compute the desired sampling distribution, we discretize the domain into 50 50 grids and calculate the absolute TD enror of each grid frepresented 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.
23

---

Under review as a conference paper at ICLR 2022
Second, 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 et 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 P2 to p by two weighting schemes: 1) on-policy weighting: 2500 d" (s)))p((ss)) p" (s;)). E [1, where d' is approximated by uniformly sample 3k states from a recency buffer and normalizing their visitation counts on the discretized GridWorld; 2) uniform (1, We examine the two weighting schemes because of two considerations: for the on-policy weighting, we concern about the asymptotic convergent 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.
weighting: 2500 Σj=1 2500
Computational cost v.s. performance in Section 4. The setting is the same we used for Section 5. We use plan step/updates=10 to generate that learning curve.
A.8.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 discrete control domains other than roundabout-vO, we use 32 x 32 neural network with ReLu hidden units except the Dyna-Frequency which uses tanh units suggested by the author (Pan et al., 2020). This is one of its disadvantages: the search-control of Dyna-Frequed requires the computation of Hessian- Hessian-gradient product and it empirically observed that the Hessian is frequently zero when using ReLu as hidden units. 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 h = 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.
Hy parraaarr settings. Across RL experiments including both discrete and continuous control tasks, we are able to fix the same parameters for hill climbing updating rule 3 8 + 8 + 0. V, log lū(s) max, Q(+,, a; 0,)l + X, where we fix or = 0.1, ~ 0.000.
For algorithm Dyna-TD, we are able to keep the same parameter setting across all discrete domains: 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) Dyna-TD does, and use Enccept 0.1 and set the maximum number of gradient step as k = 100 unless otherwise specified.
Our Prioritized ER is implemented 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 a strategy for bias correction. For Dyna-Value and setting as described by the original papers.
we use the
For the purpose of learning an environment model on those discrete control domains, we use a 64 x 64 ReLu units neural network to predict s' s and reward given state-action pair s, a; 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-specffee 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 Grid has state space S J0, 1)2 and each episode starts from the left bottom and the goal area is at the top right (0.95, 1.0]2. 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
24

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Dyna-TD
Input: mt number of states fetch through search-control: Bac: empty search-control queue;
Ber: ER buffer; Eaccepti threshold for accepting a state; initialize Q-network Qo for t 1,2.... do
Observe (st, ae, S1+1, re+1) and add it to Ber
Hill climbing on absolute TD error
Sample from B 4 0, +-
while c < m do
ÿ 4 "rmpb s.a)
max. Qo(s'.a)] Update s by rule (3)
if is out of the state space then
Sample from B + restart continue
if - SSsll//vV 2 caccept then // d is the number of state variables, i.e. S 12d Add into Bsc, 3 + 8, s.c+ct] I/n planning updates for times do
Sample mixed mini-batch with half samples from Bac and half from Ber Update Q-network parameters by using the mixed mini-batch
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 64 ReLu units, and number of search-control samples m 50 as used by the original paper. We refer readers to the original paper (Pan et al., 2020) for more details.
On roundabout-vO domain, we use 64 64 ReLu units for all algorithms and set mini- mini-batch size as 64. The environment model is learned by using a 200 x 200 ReLu neural network trained by the same way mentioned above. For Dyna-TD, we start using the model after steps and set m 100, and do search-control every 50 environment time steps reduce computational cost. To alleviate the effect model error, we use only 16 out of 64 samples from the search-control queue mini-batch.
500
On Mujoco domains Hopper and Walker2d, we use 200 x 100 ReLu units for all algorithms and set mini-batch size as 64. The environment model is learned by using 200 x 200 ReLu neural network trained by the same way mentioned above. For Dyna-TD, we start using the model after 10k steps and set 100, k 500 and do search-control every 50 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.
25

---

Under review as a conference paper at ICLR 2022
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)
ny +- count for parameter updating times, 4- 1000 target network updating frequency Caccept +- 0: threshold for accepting a state
Initialize Q network Qe and target Q network Qe for t = 1, 2, do
Observe (s, a, s', r) and add it to Ber Mas f- (aa(t-1)+s8' M/s (t(1-1)+
Σg tos -as- Map
Caccept & (1 Caceept + B11s s|12 for 0.001
// Hill climbing on absolute TD error
Sample s from Ber, c 0, 8, -
while
and < kip 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 + + Or V. log(lğ max. Q(s, 0;)) + 10-5) + + X,X ~ N(0,0.015)
if is out the state space then
// restart hill climbing
Sample from B Sts continue
if || Add into Bse, 3 c.c
1 s||2/Vd 2 caceept then
i 1+
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 +- n0 +1
if mod(n,, (n,, T) 0 then
Qo t- Q9
26


Reviews:
[{"review_id": "v2E5P2r4x9", "reviewer": "Reviewer_iRvC", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "### Strengths\n\n- This paper is well-written. The motivation and core mechanism behind their method is clearly and concisely explained, and ample, additional details are provided in the appendix.\n- The experimental results are presented in a simple and digestable manner. They highlight gains with respect to the key baseline, which is simply standard PER. These results are convincing, as their method both improves on PER in terms of both returns and distance to the ground-truth PER distribution (if all transitions were updated rather than just those in the minibatch).\n- The experimental setting is diverse: It contains both a gridworld environment, standard continuous control Gym tasks, and a driving task based on driving around a roundabout.\n- In sum, their problem motivation, method motivation and description, and experimental results make the case for Dyna-TD quite convincing.\n\n### Weaknesses\n\n- While the paper looks at the number of SGLD updates n in {10, 30} and show that larger n does not make a large difference in accuracy to the ground-truth PER distribution, it seems like a missed opportunity to further decrease n to see just how few updates are needed to retain the observed performance and accuracy gains.\n- Related to the above point, it would make the method more convincing if the authors could show that the SGLD updates do tend to approximately converge after just n=10 updates.\n- A key missing baseline in their RL experiments is Full-PrioritizedER. This baseline is required to make sure that Dyna-TD is working for the hypothesized reasons. I believe this may be as simple as adding their MountainCar result in Figure 1 (c) to Figure 4.\n- Their method, while called Dyna-TD, diverges from Dyna in that the agent only trains on samples collected from the experience replay buffers, which in this case, acts as a purely memory-based model. Therefore, it seems that an algorithm that better matches the name \"Dyna-TD\" would also train the agent on experiences collected online in each update cycle, as done in Dyna. In contrast, their method seems more accurately described as a form of PER, e.g. Langevin-Dynamics PER. Since the authors make a considerable effort drawing the connection between ER and Dyna, it would benefit the paper to benchmark a version of HC-Dyna that mirrors Dyna in also performing updates on transitions collected online.\n- Several interesting empirical findings warrant deeper analysis: For example,\n    - i) Why does Dyna-TD result in fewer car crashes and lower average speed despite attaining similar asymptotic episodic returns during training?\n    - ii) Why does Dyna-Value and Dyna-Frequency perform worse? The authors put forth a hypothesis that perhaps these variants bias toward transitions with low TD-error, leading to slower learning, but do not verify this hypothesis with data.\n- Given the similarity of this work to Pan et al, 2020, which introduced HC-Dyna and Dyna-Frequency, I believe having more in-depth analysis that highlights why the new method, Dyna-TD works better than Dyna-Value and Dyna-Frequency, is important for making this paper a more substantial, standalone contribution.\n- Dyna-TD introduces two hyperparameters, the number of SGLD updates n and the variance of the noise variable X. The paper would benefit from experiments showing how X impacts the performance of Dyna-TD.\n- The authors should make clear in the paper that their method, Dyna-TD, only applies to continuous state-space environments.", "summary_of_the_paper": "This paper proposes an alternative method for performing Prioritized Experience Replay (PER), which avoids issues of inadequate state coverage and staleness in priority scores. Their method is based on a result from stochastic langevin dynamics, which shows their specific stochastic gradient Langevin dynamics (SGLD) update to online states leads to the ground-truth PER distribution in the limit. Updating collected states this way and adding them to an additional \"stochastic-control queue\" from which sampled minibatch transitions are mixed with those sampled from a standard experience replay buffer. Empirically, this paper shows this SGLD-based method leads to a closer approximation to the ideal prioritized experience replay distribution over recent transitions than standard PER.", "summary_of_the_review": "The paper provides strong motivation and empirical results supporting their new method Dyna-TD.  However, given their method is a simple extension of HC-Dyna and Dyna-Frequency from Pan et al, 2020, where they replace the hill-climbing objective with a TD-error objective, it seems important to include more analysis comparing and contrasting TD-Dyna to HC-Dyna, as well as a deeper understanding of Dyna-TD's learning dynamics. For these reasons, while I find the method itself promising, I recommend this paper as being marginally below the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gyCJ9klaX1", "reviewer": "Reviewer_DyBg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The paper proposes to use prioritized sampling in conjunction with a model-based RL algorithm and attempts to solve issues with PER using up-to-date priorities using SGLD and using a dynamics model to augment data to cover the space. The paper is interesting, but there are several issues in my opinion:  \n\n- From the intro: \"The idea behind prioritized sweeping is quite intuitive: we should give high priority to states whose absolute TD errors are large because they are likely to cause the most change in value estimates.\" -- this is not intuitive to me, controlling TD errors on the training distribution may not give rise to a better performing policy!\n\n- Theorems 1 and 2 apply only to the supervised learning setting or FQI, but that is not what we do in practice. We typically update the target network halfway. Is prioritization still always good in this case, and improves convergence rate? To me, this is not clear -- and I think the answer is no. Let's say that the Q-function is diverging, then prioritization will cause the network to fit diverged target values compared to the more stable ones as they have higher TD errors. So I don't think Theorems 1 and 2 really reflect reality.\n\n- I don't buy the algorithm proposed. When doing SGLD to find states with high TD error, one can find arbitrary far away states. Augmenting them with model data to generate target values and then training on them may actually exacerbate the problem since the model is going to be inaccurate and may predict very high or incorrect reward values. These problems do actually arise in model-based offline RL, even though the states are obtained by unrolling short model rollouts under the learned model, on domains where models can be fit well (e.g., continuous control gym benchmarks). So I am unsure if the technique proposed is generally useful, unless we control for OOD errors. it might work well on the toy domains in the experiments, but may not still be general.\n\n- The results on continuous control tasks are not convincing. First of all, they use DDPG, which is known to be a bad algorithm. If you can show this on TD3 or SAC, I would be somewhat more convinced. Also what if you try the algorithm on a domain where the model is slightly inaccurate, or maybe do an ablation for that? It is good to know what happens when the learned model is inaccurate.", "summary_of_the_paper": "The paper proposes to use dynamics moel to augment data to alleviate some issues with PER pertaining to insufficient coverage, and outdated priorities. Some empirical validation shows that the algorithm performs well on some toy control tasks.", "summary_of_the_review": "I feel like the paper does not indicate (1) why we should build on PER (2) in my opinion, the algorithm is flawed and may not scale otherwise to problems where dynamics models are inaccurate (3) the empirical results are not convincing. So, I am going for a reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IOGVDK41MV", "reviewer": "Reviewer_xiwV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The idea in the paper is interesting. However, I can't follow some discussions and am not convinced by the arguments from the author. \n\n1. Theorem 3 basically says that cubic loss can learn faster than quadratic loss in some scenarios. However, different loss function might allow different learning rate.\n2. Why would we sample $s$​ in the full state space? There are many states that our current policy doesn't access, so why should we care about the TD loss for these states? As shown in Figure 2, PER doesn't waste its time reducing the TD loss of black cells, while Dyna-TD does so. \n3. The outdated priority issue is not solved, either. After updating value on a batch, the priorities also changes, so the search control queue $B_{sc}$​ is outdated again. \n4. SGLD in Section 4.1: Please explain what the temperature parameter is. In addition, please make it clear that the stationary distribution of $s$ depends on the the variance of $X_i$. \n5. The importance ratio, which is an important aspect of PER, is not discussed in this paper. With importance ratio, the loss is unchanged, so Section 3.1 becomes useless. In Figure 1, is the importance ratio added? If not, the comparison doesn't make much sense as we're comparing the test error of two algorithms with different training error. \n6. I don't see the point of being model-based. In Algorithm 3, how is the learned dynamics model used? Is it used to compute $\\hat y$? Please elaborate. \n7. In continuous control tasks, how is the max in Equation 3 computed? \n8. The theory on Section 3.1 is kind of simple: Theorem 1 can be simply viewed as importance sampling. Theorem 2 is basically univariate regression with mse/cubic loss. ", "summary_of_the_paper": "This paper takes a deep look at prioritized experience replay, a popular technique in deep reinforcement learning. The paper gives insights on why error-based prioritized experience replay can help when the importance ratio is unused. This paper also pointed out two limitations of prioritized experience replay, which are outdated priorities and insufficient coverage of state space, and the author proposed to use SGLD to solve the limitations. Experiments show that the proposed method leads to a good coverage of state space and improve the return of the training algorithm.", "summary_of_the_review": "I feel like there is a plenty room of improvement. Some key aspects of PER is not discussed in the paper, I'm not convinced the proposed solution solved the issue, and the theory is not very technical either. Thus I don't recommend acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AnmjgsMoq6T", "reviewer": "Reviewer_VdDV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "## Claims, contributions, and significance\n\nThere are actually two claims in the paper.  \nThe first (section 3), which I judge as minor and clumsily presented, is that sampling according to the TD error is justified by the fact that it is equivalent to optimizing a cubic loss.  \nThe second is IMHO the main contribution, consists in selecting states for minibatches according to a Langevin dynamic, then exploiting a model to build target values, and finally performing SGD using these samples. This claim could be made clearer since the beginning of the paper (currently, what the algorithm actually is is only clarified in section 4, on page 6).\nThis second claim takes the form of an algorithm, building on previous work (HC-Dyna) and could be a significant contribution to the community if it were better discussed.\n\n## Clarity\n\nI believe the paper could be improved a lot by verifying the phrasing, the typos and the syntax (all across the paper and mostly in sections 4 and 5).\nSome words are regularly missing in sentences. The paper remains readable but is clearly not polished.\nAlthough the claims appear rather clearly in the introduction, the discussion quickly becomes clumsy and difficult to follow. Some notations are also confusing (the ones in thm 2 and in section 4.1 for instance) and sometimes two different notations are used for the same notion across the paper (targets in section 3 are not the same as in section 4, $v(s)$ in 4.1 is actually $v(s,\\theta_t)$, etc.).\nAlso I fail to understand why section 4.2 is not part of section 5.\n\n## Proper grounding would make section 3 a lot better\n\nI would like to encourage the authors to ground their paper in the proper framework they are working in. What is at stake here is the resolution of the Bellman equation via approximate dynamic programming, where the approximation is solved by stochastic gradient descent. No mention of ADP is made whatsoever in the paper. Despite it being the key background of what is done here.\nTo the authors: Don't get me wrong, this is not a whim, I strongly believe taking the time to properly ground your discussion will help you substantially improve both your contribution and your paper.\nFor instance, ADP's error bound for the L2 loss have been extensively studied in (Munos 2003, 2005, Scherrer et al 2012) and there is a whole literature on MDP solving (model-based RL is just the current fancy name).\nAnecdotally, in the introduction stating that \"in particular, prioritized sweeping improves upon vanilla Dyna\" induces confusion. PS is a pure dynamic programming scheme (an asynchronous DP one to be precise), it has nothing to do with SGD in ADP. And since it uses tabular representations, it does not need perform SGD steps at all. It loosely served as an inspiration for PER, that's all. It is thus debatable to compare it with Dyna (which is an architecture, rather than an algorithm).\n\nNot setting up properly the ADP loss makes the contribution very brittle and shallow. What is the loss optimized?\nThe only place we come close to discussing this loss is section 3. But here again the discussion is shallow.\nThe loss optimized in DQN is an L2 loss. It's derivative induces the TD errors. Why not start by recalling these simple facts to develop the ideas of section 3? Looking at non-uniform sampling for SGD implies doing importance sampling in order to obtain gradient estimates. And, unfortunately, I believe the authors totally miss the literature on non uniform sampling in SGD (Needell et at 2014, Zhao and Zhang 2015, Alain et al. 2016, Wang et al. 2017, Katharopoulos and Fleuret 2018). In particular, PER does not exactly sample the transitions according to the TD errors. It actually samples them according to $(\\delta +c)^\\alpha$. And then it weights differently the contribution of each sample in the gradient computation, precisely because it mimics (approximately) an importance sampling scheme. There is nothing on this matter in section 3 and the authors seem to ignore a major part of what actually happens in PER. Also, as is common in DQN algorithms, the loss used is actually a Huber loss (so it's equivalent to L2 for small loss values) which induce a slightly different prioritization scheme of $\\min(delta,1)$.\n\nOverall, having an explicit loss would allow showing that the property illustrated in thm 1 actually holds for any L_p and L_{p+1} losses (with a few minor modifications). It could also highlight the fact that changing the loss might change to minimum of the empirical risk (L2 implies an average, not necessarily L3) and therefore the claim that \"optimizing the cubic power objective [...] has faster convergence rate\" should be mitigated: it's true, but convergence to what?\n\nAlso, relating the proof of theorem 2 (which appeared unnecessarily convoluted to me) to the convergence speed of SGD as developped in (Needell 2014) for instance could be a link for a clearer and more impactful contribution.\n\n## Insufficient sample space coverage is an issue that is linked directly with online exploration\n\nThe paper claims PER has two weaknesses: outdated priorities and insufficient sample space coverage.  \nI'll agree with the first and argue that the second has nothing to do with PER but rather with online RL in general. If you're interacting online with an MDP environment and can't sample states wherever you wish, you are doomed to concentrate samples around the starting state(s) unless you perform some kind of filtering when filling the replay buffer. It is a core question of exploration. PER mitigates unbalance in the replay buffer by prioritizing (just as the other non-uniform sampling methods for SGD). Model-based RL allows to obtain samples everywhere and thus the comparison seems unfair.  \n\n## Up to date priorities could be better discussed\n\nThe authors claim their approach allows to sample (approximately) according to TD errors, which is true. This, however, does not guarantee that sampling according to TD errors will provide good descent directions. First, because solely changing the sampling distribution without reweighting each sample, biases the gradients in SGD. Second, because nothing guarantees that TD errors are actually a good distribution for better gradient estimates. To understand this, we need to go back to basics again concerning why sampling according to TD errors makes sense in some cases. It makes sense because the optimal importance sampling distribution for the L2 loss is proportional in each sample, to the loss' gradient. And the TD error is a surrogate (and only a surrogate) of the loss' gradient. this explains why in some (not so rare) occasions, PER does not improve on DQN. The illustration of section 3.3 could be, again, related to the question of defining good sampling distributions as for example in (Katharopoulos and Fleuret 2018).\n\n## Limitations of Langevin dynamics\n\nA comment: Langevin dynamics requires a non piecewise-constant density function. Interestingly, for many MDPs, the value function is piecewise constant. Take for example the deterministic, continuous action, 2D navigation problem in a box, with a reward only at the exit, then the optimal value function is piecewise constant. This is likely to lead to piecewise constant TD errors and thus zero gradients for the Langevin dynamic. In this case, the proposed surrogate sampling scheme boils down to a Metropolis-Hastings dynamic, whose good properties fully depend on the Gaussian random variable which is not really discussed in the paper.\n\n## Section 4.1 should be clarified\n\nBesides the notations (already mentioned, e.g. $y(s)$ should be $y(s,\\theta)$) there are a lot of clumsy formulations in section 4.1.  \nFor instance, if $v(s)=\\max_a Q(s,a;\\theta_t)$ then the TD error is actually a TD error for the Bellman equation defined on $v$ functions. Then why isn't the value function $v$ directly parametrized by $\\theta$? What's the need to use $Q$?  \nAlso, when $\\hat{y}(s)$ is considered constant, it is left to the reader to assume it is with respect to $s$. This assumption seems rather strong and would deserve a better discussion (despite the argument provided in appendix A.5).\n\n## Experiments are not discussed in depth\n\nI don't understand Figure 2. If what is represented is the distribution of states in the replay buffer, why is there no mass around the starting state or around common trajectories for DQN and PER?\n\nThe comparison of the total variation metric (why not call a spade a spade?) on Figure 3,  between PER and the distribution according to a Langevin dynamic is quite unfair. Since PER only updates TD errors in states selected in minibatches, as the authors point out, the vast majority of priorities is outdated and thus these figures are not surprising. What is the point then?\n\nThe baselines made me doubt: is PER the version with a target network, Huber loss, priorities $(\\delta +c)^\\alpha$, and sample reweighting?\n\nThe discussion on Dyna-Value/Frequency deserves more than a wild conjecture. The authors refer to explosive of zero gradients, imbalance in the sampled states, hyperparameter sensitivity, but the discussion remains shallow as to why Dyna-TD outperforms them and seems to perform well in general.\n\nThe part on DDPG deserves a few precisions: minibatch sampling is done according to the Langevin dynamic for the critic alone? Or is there a common sampled minibatch for the actor and the critic? What's the rationale?  \nAlso, DDPG suffers from a number of limitations concerning its convergence speed and stability. Experimenting with the much more stable TD3 or SAC (to remain in the family of approximate value iteration algorithms) would be more convincing.\n\nThe conclusion on the Highway environment puzzles me. All algorithms optimize for cumulative (discounted) reward, so the fact that episodic return is approximately equivalent between them rather illustrates that Dyna-TD does not bring a significant advantage over PER. After that, claiming that it is better because it crashes less is a very anthropomorphic interpretation whose interest I fail to see.\n", "summary_of_the_paper": "This paper deals with stochastic gradient descent for approximate value iteration and relies upon the commonly admitted result (of prioritized experience replay) that sampling states from the replay buffer according to their TD error provides better gradient estimates. The main contribution of the paper consists in using a Langevin dynamic in order to simulate the distribution of TD errors over states, in order to build minibatches in model-based reinforcement learning.", "summary_of_the_review": "I recommend rejection of the paper.\nIn the review above, I have done my best to give the authors detailed info on why I believe the paper in its current state is too shallow. The idea of using a Langevin dynamic to draw states according to their TD error seems like an interesting basis to me but the current paper needs more work to be accepted for publication.\nTo summarize my main arguments:\n- Lack of connection to the litterature on MDP solving and non-uniform sampling in SGD.\n- No actual justification of why PER is (or not) sound.\n- Not clear enough on what the contribution is.\n- The algorithmic contribution is not studied enough, both theoretically and empirically.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work provides a theoretical analysis of Prioritized Experience Replay (PER ) in a supervised learning setting, points out limitations of PER and proposes a model-based approach to address these shortcomings for continuous control problems.  

Strengths:
-----------
The overall problem was motivated well
Reviewers agree that this proposed algorithm has promise
Overall the paper is well written
a diverse set of experiments is provided

Weaknesses:
---------------
reviewers point out some clarity issues
The theoretical analysis is performed in a supervised learning setting, and it is unclear how the resulting analysis transfers to the RL setting
There are some concerns (theoretical/technical) wrt to the proposed algorithm. 
The analysis of the experiments is lacking in depth. For instance, no analysis of why the proposed algorithm outperforms very related baselines. Furthermore, it's unclear why for the autonomous driving experiment the algorithms achieve the same return, but the proposed method leads to less crashes. 

Rebuttal:
----------
The authors have addressed many of the clarity issues. However, I agree with the reviewers theoretical concerns and deeper analysis requests were not addressed in a significant manner. 

Summary:
------------
Overall this manuscript investigates an important problem and provides a promising algorithm. However, some theoretical/technical concerns remain and a deeper analysis of results is required. Hence my recommendation is that in it's current form the manuscript is not quite ready yet for publication.
Decision: Reject