Zeroth-Order Actor-Critic
Authors: Yuheng Lei
Jianyu Chen
Shengbo Eben Li
Sifa Zheng
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
zeroth-order optimization
actor-critic

Abstract: Evolution based zeroth-order optimization methods and policy gradient based first-order methods are two promising alternatives to solve reinforcement learning (RL) problems with complementary advantages. The former work with arbitrary policies, drive state-dependent and temporally-extended exploration, possess robustness-seeking property, but suffer from high sample complexity, while the latter are more sample efficient but restricted to differentiable policies and the learned policies are less robust. We propose Zeroth-Order Actor-Critic algorithm (ZOAC) that unifies these two methods into an on-policy actor-critic architecture to preserve the advantages from both. ZOAC conducts rollouts collection with timestep-wise perturbation in parameter space, first-order policy evaluation (PEV) and zeroth-order policy improvement (PIM) alternately in each iteration. The modified rollouts collection strategy and the introduced critic network help to reduce the variance of zeroth-order gradient estimators and improve the sample efficiency and stability of the algorithm. We evaluate our proposed method using two different types of policies, linear policies and neural networks, on a range of challenging continuous control benchmarks, where ZOAC outperforms zeroth-order and first-order baseline algorithms.

Under review as a conference paper at ICLR 2022
ZEROTH-ORDER ACTOR-CRITIC
Anonymous authors Paper under double-blind review
ABSTRACT
Evolution based zeroth-order optimization methods and policy gradient based first-order methods are two promising alternatives to solve reinforcement learn- ing (RL) problems with complementary advantages. The former work with ar- bitrary policies, drive state-dependent and lemporally-extended exploration, pos- sess robustness-seeking property, but suffer from high sample complexity, while the latter are more sample efficient but restricted to differentiable policies and the learned policies are less robust. We propose Zeroth- Order Actor-Critic algorithm (ZOAC) that unifies these two methods into an on-policy actor-critic architec- ture to preserve the advantages from both. ZOAC conducts rollouts collection with timestep- wise perturbation in parameter space, first-order policy evaluation (PEV) and zeroth-order policy improvement (PIM) alternately in each iteration. The modified rollouts collection strategy and the introduced critic network help to reduce the variance of zeroth-order gradient estimators and improve the sam- ple efficiency and stability of the algorithm. We evaluate our proposed method using two different types of policies, linear policies and neural networks, on a range of challenging continuous control benchmarks, where ZOAC outperforms zeroth-order and first-order baseline algorithms.
INTRODUCTION
Reinforcement learning (RL) has achieved great success in wide range of challenging domains, including video games (Mnih et al. 2015). robotic control (Schulman et al., 2017), autonomous driv- ing (Kendall et al., (219)). etc. The majority of RL methods formulate the environment as Markov decision process (MDP) and leverage the temporal structure to design learning algorithms such as Q-learning and policy gradient (Sutton Barto 2018). Actor-critic methods are among the most popular RL algorithms, which usually introduce two function approximators, one for value func- tion estimation (critic) and another for optimal policy approximation (actor), and optimize these two approximators by alternating between policy evaluation (PEV) and policy improvement (PIM), On- policy actor-critic methods, e.g., A3C (Mnih et al. 2016) and PPO (Schulman et al., 2017), often crities to construct advantage functions and substitute them for the Monte Carlo return used in vanilla policy gradient (Williams) 1992). which significantly reduces the variance of gradient esti- mation and improve learning speed and stability. Among existing actor-critic algorithms, common choice is to use deep neural networks as the function approximators and conduct both PEV and PIM using first-order optimization techniques.
An alternative approach for RL, though less popular, is to ignore the underlying MDP structures and regard RL problems as black-box optimization, and to directly search for the optimal policy in a zeroth-order way, i.e., without using the first-order gradient information. Recent researches have shown that zeroth-order optimization (ZOO) methods, e.g.. ES (Salimans al. 2017) ARS (Mania) et al. 2018) 8) and GA (Such et al., 2017), are competitive on common RI. benchmarks, even when applied to deep neural network with millions of parameters. 700 has several advantages compared to first-order
RL methods (Schnke al. 20100] Salimans et al.) 2017: Such et al. 2017] Lehman et al. 2018 Khadka & Tumer 2018 Qian Yu! 2021): (1) ZOO is not restricted to differentiable policies: (2) ZOO perturbs the policy in parameter space rather than in action space, which leads to state-dependent and cmmporally-extender exploration; (3) Zeroth-order population- based optimization possesses monsttesss-eekinng property and diverse policy behaviors.
Despite these attractive advantages, the main limitation of ZOO is its high sample complexity and high variance of the parameter update process, especially in high-dimensional problems. Recent

---

Under review as a conference paper at ICLR 2022
researches have proposed various techniques to improve ZOO, e.g., using orthogonal or antithetic
sampling methods (Sehnke et al.; 2010; Salimans et al.) 2017 Choromanski et al. 2018 Mania
al. (0018) identifying a low-dimensional search subspace (Maheswaannathan al. 2019: Choro-
manski et al. 2019; [ener & Kolun 2020), or subtracting a baseline for variance reduction (Sehnke
al. 20T0] Grathwohl et al. 2018). One of the major reasons for the sample inefficiency of 700 is
its ignorance of the MDP temporal structures. Many recent researches have tried to combine ZOO
and first-order MDP-based RL into hybrid methods, e.g., run evolutionary algorithms in parallel with off-policy RL algorithms and optimize the population of policies with information from both sides (Khadka & Tumerr 2018 Pourchot & Sigaud 2018 Bodnar et al. (020), or inject parameter noise into existing RL algorithms for efficient exploration (Plappert et al. [0188] Fortunato et al.) 2018). However, existing hybrid methods still conduct first-order gradient- based policy improve- ment (at least as a part), which reimposes differentiable requirement on the policy.
In this paper, we propose the Zeroth- Teroth-Order Actor-Critic algorithm (ZOAC), which unifies first-order and zeroth-order RL methods into an actor-critic architecture by conducting first-order PEV to up- date the critic and zeroth-order PIM to update the actor. In such a way, complementary advantages of both methods are preserved, e.g., wide adaptability to policy parameterization, robustness seeking property, state- state-dependett and cemporally-extendee strategy from episode-wise perturbation in traditional zeroth-order methods to timestep-wise per- turbation, which results in higher sample efficiency and better exploration. We derive the zeroth- order policy gradient under this setting and point out that critic network can be introduced to estimate the state-value function and trade-off between bias and variance. We then propose a prac- tical algorithm that utilizes several parallelized rollout workers and alternates between first-order PEV and zeroth-ordes PIM based on generated experiences in each iteration. We evaluate ZOAC on a range of challenging continuous control benchmarks from OpenAl gym (Brockman et al., 2016), using two different types of policies, linear policies and neural networks. Experiment results show that ZOAC outperforms zeroth-order and first-order baseline algorithms in sample efficiency, final performance, and the robustness of the learned policies. We visualize the polices learned in an environment with sparse and delayed reward, which indicates sufficient exploration driven by pa- rameter noise in ZOAC. Furthermore, we conduct ablation studies demonstrate the indispensable contribution of the modified rollouts collection strategy and the introduced critic network to ZOAC.
exploration. We modify the rollouts collection
2
PRELIMINARIES
2.1 FROM POLICY GRADIENT TO ACTOR-CRITIC
In standard MDP-based RL settings, the environment is usually formulated as an MDP defined as (S, A. P. r). where S is the state space, A is the action space, P :S x A x S -> R is the transition probability matrix, : S x A + R is the reward function. The return is defined as the total discounted future reward G. - (r((s4i,,,++)
where 7 E (0, 1) is the discounting factor. The behavior of the agent controlled by a policy (a|s)) : 8 x A - [0, 1]. which maps states to probability distribution over actions. The state-value function is defined as the expected return under policy π starting from a certain state: (*(s) = Eawx {G, 8t = s). The goal of MDP-based RL is to find an optimal policy that maximizes the expectation of state-value function under certain state distribution. Denoting policy parameterized with @ as no. the objective function can be written as:
(O) = Eg-a (s)], d= do or dT
(1)
where do is the initial state distribution and a is the stationary state distribution of Markov chain under policy Te. Generally, the former is used for episodic tasks with finite horizon and the latter is used for continuing tasks with infinite horizon. For any differentiable policy ne, and for con- tinuing or episodic tasks, the same form of policy gradient can be derived from the policy gradient theorem (Sutton& & Barto 2018). This vanilla policy gradient given by Williams (1922 is as follows:
[o)r Es, To [G. Vo log no (0.
(2)
Vanilla policy gradient suffers from high variance since it directly uses Monte Carlo return from sampled trajectories. Actor-critic methods improved upon it, which usually introduce a critic net- work to estimate the value function and serve as baseline to substitute the expected return G, with a proper form of advantage function A,, for example, TD residual (Miih et al.) 2016). or gener- alized advantage estimation (GAB) (Schulman et al. 2015). However, the above policy gradient
2

---

Under review as a conference paper at ICLR 2022
based methods can only be applied differentiable policies, and may be unavailable when differentiable controller needs to be optimized.
2.2 EVOLUTION STRATEGIES
Existing ZOO methods focus on episodic RL problems with finite horizon and treat them as black- box optimization. In these cases, the length of trajectories is limited and the discounting factor usually set 1. Evolution strategies (ES) is one of the most popular algorithms of ZOO, which optimizes Gaussian smoothed objective function:
JES (0) (o. Bo [V (s)]
where dp is the initial state distribution and a is the standard deviation the Gaussian noise added to the policy. The zeroth-order gradient be derived using the log-likelihood ratio trick and the probability density function of Gaussian distribution (Nesterov & Spokoiny 2017):
V VoJEs(() - (0. [V (s)ec
(4)
In practice, the expectation over Gaussian distribution can be approximated by sampling noise samples {<:)imm,....n and the corresponding state value 7 can be approximated by the episodic return G, 2rrs,, of the sample trajectory of length T' collected with policy To+oc.:
VOJES
G&E:
(5)
YLO
The zeroth-order gradient estimator in Equation only relies on the episodic return of each evalu- ated random directions, so is applicable to non-differentiable policies. Besides, each perturbed pol- icy remains deterministic in one trajectory, which leads to state-dependent and smmoorall--xxtende exploration. Furthermore, the Gaussian smoothed objective also improves robustness of the learned policies in parameter space.
ZEROTH-ORDER ACTOR-CRITIC
3.1 FROM ES TO ZOAC
In this section, we will derive an improved zeroth-order gradient combining the actor-critic archi- tecture for policy improvement. We start from improving the sample efficiency and stability of ES. Most of the existing ES methods applied to RL optimize a deterministic policy (Salimans et al.) 2017 Mania al. 2018), where the exploration is driven by noise in parameter space. Without loss of generality, we follow them in the following derivations and algorithm design. A deterministic policy parameterized with is denoted Tog S A, which directly maps states to actions.
In ES, the policy is perturbed in parameter space at the beginning of an episode and remains un- changed throughout the trajectories. If large number of random directions is evaluated, the sample complexity will increase significantly. However, since the zeroth-order gradient is estimated as the weighted sum of several random directions, it exhibit excessively high variance when n is small (Berahas et al. 2202), which may greatly harm the performance. Therefore, it is essential to trade-off this contradictory between sample efficiency and variance.
To encourage sufficient exploration and low variance while maintaining high sample efficiency, here we consider perturbating the policy at every timestep, i.e., the Gaussian noise is sampled identically and independently at every timesteps. We regard it stochastic exploration policy 3 To+aes where é ~ A(00, I) is Gaussian noise in parameter space and a is the standard deviation. Our objective is to maximize the expectation of the state-valus under stationary distribution d of the ex- ploration policy 3. We can leverage Bellman equation to estimate the state-value via bootstrapping, in which the one-step reward can be replaced with sampled experiences:
(6) Since all the contents in the outer expectation E.-,o can be regarded as a function of e, the zeroth-order gradient of this objective function be derived in exactly the same way in ES.
JZoAC (0) = Eg, VV (s:) = E.-N((. E Ee [r(t, (otoe(s:)) + (V
3

---

Under review as a conference paper at ICLR 2022
Moreover, (st) can be subtracted as baseline for variance reduction because of its uncorrelation to in the outer expectation and the zero mean property of the Gaussian noise e:
VeJzOAc(0) = 1 Nt..1 1. ([r(:: ( + +VV
(7) Compared to ES which uses unbiased but high variance Monte Carlo return to evaluate each per- turbed policy, the performance each random direction here is estimated by one-step TD residual with low variance. In practice, common approach is introduce a critic network (s) to estimate the saaue function V which may lead to high bias in this form of advantage estimation.
(s))le
To trade-off between bias and variance, we consider extending our derivation further to the case where each perturbed policies (i.e., each sampled random noise) run forward N timesteps instead of one timestep only. Equation (7) can be extended to: Ve.zoAc(O))
N-1 Σ i=0
1 -. Ep
v (st) 7 To+oc($(+s)) + 7 V -
e)
where Ep refers to expectation over --step transition dynamics. Similar to one-step case, the cumulative reward within N step can be estimated from sampled experiences when 8, is the first state of the trajectory fragment collected with certain perturbed policy To+oc- By introducing a critic network and choosing an appropriate length N, this N-step residual advantage function contributes to achieving good trade-off between the bias and variance.
3.2 ANALYSIS ON VARIANCE OF GRADIENT ESTIMATORS
We analyze the variance of these two types of gradient estimators, ZOAC gradient and ES gradient. The budget of timestep of one trajectory N x H is identical for both algorithms: in ZOAC, each perturbed policy run forward N steps, and H is the number sampled random directions one trajectory; in ES, only one perturbed policy is sampled and run forward N x H steps. If we denote the accumulative reward obtained within N x H timesteps in ES NH and the N-step TD residual ZOAC as AN Fetes We can then estimate the zeroth-order gradient according to Equation 4 and g respectively:
VaJES(()
(9)
no
ve.2OAc(()) nHo
Totors AN
E
(10)
We now give the upper bound of variance for these two gradient estimators. Variance is defined
as the trace of the convariance matrix of gradient vectors Var(g) = Σ Elg;] - (Eg))? where
(g1. 92..... 9a) (Zhao et al. 2011). We can derive the variance bound as follows if both the reward and the critic network output is bounded (detailed derivation is provided in Appendix A.3 vectors are bolded in the appendix for clarity but not in the main text).
Theorem 1. If the reward (rss, a)l < a, the critic network output (V((s)) < B, and n trajectories with length of N x H timesteps are collected in one iteration, the upper bounds of the variance for gradient estimators (Equation 4 and (70)) are:
Var(VoJEs(0]] 1-7-" -H)adad
(11)
noa 7)
Var Vor(Vo)zo (11 Ja + (1- (1 nHo? 7
(12)
We can compare their variance in more intuitive way: if N H 1000, 7 0.99, and assume that / 1-y; the difference of variance bounds becomes Var Var[Vo]JoAcl
Var (ar((oJss(())) s (1 - 1) 1000002d which decreases with H and drops below zero when 4 < H < 1000 (i.e., N smaller than 250). This suggests that although same amount of data is collected, an appropriate rollout length N can indeed reduce variance of the gradient estimators. Besides, both variance bound inversely proportional n, which urges us collect trajectories.
4

---

Under review as a conference paper at ICLR 2022
Ohnond Rottowo))
Balbots
Belense Nikef Roun
War lie
7:4
11
Pelax (6) Foal000) (0
SUN
S2/H-1W
ZOAC
Relow (1) Foatt
Sun
Conditann
(a) Overall framework of ZOAC
(b) Rollouts collection strategies: ES vs. ZOAC
Figure I: (a) The overall framework of our proposed algorithm ZOAC; (b) Comparison of rollouts collection strategies (with parallelized samplers): On the top is ES, which performs spisode-wiss. perturbation; on the bottom is ZOAC, which performs N timestep-wise perturbation.
3.3 PRACTICAL ALGORITIIM
We propose the Zeroth-Order Actor-Critic (ZOAC) algorithm, which unifies first-order and zeroth- order methods into an on-policy actor-critic architecture by conducting rollouts collection with timestep-wise perturbation in parameter space, first-order policy evaluation (PEV) and zeroth-order policy improvement (PIM) alternately in each iteration. The overall framework of ZOAC is shown in Figure La and the pseudocode is summarized in Appendix A..I] In each iteration, parallelized workers will collect rollouts in the environment with perturbed policies, then the agent train the critic network to estimate state-value function under the exploration policy, and finally improve the policy along the zeroth-order gradient direction.
Rollouts collection. The rollouts collection strategy is illustrated briefly in Figure lb which is parallelized version with workers. If we denote the 1-th state sampled by the i-th worker as 8ts. the rollout strategy can be described as: when reaching states in (*t,NN J. where j E N, new random direction et, is sampled and the behavior policy perturbed: when reaching other states, the deterministic behavior policy remains unchanged. It's worth noting that the notation is only for continuing case where an episode never done. In episodic tasks, the rollout length S Ni. S N actually varies between different perturbed policies T0+oeu, since an episode may terminate at any time. However, we still use N to denote the rollout length of each perturbed policy for brevity.
A limit case of our proposed strategy is that when N is chosen the episode length and the critic network turned off (i.e., (s) = 0), the algorithm actually degenerate into ES, since all perturbed policies are evaluated by running whole episode, and the episodic return is used the fitness score.
The state-value function (s) can be estimated by jointly optimized critic network Vo (s), which aims to minimize the MSE loss between the network output and state-value larget. In each iteration, in total n x N x /l states and the corresponding target values (s, G) are calculated and used for critic training. In trajectory with length T. the target value G, for each state 8, calculated as (Schulman et al. 2015 Andrychowicz al. 202T):
First-order PEV.
T --1-1
= =
+
Σ (nA)<rr4* + VV. Vn (8++a))
(13)
k=0
where 0 < À < 1 is hyperparameter control the trade-off between bias and variance of the value target. In Figure Ia] the one-step TD residual of each state is denoted as for simplicity. The objective function of PEV can be written as:
Jeritie (w)= = (v) { ap)
(14)
In practice, the critic network is constructed as neural network and updated through several epoches of stochastic gradient descent in each iteration.
5

---

Under review as a conference paper at ICLR 2022
4.00
2075
2004
5000
500C Libeer
2000
Jound
300
Sredkes
Ievelags
Figure 2: Learning curves on MuJoCo benchmarks. Exploration noise are turned off for evaluation. The solid lines correspond to the and the shaded regions the 95% confidence interval 5 trials using fixed set of random seeds. All curves are smoothed uniformly for visual clarity.
Table 1: Max total average return within certain environmental steps (te over 5 trials).
Environment
Inv.D.P.-v2
Hopper-v2
HallCheetah--2
Ant-v2
Timesteps
le6
2e6
2c6
2c7
ZOAC(Linearr
9359.93-10.01
3333.60:197.85
1990.82:119.99
4495.33
ZOAC(Neural)
9339.66::5.29
3195.15=91176
5339.95=140.46
4292.09=108.69
ARS(Linear)
9359.86=0.06
2891.281:305.1
2967.98-889.42
3427.85=765.62
ES(NNural)
9155.73++404.25
1065.34+49.14
2349.11+444.77
3274.89+551966
PPO(Neural)
$350.89-10.04
3178.60+270.09
5219.61
3796.13=754.78
Zeroth-order PIM. We calculate the zeroth-order gradient with n x random directions and
the corresponding advantage function as (c, A). Similar to state value estimation, we leverage the generalized advantage estimation (GAE) trick (Schulman et al., 2015) to further control the bias- variance trade-off. We also perform advatage normalization to ensure consistent gradient length during training. Following the notations in Figure [bb the advantage function be written
N
T9 Feii AN
(TA) 7V (V - - (s(.
(15)
k=
where À is the same in Equation weighted sum of the sampled random directions:
The zeroth-order gradient can be then estimated as the
VgJactor (0)
tosis eij An
(16)
nHa
4 EXPERIMENTS
4.1 PERFORMANCE EVALCATION
We evaluate the performance of ZOAC the MuJoCo continuous control benchmarks Todorov et al., 2012) in OpenAl Gym (Brockman et al. 2016). We choose Evolution Strategies (ES) (Sali- mans et al. 2017 Liang al. 2018) and Augmented Random Search (ARS) (Mania al. 2013 as veroth-order baselines and proximal policy optimization (PPO) (Schulman et al. 201 Rafiin et al. 2019) as a first-order actor-critic baseline.
We use two different types of policies: linear policies for ARS and ZOAC (linear), neural networks with (64, 64) hidden nodes and tanh nonlinearities for ES, PPO and ZOAC (neural). For a fair comparison, we enable observation normalization for all methods, which has been proved effective no matter in first-order methods or zeroth-order methods (Mania et al. 2018 Andrychowicz et al.) 2021). When using neural networks as actors, we also use layer normalization (Ba et al. 2016) in ZOAC and virtual batch normalization in ES (Salimans et al.) 2017). Both of them ensure the diversity of behaviors among the population, while the former is less computationally expensive. We summarize the implementation details of ZOAC Appendix Am. follow the recommended hyperparameter settings listed in the related papers or code repositories.

---

Under review as a conference paper at ICLR 2022
200C Beuurall
20AL (Lnnaa))
AMS (iisea))
Es (Nuural 25 256.29x44
PRO (Neura))
Augit 17
Avg $8.
Aug 27.07774
0.25
-02
-694
6.75
8.5
3.1
3.0 0.0
Figure 3: Visualization of the policies learned by different methods on MountainCarCCmtinunn Color represents the action output, from -1.0 (red) to 1.0 (blue). The horizontal lines in solid indi- cate the initial car position distribution the goal > 0.45. The dashed curves are trajectories starting from the same initial state.
U-6.,6, -0.4), and the vertical lines in solid indicate
Table 2: Robustness comparison of the learned policies on HalfCheetah-v2. Best performing poli- cies from Figure are tested (4e7 timestep limitation for ARS and ES). Each policy is evaluated on 400 trajectories the same environment and the average return over policies are listed.
Noise type ZOAn(L))ear)
No extra noise
Obs. noise (a = 0.1)
Para. noise (a 0.05)
4909.53
4402.54 (-10.3%)
3289.15 (-33.0%)
ZNAC(Neural)
5179.39
5057.07 (-2.4%)
4247.08 (-18.0%
ARS(Linear)
4529.30
1771.23 (-60.9%)
1724.40 (-61.9%)
ES(Neural) 5478.01
4550.22 (-16.9%)
1527.93 (-72.1%%
PPO(Neural) 4668.55
3342.23 (-28.4%)
972.08 (-79.2%)
presents presents the learning curves four continuous control tasks. Table [ummarriee max total average return within the timestep threshold over trials. Additional results including state-valus estimation and performance comparison of different policies are attached in Appendix and
Figure 2
ZOAC matches or outperforms baseline algorithms across tasks in learning speed, final performance, and variance trials. One thing worth mentioning is that both the zeroth-order baseline methods perform reward shaping to resolve the local optima problem: ARS subtracts the survival bonus from rewards (I in Hopper and Ant), while ES transforms the episodic returns into rankings. Although these tricks improve the performance, they also alter the update directions of the policies and make difficult determine what is the real objective function being optimized. ZOAC, however, sur- passes ES and ARS without relying specific exploration tricks, which can be attributed to the introduction of critic network and the construction of advantage estimations policy improvement.
Robustness Comparison. The objective function of ZOAC aims to maximize the expected state- value of the stochastic behavior policy that contains parameter noise all the time, which intuitively encourages the agent to find wider optima and leads to better generalization and robustness. Hence, we evaluate the learned policies under two types of noise, observation noise and parameter noise. Extra observation noise is added to the normalized observation each timestep. which leads to a slightly different observation distribution. Extra parameter noise is added at the beginning of each trajectories, which pushes the learned policy to its neighborhood. The result in HalfCheetah- v2 is presented in Table 2 Results show that in general the policies learned by ZOAC possess higher robustness against both observation noise and parameter noise, which can be ascribed to the obbustness-seeking fragile and suffer significant performance degradation under extra noise, far inferior to the linear ones learned by ZOAC. Additional results and discussions attached in Appendix A.5
property of method. The linear policies learned by ARS seem very
Visualization of the learned policies. In order to intuitively observe the behaviors of the learned policies, we apply all methods on KountainCarComiinuuus only when it achieves the goal and penalized by the action output at every timestep. Policy gradient methods usually struggle on this problem because the reward sparse and delayed, while zeroth- order methods can better handle reward sparsity by nature. We visualize the policies learned by each algorithm in Figure 3 Among these learned policies, the neural policy learned by ES obtains the highest average return, while the neural policy learned by ZOAC obtains the second highest average
in which the car is rewarded +100
7

---

Under review as a conference paper at ICLR 2022
(100)
ND Eoserrmmnnton
130
14 303 (oal) 9o 1607)
400 80
Figure 4: Influence of the rollout length N with each perturbed policies.
Figure 5: Ablation studies on ZOAC with neural network (left) and linear poicy (right).
return within the shortest episode length. The latter has similar but much steeper terrain compared to the former one and implies a larger control action in most areas. As for linear policies, the one learned by ZOAC also tends to achieve the goal in a shorter episode length than the one learned by ARS. We attribute this to the usage of discounting factor, which pushes the agent to perform higher actions and achieve the goal as early as possible. ZOAC outperforms PPO both in final performance and training stability over different random seeds, due to its state-dependent exploration in parameter space, which is more efficient than action noise and is essential to solve this task.
4.2 ABLATION STUDIES
Appropriate rollout length. As illustrated in Section 3.2 choosing appropriate rollout length N of each perturbed policies may achieve a good trade-off between bias and variance. We perform an ablation study to understand the effect of timestep-wiss perturbation strategy and choice of N. We compare ZOAC and ARS on HalfChectah-v2, the former conducting timstep-wise perturbation and the latter conducting episode- -wise perturbation. We use linear policies in both methods and set hyperparameters to the same, including the standard deviation of parameter noise a, the learning rate of policy Oacttor and also the budget of timesteps within one iteration. Figure 4 shows the influence of N performance. Results show that under this setting, both 10 and 20 are good choices for N which lead to better performance, while other two choices, 5 and 50, perform similarly to ARS. Note that here we sample as many experiences as ARS per iteration for comparison, while in practice, the number of timesteps collected in each iteration is highly tunable in ZOAC. In fact, we found that rollout length N in large range, approximately from 5 to 50, perform quite well across tasks.
Analysis on different components. To evaluate the contribution of each individual component and also the potential of additional techniques, we perform ablation studies and present the results in Figure 5 Results demonstrate that critic network is a crucial part of ZOAC, i.e., N-step accu- mulative reward without bootstrapping is not sufficient to guide policy improvement. Observation normalization technique is also essential to zeroth-order methods, which helps to generate diverse policies via isotropic Gaussian noise. Besides, GAE trick and layer normalization trick slightly im- prove the performance. Mania et al. (2018) propose to use only the top performing directions in policy update to relieve the bad influence of noisy evaluation results and validate its effectiveness on ARS. Here we perform similar direction sifting technique, using only the directions that have the highest advantage in policy improvement, but it seems to pull down the learning performance of ZOAC. Moreover. results show that additional action noise is not helpful to the performance, indicating that the exploration driven by parameter noise is sufficient.
5 RELATED WORK
ZOO and its applications in RL. At each iteration, ZOO samples several random directions from a certain distribution, and then the distribution is updated according to the evaluation results over these directions. [Shnnee et al. (2010) derive parameter-exploring policy gradients (PGPE) for episodic RL problems, which has reduced variance and higher performance than vanilla policy gradient. [Salimans et al. (201)) and Such et al. 2017) propose highly scalable evolution strategies (ES) and genetic algorithms (GA) respectively, both of which can be applied to deep neural networks and achieve competitive performance with MDP-based RL algorithms. Mania et al. (2088) propose
8

---

Under review as a conference paper at ICLR 2022
augmented random search (ARS), which applied ZOO linear policies with techniques including observation normalization, reward scaling, top performing directions sifting, and achieve astonishing performance RL benchmarks considering its simplicity. ZOO has regained popularity in recent years because of its special advantages when applied in RI, including wide adaptability to policy parameterization (e.g., deterministic or stochastic, differentiable non-differentiable), robustness seeking property, state-dependent and temporally-extended exploration.
Improved techniques for ZOO. The main limitation of 700 is its high sample complexity. Re- searchers have proposed various improved techniques for ZOO from different perspectives. One way is to adopt advanced Monte Carlo sampling methods to reduce variance of the zeroth-order gradient estimation, e.g., antithetic sampling (Sehnke et al. Salimanss et al., 2017 Mania et al. 2018), orthogonal and Quasi Monte Carlo exploration (Choromanski et al. 2018). Constructing control variates (i.e., subtracting a baseline) is another popular variance reduction technique. /Sehnke et al. (210)) adopt moving-average baseline in PGPE heuristically, while Zhao et al. (2011) derive the optimal baseline for PGPE in an analytical form that minimizes the variance. Moreover, the sample complexity of zeroth-order methods will further increase with the dimension of the optimization problem (Nesterov & Spokoiny (017). therefore some researches aim to identify low-dimensional search space and guide the search towards faster convergence. Guided ES (Maheswaranathan al.) 2019) and ASEBO (Choromanski et al. 2019) are proposed based on a similar idea: to identify linear subspaces and adapt the search distribution from recent history of descent directions. [Sener & Koltun (2020) propose LMRS, which uses more expressive neural networks to represent subspaces and jointly learns the underlying subspace and optimizes the objective function.
Hybridization of ZOO and first-order MDP-based RL. These two methods have complemen- tary advantages when applied RL problems, and recent researches have tried combine them for better performance. Khadka & Tumer (2018) propose the ERL framework that runs evolutionary algorithms (EA) and DDPG (Lillicrap et al. 2015) concurrently with bidirectional information flow, i.e., the DDPG agent is trained with experiences generated by the EA population and reinserted into the population periodically to guide the evolution process. CEM-RL (Pourchot & Sigaud/ (0088) and Proximal Distilled ERL (Bodnar et al., 2020) adopt similar hybridization framework, but use differ- ent algorithms as components and improve training techniques. Fortunato et al. (2018) and Plappert et al. 2018 inject parameter noises into existing first-order MDP-based RL algorithms to drive more efficient exploration, and demonstrate that existing RL algorithms can indeed benefit from parameter space exploration through comparative experiments. Some other hybrid methods (Grathwohl et al. 2018 Tang et al. 2020) leverage policy gradient and reparameterization trick to construct control variates, which leads to unbiased, low variance gradient estimators. Our proposed method, however, unifies first-order and zeroth-order methods into an on-policy actor-critic architecture by conducting first-order PEV and zeroth-order PIM alternately in each iteration. The state-value function network does not only serve as a baseline to reduce variance, but also as a critic used for bootstrapping, which leads to reduced variance and accelerated learning (Sutton & Barto 2018). The policy is updated in a zeroth-orde oorderrorrrrrro way, which implies wide adaptability to different forms of policies.
CONCLUSION
In this paper, we propose Zeroth-Order Actor-Critic algorithm (ZOAC) that unifies evolution based zeroth-order and policy gradient based first-order methods into an on-policy actor-critic architecture to preserve the advantages from both, including the ability to handle different forms of policies, state- dependent exploration, robustness-seekin property from the former and high sample efficiency from the latter. ZOAC conducts rollouts collection with timestep-wise perturbation in parameter space, first-order policy evaluation (PEV) and zeroth-order policy improvement (PIM) alternately in each iteration. Experimental results in range of challenging continuous control tasks show that ZOAC outperforms keroth-orde and first-order basclines. Robustness analysis and ablation studies on hyperparameters and components also performed to show the properties of ZOAC.
Moreover, our methods achieve such improvement while still using traditional isotropic Gaussian noise for perturbation, in principle those improved techniques for ZOO from sampling perspec- tives can be further integrated, e.g., Monte Carlo sampling techniques, cow-dimensional subspace identification, adaptive perturbation scale, which may lead to even higher performance.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY
The code of ZOAC will be released after the author notification in https://annt /atp::/s///oommouss. 4cpen. www.sscceieeeeenieeeeeeeee Order Crctoor-Criiiiiii 1A71 We summarize the algorithm in Appendix A. and describe the implementation details in Appendix A.2
REFERENCES
Marcin Andrychowicz, Anton Raichuk, Piotr Stañczyk, Manu Orsini, Sertan Girgin, Raphaël Marinier, Leonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What matters for on-policy deep actor-critic methods? large-scale study. In International Conference on Learning Representations, 2021.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 064500, 2016.
Albert Berahas, Liyuan Cao, Krzysztof Choromanski, and Katya Scheinberg. A theoretical and empirical comparison of gradient approximations in derivative-free optimization. Foundations of Computational Mathematics, pp. 1-54, 2021.
Cristian Bodnar, Ben Day, and Pietro Lió. Proximal distilled evolutionary reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 0283-3290, 2020.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.0154: 2016.
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani. Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In International Conference on Machine Learning, pp. 970-978. PMLR, 2018
Krzysztof Choromanski, Aldo Pacchiano, Jack Marker-Holder. Yunhao Tang, and Vikas Sindhwani. From complexity to simplicity: Adaptive es-active subspaces for blackbox optimization. Ad- vances Neural Information Processing Systems, 32: 10399, 2019.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Os- band, Alex Graves, Volodymyr Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg. Noisy networks for exploration. In International Conference on Learning Representations, 2018.
Will Grathwohl, Dami Choi, Yuhuai Wu, Geoff Roeder, and David Duvenaud. Backpropagation through the void: Optimizing control variates for black-box gradient estimation. In International Conference on Learning Representations, 2018.
Alex Kendall, Jeffrey Hawke, David Janz, Przemyslaw Mazur, Daniele Reda, John-Mark Allen, Vinh-Dieu Lam, Alex Bewley, and Amar Shah. Learning to drive in a day. In 2019 International Conference Robotics and Automation (ICRA), pp. 8248 8254. IEEE, 2019.
Shauharda Khadka and Kagan Tumer. Evolution-guided policy gradient in reinforcement learning- In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 1196-1208, 2018.
Joel Lehman, Jay Chen, Jeff Clune, and Kenneth O Stanley. Es more than just a traditional fiite-ddifference approximator. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 450-457, 2018.
Eric Liang, Richard Liaw, Robert Nishihara, Philipp Moritz, Roy Fox, Ken Goldberg. Joseph Gon- zalez, Michael Jordan, and Ion Stoica. Rllib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning, pp. 3053-3062, PMLR, 2018.
Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint /509:v5500.000 2015.
10

---

Under review as a conference paper at ICLR 2022
Niru Maheswaranathan. Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: Augmenting random search with surrogate gradients. In International Conference Machine Learning, pp. 4264 4273. PMLR, 2019.
Horia Mania, Aurelia Guy, and Benjamin Recht. Simple random search of static linear policies is competitive for reinforcement learning. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 1805-1814, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 5333, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pp. 1928-1937. PMLR, 2016.
Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang. William Paul, Michael I Jordan, et al. Ray: A distributed frame- work for emerging {AI} applications. In 13th {USENIX) Symposium on Operating Systems Design and Implementation ( ({OSDI) 18), pp. 561-577, 2018.
Yurii Nesterov and Vladimir Spokoiny. Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2):227-566, 2017.
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marein Andrychowicz. Parameter space noise for exploration. In International Conference on Learning Representations, 2018.
Alois Pourchot and Olivier Sigaud. Cem-rl: Combining evolutionary and gradient-based methods for policy search. arXiv preprint ArXiv:1810.0122 2018.
Hong Qian and Yang Yu. Derivative-fre reinforcement learning: A review. arXiv preprint
arXiv:2102.05710 2021.
Antonin Raffin, Ashley Hill, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, and Noah Dor- mann. Stable baselines3. Gitffub repository, 2019.
Tim Salimans, Jonathan Ho, Xi Chen, Szymon Sidor, and Ilya Sutskever. Evolution strategies scalable alternative to reinforcement learning. arXiv preprint arXiv:/703.03888 2017.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High- dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.02433: 02438. 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707.06377 2017.
Frank Sehnke, Christian Osendorfer, Thomas RückstieB, Alex Graves, Jan Peters, and Jürgen Schmidhuber. Parameter-exploring policy gradients. Neural Networks, 23(4):551-55) 2010.
Ozan Sener and Vladlen Koltun. Learning to guide random search. In International Conference Learning Representations, 2020.
Felipe Petroski Such, Vashisht Madhavan, Edoardo Conti, Joel Lehman, Kenneth O Stanley, and Jeff Clune. Deep neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning, arXiv preprint arXiv:1712.06566 2017.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Yunhao Tang, Krzysztof Choromanski, and Alp Kucukelbir. Variance reduction for evolution strate- gies via structured control variates. In International Conference on Artificial Intelligence and Statisties, pp. 646-656. PMLR, 2020.

---

Under review as a conference paper at ICLR 2022
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. IEEE, 2012.
Ronald J Williams. Simple statistical gradient-folloingg algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 1992.
Tingting Zhao, Hirotaka Hachiya, Gang Niu, and Masashi Sugiyama. Analysis and improvement of policy gradient estimation. Advances Neural Information Processing Systems, 24:262-22 270, 2011.
12

---

Under review as a conference paper at ICLR 2022
A
APPENDIX
A.1 PSEUDOCODE OF ZOAC
Algorithm Zeroth- Oerohh-rrderra Actor-Critic (ZOAC)
1: Initialize: policy parameters 0, critic network parameters w
2: for each iteration do
3: for each worker i = 1,,,, 2,..... do
4: for j = 0, 1, H - do
5: Sample f (N, 7)
6:
Run perturbed policy agtoes, in environment for timesteps
7:
Compute advantage function 1 according to Equation 15
8:
end for
9:
Compute the state-value target G for each state 8 according to Equation 13 end for
10:
11:
Collect (s, G) for critic update and (c. A) for actor update
12: Update w with batch size L through SGD by minimizing Equation 14 for M epoches
Update 0 along the zeroth-order gradient direction estimated in Equation (16)
14:
end for
A.2 IMPLEMENTATION DETAILS
We implemented ZOAC with parallelized workers (Algorithm 1 using the distributed framework Ray (Moritz et al. 2018). We follow the parallclization techniques used in ES (Salimans et al. (017)) and ARS (Mania et al. 2018). Firstly, created a shared noise table before training starts, then the workers communicate indices the shared table but not the perturbation vectors, so as to avoid high communication cost. Besides, random seeds for constructing parallelized training environments and the evaluation environment are different and generated from a single seed designated before hand.
We use two different types of policies: linear policies for ARS and ZOAC (linear), neural networks with (64, 64) hidden nodes and tanh nonlinearities for ES, PPO and ZOAC (neural). For actor-critic algorithms,
neural networks with (256, 256) hidden nodes and tanh nonlinearities critics to estimate state-value function.
Both the zeroth-order baseline methods perform reward shaping resolve the local optima problem as described in the original paper: ARS subtracts the survival bonus from rewards (1 in Hopper and Ant), while ES transforms the episodic returns into rankings. ES further discretize the actions to encourage exploration in Hopper but we do not reserve this trick for comparison since discretization will lead different policy architecture.
We summarize the hyperparameters used in ZOAC in Table B and list their values that are used to produce the results Figure We tune several important hypermarameters (n, N, H, σ) via coarse grid search and select the best performing setting to produce the final results. During evaluation, exploration noise are turned off and the reported total average return averaged over 10 episodes. Table summarizes the maximum value of the total average return within the timestep threshold, averaged over 5 trials.
A.3 DERIVATION OF THE VARIANCE BOUND
Theorem 1. If the reward r(s,a))= < the critic network output (V)(s)) < B, and n trajectories with length of x H timesteps are collected in one iteration, the upper bounds of the variance of gradient estimators (Equation 9 and (70) are:
NH)202d
Var (o) 5 no 7
(11 - N + (1 (1- (1-
Var Vor
nllo=(1-7}
13

---

Under review as a conference paper at ICLR 2022
Table Hyperparameters of ZOAC for the learning curves shown in Figure
Environment
Inv.D.P.vv2
Hopper-v2
HalfCheetah-v2
Ant-v2
Policy type
Linear
Neural
Linear
Neural
Linear
Neural
Linear
Neural
Num. of workers n
4
4
8
Rollout length N
10
20
10
20
20
Train frequency H
16
16
32
16
256
Para. noise std. o
0.02
0.04
0.04
0.06
0.02
Batch size L
64
128
Num. of epoches M
8
4
Actor optimizer
Adam((accto = 0.005, 31 0.9, Bg 0.999)
Critic optimizer
Adati
0.0003, [1 0.9, 12 0.999)
Discount factor 7
0.99
GAE coeff.
0,95
Proof. (1) Variance bound for ES gradient estimators
Under the setting described in Section 3.2 the state-value under policy Te+oe is estimated by the accumulative return over NH timesteps. which is denoted V The isotropic Gaussian noise added to the policy can be presented
(c1, -., (.,,, ca) where 6 ~V 1), (1,2.-.,d)
d
Var NH
cl
S
B[
E
NH
d
NH
p(e))
Σ
7
1-1 ((s))
ef
d
(NH
2
p(())
Σ
1-1
a
ida
1=1
(1 - N2
p(e))e
(1->)² 7)2
1 NH
Σ
B
(1 - 7)²
(1 - N1-
7)-
The last equality holds because of (1) when e (0, 1), and B[e]] for all 1. Since random directions is sampled and evaluated, the ES gradient estimator is given according to Equation
VoJ 0 no
Therefore the variance bound for ES can be derived as in Theorem 1:
Var[VoJEs(0)]
n Varl no- E] NH
NH )2 2 (1 - 7)
(2) Variance bound for ZOAC gradient estimators
Under the setting described in Section 3.2 the performance under policy mo+ae is estimated by the Ststep TD residual, which is denoted as A ... The isotropic Gaussian noise e is added to the policy well.
14

---

Under review as a conference paper at ICLR 2022
Var[A
6) 5
Σ
((())
Σ
x r(8t, + ( Vur(S+NN) Vio(bi) ed
1=1
1=1
/ p(())
Σ)
Σ x a (1 (1+
Gdd
1=1
7 )a + - (1 + )8 2
/
Σ
p(ei)efde
(1-?)
1=1
1 ja + (1- + +
2
d
(1-7)
Totally H. random directions is sampled and evaluated, and the ZOAC gradient estimator is given according to Equation (TOh:
VaJzonc(0)) nHa
A
N
Therefore the variance bound for ZOAC can be derived:
Ver(Ve = nHo? Var ( [
((1 a + (1 - 7) x )
nHo? -1 7)
A.4 STATE-VALUE FUNCTION ESTIMATION
Hoppard
-253
DOAC T960
-08
Figure 6: Average state-value estimation difference Vi((s (*e(s) in evaluation during training Figure 2 The solid lines correspond to the mean and the shaded regions the 95% confidence interval over 5 trials using fixed set of random seeds. All curves are smoothed uniformly for visual clarity.
We plot the average state-value estimation difference (s) (s) V*) in evaluation during training in Figure Since we turn off the exploration noise for evaluation, which means that the trajectories are collected under the deterministic policy na, the discounted sum of reward-to-go can be regarded estimate of the true state-value.
Results show that the critic networks converge, but in most cases to an underestimated value. This is because the critic network is trained to fit the state-value function / (s) of the stochastic exploration policy 33 rather than V (s) of the deterministic policy To. The underestimate bias vary in different tasks and when using different forms of policies, which is related to the local shape of the optima found by the RL agent. However, due to the objective function used in ZOAC, intuitively, the agent tend to find wide optima during training, which finally result in more robust policies.
15

---

Under review as a conference paper at ICLR 2022
A.5 ADDITIONAL RESULTS OF ROBUSTNESS COMPARISON
Table the result of robustness comparison in all tested MuJoCo environments, Results show that general neural policies are more robust, which can be ascribed their strong expressive ability. InvereedDouhlePenduuum-
is the exception, in which the robustness of the neural network policies no where near the linear ones, no matter what RI. algorithms used. Since this environ- ment is the simplest one among these environments, we guess that this is due to the overfitting of neural networks, and that matrix is enough to represent an optimal policy.
When comparing between linear policies, the policies learned by ZOAC yield higher robustness to both observation noise and parameter noise in environments, compared to those learned by ARS. One possible reason is that ARS subtracts the survival bonus from rewards, which actually alter the objective function being optimized, as described in Section 4.1 As for neural policies, the policies learned by 7OAC also shown be more robust both observation noise and parameter noise. One reason that parameter noise used zeroth-order methods encourages the agent to find a wide optima which is robust to parameter perturbations, while gradient-based methods focus on the performance of a particular point. Besides, ZOAC perform timestep-wise perturbation rather than episode-wise perturbation, which explores along more random directions and collects more diverse trajectories (i.e., data) than ARS or ES. All these features finally lead to better generalization and robustness of the policies learned by ZOAC.
Table 4: Robustness comparison of the learned policies. Best performing policies from Figure 2 are tested (4e7 timestep limitation for ARS and ES HalfChectah-v2 and Ant-v2 till convergence). Each policy is evaluated on 400 trajectories in the same environment (using the same random seed that has never been used during training) and the average return over policies are listed.
Env.
Noise type ZOAC(Linear)
No extra noise
Obs. noise 0.1)
Para. noise (a 0.05)
8744.11
8615.50 (-1.5%%
3643,49 (+58.3%)
ZOAC(Neural)
8419.16
908.95 (-89.2%)
1344.54 (-84.0%)
I.v.D.P.
ARS(Linear)
8883.13
8339.77 (-6.1% (6)11)
3396.74 (-61.8%)
ES(Neural)
7333.34
3593.76 (-51.0%)
927.02 (-87.4%)
PPO(Neural)
7477.48
3537.34 (-52.7%)
3115.82 (-58.3%)
ZOAC(Linear)
2885.10
2733.24 (-5.3%)
1872.07 (-35.1%)
ZOAC(Neural)
2417.33
2284.12 (-5.5%)
1644.34 (-32.0%)
Hopper
ARS(Linear)
2587.06
1194.43 (-53.8%)
781.99 (-69.8%)
ES(Neural)
1443.77
1330.98 (-7.8%)
915.38 (-36.6%)
PPO(Neural)
2596.02
2185.02 (-15.8%)
395.80 (-84.8%)
ZOAC(Linear)
4909.53
4402.54 (-10.3%)
3289.15 (-33.0%)
ZOAC(Neural)
5179.39
5057.07 (-2.4%)
4247.08 (-18.0%)
HalfC.
ARS(Linear)
4529.30
1771.23 (-60.9%)
1724.40 (-61.9%)
ES(Neural)
5478.01
4550.22 (-16.9%)
1527.93 (-72.1%)
PPO(Neural)
4668.55
3342.23 (-28.4%)
972.08 (-79.2%)
ZOAC(Linear)
4134.79
3460.67 (-16.3%)
29011.51 (-170.2%)
ZOAC(Neural)
4013.57
3650.79 (-9.0%)
976.57 (-75.6%)
Ant
ARS(L.inear)
3749.73
2868.18 18 (-23.5%)
-2669338 (-213.9%)
ES(Neural)
4029.82
3902.70 (-3.2%)
970.30 (-75.9%)
PPO(Neural)
3103.79
2792.79 (-10.0%)
393.20 (-87.3%)
A.6 PERFORMANCE COMPARISON OF DIFFERENT POLICY PARAMETERIZAATIONS
The derivative-free nature of 7OAC allows us to estimate the zeroth-order policy gradient im- prove the policy without considering the specific policy architecture. Hence, ZOAC can be applied seamlessly to arbitrary parameterized policies theory.
We further apply ZOAC two more different policies and conduct additional experiments on the same environments with four different policies, from fewer parameters to more parameters: Toeplitz matrix, matrix, network with (64, 64) units, network with (128, 128) units, and to the perfor- mance of ZOAC when optimizing these policies. We listed the dimension of the parameter space of different policies in Table
16

---

Under review as a conference paper at ICLR 2022
Toeplitz matrix is kind of compact policies with parameter sharing schemes, each element depends only on the difference between the row index and the column index. A general dense matrix M E Rm** has
parameters. while a Toeplitz matrix T E Rmxx has only + n 1 parameters. Since a general dense matrix performs quite well all tested environments, we wonder whether a more compact policy still work. Besides, as derived in Theorem the variance bound of zeroth- order gradient increases proportional to the dimension of parameter space, and it is common view that zeroth-order methods are more suitable for iow-dimensional problems. We wonder whether larger network will improve or harm the performance.
We use the same of hyperparameters for linear policies, and another set for networks, as summa- rized in Table 3 Results in Figure show that a Toeplitz matrix can obtain average return around 2000 in challenging environments like HalfCheetah-v2 and Ant-v2 with only very few parameters. However, it is far inferior to general dense matrix, indicating that this type of policy is not suffi- cient to represent an optimal policy. Network with (64, 64) and (128, 128) hidden nodes performs quite similarly to each other.
The additional results demonstrate the wide adaptability of ZOAC to different forms of policies. Zeroth-order policy update makes it very useful when gradient information is hard to obtain or even unavailable, like low precision neural networks, hierarchical policies, or even rule-based controllers. In the future, may apply ZOAC to specific problems where first-order methods not handle and to improve existing results where the policies are trained with traditional zeroth-order methods like ES and ARS.
Table 5: Dimension of the state space, action space and parameter space different policies.
Environment
ww..Do.Pen..v2
Hopper-v2
HalfCheetah-v2
Ant-v2
State space Action space Toeplitz matrix Matrix Network (64, 64) Network (128, 128)
11
11
17
111
8
11
13
22
118
11
33
102
888
4993
5123
5702
11848
18177
18435
19590
31880
140 K4000 66.41
4000
2800
1958
2503
2000
1300
betver
550
0.2
Figure 7: Learning curves on MuJoCo benchmarks with different policies. The solid lines corre- spond the mean and the shaded regions the 95% confidence interval over 5 trials using fixed set of random seeds. All curves are smoothed uniformly for visual clarity.
17


Reviews:
[{"review_id": "yk5p5xy5Fho", "reviewer": "Reviewer_eX28", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper developed a very interesting zeroth-order actor-critic algorithm that nicely integrates gradient-based critic training with gradient-free actor training. The newly developed algorithm was also evaluated empirically on several benchmark datasets with promising outcomes.\n\nWhile this paper introduced some interesting ideas, there are some limitations too:\n\n1. It remains questionable to me why the new algorithm is designed to integrate first-order PEV with zeroth-order PIM. In fact, it seems mathematically possible to induce first-order PIM based on first-order PEV. I am not convinced about the technical and practical necessity of adopting zeroth-order PIM instead of first-order PIM. Perhaps the performance advantage of zero-order PIM over first-order PIM should be experimentally and theoretically evaluated in further details.\n\n2. The new algorithm introduces additional hyper-parameters, including N. While the performance impact of N has been evaluated on one benchmark problem in detail, it is not clear how to set this hyper-parameter properly for other reinforcement learning problems. Some further investigation on N may be necessary.\n\n3. The theoretical analysis in Subsection 3.2 produced two upper bounds on the variances of the zeroth-order gradient. Although the upper bound for the new zeroth-order gradient may be smaller than that of the existing zeroth-order gradient based on ES, this does not necessarily imply that the new zeroth-order gradient actually enjoys smaller variance than ES during practical use. In consideration of the bias introduced by the critic, the true advantage of the new algorithm may require further investigation.\n\n4. The experimental evaluation may need to be strengthened in several aspects. First, the authors should consider more challenging benchmarks including Humanoid in order to clearly show the performance advantage of the new algorithm. Second, the new algorithm is only compared to one first-order approach, i.e., PPO. This is not sufficient to demonstrate the effectiveness of the new algorithm. Comparing to other first-order approaches, such as SAC and TD3, is necessary IMHO. Third, based on the learning curves and the results presented in table 1, the performance of ZOAC is not significantly better than PPO. With suitable parameter tuning, PPO may easily outperform ZOAC on the tested benchmark problems. Hence, the true effectiveness of ZOAC should be studied further.\n\nAdditional comments based on authors' feedback:\nI would like to thank the authors for providing feedback on my review comments. Following the feedback provided, I see the necessity of mentioning the following:\n\na. In the feedback, the authors highlighted several advantages of ZOO, including its capability to train policy where gradient information is hard to obtain or even unavailable. This is a good point. However, this paper does not show that the newly proposed algorithm can effectively train such a policy, for example a rule-based policy, to solve any practically important problems. Furthermore, the robustness advantage of ZOO, in comparison to first-order PIM, should be more clearly analyzed in the paper.\n\nb. My concern is that the bounds identified in the paper may not be sufficiently tight. Hence, comparing the bounds directly does not show the true theoretical advantage of the new algorithm, affecting the theoretical contribution of this paper.\n\nc. Thank the authors for agreeing to perform more experiments, including experiments on Humanoid. However, without knowing the experiment results, it is not easy to determine the true advantage of the new algorithm on hard problems at this stage.\n\nd. It is widely known that the performance of deep reinforcement learning algorithms can be highly sensitive to detailed experimental settings. While ARS has been shown to outperform DDPG and SAC previously, this may not be sufficient to avoid comparing the new algorithm with DDPG, SAC or TD3. As carefully pointed out by the authors, the performance results reported in the paper introducing TD3 may not be identical to those presented in the paper introducing SAC. Hence, to truly understand the performance advantage of the new algorithm and hence the technical contribution of this paper, I believe the authors should consider comparing their algorithm with more SOTA algorithms, including more gradient-based algorithms.", "summary_of_the_paper": "This paper developed a very interesting zeroth-order actor-critic algorithm that nicely integrates gradient-based critic training with gradient-free actor training. The newly developed algorithm was also evaluated empirically on several benchmark datasets with promising outcomes. The literature review in the paper is very clear and comprehensive. The review adequately justified the technical innovation of the new algorithm.", "summary_of_the_review": "This paper developed a very interesting zeroth-order actor-critic algorithm that nicely integrates gradient-based critic training with gradient-free actor training. While this paper introduced some interesting ideas, the motivation for the new algorithm design may need to be clarified more. The theoretical strength of the new algorithm should be analyzed in further depth. There are rooms for improvement regarding the experimental evaluation too.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "tFMTL2t9V4G", "reviewer": "Reviewer_wk6f", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is overall well-written, and both the actor and critic part of the algorithms are relatively easy to understand (especially with the pseudocode provided in appendix). The algorithm makes sense, and the results are convincing. The introduction does a great job at motivating why a zero-order policy update is desirable, even though the list provided in paragraph 2 could be made more prominent.\n\nOne small limitation of the paper is that two extra baselines would have been interesting in the experiments: SAC and A3C. PPO is quite a dated baseline, and does not represent state-of-the-art first-order reinforcement learning. The Soft Actor-Critic has been shown to outperform PPO, and other old baselines, such as A3C, may be interesting too as they use several workers to collect rollouts (leading to better exploration).\n\nA minor remark is that Figure 1 did not help me understand the algorithm, while the pseudocode helped better. I suggest to mention how $\\hat{G}$ and $\\hat{A}$ are computed in Figure 1a (and remove the loop with the environment to save space), noting that they come from rollouts computed in parallel with each rollout having its own perturbed policy parameters. Then, I would replace the small lines like $V_{\\omega} \\rightarrow V_{\\omega'}$ with the actual gradients being followed (maybe in a simplified way), so that we clearly see that $\\hat{G}$ and $\\hat{A}$ are used to train the critic and the actor, and that training the actor does not require a gradient computation anymore, but is a weighted sum of perturbed parameters. It is challenging to draw this well, I agree, but I think that a clear drawing will be very useful if this paper is accepted and has to be presented at the conference.", "summary_of_the_paper": "The paper proposes an actor-critic reinforcement learning algorithm, compatible with continuous actions, that combines a Monte-Carlo computation of the gradient of the actor (based on workers that perform rollouts from the current state) with a standard supervised-learning based critic update rule (using gradient descent for several epochs). The core contribution of the paper seems to be the method that combines the critic network V(s) with on-policy samples, using a form of eligibility traces. This combination is used to compute target V-Values for the critic, and the weighted average used to compute the gradient of the actor. Empirical results on MuJoCo show that the proposed algorithm outperforms PPO in sample-efficiency and final policy quality (extra experiments show that robustness is high too).", "summary_of_the_review": "The paper presents a well-motivated and elegant idea to train an actor-critic algorithm, and the empirical evaluation is sufficient. I'm borderling recommending acceptance (I would be happy to see the paper accepted, but could live with it being rejected in case I missed anything). I think that more recent baselines would make the paper stronger: strong theory and motivation, then a strong comparison against state-of-the-art baselines.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qfnFUgs8PdU", "reviewer": "Reviewer_cTPK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "While it is a novel choice to sample a trajectory consisting of a number of perturbed different policies, I am not sure whether we can compute a valid value function out of these trajectories. in Eq. 14, we are learning a single critic over return estimates from many different perturbed policy samples. What policy is this value function computes value for? For accurate advantage computation and policy update in Eq. 15/16, the advantage should be computed with the value function for each perturbed, policy; however, It seems that the paper is learning a single critic over all perturbed policies and computing the zeroth-order gradient based on it. This may be OK for Mujoco-like domains where the optimizing the short-term sum of rewards is enough to get an optimal policy, but it can be problematic in the domains where long-term reward is important. It is a very important point on the correctness of the main algorithm, and I may change my position if the authors can address this concern.\n\nOn the empirical evaluations, it is interesting to have experiments showing various strengths of ZOAC, especially its robustness and ablations. However, the overall performance evaluations do not seem very competitive when compared to sota actor-critic algorithms, e.g. SAC can achieve a return over 10000 at 1e6, and it would be much better to include such algorithms for comparison. Actor with (64,64) hidden units is also not a standard choice, and it would be more interesting to see the results with different number of units, e.g. (128,128) and (256,256).", "summary_of_the_paper": "This paper proposes ZOAC, which is composed of: perturbed rollouts generation, first-order policy evaluation, and zeroth-order policy improvement. The paper proposes a new way of sampling trajectories, by using a policy only for a fixed number of steps and changing to another policy. The paper shows that we can reduce the variance of the zeroth-order gradient estimator by appropriately setting the number of steps to use the same policy. The empirical results show that ZOAC can outperform other zeroth-order and first-order baseline algorithms.", "summary_of_the_review": "For now, I have an important concern on the main algorithm and I will recommend rejection unless the authors address my concern.\n\n\n--------------------------\n\nI have read the authors' response, and I have increased the score accodingly.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new reinforcement learning actor-critic type algorithm for parameterized policy spaces. The actor builds gradient estimates derived from perturbations of the policy (in the spirit of simultaneous perturbation stochastic approximation (SPSA) or Flaxman-Kalai-McMahan's "Gradient Descent without a Gradient" idea), while the critic is based on standard temporal difference (TD) learning. The algorithm is benchmarked, along with other well-known techniques, on Mujuco-based environments where it is seen to often perform well.

There were several concerns raised by the reviews initially, including the validity of the value function obtained by the rather non-standard perturbation of the behavior policy suggested in the paper, the necessity of the zeroth order scheme, the impact of the hyperparameter N, the lack of clarity about the overall algorithmic flow, and the lack of more contemporary baselines such as SAC, A3C and TD3.

Most concerns appear to have been addressed by the author(s) in their detailed responses, and new explanations have been added with significant effort, to the credit of the author(s). While the paper breaks new ground in the conceptual sense, and the reviewers are borderline positive about the paper, I am afraid that parts of the paper, especially relating the the soundness of the algorithm, are still unclear and not concretely motivated. This, coupled with the low confidence levels expressed in the reviewers' evaluations, renders the paper's form too preliminary at this stage to merit acceptance.

For instance, I notice upon a careful reading of the paper the following issues:

(a) Equation (7) is derived by claiming that $V^\beta(s_t)$ is uncorrelated with the Gaussian noise $\epsilon$. However, I fail to see why this should hold, since the paper mentions, in the paragraph before equation (6) that $\beta = \pi_{\theta + \sigma \epsilon}$, so $\beta$ ostensibly clearly depends on $\epsilon$.

(b) The motivation behind the objective $J_{ZOAC}$ in (6), and the quantities involved in its definition, is rather opaque. For instance, the right side of (6) suggests an infinite horizon discounted reward criterion, whereas the expectation is taken with respect to $d^\beta$, the "stationary distribution" of the policy $\beta$. How/why is this justified? I would expect the use of the discounted occupancy measure here, instead of the (long term) stationary measure which washes out any near-term trajectory effects.

(c) The paper mentions that $\epsilon$ is a sequence of random perturbations *per time step* in (6) as opposed to the usual ES perturbation of a one-time perturbation. However, the size of the covariance matrix $I$ in (6) and (3) are not explicitly distinguished, leading to much confusion in the mind of the keen reader.

I hope that the author(s) can utilize the feedback from the reviews in order to put up a significantly clearer and solidly motivated paper in the next round, so that its conceptual merits can be proven without doubt. Thanks and best wishes.
Decision: Reject