Value Bonuses using Ensemble Errors for Exploration in Reinforcement Learning

“a more impactful study would involve challenging and widely recognized hard-exploration tasks”

The environments we chose in our experiments was to make sure that we have a balanced mix of hard exploration environments and relatively simpler environments. The reason is because we wanted to present an algorithm that does well in general rather than just on hard exploration problems. In this context, it is note-worthy that existing literature highlights that focusing only on hard-exploration problems while evaluating exploration algorithms can lead to a very skewed view of their general efficacy [14].

The environments we chose are pretty standard to test exploration capabilities of RL agents and have previously been used in many studies. Riverswim [1, 2, 3, 4] with a continuous state-space and noisy transitions is a continuing environment. It is a hard exploration environment as the agent starts near the sub-optimal reward and the probability of getting to the optimal reward state is low. Puddle-World [1] tests the agent’s ability to effectively explore the environment even in the presence of high magnitude negative reward for stepping inside the puddles. The agent not only has to find the shortest path to the goal but also has to learn to avoid going inside the puddles. Sparse Mountain Car [1, 3] is a variant of the classic Mountain Car environment, and highlights the difficulty of learning a good policy in absence of a dense reward. DeepSea [3,5,6,7,8] is widely regarded as a hard exploration environment as there exists only one correct path towards the goal state and throughout this path the agent receives a penalty up till the very end. A random exploration strategy would need exponential samples O(2^-N) to reach the goal state. For Atari we also chose a mix set of hard exploration environments like: Gravitar, Pitfall, Privateeye [9,10,11], and the remaining Breakout, Pong and Qbert [11, 12] were selected to test the ability of VBE and baseline agents on relatively simpler environments.

“The comparison between different RL algorithms (DDQN, PPO) under such limited environment interaction raises concerns about the fairness of the evaluation. It remains unclear whether the observed learning curve superiority of VBE after 50k steps is due to DDQN's known sample efficiency compared to PPO. ”

As mentioned below, we used the code released for ACB/RND, which uses PPO in Atari, precisely because we wanted to fairly compare to an implementation that was well-developed by those authors. We do, however, completely agree that the idea is separable from PPO and can and should be tested within DDQN. This is why we did just that in the more controlled experiments (rather than Atari, where we wanted to compare to known baselines). In Section 5.5 we evaluate ACB and RND with DDQN instead of PPO. We use the exact same base algorithm as used for VBE to test ACB and RND’s bonus. We also test these DDQN variants of ACB and RND in the pure exploration experiment, and highlight that even with DDQN implementation these reward bonus strategies fail to cover the state-space because of their limitation to provide first-visit optimism.

“I appreciate the authors' effort in providing the reference codebase for implementing the RND and ACB baselines. However, I am not convinced about the effectiveness of this particular implementation, given the limited popularity of the codebase.”

The codebase we used for ACB and RND is the one written by the authors of the ACB paper [11]. The codebase is built on top of [13] which is a much more popular and widely used implementation of RND. We also made sure that the implementation was sound and used the parameters originally proposed.

“I am curious about the author's choice to allocate computational resources to run 30 different experiments”

Our goal in exploration is to improve sample efficiency, as directed exploration should result in the agent learning with fewer samples. It is sensible, therefore, to examine early learning to gauge this sample efficiency. Testing exploration algorithms under a fixed budget is also a common experiment setup [1, 3, 5, 7, 8]. About computation, when using clusters to run experiments, it is straightforward to schedule more jobs to get more runs, since they run in parallel. Each job runs in a more reasonable amount of time than a much longer experiment, and allows for iteration on the results to better understand the methods. Also, doing 30 runs with random seeds lead to more statistically significant results.

“Environments involving 3D navigation or procedurally generated maps ”

As stated above the environments we chose in our experiments are pretty standard to test exploration capabilities of RL agents. However, this is a nice suggestion and can be considered for future work.

We hope these responses resolve your concerns, and would be happy to hear any other specific issues with the experimental setup. Thank you for your review and input.

We thank the reviewer for a detailed review of our work and the useful suggestions. We have incorporated the fixes in the minor comments and a few other fixes based on the other comments. We address the questions you have raised below.

The Atari experiments are actually run for 4 Million frames instead of 400K. The notation 1e6 is meant to demonstrate 10^6, we will make this more clear in the updated paper.

RND and ACB are much more expensive than VBE and take a lot longer to run. But, we are currently completing results for these algorithms for 10 Million frames and will update the paper with these complete results.

You bring up a reasonable point about the worse performance of VBE in Pitfall and Gravitar. In Pitfall our understanding is that VBE takes longer to converge to the policy of always going left in Pitfall, as the agent still tries to explore novel states. In Figure 7 in the Appendix, both variants of VBE continue to improve in Pitfall after 4 Million frames. VBE-CNN fully converges to the policy of always going left and outperforms all baselines.

For Gravitar, both ACB and RND start off at a better policy than VBE. This may be due to different architectures, since ACB and RND use PPO, since that is originally how they were specified. We cannot say for sure, of course, but could put some discussion on our speculations and label them clearly as speculations (One of the reasons we chose to do a more careful study in classic control environments is precisely because we can better understand the algorithms.) It is interesting to note, though, that VBE does slowly improve, whereas ACB/RND do not. This is especially evident in Figure 7 in Appendix where both variants of VBE continue to improve beyond 4 Million frames and eventually arrive at a similar mean performance to ACB/RND in Gravitar.

We did not include Montezuma’s Revenge because initial experiments indicated no baseline does well in this environment within the given frame budget (also reported in [6]). It is note-worthy that [6] also characterizes Montezuma’s Revenge as obfuscating the exploration abilities of reward-bonus based exploration methods. In the original RND work, the agent gets to use multiple parallel copies of the environment and sees much more frames (as the reviewer correctly points out), which is much much more interaction. For the sparse reward setting, we do have Sparse Mountain Car, which we have found to be surprisingly challenging for deep RL agents and actually highlights differences between methods. We will keep Antmaze in mind for future work!

For Algorithm1, we can see how it was unclear how we updated q_w. Line 10 says we update using Equation 1, with the comment in line 9 saying this update is the action-values without explicitly mentioning q_w. We will fix this and update the paper soon. The q_w is updated using the standard DDQN update using the environment reward (namely, Equation 1), with no change from the DDQN update. The primary change is the behavior policy, which now uses value bonuses, and how we update the ensemble to define the value bonus.

Riverswim and Deepsea [1, 2, 3, 4 ,5] are considered hard exploration environments, and are commonly used in literature to test exploration algorithms.

References:

[1] Kumaraswamy, R., Schlegel, M., White, A., & White, M. (2018). Context-dependent upper-confidence bounds for directed exploration. Advances in Neural Information Processing Systems, 31.

[2] Ishfaq, H., Cui, Q., Nguyen, V., Ayoub, A., Yang, Z., Wang, Z., ... & Yang, L. (2021, July). Randomized exploration in reinforcement learning with general value function approximation. In International Conference on Machine Learning (pp. 4607-4616). PMLR.

[3] Osband, I., Doron, Y., Hessel, M., Aslanides, J., Sezener, E., Saraiva, A., ... & Van Hasselt, H. (2019). Behaviour suite for reinforcement learning. arXiv preprint arXiv:1908.03568.

[4] Ian Osband, John Aslanides, and Albin Cassirer. Randomized Prior Functions for Deep Reinforcement Learning. NeurIPS, 2018.

[5] Ian Osband, Benjamin Van Roy, Daniel J Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20(124):1–62, 2019.

[6] Taiga, A. A., Fedus, W., Machado, M. C., Courville, A., & Bellemare, M. G. (2021). On bonus-based exploration methods in the arcade learning environment. arXiv preprint arXiv:2109.11052.

We thank the reviewer for their review, and appreciate suggestions to make the work clearer, since we are always striving to present the idea in the simplest way possible. We agree with the reviewer that our proposed methodology is an extension of UCB-style exploration methods to the RL setting. However, our proposed methodology is novel and different from existing attempts to extend UCB to the RL setting – which we refer to as reward bonus methods – like count-based methods, RND, ACB, ICM, etc. We will attempt to further highlight this distinction here. First, it is important to note that UCB-style exploration methods originate from the bandit literature, where the agent maintains and updates its reward estimates for each arm and UCB-based exploration methods provide reward bonuses to encourage selecting arms with higher uncertainty. In RL, an agent maintains and updates its value estimates to determine its behavior policy, thus an exploration bonus is required in the value space to encourage visiting uncertain states. The existing algorithms that attempt to extend such UCB-style exploration methods to the RL setting first approximate a reward bonus using counts, density-based counts, prediction errors [RND, ACB, ICM], etc., and then propagate these reward bonuses (or local estimates of uncertainty) either by adding this reward bonus to the environment reward or by updating a separate value function as in RND, ACB. These existing reward bonus methods attempt to extend UCB-style methods to RL by doing two steps: 1- approximating reward bonus or local uncertainty via supervised learning or self-supervised learning, 2- propagating these reward bonuses, say using TD-learning.

Our proposed method VBE attempts to extend UCB-style methods to the RL setting by directly approximating bonuses in the value space (or value bonuses). It avoids the two step process of reward bonus approaches, that require estimating local uncertainties and then propagating. VBE directly updates the value functions in the ensemble to get a value bonus. Further, directly defining the bonuses in the value space provides first-visit optimism, which the existing reward bonus methods fail to provide. This is evident from our pure exploration experiment in Section-5.3 and Figure-1.

To further understand how our value bonus method provides optimism by implicitly conserving uncertainty in the value estimates consider this example: Consider the following transition sequence: $(s, a, s’, a’)$, $f_{rqf}(s,a)$ is the predictor RQF, $f_{trg}(s,a)$ is the target RQF, and reward function for the predictor RQF is defined as $r_{rqf}(s,a,s',a') = f_{trg}(s,a) - \gamma f_{trg}(s',a')$ (Equation-3). Now suppose that the state-action pair $(s’,a’)$ has been less frequently visited and thus has high prediction error. This would mean that the error or the $bonus(s’,a’) = |f_{rqf}(s’,a’) - f_{trg}(s’,a’)|$ would be high, but how does this high uncertainty affect $bonus(s,a)$? Notice that we update $f_{rqf}(s,a)$ by bootstrapping the prediction value of $f_{rqf}(s’,a’)$ (TD learning update), that is the target for $f_{rqf}(s,a)$ is $r_{rqf}(s,a,s’,a’) + \gamma f_{rqf}(s’,a’)$. This bootstrap target can only be the “true target”, $f_{trg}(s,a)$ if $\gamma f_{rqf}(s’,a’) == \gamma f_{trg}(s’,a’)$, that is $f_{rqf}(s’,a’)$ is error-free. This means that prediction error for $(s,a)$ or the $bonus(s,a)$ will only go down to zero when the prediction error for all subsequent state-action pairs is zero. Proposition 1 reflects this property.

Connection to BDQN explained: BDQN is not a UCB-style exploration method, rather BDQN aims to approximate Thompson Sampling for exploration in RL. The ensemble in BDQN aims to approximate the posterior distribution over action-value functions. Statistical bootstrapping alone however can only approximate the epistemic uncertainty of observed state-action pairs as noted in [1]. Adding a fixed additive prior can provide the first-visit optimism. Notice this explanation from the BDQN paper “The crucial element is that when a new state s’ is reached there is some ensemble member that estimates $\max_{a’} Q_{k}(s’, a’)$ is sufficiently positive to warrant visiting, even if it causes some negative reward along the way” [1]. The ensemble in BDQN is thus responsible for approximating the posterior distribution and providing first-visit optimism.

VBE on the other hand is less sensitive to the size of its ensemble. This is especially prominent from Table-1 in Appendix B which shows that in the pure exploration experiment (Section-5.3, Figure-1) VBE only requires 1 RQF to cover the entire state-space for all grid-sizes, whereas BDQN requires 20 heads in the ensemble and still does not manage to cover the state-space for grid-sizes bigger than 35x35. This further highlights the efficacy of VBE over BDQN as it requires smaller ensembles even on hard exploration tasks and also highlights the difference in usage of the ensemble.

We thank the reviewer for their time and review and hope to address the points raised. The primary concern seems to be that this contribution is marginal, but we believe there was a misunderstanding about what our approach does and how it differs from previous work. There is no doubt that there are many approaches trying to extend UCB-style exploration to RL, namely those trying to estimate uncertainty and taking actions according to approximate upper confidence bounds. The many reward bonus approaches can absolutely be seen to do this, as we point out in the introduction. We say “One simple approach is to separate out the reward bonuses and learn them with a second value function, as was proposed for RND (Burda et al., 2019) and later adopted by ACB (Ash et al., 2022). This approach, however, still suffers from the fact that reward bonuses are only retroactive, and the resulting b is unlikely to be high for unvisited states and actions.” We demonstrate this in the pure exploration experiment Section-5.3, Figure-1, where the reward bonus methods fail to cover the state space as these methods do not encourage visiting novel states.

The reviewer mentions several reward bonus methods like RND, ICM, which aim to extend UCB-style exploration methods to the RL setting. We will further try to clarify the difference between our approach and existing reward bonus methods here. RND uses a fixed randomly initialized network to define the target for a state, and a separate prediction network is trained to predict that target using a standard supervised learning MSE loss. The reward bonus for a state is defined as the prediction error for that state. This reward bonus can not be directly used to alter the agent’s behavior as the prediction error only approximates local epistemic uncertainty. To do directed deep exploration RND uses this bonus as a reward to update a separate value function to propagate local uncertainties to earlier states. Now, since we have the uncertainty in value space, the agent’s behavior can be altered to do deep exploration. Most reward bonus methods follow this exact principle, with the difference being in how local uncertainties are estimated. For example, ACB uses stochastic targets and the bonus is defined as the maximum deviation from the mean over an ensemble. ICM uses prediction errors in the forward dynamics model. All such reward bonus methods use a two-step process, 1- measure local uncertainties (prediction errors, counts, variance, etc.), 2- propagate local uncertainties to get the value bonus (uncertainty estimate in value space).

Our proposed methodology is different from these reward bonus methods in that it aims to approximate the value bonus directly in one step, by updating the RQFs using the reward function defined for each RQF (Equation-3) and measuring the error in predictions w.r.t. true target RQFs. In doing so we also solve the problem of first-visit optimism which is a known problem with reward bonus methods.

The other claim is around theoretical analysis. To the best of our knowledge, there is very little theory in deep RL for upper confidence bound approaches (and value bonus approaches). The reviewer states that [1] has theory on this topic, but that work is focused on empirically understanding a proposed intrinsic reward (reward bonus). As mentioned above, such reward bonus methods fail to incorporate first visit optimism, as the intrinsic reward only affects the value function after visiting a state-action pair. The paper [3] proposes OPPO, an optimistic version of PPO. It is important to note that this methodology and the theory is only applicable in the fixed horizon, linear approximation setting. Extending this theory to the deep RL setting, for episodic problems that have variable length episodes, remains an open question. We did cite several theory works in the introduction; we will include this paper in that list.

When we say our bonuses go to zero by design, we are not saying that other UCB-style algorithms have bonuses that do not go to zero. We are simply pointing out that this desirable property is also a property of our algorithm.