Year: 2021

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.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has achieved great success in a wide range of challenging domains, including video games (Mnih et al., 2015), robotic control (Schulman et al., 2017), autonomous driving (Kendall et al., 2019), 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 function estimation (critic) and another for optimal policy approximation (actor), and optimize these two approximators by alternating between policy evaluation (PEV) and policy improvement (PIM). Onpolicy actor-critic methods, e.g., A3C (Mnih et al., 2016) and PPO (Schulman et al., 2017), often use critics 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 estimation and improve learning speed and stability. Among existing actor-critic algorithms, a 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 et al., 2017), ARS (Mania et al., 2018) and GA (Such et al., 2017), are competitive on common RL benchmarks, even when applied to deep neural network with millions of parameters. ZOO has several advantages compared to first-order MDP-based RL methods (Sehnke et al., 2010; 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 temporally-extended exploration; (3) Zeroth-order populationbased optimization possesses robustness-seeking 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
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 et al., 2018), identifying a low-dimensional search subspace (Maheswaranathan et al., 2019; Choromanski et al., 2019; Sener & Koltun, 2020), or subtracting a baseline for variance reduction (Sehnke et al., 2010; Grathwohl et al., 2018). One of the major reasons for the sample inefficiency of ZOO 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 & Tumer, 2018; Pourchot & Sigaud, 2018; Bodnar et al., 2020), or inject parameter noise into existing RL algorithms for efficient exploration (Plappert et al., 2018; Fortunato et al., 2018). However, existing hybrid methods still conduct first-order gradient-based policy improvement (at least as a part), which reimposes differentiable requirement on the policy.
In this paper, we propose the Zeroth-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 update 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-dependent and temporally-extended exploration. We modify the rollouts collection strategy from episode-wise perturbation as in traditional zeroth-order methods to timestep-wise perturbation, which results in higher sample efficiency and better exploration. We derive the zerothorder policy gradient under this setting and point out that a critic network can be introduced to estimate the state-value function and trade-off between bias and variance. We then propose a practical algorithm that utilizes several parallelized rollout workers and alternates between first-order PEV and zeroth-order PIM based on generated experiences in each iteration. We evaluate ZOAC on a range of challenging continuous control benchmarks from OpenAI 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 parameter noise in ZOAC. Furthermore, we conduct ablation studies to demonstrate the indispensable contribution of the modified rollouts collection strategy and the introduced critic network to ZOAC.

heading: 2 PRELIMINARIES

heading: 2.1 FROM POLICY GRADIENT TO ACTOR-CRITIC
text: 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 ×A×S → R is the transition probability matrix, r : S × A → R is the reward function. The return is defined as the total discounted future reward Gt = ∑∞ i=0 γ
ir(st+i, at+i), where γ ∈ (0, 1) is the discounting factor. The behavior of the agent is controlled by a policy π(a|s) : S × A → [0, 1], which maps states to a probability distribution over actions. The state-value function is defined as the expected return under policy π starting from a certain state: V π(s) = Ea∼π{Gt|st = s}. The goal of MDP-based RL is to find an optimal policy that maximizes the expectation of state-value function under a certain state distribution. Denoting a policy parameterized with θ as πθ, the objective function can be written as:
JPG(θ) = Es∼d[V πθ (s)], d = d0 or dπθ (1) where d0 is the initial state distribution and dπθ is the stationary state distribution of Markov chain under policy πθ. 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 πθ, and for continuing 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 (1992) is as follows:
∇θJPG(θ) = Est∼dπθ ,at∼πθ [Gt∇θ log πθ(at|st)] (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 network to estimate the value function and serve as a baseline to substitute the expected return Gt with a proper form of advantage function At, for example, TD residual (Mnih et al., 2016), or generalized advantage estimation (GAE) (Schulman et al., 2015). However, the above policy gradient
based methods can only be applied to differentiable policies, and may be unavailable when a nondifferentiable controller needs to be optimized.

heading: 2.2 EVOLUTION STRATEGIES
text: Existing ZOO methods focus on episodic RL problems with finite horizon and treat them as blackbox optimization. In these cases, the length of trajectories is limited and the discounting factor γ is usually set as 1. Evolution strategies (ES) is one of the most popular algorithms of ZOO, which optimizes a Gaussian smoothed objective function:
JES(θ) = E ∼N (0,I)Es∼d0 [V πθ+σ (s)] (3) where d0 is the initial state distribution and σ is the standard deviation of the Gaussian noise added to the policy. The zeroth-order gradient can be derived using the log-likelihood ratio trick and the probability density function of Gaussian distribution (Nesterov & Spokoiny, 2017):
∇θJES(θ) = 1
σ E ∼N (0,I)Es∼d0 [V πθ+σ (s) ] (4)
In practice, the expectation over Gaussian distribution can be approximated by sampling n noise samples { i}i=1,...,n, and the corresponding state value V πθ+σ i can be approximated by the episodic return Gi = ∑T t=0 γ
tr(st, at) of the sample trajectory of length T collected with policy πθ+σ i :
∇θJES(θ) ≈ 1
nσ n∑ i=1 Gi i (5)
The zeroth-order gradient estimator in Equation (5) only relies on the episodic return of each evaluated random directions, so it is applicable to non-differentiable policies. Besides, each perturbed policy remains deterministic in one trajectory, which leads to state-dependent and temporally-extended exploration. Furthermore, the Gaussian smoothed objective also improves robustness of the learned policies in parameter space.

heading: 3 ZEROTH-ORDER ACTOR-CRITIC

heading: 3.1 FROM ES TO ZOAC
text: In this section, we will derive an improved zeroth-order gradient combining the actor-critic architecture 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 et 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 as πθ : 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 unchanged throughout the trajectories. If a large number of random directions n 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., 2021), 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 as a stochastic exploration policy β = πθ+σ , where ∼ N (0, I) is Gaussian noise in parameter space and σ is the standard deviation. Our objective is to maximize the expectation of the state-value under stationary distribution dβ of the exploration policy β. We can leverage Bellman equation to estimate the state-value via bootstrapping, in which the one-step reward can be replaced with sampled experiences:
JZOAC(θ) = Est∼dβ [V β(st)] = E ∼N (0,I)Est∼dβEst+1∼P [r(st, πθ+σ (st)) + γV β(st+1)] (6)
Since all the contents in the outer expectation E ∼N (0,I)[·] can be regarded as a function of , the zeroth-order gradient of this objective function can be derived in exactly the same way as in ES.
Moreover, V β(st) can be subtracted as a baseline for variance reduction because of its uncorrelation to in the outer expectation and the zero mean property of the Gaussian noise :
∇θJZOAC(θ) = 1
σ E ∼N (0,I)Est∼dβEst+1∼P{[r(st, πθ+σ (st)) + γV β(st+1)− V β(st)] } (7) Compared to ES which uses unbiased but high variance Monte Carlo return to evaluate each perturbed policy, the performance of each random direction here is estimated by one-step TD residual with low variance. In practice, a common approach is to introduce a critic network Vw(s) to estimate the state-value function V β , which may lead to high bias in this form of advantage estimation.
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: ∇θJZOAC(θ)
= 1
σ E ∼N (0,I)Est∼dβEP {[ N−1∑ i=0 γir(st+i, πθ+σ (st+i)) + γ NV β(st+N )− V β(st) ] } (8)
where EP refers to expectation over N -step transition dynamics. Similar to one-step case, the cumulative reward within N step can be estimated from sampled experiences when st is the first state of the trajectory fragment collected with a certain perturbed policy πθ+σ . By introducing a critic network and choosing an appropriate length N , this N -step residual advantage function contributes to achieving a good trade-off between the bias and variance.

heading: 3.2 ANALYSIS ON VARIANCE OF GRADIENT ESTIMATORS
text: We analyze the variance of these two types of gradient estimators, ZOAC gradient and ES gradient. The budget of timestep of one trajectory N × H is identical for both algorithms: in ZOAC, each perturbed policy run forward N steps, and H is the number of sampled random directions in one trajectory; in ES, only one perturbed policy is sampled and run forward N ×H steps. If we denote the accumulative reward obtained within N × H timesteps in ES as V̂ πθ+σ NH and the N -step TD residual in ZOAC as Âπθ+σ N . We can then estimate the zeroth-order gradient according to Equation (4) and (8) respectively:
∇θĴES(θ) = 1
nσ n∑ i=1 V̂ πθ+σ i NH i (9)
∇θĴZOAC(θ) = 1
nHσ nH∑ i=1 Â πθ+σ i N i (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) = ∑d l=1 E[g2l ] − (Egl)2, where g = (g1, g2, ..., gd) > (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 |r(s, a)| < α, the critic network output |Vw(s)| < β, and n trajectories with length of N ×H timesteps are collected in one iteration, the upper bounds of the variance for gradient estimators (Equation (9) and (10)) are:
Var[∇θĴES(θ)] ≤ (1− γNH)2α2d nσ2(1− γ)2
(11)
Var[∇θĴZOAC(θ)] ≤ ((1− γN )α+ (1− γ)(1 + γN )β)2d
nHσ2(1− γ)2 (12)
We can compare their variance in a more intuitive way: if N ×H = 1000, γ = 0.99, and assume that β ≈ α1−γ , the difference of variance bounds becomes Var[∇θĴZOAC(θ)] − Var(∇θĴES(θ)) ≈ ( 4H − 1) 10000α2d nσ2 , which decreases with H and drops below zero when 4 < H ≤ 1000 (i.e., N is smaller than 250). This suggests that although same amount of data is collected, an appropriate rollout lengthN can indeed reduce variance of the gradient estimators. Besides, both variance bound are inversely proportional to n, which urges us to collect more trajectories.

heading: 3.3 PRACTICAL ALGORITHM
text: We propose the Zeroth-Order Actor-Critic (ZOAC) algorithm, which unifies first-order and zerothorder 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 1a and the pseudocode is summarized in Appendix A.1. 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 1b, which is a parallelized version with n workers. If we denote the t-th state sampled by the i-th worker as si,t, the rollout strategy can be described as: when reaching states in {si,jN}, where j ∈ N, a new random direction i,j is sampled and the behavior policy is 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 is never done. In episodic tasks, the rollout length 1 ≤ Ni,j ≤ N actually varies between different perturbed policies πθ+σ i,j 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 as the episode length and the critic network is turned off (i.e., Vw(s) ≡ 0), the algorithm actually degenerate into ES, since all perturbed policies are evaluated by running a whole episode, and the episodic return is used as the fitness score.
First-order PEV. The state-value function V̂ (s) can be estimated by a jointly optimized critic network Vw(s), which aims to minimize the MSE loss between the network output and state-value target. In each iteration, in total n × N × H states and the corresponding target values (s, Ĝ) are calculated and used for critic training. In a trajectory with length T , the target value Ĝt for each state st is calculated as (Schulman et al., 2015; Andrychowicz et al., 2021):
Ĝt = Vw(st) + T−t−1∑ k=0 (γλ)k[rt+k + γVw(st+k+1)− Vw(st+k)] (13)
where 0 < λ < 1 is a hyperparameter to control the trade-off between bias and variance of the value target. In Figure 1a, the one-step TD residual of each state s is denoted as δ for simplicity. The objective function of PEV can be written as:
Jcritic(w) = E(s,Ĝ)
{ 1
2 [Vw(s)− Ĝ]2
} (14)
In practice, the critic network is constructed as a neural network and updated through several epoches of stochastic gradient descent in each iteration.
Zeroth-order PIM. We calculate the zeroth-order gradient with n × H random directions and the corresponding advantage function as ( , Â). Similar to state value estimation, we leverage the generalized advantage estimation (GAE) trick (Schulman et al., 2015) to further control the biasvariance trade-off. We also perform advatage normalization to ensure consistent gradient length during training. Following the notations in Figure 1b, the advantage function can be written as:
Â πθ+σ i,j N = N−1∑ k=0 (γλ)k[ri,jN+k + γVw(si,jN+k+1)− Vw(si,jN+k)] (15)
where λ is the same as in Equation (13). The zeroth-order gradient can be then estimated as the weighted sum of the sampled random directions:
∇θJactor(θ) ≈ 1
nHσ n∑ i=1 H−1∑ j=0 Â πθ+σ i,j N i,j (16)

heading: 4 EXPERIMENTS

heading: 4.1 PERFORMANCE EVALUATION
text: We evaluate the performance of ZOAC on the MuJoCo continuous control benchmarks (Todorov et al., 2012) in OpenAI Gym (Brockman et al., 2016). We choose Evolution Strategies (ES) (Salimans et al., 2017; Liang et al., 2018) and Augmented Random Search (ARS) (Mania et al., 2018) as zeroth-order baselines and proximal policy optimization (PPO) (Schulman et al., 2017; Raffin 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 in Appendix A.2 and follow the recommended hyperparameter settings listed in the related papers or code repositories.
Figure 2 presents the learning curves on four continuous control tasks. Table 1 summarizes max total average return within the timestep threshold over 5 trials. Additional results including state-value estimation and performance comparison of different policies are attached in Appendix A.4 and A.6.
ZOAC matches or outperforms baseline algorithms across tasks in learning speed, final performance, and variance over 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 (1 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 it difficult to determine what is the real objective function being optimized. ZOAC, however, surpasses ES and ARS without relying on specific exploration tricks, which can be attributed to the introduction of critic network and the construction of advantage estimations in policy improvement.
Robustness Comparison. The objective function of ZOAC aims to maximize the expected statevalue of the stochastic behavior policy that contains parameter noise all the time, which intuitively encourages the agent to find a 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 at 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 HalfCheetahv2 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 robustness-seeking property of our method. The linear policies learned by ARS seem very fragile and suffer significant performance degradation under extra noise, far inferior to the linear ones learned by ZOAC. Additional results and discussions are attached in Appendix A.5.
Visualization of the learned policies. In order to intuitively observe the behaviors of the learned policies, we apply all methods on MountainCarContinuous-v0, in which the car is rewarded +100 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 is sparse and delayed, while zerothorder 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
return within the shortest episode length. The latter has a 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.

heading: 4.2 ABLATION STUDIES
text: 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-wise perturbation strategy and choice of N . We compare ZOAC and ARS on HalfCheetah-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 σ, the learning rate of policy αactor, and also the budget of timesteps within one iteration. Figure 4 shows the influence of N on 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 a 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 accumulative 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 improve 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 a 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.

heading: 5 RELATED WORK
text: 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. Sehnke 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. (2017) 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. (2018) propose
augmented random search (ARS), which applied ZOO to linear policies with techniques including observation normalization, reward scaling, top performing directions sifting, and achieve astonishing performance on RL benchmarks considering its simplicity. ZOO has regained popularity in recent years because of its special advantages when applied in RL, including wide adaptability to policy parameterization (e.g., deterministic or stochastic, differentiable or non-differentiable), robustness seeking property, state-dependent and temporally-extended exploration.
Improved techniques for ZOO. The main limitation of ZOO is its high sample complexity. Researchers 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., 2010; Salimans 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. (2010) adopt a 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, 2017), therefore some researches aim to identify a low-dimensional search space and guide the search towards faster convergence. Guided ES (Maheswaranathan et 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 complementary advantages when applied to RL problems, and recent researches have tried to 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, 2018) and Proximal Distilled ERL (Bodnar et al., 2020) adopt similar hybridization framework, but use different 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-order way, which implies wide adaptability to different forms of policies.

heading: 6 CONCLUSION
text: 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, statedependent exploration, robustness-seeking 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 a range of challenging continuous control tasks show that ZOAC outperforms zeroth-order and first-order baselines. Robustness analysis and ablation studies on hyperparameters and components are also performed to show the properties of ZOAC.
Moreover, our methods achieve such improvement while still using traditional isotropic Gaussian noise for perturbation, so in principle those improved techniques for ZOO from sampling perspectives can be further integrated, e.g., Monte Carlo sampling techniques, low-dimensional subspace identification, adaptive perturbation scale, which may lead to even higher performance.

heading: 7 REPRODUCIBILITY
text: The code of ZOAC will be released after the author notification in https://anonymous. 4open.science/r/Zeroth-Order-Actor-Critic-1A71. We summarize the algorithm in Appendix A.1 and describe the implementation details in Appendix A.2.

heading: A APPENDIX
text: A.1 PSEUDOCODE OF ZOAC
Algorithm 1 Zeroth-Order Actor-Critic (ZOAC) 1: Initialize: policy parameters θ, critic network parameters w 2: for each iteration do 3: for each worker i = 1, 2, ..., n do 4: for j = 0, 1, ...,H − 1 do 5: Sample i,j ∼ N (0, I) 6: Run perturbed policy πθ+σ i,j in environment for N timesteps 7: Compute advantage function Âπθ+σ i,j according to Equation (15) 8: end for 9: Compute the state-value target Ĝt for each state st according to Equation (13) 10: end for 11: Collect (s, Ĝ) for critic update and ( , Â) for actor update 12: Update w with batch size L through SGD by minimizing Equation (14) for M epoches 13: Update θ 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 parallelization techniques used in ES (Salimans et al., 2017) and ARS (Mania et al., 2018). Firstly, we created a shared noise table before training starts, then the workers communicate indices in 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, we use neural networks with (256, 256) hidden nodes and tanh nonlinearities as critics to estimate state-value function.
Both the zeroth-order baseline methods perform reward shaping to 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 to a different policy architecture.
We summarize the hyperparameters used in ZOAC in Table 3 and list their values that are used to produce the results in Figure 2. 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 is averaged over 10 episodes. Table 1 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 |Vw(s)| < β, and n trajectories with length of N ×H timesteps are collected in one iteration, the upper bounds of the variance of gradient estimators (Equation (9) and (10)) are:
Var(∇θĴES(θ)) ≤ (1− γNH)2α2d nσ2(1− γ)2
Var[∇θĴZOAC(θ)] ≤ ((1− γN )α+ (1− γ)(1 + γN )β)2d
nHσ2(1− γ)2
Proof. (1) Variance bound for ES gradient estimators
Under the setting described in Section 3.2, the state-value under policy πθ+σ is estimated by the accumulative return over NH timesteps, which is denoted as V̂ πθ+σ NH . The isotropic Gaussian noise added to the policy can be presented as = ( 1, 2, ..., d)>, where l ∼ N (0, 1), l ∈ {1, 2, ..., d}.
Var[V̂ πθ+σ NH ] ≤ d∑ l=1 E[(V̂ πθ+σ NH l) 2]
= d∑ l=1 ∫ p( l) ( NH∑ t=1 γt−1r(st, at) )2 2l d l ≤ d∑ l=1 ∫ p( l) ( NH∑ t=1 γt−1α )2 2l d l
= (1− γNH)2α2 (1− γ)2 d∑ l=1 ∫ p( l) 2 l d l
= (1− γNH)2α2 (1− γ)2 d∑ l=1 E l∼N (0,1) 2 l
= (1− γNH)2α2d
(1− γ)2
The last equality holds because 2l ∼ χ2(1) when l ∼ N (0, 1), and E[ 2l ] = 1 for all l. Since n random directions is sampled and evaluated, the ES gradient estimator is given according to Equation (9):
∇θĴES(θ) = 1
nσ n∑ i=1 V̂ πθ+σ i NH i
Therefore the variance bound for ES can be derived as in Theorem 1:
Var[∇θĴES(θ)] = 1
nσ2 Var[V̂
πθ+σ NH ]
≤ (1− γ NH)2α2d
nσ2(1− γ)2
(2) Variance bound for ZOAC gradient estimators
Under the setting described in Section 3.2, the performance under policy πθ+σ is estimated by the N -step TD residual, which is denoted as Âπθ+σ N . The isotropic Gaussian noise is added to the policy as well.
Var[Â πθ+σ N ] ≤ d∑ l=1 E[(Âπθ+σ N l) 2]
= d∑ l=1 ∫ p( l) ( N∑ t=1 γt−1r(st, at) + γ NVw(st+N )− Vw(st) )2 2l d l ≤ d∑ l=1 ∫ p( l) ( N∑ t=1 γt−1α+ (1 + γN )β )2 2l d l
=
( (1− γN )α+ (1− γ)(1 + γN )β
(1− γ)
)2 d∑ l=1 ∫ p( l) 2 l d l
=
( (1− γN )α+ (1− γ)(1 + γN )β
(1− γ)
)2 d
Totally n × H random directions is sampled and evaluated, and the ZOAC gradient estimator is given according to Equation (10):
∇θĴZOAC(θ) ≈ 1
nHσ nH∑ i=1 Â πθ+σ i N i
Therefore the variance bound for ZOAC can be derived:
Var[∇θĴZOAC(θ)] = 1
nHσ2 Var[Â
πθ+σ N ]
≤ ((1− γ N )α+ (1− γ)(1 + γN )β)2d
nHσ2(1− γ)2
A.4 STATE-VALUE FUNCTION ESTIMATION
We plot the average state-value estimation difference Vw(s)− V πθ (s) in evaluation during training in Figure 6. Since we turn off the exploration noise for evaluation, which means that the trajectories are collected under the deterministic policy πθ, the discounted sum of reward-to-go can be regarded as an 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 V β(s) of the stochastic exploration policy β rather than V πθ (s) of the deterministic policy πθ. 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.
A.5 ADDITIONAL RESULTS OF ROBUSTNESS COMPARISON
Table 4 shows the result of robustness comparison in all tested MuJoCo environments. Results show that in general neural policies are more robust, which can be ascribed to their strong expressive ability. InvertedDoublePendulum-v2 is the exception, in which the robustness of the neural network policies is no where near the linear ones, no matter what RL algorithms is used. Since this environment is the simplest one among these environments, we guess that this is due to the overfitting of neural networks, and that a 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 all 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 ZOAC are also shown to be more robust to both observation noise and parameter noise. One reason is that parameter noise used in 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.
A.6 PERFORMANCE COMPARISON OF DIFFERENT POLICY PARAMETERIZATIONS
The derivative-free nature of ZOAC allows us to estimate the zeroth-order policy gradient to improve the policy without considering the specific policy architecture. Hence, ZOAC can be applied seamlessly to arbitrary parameterized policies in theory.
We further apply ZOAC on 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 see the performance of ZOAC when optimizing these policies. We listed the dimension of the parameter space of different policies in Table 5.
Toeplitz matrix is a 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 ∈ Rm×n has m× n parameters, while a Toeplitz matrix T ∈ Rm×n has only m+ n− 1 parameters. Since a general dense matrix performs quite well in all tested environments, we wonder whether a more compact policy still work. Besides, as derived in Theorem 1, the variance bound of zerothorder gradient increases proportional to the dimension of parameter space, and it is a common view that zeroth-order methods are more suitable for low-dimensional problems. We wonder whether a larger network will improve or harm the performance.
We use the same set of hyperparameters for linear policies, and another set for networks, as summarized in Table 3. Results in Figure 7 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 a general dense matrix, indicating that this type of policy is not sufficient 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, we may apply ZOAC to specific problems where first-order methods can not handle and to improve existing results where the policies are trained with traditional zeroth-order methods like ES and ARS.

Review summaries:
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.

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.

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).