Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

On 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_review: For now, I have an important concern on the main algorithm and I will recommend rejection unless the authors address my concern.


--------------------------

I have read the authors' response, and I have increased the score accodingly.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

While this paper introduced some interesting ideas, there are some limitations too:

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

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

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

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

Additional comments based on authors' feedback:
I 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:

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

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

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

d. 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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).
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.

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

A 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_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.
review_title: null

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