Augmented Bayesian Policy Search
Authors: Mahdi Kallel
Debabrota Basu
Riad Akrour
Carlo D'Eramo
Venue: ICLR 2024 poster (2024)
Keywords: Reinforcement learning
Policy search
Bayesian optimization
Gaussian Processes
Primary area: reinforcement learning
TL;DR: A novel mean function for Gaussian processes that bridges the gap between reinforcement learning and Bayesian optimization (BO) by leveraging the performance difference lemma to augment BO schemes with an action-value function.

Abstract: Deterministic policies are often preferred over stochastic ones when implemented on physical systems. They can prevent erratic and harmful behaviors while being easier to implement and interpret. However, in practice, exploration is largely performed by stochastic policies.
First-order Bayesian Optimization (BO) methods offer a principled way of performing exploration using deterministic policies. This is done through a learned probabilistic model of the objective function and its gradient. Nonetheless, such approaches treat policy search as a black-box problem, and thus, neglect the reinforcement learning nature of the problem. In this work, we leverage the performance difference lemma to introduce a novel mean function for the probabilistic model. This results in augmenting BO methods with the action-value function. Hence, we call our method Augmented Bayesian Search (ABS).
Interestingly, this new mean function enhances the posterior gradient with the deterministic policy gradient, effectively bridging the gap between BO and policy gradient methods. The resulting algorithm combines the convenience of the direct policy search with the scalability of reinforcement learning.
We validate ABS on high-dimensional locomotion problems and demonstrate competitive performance compared to existing direct policy search schemes.

Published as a conference paper at ICLR 2024
AUGMENTED BAYESIAN POLICY SEARCH
Mahdi K Debabrota Basu², Riad Akrour?, Carlo D'Eramo 1,31
Center for Artificial Intelligence and Data Science, University of Würzburg, Germany Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, Lille, France dDepartment of Computer Science, TU Darmstadt, Germany *Hessian Center for Artificial Intelligence (Hessian.ai), Germany
ABSTRACT
Deterministic policies are often preferred over stochastic ones when implemented physical systems. They can prevent erratic and harmful behaviors while be- ing easier to implement and interpret. However, in practice, exploration is largely performed by stochastic policies. First-order Bayesian Optimization (BO) meth- ods offer a principled way of performing exploration using deterministic poli- cies. This is done through learned probabilistic model of the objective function and its gradient. Nonetheless, such approaches treat policy search as a black- box problem, and thus, neglect the reinforcement learning nature of the problem. In this work, we leverage the performance difference lemma to introduce novel mean function for the probabilistic model. This results in augmenting BO methods with the action-value function. Hence, we call our method Augmented Bayesian Search (ABS). Interestingly, this new mean function enhances the posterior gradi- ent with the deterministic policy gradient, effectively bridging the gap between BO and policy gradient methods. The resulting algorithm combines the convenience of the direct policy search with the scalability of reinforcement learning. We vali- date ABS on high-dimensional locomotion problems and demonstrate competitive performance compared to existing direct policy search schemes.
INTRODUCTION
The majority of policy gradient literature in Reinforcement Learning (RL), from traditional meth- ods (Sutton & Barto, 2018) to contemporary actor-critic strategies (Schulman al., 2017: 2015; Haarnoja et al.. 2018), employs stochastic policies for experience gathering. This is typically achieved either by modeling policies as probability distributions or by injecting noise into the ac- tions of deterministic policies (Lillicrap et al., 2015; Fujimoto et al., 2018). Having algorithm that explores effectively using only deterministic policies is preferable when these policies are de- ployed on physical systems like robotics. Indeed, deterministic policies can prevent the erratic and potentially damaging behavior of stochastic policies while being easier to implement and interpret.
To this end, Bayesian Optimization (BO) methods (Garnett, 2023) perform search directly in the parameter space. BO has emerged as powerful tool for the global optimization of black-box func- tions, demonstrating its effectiveness across diverse landscapes and practical applications. such as parameter tuning for machine learning algorithms (Turner et al., 2021; Cowen-
et al., 2022), robotics (Calandra et al., 2016; Muratore al., 2021), and RI. (Bruno et al., 2013). The strength of BO lies in its two core components: (i) a probabilistic model of the objective function, which usually takes the form of a Gaussian Process (GP) prior, and (ii) sampling procedure that ex- ploits this model to identify informative samples. However BO methods often struggle as the task dimensionality increases since they require a prohibitive number of samples build global model.
Local Bayesian Optimization provides an intriguing solution to this challenge (Akrour et al., 2017; Eriksson et al.. 2019: Wang al., 2020; Müller al., 2021; Nguyen et al., 2022). By focusing on specific regions within the search space, local BO improves the handling of the high-dimensional spaces by promoting more targeted exploration and exploitation, thus reducing the number of eval- uations needed to pinpoint optimal solutions. Consequently, there has been a recent upswing in
"Correspondence mahdi 1allel@un wwerzburg.de.

---

Published as a conference paper at ICLR 2024
efforts to scale BO high-dimensional problems through the design of local schemes. However, when applied to high-dimensional RL problems, these schemes fall short as they treat the policy search problem as black-box problem, and thus, use only the information of the policy return. By doing so, they overlook the sequential nature of MDPs and discard potentially useful experience.
In this paper, introduce a principled solution this problem by building novel RL-aware mean function to enhance local BO methods. We leverage the performance difference lemma to inject an action-value function into the GP prior of the objective function, thus, effectively incorporating knowledge of past trajectories into our belief about the return of untested policies. We provide further theoretical ground for our approach by deriving a new bound on the impact of altering deterministic policies on expected returns for Lipschitz MDPs. Then, we show that the posterior gradient yielded by using our new mean function, corresponds the deterministic policy gradient. Thus, it bridges the gap between BO approaches and policy gradient methods.
The primary contribution of this work novel mean function that enhances GPs with the action- value function. Additionally, we propose fitness-aware adaptive scheme for aggregating multiple Q-function approximators. Integrating these components into the Maximum Probability of De- scent (MPD) framework (Nguyen et al., 2022) leads to the development of the Augmented Bayesian Search (ABS) algorithm. ABS effectively unifies policy gradient and BO methods, capitalizing on the scalability and sample-efficiency of RL, while also leveraging the principled exploration and practicality offered by BO methods. We provide empirical evidence on the effectiveness of our novel mean function, demonstrating that ABS surpasses previous BO schemes in high-dimensional MuJoCO locomotion problems (Todorov et al., 2012).
2
PRELIMINARIES
2.1
REINFORCEMENT LEARNING
We consider Markov Decision Processes (MDPs) (Sutton & Barto, 2018) with a continuous bounded state space S C R", a continuous action space A S Rd stationary transition dynamics with conditional density p(s St. a4) satisfying the Markov property, an initial state distribution 4, reward function r S x A + R and a discount factor y. We denote by π S + A a deterministic policy mapping states into actions. Throughout this manuscript, we use only deterministic policies.
At each discrete time step f, from a given state E S, the agent takes an action a; = (s;), receiv- ing a reward r(sr, at) and the new state of the environment s' according to the dynamics p(,|s;, a.). We denote by P(s + s', x) the probability of being at state s' after t transitions following pol- icy starting from We also denote p% (s') Et= 7² P(s s,,t, the improper discounted state visitation density of s' starting from 8. By integrating over the initial state distribution i, we can deduce the improper discounted visitation measure d= (s')= .s P. (s')(s)dss
The action- value function Q" describes the expected return after taking action in the state and thereafter following policy i..., Q* & "e'pppaa==<(d [r(s', "'')aaaa)aa a]. Given the action- value function, we can derive the advantage function as A (s, a) A Q= a) (* π (s)). The goal of RL is to optimize a policy Te, parameterized by 0, with the goal of maximizing the expected discounted policy return J (TT)
[r(s, a)] Ee [QTH (s, (s))).
To this end, a popular class of RL methods, known as actor-critic, leverages an additional parametric approximation of the action-value function Q (Schulman et al., 2015; Haarooj al., 2018). When restricting actor-critic methods to deterministic policies, policy can be updated using the deterministic policy gradient, which changes its actions to maximize QTT (Silver et al., 2014):
(Te( Eg
VoQTM
VOTO(S)
a=mo(s)
2.2 INFORMATION MAXIMIZING BAYESTAN OPTIMIZATION
Bayesian Optimization (BO) is sequential method for global optimization of black-box functions when sample-effiiieny is paramount. It builds a probabilistic model of the objective function, often Gaussian Process (GP), which is used by acquisition function that guides the parameter
2

---

Published as a conference paper at ICLR 2024
space exploration. However, BO struggles with high-dimensional spaces as it requires a prohibitive amount of data to build a global model of the objective function. To address these issues, local BO methods have been developed (Nguyen et al., 2022; Müller et al., 2021; Eriksson et al., 2019; Fröhlich et al., 2021). These methods constrain the search to a subspace of interest, circumventing difficulty of modeling and finding promising candidates in high dimensional problems.
A recent development in the local BO methods is the introduction of Information Maximizing BO. First introduced by Müller al. (2021), and subsequently refined by Nguyen et al. (2022), these methods rely on an acquisition function that seeks to maximize a local measure of information. By considering a GP belief about the objective function J ~ GP (m (z), ) K (xx,²) with a differentiable mean function m and a wwic-difffereniabbl covariance function K. we have that the joint distribu- tion between the GP and its derivative is still GP (Rasmussen, 2003). Hence, by conditioning on a dataset of observations (X, Y), the posterior distribution of the derivative at point of interest 0 takes the form of a Gaussian distribution (0) 0, Y) = N N(e, Eg), where
Hg - V vm VxX Σg A (0,(0, (O, X) "XX,,)X))XXXXXXXXXXXXXX>
mm(x))
(2)
(3)
In Nguyen et al. (2022), the measure of information is taken to be the probability of descent at central point 0. Subsequently, an acquisition function (==10, X, Y) is developed to guide the explo- ration towards an acquisition point such that adding (z, U2) to our observation dataset maximizes the probability of descent at O. The resulting BO algorithm, named MPD (Nguyen et al., 2022), alternates between two steps. Starting from central point 0, it uses the acquisition function to sequentially query multiple acquisition points Z and observe their values yz until obtaining satisfy- ing information about f. Then, MPD uses the better-estimated gradient 140 move along the most probable descent direction 1/8 _ Σg ji9 to new point l', and repeats this loop.
3 REINFORCEMENT LEARNING-AWARE BAYESIAN OPTIMIZATION
The mean function of GP determines the expected value at given point. In interpolating regions, the posterior mean is largely influenced by observed data points due to significant correlation. Con- versely, in extrapolating regions, the data's influence is minimal, causing the posterior mean to revert to the mean function. Despite its importance, this function has received little attention in BO liter- ature, especially in RL applications where uninformative priors like constant functions are favored. In this section, we leverage the MDP properties of the problem to build a better mean function.
3.1 ON THE SMOOTHNESS OF DETERMINISTIC POLICY RETURNS
First, we develop a new bound on the impact of altering deterministic policies on expected returns in the particular case of Lipschitz MDPs (Pirotta et al., 2015). We assume that the implementation of a policy ze gives access to J J(TT), d and Q Given an alternative policy Ty our objective is to accurately estimate its return J (TT) The performance difference lemma (Kakade & Langford, 2002) can establish the relation between deterministic policies returns and the advantage function
J(mx) - [(T) = Rg-a+= [A** (s, (+))] (d (.), ATM (-,).
(4)
Direct application of this lemma to infer (TT)) is not feasible due to the need for d= However, by reordering terms, we can express policy return as an estimable term plus an unknown residual.
J (Tx)) J (TT) + (d ()) A (.)))
((d==
d ).), A (.. (.)))
(S)
Estimate
Residual
The following assumptions allow to bind the residual term while using deterministic policies. Assumption 3.1. An MDP is (I,, -ippschhh for all s E S and a' e A:
(r(s,a) r(si, a')l < L, (ds d' (oo((ls,)..(-1) d')) < (ds 8') (a)aaa))
'The findings of this section relevant to both parametric and non-paramtrric policies. Parametric nota- tions used for consistency throughout the paper.
3

---

Published as a conference paper at ICLR 2024
Assumption 3.2. A policy Tu is Lx Lipschitz for all s, E S
(s) Tx (s())) S L=(ds(s,)))).
Here, we denote by ds, d the distances in S and A respectively. In this work, we take this distance to be the Euclidean distance |I-II and W be the Wassertstein-2 distance on the space of measures.
Theorem 3.3. For an (Irr -Lipshhht MDP operating with deterministic --p-iipschitz policies, and y T + Ii=) < 1, we bound the residual term for any policies Va and a as
where C - 2yI. L.r (1 + I_,) (1-7Lp(1 + _x)
1(d= - d A (1 C. C'suup -==)))))=(())) (o)s,,,
(6)
The bound describes the worst-case value of the residual term. Theorem 3.3 extends the existing bounds the residual term (Kakade & Langford, 2002; Schulman et al., 2015) to setting, where both the policy and the dynamics are deterministic. Similarly, we extend this bound to the case of linear policies and bounded state spaces
ldd= o A (T)) C' sup || 0|1-
3.2 ADVANTAGE MEAN FUNCTION
Now, we construct GP that models the policy return J over the space of parameters of deterministic linear policies. To solve the policy search problem,
query oracle obtain noisy evalu- ation J(T)) (TT) + of any point x, an empirical estimate of its discounted state distribution d== d== and the transitions of the corresponding trajectory. In order to construct such a model, first, we roll out central point 0 and obtain estimates J(Ta) and dha Then, we train a deep neural network parameterized by & to estimate the action-value function Q% Q For any policy parameterized by x, if sup, ||=: 0|| is small enough, Theorem 3.3 and Equation (7) indicate that good prior on its return (Tz) is an estimate of the first term in Equation (5), i.c.
m (x) J(TT) + E Ey.iro (s.
(8)
Therefore, we advocate using M as a mean function for our GP, which we call Advantage Mean Function. We emphasize that the advantage mean function m. (z) for the policy return ((Tx) de- pends on the current central point 0. By using myg we leave the GP to model the residual term from Equation (5), which can be viewed as a second-order term (Saleh et al., 2022), and the errors due to empirical estimates and approximations. This is in contrast the typical constant mean function, which forces the GP to fit all the variations of the objective function. By plugging in the advantage mean function in the posterior of the derivative pso (Equation (2)), we unravel interesting property. Corollary 3.3.1. Given the mean function mo the mean of the gradient posterior at 8 is
150 = E amitr VaQ (s,
VOTO(S) + VoK(O, K(X, X(Xxx))+(((( mx)))) (9)
a=a(()
where X & {21,22,-. 22, 2a,.......... servations, J(X) = (J(TT) ), (TZZ)..... denotes the set of their noisy policy evaluations, and mx(X)= (21). (2) ...} denotes the mean function estimate of their policy return.
(01,02,.... denotes the set of policy parameters of the past ob-
The mean of the gradient posterior, 14g takes the form of the Deterministic Policy Gradient (Silver al., 2014), corrected by factor that is proportional to the alignment of the advantage mean function with the observed data points. Given that our objective function is the policy return, the mean of the gradient posterior aims to get a closer correspondence with the actual deterministic policy gradient, as compared to the estimate obtained by using only the estimator Q
In Figure 1, we demonstrate the behavior of the acquisition function of MPD (Nguyen et al., 2022). We observe its tendency to keep the acquisition points in the immediate vicinity of the central point d effectively controlling 2| Ø|| and therefore the residual term of Equation (5). In conclu- sion, the proposed mean function mn integrates both zero-order (returns) and first-order (gradient) observations into the BO framework, as hypothesized in (Müller et al., 2021), thereby seamlessly bridging the gap between policy gradient and Bayesian Optimization methods.
4

---

Published as a conference paper at ICLR 2024
0.4
0.2
0.02
0.00
00
805
-0.0
0.00
-002
-0.04
-0.0
00.4
0.02
0.00
(a) f 0: Observed only 0 (star)
(b) t = 1: Observed 0, 21 (white) (c) = 2: Observed 0, 21, 22 (white)
Figure 1: Behavior of the acquisition function of MPD (Nguyen et al., 2022) augmented with the advantage mean function (Equation (8)). The maximum of the acquisition function (blue dot) lies in the direction of the mean of the gradient posterior 0 (star), i.e. po (violet line). The posterior cor- rects the mean gradient Vams (pink line) when the mean function my does not fit the observations.
ENHANCING Q-FUNCTION ESTIMATORS: EVALUATION & AGGREGATION
The mean function, depicted in Figure 1, steers the acquisition function in its search for points that maximize the ascent probability at the central point 0. Equation (2) indicates that the same function influences the computation of the descent direction. Consequently, the quality of the approximator 0% embedded the advantage mean function, is crucial for both exploration and exploitation.
Therefore, it is desirable for Q to generalize beyond observed trajectories. In this section, we propose criterion for estimating the quality of such approximators. Utilizing this criterion, further develop an adaptive strategy for aggregating the predictions of an ensemble of approximators.
4.1 EVALUATING Q-FUNCTION ESTIMATORS
In the existing literature (Fujimoto et al., 2018; Van Hasselt et al., 2016), the quality of a parametric approximator Q is assessed by comparing its predictions to those obtained by an empirical esti- mate @Th generated by rolling out the policy mp. The weakness of this scheme that only uses the trajectories collected by wa, which cover only subset of the state-action space.
To tackle this limitation, we leverage the performance difference lemma (Equation (4)). This prop- erty indicates that given action-value function QT" and the corresponding policy return ((Te), we can perfectly recover the policy return ((Tz) of any actor u.. d is also known.
In our setting, roll out the policy corresponding to the central point 0 to have access to an empirical estimate [(TO and approximator 2 Similarly, roll out the policy corresponding to any point to get access to the sample estimates of J(Tz) and d= Thanks to the performance difference lemma (Equation (4)), we can use the error induced by Q% as a measure of its quality:
(J(Te) + E Ba [A (s, (s) - {(Ta) 2
(mo(x)- J(x))
(10)
We emphasize that my relies dm while my leverages d== estimate the policy return J(x)). This method evaluates Q on trajectories from policies other than Te, allowing all available tra- jectory data to be used for our approximator's evaluation. This provides a more comprehensive validation criterion, addressing the existing assessment scheme's limitations.
4.2 ADAPTIVE AGGREGATION OF Q-FUNCTION ESTIMATORS
In our setting, we have access to the dataset D [x, 2 (X)) collected during the previous iterations the algorithm. consists of the observation points X, their sample policy returns [()), and empirical discounted state occupation measures d= (X) A {d dd= Assuming good approximator @ Equation (10) suggests mo should serve effective predictor of J(x))-
5

---

Published as a conference paper at ICLR 2024
Algorithm Rollout for one point
Require: Policy parameters z, observation dataset D = (1 replay buffer 0
1: if is central then
2: Reset the optimizers of all critics
3: Reset the weights of least performing critic
4: end if
5: Collect J(T.) (mz) d== T(T)) (sr, oe, ras (t11)(t=1....)))
6: Update training data D <- DU (I, [[TTT(TT))))) d=x) replay buffer B t- B u ((x))
7: Update the parameters of critics 2 (........ on B
8: Compute the weights of every critic according Equation (12) using D
9: Fit the GP parameters on D and mng.
Therefore, evaluate the quality of 2 we use the coefficient of determination of ma on the dataset D. This metric measures the percentage of variance in the data explained by our predictor:
Exex (mo(x)
[(TT)) (
where J(X)= Exex [ |X
R () 1
(11)
Σxex (J(X)- - [(Tm))
Estimating (T a) requires rolling out trajectories T(s, a; πΦ) _ as, (o(s)), ), 8" nod (s").....
These trajectories play the role of the training data to learn good approximation 1 (s, Hence, d= present in our training dataset. Similarly, we can define (e) D) for the predictor ms. The trajectories T(s, (s); for ~ d used by my are different from the validation trajectories. Since m is used during inference, refer to ( D) the test score. We note that while a perfect Q estimator can have perfect validation score, it might not achieve perfect test score due to the residual term in Equation (5).
we refer to (e10, D) as the validation score since the trajectories 7(s, (s): n3 for used by my
In our context, we deploy ensemble of critics Q (.........)' We adopt the Follow The Regularised Leader (FTRL) algorithm Besa-BBincch Lugosi, 2006) construct an aggregated critic, Q via softmax weighting of the predictions of each critic using its respective Ri2 score:
exp R2 10,
(s, Σ
w. Q70 de
(s,
where
WA
(12)
exp 122 (0, 0,
We denote by mh the advantage mean function that uses the aggregate estimate Q Additionally, we reset the optimizer of every critic when changing the central point 0 because we are learning the Q-function of new policy. We also reset the weights of the worst-performing critic in order to improve the general performance by avoiding the primacy bias (Nikishin et al., 2022). This resetting also helps in decorrelating the predictions of each critic, and thus, reducing the variance of the predictions. We illustrate this step in Algorithm and describe the full BO scheme Algorithm 2.
Algorithm 2 Augmented Bayesian Search (ABS)
Require: central point 0, number iterations N, number of acquisition points M, stepsize 6, observation dataset D O}. replay buffer B
1: for = ...... N do
2: Rollout the central point @ using Algorithm 1.
3: for 0, 0.... M do
4: Query for an acquisition point arg max, (= 20,
5: Rollout the acquisition point using Algorithm 1.
6: end for
7:
end for
8:
Move in the direction of the most probable descent 0 B + 8 E 44
"The main BO loop of ABS can be seen simplified version of that of MPD. The only difference being that MPD performs multiple descent steps and uses constant mean, whereas our method uses the advantage m. which depends the current central point 0 limiting
descent step.

---

Published as a conference paper at ICLR 2024
5 EXPERIMENTAL ANALYSIS
In this experimental analysis, we aim to answer the following questions: (I) Is our advantage mean function a good prior the policy return? (II) Does our advantage mean function improve the efficiency of BO methods? (III) What role does our adaptive aggregation play?
5.1 IMPLEMENTATION DETAILS
For our Q-function estimator, we leverage the state-of-the-ar ensemble method of DroQ networks (Hiraoka al., 2021) with default parameters. For our ensemble of critics we use 5 distinct DroQ networks. After querying for an acquisition point we perform 5000 gradient steps to the Q-function. For our covariance function we choose a squared exponential kernel SE(x,x')
of exp Eisd | oi where on Oie(),.... are the signal variance, the observation noise, and lengthscales for dimension i, respectively. We model the policy return GP over the parameters of deterministic linear policies Jzx) ~ GP( ( x')).
o,²
BO requires prior knowledge about the tasks in order to fix the hyperpriors for parameters, such as the signal variance of and the observation noise on adding more hyperparameters to the problem. For our implementation of MPD and ABS, rely f, on from the observation data. This leaves us only to set the lengthscale hyperprior alleviating the burden of tuning these parameters. We refer the reader the Appendix A for further details.
heuristic to derive dynamic hyperpriors for
We validate our contributions using MuloCo locomotion tasks (Todorov et al., 2012). We use a discount factor 7 0.99 for all tasks, apart from Swimmer where it is 7 0.995. For our experiments, we use the state normalization scheme employed in (Mania et al., 2018; Nguyen al., 2022) where the states are normalized to normal distribution using online estimates of the mean and the variance. We have implemented ABS using Python 3.10 and Jax 0.4.20, we run all of our experiments on cluster of NVIDIA A100 40 GB GPU. Our code is available at ht https:: github. com/ wtw.ccoomllleeeeece wawleeelmadd/aaaee
5.2 RESULTS AND ANALYSIS
Goodness of Fit of the Advantage Mean Function. In Figure 2, we show the evolution of the validation metric of the best critic in the ensemble R2, taking all the samples collected in the last 3 outer loop steps of Algorithm 2. We superpose to it the test metric It of the ensemble Q over the acquisition points sampled during the same step. This is done for 3 high-dimensional tasks of Mu- JoCo (Todorov et al., 2012). We observe that the validation metric R² remains consistently positive with the validation predictor n. explaining on average approximately 50% of the variance observed data. The test metric R2 manages also to be positive quite frequently, while being sometimes nega- tive, meaning that our mean function my fails sometimes to explain the variance of policy return for the acquisition points. However, this is not a big concern as we only need the mean function to be able to identify one good direction of descent at time and not be perfect predictor for every point. Similar to a validation and test error, we observe a positive correlation between both metrics and that the validation error acts like upper bound to its test counterpart in the supervised setting.
Hollfhetttn 2070
Wallerdd Lin, derso100
1.00
1.2
0.5
3.5
0.35
800
3.03
-2.5
-229
430
820
0.5
-375
-8.5
-375
-000
-2.00
-1.9
0230 oude
Figure 2: Evolution of the validation and test scores some of the MuJoCo tasks. We plot the results of a seed to facilitate the interpretation our results. We provide the histogram and correla- tions of these distributions in the Appendix.

---

Published as a conference paper at ICLR 2024
peeetesPeneaumm LBP, (R
Suerense Cer (110116
Peppor 30050531
0.3
044
05
400
3890
2300
5008
*Gplodeet
Peftheeuah 211a0222
1.4
114
0.5
34
0.2
0.8
3
3830
2030 3000
4833
3000
2005
4333
6030
1093
10000
12893 34003
2033
4000
8300 8000
3900
12000
1000
Figure 3: Evolution of the maximum discounted policy return on MuJoCo-v4 tasks. We use random seeds for every algorithm. We report the undiscounted returns in Figure 6 in the Appendix.
Performance of ABS in terms of Policy Return. We evaluate ABS against two baselines, namely, MPD which is the current state-of-art of local BO methods (Nguyen et al., 2022) and Augmented Random Search (ARS) (Mania et al., 2018), an evolutionary algorithm that estimates the gradient of the noisy objective using random perturbations of the policy. In Figure 3, we see that ABS is competitive with MPD and ARS in low-dimensional tasks. Notably, ABS consistently outperforms the MPD demonstrating that the advantage mean function is helpful for local BO schemes. The rela- tive performance of ABS improves in high-dimensional tasks, such as Walker2d and Ant, where the curse of dimensionality makes it harder for ARS and MPD to identify promising descent directions, whereas our mean function can focus the search on more promising regions of the parameter space.
Effectiveness of the Aggregation Scheme. We perform an ablation study confirm the effective- ness of our adaptive scheme for aggregating critics in Figure 4. First, we observe that an ensemble of critics outperforms a single critic. We also notice that our strategy of adaptive aggregation (Equation 12) outperforms average ensembling. This is especially in the initial phases when transition data is scarce and it is easy to have poorly performing critic. Resetting the least performing critic im- proves the performance of the ensemble, and its effect is more pronounced when it is combined with our adaptive aggregation method. We explain this performance by the capability of our validation metric to detect when the recently reset critic performs poorly and ignore its predictions.
To summarize, ABS, which can be viewed as MPD augmented with the advantage mean function and the adaptive aggregation scheme consistently outperfoms the original MPD that uses the unin- formative constant mean function. The advantage mean function can explain a fair portion of the policy return of the observation points and hence represents good prior. Our validation metric and the consequent aggregation scheme are effective in dynamically selecting good critics.
So miner Lin, dire- 16)
Halfhhwihhh a mo- 1621
Alt (10, Smn-21
3.0
8.C
ANE
289
2003
5900
Figure 4: Ablation study: Effect of the adaptive aggregation on the performance of ABS. Combining adaptive aggregation and resetting the worst critic outperforms all baselines.
8

---

Published as a conference paper at ICLR 2024
6 RELATED WORK
Several prior works applied a Bayesian view to reinforcement learning and policy gradient meth- ods (Ghavamzadeh et al., 2016). However, in Bayesian Optimization, the majority of works treat reinforcement learning as a black-box problem (Martinez-Cantin et al., 2007; Englert & Toussaint, 2016; Martinez-Cantin, 2018; Eriksson et al., 2019; Nguyen et al.. 2022) and are oblivious to the MDP properties. As an exception, Wilson et al. (2014) propose a GP mean function leveraging a teaamics-moded estimate as a prior for the policy return and develop a kernel function measuring similarity between policies using trajectory data. In the black-box setting, Akrour et al. (2017) use sampling- based approach where the parameters of a normal distribution are updated using information-thooeeee constraints leading to optima. Fröhlich et al. (2021) introduce confidence region BO scheme to constrain the search space to points with less uncertainty. Eriksson et al. (2019) introduce trust region BO scheme that uses a collection of simultaneous local optimization runs using independent probabilistic models. Müller et al. (2021) propose the Gradient Information BO algorithm (GIBO) that utilizes probabilistic model of the objective function and its gradient to maximize information about the gradient posterior. Finally, Nguyen et al. (2022) improve on the information criterion of GIBO by querying for points that maximizes the probability of descent, and then moves in the direction of most probable descent. In contrast, our work exploits the sequential nature of the task which provides large practical gains, especially on higher dimensional tasks.
In the direct policy search literature, one alternative to BO is the use Particle Swarms (Hein et al., 2016; Hein, 2019). Closer to our work are Evolutionary Strategies (ES). They are gradient- free methods deploying a random process to iteratively generate candidate solutions. Then, they eval- uate these solutions and bias the search the direction of the best-scoring ones (Hansen, 2006; Salimans et al., 2017; Mania et al., 2018). (Salimans et al., 2017) propose variant of ES for op- timizing the policy parameters. They estimate a gradient via Gaussian smoothing of the objective function. (Mania et al., 2018) build on the work of (Salimans et al., 2017) and introduce simple random search algorithm that is competitive with the state of the art while using only linear policies. Compared to BO, ES uses a less principled exploration strategy and, in comparison our work, does not include the structure of the MDP in its search.
The deterministic policy gradient (Silver et al., 2014) and its practical variants (Lillicrap et al., 2015; Fujimoto et al., 2018) are also closely related to the context of our work. These methods apply the deterministic actor-critic algorithm to learn deep neural network policies. Kakade & Langford (2002): Schulman et al. (2015) develop algorithms for learning monotonously improving policies. This class of algorithm relies on lower bounding the difference of return between the current and the potential next policy and taking a step such that we are sure to improve our policy. Saleh et al. (2022) are the first derive such bounds for deterministic policies, but we specify these bounds further for Lipschitz MDPs. We further leverage this result to design our advantage mean function.
7 CONCLUSION AND DISCUSSION
In this work, we have presented Augmented Bayesian policy Search (ABS), a method that lever- ages a new mean function for the Gaussian Process (GP) prior which is tailored to Reinforcement Learning (RL). We derive our method by resorting to the performance difference lemma, to inject an action-value function of deterministic policies into the GP prior on the policy return. Our advantage mean function acts like a first order taylor expansion of the policy return, bridging the gap between BO and RL methods. We theoretically ground our approach by deriving a new bound on the impact of altering deterministic policies on the expected returns for Lipschitz MDPs. Moreover, we propose a novel adaptive scheme for aggregating multiple Q-function estimators. Empirically, we show that ABS scales to high-dimensional problems and establishes state-of-the-art performance for Bayesian Optimization (BO) methods in MuloCo locomotion problems. ABS can explore using deterministic policies and learn effectively in an episodic setting. It also allows trading-off off compute for learning speed, which is a highly desirable property in real-world applications.
For this work, we were limited linear policies due to computational considerations. A promising future direction is scaling BO methods to deep policies. To this end, viable solutions include random projection methods (Ziomek & Ammar, 2023) and kernel functions for the GP that are tailored for deterministic policies, close to works like Wilson et al. (2014); Ghavamzadeh et al. (2016).

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The authors thank Gandhary Patil and Tom Dupuis for their helpful comments and discussions. This work was funded by the German Federal Ministry of Education and Research (BMBF) (Project: 011S22078). This work was also funded by Hessian.ai through the project 'The Third Wave of Ar- tificial Intelligence 3AT by the Ministry for Science and Arts of the state of Hessen. D. Basu acknowledges the Inria-Kyote Kyoto University Associate Team "RELIANT", and the ANR JCJC for the REPUBLIC project (ANR-22 22-CE23-0003--22 knowledge the scientific support and HPC resources provided by the Frlangen National High Perfor- mance Computing Center (NHR FAU) of the (FAU) under the NHR project b187cb. NHR funding is provided by federal and Bavarian state au- thorities. NHR @ FAU hardware is partially funded by the German Research Foundation (DFG) 440719683.
for supporting this work. The authors gratefully ac-
Frlangen-Nürnberg
AUTHOR CONTRIBUTIONS
R. Akrour proposed the idea of the advantage mean function which was explored as part of the internship of M. Kallel at Inria Scool under the supervision of R. Akrour and D. Basu, After his internship, M. Kallel started his Ph.D. at the University of Würzburg under the supervision of C. D' Eramo, where he kept working on the project and finalized All the authors contributed to the writing of the paper.
REFERENCES
Riad Akrour, Dmitry Sorokin, Jan Peters, and Gerhard Neumann. Local Bayesian optimization of motor skills. 34th International Conference on Machine Learning, ICML. ICM1.2017, 1:59-68, 2017.
Danilo Bruno, Sylvain Calinon, and Darwin Caldwell. Bayesian nonparametric multi-optima policy search in reinforcement learning. In Proceedings the AAAI Conference on Artificial Intelli- gence, volume 27, pp. 1374-1380, 2013.
Roberto Calandra, André Seyfarth, Jan Peters, and Mare Peter Deisenroth. Bayesian optimization for learning gaits under uncertainty: An experimental comparison on a dynamic bipedal walker. Annals of Mathematics and Artificial Intelligence, 76:5-23, 2016.
Nicolo
and Gábor Lugosi. Prediction, learning, and games. Cambridge university
press, 2006.
Alexander Nowen-Riieers Wenlong Lyu, Rasul Tutunov, Zhi Wang, Antoine Grosnit, Ryan Rhys Griffiths, Alexandre Max Maraval, Hao Jianye, Jun Wang, Jan Peters, et al. Hebo: Pushing the limits of sample-efficient hyper-parameter optimisation. Journal of Artificial Intelligence Research, 74:1 14:1269-1333 1349, 2022.
Peter Englert and Mare Toussaint. Combined optimization and reinforcement learning for manipu- lation skills. In Robotics: Science and systems, volume 2016, 2016.
David Eriksson, Michael Pearce, Jacob Gardner, Ryan D Turner, and Matthias Poloczek. Scalable global optimization via local Bayesian optimization. Advances in neural information processing systems, 32, 2019.
Lukas P Fröhlich, Melanie N Zeilinger, and Edgar D Klenske. Cautious Bayesian optimization for efficient and scalable policy search. Learning for Dynamics and Control, pp. 227-240. PMLR, 2021.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference on machine learning, pp. 1587-1596. PMLR, 2018.
Roman Garnett. Bayesian optimization. Cambridge University Press, 2023.
Mohammad Ghavamzadeh, Yaakov Engel, and Michal Valko. Bayesian policy gradient and actor- critic algorithms. The Journal of Machine Learning Research, 17(1)2231-2377, 2016.
10

---

Published as a conference paper at ICLR 2024
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International confer- on machine learming, pp. 1861-1870. PMLR, 2018.
Nikolaus Hansen. The ema evolution strategy: a comparing review. Towards a new evolutionary computation: Advances in the estimation of distribution algorithms, pp. 75-102, 2006.
Daniel Hein. Interpretable Reinforcement Learning Policies by Evolutionary Computation. PhD thesis, Technische Universität München, 2019.
Daniel Hein, Alexander Hentschel, Thomas Runkler, and Steffen Udluft. Reinforcement learning with particle swarm optimization policy (pso-p) in continuous state and action spaces. Interna- tional Journal of Swarm Intelligence Research (IJSIR), 7(3):23 42, 2016.
Takuya Hiraoka, Takahisa Imagawa, Taisei Hashimoto, Takashi Onishi, and Yoshimasa Tsu- ruoka. Dropout q-functions for doubly efficient reinforcement learning. arXiv preprint arXiv:2110.02034, 2021.
Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning, 2002.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. CoRR, 09 2015.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search provides competitive approach reinforcement learning. arXiv preprint 1803: 07055, 2018.
Ruben Martinez-Cantin. Funneled Bayesian optimization for design, tuning and control of au- tonomous systems. IEEE transactions on cybernetics, 4900)1149--1500 2018.
Ruben Maatinez-Canntin Nando de Freitas, Arnaud Doucet, and José A Castellanos. Active policy learning for robot planning and exploration under uncertainty. In Roboties: Science and systems, volume 3, pp. 321-328, 2007.
Sarah Müller, Alexander Rohr, and Sebastian Trimpe. Local policy search with Bayesian opti- mization. Advances in Neural Information Processing Systems, 34:20708-20720, 2021.
Fabio Muratore, Christian Eilers, Michael Gienger, and Jan Peters. Data-efficient domain random- ization with Bayesian optimization. IEEE Robotics and Automation Letters, 6(2):911-918, 2021.
Quan Nguyen, Kaiwen Wu, Jacob Gardner, and Roman Gamett. Local Bayesian optimization via maximizing probability of descent. Advances in neural information processing systems, 35: 13190-13202, 2022.
Evgenii Nikishin, Max Schwarzer, Pierluca D'Oro, Pierre-Lue Bacon, and Aaron Courville. The primacy bias deep reinforcement learning. In International conference on machine learning, pp. 16828-16847, PMLR, 2022.
Mattco Pirotta, Marcello Restelli, and Luca Bascetta. Policy gradient in Lipschitz Markov decision processes. Machine Learning, 100, 03 2015. doi: 10. 10.1007/110994-015555
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pp. 63-71. Springer, 2003.
Ehsan Salch, Saba Ghaffari, Tim Bretl, and Matthew West. Truly deterministic policy optimization. Advances in Neural Information Processing Systems, 35:8469 84882, 2022.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.0388 2017.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning. pp. 1889-1897. PMLR, 2015.

---

Published as a conference paper at ICLR 2024
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In International conference on machine learning, pp- 387-395, Pmir, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physies engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Ryan Turner, David Eriksson, Michael McCourt, Juha Kiili, Eero Laaksonen, Zhen Xu, and Isabelle Guyon. Bayesian optimization is superior to random search for machine learning hyperparameter tuning: Analysis of the black-box optimization challenge 2020. NeurIPS 2020 Competition and Demonstration Track, pp. 3-26. PMLR, 2021.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Cédric Villani et al. Optimal transport: old and new, volume 338. Springer, 2009.
Linnan Wang, Rodrigo Fonseca, and Yuandong Tian. Learning search space partition for black-box optimization using Monte-Carlo tree search. Advances in Neural Information Processing Systems, 33:19511-19522, 2020.
Aaron Wilson, Alan Fern, and Prasad Tadepalli. Using trajectory data to improve Bayesian opti- mization for reinforcement learning. Journal of Machine Learning Research, 15:253-282, 2014. ISSN 15337928.
Juliusz Krzysztof Ziomek and Haitham Bou Ammar. Are random decompositions all need in high dimensional Bayesian optimisation? International Conference on Machine Learning, pp- PMLR, 2023.
12

---

Published as a conference paper at ICLR 2024
A IMPLEMENTATION DETAILS
Task name
Learning rate
Lengthscale prior
InvertedPendulum
{0.0025, 0.005]*
[4(0000125,
2.00),, 0.05)
Swimmer
{0.0025, 0.005
{4(0.00125, 0.025) 0.05)
Hopper
{0.0025, 0.005]*
[L((000122, (0000,, 0.05)
Halfcheetah
(0.001 25, 0.0025)*
(2(00000625, (00005), 0.025)
Walker2d
05, 0.0025
(4(0.000625,
(00025), 0.025)
Ant
(0.00125, 0.0025)*
0.,000062,..0122,,,,000000.222 0.025)
Table I: Hyperparameters used for grid-search for MPD and ABS. (+) For MPD use only learning rate of 0.01.
Task name
Learning rate
Lengthscale prior
N
Naca
N
maz
InvertedPendulum
0.005
l<000025, 0.05)
2
6
21
Swimmer
0.0025
(((000255 0.05)
3
39
Hopper
0.0025
l/(0.0025, 0.05)
3
16
51
Halfcheetah
0,0025
((00.01155, 0.025)
4
20
63
Walker2d
0.0025
U(00000025,, 0.0125)
4
20
63
Ant
0.0025
4(0.000625, 0.0125)
5
24
75
Table 2: Hyperparameters used for ABS.
We use a DroQ critic with the original hyperparameters (Hiraoka al., 2021) which consists of two critics with layers of size (256, 256) with ReLU activations, and using LayerNormalization critics. We leverage the fact that the discounted policy returns are normalized and apply a tanh layer to bind the predictions of every critic between [-1, We use 32 parallel optimizers to optimize both the parameters of the Gaussian Process and the acquisition function. We follow Müller et al. (2021) and only train our GPs on the last Nmaz data points collected in the Bayesian Optimization loop. In all our experiments, we keep track of the data generated by the last 3 outer loops of Algorithm 2, thus Nmaz 3 x (1 + Naeg) where Noeg is the number of acquisition points sample at one outer loop. We also rollout the central point 0 Ne times in order to have better advantage mean function estimate and to also alleviate the need for signal prior as described below.
and Dropout. For all our experiments, we use an ensemble
The selection of hyperpriors for the signal variance oy and the noise variance on requires domain knowledge about the task at hand and adds other hyperparameters to the BO problem. In the partic- ular case of local BO, when roughly similar among all points. The same logic applies to the signal variance. With this intuition in mind, we develop a heuristic to dynamically fix the hyperpriors for oj, On. Using the fact that Jw. (To))
at fixed neighborhood it is fair say that the observation noise
we roll out the central point N₂ times, we use a noise estimate & = (ar(J We then fix the hy-
where J, is the noisy policy return estimate from the i-th rollout policy perprior to be U[ x on, 3 x ān). For the signal variance, we adopt similar scheme by taking {(zz) and use as a signal variance prior Ld[3 Ø x ōy]- In the case of the constant mean used in MPD, the variance corresponds to the observation variance. MPD (Nguyen et al., 2022) has the merit of being less learning rate dependent than our method, being able to use a small learning rate and perform multiple descent steps. ABS cannot perform the same scheme as our advantage mean function depends on the central point 0. In our implementation of MPD, we follow the code provided by the authors where we first normalize the gradient g Σ 1440 to have an L2 norm of 1 and use the same learning rate 0.01 for all environments. Hence, for MPD we perform grid-search only for the lengthscale hyperprior. For ABS, perform search over the learning rate and the lengthscale prior, and report the best-performing set of hyperparam- eters (Table 1). For all the results obtained with MPD and ABS in this manuscript, we used these best set of parameters (Table and 3). For ARS, we use the original parameters reported in the paper (Mania et al., 2018).
o3
13

---

Published as a conference paper at ICLR 2024
Task name
Learning rate
Lengthscale prior
Ne
Naeg
N Mma
InvertedPendulum
0.01
71(0.0025 0.05)
2
21
Swimmer
0.01
u(0.0025, 0.05)
3
12
39
Hopper
0.01
14(0.0025, 0.025)
3
16
51
Halfcheetah
0.01
((0.00125, 0.025)
4
20
63
Walker2d
0.01
((00000625, 0.0125)
4
20
63
Ant
0.01
((0.000625, 0.0125)
5
24
75
Table 3: Hyperparameters used for MPD.
B EXPERIMENTAL SECTION
B.1 UNDISCOUNTED RETURNS
Here, we plot the evolution of the maximum undiscounted policy return function of the number of episodes. ABS, which can be seen as MPD augmented with the advantage mean function and the adaptive aggregation scheme consistently outperfoms MPD that uses the constant mean function. Our algorithm outperforms substancially the ARS baseline for the Walker2d and Ant tasks.
InvesedTanddllmm.om diramm)
Hoppar (et, d23
3300
152
MPC
4.6
6000
400
393
1200
200
500
831
330
1283
2003
Naltchestan d2m
3900
4300
0200
3500
3000
$2.0
2000
22.0
U80
2200
509
3500
3000
2300
2202
1000
4331
1293
2006
430
HERS
1980
12001
10003
2200
2000
1223
1091
11691
L18E0 1403)
Figure 5: Evolution of the maximum undiscounted policy return on the MuJoCo-v4 tasks. We use random seeds for every algorithm.
B.2 VALIDATION AND TEST SCORES
Here, we plot the histogram of the distribution of the validation score R2 and test score R2 used Figure 2 for better visualization. We observe that the validation metrie R²2 remains consistently positive with the best critic explaining average approximately 50% of the variance observed data. The test metric R² manages also to be positive quite frequently, while being sometimes negative
14

---

Published as a conference paper at ICLR 2024
Haafhhersh L0F, 1i 1021
WalroDo LdF, (00
ARtERn, (815-229
25.5%
That Score
15 85
21.%%
23.85
185
386
5.%
0.5%
Figure 6: Histogram and correlation of the validation and test scores for MuJoCo- v4 tasks for run of ABS. The dashed vertical lines represent the medians of their respective distributions. We clip the scores to [-1,1] for easier visualization.
C PROOFS
C.I PROOF OF THE POSTERIOR OF THE GRADIENT
Corollary C.0.1. Under the advantage mean function, the mean of the gradient posterior at 0 is
[vaQ% (s, (s))))= ((X |
N10
E "andta
(x))(x)))(())) (13)
Proof.
@mp(xx
V (0)
Ox
==
(J(TT)
+ Eanaro
[ATH (s,
( Fx
==
0 Q (s.
Esnd
(s,
Ox
m==
dr
1=
0 Q (s, (x))
0
E Ra
Q (8,
(8, mo(s))
(it)
dr
x=
Fx
Egnd
( (s, T [s))
Ox
x=
O
Eg
2= a) ia
a=mo(
dx
Step (i) is due to independence of ((TO) and æ. Step (ii) is true because Q (TT()), is independent of x. We get the final result by injecting this equality into Equation 2.
C.2 LIPSCHITZ MDPs INDUCE DISTRIBUTIONALLY LIPSCHITZ MDPS
Assumption C.1 (Lipschitz MDP (Pirotta al., 2015)). An MDP with policy class II is (L,, Lp: Lz)- Lipschitz for all s, s E S and a, a' E A:
Lipschitaness of reward: - - r(s' d')l s (dd(((s,))) + dala,a')
Lipschitzness of transition: W(p(1ss,), p(-1s/ d')) S Lp(ds(s, 80) + da(a,a'))
Lipschitzness of policy: ( S Ly ds s2) for all क E 11.
Assumption C.2 (Distrributionally Lipschitz MDP (Saleh et al., 2022)). For an MDP with a policy class II is (I,, Li)-Sischitz for all m, E TI and μ1, n22 E PPS), the following holds true.
Lipschitzness w.r.f. policy: (((( P(,, m2)) S Li supses W (T)(s),, R2(s))
Lipschitzness w.r.t. state distribution: W (P (( m)) < T. W T22(n, (11,
15

---

Published as a conference paper at ICLR 2024
Where P denotes the generalization of the transition dynamics to take input probability distribu- tions of actions or states.
Assumption C.3. The state space S E Rd and is bounded.
Theorem C.4. Lipschitz MDPs (Assumptions C.1) induces Distributionally Lipschitz MDPs (As-
sumptions C.2) with Lipschitz rewards such that L1 = I. and L2 = Tpp(1 LT).
Proof. Now, we prove that Assumptions C.I (without Lipschitzness of reward) implies Assumptions C.2.
Part 1: Lipschitzness w.r.t. policy.
W(P(H, P(u, (()) = (a [(((e / pl-18, (2(s))((()
W(a(s)
S sup ((((s), SES
s 1 sup W ( (s), +2(3)) SES
L 72)
Step (a) is due to Theorem 4.8 (Villani et al., 2009).
This implies that L1 = Lxx
Part 2: Lipschitzness w.r.t. state distribution.
Ss p(.1s, ([((s,,((s))))) (()) du)(s) / pl-1s, x pl.1s,((s))) (()))
(I(P(u,)T) (TP(H,,,,,P(pa)) P()2,T)) = w
Mc-1s)
= W ( ((1lsdju (s), / A(1s))pp((s)
( [/8 ((s((s) ds'
sup
11ll
- ((6') [/ ((s' ((s()s) ds')
= sup / f(5') [[ ((()()) ds'
1
(12()) (s()))
F(s')\(s'is)dds ds
sup
(c) 1
9(e)
sup / (12(8) un (s)
Lp Ixx)
|
< Lp W M1).
Step (b) is due to Remark 6.5 in Villani et al. (2009). Step (c) is obtained by applying Fubini-Tonelll theorem, as S is bounded. Step (d) holds true as g is Lp L,) Lipsshitttt (Lemma C.5) and is maximum 1-Lipschitz.
Thus, conclude that T-2 (1 + I.z)-
Lemma C.5. If define g(s) & Ss (s')))sssssssdd for Lipschitz MDP (Assumption C.I) and su [|/l], 1, then g [1p(1 (1 Lo -iipschitz.
16

---

Published as a conference paper at ICLR 2024
Proof.
/ f(dd))((\(s)ddd - [(5))((511s))dd
[g(s)) - g(52)]
/ h(s')A(</ (s)ddssssddss - -J h(o')2('((02)dd)
sup
||N]
W(A((151))\((152))
Lp(1 + Lx) x (5)
I (p(1+ x ds( 82)
Step (e) holds true because Lipschitz constant of is less than equal to 1, and we take supremum over such functions.
C.3 BOUND ON THE RESIDUAL TERM
Now, we use Theorem C.4 to bound the residual for Lipschitz MDPs.
Theorem C.6. For a Lipschitz MDP satisfying (Assumptions C.I) and yLp(1 1 + L < 1, we have that the residual term
d
S sup [2((s) - (100)-(((3)) (s)ll.
(14)
SES
for C L, (1+Le) (1
Proof. Step 1: First, we bound the residual using the Wasserstein distance between policies and L2
distance between the gradient of Q functions.
(d"= -_-dd d A (s,
= (d d=t,,0 ddt, (s, (s,
S W (d)) sup V IQ (s, m2(5)) Q (s, (s))ll
(15)
We obtain the last inequality from the Kantorovich Rubiinttenn inequality (Villani et al., 2009).
Step 2: Now, we bound the the change in gradient of Q-functions due the change in policies.
V. 1Q (s, T2 (s)) Q
(s,
(s))
aQ
aQ
aQ
aQa
+ STT((S)
(T)
0S
(.)2(s)
da
1,32(8)
ØS (1)
Oa (.)
aQ
aQ
aQ
aQ
V ST)
ST (s)
Oa (s)
05
(s))(ss
(s)
Da
(.)7((())
Step 3: Bounding Term Here, leverage the property that if f is L-Lipschitz, || S L.
Q function is LQ Lipschit for Lipschitz MDP, such that Le T- for 7Lp(1 +1+ Lx) < 1 (Pirotta al., 2015).
La
Thus, we conclude that
iQ
< LQ. This bounds the Term by 2LQ.
ds
Step 4: Bounding Term b.
aQ* 9
aaQ
T2
(s)
S [T)(())) x
Da ()))(()
S L
da
(.)
17

---

Published as a conference paper at ICLR 2024
The first inequality is a consequence of Hölder's incquality, while the second one is obtained from Lipschitzness of and x. Thus, Term b is bounded by 2..
Step 5: Putting it all together. Combining Equation (15) with the bounds on Term a and Term yields
1d d T (2)) W(d ,d x 2 LQ 2Tx²)
7
sup
(2), x 2 LQ(1 + T.=)
(4)
1 - Lpp Lxx)
SES
2, (1 + L
(1 71-><p(1 + L ))² sup [[ TT (s)ll
Step (a) is derived by an application Theorem B.4 (Saleh al., 2022), when y + Lx) < 1.
18


Reviews:
[{"review_id": "Pf5DSBiRBp", "reviewer": "Reviewer_gD9d", "summary": "This paper presents a method for policy search/actor critic based on local Bayesian optimization. The main contribution is in the use of a mean function that captures the advantage (critic) of the model  that relates a set of parameters theta with the queried set of parameters x.", "questions": "-In the paragraph before eq 8, it says “Proposition 3.3”. I think you mean “Theorem 3.3”\n-Why all the policies in Figs 3 and 4 are normalized? What do you mean by discounted policy returns? It seems that the undiscounted returns like the ones presented in the appendix are more standard in the literature and allows comparisons with other works. Also, the standard approach is to use steps for the horizontal axis, instead of episodes.\n-The R2 analysis is unclear. The fact that for many iterations the correlation is negative and it is mostly below 0.5 means that the fitness might not be accurate. Furthermore, the R2 is a fitness measurement for linear regression, which does not seem to be the case for the Q-function.\n-Policy search with Bayesian optimization has been extensively studied since 2007 [B] and there are many works missing. For example, [C] presented a PS method with BO using local models as well, while [D] also combines parametric and non-parametric (GP) models.\n\n[B] Martinez-Cantin R, de Freitas N, Doucet A, Castellanos JA. Active policy learning for robot planning and exploration under uncertainty. In Robotics: Science and systems 2007 Jun (Vol. 3, pp. 321-328).\n\n[C] Martinez-Cantin R. Funneled Bayesian optimization for design, tuning and control of autonomous systems. IEEE transactions on cybernetics. 2018 Feb 27;49(4):1489-500.\n\n[D] Englert P, Toussaint M. Combined Optimization and Reinforcement Learning for Manipulation Skills. In Robotics: Science and systems 2016 Jun (Vol. 2016).\n\n----\nAfter discussion comment: After reading the authors and other reviewers comments, I have decided to increase my rating although there are still some minor problems: R2 analysis relies on some assumptions that are only valid in the linear case and can be deceptive in the nonlinear case [E]\n\n[E] Spiess, Andrej-Nikolai, Natalie Neumeyer. An evaluation of R2 as an inadequate measure for nonlinear models in pharmacological and biochemical research: a Monte Carlo approach. BMC Pharmacology. 2010; 10: 6.\n\nAlso, the reference [C] is incorrectly attributed as a particle swarm algorithm. In my previous comment, I meant PS as in policy search, not particle swarm. Apologies for the confusion.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The idea of using the recent local Bayesian optimization methods for efficient policy search for high dimensional problems is quite interesting. Furthermore, it is well integrated with the performance difference lemma to enable updates on the information of theta with queries at x. I can see a lot of potential of this work in the community.", "weaknesses": "There are some limitations that can reduce the applicability of this work and make it difficult to understand. For example, it is never explained the type of policy being used. The derivation is based on nonparametric (tabular) policies, but those type of policies are too limited for the MuJoCo experiments. Even the linear policy seems to be very limited.\nThe idea of incorporating information from x at theta is interesting, but that still requires to sample rollouts from the policy pi_x, which seems counterintutive in a BO setting where sample efficiency is of paramount importance. It seems that the philosophy behind the mean function is similar to having a GP with inducing points. The other advantage of using pi_x seems exploration, but that can also be achieved with importance sampling.\nGiven the nature of the application (sample efficient PS), the authors should include in the comparison both novel AC methods (SAC, TQC…), model based approaches which are also sample efficient (MBPO…). For example, according to the MBPO paper [A], MBPO is able to achieve 6000 reward in a similar number of steps than ABS gets 4000.\n\n[A] Janner M, Fu J, Zhang M, Levine S. When to trust your model: Model-based policy optimization. Advances in neural information processing systems. 2019;32.", "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": "", "extra_scores": {}}, {"review_id": "DHWbsC0QwB", "reviewer": "Reviewer_yvFW", "summary": "The paper deals with model-free, bootstrapping-free online RL. It investigates Bayesian optimization for policy search. The new method is compared with two similar methods on six deterministic benchmark MDPs and shows similar results.", "questions": "* Why was a comparison with bootstrapping-based methods such as NFQ [4], DQN [5], SAC [6], etc. omitted?\n* Why was a comparison with a bootstrapping-free, model-based method such as PILCO [7] omitted?\n\n[4] Riedmiller, Neural Fitted Q Iteration – First Experiences with a Data Efficient Neural Reinforcement Learning Method, 2005\\\n[5] Mnih et al., Playing Atari with Deep Reinforcement Learning, 2013\\\n[6]  Haarnoja et al.,  Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, 2018\\\n[7] Deisenroth and Rasmussen, PILCO: A Model-Based and Data-Efficient Approach to Policy Search, 2011", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The approach is interesting, I think bootstrapping-free approaches should be given more attention.", "weaknesses": "* There is no comparison with one of the frequently used model-free RL methods with bootstrapping.\n* The presentation does not classify the approach clearly enough in the very broad field of RL algorithms.\n* The results do not show a clear superiority over the two comparative methods. It is not made sufficiently clear why this approach should nevertheless receive attention.\n* The method is only tested on deterministic MDPs without mentioning this limitation.\n\nFurther comments:\n\n* The term \"deterministic exploration\" requires an explanation.\n\n* Regarding \"deterministic policy gradient, which changes its actions to maximize Qπθ (Silver et al., 2014)\", I would like to note that this principle was already introduced in 2007 in [1].\n\n* \"max\" should not be italicized, see Algorithm 1.\n\n* The sentence \"Evolution of the validation and test scores a representative seed on the MuJoCo task\" is incomprehensible.\n\n* The claim \"Our learned Q-function can reconstruct the real Q-function\" is, in my opinion, not sufficiently substantiated by Figure 2.\n\n* In my opinion, \"In the direct policy search literature, an alternative to BO is the use of Evolutionary Strategies\" lacks the mention of the use of swarm-based methods such as PSO in [2] and [3].\n\n\n* There are several unintentional lower case letters in the references: bayesian, gaussian, lipschitz, markov\n\n[1] Schneegaß et al., Improving optimality of neural rewards regression for data-efficient batch near-optimal policy identification, 2007\\\n[2] Hein et al., Reinforcement learning with particle swarm optimization policy (PSO-P) in continuous state and action spaces, 2016\\\n[3] Hein, Interpretable Reinforcement Learning Policies by Evolutionary Computation, 2019", "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": "", "extra_scores": {}}, {"review_id": "DdfCY5yNkA", "reviewer": "Reviewer_ysm5", "summary": "The authors present a new method for policy search, combining local Bayesian optimization with policy search. In essence, they describe novel mean function for a Gaussian process that is derived from the performance difference lemma. \n\nOverall, the algorithm performs reasonably well and appears to outperform existing methods on some tasks", "questions": "Did you see that compared to the baseline your approach gave a more stable/monotonic improvement over time?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- the paper is well written, contributions are highlighted, clear experimental questions\n- while not easy to follow (one needs to have expertise in many different areas: model-free RL, (local) Bayesian Optimization, Gaussian processes) the author explain their reasoning well\n- the experiments  are carried out rigourosly, including repetitions, definition of research questions, etc\n- the finding is novel: utilizing the performance difference lemma to derive a more informed mean function to have a better estimate of the performance of neighboring policies is clever (in some ways an informed Taylor approximation)", "weaknesses": "1. minor: The plots can be improved, figure 2-4  is not very pretty (too high linewidth, scrollbar on the right, grid overrides plot)\n2. Performance is only marginally better/worse than existing methods\n\n3. This is not a weakness/critique directly but it relates to point 2. Also this point will be a bit opinionated.\n\nI do not believe that the \"classical RL setup\" of:  exploration towards exploitation(i.e. gradually improving/figuring out the task) is where this method is applied best. Essentially you use the BO + the local mean function interpolation to iteratively improve the policy estimation.    That is why, comparing to \"less rigorous/Bayesian\" approaches the improvements are not very striking\n\nHowever, I believe a stronger case can be made if you would look at the method from a risk-sensitive perspective. Your mean function will give you an informed estimate around the known evaluation. The more you move away from that the more the epistemic uncertainty of the probabilitc model will set in. This would enable you to essentially define a \"safe zone\" around your current estimate.  And your method would have a better informed safe zone compared to other approaches because you leverage the information better using the advantage mean function. Therefore I would expect that your method would still maintain the advantages of a risk-sensitive method (i.e. by monotonic improvement over time) but be more \"quick\"/greedy compared to traditional risk-sensitive approaches.\n\n4. Related,  conceptually speaking   you make your mean function more informed utilizing the performance difference lemma. This, essentially is a form of interpolation from existing points (i.e. estimating the return of a policy \\phi, given knowledge of the return of policy \\theta.).  Such knowledge/modelling naturally would go to the kernel function, instead.  The result of your current approach, infusing it in the mean funciton instead,  is that while you mean function is more informed, your covariance function is not.  Therefore, your covariance function will only be a function of the standard kernel function and X.  This means, your estimate of predictive epistemic uncertainty does not take into account the insight \"using the knowledge of \\theta I can make a more informed guess about the policy \\phi\". So in my opinion you are still underutilizing the insight described in this paper.", "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": "", "extra_scores": {}}, {"review_id": "vJvoZ9p1cq", "reviewer": "Reviewer_m5Gu", "summary": "This paper presents an elegant BO framework that combines policy gradient and policy evaluation information.  The paper leverages a new construct, the advantage mean function, to improve the typical mean function used in Gaussian processes; this mean function leverages the nature of RL to improve over a naive mean function, and allows the GP to focus its modeling power on second-order residuals.  By jointly modeling the mean and gradient exploration can be improved.\n\nOverall, I really liked this paper. I felt like it presented a strong combination of ideas that are novel, creative, and likely to have impact in the field.\n\nI only gave it a 6 because I have several questions about the method that I could not resolve by reading the paper.", "questions": "I am a little bit worried about the assumption of a linear policy; it was unclear to me if this was for exposition, or a constraint on the algorithm. Could you clarify?\n\nI see that you assume that you have access to J, d, and Q, but not more granular information about observed s,a,r sequences. Why is that? Is that just an assumption that could be relaxed, and if so, would the more granular information be useful in constructing better GP posteriors?\n\nYou combine the Q-experts using a softmax of exp(R^2) terms. This seems somewhat ad hoc. Is there a principled reason for this choice?\n\nResetting the least-performing critic also seems like an ad hoc choice. Is there a principled reason for it?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ An elegant combination of multiple ideas\n+ The advantage mean function is a good idea\n+ Love the idea of jointly modeling the value and gradient with a single GP\n+ Clearly written (although reader needs to be an expert), well-referenced, etc.", "weaknesses": "- The paper is somewhat dense and difficult to parse.\n- Empirical results are fine, but could be stronger.", "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": "", "extra_scores": {}}, {"review_id": "bomVqnEfpc", "reviewer": "Reviewer_fyPW", "summary": "The authors popose Augmented Bayesian policy Search (ABS) a Bayesian optimisation (BO) algorithm for reinforcement learning (RL). Typically, BO methods for RL estimate the objective function (dsicounted rewards) using Gaussian Processes (GP) with a constant mean function for the GP prior. In this work the authors propose a new mean function for the GP prior based on empirical estaimtes of the objective function and the advantages between the old policy and new policy. By using this advantage mean function the authors show that the gradient of the posterior takes the form of the deterministic policy gradient corrected by how closely the mean function fits the observed dataset. This approach is theoretically backed by a new bound derived by the aithors that bounds the residual term of a rearranging of the performance difference lemma for Lipschitz MDPs. Finally, the authors also develop an adaptive scheme for aggregating ensembles of Q function estimators based on fitness measure (R-squared) on the whole dataset.", "questions": "I am not familiar with Lipschitz MDPs, presumable the reward function is Lipschitz bounded, but what of the transition functions and policies? Is there a natural way of bounding these that makes sense?\n\nWhat are the key difference between your approach and the baselines considered in this paper? \n\nWhat are the reasons for only considering deterministic policies?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "(1) The paper is well motivated and a comprehensive introduction and related work section helps the reader grasp where this research sits in the literature.\n\n(2) The contribution is novel and significant. Specifically, the new bound based on the performance difference lemma for Lipschitz MDPs is convincing and useful (although I haven't thoroughly checked the details on this). The results are also promising and demonstrate good sample complexity.\n\n(3) The algorithm itself is well motivated and theoretically backed, and the evaluation is sufficient enough for me.\n\n(4) To me the paper seems mathematically sound, presented well and well written.\n\nI find this an interesting paper and I'm sure it would be of interest at ICLR, which is why I am recommending it for acceptance. Although since I am not an expert in BO for RL I only feel able to weakly accept this paper. Hopefully a more well read reviewer can see more of the merit of this paper.", "weaknesses": "(1) Quite a lot of prior knowledge is required to understand this paper. I am not immediately familarly with BO methods for RL, perhaps some more intuition for comparison to more familair RL methods may be helpful for the average RL practitioner.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)