Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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. 

1. 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.
2. 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. 
3. 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. 
4. 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$. 
5. 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. 
6. 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. 
7. In continuous control tasks, how is the max in Equation 3 computed? 
8. 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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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:  

- 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!

- 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.

- 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.

- 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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: ### Strengths

- 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.
- 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).
- 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.
- In sum, their problem motivation, method motivation and description, and experimental results make the case for Dyna-TD quite convincing.

### Weaknesses

- 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.
- 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.
- 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.
- 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.
- Several interesting empirical findings warrant deeper analysis: For example,
    - i) Why does Dyna-TD result in fewer car crashes and lower average speed despite attaining similar asymptotic episodic returns during training?
    - 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.
- 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.
- 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.
- The authors should make clear in the paper that their method, Dyna-TD, only applies to continuous state-space environments.
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: ## Claims, contributions, and significance

There are actually two claims in the paper.  
The 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.  
The 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).
This 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.

## Clarity

I 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).
Some words are regularly missing in sentences. The paper remains readable but is clearly not polished.
Although 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.).
Also I fail to understand why section 4.2 is not part of section 5.

## Proper grounding would make section 3 a lot better

I 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.
To 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.
For 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).
Anecdotally, 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).

Not setting up properly the ADP loss makes the contribution very brittle and shallow. What is the loss optimized?
The only place we come close to discussing this loss is section 3. But here again the discussion is shallow.
The 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)$.

Overall, 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?

Also, 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.

## Insufficient sample space coverage is an issue that is linked directly with online exploration

The paper claims PER has two weaknesses: outdated priorities and insufficient sample space coverage.  
I'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.  

## Up to date priorities could be better discussed

The 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).

## Limitations of Langevin dynamics

A 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.

## Section 4.1 should be clarified

Besides the notations (already mentioned, e.g. $y(s)$ should be $y(s,\theta)$) there are a lot of clumsy formulations in section 4.1.  
For 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$?  
Also, 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).

## Experiments are not discussed in depth

I 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?

The 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?

The baselines made me doubt: is PER the version with a target network, Huber loss, priorities $(\delta +c)^\alpha$, and sample reweighting?

The 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.

The 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?  
Also, 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.

The 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.

summary_of_the_review: I recommend rejection of the paper.
In 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.
To summarize my main arguments:
- Lack of connection to the litterature on MDP solving and non-uniform sampling in SGD.
- No actual justification of why PER is (or not) sound.
- Not clear enough on what the contribution is.
- The algorithmic contribution is not studied enough, both theoretically and empirically.
review_title: null

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