Deep Exploration with PAC-Bayes

Edit: Fixed a typo

Thank you for reviewing our submission and the provided feedback.

• Why does PBAC outperform baselines in the environments where it does? Why doesn't it see a similar improvement for the other benchmarks The only two environments where PBAC does not perform as well as or better than the baselines are humanoid in both performance metrics and reacher in the area under learning curve. For humanoid, we hypothesize that this is due to the very high health reward the agent receives (5x as large as in the other dense environments). For reacher, while the difference is statistically significant, it is still very small in absolute reward.

• I think it would be good to see some other common exploration benchmarks.
  Based upon the suggestion of reviewer v8fi, we are currently running experiments on various Meta-World environments and will update the general answer with those results once they are ready. Would you require further benchmarks?

• Can you give more intuition for how to interpret the positional delay parameter? How many timesteps does it take for the agent to reach these distances?
  The forward reward in MuJoCo environments depends on an agent's movement as measured in changes of the $x$ coordinate (See the gymnasium documentation for specifics on each environment). The delay parameter $c$ enforces that the agent only receives this reward if it has moved a distance of 1 or 2 from its starting position. As the hopper agent can fall over more easily, and thus end its episode, than an ant agent, we chose the required distance for the latter to be higher. See also Section B.2.1 for further details. As the humanoid environment is even more complex, even removing the health reward causes the baselines to fail. Further adding a positional delay restriction on the forward reward makes learning practically impossible.

• How are hyperparameters tuned for comparison algorithms?
  To stay close to each other, all methods share the same optimizer and architectural backbone. BootDQN-P and PBAC contain several extra hyperparameters, summarized in Tables 4 & 7. Note that most of these parameters are constant throughout the experiments, i.e., the methods tend to be robust to them. REDQ does not contain any extra hyperparameters that require tuning on top of the shared ones. BEN's hyperparameters are also all shared apart from a similar bootstrap rate parameter which we kept fixed throughout after preliminary results showed it to be robust against it. Finally, for DRND the $\alpha$ scaling parameter from SAC is optimized via gradient descent during training. Its main distinction from the other baselines and our proposal is its predictive network. As a large search over potential architectures for each environment would have been too costly, we followed the choices of the original authors, who kept them constant on a wide array of experiments indicating their robustness.

• Why does your method perform better on the sparse version of humanoid than the original?
  As discussed in the conclusion, the high health reward (five times higher than in the other two MuJoCo environments) means that our method with its focus on exploration is unlikely to be able to compete. However, as soon as this health reward is dropped, the very sparse reward signal requires a powerful exploration method.

We hope that these answers clarify your concerns. Please let us know if there are further points that should be discussed.

Dear reviewer,
As the discussion period will soon end, we are contacting you to double-check whether our answers resolved the concerns and questions you raised during your rebuttal. Due to the cross-discipline nature of our submission, i.e., the combination of PAC-Bayesian with RL approaches, we want to ensure that any potential communication gap that seems to be reflected in your low confidence score can be overcome.
Please let us know if we can provide further details and clarification.

Thank you for the detailed review of our submission.

• In dense reward environments random exploration performs as well or better.
  That is to be expected. If the reward structure is dense, a method build for deep exploration looses its distinguishing feature. This is indeed the main motivation for performing deep exploration. See, e.g., the discussion in Osband et al. (2016a).

• The method lacks convergence guarantees, limiting confidence in its stability and long-term performance across diverse tasks.
  We acknowledge that we do not provide a theoretical convergence guarantee. Note, that neither does $Q$-learning for continuous state-action spaces, and consequently any deep actor-critic method. All guarantees assume finite state space size. See for instance Theorem 1 of the famous TD3 method proposed by Fujimoto et al. (2018) for a proof of convergence assuming a finite Markov decision process. Once these assumptions are made, it is trivial to show that our method has identical convergence profile to any other actor-critic approach.. Currently only empirical results are available for its long-term performance and stability. We are currently increasing the diversity of our experiments by running further experiments on the Meta-World testbed as you suggested.

• Looking at the results, particularly the reward plots and Figure 4, it seems that the complexity of this method outweighs its advantages. The performance improvements shown aren’t particularly impressive, and given the considerable complexity involved.
  We provide one-sided paired t-tests in the general answer above, which demonstrates significantly ($p<0.05$) improved performance for most experiments. Could you provide further details on where you see a considerable complexity? The final algorithm (Alg 1 on p23) can be implemented in a straight-forward manner that isn't more difficult than our reported baselines.

• I’m curious why the authors opted to modify Gym environments for sparse rewards. Sparse reward testbeds, such as Meta-World and D4RL, naturally simulate environments with sparse feedback.
  Thank you for the suggestion. We are now running additional experiments on Meta-World and will provide them in a general answer once they are ready. Our decision to report custom environments was due to our aim to provide a set of experiments of increasing sparsity which a clearly defined reward structure (see Sec B.2.1).

• Could you elaborate on the decision to present performance results in Table 1 using IQM scores rather than traditional reward plots?
  We do report the reward plots in Figure 2 and 4, which you also refer to in this review. Table 1 gives an additional concise scalar summary of these plots. Table 1(a) summarizes the results at the end of training, i.e., the end of each reward plot, while Table 1(b) summarizes the overall learning trajectory by computing its area under curve. We consider both, tabular and graphical presentation as important. The decision to include only a subset of the reward plots in the main text was only due to space restrictions. Could you clarify the question?

We hope that this clarifies the concerns raised in this review. If there are further questions, please let us know.

Fujimoto et al. 2018., Addressing function approximation error in actor-critic methods

Dear reviewer,
As the discussion period will soon end, we are contacting you to double-check whether our answers resolved the concerns and questions you raised during your rebuttal. Due to the cross-discipline nature of our submission, i.e., the combination of PAC-Bayesian with RL approaches, we want to ensure that any potential communication gap that seems to be reflected in your low confidence score can be overcome.
Please let us know if we can provide further details and clarification.

Thank you for your review. We will answer to each of your points below.

• The algorithm requires "a series of approximations [...] which are well described in the paper but strike me as somewhat complicated and ad-hoc
  Could you point to the specific approximations that seem ad-hoc? We could then offer further details and justification. In Section 3.2, the first and second steps in moving the ensemble to a function space are justified by a growing trend in the Bayesian deep-learning literature to switch from weight-space priors to function-space priors. See, e.g., Papamarkou et al. (2024) and the justifications therein. Data-informed priors (Step 3) are well-known in the PAC-Bayesian literature, and bootstrapping (Step 6) was evaluated at length by Osband et al. (2016a,1018). The remaining two (Steps 4 and 5) are indeed primarily motivated by empirical results and numerical stability. Our proposed model is not decomposable and individual effects wouldn't be visible. However, if you have a specific factor in mind that should be observed in isolation, we are happy to conduct such an experiment.

• How easy would it be to reproduce and build on top of it?
  We provide a full pseudo-code version of the final algorithm in Algorithm 1 (see p 23), which together with the provided hyperparameters, architectural details, and a public pytorch implementation (currently hidden to keep anonymity) of the experimental pipeline ensure reproducibility of our reported results. The required critic ensemble and multi-headed actor network described in Table 6 are straightforward and the loss objective consists mainly of moment computations and their predictive mean-squared error terms, i.e., is comparable to our baselines.

• The empirical results still only consider fairly low-dimensional domains and no vision-based policies/critics. What about more expressive function approximator classes such as using transformers or other large models? Humanoid and ant both already provide a rather large observation space compared to other benchmarks (348 and 105 dimensions respectively). PBAC and the baselines share the same architectural backbone to stay as comparable as possible. Architectural advancements such as transformers, or layers adapted for spatial information, such as convolutional layers, would have to be shared with the baselines, after which we expect that the relative performance structure remains the same. Note that while the architectures are seemingly simple they already follow the latest recommendations from a recent study by Nauman et al. (2024). Of course, depending on the use case more powerful approximators, or newer ensembling methods, could directly replace the current backbone. As such the model could also be applied to vision-based benchmarks or similar. Our implementation is agnostic to such details. We would also like to remind, that the focus of this paper is on continuous control where the true bottleneck is the action space dimensionality rather than the observation space. Deep exploration in continuous control is far from being solved even from small action spaces. Hence, we leave scaling to future work.

• I could not fully understand how the treatment still captures the uncertainty over the full trajectory space
  The critic network approximates the value function, which is a predictor for the discounted return of a trajectory starting from a given state and generated by following a fixed policy. Hence, an uncertainty on the value of a state given as an input directly models the uncertainty over the value whole trajectory following that state. Does this clarify the question?

Please let us know in case these answers have not fully clarified your concerns and questions.

Papamarkou et al., 2024: Position: Bayesian Deep Learning is Needed in the Age of Large-Scale AI

Dear reviewer,
As the discussion period will soon end, we are contacting you to double-check whether our answers resolved the concerns and questions you raised during your rebuttal. Due to the cross-discipline nature of our submission, i.e., the combination of PAC-Bayesian with RL approaches, we want to ensure that any potential communication gap that seems to be reflected in your low confidence score can be overcome.
Please let us know if we can provide further details and clarification.

Thank you for reviewing our submission and for your comments.

• W1. The main theoretical result is vacuous.
  Indeed, the PAC-Bayes bound is, as discussed in the paper, vacuous. Its motivation is to serve as a training objective as is commonly done in PAC-Bayesian learning. Note that there is no relation between whether the bound is tight and whether it is a suitable training objective. If a non-vacuous generalization bound is desired at a later stage, the inferred posterior can be plugged into any tight PAC-Bayesian bound. The $\frac{nR^2}{(1 - \gamma)^2}$ which we introduce in the proof of Theorem 2 (line 851) is independent of the parameters, i.e., is irrelevant in the training process.

• W2. The experimental evaluation is limited

  • Regarding the limited set of results, we are currently running experiments on the Meta-World (Yu et al., 2019) benchmark, as suggested by reviewer v8fi. We will report these results as a main answer to all reviewers once they are completed.
  • Regarding the significance. See the general answer for a pairwise one-sided t-test analysis of the results reported in Table 1. Please note that even in the currently reported way of highlighting every method whose interquartile range overlaps, we get the following ranking, which clearly shows the average improvement of PBAC upon the baselines (the brackets provide the number of overlaps with the highest IQM range).
    • Final episode reward: DRND(1), BootDQN-P(3), BEN(4), REDQ (8), and PBAC (10)
    • Area under learning curve: BootDQN-P (0), DRND (1), BEN (1), REDQ (5), and PBAC (8)

• W3. Writing of the paper and overall storyline

  • "Apply PAC-Bayes analysis [...] to induce exploration in a USB-like manner"
    We essentially do posterior sampling, which is nowadays emerging as an alternative to UCB. The idea is to sample a value function from the learned posterior and act greedily with respect to it. There exist theoretical findings showing that posterior sampling is more sample-efficient than UCB (see, e.g., Tiapkin et al., 2022).
  • What does "Implement the bound" mean?
    Throughout this work, we follow the common practice of designing a PAC-Bayesian bound that is subsequently used as a training objective to be minimized. The expression implementing the bound means that we derive in Section 3.2 an approximation to the theoretical bound we proved in Theorem 2. This approximation finally provides us the loss term given by equation (3) which is subsequently minimized as described in Algorithm 1.
  • Line 266: It was not clear to me why a function is replaced by a distribution here.
    We do this to capture the randomness caused by the function approximation error resulting from the approximate TD approach. Standard actor-critic methods use double critics and min-clipping to overcome the negative effects of this error. Our novelty is to model the distribution caused by this error and use the resulting uncertainty for deep exploration.
  • It was difficult to parse what the final algorithm actually is.
    We described the final algorithm in Algorithm 1 in the appendix (see p23) which implements equation (3). We aim to explain every step in Section 3.2. Could you tell which of these steps is unclear or not sufficiently justified? Does the algorithm make the specific steps clearer, or would a further explanation be helpful?

• W4. Another paper that would be good to compare against is Sunrise.
  Thank you for the reference, we will add it to our related work section. SUNRISE (Lee et al., 2021) uses an ensemble of actor critic nets in a SAC setup and weights the Bellman error by the empirical standard deviation of their predictions. Additionally, they rely on a bootstrapping mask, as do we, and perform UCB-based exploration. Their target can be interpreted as roughly corresponding to a weighted version of the first term in our objective in Equation (3).

Please let us know whether these answers clarify your questions or whether you have further requests or additional questions.

Lee et al., 2021: SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning
Tiapkin et al., 2022: Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees_Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees

Dear reviewer,
As the discussion period will soon end, we are contacting you to double-check whether our answers resolved the concerns and questions you raised during your rebuttal. Due to the cross-discipline nature of our submission, i.e., the combination of PAC-Bayesian with RL approaches, we want to ensure that any potential communication gap that seems to be reflected in your low confidence score can be overcome.
Please let us know if we can provide further details and clarification.

We agree with the difficulties the vacuousness of the bound creates in interpreting our contribution. It is easily fixable by minor changes in the manuscript following the recipe below.

The vacuousness stems from the worst-case upper bound we build on the term:

in Line 848 of the proof of Theorem 2. Define $\lambda_t \in [0,1]$ as the operator norm of the state transition kernel $P_{\pi_t}(s_{t+1}|s_t, \pi_t(s_t))$ employed during the construction of the replay buffer at environment interaction time $t$. Then defining a non-stationary Markov chain on the sample Bellman operator error $(\tilde T_{\pi_t} Q(s_t,a_t,s_{t+1}) - Q(s_t, a_t))$ and applying Theorem 5 of Fan et al. (2021) with a trivial union bound argument on two alternative orders of the random variable and its expectation (as standard in the Hoeffding inequality variants) as well as few small algebraic manipulations we attain

Plugging this result into Line 848 of our submission with further few small steps yields the following inequality

$E_{X \sim \rho} ||Q_\pi - X||^2_{P_\pi} \leq \frac{1}{(1-\gamma)^2} \Bigg ( \hat L_D(\rho) + \frac{1}{n} \Big [ KL(\rho || \rho_0) + \log \frac{1}{\delta} + \frac{(1+\max_{t \in [n]} \lambda_t)R}{(1-\max_{t \in [n]} \lambda_t) 8} \Big ] \Bigg )- \gamma^2 E_{X \sim \rho} var_{s \sim P_\pi}[X(s,\pi(s))]$.

We will replace it with Eq. (2) of the current version of our manuscript. Although calculating $\lambda_t$'s is not practical for many MDPs, the term it appears in the bound does not depend on the posterior distribution, hence it boils down to constant in the policy evaluation step. Hence, all the rest of our argumentation, algorithm, and experiment results remain valid.

Does this address your concern?

Fan et al., 2021: Hoeffding's Inequality for General Markov Chains and Its Applications to Statistical Learning, JMLR, 2021

We provide a first set of results on five sparse environments, comparing PBAC with REDQ, our strongest baseline in the original submission. We follow Fu et al. (2024)'s sparse experimental setup, where an agent only receives a reward upon task completion, e.g., when it successfully opens a window, without any intermediary reward. As our computational resources are limited during this rebuttal, we consider a task to be solved after the agent has received a success rate of 100% for two consecutive evaluation episodes. We will provide success curves over a longer run of 1e6 environmental steps in the camera-ready version. We report the average number of steps needed over three seeds. The * indicates that PBAC failed in one of the seeds and that the reported average is over the remaining two.

In four out of the five tasks, PBAC is clearly better than REDQ. Only on drawer_open_goal_hidden does it perform worse.
Note that these results are without hyperparameter tuning, i.e., using the default parameters we reported in our paper. We expect these numbers to improve further with tuned hyperparameters.

The remaining three baselines reported in our paper are currently training and we will update the table once they are ready. Preliminary results indicate that all three perform worse.

Fu et al., 2024: FuRL: Visual-Language Models as Fuzzy Rewards for Reinforcement Learning
Yu et al., 2019: Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning