Year: 2021

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.

text: 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.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) has been widely adopted for solving various complicated sequential problems such as games (Mnih et al., 2013) and robotics applications (Kober et al., 2013). In particular, the actor-critic (AC) approach has achieved remarkable performance in many realworld 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., 2021a;b; Wen et al., 2021), which is known to suffer from convergence to limit cycles or bad locally optimal solutions (Wang et al., 2019; Jin et al., 2020; Balduzzi et al., 2018). Moreover, as mentioned in Yang et al. (2019), the GDA training scheme is fragile, which could lead to biased critic and may not converge.
To address these issues, Zheng et al. (2021a) and Wen et al. (2021) reformulate the actor-critic problem as a bilevel optimization problem, and introduce a leader-follower (Stackelberg) training scheme (Fiez et 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 environments 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 al., 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 solving of a linear system. However, to have good performance, a sufficient number of 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 et 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 to compute (We name it as 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 is possible to further reduce the training complexity from O(n3m3) to O(n2m2), where n is the number of layers andm 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.

heading: 2 RELATED WORKS
text: Actor Critic. The AC methods are widely adopted in solving complicated sequential problems (Sutton & 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.e., 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., 2021), and we also show it in our experiments in Sec. 6. Theoretically, most of the stable training methods of GDAs are based on the Two Time Scale Updates (TTSU) scheme (Wu et al., 2020; Dalal et al., 2018). Although the simultaneously update rule for AC can also be proven convergence (Fu et al., 2020), it may not suit all the environments since AC (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).
As the AC training schemes can be also represented as a bi-level optimization process, it is naturally to introduce Stackelberg training scheme to AC as the Stackelberg Actor Critic to stabilize training (Zheng et al., 2021a; Wen et al., 2021). 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., 2021).
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., 2020). 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 et al., 2020), hyper-parameter optimization (Lorraine et 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, 2015; Botev et al., 2017). To address this challenge, the conjugate gradient approximation (Rajeswaran et al., 2019; Mehra, 1969; Ghadimi & Wang, 2018), block diagonal approximation (Martens & Grosse, 2015; Botev et al., 2017), as well as the approximate Newton methods (Martınez, 2000; Xu et al., 2016) 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 computing, 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).

heading: 3 PROBLEM FORMULATION
text: A Markov decision process (MDP) can represented by the tuple 〈S,A,R, P (S|S,A), γ〉, where s ∈ S is the state, a ∈ A is the action, p(s′|s, a) is the transition probability, and r(s, a) ∈ [Rmin, Rmax] is the bounded reward function. ρβ(s) is the discounted state distribution of s conducted by a behavior policy β 1. π : S × A → ∆(A) is the policy, where ∆(A) is the simplex of action set A. Qπ is the state-action value function w.r.t. π: Qπ(s, a) := Eπ[ ∑ k γ
krk|s, a]. Here, we parameterize Q and π with w ∈ Ω and θ ∈ Θ, respectively (Qω and πθ), where Ω and Θ are the parameter spaces. Following (Zheng et al., 2021a), we formulate the actor-critic as a differential Stackelberg game (Fiez et al., 2020): maxθ J(θ, w∗(θ)) (1)
s.t. w∗(θ) = arg min w L(θ, w),
whereJ(θ, w) =Es∼ρ(s),a∼π(·|s)[Qπθw (s, a)], L(θ, w) =Es∼ρ(s),a∼π(·|s) [ (Qπθw (s, a)− ⊥ [Qπθ (s, a)])2 ] , which is the temporal difference (TD) error, and ⊥ (·) is the stop-gradient operator to achieve semi-gradient method (Sutton & Barto, 2018).
1For compactness, we omit the superscript of ρβ(s) as ρ(s) with a little abuse of notations.
Stackelberg learning (or approximate implicit differentiation) (Fiez et al., 2020; Ji et al., 2021) is a 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 (Fujimoto et al., 2018) and SAC (Haarnoja et al., 2018)). Using it on (1), we obtain (Fiez et al., 2020):
θ ← θ + α∂J (θ, w ∗(θ))
∂θ , w ← w − αw
∂L(θ, w)
∂w , (2)
where ∂J(θ,w ∗(θ))
∂θ = ∂J(θ,w) ∂θ − ( ∂2L(θ,w) ∂θ∂w )( ∂2L(θ,w) ∂w2 )−1 ∂J(θ,w) ∂w , and α, αω are learning rates
for the actor and critic, respectively.2 Here,( ∂2L(θ, w)
∂θ∂w
)( ∂2L(θ, w)
∂w2
)−1 ∂J(θ, w)
∂w (3)
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 environments (Wen et al., 2021). 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 × n Hessian matrix in (3) takes O(n3) 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 complicated continuous control environments (Wang et al., 2020). In DPG family, π(a|s) degenerates to π(a|s) = δ(a − πθ(s)), where πθ(s) : S → A is the deterministic policy, and δ(·) is the Dirac-Delta function. L(θ, w) becomes Eρ(s) [ (Qπθw (s, a)− ⊥ [Qπθ (s, πθ (s))])2 ] , where Qπθw (s, a) := Qw(s, a), s.t. a = πθ (s). J(θ, w) becomes Es∼ρ(s)[Qπθw (s, a)].
Notice that the practical DPG based methods update the critic by using L̂(θ, w) = Eρ(s),a∼β [ (Qπθw (s, a)− ⊥ [Qπθ (s, a)])2 ] 3 (Lillicrap et al., 2016; Fujimoto et al., 2018). We follow the critic’s loss, and the modified update scheme becomes:
θ ← θ + α∂J (θ, w ∗(θ))
∂θ , w ← w − αw
∂L̂(θ, w)
∂w , (4)
Comparing with Eq. (2), the update scheme for policy θ maintains the same. The main reason is that ∇θL̂(θ, w) = Eρ(s),a∼β [ ∇θ(Qπθw (s, a)−Qπθ (s, a))2 ] is not well-defined when a 6= π(s), and thus we still use L(θ, 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.

heading: 4 PROPOSED METHOD
text: To alleviate the two challenges in Section 3, we 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). As discussed in (Wang et al., 2019), the indirect gradient term pulls the follower to stay along in the best response 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(θ,w)∂w = 0. It can be shown that ∇wb(w) = ∂ 2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 −1 (Fiez et al., 2020). Hence, we have −α∂ 2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 −1 ∂J(θ,w) ∂w = ∇wb(w) ( −α∂J(θ,w)∂w ) . If θt ≈ b(wt) (θt is closed to the best
2For simplicity of notations, we write ∂w2 := ∂w>∂w and ∂θ∂w := ∂θ>∂w. 3For simplification, we omit ⊥ (·) in ⊥ [Qπθ (s, a)].
response parameters b(wt) ), then θt − ∇wtb(wt) ( α ∂J(θt, wt)
∂wt
) = b(wt)− ∇wtb(wt)(wt+1 −
wt) ≈ b(wt+1), where ≈ is according to the Taylor’s series approximation. It 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 be 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(θ, w)?
Here, we observe that the TD-related term is a good option because it contains the residue term Qπθw (s, a) − Qπθ (s, a) that are closely connected to L(θ, w), which indicates the distance to best response. Thus, removing them could reduce the influence of the best response in indirect gradient to the follower (actor). Another advantage is that since (partial of) the Hessian matrices ∂
2Q πθ w (s,a) ∂w2
and ∂ 2Q πθ w (s,a) ∂w∂θ are hard to compute, reducing them can help improve the computing time.
But, one still needs to compute the inverse matrix, which dominates the time complexity for computing the gradients. To simplify the computation, in Sec. 4.2 we propose to use a block-diagonal approximation to approximate the inverse matrix.
4.1 DERIVATIVES OF ∂ 2L(θ,w) ∂θ∂w AND ∂2L(θ,w) ∂w2
First, we show how to simplify the indirect gradient term in (3) by proposing the following proposition: Proposition 1. For SDDPG and STD3, ∂ 2L(θ,w) ∂θ∂w and ∂2L(θ,w) ∂w2 can be further explicitly expressed as: ∂2L(θ, w)
∂θ∂w = 2Eρ(s)
[( ∂
∂w Qπθw (s, a)
∂w
∂θ
)>( ∂
∂w Qπθw (s, a) ) +(Qπθw (s, a)−Qπθ (s, a)) ( ∂
∂θ> ∂ ∂w Qπθw (s, a)
)] , (5)
∂2L(θ, w)
∂w2 = Eρ(s)
( 2 ∂Q πθ w (s, a)
∂w
∂Q πθ w (s, a) >
∂w + 2 (Qπθw (s, a)−Qπθ (s, a))
∂2Q πθ w (s, a)
∂w2
) . (6)
Proofs can be found in Appendix A. Notice that here we use the chain rules of composite functions Qπθw (s, a), which is different from the original DPG form (Silver et al., 2014). Our form is more suitable for our bi-level optimization settings. Discussion can be found in Remark 1 in Appendix A.
Also note that both (5) and (6) contain the residue termQπθw (s, a)−Qπθ (s, a), which can be ignored if Eρ(s) [ (Qπθw (s, a)−Qπθ (s, a))2 ] is small. Eqs. (5) and (6) then degenerate to:
∂2L(θ, w)
∂θ∂w ≈ 2Eρ(s)
( ∂
∂w Qπθw (s, a)
∂w
∂θ
)>( ∂
∂w Qπθw (s, a)
) := k1(θ, w),
∂2L(θ, w)
∂w2 ≈ Eρ(s)
( 2 ∂Q πθ w (s, a)
∂w
∂Q πθ w (s, a) >
∂w
) := k2(θ, w).
Substituting k1(θ, w), k2(θ, w) into (4), the follower’s approximated update scheme becomes4: θt+1 ← θt + α [ ∂J(θt, wt)
∂θt − k1k−12
∂J(θt, wt)
∂wt
] , (7)
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 ( m3n3T ) to O ( max{m2n2,mno2}T ) to compute the gradients. Details are shown in Sec. 4.3.
Notice that k2(θ, w) is also known as the Gauss Newton matrix (Schraudolph, 2002). Besides fast computing, the Gauss Newton matrix is always Positive Semi-Definite (PSD) which helps better convergence comparing with the Hessian term ∂
2L(θ,w) ∂w2 , which may not guarantee PSD (Martens,
2020). This gives us a numerical analysis perspective why the our approximation works.
We will show that it improves the convergence rate theoretically and empirically in Section 5. 4For simplification, we use k1 and k2 to denote k1(w, θ) and k2(w, θ).
4.2 APPROXIMATED INVERSE k2
Algorithm 1 FSDDPG algorithm Randomly initialize Q(s, a|w) and π(a|s, θ). Initialize target network Q′, π′, and replay buffer R. for episode = 1, M do
Using π to interact with environment to obtain transitions (st, at, rt, st+1). R = R ∪ (st, at, rt, st+1). Sample N transitions from R. Update the critic using ∂L̂(θ,w)∂w . Update the actor policy using the sampled policy gradient: ∂J(θ,w)∂θ − k1k −1 2 ∂J(θ,w) ∂w
Update the target networks. end for
k2(θ, w) and k1(θ, w) do not include any Hessian term, which avoidsO(m3n) for computing partial of the Hessian matrix. However, computing the gradients of the FSDDPG is still expensive since inverting k2 (nm × nm size matrix) usually takes O(m3n3) time. 5
To accelerate the computation of k−12 , we use a block-diagonal approximation scheme:
k2 ' k̂ := k̂1 ⊕ k̂2 ⊕ . . .⊕ k̂d, where k̂i is the ith diagonal block of k2, ⊕ is the direct sum operator, and d ∈ Z+ is the number of diagonal blocks which can be set manually. Define o := d|nm, where | is the integer division operator as the diagonal degree. Also notice that the time complexity of inverting a block diagonal matrix is equal to the sum of inverting each block (Boyd et al., 2004). Thus the time complexity of inverting the matrix k2 is reduced from O ( (nm)3 ) to O ( d(nmd ) 3 ) = O ( mn o (o) 3 ) = O ( mno2 ) . 6 Since inverting k2 dominates the time complexity, when it is reduced, time complexity reduces to O ( max{m2n2,mno2}t ) consequently. More details can be found in Appendix C.

heading: 4.3 TIME COMPLEXITY FOR COMPUTING THE GRADIENT
text: 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 o = 1 (just taking the diagonal) is sufficient to be wellperforming. Also, 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 the term ∂
2L(θ,w) ∂θ∂w still contains (partial) of the Hessian which needs O(n
2m3) to compute, which have been removed in ours. Thus, the time complexity of SDDPG with diagonal block technique (SDDPG-DB) is larger than ours when o is small. Moreover, the mainstream deep learning framework (e.g., PyTorch (Paszke et al., 2019)) does not support calculate diago(∂
2L(θ,w) ∂θ∂w ) in parallel
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−12 ∂J(θt,wt) ∂wt , which solves the linear system k2x = ∂J(θt,wt) ∂wt , where x is the vector to be solved. We name this method as FSDDPG-CG (ours).

heading: 5 THEORETICAL ANALYSIS
text: Before we go deeper into our analysis, we define some useful notations that help the analysis:
ξ(θ) :=
[ ∂−J(θ,w)
∂θ − k1(θ) k −1 2 (θ) ∂−J(θ,w) ∂w
τ ∂L̂(θ,w)∂w
] , is the dynamics of our FSDDPG, τ := αwα is
defined as the time separation.
we also define the Jacobian of the dynamics of our method as:
JS(θ) :=
[ ∂ ∂θ ( ∂−J(θ,w) ∂θ − k1k −1 2 ∂−J(θ,w) ∂w ) ∂ ∂w ( ∂−J(θ,w) ∂θ − k1k −1 2 ∂−J(θ,w) ∂w ) τ ∂
2L̂(θ,w) ∂θ∂w τ ∂2L̂(θ,w) ∂w2
]
and S (θ∗) := 12 ( JS (θ ∗) > + JS (θ ∗) ) , where θ := [θ, w] (θ∗ := [θ∗, w∗] is a fixed point), and T (θ∗) = (JS (θ ∗) > JS (θ ∗)) which helps our analysis.
Now, we prove that our method can converge to a fixed point.
Theorem 1. When π ∈ Cq(S ⊗ Θ,R) and Q ∈ Cq(S ⊗ A ⊗ W,R), q ≥ 2. For a fixed point θ∗ and w∗ such that JS (θ∗) > + JS (θ ∗) is positive-definite, the our method with learning rate α = √ υ ψ converges locally with a rate of O (( 1− υ2ψ )T/2) , where υ = λ2min (S (θ ∗)),
ψ = λmax (T (θ ∗)).
The proof sketch follows Theorem 5 in (Fiez et al., 2020). To compare the convergence rate of FSDDPG (ours) and SDDPG, we firstly define linear actor as π = ϕ(s)θ, where ϕ(s) is the embedding (abstract state), θ is the learnable parameters. The linear critic is Q(s, a) = [ ϕ(s) ϕ(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 O ((
1− υ̂ 2ψ̂
)T/2) (The proof
is similar to Theorem 1 and we provide details in Appendix D), where υ̂ = λ2min ( Ŝ (θ∗) ) , ψ̂ =
λmax
( T̂ (θ∗) ) , and Ŝ(·) as wells as T̂ (·) are defined similar to S(·) and T (·) by replacing k1k−12
with ( ∂2L(θ,w) ∂θ∂w )( ∂2L(θ,w) ∂w2 )−1 in JS(·), respectively.
Theorem 2. For linear actor and critic, if wᵀA [ ϕ(s) ϕ(s)θ ] < 0, 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.
The proof sketch relies on Matrix inequality. The motivation behind this is that we can show that S (θ∗) (resp. ( JS (θ ∗) > JS (θ ∗) ) ) with TD-related term minus S (θ∗) (resp. ( JS (θ ∗) > JS (θ ∗) )
) is always PSD (resp. NSD), which can imply the relationship in eigenvalues of S (θ∗) and( JS (θ ∗) > JS (θ ∗) )
. Notice that since the convergence rate is decided by these eigenvalues (Theorem 1), we can thus obtain the result.
We can use toy example 1 as an 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(1T/2), while FSDDPG is O(0.75T/2). This coincide with our empirical result that ours is faster than SDDPG. Details are in Appendix D.
The following we show some properties of our method (Details are in Appendix F):
We show the connections between Eq. (2), FSDDPG (ours) and SDDPG:
Corollary 1. If 〈θ∗, w∗〉 is the optimal solution for SDDPG. Then, 〈θ∗, w∗〉 is also the optimal solutions for Eq. (2) as well as FSDDPG.
We also show that our method can avoid strict saddle point almost surely under mild assumption in Appendix F.

heading: 6 EXPERIMENTS

heading: 6.1 EXPERIMENTS ON TOY EXAMPLES
text: Environment Setup. 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(θ) = −θ2. Thus, L̂(θ, w) = L(θ, w) = (wθ2 + θ2)2, J(θ, w) = wθ2. The optimal solution of the the first toy example is θ∗ = 0, w∗ = −1. The second example is similar except that we set L̂(θ, w) = L(θ, w) = (wθ + θ2)2, J(θ, w) = wθ. The optimal solution is θ∗ = 0, w∗ = 0. The initial point for the two examples are θ = 1, w = 1 and θ = 2, w = 2, respectively. The distance to optimality is defined as (w − w∗)2 + (θ − θ∗)2. Toy example 2 is harder than Toy example 1 since the best response w.r.t w are w = −1 and w = θ respectively, i.e., w∗ is a constant in toy example 1, while w∗ needs to trace the value of θ in toy example 2.
Baselines. We compare our methods (without block diagonal approximation technique) with for DDPG (Lillicrap 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. 1, for the first example, DDPG and FSDDPG (ours) converge faster than SDDPG, while DDPG is much more unstable than ours and SDDPG since it 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.e., 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 J(θ, w∗) value as 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 a few episodes. DDPG could drives very far from the best response area.

heading: 6.2 EXPERIMENTS ON MUJOCO
text: Environment Setup. We conduct our experiments in standard physical simulator MuJoCo (Todorov et al., 2012), including Ant, HalfCheetah, Humanoid, InvertedDoublePendulum, InvertedPendulum, Swimmer, Reacher, and Walker. The network sizes are 16× 16 for all the methods to make SDDPG and STD3 trainable, larger networks make SDDPG and STD3 hard to train. All the experiments are conducted on a single GeForce RTX 2080 Ti GPU and Intel(R) Xeon(R) CPU E5-2680, and
implemented by PyTorch (Paszke et al., 2019). More details on the environments and the hyperparameters can be found in Appendix G.
Baselines. We uses DDPG (Lillicrap et al., 2016) TD3 (Fujimoto et al., 2018), DDPG-TTSU, SDDPG-CG, STD3-CG (Wen et al., 2021; Zheng et al., 2021a;b) as our baselines:
1) DDPG is a deep learning implementations of DPG.
2) TD3 is the DDPG method with twined delayed critics to avoid high variance.
3) DDPG-TTSU is similar to DDPG except that the critic is updated much more frequently than actor. In our experiments, we set the frequency ratio as 10 : 1.
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-parameters can be found in Appendix G.
Results. As shown in Fig. 3, FSDDPG (ours) reaches the best performance in Humanoid, while FSTD3 (ours) reaches the best performance in 6 out of 8 environments (Ant, HalfCheetah, InvertedDoublePendulum, InvertedPendulum, Swimmer, and Walker). More specifically, comparing FSDDPG with DDPG, and FSTD3 with TD3, FSDDPG outperforms DDPG in 6 out of 8 environments (Ant, HalfCheetah, Humanoid, InvertedDoublePendulum, Swimmer, and Walker); FSTD3 outperforms 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 InvertedDoublePendulum 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, we find that
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, including FSDDPG-CG and SDDPG-BD (SDDPG with the diagonal block approximation) in Fig. 5. Results show that the ours with CG perform better than ours with DB approximation in 2 out of 3 environments. However, as shown in Tab 3, 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. 3, 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 in 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 of degrees o affects the performance. As shown in Fig. 2 and Tab. 2, 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. Finally, we visualize the losses of critics to see whether the leaders are in best response areas, and the results coincide with the results in Fig. 1. Details are in Appendix H.

heading: 7 CONCLUSION
text: 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 Deterministic 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 ours outperform SOTAs in terms of average returns under acceptable training times.

heading: A DERIVATIVES
text: This section we discuss the derivatives.
We firstly introduce a lemma that helps our analysis. Lemma 1. We have ∇θEρ(s) [Qπθw (s, πθ(s))] = Eρ(s) [ ∇θπθ(s) [∇aQπθw (s, a)]a=πθ(s) ] .
Proof. By using the Leibniz integral rule to∇θEρ(s) [Qπθw (s, πθ(s))], we have: ∇θEρ(s) [Qπθw (s, πθ(s))] = Eρ(s) [∇θQπθw (s, πθ(s))] = Eρ(s) [ ∇θπθ(s) [∇aQπθw (s, a)]a=πθ(s) ] ,
which achieves our desired result.
This lemma reveals that our off-policy gradient is different from the gradient derived in (Silver et al., 2014). Remark 1 discusses why they are different, Lemma 2 discusses when these two methods have the same results.
Now, we derive the derivatives using Lemma 1.
Proposition 1. For SDDPG and STD3, ∂ 2L(θ,w) ∂θ∂w and ∂2L(θ,w) ∂w2 can be further explicitly expressed as:
∂2L(θ, w)
∂θ∂w = 2Eρ(s)
[( ∂
∂w Qπθw (s, a)
∂w
∂θ
)>( ∂
∂w Qπθw (s, a) ) + (Qπθw (s, a)−Qπθ (s, a)) ( ∂
∂θ> ∂ ∂w Qπθw (s, a)
)] , (8)
∂2L(θ, w)
∂w2 = Eρ(s)
( 2 ∂Qπθw (s, a)
∂w
∂Qπθw (s, a) >
∂w + 2 (Qπθw (s, a)−Qπθ (s, a))
∂2Qπθw (s, a)
∂w2
) .
(9)
Proof. Based on the basic technique of matrix derivatives and the integral rule of interchanging the integration and differentiation, we have:
∂2L(θ,w) ∂w2 = Eρ(s) [ ∂ ∂w2 ( Q π θ w (s, a)−Qπθ (s, a) )2] = 2Eρ(s) [ ∂
∂w>
[( Q π θ w (s, a)−Qπθ (s, a) ) ∂ ∂wQ π θ w (s, a) ]] = 2Eρ(s) [ ( ∂Q π θ w (s,a) ∂w> ∂Q π θ w (s,a) ∂w + ( Q π θ w (s, a)−Qπθ (s, a) ) ∂2Q π θ w (s,a) ∂w2 )
] (10) and
∂2L(θ,w) ∂θ∂w = ∂ ∂θ> Eρ(s) [ ∂ ∂w ( Q π θ w (s, a)− ⊥ (Qπθ (s, a)) )2] = 2 ∂
∂θ> Eρ(s)
[[ ( Q π θ w (s, a)− ⊥ (Qπθ (s, a)) )> ( ∂ ∂w Q π θ w (s, a) )]] = 2Eρ(s) [ ∂
∂θ>
{( Q π θ w (s, a)− ⊥ (Qπθ (s, a)) )> ( ∂ ∂w Q π θ w (s, a) ) }] = 2Eρ(s)[ ( ∂ ∂θ> Q π θ w (s, a) )> ( ∂ ∂w Q π θ w (s, a)
) + ( Q π θ w (s, a)−Qπθ (s, a) )> ( ∂
∂θ> ∂ ∂w Q
π θ w (s, a) ) ]
= 2Eρ(s)[ ( ∂ ∂θ> Q π θ w (s, a) )( ∂ ∂w Q π θ w (s, a) ) + ( Q π θ w (s, a)− ⊥ (Qπθ (s, a)) )( ∂
∂θ> ∂ ∂w Q
π θ w (s, a) ) ]
= 2Eρ(s)[ ( ∂ ∂w Q π θ w (s, a) ∂w ∂θ )> ( ∂ ∂w Q π θ w (s, a) ) + ( Q π θ w (s, a)− ⊥ (Qπθ (s, a)) )( ∂
∂θ> ∂ ∂w Q
π θ w (s, a) ) ]
The last equation is due to the fact that ∂ ∂θ>
Q π θ w (s, a) = ( ∂ ∂θ Q π θ w (s, a) )> =(
∂ ∂w Q
π θ w (s, a)
∂w ∂θ
)> .
With a little abuse of the notations, for the last equation, we useQπθ (s, a) to replace⊥ (Qπθ (s, a)).
Remark 1. Here, comparing with off-policy DPG, our derived policy gradient is different. In (Silver et al., 2014), under some assumptions (mentioned in Appendix A in (Silver et al., 2014)), the (deterministic) policy gradient is derived from Qπθ (s, a) as
∇θEρ(s)[Qπθ (s, πθ(s))] = Eρ(s)[∇θ ∫ A
[π(a|s)Qπθ (s, a)]da] = Eρ(s)[ ∫ A ∇θπ(a|s)Qπθ (s, a)da+ ∫ A π(a|s)∇θQπθ (s, a)da] = Eρ(s)[∇θπθ(s) [∇aQπθ (s, a)]a=πθ(s) + [∇θQ πθ (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πθ (s, πθ(s)) is approximated by Qπθw (s, πθ(s)) to make the Q value trackable.
For ours, Qπθw (s, a) has been already introduced when the objective is formed. So, by the integral rule of interchanging the integration and differentiation, ∇θEρ(s) [Qπθw (s, πθ(s))] = Eρ(s) [∇θQπθw (s, πθ(s))] = Eρ(s) [ ∇θπθ(s) [∇aQπθw (s, a)]a=πθ(s) ] . Therefore, our gradient is exact 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. (11), in order to use the integral rule of interchanging the integration and differentiation 7, Qπθw (s, a) should be a continuous function w.r.t θ, ∀ a ∈ A. But according to our definition, it is only differentiable w.r.t θ when a = π(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. If Q is always a continuous function w.r.t θ, ∀ a ∈ A, which w.l.o.g. is represented as Q(s, a, θ). The derivatives of Eρ(s) [Q(s, πθ(s), θ)] derived by (Silver et al., 2014) and ours are equal.
Proof. First of all, following the same steps in off-policy DPG, we have:
∇θEρ(s)[Q(s, πθ(s), θ)] = = Eρ(s) [ ∇θ ∫ A π(a|s)Q(s, a, θ)da ] = Eρ(s) [∫ A ∇θπ(a|s)Q(s, a, θ)da+ ∫ A π(a|s)∇θQ(s, a, θ)da
] (a) = Eρ(s) [∫ A ∇θπ(a|s)Q(s, a, θ)da ] + Eρ(s)[∇θQ(s, a, θ)] (b) = Eρ(s) [ ∇θπθ(s) [∇aQ(s, a, θ)]a=πθ(s) +∇θQ(s, a, θ)
] (a) follows the property of Dirac-Delta distribution. (b) follows the the last equation in Eq. (15) in (Silver et al., 2014). The result can also be found in Corollary 3 in (Whiteson, 2020).
For ours, following the chain rule, we have: ∇θEρ(s)[Q(s, πθ(s), θ)] = Eρ(s) [ ∇θQ(s, a, θ) +∇θπθ(s) [∇aQ(s, a, θ)]a=πθ(s) ] .
Then, we can 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(θ, w): because ∂ ∂θEρ(s) [ (Qπθw (s, a)−Qπθ (s, πθ(s)))2 ] may not be well-defined since ∂∂θQ
πθ (s, πθ(s)) does not exist in our settings.
Lemma 3. ∂∂θQ πθ (s, πθ(s)) is not well-defined if r(s, πθ(s)) and p (s′| s, πθ(s)) are nondifferentiable. 7Details can be found in https://math.stackexchange.com/questions/2530213/ when-can-we-interchange-integration-and-differentiation
Proof. We can rewrite the state-action function under the expectation of rewards for different trajectories: Qπθ (st, πθ(st)) = Eτ [ ∞∑ k=t γkrk|τ ] , where τ :=
p(st|st, πθ(st)) ∞∏
k=t+1
πθ(sk)p(sk+1|sk, πθ(sk)) ∈ > is the probability of trajectories.
dτ := dst ∞∏ k=t+1 dakdsk
Then, we have: Qπθ (st, πθ(st)) = Eτ [ ∑∞ k=t γ krk|τ ]
= ∫ T ∑∞ k=1 γ krkdτ
= ∫ T p(st|st, πθ(st)) ∏∞ k=t+1 πθ(sk)p(sk+1|sk, πθ(sk)) ( γtrt(s, πθ(st)) + ∑∞ k=t+1 γ krk ) dτ
= ∫ T p(st|st, πθ(st)) ∏∞ k=t+1 πθ(ak|sk)p(sk+1|sk, a) ( γtrt(s, πθ(st)) + ∑∞ k=t+1 γ krk ) dτ
= ∫ T p(st|st, πθ(st)) ∏∞ k=t+1 πθ(ak|sk)p(sk+1|sk, a) ( γtrt(s, πθ(st)) + ∑∞ k=t+1 γ krk ) dτ
(a) = ∫ T \A p(st+1|st, πθ(st)) ∏∞ k=t+2 πθ(ak|sk)p(sk+1|sk, ak)(∫
A πθ(at+1|st+1)p(st+2|st+1, at+1) ( γtrt(s, πθ(st)) + ∑∞ k=t+1 γ krk ) dat+1 ) d(τ\at+1)
(b) = ∫ T \A p(st+1|st, πθ(st)) (∏∞ k=t+2 πθ(ak|sk)p(sk+1|sk, ak) ) (p(st+2|st+1, πθ(st+1))) (∑t+1 k=t γ krk(s, πθ(st)) + ∑∞ k=t+1 γ krk ) dτ\at+1 = ∫ T \(∪∞k=tA) ∏∞ k=t p(sk+1|sk, πθ(sk) ) (∑∞ k=t γ krk(s, πθ(st)) ) dτ\ (∪∞k=tat+1)
(a) is based on the Fubini’s theorem.
(b) is due to the property of Dirac-delta function. d(τ\at+1) means dstdst+1( ∞∏
k=t+2
dakdsk).
T \A means removing the set A from T . According to the assumptions, r(s, πθ(s)) and p (s′| s, πθ(s))are non-differentiable w.r.t θ.
Since Qπθ (st, πθ(st)) does not contain any differentiable elements, ∂∂θQ πθ (s, πθ(s)) are not welldefined.
This Lemma reveals that the ∂ ∂θ> Qπθ (s, πθ(s)) 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 is another reason that we need to use the stop-gradient operator.

heading: B BLOCK DIAGONAL MATRICES
text: We firstly define E := k2diago(k2)−1 − I We now show a technical lemma here:
Lemma 4. (Henderson & Searle, 1981) For two non-degenerate matrices A and B, we always have:
(A+B)−1 = A−1 −A−1B(A+B)−1,
Now we show that larger o does not mean that the distance will be smaller: Lemma 5. D(k2, diago(k2)) is not always monotonic decreased w.r.t. o:
Proof. This can be done by finding a counter-example:
For k2 = 1 1 1 21 1 1 31 1 9 4 5 5 6 1 , we have D (k2, diag1(k2)) = 11.0, D (k2, diag2(k2)) = 8.2, D ( k2, diag 3(k2) ) = 10.7.
But we can always find a sub-series that satisfies the following Lemma: Lemma 6. When o can be represented as lx, where x, l ∈ Z+ , D ( k2, diag lx(k2) )
is a strict decreased series with the increasing of l. Proof. ||k2 − diaglx(k2)||F = √∑ i,j∈G |kij | , G = {i, j|i 6= lxj + k, k = 1, 2 . . . , lx},
||k2 − diag(l+1)x(k2)||F = √ ∑ i,j∈G1 |kij | , G1 = {i, j|i 6= (l + 1)xj + k, k = 1, 2 . . . , (l + 1)x}
Since G ⊂ G1 , we have:√∑ i,j∈G |kij | > √ ∑ i,j∈G1 |kij |
||k2 − diaglx(k2)||F − ||k2 − diag(l+1)x(k2)||F < 0. Since||k2 − diagmn(k2)||F = 0. So D ( k2, diag lx(k2) ) is 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 1 to guarantee that the distance is D ( k2, diag lx(k2) ) is a strict decreased (e.g., 2, 4, 6, . . . ).

heading: C TIME COMPLEXITY FOR COMPUTING THE GRADIENT
text: We assume that critic has n layers with m neurons, while actor has n1 layers with m1. We also define t as the training episodes.
We define OPM as the time complexity of multiplication two real numbers, OPG as the time complexity of calculating the gradient of one element w.r.t other, and OPA as the time complexity of adding two real numbers.
Now we analyze the one step time complexity of different terms.
1) The time complexity of ∂∂w Q π θ w (s, a) is
OPG
( m+ ∑n+1 i=2 m 2 ) +OPM (∑ n+1 i =1m 2 ) = OPG ( m+ nm2 ) +OPM (n+ 1)m 2.
m+ ∑n+1 i =2m 2 is because the the dimension of gradient between the output layer and the last layer
is m, and thus the dimension of gradient is m2 for each intermediate layer. (∑n+1 i =1m 2 ) is because each layer requires m2 times multiplication to form the chain rules. 8
8Recall the time complexity of multiplication two matrices with dimensions m,n and n, p is mnp.
The time complexity of ∂π∂θ is ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) , which follows the same analysis of ∂∂w Q π θ w (s, a). Combining the above analysis, the time complexity of ∂J(θ,w)∂w is = s ( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ) , which follows the same analysis of ∂∂w Q π θ w (s, a).
2) The time complexity of ∂J(θ,w)∂θ is( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+ (OPG +OPM )m + ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) +OPM (mn+m1n1)
, which is a combination of the time of calculating ∂∂w Q π θ w (s, a) (require ( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
times), ∂w∂π (require (OPG + OPM )m times), and ∂π∂θ (require ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) times) (since ∂J(θ,w) ∂θ ≈ ∑ ∂ ∂w Q π θ w (s, a) ∂w ∂π ∂π ∂θ ).
3) The time complexity of E∂Q π θ w (s,a) ∂θ is exactly the same as ∂J(θ,w) ∂θ .
4) For the time complexity of ∂ 2 ∂w2 Q π θ w (s, a) is
OPG ( m+ nm2 ) +OPM (n+ 1)m 2 + nmOPG ( m+ ∑ n+1 i =2m 2 ) + nmOPM (∑ n+1 i =1m 2 )
= OPG ( m+ nm2 ) +OPM (n+ 1)m 2 + OPG ( nm2 + n2m3 ) +OPM n(n+ 1)m 3,
which is based on the fact that the Hessian can be decomposed to ∂∂w [ ∂ ∂w Q
π θ w (s, a)].
5) For ∂ ∂θ> ∂ ∂w Q
π θ w (s, a),
n1m1 ( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+ n1m1(OPG +OPM )m +n1m1 ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) +OPM (mn+m1n1)
6) The time complexity of (
∂ ∂w Q
π θ w (s, a)
∂w ∂θ )> ( ∂ ∂w Q π θ w (s, a) ) is the summation of
∂ ∂w Q
π θ w (s, a)
∂w ∂θ and ∂ ∂w Q π θ w (s, a), and their multiplication.(
OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+ (OPG +OPM )m + ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) +OPM (mn+m1n1)
+ ( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+OPM (mnm1n1) = O ( max { nm2,mnm1n1, n1m 2 1 }) 7) For ∂Q π θ w (s, a)
∂w
∂Q π θ w (s, a)>
∂w( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ) +OPM ( m2n2 ) Combining them together, for
Eρ(s) [( ∂ ∂w Q π θ w (s, a) ∂w ∂θ )> ( ∂ ∂w Q π θ w (s, a) ) + ( Q π θ w (s, a)−Qπθ (s, a) ) ∂ ∂θ> ∂ ∂w Q π θ w (s, a) ] ,
the time complexity is:
( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+ (OPG +OPM )m + ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) +OPM (mn+m1n1)
+ ( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+OPM (mnm1n1) +n1m1 ( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 )
+ n1m1(OPG +OPM )m +n1m1 ( OPG ( m1 + n1m 2 1 ) +OPM (n1 + 1)m 2 1 ) +OPM (mn+m1n1)
= O ( max { n21m 3 1, n1m1nm 2 })
For Eρ(s) [( 2∂Q π θ w (s,a) ∂w ∂Q π θ w (s,a) > ∂w + 2 ( Q π θ w (s, a)−Qπ(s, a) ) ∂2Q π θ w (s,a) ∂w2 ) ] , the time complexity is:
( OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ) +OPM ( m2n2 )︸ ︷︷ ︸ calculate k2
+OPG ( m+ nm2 ) +OPM (n+ 1)m 2 + OPG ( nm2 + n2m3 ) +OPM n(n+ 1)m
3︸ ︷︷ ︸ calculate κ2 ,
= O ( n2m3 ) For inverse k2 + κ2, the time complexity is:
[ OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ] + s [ OPMn 2 1m 2 1 ]︸ ︷︷ ︸ calculate k2
+ [ OPG ( m+ nm2 ) +OPM (n+ 1)m 2 + OPG ( m2 + nm3 ) +OPM (n+ 1)m 3 ]︸ ︷︷ ︸
calculate κ2 + O ( n3m3 )︸ ︷︷ ︸ inverse matrix
= O ( n3m3 ) For inverting diago(k2), the time complexity is:
[ OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ] + s [ OPMn 2 1m 2 1 ] +OPGm
2︸ ︷︷ ︸ calculate part of k2 +O
( o n3m3
o3 t ) ︸ ︷︷ ︸ inverse matrix + O ( o (nm o )2 t ) ︸ ︷︷ ︸ extract the diago(k2)
= O ( max { nm2, n1m 2 1, n3m3
o2
} t )
For inverting diago(k2 + κ2)[ OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ] + s [ OPMn 2 1m 2 1 ] +OPGm
2︸ ︷︷ ︸ calculate part of k2 +
+
[ OPG ( m+ nm2 ) +OPM (n+ 1)m 2 ] + [ OPMn 2 1m 2 1 ] +OPGm︸ ︷︷ ︸
calculate part of κ2
+O ( k n3m3
k3 t ) ︸ ︷︷ ︸ inverse matrix + O ( k (nm k )2 t ) ︸ ︷︷ ︸ extract the diago(k2)
= O ( max { nm2, n1m 2 1, n3m3
k2
} t )
Therefore, the time complexity of calculating the actor for SDDPG in Eq. (4) is
O max{nm2, n1m21} t︸ ︷︷ ︸ ∂Q
π θ w (s,a) ∂θ and ∂Q π θ w (s,a) ∂w
+ ( m1n1m 2n2 ) t+ (m1n1mn)t︸ ︷︷ ︸
multiply matrices
+n3m3t+ n1m 2 1t︸ ︷︷ ︸
get k1+κ1  = O ( max { n3m3, n1m 2 1,m1n1m 2n2 } t )
The complexity of FSDDPG (ours) is
O  max{nm2, n1m21} t︸ ︷︷ ︸ ∂Q
π θ w (s,a) ∂θ and ∂Q π θ w (s,a) ∂w
+m2n2t+ ( om2n2 ) t︸ ︷︷ ︸
multiply matrices
+ max { nm2, n1m 2 1, o 3 } t  = O ( max { n21m 2 1,m1n1mn, nm 2,m2n2o, o3 } t )
The time complexity of DPG is:
O max (nm2t, n1m21t)︸ ︷︷ ︸ ∂Q
π θ w (s,a) ∂θ . The time complexity of SDDPG-CG is:
O  max{nm2, n1m21} t︸ ︷︷ ︸ ∂Q
π θ w (s,a) ∂θ and ∂Q π θ w (s,a) ∂w
+ (m1n1mn) t︸ ︷︷ ︸ multiply matrices + n2m2pt︸ ︷︷ ︸ get inverse CG  = O ( max { n2m2p, n1m 2 1,m1n1mn } t )
where p is the number of iterations of CG in each episode, which is O(1/ ), where is the error of CG.
The time complexity of SDDPG-BD (SDDPG with block diagonal approximation) is:
O( max { nm2, n1m 2 1 } t︸ ︷︷ ︸
∂Q π θ w (s,a) ∂θ and ∂Q π θ w (s,a) ∂w
+ (mn)t+ ( k (nm k )2 × nm ) t︸ ︷︷ ︸
multiply matrices
+ max { nm2, n1m 2 1, n3m3
k2 } t︸ ︷︷ ︸
get block diagnal of k2+κ2 +O ( max { n21m 3 1, n1m1nm 2 })︸ ︷︷ ︸
get k1+κ1
) =
O ( max { n1m1nm 2, nm2, n 3m3 o2 , n 2 1m 3 1 } t )
if m1 = m, n1 = n:
The time complexity of SDDPG is: O ( max { n3m3, n1m 2 1,m1n1m 2n2 } t ) = O ( m3n3t ) The time complexity of FSDDPG (ours) is:
O ( max { n21m 2 1,m1n1mn, nm 2,mno2, o3 } t ) = O ( max{m2n2,mno2}t ) The time complexity of DDPG is:
O ( max { n21m 2 1, nm 2 } t ) = O ( nm2t ) The time complexity of SDDPG-CG is:
O ( max { n2m2p, n1m 2 1,m1n1mn } t ) = O ( m2n2 1 t ) The time complexity of SDDPG-DB is:
O ( max { n3m3
k2 , n1m 2 1, n 2 1m 3 1, n1m1nm
2 } t ) = O ( max { nmo2, n2m3 } t )

heading: D CONVERGENCE RATE
text: This section we discuss the convergence rate.
We firstly show the relationship between SDDPG, FSDDPG, and Eq. (2):
Corollary 1. If 〈θ∗, w∗〉 is the optimal solution for SDDPG. Then, 〈θ∗, w∗〉 is also the optimal solutions for Eq. (2) as well as FSDDPG.
Proof. We firstly prove the relationship between SDDPG and Eq. (2). The global fixed point satisfies:
w∗ = arg minEs∼ρ(·), a∼β [(Qπθw (s, a)−Qπθ (s, a)) 2 ]
θ∗ = arg maxEs∼ρ(·) [Qπθw (s, a)]
Since the minimum of Es∼ρ(·), a∼β [(Qπθw (s, a)−Qπθ (s, a)) 2 ] is zero,
this implies ∀s,Qπθw (s, a) = Qπθ (s, a). Therefore, putting the above equation into the dynamic of Eq. (2), we have
w∗ − αw ∂L(θ,w ∗) ∂w = w ∗ − αwEs∼ρ(·)[2 (Qπθ∗w (s, a)−Qπθ∗ (s, a)) ∂∂wQ πθ∗ w∗ (s, a)] = w ∗ Therefore, w∗ is the fixed point. By further using the fact that
∀s,Qπθw (s, a) = Qπθ (s, a)→ ∀s,Qπθw (s, πθ(s)) = Qπθ (s, πθ(s)) , we conclude that w∗ is the optimal solution for Eq. (2).
Also notice that the dynamic of θ is the same for SDDPG and Eq. (2). Thus, θ∗ is also the optimal solution for Eq. (2).
Now, we prove the relationship between SDDPG and FSDDPG. Since we already knew that ∀s,Qπθw (s, a) = Qπθ (s, a), we can quickly verify that k1(θ) = ( ∂2L(θ, w)
∂θ∂w ) and k2(θ) =(
∂2L(θ, w)
∂w2
) .
Thus, ∂J(θ, w)
∂θ − k1(θ) k−12 (θ)
∂J(θ, w)
∂w =
∂J(θ, w) ∂θ − ∂
2L(θ, w) ∂θ∂w ( ∂2L(θ, w) ∂w2 )−1 ∂J(θ, w) ∂w .
Thus, the dynamics of SDDPG and FSDDPG is the same. So, it is also optimal solution for FSDDPG.
This lemma indicates that if we can find a solution of SDDPG, it is exactly the solution for the standard Stackelberg learning Eq. (2), as well as FSDDPG.
Now, we focus on the convergence rate of FSDDPG and SDDPG: Theorem 1. When π ∈ Cq(S ⊗ Θ,R) and Q ∈ Cq(S ⊗ A ⊗ W,R), q ≥ 2. For a fixed point θ∗ and w∗ such that JS (θ∗) > + JS (θ ∗) is positive-definite, the our method with learning rate α = √ υ ψ converges locally with a rate of O (( 1− υ2ψ )T/2) , where υ = λ2min (S (θ ∗)),
ψ = λmax ( JS (θ ∗) > JS (θ ∗) ) .
Proof. Our framework follows Theorem 5 in (Fiez et al., 2020). We firstly have
(I − γ1JS (θ∗))> (I − γ1JS (θ∗)) ≤ ( 1− 2γ1λmin (S (θ∗)) + γ21λmax ( J>Sτ (θ ∗) JSτ (θ ∗) )) I ≤ (1− υ/ψ)I
Taking the Taylor series of I − γ2ξ(θ) around θ∗, we have I − γ2ξ(θ) = (I − γ1ξ(θ)) + (I − γ1JS (θ∗)) (θ − θ∗) +R1 (θ − θ∗) where R1 (θ − θ∗) is the remainder term satisfying R1 (θ − θ∗) = O (||θ − θ∗||2) as θ → θ∗. This implies that there is δ such that R1 (θ − θ∗) ≤ υ4ψ ||θ − θ ∗|| whenever ||θ − θ∗|| ≤ δ. Hence
||I − γ2ξ(θ)− (I − γ2ξ(θ∗)) ||2 ≤ ( ||I − γ1JS (θ∗) ||2 + υ4ψ ) ||θ − θ∗||2
≤ (( 1− υψ )1/2 + υ4ψ ) ||θ − θ∗||2.
Note that υ/ψ ∈ [0, 1] since υ ≤ ψ, in fact,
υ = λ2min (S (θ ∗)) ≤ λ2max (S (θ∗)) ≤ λmax ( J>S (θ ∗) JS (θ ∗) ) = ψ
Thus, for any θ0 ∈ {θ| ||θ − θ∗|| < δ}
‖θT − θ∗‖2 ≤ ( 1− υ2ψ )T/2 ‖θ0 − θ∗‖2
so the local rate of convergence is O (( 1− υ
2ψ
)T/2) .
Before we get deeper into the analysis, we define
ξ̂(θ) :=
[ ∂−J(θ,w)
∂θ − k1(θ) k −1 2 (θ) ∂−J(θ,w) ∂w
τ ∂L̂(θ,w)∂w
]
ĴS(θ) :=
 ∂∂θ ( ∂−J(θ,w) ∂θ − ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 −1 ∂−J(θ,w) ∂w ) ∂ ∂w ( ∂−J(θ,w) ∂θ − ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 −1 ∂−J(θ,w) ∂w ) τ ∂
2L̂(θ,w) ∂θ∂w τ ∂2L̂(θ,w) ∂w2  Ŝ (θ∗) := ( Ĵ>S (θ ∗) + ĴS (θ ∗) )
which decides the dynamic and the Jacobian of SDDPG.
Now, we show that the convergence rate of SDDPG:
Proposition 2. When π ∈ Cq(S ⊗ Θ,R) and Q ∈ Cq(S ⊗ A ⊗ W,R), q ≥ 2. For a fixed point θ∗ and w∗ such that ĴS (θ∗) > + ĴS (θ ∗) is positive-definite, the our method with learning rate α̂ = √ υ̂ ψ̂ converges locally with a rate of O (( 1− υ̂ 2ψ̂ )T/2) , where υ̂ = λ2min ( Ŝ (θ∗) ) ,
ψ̂ = λmax ( ĴS (θ ∗) > ĴS (θ ∗) ) .
Proof. Following the same steps in Theorem 1, we can easily check that( I − γ1ĴS (θ∗) )> ( I − γ1ĴS (θ∗) ) ≤ (1− υ̂/ψ̂)I, and
||I − γ2ξ̂(θ)− ( I − γ2ξ̂(θ∗) ) ||2 ≤ (( 1− υ̂
ψ̂
)1/2 + υ̂
4ψ̂
) ||θ − θ∗||2,
and
υ̂ ≤ ψ̂. Thus, for any θ0 ∈ {θ| ||θ − θ∗|| < δ}
‖θT − θ∗‖2 ≤ ( 1− υ̂ 2ψ̂ )T/2 ‖θ0 − θ∗‖2
so the local rate of convergence is O (( 1− υ̂
2ψ̂
)T/2) .
Now, we show that FSDDPG is faster or equivalent to SDDPG for linear actor critic.
We firstly define linear actor as π = ϕ(s)θ, where ϕ(s) is the embedding, θ is the learnable parameters.
The linear critic is Q(s, a) = [ ϕ(s) ϕ(s)θ ] w , where w is the learnable parameters for critic.
Theorem 2. For linear actor and critic, if wᵀA [ ϕ(s) ϕ(s)θ ] < 0, 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.
Proof. 9 10 We show the deriviatives for different terms:
∂2L(θ, w)
∂θ∂w = 2Eρ(s)
[( ∂
∂w Qπθw (s, a)
∂w
∂θ
)>( ∂
∂w Qπθw (s, a)
) + (Qπθw (s, a)−Qπθ (s, a)) ( ∂
∂θ> ∂ ∂w Qπθw (s, a)
)] ,
= Eρ(s)
[[ 0
ϕ(s)1ᵀ ]> [ ϕ(s) ϕ(s)θ ] + ([ ϕ(s) ϕ(s)θ ] w −Qπθ (s, a) )([ 0 ϕ(s)1ᵀ ])] .
,
∂2L(θ,w) ∂w2 = Eρ(s) [ ∂ ∂w2 ( Q π θ w (s, a)−Qπθ (s, a) )2] = Eρ(s) [ ∂ ∂w [ 2 ( Q π θ w (s, a)−Qπθ (s, a) ) ∂ ∂wQ π θ w (s, a) ]] ,
= Eρ(s) [ ∂ ∂w [ 2 ( Q π θ w (s, a)−Qπθ (s, a) )[ ϕ(s) ϕ(s)θ ]]] = Eρ(s) [ ∂ ∂w [ 2 ([ ϕ(s) ϕ(s)θ ] w −Qπθ (s, a) )[ ϕ(s) ϕ(s)θ ]]] ,
= Eρ(s)
[ 2 ([ ϕ(s) ϕ(s)θ ] [ ϕ(s) ϕ(s)θ ]>)] .
,
∂J(θ,w) ∂θ = Eρ(s) [ ∂ ∂θQ π θ w (s, a) ] = Eρ(s) [[ 0
ϕ(s)1ᵀ
] w ] , ∂J(θ,w)∂w = Eρ(s) [[ ϕ(s) ϕ(s)θ ]] . ,
k1(θ, w) = Eρ(s)
[( ∂
∂w Qπθw (s, a)
∂w
∂θ
)>( ∂
∂w Qπθw (s, a)
)] = 2Eρ(s) [([ 0
ϕ(s)
] w )>([ ϕ(s) ϕ(s)θ ])] .
, and k2(θ, w) = Eρ(s) ( 2 ∂Qπθw (s, a)
∂w
∂Qπθw (s, a) >
∂w
) = 2Eρ(s) ( ∂Qπθw (s, a)
∂w
∂Qπθw (s, a) >
∂w
) =
2Eρ(s) ([ ϕ(s) ϕ(s)θ ] [ ϕ(s) ϕ(s)θ ]>) .
Now, we put these derivatives into the JS(θ):
JS(θ) :=
[ ∂ ∂θ ( ∂−J(θ,w) ∂θ − k1k −1 2 ∂−J(θ,w) ∂w ) ∂ ∂w ( ∂−J(θ,w) ∂θ − k1k −1 2 ∂−J(θ,w) ∂w ) ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 ]
= [ A B C D ] .
where
A = Eρ(s)
[([ 0
ϕ(s)1ᵀ
] w )>([ 0
ϕ(s)1ᵀ
])] k−12 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] +Eρ(s) [([ 0
ϕ(s)1ᵀ
] w )>([ ϕ(s) ϕ(s)θ ])] ∂ ∂θk −1 2 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] ,
+Eρ(s)
[([ 0
ϕ(s)1ᵀ
] w )>([ ϕ(s) ϕ(s)θ ])] k−12 Eρ(s) [[ 0 ϕ(s)1ᵀ ]]
B = Eρ(s) [([
ϕ(s) ϕ(s)θ
] [ 0
ϕ(s)1ᵀ
])] k−12 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] ,
C = Eρ(s)
([ 0
ϕ(s)1ᵀ ]> [ ϕ(s) ϕ(s)θ ] + ([ ϕ(s) ϕ(s)θ ] w −Qπθ (s, a) )([ 0 ϕ(s)1ᵀ ]) ) ,
D = Eρ(s)
[ 2 ([ ϕ(s) ϕ(s)θ ] [ ϕ(s) ϕ(s)θ ]>)] .
9With a little abuse of notations, we use θ as θ∗ and w as w∗ throughout the proof of this theorem. 10A < B means A−B is PSD.
Similarly, for ĴS(θ), we have:
ĴS(θ) :=
 ∂∂θ ( ∂−J(θ,w) ∂θ − ∂2L(θ,w) ∂w∂θ ∂2L(θ,w) ∂w2 −1 ∂−J(θ,w) ∂w ) ∂ ∂w ( ∂−J(θ,w) ∂θ − ∂2L(θ,w) ∂w∂θ ∂2L(θ,w) ∂w2 −1 ∂−J(θ,w) ∂w ) ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2  = [ E F C D
] where
E = Eρ(s) [([
0 ϕ(s)1ᵀ
] w )ᵀ [ 0
ϕ(s)1ᵀ
] + [ 0
ϕ(s)1ᵀ
] w [ 0
ϕ(s)1ᵀ
]] k−12 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] ,
+Eρ(s) [([
0 ϕ(s)1ᵀ
] w )ᵀ [ ϕ(s) ϕ(s)θ ]] ∂ ∂θk −1 2 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] ,
+Eρ(s) [([
0 ϕ(s)1ᵀ
] w )ᵀ [ ϕ(s) ϕ(s)θ ]] k−12 Eρ(s) [[ 0 ϕ(s)1ᵀ ]] = A+G,
and G = Eρ(s) [ wᵀ [
0 ϕ(s)1ᵀ
]ᵀ [ 0
ϕ(s)1ᵀ
]] k−12 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] ,
F = Eρ(s) [[
ϕ(s) ϕ(s)θ
] [ 0
ϕ(s)1ᵀ
]] Eρ(s) ([ ϕ(s) ϕ(s)θ ] [ ϕ(s) ϕ(s)θ ]>)−1 Eρ(s) [[ ϕ(s) ϕ(s)θ ]] ,
Notice that, we can easily check that:
B = F = G.
Thus,
S (θ∗) − Ŝ (θ∗) = 12
([ A− E B − F
0 0
]> + [ A− E B − F
0 0
]) =
1 2
[ G + (G)> 0
0 0 ] Since according to the assumption, we have G to be Positive Semi Definite (PSD). Therefore,
S (θ∗)− Ŝ (θ∗) < 0. According to the property of definite matrices, we have
λ2min (S (θ ∗)) ≥ λ2min
( Ŝ (θ∗) ) .
For JS (θ∗) > JS (θ ∗) , we have:
JS (θ ∗) > JS (θ ∗) =
[ Aᵀ Cᵀ
Bᵀ Dᵀ ] [ A B C D ] = [ AᵀA+ CᵀC BᵀA+ CᵀD ABᵀ +DᵀC BᵀB +DᵀD ] ,
and
ĴS (θ ∗) > ĴS (θ ∗) =
[ Eᵀ C ᵀ
F ᵀ D ᵀ ] [ E F C D ] = [ EᵀE + CᵀC F ᵀE + CᵀD EF ᵀ +D ᵀ C F>F +DᵀD ] ,
Therefore,
ĴS (θ ∗) > ĴS (θ ∗) − JS (θ∗)> JS (θ∗) = [ EᵀE −AᵀA F ᵀE −BᵀA EF ᵀ −ABᵀ F ᵀF −BᵀB ] =[
EᵀE −AᵀA F ᵀE −BᵀA EF ᵀ −ABᵀ 0
] ,
Also notice that EᵀE − AᵀA = (A +G)ᵀ(A +G)− AᵀA = (Aᵀ +Gᵀ) (A +G) − AᵀA = GᵀA+ AᵀG+GᵀG,
Based on the property of PSD, we can know that GᵀG and GᵀA + AᵀG are also PSD. Thus, EᵀE −AᵀA is also PSD. Moreover, we can check that

heading: EF ᵀ −ABᵀ = GBᵀ, and
text: GBT = ( Eρ(s) [ [ 0
ϕ(s)1ᵀ
] w [ 0
ϕ(s)1ᵀ
]] k−12 Eρ(s) [[ ϕ(s) ϕ(s)θ ]]) ( Eρ(s) [ [ 0
ϕ(s)1ᵀ
] w [ 0
ϕ(s)1ᵀ
]] k−12 Eρ(s) [[ ϕ(s) ϕ(s)θ ]])> a < 0,
Where a is due to the property of PSD .
Thus, we have
ĴS (θ ∗) > ĴS (θ ∗) − JS (θ∗)> JS (θ∗) < 0, Therefore, λmax ( ĴS (θ ∗) > ĴS (θ ∗) ) ≥ λmax ( JS (θ ∗) > JS (θ ∗) ) .
Thus, 1− λ2min ( Ŝ (θ∗) ) 2λmax ( ĴS (θ∗) > ĴS (θ∗) ) T/2 ≥ 1− λ2min (S (θ∗)) 2λmax ( JS (θ∗) > JS (θ∗) ) T/2 , which
achieves our desired result.
Here is an example that helps us to show the convergence rate, and we use toy example 1 as an example:
Recall that in toy example 1, we have L(θ, w) = (wθ2 + θ2)2, J(θ, w) = wθ2, τ = 1.
And we can easily calculate that:
−∂J(θ,w)∂θ − ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2
−1 ∂−J(θ,w) ∂w = −w + [ 4(2w + 2)θ3 ] [ 2θ4 ]−1
θ = 3w + 1
Thus, we have:
ĴS(θ) :=
 ∂∂w ( ∂−J(θ,w) ∂θ − ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 −1 ∂−J(θ,w) ∂w ) ∂ ∂θ ( ∂−J(θ,w) ∂θ − ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2 −1 ∂−J(θ,w) ∂w ) ∂2L(θ,w) ∂θ∂w ∂2L(θ,w) ∂w2  = [ ∂ ∂w (3w + 1 ) ∂ ∂θ (3w + 1)
2(wθ2 + θ2)2θ 4θ3
] = [ 1 0
2(wθ2 + θ2)2θ 4θ3 ] putting θ∗ = 0, w∗ = −1 into the equation,
ĴS(θ ∗) = [ 1 0 0 0 ] Finally,
0.5 ( ĴS(θ ∗)> + ĴS(θ ∗) ) = 0.5 ([ 1 0 0 0 ] + [ 1 0 0 0 ] ) = [ 1 0 0 0 ] ĴS(θ ∗)>ĴS(θ ∗) = [ 1 0 0 0 ] × [ 1 0 0 0 ] = [ 1 0 0 0 ]
Thus λ2min = 0, λmax = 1 , the convergence rate is O ( (1− 0 )T/2 ) = O ( 1T/2 ) .
Similarly, we have:
−∂J(θ,w)∂θ − k1k −1 2 ∂−J(θ,w) ∂w = −w + θw
( θ2 )−1 θ ,
Thus,
JS(θ) :=
[ ∂ ∂w ( −λ (θ2+λ) w ) ∂ ∂θ ( −λ (θ2+λ) w )
∂2L(θ,w) ∂θ∂w
∂2L(θ,w) ∂w2 ] = [ −λ (θ2+λ) 2λθ (θ2+λ)2 w
2(wθ2 + θ2)2θ 4θ3 ] putting θ∗ = 0, w∗ = −1 into the equation,
JS(θ ∗) = [ −1 0 0 0 ] = [ −1 0 0 0 ] Finally
0.5 ( JS(θ ∗)> + JS(θ ∗) ) = [ −1 0 0 0 ] JS(θ ∗)>JS(θ ∗) = [ −1 0 0 0 ] × [ −1 0 0 0 ] = [ 1 0 0 0 ]
Thus λ2min = 1, λmax = 1 O
(( 1− 1
2
)T/2) = O ( 0.5T/2 )

heading: E TRAJECTORIES OF SDDPG AND FSDDPG.
text: This section we show the distances of trajectories of SDDPG and FSDDPG are bounded. We firstly introduce an assumption: Assumption 1. Qw(s, a) is a linear function.
This assumption is also adopted in the analysis of temporal difference (Bhandari et al., 2018). In fact, the assumption only serves as foundations of the proofs ine (Bhandari et 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.
|| ∂w∂π(a|s) || ≤ H1, || ∂ ∂θ πθ(a | s)|| ≤ H2, ||
∂2 ∂w2 Q π θ w (s, a)|| ≤ H3, ||∂Q π θ w (s,a) ∂θ || ≤ H4 || ∂∂θ ( ∂ ∂w Q π θ w (s, a) )( ∂ ∂w Q π θ w (s, a)> )−1) || ≤ H5,
|| ∂∂w (( ∂ ∂w Q π θ w (s, a) )( ∂ ∂w Q π θ w (s, a)> )−1) || ≤ H6
|| ∂ ∂θ> ∂ ∂w Q π θ w (s, a)|| ≤ H7 ||∂Q π θ w (s,a) ∂w || ≤ H8
This assumption is standard assumption that the norm of derivatives is bounded, similar to (Ghadimi & Wang, 2018; Reddi et al., 2018). We set Ĥ = max{H1, H2, . . . ,H8}, and H̄ = min{H1, H2, . . . ,H8}.
For compactness, we define k̂1 := ( ∂2L(θ,w) ∂θ∂w ) , and k̂2 := ( ∂2L(θ,w) ∂w2 ) .
We also define κ1 := k̂1 − k1, and κ2 := k̂2 − k2 as the residual terms. We also define := ||Qπθw (s, a)−Qπθ ||.
We also denote the minimum eigenvalue of E [ ∂Q
π θ w (s,a) ∂w ∂Q π θ w (s,a) > ∂w ] as λmin :=
λmin
( E [ ∂Q π θ w (s, a)
∂w
∂Q π θ w (s, a)>
∂w
]) .
Lemma 7. we have ||κ1|| ≤ 2 H7 and ||κ2|| ≤ 2 H3.
Proof. Based on the definition of κ1and κ2 and the property of norm, we have:
||κ1|| = ||Es∼ρ,a∼π θ (·|s)
[ 2 ( Q π θ w (s, a)−Qπθ (s, a) )( ∂ ∂θ> ∂ ∂w Q π θ w (s, a) )] ||
≤ 2 H7
||κ2|| = ||Es∼ρ,a∼π θ (·|s)
[ 2 ( Q π θ w (s, a)−Qπθ (s, a) ) ∂2Qπθw (s, a) ∂w2 ] ||
≤ 2 H3
Lemma 8. For the i.i.d sampling schemes, we have ≤ HT , where H is a positive constant.
Proof. The proof directly follows Sec. 6.1 in (Bhandari et al., 2018).
The i.i.d sampling scheme assumptions are also used in (Nachum et al., 2019; Sutton et al., 2012; Liu et al., 2020; Dalal et al., 2018).
Lemma 9. If ≤ √
λmin−1 4H23H8 , We always have ||κ1k2 − k1κ2|| ≤ 2 (H8H10H7 + H1H2H3) , ||(k2 + κ2)k2|| ≤ 2H3H8 .
Proof. For ||κ1diago(k2)− k1κ2||, we have:
||κ1k2 − k1κ2|| = || (( Q π θ w (s, a)−Qπθ (s, a) )( ∂
∂θ> ∂ ∂w Q
π θ w (s, a)
)) ∂Q
π θ w (s,a) ∂w ∂Q π θ w (s,a) > ∂w
− ∂ ∂θ> ∂ ∂w Q
π θ w (s, a) (( Q π θ w (s, a)−Qπθ (s, a) ) ∂Q π θ w (s,a) ∂w ∂Q π θ w (s,a) > ∂w ) ||
≤ ||∂Q π θ w (s,a) ∂w ∂Q π θ w (s,a) > ∂w || || ( Q π θ w (s, a)−Qπθ (s, a) )( ∂ ∂θ> ∂ ∂w Q π θ w (s, a) ) ||
+2|| (
∂ ∂w Q
π θ w (s, a)
∂w ∂θ )> ( ∂ ∂w Q πθ w (s, a) ) || || ( Q π θ w (s, a)−Qπθ (s, a) ) ∂2 ∂w2 Q π θ w (s, a)||
≤ 2H8H7 + 2H1H2H3 = 2 (H8H7 +H1H2H3)
For ||[κ2 + k2]−1||, we have:
||[κ2 + k2]−1|| (a) = ||κ−12 − κ −1 2 k2[k2 + κ2] −1|| ≤ 2 H3 + 2 H32 H3||[k2 + κ2]−1||
After some simplification, we have:
||[k2 + κ2]−1|| ≤ G1 G2
(a) follows Lemma 4, where G1 = 2 H3, G2 = 1− 2 H32 H3. Therefore, putting the above inequality together, we have:
||[(k2 + κ2)k2]−1|| ≤ ||[k2 + κ2]−1||||k2−1||
≤ G1 G2 ||k−12 ||
≤ G1 G2λmin
(b) ≤ 2H3 .
(b) is based on the assumption ≤ √
λmin−1 4H23 , which induces 1− 2 H32 H3 ≤ λmin .
Theorem 3. ||ζ(θ)− ζ̂(θ)|| is bounded by 5H10H3H8(H8H10H7 +H1H2H3)H 1T 2 .
Proof. Using the lemmas mentioned above, we have: ||ζ(θ)− ζ̂(θ)|| = || [(
(k1+κ1) (k2+κ2) − k1k2 ) ∂J(θ,w) ∂w , 0 ] ||
≤ || (
(k1+κ1) (k2+κ2) − k1k2 ) ||||∂J(θ,w)∂w ||
= ||(κ1k2 − k1κ2)(k2 + κ2)k−12 |||| ∂J(θ,w) ∂w || ≤ ||((k2) + κ2)(k2||||(((k2 + κ2)k−12 |||| ∂J(θ,w) ∂w || ≤ 5H10H3(H10H7 +H1H2H3) 2 ≤ 5H10H3(H10H7 +H1H2H3)H 1T 2
Where the third inequality is based on Lemma 7 and 9, and the last inequality is based on Lemma 8.

heading: F ALMOST SURELY AVOID SADDLE POINTS.
text: The proof relies on Theorem 4 in (Fiez et al., 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 if ζ(θ) = 0. Definition 2. A point is a strict saddle point if ζ(θ) = 0,and its some eigenvalues are less than 0, while others are larger than 0. Definition 3. A point is a locally asymptotically stable equilibrium if ζ(θ) = 0,and all its eigenvalues are larger than 0. Lemma 10. ||ζ(θ1)− ζ(θ2)|| is Lipschitz continuous.
Proof. Firstly we observe the following inequalities:
|| ∂∂w1 ∂L(θ1,w1) ∂w1 || ≤ || ∂∂w1 ( Q π θ1 w1 (s, a)−Qπ(s, a) ) ∂Q π θ1 w1 (s,a) ∂w1 ||
= || ∂∂w1 [( Q π θ1 w1 (s, a)−Qπ(s, a) ) ∂Q π θ1 w1 (s,a) ∂w1 ] ||
= ||∂ 2Q
π θ1 w1 (s,a) ∂w21 ( Q π θ1 w1 (s, a)−Qπ(s, a) ) + ∂Q π θ1 w1 (s,a) ∂w1 ∂Q π θ1 w1 (s,a) ∂w1 ||
≤ 2H3Rmax1−γ +H 2 4 || ∂∂θ ( ∂J(θ,w) ∂θ − k1(θ) k −1 2 (θ) ∂J(θ,w) ∂w ) ||
≤ || ∂∂θ ∂Q π θ w (s,a) ∂θ − ∂ ∂θ{ [ ( ∂ ∂w Q π θ w (s, a) )> ( ∂ ∂w Q π θ w (s, a) ∂w ∂θ )]> (
∂ ∂w Q
π θ w (s, a)
∂ ∂w Q
π θ w (s, a)>
)−1 ∂Q
π θ1 w (s,a) ∂w }||
= || ∂ 2Q π θ w (s,a) ∂θ2 − ∂ ∂θ {( ∂ ∂w Q π θ w (s, a) ∂w ∂θ )> ( ∂ ∂w Q π θ w (s, a) )( ∂ ∂w Q π θ w (s, a)> )−1} ||
= ||∂ 2Q π θ w (s,a) ∂θ2 − ∂ ∂θ
{ ∂Q
π θ w (s,a) ∂θ ( ∂ ∂w Q π θ w (s, a) )( ∂ ∂w Q π θ w (s, a)> )−1} ||
≤ H3 + H3H4 + H1H2H4H5
||∂ 2L(θ,w) ∂θ∂w || ≤ || ∂ ∂θ ( Q π θ1 w1 (s, a)−Qπ(s, a) ) ∂Q π θ1 w1 (s,a) ∂w1 ||
= || ( ∂ ∂θQ π θ1 w1 (s, a) ) ∂Q π θ1 w1 (s,a) ∂w1 + ( Q π θ1 w1 (s, a)−Qπ(s, a) ) ∂ ∂θ ∂Q π θ1 w1 (s,a) ∂w1 || ≤ H1H3H24 + 2H3Rmax1−γ H4
|| ∂∂w ( ∂J(θ,w) ∂θ − k1(θ) k −1 2 (θ) ∂J(θ,w) ∂w ) ||
≤ || ∂∂w ( ∂Q π θ w (s,a) ∂θ ) − ∂∂w{ [ ( ∂ ∂w Q π θ w (s, a) )> ( ∂ ∂w Q π θ w (s, a) ∂w ∂θ )]> (
∂ ∂w Q
π θ w (s, a)
∂ ∂w Q
π θ w (s, a)>
)−1 ∂Q
π θ1 w (s,a) ∂w }||
= || ∂∂w ( ∂Q π θ w (s,a) ∂θ ) − ∂∂w { ∂Q π θ w (s,a) ∂θ ( ∂ ∂w Q π θ w (s, a) )( ∂ ∂w Q π θ w (s, a)> )−1} ||
= H4 + H1H2H4H6
Therefore, based on the fact that for any continuous function f if sup ||∇xf(x)|| ≤ L, then f(x) is L-lipschitz continuous, we have:
||w(θ1)− w(θ2)||
= ||
[( ∂J(θ1,w1)
∂θ1 − k1(θ1) k−12 (θ1) ∂J(θ1,w1) ∂w1
) − ( ∂J(θ2,w2)
∂θ2 − k1(θ2) k−12 (θ2) ∂J(θ2,w2) ∂w2 ) τ ∂L(θ1,w1)∂w1 − τ ∂L(θ2,w2) ∂w2 ] ||
≤ τ ||∂L(θ1,w1)∂w1 − ∂L(θ2,w2) ∂w2 || + || ( ∂J(θ1,w1)
∂θ1 − k1(θ1) k−12 (θ1) ∂J(θ1,w1) ∂w1
) − ( ∂J(θ2,w2)
∂θ2 − k1(θ2) k−12 (θ2) ∂J(θ2,w2) ∂w2
) ||
≤ max{ H4 + H1H2H4H6, H3 + H3H4 + H1H2H4H5 }||θ1 − θ2|| + max { 2H3Rmax
1−γ +H 2 4 , H1H3H 2 4 + 2H3Rmax 1−γ } ||θ1 − θ2||
≤ 2 max{ H4 + H1H2H4H6, H3 + H3H4 + H1H2H4H5, 2H3Rmax
1−γ +H 2 4 , H1H3H 2 4 + 2H3Rmax 1−γ }||θ1 − θ2|| ≤ L||θ1 − θ2||,
where L := 2 max{ H4 + H1H2H4H6, H3 + H3H4 + H1H2H4H5, 2H3Rmax
1−γ +H 2 4 , H1H3H 2 4 + 2H3Rmax 1−γ }.
Now, we can finally prove our claim, the framework follows Theorem 4 in (Fiez et al., 2020):
Theorem 4. If αL < 1, our method converges to the strict saddle points of both ζ(θ) and ˆzeta(θ) on a set of measure zero.
Proof. We firstly prove that g(θ) is invertable, which can be done by contradictions. Consider θ1 6= θ2, and suppose g(θ1) = g(θ2) so that θ1 − θ2 = αw(θ1)− αw(θ2) . According to Lemma 10, α||w(θ1) − w(θ2)|| ≤ αL||θ1 − θ2|| < ||θ1 − θ2|| , giving a contradiction. Therefore, it is invertible.
Now, observe that ∂g(θ)
∂θ = I − αJS(θ), and if
∂g(θ)
∂θ is invertible, then according to the inverse
function theorem, we have g(θ) is local diffeomorphism. Hence, it suffices to show that I − αJS(θ) does not have an eigenvalue of 0 (or ∂g(θ)
∂θ does not have an eigenvalue of 1). Indeed, letting ρ(A)
be the spectral radius of a matrixA, we know that ρ(A) ≤ ||A|| for any square matrixA and induced operator norm || · || so that ρ(αJS(x)) ≤ ‖αJS(x)‖ ≤ α sup
θ ‖JS(θ)‖ < αL < 1,
The above implies that all eigenvalues of αJS(θ) have absolute value less than 1. Since g(θ) is injective by the preceding argument, its inverse is well-defined . Also, since g(θ) is a local diffeomorphism on Θ ⊗ Σ, it follows that g(θ) is smooth on Θ ⊗ Σ. Thus, g(θ) is a diffeomorphism.
Consider all critical points of θ, given by ker(w). For each u ∈ ker(w), let Bu, where u indexes the point, be the open ball derived from the center manifold theorem, and let B = ∪uBu. Since Θ ⊗
Σ ⊆ Rm, Lindelöf’s lemma indicates that every open cover has a countable sub-cover. That is, for a countable set of critical points {ui}∞i=1 with ui ∈ ker(w), we have that B = ∪∞i=1Bui .
Starting from some point θ0 ∈ Θ ⊗ Σ, if our methods converges to a strict saddle point,
then there exists a t0 and index such that gt(θ) ∈Bui . Applying the center manifold theorem and using that g(θ) ⊆ Θ ⊗ Σ, we get that g(θ0) ∈W csloc ∩Θ ⊗ Σ.
Using the fact that g(θ) is invertible, we can iteratively construct the sequence of sets defined by W1(ui) = g −1 ( W csloc ∩Θ ⊗ Σ ) and Wk+1(ui) = g−1(Wk(ui)∩Θ ⊗ Σ). Then we have that
θ0 ∈Wt(ui) for all t ≥ t0. The set Θ0 ⊗
Σ0 = ∪∞i=1 ∪∞t=0Wt(ui) contains all the initial points in X such that our method converges to a strict saddle.
Since ui is a strict saddle, I − αJS(θ) has an eigenvalue greater than 1. This implies that the codimension of the unstable manifold is strictly less than m—i.e., dim (W csloc) < m . Hence, W cs loc∩X has Lebesgue measure zero.
Using again that g(θ) is a diffeomorphism, g−1 ∈ C1 so that it is locally Lipschitz and locally Lipschitz maps are null set preserving. Hence, WK(ui) has measure zero for all k by induction so that Θ0 ⊗ Σ0 = ∪∞i=1 ∪∞t=0Wt(ui) is a measure zero set since it is a countable union of measure zero sets.

heading: G ENVIRONMENTS SETUP
text: We list some important statstics about the environments as shown in Table 6 and the detailed dynamics of each environments can be found in (Duan et al., 2016; Tunyasuvunakool et al., 2020).
Moreover, we also list hyper-parameters of our methods and baselines as shown in Tables 4 and 5.
Here, we would like to discuss more details on why SDDPG-BD is slow comparing with FSDDPGBD. Theoretically speaking, since it needs to compute the partial of the Hessian ∂
2Q πθ w (s,a) ∂wθ , its
convergence rate is slow than ours as mentioned in Sec. 4.3.
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 diago(∂
2L(θ,w) ∂w2 ) in parallel through GPU. That
is, we need to calculate the elements of Hessian matrices on diagonal block matrix. However, the torch.autograd.grad11 function does not support calculating the gradient of a 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 on OpenAI’s Spinning UP (Achiam, 2018). The codes for DDPG and TD3 are from https://spinningup.openai.com/.

heading: H EXTRA EXPERIMENTS
text: We conduct the full version of SDDPG on two of the simplest environments in MuJoCo: InvertedDoublePendulum, as well as 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 in 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. 1, which also supports the assumption that the TD-related term pulls the agent to remain in best repsonse area in Sec. 4.
11https://pytorch.org/docs/stable/generated/torch.autograd.grad.html

heading: I SOME IMPORTANT SOURCE CODES
text: To make our reader know more about our algorithm. We put some important part of the source Codes here. One can implement our FSDDPG by just putting the following code to replace the corresponding functions in https://github.com/openai/spinningup/blob/master/ spinup/algos/pytorch/ddpg/ddpg.py.
def compute_loss_q(data): """Calculates the loss for the critic""" o, a, r, o2, d = data[’obs’].to(device), data[’act’].to(device),
data[’rew’].to(device), \ data[’obs2’].to(device), data[’done’].to(device)
q = ac.q(o,a)
# Bellman backup for Q function with torch.no_grad(): #stop-gradient operator for semi-gradient
technique. q_pi_targ = ac_targ.q(o2, ac_targ.pi(o2)) backup = r + gamma * (1 - d) * q_pi_targ
# MSE loss against Bellman backup loss_q = ((q - backup)**2).mean()
# Useful info for logging loss_info = dict(QVals=q.detach().cpu().numpy())
return loss_q, loss_info
def calculate_s_actor_loss(data): """Calculates the Stackelberg gradient for the actor""" states = data[’obs’].to(device) actions_pred = ac.pi(states) q = -ac.q(states, actions_pred).mean() dq_dws = autograd.grad(outputs=q, inputs=ac.q.parameters(),
create_graph=True) dq_dthetas = autograd.grad(outputs =q,
inputs = ac.pi.parameters(), create_graph=True)
# vectorize dq_dw_vec = torch.zeros(size=[1]).to(device) dq_dtheta_vec = torch.zeros(size=[1]).to(device)
for dq_dw in dq_dws: dq_dw = torch.flatten(dq_dw) dq_dw_vec = torch.cat((dq_dw_vec,dq_dw),dim=0) dq_dw_vec = dq_dw_vec[1:].unsqueeze(0) #delete the first element
for dq_dtheta in dq_dthetas: dq_dtheta = torch.flatten(dq_dtheta) dq_dtheta_vec = torch.cat((dq_dtheta_vec,dq_dtheta),dim=0) dq_dtheta_vec = dq_dtheta_vec[1:].unsqueeze(0) #delete the first element
k_1 = 2*torch.transpose(dq_dw_vec,dim0=0,dim1=1)@dq_dtheta_vec# Theta*w
#deal with the diagonal block k_2_dia = 2 * dq_dw_vec * dq_dw_vec # w*w rec_k_2_dia = torch.reciprocal(k_2_dia + 1e-5)
#calculate the gradient for actor dq_dtheta_stack = torch.transpose(dq_dtheta_vec,
dim0=0, dim1=1) \
+ torch.transpose(k_1, dim0=0, dim1=1) * \ rec_k_2_dia @ torch.transpose(dq_dw_vec, dim0=0, dim1=1)
dq_dtheta_stack = dq_dtheta_stack[:,0]
for i,para in enumerate(ac.pi.parameters()): para.grad = dq_dtheta_stack[param_index[i]:param_index[i+1]].
reshape(para.shape)
def update(data): # First run one gradient descent step for Q. q_optimizer.zero_grad() loss_q, loss_info = compute_loss_q(data) loss_q.backward() q_optimizer.step()
# Manaully reset gradient for p in ac.pi.parameters():
p.requires_grad = False p.requires_grad = True
# SDDPG Next run one gradient descent step for pi. calculate_s_actor_loss(data) pi_optimizer.step()

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

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.

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. 

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.