Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper improves upon Stackelberg Deep Deterministic Policy Gradients by proposing a set of strategies on how to deal with the Hessian part of the gradient. This should overcome the major limitations of this class of methods, which are the great time complexity and the slow converging rate with respect to the standard actor-critic framework. The authors provide a formal justification on why removing parts of the Hessian and using a block-diagonal approximation is still achieving convergence. Time complexity is analyzed for many variations of the algorithm and the experimental session provides mixed results.
main_review: 
I found this paper in general well written and the method presented seems to be novel. The authors analyzed many different Hessian approximation scenarios and I believe that this line of work can be relevant in order to make the Stackelberg approach feasible for larger neural networks.

Unfortunately, I found a few issues with the theory related to DDPG and the way experiments have been conducted, which might violate most of the proposed theoretical results.

The main issue with this paper is that it considers the approximated off-policy policy gradient of DDPG, which appears here in equation (4) as if it was the true policy gradient. 

I want to discuss two cases and explain why equation (4) is not correct:

- In the on-policy case, the expectation of the left side of equation (4) should be over the distribution on the initial state of the agent, while on the right side it becomes the (improper) discounted state visitation under the current policy. This is because the gradient $\nabla_{\theta}Q^{\pi_{\theta}}(s,a)$ (here a is any action, not the deterministic one) can be iteratively decomposed (see Theorem 1 in [1] and  Theorem 1 in [2]).

- In the off-policy case, however, since we do not have samples from the stationary distribution under the current policy, the expectation on the left side of equation (4) is taken over the discounted state visitation under the behavioral policy, here called $\rho(s)$. If this is the case, the gradient  $\nabla_{\theta}Q^{\pi_{\theta}}(s,a)$ is difficult to compute and it is usually dropped (see Eq. 15 in [1] and comment below, see Section 2.2 and Appendix B Errata in [3]). Therefore the gradient is only an approximation of the true off-policy policy gradient. This is what happens in off-policy DPG, DDPG and TD3. So, in order to have equality in equation (4), the term  $\nabla_{\theta}Q^{\pi_{\theta}}(s,a)$ must be added. Formally, equation 4 should be: $\nabla_{\theta} \mathbb{E}_{s \sim \rho(\cdot)} [Q^{\pi_{\theta}}(s, \pi_{\theta}(s))] = \mathbb{E}_{s \sim \rho(\cdot)} [\nabla_{\theta}\pi_{\theta}(s) \nabla_a Q^{\pi_{\theta}}(s,a)|_{a=\pi_{\theta}(s)} + \nabla_{\theta}Q^{\pi_{\theta}}(s,a)|_{a=\pi_{\theta}(s)}]$.

This issue is present in most of the proofs, where equation (4) is used ignoring the additional term, so the results of proposition 1, Theorem 1, Theorem 2, Corollary 1, should not hold in the off-policy setting. Note that the experiments performed are off-policy and use a replay buffer containing past trajectories.

In the problem formulation, it is not clear how $\rho(s)$ is defined. The authors claim it is the "discounted state distribution of s", but under which policy? The definition of the action-value function should not depend on the initial state. 

The authors define $Q_w^{\pi_{\theta}}(s,a)$ to be equal to $V_w^{\pi_{\theta}} (s)$, because they always consider the deterministic action of the policy. This can be seen also in the minimization of the TD error in equation (1), where the expectation is never taken over the actions in the replay buffer, but only over the states ($\nabla_w \mathbb{E}_{s \sim \rho(\cdot)} [(Q^{\pi_{\theta}}_w(s, \pi_{\theta}(s)) - Q^{\pi_{\theta}}(s, \pi_{\theta}(s)) )^2]$). Note how this differs from DDPG, where the target value function is deterministic, but the learned value function is evaluated on a set of noisy actions. This is relevant here because when taking the second order gradient, the authors must use the chain rule for both terms in the temporal difference loss, while this would not be the case in standard DDPG. Note that in the experiments the authors are instead using the standard DDPG approach and learn a full action-value function, sampling state-actions pairs from the replay buffer. This is evident also in Table 4 where a noisy version of the policy is used for exploration. How is this affecting the theoretical results?

In the proof of Proposition 1, why is the term $\nabla_{\theta^T} Q^{\pi_{\theta}}(s,a)$ disappearing?

I would like to note that this paper is building on the work of Zheng et. al. [4], which appeared on ArXiV only 3 days before the first ICLR submission deadline. I was not able to verify if [4] has been peer-reviewed, but given the issues above, I believe that [4] might contain similar theoretical problems.

[1]David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14, pages I–387–I–395.JMLR.org, 2014.

[2]Sutton, R. S., McAllester, D. A., Singh, S. P., & Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in neural information processing systems (pp. 1057-1063).

[3]Thomas Degris, Martha White, and Richard S. Sutton. Off-policy actor-critic. In Proceedings of the 29th International Conference on International Conference on Machine Learning, ICML’12, pages 179–186, USA, 2012.Omnipress.

[4]Zheng, L., Fiez, T., Alumbaugh, Z., Chasnov, B., & Ratliff, L. J. (2021). Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning Algorithms. arXiv preprint arXiv:2109.12286.

summary_of_the_review: While I find the paper well written and potentially relevant for this field, there is a major flaw in how the policy gradient is computed. It is not clear to me how the theoretical results can be fixed in the off-policy case, while for on-policy learning some additional work might be able to keep the results valid. Unfortunately, the experiments conducted are in the off-policy setting, hence, it is not clear what we can conclude from them. Given the issues above, I propose to reject this paper in the current version.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper aims to establish a computational efficient Stackelberg training scheme for deep-learning-based actor-critic methods. The proposed approach,  Fast Stackelberg Deep Deterministic Policy Gradient (FSDDPG), considers the block diagonal approximation technique to reduce the training complexity while improving the convergence rate. This paper conducts both theoretical analysis and empirical evaluation to demonstrate the strength of the proposed approach.
main_review: This paper is well-organized, and the discussion of the literature background is thorough. The proposed method is novel and sound, which has solid theoretical analysis and empirical grounding. Overall, I recommend accepting this paper.

Minor comments:

- Several curves in Figure 3 do not seem to converge, e.g, in InvertedDoublePendulum and Walker. It would be better to include a longer training horizon to establish a rigorous comparison.

- In Table 1, how does the scale of $\epsilon$ compare to $\frac{1}{nm}$ and $\frac{1}{o}$ in practice?

summary_of_the_review: To my knowledge, the method proposed by this paper is novel and tackles an important problem. I recommend acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a method to accelerate Stackelberg Actor-Critic by ignoring the terms that contain Hessian in the indirect gradient term and applying block-diagonal approximation technique to remaining inverse terms. They prove a faster convergence rate of the proposed method to a fixed point. Experiments are conducted to validate the fast convergence and stability. 
main_review: Strengths: This paper is well-written and organized. The motivation and intuition of the proposed method are clear and easy to follow. Various experiments are presented to compare the proposed method with baselines.

Weaknesses: My concerns about this paper are three-folds. Firstly, the novelty. The theoretical analysis in Section 5 mainly follows Theorem 5 in (Fiez et al., 2020), the authors should clearly state the connections of these two works. Second, the theoretical analysis is pretty weak. They only show a faster convergence rate, which is an expected and relatively weak result. They don't show any theoretical results for stability, which is stated as one of their two main contributions (faster convergence rate and maintained stability). Third, in terms of the experiments, stability is mainly illustrated and validated only on toy examples, hence less convincing. 

summary_of_the_review: In all, although this paper is clear to follow and nicely presented, I believe the theoretical analysis part is weak. The fast convergence rate somehow lacks significant novelty. The stability of the proposed method is less convincing.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes a variant of the Stackelberg actor-critic algorithm, which treats actor-critic as a Stackelberg game with the actor being the leader and critic being the follower. Based on Stackelberg AC, this paper proposes to adopt deterministic policies in order to simplify the computation of the implicit gradient. Additionally, the authors propose approximation schemes including dropping small-order terms and matrix inversion via block diagonal matrix approximation. The computational complexity of gradient computation is established. Moreover, under relatively strong assumptions, the proposed method is shown to be convergent. Experiments on Mujoco are conducted to demonstrate the efficacy of the method.
main_review: Strength: This paper seems to provide numerical experiments on Mujoco that are comparable to the state-of-the-art. 

Weakness:

1. The formulation of Stackelberg game between the actor and critic seems problematic. In specific, the actor $\pi_{\theta}$ is the leader and the critic $Q_{\omega}$ is the follower. The follower's loss of the mean-squared temopral difference error 
\begin{align}
L(\theta, \omega) = \mathbb{E} _ {s \sim \rho_{\theta}, a\sim \pi_{\theta}} \big  [ ( Q_{\omega} (s,a) - Q^{\pi_{\theta} } (s,a))^2 \bigr ] ,
\end{align}
where $\rho_{\theta}$ is the visitation measure or stationary distribution induced by the policy $\pi_{\theta}$. Then, when calculating the indirect gradient term in Eq. (3), we  need to handle the partial direvative $\partial ^2 L(\theta, \omega) / \partial \theta \partial \omega$, which involves taking the gradient with respect to $(s,a) \sim \rho_{\theta} \otimes \pi_{\theta}$ and needs to be handled using policy gradient thoerem. This work seems to neglect this matter by using a fixed sampling distribution 
$\rho$, which is problematic. 

2. More importantly, I feel that the issue raised in this work: 
> Most AC methods perform stochastic gradient descent on
the actor and critic simultaneously. This can be regarded as performing Gradient Descent Ascent
(GDA) (Zheng et al., 2021; Wen et al., 2021), which is known to suffer from convergence to limit
cycles or bad locally optimal solutions (Wang et al., 2019; Jin et al., 2020; Balduzzi et al., 2018).
Moreover, Yang et al. (2019) show that the critic is biased and may not converge when the actor and
critic are updated simultaneously with similar learning rates.
seems not well justified. First, it seems [Yang et al. (2019)] does not provide a proof showing biased critic leads to divergence. Second, there are various recent works showing that actor-critic converges in finite-time. See [1,2,3,4]. It seems unclear what advantage such a Stackelberg view brings to the analysis.

3. It seems that the Stackelberg formulation of actor-critic used in this work is proposed in [Zheng et al., 2021]. The main contribution of this work is to (i) additionally use deterministic policy gradient and drop a term involving TD error, and (ii) use block diagonal approximation in the calculation of the inverse Hessian. 

4. The theoretical results and the proof seem hard to understand. It seems Theorem 1 directly follows from [Fiez et al., 2020] and convex analysis. Moreover, the assumption of positive-definiteness seems very strong. It would be nice to provide examples on which the assumptions hold. In addition, how is the stepsize separation $\tau$ chosen and how does it affect the theory?

References:

[1] A Finite Time Analysis of Two Time-Scale Actor Critic Methods - Yue Wu, Weitong Zhang, Pan Xu, Quanquan Gu

[2] Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms - Tengyu Xu, Zhe Wang, Yingbin Liang

[3] A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic - Mingyi Hong, Hoi-To Wai, Zhaoran Wang, Zhuoran Yang

[4] An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods - Yanli Liu, Kaiqing Zhang, Tamer Basar, Wotao Yin
summary_of_the_review: a. The Stackelberg view of actor-critic seems not well motivated. 

b. There exists a small issue in the implicit gradient involving the sampling distribution. 

c. The theoretical arguments depend on strong and ungrounded assumptions and the proofs are hard to follow.
review_title: null

Meta-review: This paper aims to make Stackelberg Deep Deterministic Policy Gradients practical and efficient. The main contributions are an analysis which suggests terms involving the Hessian can be dropped and a block-diagonal approximation to an expensive matrix inversion.

Several reviewers who voted for rejection expressed concerns about the soundness of the theoretical arguments. The response provided by the authors did help alleviate some of the reviewers’ concerns but still left significant doubts. While some of the remaining concerns could be due to a misunderstanding of the deterministic setting it is up to the authors to convince the reviewers that their arguments are sound. Given the current scores and the low confidence of the reviewer voting for acceptance, I recommend rejecting the paper in its current form.
Decision: Reject