Fast Deterministic Stackelberg Actor-Critic
Authors: Runsheng Yu
Xinrun Wang
James Kwok
Venue: ICLR 2022 Submitted (2022)
Keywords: Deep Reinforcement Learning

Abstract: Most advanced Actor-Critic (AC) approaches update the actor and critic concurrently through (stochastic) Gradient Descents (GD),  which may be trapped into bad local optimality due to the instability of these simultaneous updating schemes.  
Stackelberg AC learning scheme alleviates these limitations by adding a compensated indirect gradient terms to the GD. However, the indirect gradient terms are time-consuming to calculate, and the convergence rate is also relatively slow.  To alleviates these challenges, we find that in the Deterministic Policy Gradient family, by removing the terms that contain Hessian matrices and adopting the block diagonal approximation technique to approximate the remaining inverse matrices, we can construct an approximated Stackelberg AC learning scheme that is easy to compute and fast to converge. Experiments reveal that ours outperform SOTAs in terms of average returns under acceptable training time.

Under review as a conference paper at ICLR 2022
FAST STACKELBERG DETERMINISTIC ACTOR-CRITIC
Anonymous authors
Paper under double-blind review
ABSTRACT
Most advanced Actor-Critic (AC) approaches update the actor and critic concur- rently through (stochastic) Gradient Descents (GD), which may be trapped into bad local optimality due to the instability of these simultaneous updating schemes. Stackelberg AC learning scheme alleviates these limitations by adding a compen- sated indirect gradient terms to the GD. However, the indirect gradient terms are time-consuming to calculate, and the convergence rate is also relatively slow. To alleviates these challenges, ily. by removing the terms that contain Hessian matrices and adopting the block diagonal approximation technique to approximate the remaining inverse matrices. we can construct an approximated Stackelberg AC learning scheme that is easy to compute and fast to converge. Experiments reveal that ours outperform SOTAs terms of average returns under acceptable training time.
find that in the Deterministic Policy Gradient fam-
INTRODUCTION
Reinforcement learning (RL) has been widely adopted for solving various complicated sequen- tial problems such as games (Mnih et al. 2013) and robotics applications (Kober et al. (013). In particular, the actor-critic (AC) approach has achieved remarkable performance in many real- world tasks (Arulkumaran et al. 2017). 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 b. Wen et al.]|2021] which is known to suffer from convergence to limit cycles or bad locally optimal solutions WWan et al., [2019] Jin et al.) 2020 Balduzzi et al., 2018). (2019). the GDA training scheme fragile, which could lead Moreover, mentioned in Yang et al.
to biased critic and may not converge.
To address these issues, Zheng al. 2021a) and Wen al. (2021) reformulate the actor-critic problem as a bilevel optimization problem, and introduce a leader-follower (Stackelberg) training scheme (Fiez al.] 2020). However, this requires the computation of several indirect gradient terms (including the inverse Hessian matrices), which are difficult to compute or accurately approximated. Moreover, empirically, this Stackelberg training scheme converges slower than GDA in the envi- ronments where GDA is not trapped into limited cycles or bad local optimums, since the indirect gradient terms pull back the parameters to stay within the best response areas to guarantee that the leader's loss is always small (Wang et 2019). To reduce the computational complexity, (Shewchuk (2007) introduces the use of conjugate gradient (CG) descent, which simplifies the computation of the approximated inverse Hessian to the sol of a linear system. However, to have good perfor- mance, a sufficient number inner iterations is still required to obtain a good approximation of the Hessian matrices. Empirically, its convergence is still not fast.
Among these actor-critic methods, the deterministic policy gradient (DPG) family (Silver et al. 2014 Lillicrap et al. 2016; Fujimoto et al. 2018 Haarnoja al. 2018) has some advantages over other methods: if we assume the actor to be the follower, and the critic to be the leader, the gradient of the follower can be divided into several terms, some are closely related to the best response function which slows down the training process. Also, they include Hessian matrices which are hard compute (We name it the TD-related term which is formally discussed in Sec. 4. Based on this observation, we propose Fast Stackelberg Deep Deterministic Policy Gradient (FSDDPG), which reduces these TD-related terms to improve the convergence rate and reduce training time. Moreover, together with the block diagonal approximation technique to approximate the remaining matrices, it possible to further reduce the training complexity from O(n'm²) to Onn2m²) where is the number of layers and m is the number of neurons in each layer. Experiments reveal that with our approximated methods outperform SOTAs in terms of average returns under acceptable training time.

---

Under review as a conference paper at ICLR 2022
2 RELATED WORKS
Actor Critic. The AC methods are widely adopted in solving complicated sequential problems (Sut- ton & Barto 2018). Among these methods, the DPG family are prevalent since they can be both off and on policy and able to be deployed in discrete time and continuous time environments, which are efficient and suit various environments (Lillicrap et al. 2016). However, most of the ACs use simultaneously update rule, i.c., the actor and critic update with the same learning rate, which are not always stable. Empirically, the AC may find better solutions when the critic is updated more frequently than the actor (Wen et al. (021). and we also show it in our experiments in Sec. 6 The- oretically, most of the stable training methods of GDAs are based the Two Time Scale Updates (TTSU) scheme (Wu et al. 2020. Dalal et al. AC can also be proven convergence (Fu et al. (GDA) may trapped into limited cycles and bad local optimality (Zhang et al., 2020; Wang et al,, 2019). Regarding TTSU, since it requires the learning rate of the follower to be slower than that of the leader, its convergence rate is slow consequently (Kaledin et al. 2020).
2018). Although the simultaneously update rule for 2020 it may not suit all the environments since AC
As the AC training schemes can be also represented as bi-level optimization process, is naturally to introduce Stackelberg training scheme to AC as the Stackelberg Actor Critic to stabilize train- ing (Zheng et al., 2021a| Wen et al., 202T). However, the gradient of the follower is time consuming to calculate, and the convergence rate is relatively slow. Thus, in many environments, Stackelberg training may perform worse than vanilla AC under acceptable training time (Wen et al. 202T).
Gradient-based bi-level optimization. The gradient-based bi-level optimization is used to minimize/- maximize a cost function defined in terms of the optimal solution to another cost function (Sinha et al. 2017). Currently, the idea of differential Stackelberg (leader-follower) game is introduced to convert these problems into the differential (Stackelberg) game problems (Fiez et al. (020). To solve the differential Stackelberg game, the Stackelberg gradient descent is introduced by leveraging the
implicit function theorem (Ji et al. 2021 Fiez et al.
2020 Grazzi et al. 2020), which has already be
applied into different areas, e.g., GAN (Fiez al.
2020 hyper-parameter optimization (Lorraine)
it al. 2020), as well as meta learning (Rajeswaran et al.
2019).
Approximating (inverse) Hessian. Calculating the (inverse) Hessian is time-consuming, especially for the deep neural networks (Martens & Grosse 22015) [ootvv et al. 2017). To address this chal-
al. 2019 Mehra 1969 Ghadimi & Wang 2018), block diagonal approximation (Martens & Grosse 2015 Botev et al. 2017), 7, as well as the approximate Newton methods (Martinez, 2000 Xu et al. (016)) are proposed. Here, we choose the block diagonal approximation, since it is easy to be implemented and fast to compute while maintaining a good performance. Another method to approximate Hessian is the Gauss Newton matrix (Schraudolph) 2002), which is generally used to approximate Hessian for the Mean Squared loss (MSE) (Martens 2020). Gauss Newton matrix outperforms Hessian matrix for its fast comput- ing, and stability since it is always positive semi-definite (Chen. 2011). However, it still lacks the obvious justification why dropping the Hessian term helps convergence (Martens) 2020).
lenge, the conjugate gradient approximation (Rajeswaran
PROBLEM FORMULATION
A Markov decision process (MDP) can represented by the tuple (S, A, R, P(S]S, A), 7), where
S is the state, a E A is the action, p(s1|s, a) is the transition probability, and r(s, a) E Rmin Rmax the bounded reward function. 0² (s) is the discounted state distribution of s conducted by behavior policy 3 U
S x A + A(A) is the policy, where A(A) is the simplex of action set A. Q" the state-action value function w.r.t. w: (*(ssa) a) == E, E. r a). Here, we parameterize Q and π with w E Ω and 0 E O, respectively (Qw and To), where Ω and θ are the parameter spaces.
Following (Zheng et al. 2021a). we formulate the actor-critic as a differential Stackelberg game Fizz et al. 2020):
max J(0 wn (0))
(1)
s.t. w" (8) arg min L(8,
where.J w) -
(-1s) 1@ (s, a)), L(e, w) = (e-p(s))amt(( (Q,(ss -1 _Q (s, a))) which is the temporal difference (TD) error, and 1 (-) is the stop-gradient operator to achieve
semi-gradient method (Sutton& & Barto 2018
For compactness, we omit the superscript of p² ()) as p(s) with little abuse of notations.
2

---

Under review as a conference paper at ICLR 2022
Stackelberg learning (or approximate implicit differentiation) (Fiez al. 2020 Ji et al. 2021 is
framework for solving the bilevel optimization problems (Ji et al. 2021 Fiez et al. 2020: Grazzi
et al.] 2020), and can be used on most AC variants (e.g,, DDPG Lillicrap et al. 2016), TD3 (Fuji-
moto et al. 2018) and SAC (Haarnoja et al. 2018)). Using it on we obtain (Fiez et al. 2020
O. (0, w (0))
aL(O, w)
0 x 0 +
t ahe
00
aw
where 0J (0 (0)) 00
8 L(8,wu)
82 L((
-1 8J(8,
and a, aw are learning rates
00
Our
Bw
for the actor and critic, respectively
2 Here.
0 L(0, w)
L(0,w)
)
8 L(0, w)
0J(0, w)
(3)
a0dw
Ow?
Oc
is known as the indirect gradient term (Lorraine et al.
2020).
Empirically, AC with Stackelberg training does not improve the performance of ACs in many envi- ronments (Wen al. (02T). This is also confirmed by our experiments in Sec. 6 This is mainly due to the fact that Stackelberg training converges slowly, and thus it performs worse than vanilla AC when AC does not be trapped into limited cycles and some bad local optimality. Also, inverting the n X n Hessian matrix in (3) takes O(n²) time, where n is the matrix size and is equal to the number of neural network parameters. Although Conjugate Gradient (CG) can be used to reduce the computing complexity (Zheng et al.] (2021a), it still needs sufficient steps for CG to obtain a precise approximation of the Hessian matrix.
In this paper, we focus on improving Stackelberg learning in DDPG (Lillicrap et al. 2016) and TD3 (Fujimoto et al. 2018). DDPG and TD3 have been widely adopted for solving compli- cated continuous control environments (Wang et al. 2020). In DPG family, =[als) degener- ates to (als) = 5(a- - To())), where TØ(3) : S is the deterministic policy, and 6(-) the Dirac-Delta function. I.00 w) becomes Ppp() [[Q% (8, aa- 1 [Q** (s,TT, (s))1))) where Q a) == (s) s.t. a = n, (s). J(0, w) becomes 1e)= 1 a)).
Notice that the practical DPG based methods update the critic by using i(0, w) = Ep()) [(0 a) 1 'Q* (s, ))))² Lillicrap et al. 2016 Fujimoto et al. 2018). We follow the critic's loss, and the modified update scheme becomes:
aJ (0, (0))
ai. w)
0 x- 0 + a
Oue
(4)
09
Ow
Comparing with Eq. 2 the update scheme for policy 0 maintains the same. The main reason is that (0, w) = E E-( [o(QT (s, a) - Q=* a] is not well-defined when a * rTs), and thus we still use L0, w) to update the policy.
To help our analysis, we denote algorithms that replace the vanilla policy gradient in Eq. 4 to DPG in DDPG (resp. TD3) as SDDPG and (resp. STD3), respectively.
4 PROPOSED METHOD
To alleviate the two challenges in Section find that the indirect gradient term for the DPG family (Silver et al., 2014) can be divided into several terms. The TD-related terms are closely related to the TD loss of the critic and contain Hessian matrices.
When the TD loss is small, these TD-related terms can be eliminated (Sec. 4.1 in (Wang et al.] (019)) the indirect gradient term pulls the follower stay along in the best sponse area, which may hinder the update scheme and slows convergence: Formally speaking, the best response function b(w) Ω + θ is the implicit function defined by (L(0,w) 0.
As discussed
It can be shown that Vub(w) = o L(0, L(),ww)) 8 L() 800
(Fiez et al. 2020 Hence, we have ) o L() -1 (0(,)))) bwb(w) (-a aJ(0,w) If A, b(we) (0, is closed to the best
803w Sio
Ou2
duc
du
"For simplicity of notations, we write dw = Ow" Br and 080m. = 00 aro.
For simplification, omit (-) in [Q (s,a)):
3

---

Under review as a conference paper at ICLR 2022
aJ,, we)
response parameters b(w+)) ), then 0. Tw,b(ur)
b(we)) - V., (w)))))(
Owe
w)) b(w++1), where is according the Taylor's series approximation. means that LHS tries to keep follower in the best response area. Therefore, since the convergence rate is slow with the indirect gradient term; while the training may not stable without it (Wang et al. 2019), could we find a balance that maintain the good properties for both fast convergence and stability by removing some terms which are closely related to the best response indicator L(0,w)
Here, we observe that the TD-related term is a good option because it contains the residue term Q (8 QT (s,a) that are closely connected to [(O, w), which indicates the distance to best response. Thus, removing them could reduce the influence of the best response in indirect gradient 0 @* (s.a) Ow
to the follower (actor). Another advantage is that since (partial of) the Hessian matrices
@2Q2" (s.a) are hard to compute, reducing them can help improve the computing time. Owod
and
But, one still needs to compute the inverse matrix, which dominates the time complexity for com- puting the gradients. To simplify the computation, Sec. 4.2 we propose to use block-diagonal approximation approximate the inverse matrix.
4.1 DERIVATIVES L'1(0,.)
8" L(0,w)
AND
090w
Ow
First, we show how to simplify the indirect gradient term in 3 by proposing the following proposi- tion:
Proposition For SDDPG and STD3,
L(9.w.) 80the
and
L(9ww) Ow
can be further explicitly expressed
as:
8 L(0, w)
dw
( ( (
The
(s,a)
000w
dw
30
Ow
(s, (s,
Q (8,0)
(5)
ThT
Or
L w) Ow22
SQ7 (s, 0Q% (s, aT + (Q (s.a) (s, a))
o @Q (s,
= Ep(()
(6)
Ow
Ow
Oue
Proofs can found Appendix A Notice that here we use the chain rules of composite functions
@Te (8,a), which is different from the original DPG form Siiver et al. 2014). Our form is more
suitable for our bi-level optimization settings. Discussion can found in Remark iin Appendix A
Also note that both 5) and 6 contain the residue term Q (s) a), which can be ignored if pts) [1 (s, a)
T
a))
is small. Eqs. and 66 then degenerate to:
LL(0, w)
2Bp()
Q (s
a)
Ow
Q (s, = 1: w),
a00w
Ow
00
Ow
8 LL,(0, w) Ohe
2 aQ0 (s, a)
8Q (s, (..a)
Ba(a)
kz
Ow
Ehe
Substituting w) (0, w) into the follower's approximated update scheme become
Ta,( w.)
OJ wx.)
0+1 0: +
a0, k2
Ow,
The leader update scheme is still the same as in (4. Intuitively, 7 reduces the TD-related terms
which consequently reduce the time from O (mere m the gradients. Details are shown in Sec.
to O (max moaxx(m21r (m=2 mmmo (T) to compute
Notice that (0, w) is also known the Gauss Newton matrix (Schraudolph 2002 Besides fast computing, the Gauss Newton matrix is always Positive Semi-Delinice (PSD) which helps better
convergence comparing with the Hessian term (LL(0,0) which may not guarantee PSD Martenns Pu1 2020). This gives us a numerical analysis perspective why the our approximation works.
We will show that improves the convergence rate theoretically and empirically in Section
For simplification, use kn and 2 denote ky (w. 9) and (2 0).
4

---

Under review as a conference paper at ICLR 2022
4.2 APPROXIMATED INVERSE K2
(2 w) and ki (O, w) do not include any Hes- sian term, which avoids (mm²n) for computing partial of the Hessian matrix. However, com- puting the gradients of the FSDDPG still ex- pensive since inverting 22 (nm x nm size ma- trix) usually takes O(m time.
Algorithm FSDDPG algorithm
Randomly initialize Q(s, a alw) and π raas, (alss,00 0). Initialize target network Q', n', and replay buffer R.
for episode 1, M do
Using to interact with environment to ob- tain transitions (3t, aey Tt, 8t+1).
To accelerate the computation of k we use block-diagonal approximation scheme:
R= R U (st, at, Tr, 8t+1).
k2 = == hy @ k2 L ..... @ ka, where k; is the ith diagonal block of k2, @ is the direct sum operator, and d E Z+ is the number of diagonal blocks which can be set manually. Define o == d|mm, where is the integer division operator as the diagonal degree. Also notice that the time complexity of inverting block diagonal matrix is equal to the sum of inverting each block (Boyd 2004). Thus the time complexity of inverting (o))) - mn
Sample N transitions from R.
Update the critic using @L(0.w)
Dhe Update the actor policy using the sampled @J(0,w) kyke
policy gradient: 88
a.(0.)) Update the target networks.
8m
end for
the matrix 22 is reduced from O ((rm)))) to
(mno*)
Since inverting k2 dominates the time complexity, when it is reduced, time complexity reduces to O (max(m²r) , ,mnoo)) )() consequently. More details can be found in Appendix C
4.3
TIME COMPLEXITY FOR COMPUTING THE GRADIENT
The time complexity analysis table is shown in Tab. 1 SDDPG is the Stackelberg learning method directly implemented to DDPG (as mentioned in Sec. 3), and SDDPG-CG is the SDDPG with Conjugate Gradient (CG) technique to approximate for the inverse Hessian matrix (Zheng et al. 2021a
Wen et al. 2021). SDDPG-BD is SDDPG with the block diagnal technique.
From empirical studies, we found that taking 1 (just taking the diagonal) is sufficient to be well- performing. Also, e is always small to guarantee performance. Thus, in practical implementation, ours is faster than SDDPG-CG.
Notice that the diagonal block technique may not suit vanilla SDDPG well. The main reason is that L(0,w,)) the term 063w still contains (partial) of the Hessian which needs O(n2m²) to compute, which have been removed in ours. Thus, the time complexity of SDDPG with diagonal block technique (SDDPG-DB) larger than ours when is small. Moreover, the mainstream deep learning frame-
8 L(f,w) in parallel a0che
work (e.g.. PyTorch (Paszke et al. 2019)) does not support calculate diag through GPU, which makes it hard to implement in practice. Details are in Appendix G Therefore, the diagonal block technique is an approach that design for our reduction.
Our method can also adopt CG to approximate the k aJ(0,,..), which solves the linear system Owy
aJ(0,,w.) where x the vector be solved. We name this method as FSDDPG-CG (ours). kyz 8we
Table 1: Time complexities of calculating the follower's gradient for SDDPG, FSDDPG (ours), SDDPG-CG, and SDDPG-BD, Here, n is the size of layer, and m is the number of neurons in each layer. is the total number of episodes. solutions for CG.
[1, mn] is the diagonal degree. e is the c-optimal
SDDPG
ESDDPG
SDDPG-CG
SDDPG-BD
Time complexity
O (m= (m))))
O (max m n² mno") yT) O (m (m²",T/0)
O ( mmax umoo 2mm" T))
5 THEORETICAL ANALYSIS
This section focuses on some theoretical results of our FSDDPG.
In this subsection, we regards ko as a mm x nm matrix since 0 and t are fixed.
We assume am is interger.
5

---

Under review as a conference paper at ICLR 2022
Before go deeper into our analysis, define useful notations that help the analysis:
J(8,w, 1 (0) (0)
a-J(0.w)
((0)
80
aL18,00 an) cha
is the dynamics of our FSDDPG, T ==
Gac. is
the
defined as the time separation.
we also define the Jacobian of the dynamics of our method as:
2 #- 100,10)
11 kg
0- (=-](0,0)
H- J(0,00
k1kg
0- ((-,0)))) the
Js( =
30
80
dw
The
00
8 L(0,w))
8² L(0,w) .))
898hc
Ow?
and 5 (0*) Js (0") Jss(0 (s()))) where 0
= [0, wi (0" = 10", wn] is fixed point), and
T (00)) = (Js ) Js (0*)) which helps our analysis.
Now, we prove that method can converge fixed point.
Theorem When x E CS O, RR) and Q E C" @ A & W,R), 9 2 2. For a fixed point 6 and w" such that Js (0r) + Js (0") is positive-definit the our method with learning 1/2
L converges locally with a rate of O ((1 (1- 266 where u = Xmiin (S (0")),
rate a
Amax (T (0)))
The proof sketch follows Theorem 5 in (Ficz et al. 2020 To compare the convergence rate FSD-
DPG (ours) and SDDPG, firstly define linear actor p(s)0, where sp(s) is the embedding
((s))
(abstract state), 0 is the learnable parameters. The linear critic is Q(s. = 4 (s) w where w is the learnable parameters for critic.
We now show that for linear actor and critic, under some mild assumptions, the convergence rate of FSDDPG is equivalent to or faster than that of SDDPG, which is ((1
T/2
6
(The proof
2Ø
similar to Theorem and we provide details in Appendix D). where à = A ($(0r)
Amax (f (00). and (--) as wells as 7-)) are defined similar to S(-) and T(-) by replacing k kig 88 ((9.w) Bhe
0 L(0,00) D00w
-1 in Js(+), respectively.
with
(s)
> where A any Positive Semi Definite (PSD) matrix. Then, the convergence rate of FSDDPG (ours) is faster than equivalent to that of SDDPG.
Theorem 2. For linear actor and critic, if w
p(s)
The proof sketch relies on Matrix inequality. The motivation behind this is that we can show that (0*) (resp. (Js (0*) Js (0r)) with TD-related term minus S (0") (resp. (Js (0r) Js (0*)) is always PSD (resp. NSD), which imply the relationship in eigenvalues of S (0*) and (Js (0*)* Js (0*)) Notice that since the convergence rate is decided by these eigenvalues (Theo- rem D. we can thus obtain the result.
We can toy example I as application of Theorem 2 (environment setting is in Sec. 6.1 After calculation, we find that the the theoretical convergence of SDDPG is near O(17/2), while FSDDPG is O00.757/2). This coincide with our empirical result that ours is faster than SDDPG. Details are Appendix(D
The following we show some properties of our method (Details are in Appendix F):
We show the counections between Eq. 2 FSDDPG (ours) and SDDPG:
Corollary 1. If (8","")) w²) the optimal solution for SDDPG. Then, (0", w²) is also the optimal solutions for Eq. ( well FSDDPG.

---

Under review as a conference paper at ICLR 2022
Figure I: Toy examples. The first row is the toy example and the second row is the toy example
2. The first column is the trajectories of 8 and w (The contours are for L(0, w) value). The second column is the trajectories of 0 and w w.r.t different episodes (The contours are for J(0, w) value). The third column the training curves. The forth column is the enlarged part of the training curves.
We also show that our method can avoid strict saddle point almost surely under mild assumption in Appendix F
6 EXPERIMENTS
6.1 EXPERIMENTS ON TOY EXAMPLES
Environment Semu. Inspired by (Zheng et al. 2021a), we conduct two toy examples to illustrate that our methods are fast convergence and do not being easily trapped into bad local optimality and limited cycles. In the first example, we set both actor and critic as a one-dimension scale
and w respectively. The reward is set to r()) = - Thus, i(0 w) I.(0, w) (wr0² + 02)2,
[(, w) = wt2 The optimal solution of the the first toy example is 0t = 0, w² = -1. The second example is similar except that set Ī(0, w) L(A, w) (wo 02)2, J(8, w) wt. The
optimal solution is 8" = 0, w" = 0. The initial point for the two examples are = 1, = 1 and
0 2, w 2, respectively. The distance optimality is defined as (w w²)² (0 0²)3. Toy example 2 is harder than Toy example since the best response w.r.f w are w = -1 and w = respectively, i.c., w² is a constant in toy example while w" needs to trace the value of 0 in toy example 2.
Baselines. We compare our methods (without block diagonal approximation technique) with for DDPG [Lilierrap et al. 2016). and SDDPG (Zheng et al. 2021a). Notice that due to both the parameters for actor and critic are one-dimension.
Results. As shown in Fig. for the first example. DDPG and FSDDPG (ours) converge faster than SDDPG, while DDPG much more unstable than ours and SDDPG since moves very far away from the goal. For the second example, DDPG is trapped into the limited cycle, while both FSDDPG (ours) and SDDPG finds the optimal efficiently. Also, ours converges faster than SDDPG. These results reveal that DDPG converges fast yet relative unstable. SDDPG is stable but converges slowly. Ours method combines both the advantages of DDPG and SDDPG, i.c., it converges fast while maintain the stability during training. These results coincide with the assumption that eliminating the TD-related term can improve the convergence rate in Sec. 4
We also visualize the trajectories on the contours of the [(0, w²) value in Appendix H Results find that SDDPG tries to stay in the best response area, while ours are somewhat drifts from best response area, but it returns back only after few episodes. DDPG could drives very far from the best response area.
6.2 EXPERIMENTS ON MUJoCo
Environment Setup. We conduct our experiments in standard physical simulator MuJoCo (Toorov et al. 2012), including Ant, HalfCheetah, Humanoid, InverredDoubleeeendduum. InvertedPendulumm Swimmer, Reacher, and Walker. The network sizes 16 x 16 for all the methods to make SDDPG and STD3 trainable, larger networks make SDDPG and STD3 hard to train. All the experiments conducted single GeForce RTX 2080 Ti GPU and Intel(R) Xeon(R) CPU E5-2680, and
7

---

Under review as a conference paper at ICLR 2022
Table 2: Ablations on running times in different degrees for diagonal block approximation.
Average Running times (scconds) of cach episode
FSDDPG-DEG
FSDDRG-DEG2
FSDDRG-DEG
22.73
TW7 70
(d) InvertedDoubleeenddu
(a) Ant.
(b) HalfChectah.
(c) Humanoid.
lum.
(c) InvertedPendulum.
(f) Swimmer.
(g) Reacher.
(h) Walker.
Figure 3: Results for various methods on MuJoCo.
implemented by PyTorch (aaskee al. parameters can be found in Appendix
2019). More details on the environments and the hyper-
Baselines. We uses DDPG (Lillicrap et al.
2016) TD3 (Fujimoto
et al. 2018), DDPG-TTSL SDDPG-CG, STD3-CG (Wen et al.
2021 Zheng et al. 2021a b) as our baselines:
1) DDPG a deep learning implementations of DPG.
2) TD3 the DDPG method with twined delayed crities to avoid high variance.
3) DDPG-TTSU is similar to DDPG except that the critic is up- dated much more frequently than actor. In our experiments, we the frequency ratio as 10:
Figure 2: Ablations on average returns in different degrees the diagonal block approximation.
4) SDDPG & STD3 are the Stackelberg learning of DDPG and TD3, respectively.
5) SDDPG-CG & STD3-CG are the SDDPG and STD3 with conjugate gradient to approximate the inverse Hessian, respectively.
Details on the hyper-parametent can be found in Appendix
Results. As shown in Fig. FSDDPG (ours) reaches the best performance in Humanoid, while FSTD3 (ours) reaches the best performance in 6 out of 8 environments (Ant, HalfChectah, Inverted- DoublcPendulum, InvertedPendulum, Swimmer, and Walker). More specifically, comparing FSD- DPG with DDPG, and FSTD3 with TD3, FSDDPG outperforms DDPG in 6 out of 8 environments (Ant, HalfCheetah, Humanoid, InverteDDubleeeeddiimm Swimmer, and Walker); FSTD3 outper- forms TD3 in all of the environments. Results indicate that our approximated Stackelberg scheme does improve the performance.
For SDDPG-CG and STD3-CG, they do not perform well enough in many environments comparing with ours due to the slow convergence rate. But they could perform better than DDPG and TD3 for some environments that DDPG and TD3 are not converge well (e.g., Swimmer and InvertedDou- blePendulum for DDPG).
For DDPG-TTSU, its convergence rate is comparable to FSDDPG and DDPG in all environments. But notice that the critic needs to be updated for ten times in each episode, its actual convergence rate is slower.
We conduct extra experiments in terms of the training times. We use CPUs to testify the training time since precise GPU time per thread is not easy to estimate. As shown in Fig. 4 find that
8

---

Under review as a conference paper at ICLR 2022
710
333
TELL
9000
TTLL
400
(a) Reacher.
(b) Ant.
(c) HalfChectah.
Figure 4: Average running time per episode of different methods. The enlarged training time per
episode different methods is shown Appendix H
Table 3: Ablations of training time per episode on different Hessian approximation approaches.
Average training times (scconds) of each opisode
FSDDPG (ours)
FSDDPG-CG (ours)
SDDPG-CG
SDDPG-D8
SDDPG
HaltChectah
29.27
2000
2000
Inverted Double Pendulum
12.19
28.45
43.58
446
1780
Inverted Pendulum
13.25
30.96
43.69
339
1268
the training time of SDDPG is far longer than others. Also, DDPG-TTSU and SDDPG-CG are all requires more training time than ours. This reveals that our methods are fast to compute.
Ablations. We firstly compare the performance of different Hessian approximation methods, in- cluding FSDDPG-CG and SDDPG-BD (SDDPG with the diagonal block approximation) in Fig. Results show that the ours with CG perform better than ours with DB approximation in 2 out of en- vironments. However, as shown Tab ours with CG requires twice training times than ours with DB approximation to reach that performance. Thus, we choose the diagonal block approximation as our final method since it balances the tradeoff between times and performance well. Combining Fig. 5 and 3 we find that ours with CG performs much better than SDDPG-CG. Thus, it reveals that the TD-related terms do affect the convergence rate in complicated environments.
In terms of SDDPG-DB, from Tab. we find that SDDPG-DB is still slow in both computing and convergence comparing with FSDDPG, revealing that the block diagonal method may not suit SDDPG well, which testify our claim Sec. 4.3 Also, regarding the average returns, as shown in Fig. 5 SDDPG outperforms SDDPG-DB. Together with the result of FSDDPG, we conclude that the improvement of performance is mainly based on removing the TD-related terms rather than using the diagonal block approximation.
We also testify how the change degrees o affects the performance. As shown in Fig. and Tab. the increasing of the degrees costs more training time but leads to better performance. Moreover, we run the SDDPG (without approximation), and the results reveal that SDDPG is relatively slow. whether the leaders in best response areas, and
Finally, we visualize the losses of critics the results coincide with the results in Fig. Details are in Appendix H
1239-
(a) HalfChectah.
(b) InvertedPendullum
(c) InvertedDDubblePedduuu.
Figure 5: Ablations of average returns different Hessian approximation approaches. SDDPG-CG (ours) does not be conducted in HalfCheetah due its long training time.
7 CONCLUSION
This paper aims to mitigate the challenges of high complexity and slow convergence rate in current Stackelberg actor critic scheme. Specifically, we propose an approximated Stackelberg Determinis- tic Policy Gradient that removes TD-related terms to improve convergence rate, and together with the block diagonal approximation technique to further reduce the computing times. Experiments show that outperform SOTAs in terms of average returns under acceptable training times.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Joshua Achiam. Spinning Up in Deep Reinforcement Learning. 2018.
Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep rein- forcement learning: A brief survey. IEEE Signal Processing Magazine, pp. 26-38, 2017.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Grae- pel. The mechanics of n-player differentiable games. In ICML, pp. 354-363. PMLR, 2018.
Jalaj Bhandari, Daniel Russo, and Raghay Singal. A finite time analysis of temporal difference learning with linear function approximation. In COLT, pp. 1691-1692. PMLR, 2018.
Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical Gauss-Newton optimisation for deep learning. In JCML, pp. 557-565. PMLR, 2017.
Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Qi Cai, Zhuoran Yang, Jason D Lee, and Zhaoran Wang. Neural temporal-ditee -diffeeeee and q-learning provably converge to global optima. arXiv preprint arXiv: /905. /0027, 2019.
Benjamin Chasnov, Lillian Ratliff, Eric Mazumdar, and Samuel Burden. Convergence analysis of gradient-based learning in continuous games. In UAI, pp. 935 944.944. PMLR, 2020.
Pei Chen. Hessian matrix vs. Gauss- hessian matrix. SIAM Journal on Numerical Analysis, pp. 1417-1435, 2011.
Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications reinforcement learning. In COLT, pp- 1199-1233. PMLR, 2018.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep
reinforcement learning for continuous control. In ICMI. pp. 1329-1338. PMLR, 2016.
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in Stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In ICML, pp- 3133-3144. PMLR, 2020.
Zuyue Fu, Zhuoran Yang, and Zhaoran Wang. timele-ti actor-critic provably finds globally optimal policy. In ICLR, 2020.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In ICMI., pp. 1587-1596. PMLR, 2018.
Saeed Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint arXiv:/802.022446, 2018
Riccardo Grazzi, Luca Franceschi, Massimiliano Pontil, and Saverio Salzo. On the iteration com- plexity of hypergradient computation. In ICML, 2020.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critie: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In ICMI. pp. 1861-1870. PMLR, 2018.
Harold V Henderson and Shayle Searle. On deriving the inverse of sum of matrices. SIAM Review, 23(1):53-60) 1981.
Kaiyi Ji, Junjie Yang, and Yingbin Liang. Bilevel optimization: Convergence analysis and enhanced design. In ICML, 2021.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-noncomean minimax optimization? In ICML, pp. 4889. PMLR, 2020.
Maxim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, and Hoi-To Wai. Finite time analysis of linear two-timescale stochastic approximation with Markovian noise. In COLT, 2020.
10

---

Under review as a conference paper at ICLR 2022
Jens Kober, J Andrew Bagnell, and Jan Peters. Reinforcement learning in robotics: A survey. WJR, Pp. 1238-122221 1238-1274, 2013.
Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. ICLR, 2016.
Bo Liu, Ji Liu, Mohammad Ghavamzadeh, Sridhar Mahadevan, and Marek Petrik. Finite-sample analysis of proximal gradient td algorithms. arXiv preprint arXiv:2006. 14364, 2020.
Jonathan Lorraine, Paul Vicol, and David Duvenaud. Optimizing millions of hyperparameters by implicit differentiation. In AISTATS, pp. 1540-1552. PMLR, 2020.
James Martens. New insights and perspectives on the natural gradient method. JMLR, 21:1-76, 2020.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approxi- mate curvature. In ICML, pp. 2408-2417. PMLR, 2015.
José Mario Martinez. Practical quasi-newton methods for solving nonlinear systems. JCAM, pp- 97-121, 2000.
Eric Mazumdar, Lillian Ratliff, and S Shankar Sastry. On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, pp. 101-131, 2020.
Raman K Mehra. Computation of the inverse hessian matrix using conjugate gradient methods.
Proceedings of the IEEE, pp. 225-226, 1969.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1rXiv:1312.5600 2013.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. NeurlPS, pp. 2318-22182 2228, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. NeurIPS, pp. 8026-8037, 2019.
Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with im- plicit gradients. NeurlPS, pp. 113-124, 2019.
Lillian J Ratliff, Samuel A Burden, and S Shankar Sastry. On the characterization of local Nash equilibria in continuous games. TAC, 61(8):2301-2307, 2016.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. ICLR, 2018.
Nicol N Schraudolph. Fast curvature matrix- products for second-order gradient descent. Neural computation, pp. 1723-1738, 2002.
J Shewchuk. Conjugate gradient without the agonizing pain. Technical report, 2007.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In ICML, pp. 387-395. PMLR, 2014.
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review bilevel optimization: from classical to evolutionary approaches and applications. TEC, pp. 276-295, 2017.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
Richard S Sutton, Csaba Szepesvári, Alborz Geramifard, and Michael P Bowling. Dyna- style planning with linear function approximation and prioritized sweeping. arXiv preprint arXiv:/206.220 2012.

---

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 ICLRS, pp. 5026-5033 IEEE, 2012.
Saran Tunyasuvunakool. Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, Nicolas Heess, and Yuval Tassa. dm_control: Software and tasks for continuous control. Software Impacts, pp. 100022, 2020.
Hao-nan Wang, Ning Liu, Yi-yun Zhang, Da-wei Feng, Feng Huang, Dong-sheng Li, and Yi-ming Zhang. Deep reinforcement learning: a survey. Frontiers of Information Technology & Electronic Engineering, pp. 1-19, 2020.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. ICLR, 2019.
Junfeng Wen, Saurabh Kumar, Ramki Gummadi, and Dale Schuurmans. Characterizing the gap
between actor-critic and policy gradient. arXiv preprint arXiv:2106. 06932, 2021.
Shimon Whiteson. Expected policy gradients for reinforcement learning. JMLR, 21, 2020.
Yue Wu, Weitong Zhang, Pan Xu, and Quanquan Gu, A finite time analysis of two time-scale actor critic methods. arXiv preprint 20x.::200000033000 2020.
Peng Xu, Jiyan Yang, Farbod Roosta- Khoras-K, Christopher Ré, and Michael W Mahoney. Sub- sampled newton methods with non-uniform sampling. In NeurIPS, pp. 3008-3016, 2016.
Zhuoran Yang. Yongxin Chen, Mingyi Hong, and Zhaoran Wang. On the global conver- gence of actor-critic: case for linear quadratic regulator with ergodic cost. arXiv preprint arXiv:1907.06226, 2019.
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for Minimax optimization. arXiv preprint arXiv:2006.14520 2020.
Liyuan Zheng, Tanner Fiez, Zane Alumbaugh, Benjamin Chasnov, and Lillian Ratliff. Stackelberg actor-critic: Game-theoretic reinforcement learning algorithms. arXiv preprint arXiv:2109.12286 2021a.
Liyuan Zheng, Tanner Fiez, Zane Alumbaugh, Benjamin Chasnov, and Lillian J Ratliff. Stackelberg actor-critic: A game-theoretic perspective. AAAI-RLG 2021, 2021b.
12

---

Under review as a conference paper at ICLR 2022
A DERIVATIVES
This section we discuss the derivatives.
We firstly introduce lemma that helps our analysis.
Lemma 1. We have Vo [QTh (8, mo(s))]
(Bp(.) V VOTO [Va l==
Proof. By using the Leibniz integral rule Vglppss) (Q (s, To (s))], have:
Boe) (ww (s, (+())) = pp))) VoQw (8, +o())) = ppts) VoTO(s) VaQw (8, a) ))l==mo())
which achieves our desired result.
This lemma reveals that our off- off-ppolcy gradient is different from the gradient derived in (Silver al. 2014). Remark D discusses why they are different, Lemma CommaZdiisen discusses when these two methods have the same results.
Now, we derive the derivatives using Lemma
!
(L(..))) 80thr
8 (L Ow
Proposition For SDDPG and STD3,
and
can be further explicitly expressed
(
(
2 Q
Qw (s, a) dw
)
2Ep(s)
Q (s,
a00w
dw
00
Ow
Q (s, a)) ))]
(Q (s, a) Q) (s,(
(8)
Tg
dw
LO, w) Ow
TQ (8, a) TQTH (8, a)
O² Q (s,
= Ep(s)
+ 2 (Q2e (s. (s,
Dw
Ow
Ow
Proof. Based the basic technique of matrix derivatives and the integral rule of interchanging the integration and differentiation, we have:
L(8,w) Ou2
Si Qhe (s, Qc))(s
Ep(s)
=2Epp(s)
Fw0 QTe (s,a) Q (s,
Fw Qu (s.a)]
Q
(10)
(
(00 (s.0)
aQ (s,a) + (s. Q (s.
80 (3,a)
2)p(s)
Ow
Om
Ow
and
L(
(o The (s, (Q*o(s,a)))
Ep(e)
000w
30
Fw
=2 2
a
E
Ep(s)
Q (s, a) 1 (Q (s, (s,
ow
a
Que (8,
2F)(s)
8
{ (s, a)
(Q (8,
Q (a, a))
56
Fw
2Bp(s)
9
Que
(s,a)
a
(s)
+ (Q (s,
Q
(s, a))
30
dw
= 2Ep(sy
39 QT (s,a)
á (s.a)
The
+ @ww (5,
a)
(Q+ (s.
89
B
2Bperi
Q (s, a)
Ow
Qu (s,a)
80
8w
+ (ox (s,a)= 1 (Q (8,4))
8
Qu (8, a)
50
Tw
13

---

Under review as a conference paper at ICLR 2022
The last equation
due
the fact that
e 20
(s,
e (s,
Q (z)
20
e Uw
Que
the 0B
With little abuse of the notations, for the last equation, use Q (8, to replace 1 (Q% (s, a)).
Remark 1. Here, comparing with off-policy DPG, our derived policy gradient is different. In Sil-
ver et al. 2014) under some assumptions (mentioned in Appendix A Siiver 2014 the
[deterministic) policy gradient is from Q (s,a)
VolEpt)) (s, [o(s))]= Ppss Ve f (T(ass)) a)]daj -B(c) VoT (s, + SA v(ass) (s, a)da) [ (V (8.))(( (=))(s)) VoQ (s, a) (a==)(s))
(11)
The second equation is based on the integral rule of interchanging integration and differentiation, and the chain rule. The last equation is based on the property of the Dirac-Delta function. Then Q (8, vo(s)) is approximated by Q (8, To(s)) ()) to make the Q value trackable.
For ours, Qhe (s, a) has been already introduced when the objective is formed. So, by the integral rule of interchanging the integration and differentiation, Vo 1QTH (s, mo(s))] =
Epts) NoQT (s, (s,To(s)) =p(s)) VOTO(S) NoQTH (s,a)) (s,a))a-mnos) Therefore, gradient is act and does not have extra term.
The reader may ask: why the two proofs have different results? The main reason is that in the second equation of Eq. (TT). in order to use the integral rule of interchanging the integration and differentiation Q% (s.a) should be continuous function w.r. 0 V A. But according to our definition, it is only differentiable w.r.t 0 when a = x(s). Therefore, we can not use the technique as DPG. The following we show that when Q satisfies some conditions, the gap can be bridged:
Lemma 2. Q is always a continuous function w.t V a A. which w.l.ogg is represented as Q(s, a, f). The derivatives of Ep(s) [Q(s, To(s), 0)] derived by (Silver et al. 2014) and ours are equal.
Proof. First of all, following the same steps in off-policy DPG, we have:
VoEMo
Q(, (o(s)
Ep(e)
Va ((s,,))((s,,
Ep(s)
La (os + ( ((ss) a,
Ep(s)
SA (or 0dda + (e
Ep(s)
Vono(s) VaQ () + voQ(s,
(a) follows the property of Dirac-Delta distribution. (b) follows the the last equation in Eq. (15) in Siiverr et al. 2014). The result can also be found Corollary in (Whiteson, 2020).
For ours, following the chain rule, we have:
VoEpts]((s Te(s), 0)] = ppts) VoQ(s, + Veno(s) a, m))=))
Then, easily check the two derivatives are equal, which is our desired result.
Here, we show the reason that the stop-gradient operator is necessary in L(0, w): because 00 p(())) [(QT (s Q=t (s,a)s)))) may not be well-defined since oh Q (s, does exist in our settings.
Lemma 3. 34 differentiable.
is not well-defined if r(s, (o(s) and p (s'l s, (s()) are non-
Details can be found in http:////eeti..oooeeeoeeeeee//rs when we- org.rrahnnngaaaaaaattoaaaaaaaaaa
14

---

Under review as a conference paper at ICLR 2022
rewrite the state-action function under the expectation of rewards for different trajectories:
Proof. We
(st,
E where r
p(srsst, (s()))
II k=t+1
no (s(s))((sx+tll (s())) T is the probability of trajectories.
dr ds; II
dayds;
k=(+1
Then, have:
(s))))))))))) = E, ERke +
4 1 dr
p(s To [ (0(s))((s++11s)) mo(sk)) (s'r'(s, mo(s:) + Ek=e+1 1hr dr
p (st) II na(ax
+ Ek=141 *ha dr + Eis+1 phrn dr
p(s Ik=141 (o
@ JTiA p(144 st, mo(s)) (o
(I4 no(aro 844
(1 (0, Ex (hyh) da ddd
①
Ji p(s no(s)) (1 ax))
(p($442/5441 (
C To(S:)) + Ei-41 xkrrt) dr att1
-TT(U IT P(sktils, no(sk)
((())))))) drl (Ut))))1)
(a) is based on the Fubini's theorem.
(b) is due to the property of Dirac-delta function.
d(r)a means di ( II dagdss).
k=t+2
T/A means removing the A from T.
According to the assumptions, r(s, no (s)) and p (s'l () non-differentiable w.r.t 0.
Since TT (st, (s())) does not contain any differentiable elements, a e (s)Tsss)))) are not well- defined.
This Lemma reveals that the - QT n (+)) is not well-defined in many cases, since most of the environments are natively non-differentiable w.r.t the parameters of policy, e.g., (Todorov et al. 2012). That another reason that we need to use the stop-gradde gradient operator.
B BLOCK DIAGONAL MATRICES
We firstly define =: k2ding (k2) - I
We now show technical lemma here:
15

---

Under review as a conference paper at ICLR 2022
Lemma 4. (Henderson & Searle 1981 For two non-degenerate matrices A and B, always have:
(A + B) = A-
Now we show that larger does not mean that the distance will be smaller: Lemma 5. Dik,, diag"(k2) (k2)) is not always monotonic decreased w.r.l
Proof. This can be done by finding counter-example:
1
1
1
27
1
1
3
For l2
we have D diag (k2)) 11.0, D (k2, diag = 8.2,
1
9
4
5
5
6
1
D (k2, diag (k2))
10.7.
But we can always find a sub-series that satisfies the following Lemma: Lemma 6. When can be represented lz, where x, I E Z+ D (12, diag)* is strict decreased series with the increasing of
Proof. || diag'"(k22ll (k2)]lF=
Σ IJEG
|kall (i. * lzj + + 1z2....,
||k ding (1+1)z (k2))lB
Σ HE
lkgl G1 (i,jli (1+ 1)2j + k 1.2...
....... .l 1)x}
Since G C G1, we have:
Σ lkyl We
Ikagl
V
||kg diag LF (ll) l|ke ( < 0.
kincellk2 diag (k2))lr = O. So D (k2, diog (ki2)) a strict decreased series with the
increasing of l.
Therefore, we conclude that we can select a series of o that are have the same common factor larger than to guarantee that the distance D (k2, diag (Ri2) is a strict decreased (e.g., 2, 4, 6, .....).
C TIME COMPLEXITY FOR COMPUTING THE GRADIENT
We assume that critic has layers with neurons, while actor has nı layers with mi. We also define as the training episodes.
We define OP the time complexity of multiplication two real numbers, OPe the time com- plexity of calculating the gradient of one element w.r.t other, and OPA as the time complexity of adding real numbers.
Now we analyze the one step time complexity of different terms.
1) The time complexity of The Q" (s, a) is
OPa m n++ m²) +OM (Ert]m?) = OPo (m + nm?) + OPar (n + 1)m?
m + Enth =2 m² because the the dimension gradient between the output layer and the last layer
m,, and thus the dimension of gradient is m² for each intermediate layer. (E m²) is because each layer requires m² times multiplication to form the chain rules.
Recall the time complexity of multiplication two matrices with dimensions m, n and n. p is mnp.
16

---

Under review as a conference paper at ICLR 2022
0z is ( (O&& (m1 + nim?) OPM (n1 + 1)m3), which follows the same The time complexity of 06
analysis of Fw Qw (s,
Combining the above analysis, the time complexity of @J(6,w)
is
Bio
(OPa (m + nm²) + OPr (n + 1)m²), which follows the same analysis of Tw Qu (8,0).
2) The time complexity of aJ(0.wl is
99
(OPc (m+ + nm?) + OP (n+ 1)m²) + (OPc + +PM)) + (OPG (m1 + n1mf) + OPM (m + 1)m + +OPM (mn + mım1)
which
combination of the time of calculating OPo (m + mm²) + +OPM (n + 1)m²) times), (OPa (m) + mmm) + +0PM (n, 1)mf)times)
a Q (8,a) dw
(require
di 8i
(require (OPa + OP
times),
and
On
(require
(since
a)(0, 09
Σ
a Ban
Q (s, a)
dw 0z Bi 0H ).
3) The time complexity of E (Q." is exactly the same as a0(0.))
00
4) For the time complexity of @
Q (s,a) is
OPg (m + nm²) + +OPM (n + 1)m² + nm0PG (m + Σ n+ i m
+ nm0PM (Σ m+? + OPM n(n + T)m?
OP (m nm²) + OPM (n + 1)m2 + OPo (nm² + n m²
which is based on the fact that the Hessian can be decomposed to The
Sw Q (s, a))-
5) For
a a
Q (s,
50
Tw
mimi (OPe (m + nmm) + OPM (n + 1)m²² ) + -nmi + OPM) )m
+1 (Opa (m1 + m2m?) + +OPM (n1 + 1)m3) + OPas (mn + min1)
6) The time complexity of (ou Q (s,
Ow a)
) oow Q
@ (s.
is the summation of
00
a Qwi (s, a) The
dw and 56
Pu Q" (s, a), and their multiplication.
(OPc (m + nm?) ) + OPM (n + +)m²² + (OPG mP
+ (OPG (m1 + n1m?) + OPM (1++1)mf +OPM(mn + m2n1)
+ (OPG (m+)m²² + +PM (n+ +1)m²) + +PPM(mmmm))
0 (max {nm², mmmmm.,
OQ (s, a) aQw (s,a)
7) For
dw
Dw
(P&a (m + nm?) + OPM (n + 1)m²) + +PM (m²n²)
Combining them together, for
Ep(s)
a The
Q
Th (s, a)
50
Ow
) (22Q dre QTe (s,0)) + (Q% (s,a) - (s,"(s,)) a
00 dw
a
Q (s,a)
the time complexity is:
OP& (m + (mm)) OP (n +)m? + (OP& + OP
+ OPp (m + mmm)) + OP (n1 + 1)m?) OPM (mn + min1)
+ (OPG (m (m+
OPM (n+ 1)m²) + +O (m
tRim (OPa (m nm=² + -PP (n 1)m²) + #nmm + OPa)mm
+nimi OP& (m + nmm?) + +OPM (ni + 1)m3) + +OPM + min1)
O (max mnfm) niminm]
17

---

Under review as a conference paper at ICLR 2022
(2 (2 (x.a)
- + 2 Qw ( (s, aQ (s.a) dw
@2 (s.a) cw
For E Eps))
the time complexity
the
is:
OP& (m + nmm
OPas (n + 1)m²) OPMs (m²n²²
calculate kn
OPG (m + nm²) OPM (n + 1)m²
OPG (nmm² +n²m²) + OPM n(n + 1)m²
calculate
=0 (n²33)
For inverse 1i2 + fiz, the time complexity is:
OP& (m + nm²) OPas (n + 1)m² [OPaenfm]]
caleutate
OP& (m + nm?) +OPM (n+ + 1)m?
OP& (m² nmm2) + OPM (n 1)m²
calculate
O m² (n"m²)
inverse matriz
=0 (n²m²)
For inverting (k2)) the time complexity is:
OP& (m + nm²) + OPrs (n + 1)m?] + [OPMM)m] + OPom2
(
n
+
o 0
Tum
cateulate part of loa
Anverse matriz
entract the diog (k2)
n'm² a2 =0 { nmm nom?,nmms nim,, }1)
For inverting diag (k: + K2) OP& (m + nm?? + OP (n + 1)m²] + @[OPMM + +Pamm
caleulate part of
n m3
7m 2
OP& (m + nm? 2) + OPM (n + 1)m² + [PPMn)m + +Ppm++0
+
13
k
calculate part of 82
inverse matria
diago
= =0 { numm
nim,, pomm,,im
n nmm 12
Therefore, the time complexity of calculating the actor for SDDPG in Eq. 44 is
O max nmm ni mmmp] t (m)n t (mimmmn)t++ + n'm S + ne mift
uo (oin) and on J0 (ave)
multiply matrices
get t
O max {nimn" nime, m
The complexity of FSDDPG (ours) is
o max nmm nmm3) + m2?tt + (om²n?) t max {nm?, (nm?nnmmj mim,, o"
00.0.c.m (r.a) and TO (eia)
multiply matrices
O (max (nfmp, minmmn, nm? m m o, 03) t)
18

---

Under review as a conference paper at ICLR 2022
The time complexity of DPG is:
O
max (nmm² n2 mt)
BQ2 (xyo)
The time complexity SDDPG-CG is:
max nmm, nim3] +
(minimn)t + n2m2 pt
aQ To (s.m) and 0Q.0 (a.a)
multiply matrices
get inverse CG
O maxx {n²m² p, mimi, mmmmm)) 1)
where p is the number iterations of CG in each episode, which is O(1/c), where is the error of CG.
The time complexity of SDDPG-BD (SDDPG with block diagonal approximation) is:
nm t max nm² nymi, n'm"
O max (nm² (umm,,mm)) + (mn)t +
nm
(a,e) and PQ (a.)) dw + (max {nîm,, niminm??))
00
multiply matrices
get block dingnol of k2
get tat
O max mimmnm? nm? n n'm"
ot , nimi)
if m. m, m1
The time complexity of SDDPG is:
O (max m nyme, m t) O 0 (m²n²t)
The time complexity FSDDPG (ours) is:
O (max [nīmī, minimn, nm² mno?, o² 0 (max/(m2') m)n?)))
The time complexity DDPG
O (max "nimmi t) O (nm²²)
The time complexity SDDPG-CG is:
O (max (n²m²p. n.mf, m1n1mn) t) = 0m
The time complexity SDDPG-DB is:
2m O max Ri, m,m, nî n m =0 (max {nmo² n2m²
D CONVERGENCE RATE
This section we discuss the convergence rate.
We firstly show the relationship between SDDPG, FSDDPG, and Eq. (2
Corollary 1. If (0* w") is the optimal solution for SDDPG. Then, (0", w²) is also the optimal solutions for Eq. ( as well as FSDDPG.
Proof. We firstly prove the relationship between SDDPG and Eq. The global fixed point satis- fies:
"= arg min Eg-p()) a ( (s) a0 (s, 2
19

---

Under review as a conference paper at ICLR 2022
8" arg max (x) [Q as)
Since the minimum of E Exmp()), a> (8, (s, is zero, this implies Vs, (s, a) (s.
Therefore, putting the above equation into the dynamic of Eq. 2 we have
wº aw aIA(0.u") w' aw..sppp: (QTT (s, a) TTe" (s,a) a)) du Qwr (s,a)) = w
dw
Therefore, w" the fixed point. By further using the fact that
Vs, Q (s. a) QT (s, a) Vs, Q (8, (T)))) (s,
we conclude that w² is the optimal solution for Eq. 22
Also notice that the dynamic of 0 is the same for SDDPG and Eq. Thus, l" is also the optimal solution for Eq. (2).
Now, we prove the relationship between SDDPG and FSDDPG. Since we already knew that [02 (6, w) and k2(0) =
Vs, Q (8,a) = QT (s. a), we can quickly verify that ky k0)
80dw
L w)
Ow
0J((, w)
aJ(0, w)
aJ(0, w)
L d0dw
8 L2 w)
0J w)
Thus,
(0) h2 (0)
00
dw
00
Ow
Ow
Thus, the dynamics of SDDPG and FSDDPG is the same. So, it also optimal solution for FSD- DPG.
This lemma indicates that if we can find solution of SDDPG, it is exactly the solution for the standard Stackelberg learning Eq. (2). well as FSDDPG.
Now, we focus on the convergence rate of FSDDPG and SDDPG:
Theorem 1. When π E C9 H, and Q e C9(S @ A W,R), 9 Z 2. For a fixed point and w such that Js (0-) + Js (0*) is positive-definiz the our method with learning T/2
ve converges locally with rate of O (11-)) v
rate a
26
where v Xmin (S (0")),
1/ = Amax (Js (0)) Js (0*).
Proof. Our framework follows Theorem 5 in (Fiez et al. 2020). We firstly have
- [J- (0*)) (1- (0*)) 27) (8 (0*)) + 7 Amax (Jg, (0*) Js, (0))) (1-v/v)
Taking the Taylor series of (0) around 0" have
I -- (0) = (0) + (I Js (0")) (e 0²) + R1 (0 8*)
where R1 (0 0*) is the remainder term satisfying R₁ (0 8*) O (I (2112) 0 - 0". This implies that there is 8 such that R₁ (0 0*) I
u. 4v 0" whenever |0 - 0*1 < 8. Hence
|| 725(0) (I 72E(0")) 112 - (1II Js (0)) ||2 (i) |10 0" 0|12
(1
1/2 + 44 110 0-112-
Note that v/1 E [0, 1] since e S vb in fact.
Xin (S (0))) < 2max (S (B*)) < Amax (Jz (0 (0'))
Thus, for any 0g (0) |00 0* < <)
20

---

Under review as a conference paper at ICLR 2022
100--011, - <(1=
7/2 110
-0112
26
(11-
T/2
so the local rate of convergence is O
Before we get deeper into the analysis, we define
J(0.0o
k
Kg k0)
a ((
{(O) =
09
8he
BL(
8 L19.0
0² L(P.w)
0-
J(8,
a-J(( 89
L18. (.).w)) 0² L(0.w)
-1
8 J- 8m
Js(
80
09
000
8 L(8 (w)
8 L18.0 (.w)
803w
81
$ 600) JJs (0*) + Js (0*))
which decides the dynamic and the Jacobian of SDDPG.
Now, we show that the convergence rate of SDDPG:
Proposition 2. When æ E (S & O, R) and Q E C9 & A & WRR.,, 2 2. For a fixed point O* and w" such that Js (0*) + Js (0") is positive-definite, the our method with learning rate â La 3
converges locally with a rate of O (11-2) - ) where â = > $ (0*))
T/2
= Amax
Is (8.).
Proof. Following the same steps Theorem
!
we can easily check that
(1 (1- (1- (I (I- (0r) < e/8)1,
and
|r 72 (T (T->2((07)) 11a ((1 3)
1/2
+ à
110
0-112,
46
and
G < b.
Thus, for any 0, E [0] ||0 0* < <8)
|0 81 S (1
T/2
0
0-112
2
((1
à T/2
so the local rate of convergence is O
2
Now, we show that FSDDPG is faster or equivalent to SDDPG for linear actor critic.
We firstly define linear actor sp(s), where (ps) is the embedding, 0 is the learnable parameters.
(ps) where w is the learnable parameters for critie. (0))
The linear critic is Q(s,a)
(p(s)
Theorem 2. For linear actor and critic, if wTA
O, where A is any Positive Semi Definite (PSD) matrix. Then, the convergence rate of FSDDPG (ours) is faster than or equivalent to that of SDDPG.
p(s)0
21

---

Under review as a conference paper at ICLR 2022
Proof.
We show the deriviatives for different terms:
0 L0, w)
(
dw aw Qw (w((,,))
(ou
ou Q (T (Q (s, a -5t (TM((s (
a
a a
Qw (ol
p())
a0dw
80
00 dw
=Ep(s) [
O
(0(5)
( (((()
[0()}) w - - ([c(9)r1)
(0(()0)
+
((0,w))
ppp)
8 Dw?
(ww To (5,a) - (s,
27
=Ep(s)
Q (s,a) Q=)(aa)) ou
2 (s,a) ((())
Ow
p(ee)
Bw
0
2
Q To (s, (5, a))
(0()]
(s(s)
1
= Bp(s)
tuu
a
[2 [[((s)
(((s))
w - (0))
(0()))
) (0(s))) [
(p(s)
(p(s)
Ep(s)
2
(p(s)
a0(0,w)
09
EE(())
00
0 Q (s. = -Bp(s)
[p(()1T
0
w
as(a,w) Sw
= =B((s)
[
[(((s)
[p(s)
(oo Qw (8, a) Ow
((2 Qw (6,
p(e) [( (P(s) ((p(()])))
w) (
((((())
(p(s)
)
(0,0, w) pp(s)
@w
00
Ow
aQ (s,
oQ (s, (s,
(QT 0Q (s, a) )
and k22 w) =B(ss)
2Bp(s)
Ow
Ow
dw
dw
([(())) (p(s)
(x()))) )
p(x))
Now, we put these derivatives into the (o(
((-J(8,w) w) 80
k
((,we) the
a
(())()
89
00
Omn
82 LAB
8 L(9,0))
a00
Ow
A
B
C
D
where
A p((s)
(1 [())[T] w)
(1
O
1)
K " ((()
(ss)
(1oc0 (((()
((2())
))
((s))
+ +E (+)
2
Ro IF (s))
26
(s()
((S) w ( s0(5) 1)
T
0 [[(()
+Ep((s
1-
[(]
(ss)
[ ((())IT] (0)
| ((())
B = Ep(e)
(1())
A:5 A Ep())
Ep(x)
[P())11]]
0
[[x(ss]
(p(()))
(o(s)]
+ ([p(3))
(s)))
w - -(7().a)) ((a()rr))
([s(s) p(s) (s))
((s)) (p(s))
17)]
D Ep(s)
"With a little abuse of notations, we use @ as 0" and w as w" throughout the proof of this theorem.
A ty B means A B is PSD.
22

---

Under review as a conference paper at ICLR 2022
Similarly, for (s) we have:
8
(0.(0,w))
8 L(0.w)
L(6,w)
3-J(0.w)
8
0-,(6
LIL (w)
8 L18,ww
a-J(6.u
(s(
56
86
Ou
Bw
86
Om
8 1100m))
8 L(0,an)
063w
Ow
E
F
=
C
D
where
(c(s) [0()))
E Ep(s)
1T
( IT 1
+
(0) 1
(s)
1T
k5
E p(s)
(8)
(
p(x((s)
(()
(s))
E p(s)
(s)
((s)
+))p(s)
(P)
((s)
15 T (())
((s)1T
A G,
and G = Bp(s)
(0(S)TT
[+())_T]
O
1
R -
[[
[
(((s)
[
(s(s) (())
(((8 [
[p(s)
1') -1
sps)
F p(s)
(P(()
pp(())
((())
[0())0
Ep(s)
[
Notice that, we can easily check that:
B F G.
Thus,
( (
A 0
B
A-E
A
E
B
F 0
1)
(00)
2
0
(G)T
0
Since according to the assumption, we have G to be Positive Semi Definite (PSD). Therefore,
S (00) - $ (0") > 0. According to the property of definite matrices, we have X (5*)) 2 X (0-)).
For Js (0") Js (0"), we have:
AT
CT
A C
B D
ATA CTC BTA+ ABT DTC BTB+D
Js (0)) Js (0") =
B
D
and
ET C'
E F D
E + CTC + E FF+DDD
is (0~) (0')
F" D
C
Therefore,
ETE A EFT ABT FTF-BTB
is (0*)T Js (0*)
Js O Js (0")
ETE A
FT BT
EFT ABT
0
Also notice that ETE - TTA- = (A +G) +G) - = (AT +GT) (4 +G) - ATA
GT + DGG+GG
23

---

Under review as a conference paper at ICLR 2022
Based on the property of PSD, can know that GTG and G ATG are also PSD. Thus, ETE ATA is also PSD.
Moreover, check that
EET ABT GB and
0
0
]]
(0(s) [x(s)0
GB
Ep(e)
P(s)1T
( L7
kg
-
p(s)
((s) [0())0
Ep(+)
[T()
w
1T
k p(a)
> O,
Where a due to the property of PSD.
Thus, we have
Is (0r) Is (0") - Js (0") Js (0") > 0, Therefore, Xmaz
Js (0)) Is (0)) 2 Amar
(0r) Is (8r)
Thus, (1 11-
Xmin ($()
T/2
T/2
2 (S (0*))
2
which
2Amax achieves our desired result.
JJs (0+)* Js (0-))
2Xmax
(Js(0) Js (0-)
Here is an example that helps us show the convergence rate, and we use toy example as an example:
Recall that toy example 1, we have L(0,w) w) = (w:0² + J(0, w) = w02 r
And we can easily calculate that:
aJ(0.w) L(e.w) 8 L(0,w) 8-J(U.m) - + [4(2w + 2)00 |204]
80th Om
3w
Thus, have:
((8.w)
8 LiB.w)
L(8,w)
J(8.00 w/ tho
[[_](8.)) w))
8² L(8 sn)
8(8,8
Js(0): =
Dun
09
890
79
66
08th
thu
8 L(0aa))))
8 L(00m)))
Ow
① (3w 1)
(3w 1)
1 2(w + 02)20
0
aw
2(w02 82) 02)20
403
403
putting 8" = 0, w" = -1 into the equation,
3s(00)
0
0 0
Finally,
0.5 (Js(0')++ + +s(( 0.5
0
0
1)
0
+
0
0
0
0
0
Ts(0))
0
0
0
0
Thus 2 = 0, Amax = 1 the convergence rate is O (11-0)
= 0 (1112))
Similarly, have:
24

---

Under review as a conference paper at ICLR 2022
8J(0, 00
k k:2
1--10-J11 J(0,on) )10,0))
Ow (02)
Bu
Thus,
Js(0)
(B2+2)
(0= (-2+
8 L(0,w)
d00w
Ow
2
18 +X
(+)+ W
2(w0f 8 )2)20
48
putting H" = 0, w² = -1 into the equation,
Js(00)
-1
0
=
0
Finally
-1 0
0.5 (Js(0T)T + Js(0)) =
0
Js(0'))s(('))
0 0
0
0
0
((1
Thus 2 1, Amax =
2 )
o (0.57/3)
E TRAJECTORIES OF SDDPG AND FSDDPG.
This section we show the distances of trajectories of SDDPG and FSDDPG are bounded. We firstly introduce an assumption:
Assumption 1. Q a) a linear function.
This assumption is also adopted in the analysis of temporal difference (Bhandari et al. 2018 In fact, the assumption only serves foundations of the proofs ine (Bhandari al. 2018). and it is possible to extend this assumption into the neural networks form (Cai et al. 2019))
Some mild assumptions are given:
Assumption 2. The following Hessian matrices and the Jacobian matrices are bounded.
< H1,
à To(a s)]l < H2,
|| Dw Qu (8,a)ll < H3, AQ (a.0) < H4
8²
Qn (s, a))
Q (s.a)
|| s Hs.
Bhe
Bu
a Qie (s,a) a))
0 Qie (s,a)T)
S He
a Q (s, a)ll s H
aQ (s.a)
<
Hs
This assumption standard assumption that the norm of derivatives is bounded, similar to (Ghadimi
Wang. 2018 Reddi et al. 2018). We set H = max (H, H2...., Ha). and min H H2... Hz).
For compaetness, we define k :
L.(0.w) and b = (B r.(0,w))
Ow?
We also define Ki [|Q" (s,a) - QF ||.
k K1, and N2 k2 K2 the residual terms. We also define
We also denote the minimum eigenvalue of Taa (s.a) 8Q (a.a)
as Amin
Oie
aQw (s, a) aQy (s, a)"
Amin
E
On
Iw
25

---

Under review as a conference paper at ICLR 2022
Lemma 7.
have ||<||| - 2cH, and ||2l| 2cHs-
Proof. Based on the definition of K1 and K2 and the property of norm, we have:
||a||| || (118)
2 (otr (s. a) (=)(aa)))
(
00T Ow Q (s.a)) ]
a
II
S 2EHl7
8Q (s. |1
||2l|
Rauppar (18)
@Q (((()))
Ow?
2ella
Lemma 8. For the ii.d sampling schemes, we have S
H T where H is positive constant.
Proof. The proof directly follows Sec. 6.1 in (Bhandari et al. 2018
The iidd sampling scheme assumptions are also used in (Nachum et al. 2019 Sutton et al. 2012
Liu et al. 2020; Dalal et al. (0118).
Lemma 9. If c Σ V 11(k2 + k22l < 2z.
Amin-1 We always have || - k2 S 2 (Hg H 10 Hy + H H3)
AMgH
Proof. For ||siding (k2) kill,,, we have:
|| kik2ll
(s, (s) (
30 de Qw (s,
8
0Q (s,a) 8Q% (x.a)
Dw
O Qud (s) ((0Th (s, Q% (s,
0Q (s,a) NQ (0,0) Due
Dw
du Qu (s.a))
NQ (a,a) "Q" (s.a)
Qw (s) QTo (5, (To
#
Om
Oic
500
Tw
Ow +2|l Ohe Qn (s)
Q (s, a)) || Q (s, (s,
Q (s,a)]
00
ow
< 2Hg + 2H, H2 (Hg H + H. H
For [| + k2] k=]
we have:
|| K2) -11 (4) | K2 ke + K2]
S 2eHs + 2eHz2eHs [ + 1-
After some simplification, we have:
lkk + K2 1 < G
G2
(a) follows Lemma where G, 2c G2 1 - 2c 2cH22eH3
Therefore, putting the above inequality together, we have:
|l((A2 + #2 k2) -11 S || [K + wa]
|1 111
G
|
G2
G
(b)
< 2Hgc.
Gz
(b) is based on the assumption
< /
Amin 4H3
which induces
2eHg2eHls Smune.
26

---

Under review as a conference paper at ICLR 2022
Theorem 3. ||s(0) č(0)] is bounded by HH H,
Proof. Using the lemmas mentioned above, we have:
lk((0) [(0)]] =
(ki +N1)
aJ(e.w)
0
(12))
8m
(k) t(1) k1
@J(0,w)
(k2) kz
[1(11 - k)x2) + K22 k22 111
8J(
8u
[I((kz) + (22
k2)kk
1111 aJ(0,
8
HHo + H
Ho H
Where the third inequality is based on Lemma and 9
and the last inequality is based on Lemma
F ALMOST SURELY AVOID SADDLE POINTS.
The proof relies on Theorem 4 in (Fiez et 2020 as well as Corollary 23 in (Mazumdar et al. 2020).
Firstly recall that the definitions of critical points, strict saddle points, as well as fixed points (for our methods) in (Fiez et al., 2020 Chasnov et al.) 2020 Ratliff et al. 2016):
Definition 1. A point is a critical point i(0) = 0. strict saddle point if ((0) 0,and its some eigenvalues are less than 0, while others are larger than O.
Definition 2. A point
Definition 3. A point is a locally asymptotically stable equilibrium if ((0) = 0, and all its eigenval- are larger than O. Lemma 10. [|<(0)) [(02)]] is Lipschitz. continuous.
Proof. Firstly we observe the following inequalities:
9_ (1.001111) Own
Qui Thi (s,a) (s)
sQwi To
(s.a) chei
Dwn
a ll Dwn
(Qui (s, a) Q" (s,
Toz
0Q Te,
(s.a)
Oar
QuQu" " (x.0)
Qui (s, a) - Q (s, a)) +
Je
aQu; (s.a)
0Q"" (s,a)
Bwn
Our
2 Rimax
+ H²
1-y
[J((0.)) 00
k: (0) kz * (0)
aJ(0,a)) dw
00
0
8Q (a.0)
0
Qn (s)
Ow a QT (s,a)
11:00
00
00
30
-1 aQ (s.a)
QT F0
(s,a)
Q (s,a)
H1
Fw
Ow
8Q" (s.a)
9
Que (s,
8 Que (s, a)) (2m Qhe (s,a)T) "}1
80
p (a.0)
a
an (s.a)
QT (8, (
Qne (s, |1
d07
00
00
< Ha + H3H14 + H2gHts
8 110..n) 303
|| - 11:00
(Q The
(s,a)- (oa0-QF(6) Qss,
"0 (s.a) 02 02
Bun
Jo
(s.a)
8Q (a.0)
+ (Q
To, (s, (s,a)) 30
aQ aQ (s.a) own
mi
owe
H7, H3 H
211 R.max HA
27

---

Under review as a conference paper at ICLR 2022
a Fow
(J((0.0)
(0) k0)
(J(0..)
00
Ehe
0
1Q To (s.a)
a
{
a Quo (5, (3,
T
a Br
Qu (s, a) du
Bv
00
Bw
BQ The (s.a)
Qui n
(s, a)
Qud (s,
H1
De
che
8Q (8.0)
0Q2 (s.a)
Qui (8. (
Q (s.a) "} II
Dhe
20
the
00
The
dw
= H4 +
Hg
Therefore, based on the fact that for any continuous function f if sup af || S L, then f(x) is L-lipschitz continuous, we have:
[I=(01 - w (1))ll
0J(0) w1) (01) Kn (0))
(001)
k02) k22 (02) (6(22.02) 7
(.((0
aJ O w22) Dwy
=11
80,
Ehen
00g
OL(0,.w1)
ther
T|| aL(0 OL(0,.00))
8wn
Ounz
||
[J((
hi (0,) (0)) aJ(0
(.(00)))))
1 (02) K:z (02)
(0g. cwar
80,
che
00,
max H1 + H2 H3 + HaH4 + H2 }1101 02ll
I-7 < 2 max { H4 + H.HsH&Hs, H3 + H3H + H, H4 Hs.
max
2 Rumus + H2, Hg + 1- 1-7
110 021l
2Hg Buunx
+ H3: HgggH] + 2M Raaax
1-7 0101 021 S 0 - 0211.
where L = maxx H4 + H4H Ha + Hzll4 + H1 2Hg Rumax
+ H2, H3 H3 + 2Hg Ruaa
1-7
Now, we can finally prove our claim, the framework follows Theorem 4 in (Fiez et al. 2020):
Theorem 4. If aT < 1, our method converges to the strict saddle points of both ((0) and (0 on a set of measure zero.
Proof. We firstly prove that g(0) is invertable, which can be done by contradictions. Consider 0, o 02, and suppose g(01) = g(02) so that 0, - 02 oww(0) oew (2) According to Lemma
10 al ([] (02))l S aL 0 02ll < 100 02ll giving a contradiction. Therefore, it is invertible.
Now, observe that 0g = I (0) and if 0g(
00 is invertible, then according to the inverse function theorem, we have g(0) is local diffeomorphism. Hence, it suffices to show that / - (f)
d0
does not have an eigenvalue of (or 0g) does not have an eigenvalue of 1). Indeed, letting p(A) be the spectral radius of a matrix A, we know that p(A) S ||^|| for any square matrix A and induced operator norm || so that p(a.Js(x)) - ||aJs( (x) < sup (O)) < al < 1,
0e
0
The above implies that all eigenvalues of aJss()) have absolute value less than 1. Since g(0) is injective by the preceding argument, its inverse is well-defined. Also, since g(0) is local diffeo- morphism on Σ, it follows that (() is smooth on θ Σ. Thus, (0) is diffeomorphism.
Consider all critical points of 0, given by ker(w). For each ker(w), let B., where indexes the point, be the open ball derived from the center manifold theorem, and let B = U, Since θ Σ " Lindelöf's 's lemma indicates that every open cover has a countable sub-cover. That is, for countable set of critical points { with u, E ker(w), we have that B = B
Starting from some point Ou θ Σ, if our methods converges strict saddle point,
28

---

Under review as a conference paper at ICLR 2022
then there exists to and index such that gi (:) B Applying the center manifold theorem and using that g(0) _e >. we get that g(0)) E Woo n
Using the fact that (()) is invertible, we can iteratively construct the sequence of sets defined by Wi(u:) = =g- (wee n θ
X
Σ and W*+1(u)) = 9 (
)) Then we have that X Eg = U U ((())) contains all the initial points
Og E (u,),) for all 2 tu. The set Ou in X such that our method converges to strict saddle.
Since u, a strict saddle, dimension of the unstable manifold is strictly less than m m-i.e, dim (Wor) < m. Hence, Wis nx has Lebesgue measure zero.
a.J((0) has an eigenvalue greater than This implies that the co-
Using again that g(0) is diffeomorphism, g- E Ca so that it is locally Lipschitz and locally Lipschitz maps are null set preserving. Hence, Wx(u,) (u,) has measure zero for all by induction so that Oo zero sets.
- U (w,us) ) is measure zero set since it is countable union of measure X Eo
G ENVIRONMENTS SETUP
We list some important statstics about the environments as shown in Table 6 and the detailed dy- namics of each environments can be found in (Duan et al.] 2016 Tunyasuvunakool et al. (020).
Moreover, we also list hyper-parametert
our methods and baselines as shown in Tables and
Here, we would like to discuss more details on why SDDPG-BD is slow comparing with FSDDPG-
BD. Theoretically speaking, since it needs compute the partial of the Hessian 8² (s.a) convergence rate is slow than ours mentioned in Sec. 4.3
its Chel
But the main reason makes SDDPG-BD slow is that the current deep learning framework (e.g., PyTorch (Paszke et al. 2019) is hard to implement diag ((L,())) ( in parallel through GPU. That is, we need to calculate the elements of Hessian matrices on diagonal block matrix. However, the torch.autograd.graa
function does not support calculating the gradient of series of gradients in parallel, meaning that we need to loop them one by one. This makes the training process slow.
The RL platform is based OpenAl's Spinning UP (Achiam 2018). The codes for DDPG and TD3 are from https: httptttsss/ppmmmii http://piinnnnnnggnee.... rguup openai. com/
H EXTRA EXPERIMENTS
We conduct the full version SDDPG on two of the simplest environments MuJoCo: Inverted- DoublePendulum, well InvertedPendulum. Results (Fig. [6) reveal that the SDDPG converges slowly than ours, indicating that the removing the TD-related terms do help improve the convergence rate of Stackelberg learning.
We also show toy example on the best response landscapes. We find that SDDPG can always keep in the best response region.
As shown in Fig. 8, we can find that SDDPG-CG has smaller losses for the critic. meaning that it does keep w the best response area. For DDPG, the losses of the Q values increase dramatically, revealing that it may drifts far form the best response area. For ours, the loss of FSDDPG is between SDDPG-CG and DDPG. This coincide with the results in Fig. which also supports the assumption that the TD-related term pulls the agent to remain in best repsonse area in Sec. 4
29

---

Under review as a conference paper at ICLR 2022
Table The parer-par of SDDPG (ours), SDDPG, and DDPG.
SDDPG (ours)
SDDPG
DDPG
Critic Learning Rate
10
10
10
Actor Learning Rate
10
10
10 3
Target Update Rate
5 10
10
x
Batch Size
100
100
100
Discount Factor
0.99
0.99
0,99
Exploration Policy
A (0,0.1)
N (0, 0.1)
(0,00.1 0.1)
Network Sizes for Actor
16 x 16
16 x 16
16 16
Other Useful Parameters
block diagonal rate =1
Table 5: The hyper-parameters of STD3 (ours), TD3, and SDDPG-CG, FSDDPG-CG.
FSTD3 (ours)
TD3
SDDPG-CG
FSDDPG-CG
Critic Learning Rate
10
10
10
10
Actor Learning Rate
10-3
10"3
10 3
Target Update Rate
5 10-3
5 10-3
5 x 10
5 x 10
Batch Size
100
100
100
100
Discount Factor
0.99
0.99
0.99
0,99
Exploration Policy
(0,
[00 0.1)
NO 0.1)
N/O, 0.1)
Network Sizes for Actor
x
16
x CG iterations=5
16
Other useful Hyper-Parament block diagonal rate =1
CG iterations=5
Table 6: Some statistics about the environments.
Environments
State Dimension
Action Dimension
Ant
125
HalfCheetah
20
Humanoid
102
10
Inverted DoirreedDoubbeeeeduuuu
6
InvertedPendulumm
3
Swimmer
13
Reacher
6
Walker
24
Methoc'
Methods
3002
I50090
530P0 000
50000 CO
FSD095
3:301
300F0
020
3002
800
2000
200
1000
20
40
50
00
20
60
E0
Epaeode
(pance
Inveree@Doubeeendullum
(b) InvertedPendulum.
Figure 6: Ablations on different Hessian approximation approaches and SDDPG approaches.
30

---

Under review as a conference paper at ICLR 2022
24
(sun))
FSDDAG (ound)
point
9 poit
R.C.E.
29
1.5
2.0
0.3
00
0.3
1.0
15
Figure 7: The trajectories of 0 and w for toy example and toy example (The contours are for [0, w*) value).
methods
methods
FSDERG Suung
F500HG (oan)
SCCPO co
S2D19.C0
Locors for lhe cie
70
40
60
80
20
62
60
Epleade
Opaace
(a) Inverte@Doubbeeendulum..
(b) InvertedPendulum.
Figure 8: Ablations on losses of the critics for different methods.
30
(a) Reacher.
(b) Ant.
(c) HalfChectah.
1260-
12000
(d) Reacher.
(e) Ant.
(f) HalfCheetah.
Figure 9: Average running time per episode of different methods. The first row (a-c) the training time per episode of different methods without SDDPG. The second row (d-f) is the training time per episode of all the methods.
31

---

Under review as a conference paper at ICLR 2022
1 SOME IMPORTANT SOURCE CODES
To make our reader know more about our algorithm. We put some important part the source Codes here. One can implement our FSDDPG by just putting the following code to replace the cor- responding functions in /ttpp:://githu:
master/ wtt.cooo/ooo//e. httm://ppaaaiaap.iiggggg////b/ue
spinup/ sppnup/aaggs///aeeee http://aloso//occ/aa/aa//// ddpp.pp
def compute_loss_q
"*"Calculates the loss for the critic""*
0, a, r, o2, data [' cbabs' ] 1. (device), data J. to (deví ce), datal detal'rew rew' |.to (device) datal 'bs2'' to (device), 'done' I (device)
a
Beliman backup for Q function
with corch.no_grad (): #stop-gradient operator for semi-gradient technique.
q_pi_targ re_targ.q(o2 ac_targ.pi (o2))
backup r gamma (1 d) p_pi_arrg
MSE loss against Bellman backup
lcss_q (q packup) ++2 mean
Useful info for logging loss_info dist (Qvals q. () cpp () numpy ())
return loss q loss info
def sacoullatt___ctto__leee (data):
"*"aacculates the Stackelberg gradient for the actor"""
states data lttoosttoooooooooooooo acticns_pred ac.pi (states)
tto (device)
q aac.q acticns_pred) mean mean)
dq autograd. (cuttptss- inputs www.aaattr..aaaarrrrrer.. (),
create_graph-Irue)
aq dthetas
=q,
inputs ac.pi.parameters ()
create_graph-Imnue
vectorize da dw vec torch. zeros (size= [1]) (device)
dg dt_dhhet___ee vec torch. zeros (size= [1]) .to (device)
for dw in ds_:
dw_dw forch.flatten. (dg.dttdttdddddd
dg_dw_vec torch. cat (dq_dw_vee, dw) dim=0)
dd_dw_ved vec dq_dv_vec[1; [t__d__ec[1:].unquuuu unsqueeze (0) #delete the first element
for dt_ath in da dt_etas:
dtheta torch.flatten (dq dtheta)
iq_dtheta_ves torch. cat dtheta vec, dq dtheta) dim=0)
ag dtheta_ vec da dwwettttaeeeee vec vec|l:1| lul.uuueeeezzee (0) #delete the first element
k_ 2storch. transpose (dq ddd__d__eee dim0=0, diml-11)mmmm1))eee did Theta
#deal with the diagonal block dia dq_dw_vec dq__d_wwd dec vec rec rec_k_2_dis dia rorch. (k 2 1c-5)
fcaiculate the gradient for actor dg_dtheta_stack = torch. barch.transpose (de_dtheta_vec, dim0-0, diml=1) \
32

---

Under review as a conference paper at ICLR 2022
forch.transpont 1, dim0=0, diml=1)
rec_K___dia torch. transooee dw_e, dim0=0, dimí=1)
@o_dtheta_stack dg_dtheta_stackl:. [;,]]
for para in enumerate (ac. parp ())
para. grad dg_dtheta_sttaee stack [param_indes) [i] :param_i index [i+11l.
reshape (para. shape)
def update (data)
First run one gradient descent step for Q.
loss_q, lass_info compote_loss_[(dtte loss_q.backwardy c_optimizer. (t
Manaully reset gradient for p in par.meeerrmmterss)>>)> p.requires_grad False
p.requires_grad True
SDDPG Next run one gradient descent step for pi. balculate___actor_los (data) pi_optimizer. step()
33


Reviews:
[{"review_id": "zjuc4JHiEOb", "reviewer": "Reviewer_jvHe", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Strength: This paper seems to provide numerical experiments on Mujoco that are comparable to the state-of-the-art. \n\nWeakness:\n\n1. 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 \n\\begin{align}\nL(\\theta, \\omega) = \\mathbb{E} _ {s \\sim \\rho_{\\theta}, a\\sim \\pi_{\\theta}} \\big  [ ( Q_{\\omega} (s,a) - Q^{\\pi_{\\theta} } (s,a))^2 \\bigr ] ,\n\\end{align}\nwhere $\\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 \n$\\rho$, which is problematic. \n\n2. More importantly, I feel that the issue raised in this work: \n> Most AC methods perform stochastic gradient descent on\nthe actor and critic simultaneously. This can be regarded as performing Gradient Descent Ascent\n(GDA) (Zheng et al., 2021; Wen et al., 2021), which is known to suffer from convergence to limit\ncycles or bad locally optimal solutions (Wang et al., 2019; Jin et al., 2020; Balduzzi et al., 2018).\nMoreover, Yang et al. (2019) show that the critic is biased and may not converge when the actor and\ncritic are updated simultaneously with similar learning rates.\nseems 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.\n\n3. 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. \n\n4. 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?\n\nReferences:\n\n[1] A Finite Time Analysis of Two Time-Scale Actor Critic Methods - Yue Wu, Weitong Zhang, Pan Xu, Quanquan Gu\n\n[2] Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithms - Tengyu Xu, Zhe Wang, Yingbin Liang\n\n[3] A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic - Mingyi Hong, Hoi-To Wai, Zhaoran Wang, Zhuoran Yang\n\n[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_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.", "summary_of_the_review": "a. The Stackelberg view of actor-critic seems not well motivated. \n\nb. There exists a small issue in the implicit gradient involving the sampling distribution. \n\nc. The theoretical arguments depend on strong and ungrounded assumptions and the proofs are hard to follow.\n\n", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "oY1cT2qCDPi", "reviewer": "Reviewer_6tEQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\nI 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.\n\nUnfortunately, 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.\n\nThe 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. \n\nI want to discuss two cases and explain why equation (4) is not correct:\n\n- 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]).\n\n- 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)}]$.\n\nThis 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.\n\nIn 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. \n\nThe 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?\n\nIn the proof of Proposition 1, why is the term $\\nabla_{\\theta^T} Q^{\\pi_{\\theta}}(s,a)$ disappearing?\n\nI 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.\n\n[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.\n\n[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).\n\n[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.\n\n[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.\n", "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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}, {"review_id": "YcSmNWN8n2D", "reviewer": "Reviewer_7evM", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 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.\n\nMinor comments:\n\n- 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.\n\n- In Table 1, how does the scale of $\\epsilon$ compare to $\\frac{1}{nm}$ and $\\frac{1}{o}$ in practice?\n", "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.", "summary_of_the_review": "To my knowledge, the method proposed by this paper is novel and tackles an important problem. I recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "5FHRiBbLINn", "reviewer": "Reviewer_WR2J", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "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.\n\nWeaknesses: 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. \n", "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. ", "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. ", "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": "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: 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