Uncertainty Prioritized Experience Replay

Authors: Rodrigo Antonio Carrasco-Davis, Sebastian Lee, Claudia Clopath, Will Dabney
Primary area: reinforcement learning
Keywords: reinforcement learning, replay, uncertainty

Abstract:
Prioritized experience replay, which improves sample efficiency by selecting relevant transitions to update parameter estimates, is a crucial component of contemporary value-based deep reinforcement learning models. Typically, transitions are prioritized based on their temporal difference error. However, this approach is prone to favoring noisy transitions, even when the value estimation closely approximates the target mean. This phenomenon resembles the _noisy TV_ problem postulated in the exploration literature, in which exploration-guided agents get stuck by mistaking noise for novelty. To mitigate the disruptive effects of noise in value estimation, we propose using epistemic uncertainty to guide the prioritization of transitions from the replay buffer. Epistemic uncertainty quantifies the uncertainty that can be reduced by learning, hence reducing transitions sampled from the buffer generated by unpredictable random processes. We first illustrate the benefits of epistemic uncertainty prioritized replay in two tabular toy models: a simple multi-arm bandit task, and a noisy gridworld. Subsequently, we evaluate our prioritization scheme on the Atari suite, outperforming quantile regression deep Q-learning benchmarks; thus forging a path for the use of epistemic uncertainty prioritized replay in reinforcement learning agents.

Decision: reject
Reviewer scores: 5, 5, 5

Reviews and discussion:
<thread>
creation date:
1729779779766

thread_type:
official_review

<thread_object>
creator: reviewer_peo7

<content>
summary:
In this paper, the authors propose a new experience replay method, called Uncertainty Prioritized Experience Replay (UPER), which leverages epistemic uncertainty to improve sample efficiency. To estimate epistemic uncertainty, they introduce a modified concept of total uncertainty and they decompose it into aleatoric and epistemic uncertainties, as shown in Eq. (7). Based on the estimation of aleatoric uncertainty, they also propose a priority motivated by information gain, as detailed in Eq. (11). They validated UPER in various atari task under QRDQN

strengths:
1. Reasonable Motivation: The authors introduced two examples: conal bandits and noisy greedy world 
2. Easy to Implement but good insights: The authors proposed new formula for uncertainty and a way to compute prioritization using the uncertainty with the concept of information gain.
3. Implementation seems to be not difficult.

weaknesses:
1. The authors used QR-DQN as the benchmark. So it is unclear whether this concept is still valid across different distributional Q-learning (e.g., C51, Rainbow)

2. The authors provided compuational costs in Table 1 for each algorithm. But it is unclear the coupuational cost between Random vs PER vs UPER.

questions:
1. The Introduction section lacks sufficient depth, and the proposed method is introduced too briefly. For example, there is no mention of the need for an ensemble or the importance of the concept of information gain. Additionally, while the motivating examples are significant, they are not presented until Section 4. In my view, the Introduction should consider the following points: First, it would be meaningful to include the motivating examples and explain why epistemic uncertainty is crucial, as well as why PER is not suitable for certain tasks. Second, providing why the concept of information gain is necessary would improve the readibility. Third, utilizing an ensemble, while the computational costs are marginal, to estimate the uncertainties would be also helpful to the readers. I would appreciate it if the authors could provide their thoughts on these points.


2. It could be valuable to evaluate the feasibility of this method under different RL distributions. For example, the study (https://arxiv.org/abs/1906.05243) referenced in this paper used only 100K steps (see Table E). I would appreciate your thoughts on whether the experiments I have proposed are feasible by utilizing the efficient rainbow in (https://arxiv.org/abs/1906.05243) or C51 another algorithm, even though  the new method seems to be effectively independently of algorithms from a mathematical standpoint. 

3. Prioritized Experience Replay (PER) is a meaningful method, but I believe that some of the expressions used may contain exaggerated aspects. For instance, the authors state, "PER has been widely adopted as a standard technique in DRL" in Line 29, and "Prioritized experience replay is a crucial component of contemporary deep reinforcement learning models" in Line 10. However, I think that the effectiveness of PER has been primarily studied in value-based learning, rather than in policy-based or actor-critic methods, such as TD3. I would appreciate hearing the authors' perspective on this matter.

4. I believe the readability of this paper could be improved if the authors were to change their citation style, such as using numbering or placing parentheses around citations. For instance, in line 39~41, "PER is an extension of Experience Replay Lin (1992), which uses ...." can be revised as "PER is an extension of Experience Replay, as introduced by Lin (1992)" or "PER is an extension of Experience Replay (Lin (1992))". I am curious about the authors' opinions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730516428557

thread_type:
official_review

<thread_object>
creator: reviewer_7m4h

<content>
summary:
This paper proposes a novel prioritized experience replay method to enhance exploration in reinforcement learning (RL). To address the adverse effects of noise on value estimation observed in previous methods, the authors suggest leveraging epistemic uncertainty to guide the prioritization of transitions. The effectiveness of their approach is demonstrated through comprehensive experiments.

strengths:
1. The paper tackles the critical issue of exploration in RL and offers a promising method that uses uncertainty to prioritize interaction data.
2. Comprehensive experiments are provided, ranging from bandits and tabular tasks to Atari tasks.

weaknesses:
1. The paper lacks contemporary baselines in Atari games. The baselines compared in this paper are somewhat outdated, while several recent works also consider estimating uncertainty to improve exploration.
2. The writing could be polished further. Some sentences are quite colloquial, such as "this is shown graphically in Figure 14 and Figure 15" in line 394.
3. The paper primarily discusses the advantages of their prioritized variables through verbal descriptions and toy examples. It would benefit from some theoretical analysis to substantiate the improvement of their methods.

questions:
1. I don't think the MSE in Figure 1(b) is a good metric for bandit tasks, as overfitting can also lead to lower MSE. Can you replace it with accumulated regret? Figure 1(c) is messy. The legend in the figures is "Unstable" and "Stable," but the caption uses "stablest" and "noisiest." The colors in the legend are black, but the lines in the figures are blue and green. Figure 1(c) needs to be polished with clearer explanations.
2. More baselines should be considered in Atari. The naive prioritized DQN[1] can act as the basic baseline since it uses the TD-error as the priority. Additionally, other methods using uncertainty should be considered, such as HyperAgent[2]. There are some Atari games requiring hard exploration as described in [3]. How does your method perform on these Atari games? Can UPER be applied to some SOTA deep RL algorithms, such as Rainbow[4] or BBF[5]?
3. It seems like the uncertainty in Eq(9) also depends on the error. Does it consider the disagreement among ensembles?

[1] Schaul T. Prioritized Experience Replay[J]. arXiv preprint arXiv:1511.05952, 2015.

[2] Li Y, Xu J, Han L, et al. Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent[J]. arXiv preprint arXiv:2402.10228, 2024.

[3] Bellemare M, Srinivasan S, Ostrovski G, et al. Unifying count-based exploration and intrinsic motivation[J]. Advances in neural information processing systems, 2016, 29.

[4] Hessel M, Modayil J, Van Hasselt H, et al. Rainbow: Combining improvements in deep reinforcement learning[C]//Proceedings of the AAAI conference on artificial intelligence. 2018, 32(1).

[5] Schwarzer M, Ceron J S O, Courville A, et al. Bigger, better, faster: Human-level atari with human-level efficiency[C]//International Conference on Machine Learning. PMLR, 2023: 30365-30380.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730627830533

thread_type:
official_review

<thread_object>
creator: reviewer_c2gf

<content>
summary:
The paper introduces an approach called Uncertainty Prioritized Experience Replay (UPER) to enhance sample efficiency in deep reinforcement learning. The traditional Prioritized Experience Replay (PER) relies on temporal difference (TD) error to prioritize samples in the replay buffer which does not perform well in noisy environments. UPER addresses this issue by utilizing epistemic uncertainty—representing uncertainty that can be reduced through learning—along with aleatoric uncertainty, which refers to the inherent randomness in the data. The authors use these uncertainties to rank samples in the replay buffer. The authors validate UPER through experiments conducted on toy models and the Atari-57 benchmark, demonstrating that it outperforms PER and vanilla QR-DQN.

strengths:
1) Motivating examples that clearly show the advantage over PER.
2) The paper is well-written and clearly presented.

weaknesses:
1) The method is only compared to Prioritized Experience Replay (PER), which is quite old. There are other approaches that have improved upon PER in recent years, such as [1]. We expected to see comparisons with these newer methods.

2) The paper claims that it enhances sample efficiency; however, it does not demonstrate how their approach contributes to solving one of the most challenging Atari games, Montezuma’s Revenge, in the main paper. An experiment in the appendix reveals no improvements for these difficult problems.

3) Both PER and UPER are more computationally expensive than Uniform Sampling. We anticipated a comparison between these algorithms using the same training time or, at the very least, a comparison based on wall-clock time.





[1]- Understanding and mitigating the limitations of prioritized experience replay.

questions:
1) PER can be applied in all RL algorithms which are based on TD error. How can we apply your idea in algorithms such as vanilla DQN where we do not have an ensemble of models or the distribution of Q-values?

2) Can you explain how Equations 7 and 8 are connected? I mean if we sum both uncertainties in Equation 8, can we get the total uncertainty in Equation 7?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732154512678

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
Thank you to all reviewers for their careful reading, insightful questions, and valuable suggestions. We have addressed all concerns, significantly improving the paper. Here are key points based on the feedback:

One aspect of our proposed method UPER  we could have been clearer about is that it is not an algorithm that enhances exploration explicitly. Traditional exploration algorithms use uncertainty measures to encourage exploration by rewarding agents for interacting with unvisited, uncertain, or high-error states. In contrast, UPER employs estimators for epistemic and aleatoric uncertainty to prioritize sampling transitions from the replay buffer based on information gain, which is then used to update value estimates. While these uncertainty measures are partly inspired by exploration-focused reinforcement learning literature, UPER applies them with a different goal. One implication of this for instance, is that we do not necessarily expect significant improvements in exploration-heavy games like Montezuma’s Revenge. We appreciate the reviewer’s feedback and have added clarifications in the discussion and introduction sections, with further details on uncertainty estimation methods provided in Appendix A.

UPER can integrate with other reinforcement learning features, as it modifies only the priority variable for sampling transitions from the buffer. For instance, it could be combined with intrinsic motivation or other exploration techniques. However, we anticipate less effective results when combining UPER with categorical distribution methods like C51, Rainbow, or BBF. These methods tend to overestimate variance, require manually defined distribution support, and often concentrate probability mass in longer state trajectories (see Fig 2 in https://arxiv.org/abs/1902.08102). Besides, QR-DQN (https://arxiv.org/pdf/1710.10044) consistently performs better across various scenarios, and building a QR-DQN version of Rainbow is out of the scope of our work. Our experiments, spanning toy models, Atari benchmarks, and ablation studies in the appendix, focus on isolating the effect of the prioritization variable to confirm the contribution of using epistemic and aleatoric uncertainty for replay prioritization.

The estimators in UPER are derived from the total uncertainty defined in Equation 9, which measures the expected prediction error across quantiles and ensembles. While prior work (Clements et al., 2020) used prediction variance as total uncertainty, our approach considers expected prediction error instead. This adds a term to the epistemic uncertainty, akin to the commonly used TD error, capturing both the deviation from the target and ensemble disagreement. Our extension, termed target epistemic uncertainty in Equation 9, is crucial for effectively prioritizing transitions in the replay buffer. Appendix D includes extensive ablation studies on this term and alternative prioritization methods.

We are eager to engage in further discussion and address any additional questions or feedback.

Thank you.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733275749931

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Additional Atari Results for UPER

comment:
We thank the reviewers for their time and effort evaluating our work. While we do not fully agree (for various reasons outlined in the individual discussions), we understand the reviewers’ contention that the value of our work would be greater if we can demonstrate the effectiveness of UPER on multiple models. To the best of our understanding this represents the only significant remaining concern among the reviewers. The extended rebuttal period has allowed us to implement and evaluate UPER on an additional distributional algorithm, C51. Our results robustly show that UPER outperforms PER (on 5/6 Atari games we tested, with equal performance on the sixth—over 2 seeds). Since we can no longer update the manuscript, we have added the plots to [this anonymous link](https://www.dropbox.com/scl/fi/ssvqvoh3j9294hncfkqn7/c51_uper.pdf?rlkey=m9o5mqy8iu6fy157ass6egn9s&dl=0)—we will format these plots properly and add them to future manuscript versions; note that not all runs were able to finish fully. Despite initial concerns about variance over-estimation in categorical representations, UPER still finds a good trade-off between epistemic and aleatoric uncertainty estimates for effective use as a prioritization criterion. We think these results add significant support for our proposed method and consequently improve our paper overall; we thank the reviewers for encouraging this direction. We hope the reviewers appreciate the considerable effort we have put in to address their concerns, especially in producing additional Atari results, and will re-consider their scores accordingly.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studied uncertainty priorized experience replay where they use epstimic uncertainty to prioritize the samples in the replay buffer. The authors demonstrated the efficacy of their approach using QR-DQN and C51 as the underlying distributional RL optimizers. 

The main weaknesses identified by reviewers are lack of sufficient comparison to prior works that use different strategies for prioritized experience replay. The reviewers also concerned about the approach's applicability to other RL algorithms.