Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning Algorithms

Link: https://arxiv.org/abs/2109.12286
Authors: Liyuan Zheng, Tanner Fiez, Zane Alumbaugh, Benjamin Chasnov, Lillian J. Ratliff
Written by: Pronoma Banerjee

---

Abstract and Introduction

The paper discusses the following:

1. It models the actor-critic interactions in the actor-critic reinforcement learning algorithms as a two-player general sum Stackelberg game with a leader-follower structure.
2. Modeling Contributions: Proposes a framework for the Stackelberg actor-critic algorithms where the leader follows the total derivative of its objective function defined using the implicit function theorem and the follower updates using individual gradient dynamics, and compares it with previous approaches of using individual gradients for both the actor and critic.
3. Theoretical contributions: Develops a policy gradient theorem (Theorem 1) for the refined update of the total derivative, builds a meta-framework of Stackelberg actor-critic algorithms, adapting the standard actor-critic, deep deterministic policy gradient and soft actor-critic algorithms, and provides a local convergence guarantee (Theorem 2) for them to a local Stackelberg equilibrium defined by gradient-based sufficient conditions.
4. Experimental contributions: Show through examples that Stackelberg gradient dynamics mitigate cycling and accelerate convergence. Further experiments show that Stackelberg actor-critic algorithms always perform at least as well and often significantly outperform the standard actor-critic algorithm counterparts.

---

Motivation and Preliminaries

We first start by stating the implicit function theorem used for the objective function of the leader in a Stackelberg game:

Implicit function theorem
Let

$f=(f_1,f_2,...,f_n)$ be a vector-valued function defined in an open set in

$R^{n+k}$ with values in

$R^n$. Suppose

$f\in C^{\prime }$ on

$S$. Let

$(x_0,t_0)$ be a point in

$S$ for which

$f(x_0,t_0)=0$ and for which the

$n\times n$ determinant

$det[D_j{f}_i(x_0,t_0)]\ne 0$. Then there exists a k-dimensional open set

$T_0$ containing

$t_0$ and one and only one vector valued function

$g$, defined on

$T_0$ and having values in

$R^n$ such that:

1. $g\in C^{\prime }$ on
   $T_0$
2. $g(t_0)=x_0$
3. $f(g(t),t)=0$ for all
   $t\in T_0$

Game theoretic priliminaries

A Stackelberg game is a game between two agents where one agent is deemed the leader and the other the follower. The leader optimizes it's objective assuming that the follower will play its best response. We frame the leader's objective using the implicit function theorem.

Let

$f_1(x_1,x_2)$ and

$f_2(x_1,x_2)$ be the objective functions that the leader and follower want to minimize, respectively, where

$x_1\in X_1\subseteq R^{d_1}$ and

$x_2\in X_2\subseteq R^{d_2}$ are their decision variables or strategies and

$x=(x_1,x_2)\in X_1\times X_2$ is their joint strategy.

The leader L aims to solve the following:
min

${}_{x_1\in X_1}\{f_1(x_1,x_2)|x_2\in arg$ min

${}_{y\in X_2}{f}_2(x_1,y)\}$

and the follower F aims to solve the following problem:
min

${}_{x_2\in X_2}{f}_2(x_1,x_2)$

Since the leader assumes the follower chooses a best response

$x_2^{\ast }(x_1)$ = arg min

${}_y{f}_2(x_1,y)$, the follower’s decision variables are implicitly a function of the leader’s. The leader utilizes this while deriving the sufficient conditions for its optimization, from the total derivative of its cost function:

$\nabla f_1(x_1,x_2^{\ast }(x_1))={\nabla }_1{f}_1(x)+(\nabla x_2^{\ast }(x_1){)}^{\top }{\nabla }_2{f}_1(x)$.
where

$\nabla x_2^{\ast }(x_1)=-({\nabla }_2^2{f}_2(x){)}^{-1}{\nabla }_{21}{f}_2(x)$

Hence, a point

$x=(x_1,x_2)$ is a local solution to L's objective if

$\nabla f_1(x_1,x_2^{\ast }(x_1))=0$ and

${\nabla }_2{f}_1(x_1,x_2^{\ast }(x_1))>0$. For the follower’s problem, sufficient conditions for optimality are

${\nabla }_2{f}_2(x_1,x_2)=0$ and

${\nabla }_2{f}_2(x_1,x_2)>0$.

Next we define a concept that gives the sufficient conditions for a local Stackelberg equilibrium:

Differential Stackelberg Equilibrium
The joint strategy

$x^{\ast }=(x_1^{\ast },x_2^{\ast })\in X_1\times X_2$ is a differential Stackelberg equilibrium if

$\nabla f_1(x^{\ast })=0,{\nabla }_2{f}_2(x^{\ast })=0,{\nabla }^2{f}_1(x^{\ast })>0,$ and

${\nabla }_2^2{f}_2(x^{\ast })>0.$

Stackelberg gradient dynamics
It is derived from the first-order gradient based sufficient conditions and are given by:

$x_{1,k+1}=x_{1,k}-{\alpha }_1\nabla f_1(x_{1,k},x_{2,k})$

$x_{2,k+1}=x_{2,k}-{\alpha }_2\nabla f_1(x_{1,k},x_{2,k})$

Motivating Examples
The actor and critic exhibit simple hidden structure in their parameters for all actor-critic algorithms. The actor objective typically has a hidden linear structure in terms of the parameters

$\theta$ which is abstractly of the form

$Q_w(\theta )=w^{\top }\mu (\theta )$. The critic objective usually has a hidden quadratic structure in the parameters

$w$ which is abstractly of the form of

$(R(\theta )-Q_w(\theta ){)}^2$. The actor seeks to find the action that maximizes the value indicated by the critic and the critic approximates the rewards of actions generated by the actor. For simplicity, we assume the critic only minimizes the mean square error of the sample action generated by current actor

$\theta$.

Next we briefly go through the various actor-critic algorithms. The vanilla actor-critic and the deep deterministic policy gradient optimize their objectives by performing the individual gradient dynamics (gradient descent and ascent) on the actor and critic parameters. The soft actor-critic exhibit a similar structure as the others, but with entropic regularization in the actor objective.

1. Actor Critic (AC):

   • Relies on the critic function
     $Q_w(s,a)$ parameterized by
     $w$ to approximate
     $Q^{\pi }(s,a)$.
   • The actor which is parameterized by
     $\theta$ has the objective:
     
     $J(\theta ,w)$ = E
     ${}_{s\sim \rho ,a\sim {\pi }_{\theta }(·|s)}[Q_w(s,a)]$
     (from policy gradient theorem).
   • The objective is optimized using gradient ascent where:
     
     $\nabla \theta J(\theta ,w)$ = E
     ${}_{s\sim \rho ,a\sim {\pi }_{\theta }(·|s)}[{\nabla }_{\theta }log({\pi }_{\theta }(a|s))Qw(s,a)]$.
   • The critic which is parameterized has the objective to minimize the mean square error between the Q-functions:
     
     $L(\theta ,w)$ = E
     ${}_{s\sim \rho ,a\sim {\pi }_{\theta }(·|s)}[(Q_w(s,a)-Q_{\pi }(s,a){)}^2]$,
     where
     $Q^{\pi }(s,a)$ is approximated by Monte Carlo estimation or bootstrapping.

2. Deep Deterministic Policy Gradient (DDPG):

   • Deterministic actor
     ${\mu }_{\theta }(s):S\to A$ with objective:
     
     $J(\theta ,w)$ = E
     ${}_{\xi \sim D}[Q_w(s,{\mu }_{\theta }(s))]$.
   • Critic objective is the mean square Bellman error:
     
     $L(\theta ,w)$= E
     ${}_{\xi \sim D}[(Q_w(s,a)-(r+\gamma Q_0(s^{\prime },{\mu }_{\theta }(s^{\prime }))){)}^2]$.
     where
     $\xi =(s,a,r,s^{\prime })$,
     $D$ is a replay buffer, and
     $Q_0$ is a target
     $Q$ network.

3. Soft Actor Critic (SAC):

   • Exploits double Q-learning and employs entropic regularization to encourage exploration.
   • Actor's objective:
     
     $J(\theta ,w)$ = E
     ${}_{\xi \sim D}$[min
     ${}_{i=1,2}{Q}_{w_i}(s,a_{\theta }(s))-\eta$ log
     $({\pi }_{\theta }(a_{\theta }(s)|s))]$,
     where
     $a_{\theta }(s)$ is a sample from
     ${\pi }_{\theta }(.|s)$ and
     $\eta$ is the entropy regularization coefficient.
   • The parameter of the critic is the union of both Q networks parameters
     $w=\{w1,w2\}$ and the critic objective is defined correspondingly by:
     
     $L(\theta ,w)$ = E
     ${}_{\xi \sim D}[\sum _{i=1,2}(Q_{w_i}(s,a)-y(r,s^{\prime }){)}^2]$,
     where
     
     $y(r,s^{\prime })=r+\gamma$(min
     $Q_{0,i}(s^{\prime },a_{\theta }(s^{\prime }))-\eta$ log
     $({\pi }_{\theta }(a_{\theta }(s^{\prime })|s^{\prime })))$.

The target networks in DDPG and SAC are updated by taking the Polyak average of the network parameters over the course of training, and the actor and critic networks are updated by individual gradient dynamics:

$\theta \leftarrow \theta +{\alpha }_{\theta }{\nabla }_{\theta }J(\theta ,w)$

$w\leftarrow w-{\alpha }_w{\nabla }_{w}L(\theta ,w)$

---

Stackelberg framework

Meta algorithm

---

Algorithm: Stackelberg Actor-Critic Framework

Input: actor-critic algorithm ALG, player designations, and learning rate sequences

${\alpha }_{\theta ,k},{\alpha }_{w,k}$.

Case 1: if actor is leader, update actor and critic in ALG with:

${\theta }_{k+1}={\theta }_k+{\alpha }_{\theta ,k}\nabla J({\theta }_k,w_k)$

$w_{k+1}=w_k-{\alpha }_{w,k}{\nabla }_{w}L({\theta }_k,w_k)$

Case 2: if critic is leader, update actor and critic in ALG with:

${\theta }_{k+1}={\theta }_k+{\alpha }_{\theta ,k}{\nabla }_{\theta }J({\theta }_k,w_k)$

$w_{k+1}=w_k-{\alpha }_{w,k}\nabla L({\theta }_k,w_k)$

---

When actor is the leader (case 1), the total derivative of the actor is given by:

${\nabla }_{\theta }J(\theta ,w)-{\nabla }_{w\theta }^{\top }L(\theta ,w)({\nabla }_w^{2}L(\theta ,w){)}^{-1}{\nabla }_{w}J(\theta ,w)$.

When critic is the leader (case 2), the total derivative of the critic is given by:

${\nabla }_{w}L(\theta ,w)-{\nabla }_{\theta w}^{\top }J(\theta ,w)({\nabla }_{\theta }^{2}J(\theta ,w){)}^{-1}{\nabla }_{\theta }L(\theta ,w)$.

Stackelberg “Vanilla” Actor-Critic (STAC)

The critic assists the actor in learning the optimal policy by approximating the value function of the current policy. The critic aims to be selecting a best response

$w^{\ast }(\theta )=argmi{n}_{w\prime }L(\theta ,w^{\prime })$. Thus, the actor plays the role of the leader and critic the follower.

${\nabla }_{w}J(\theta ,w)=E_{s\sim \rho ,a\sim {\pi }_{\theta }(·|s)}[{\nabla }_w{Q}_w(s,a)]$

${\nabla }_w^{2}L(\theta ,w)=E_{s\sim \rho ,a\sim {\pi }_{\theta }(·|s)}[2{\nabla }_w{Q}_w(s,a){\nabla }_w^{\top }{Q}_w(s,a)+2(Q_w(s,a)-Q^{\pi }(s,a)){\nabla }_w^2{Q}_w(s,a)].$

• Theorem 1: Given an MDP and actor-critic parameters

  $(\theta ,w)$, the gradient of
  $L(\theta ,w)$ with respect to
  $\theta$ is given by:
  ${\nabla }_{\theta }L(\theta ,w)=E_{\tau \sim {\pi }_{\theta }}[{\nabla }_{\theta }log({\pi }_{\theta }(a_0|s_0))(Q_w(s_0,a_0)-Q^{\pi }(s_0,a_0){)}^2$
  $+\sum _{t=1}^T{\gamma }^t{\nabla }_{\theta }log({\pi }_{\theta }(a_t|s_t))(Q^{\pi }(s_0,a_0)-Q_w(s_0,a_0))Q^{\pi }(s_t,a_t)]$.

Theorem 1 allows us to compute

${\nabla }_{\theta w}L(\theta ,w)$ directly by

${\nabla }_w({\nabla }_{\theta }L(\theta ,w))$ since the distribution of

${\nabla }_{\theta }L(\theta ,w)$ does not depend on

$w$ and

${\nabla }_w$ can be moved into the expectation.

The critic in AC is often designed to approximate the state value function

$V^{\pi }(s)$ which has computational advantages, and the policy gradient can be computed by advantage estimation. In this formulation,

$J(\theta ,w)=E_{\tau \sim {\pi }_{\theta }}[r(s_0,a_0)+V_w(s_1)]$ and

$L(\theta ,w)=E_{s\sim \rho }[(V_w(s)-V^{\pi }(s){)}^2]$.

Then

${\nabla }_{\theta }L(\theta ,w)$ can be computed by the next proposition.

• Proposition 1: Given an MDP and actor-critic parameters
  $(\theta ,w)$, if the critic has the objective function
  $L(\theta ,w)=E_{s\sim \rho }[(V_w(s)-V^{\pi }(s){)}^2]$, then
  ${\nabla }_{\theta }L(\theta ,w)$ is given by
  
  $E_{\tau \sim {\pi }_{\theta }}[2\sum _{t=0}^T{\gamma }^t{\nabla }_{\theta }$ log
  ${\pi }_{\theta }(a_t|s_t(V^{\pi }(s_0)-V_w(s_0))Q^{\pi }(s_t,a_t)]$.

Stackelberg DDPG (STDDPG) and SAC (STSAC)

In comparison to on-policy methods where the critic is designed to evaluate the actor using sampled trajectories generated by the current policy, in off-policy methods the critic minimizes the Bellman error using samples from a replay buffer. Thus, the leader and follower designation between the actor and critic in off-policy methods is not as clear. Given the actor as the leader, the algorithms are similar to policy-based methods, where the critic plays an approximate best response to evaluate the current actor. On the other hand, given the critic as the leader, the actor plays an approximate best response to the critic value, resulting in behavior closely resembling that of the value-based methods.

The objective functions of off-policy methods are defined in expectation over an arbitrary distribution from a replay buffer instead of the distribution induced by the current policy. Thus, each terms in the total derivatives updates can be computed directly and estimated by samples.

Convergence guarantee

The following theorem gives a local convergence guarantee to a local Stackelberg equilibrium under the assumption that the maps

$\nabla J:R^m\to R^{m_{\theta }},{\nabla }_{w}L:R^m\to R^{m_w}$ are Lipschitz, and

$||\nabla J||<\infty$, the learning rate sequences for the gradient updates such that

${\alpha }_{\theta ,k}=o({\alpha }_w,k)$ and

$\sum _k{\alpha }_{i,k}=\infty ,\sum _k{\alpha }_{i,k}^2<\infty$ for

$i\in I=\{\theta ,w\}$, and the stochastic components in the gradient updates

$\{{ϵ}_{i,k}\}$ are zero mean, martingale difference sequences.

(A stochastic series is a martingale difference sequence if its expectation with respect to the past is zero.)

• Theorem 2: Consider an MDP and actor-critic parameters
  $(\theta ,w).$ Given a locally asymptotically stable Stackelberg equilibrium
  $({\theta }^{\ast },w^{\ast })$ of the continuous time-limiting system
  $(\dot{\theta },\dot{w})=(▽J(\theta ,w),-{▽}_{w}L(\theta ,w)),$ under the above assumptions there exists a neighbourhood
  $U$ for which the iterates
  $({\theta }_k,w_k)$ of the discrete time system
  
  ${\theta }_{k+1}={\theta }_k+{\alpha }_{\theta ,k}(\nabla J(\theta ,w)+{\epsilon }_{\theta ,k+1})$,
  
  $w_{k+1}=w_k-{\alpha }_{w,k}({\nabla }_{w}L(\theta ,w)+{\epsilon }_{w,k+1})$

This result is effectively giving the guarantee that the discrete-time dynamics locally converge to a stable, game theoretically meaningful equilibrium of the continuous-time system using stochastic approximation methods given suitable learning rate sequences and unbiased gradient estimates.

Implicit Map Regularization

The total derivative in the Stackelberg gradient dynamics requires computing the inverse of follower Hessian

${\nabla }_2{f}_2(x)$. Since critic networks in practical reinforcement learning problems may be highly non-convex,

$({\nabla }_2{f}_2(x){)}^{-1}$ can be ill-conditioned. Thus, instead of computing this term directly in the Stackelberg actor- critic algorithms, we compute a regularized variant of the form

$({\nabla }_2{f}_2(x)+\lambda I{)}^{-1}$. This regularization method can be interpreted as the leader viewing the follower as optimizing a regularized cost

$f_2(x)+{\lambda }_2||x_2|{|}^2$, while the follower actually optimizes

$f_2(x)$. Interestingly, the regularization parameter

$\lambda$ can serve to interpolate
between the Stackelberg and individual gradient updates for the leader.

• Proposition 2: Consider a Stackelberg game where the leader updates using the regularized total derivative:
  ${\nabla }^{\lambda }{f}_1(x)={\nabla }_1{f}_1(x)-{\nabla }_{21}^{\top }{f}_2(x)({\nabla }_2^2{f}_2(x)+\lambda I{)}^{-1}{\nabla }_2{f}_1(x)$. As
  $\lambda \to 0$ then
  ${\nabla }^{\lambda }{f}_1(x)\to \nabla f_1(x)$ and when
  $\lambda \to \infty$ then
  ${\nabla }^{\lambda }{f}_1(x)\to {\nabla }_1{f}_1(x)$.

---

Experiments

Performance:

1. STAC, STDDPG and STSAC are implemented on several tasks on the OpenAI gym environments. The critic is unrolled m steps between each actor step. For each task, STAC with multiple critic unrolling steps performs the best. This is due to the fact when the critic is closer to the best response, then the real response of the critic is closer to what is anticipated by the Stackelberg gradient for the actor.
2. STDDPG with both actor and critic as leader overall perform better than DDPG on the same tasks. However, STSAC's performance does not prove to be advantageous over SAC.
3. In all experiments, when the actor is the leader, the Stackelberg versions either outperform or are comparable to the existing actor-critic algorithms, showing that the Stackelberg framework has an emperical advantage in most tasks.

Game-Theoretic Interpretations
SAC is considered the state-of-the-art model-free reinforcement learning algorithm and it significantly outperforms DDPG on most tasks. The interpretation for this is as follows:

1. The common interpretation of its advantage is that SAC encourages exploration by penalizing low entropy policies.
2. The authors further suggest that the hidden structures in AC and DDPG may lead to cyclic behavious in their individual gradient dynamics. SAC constructs a more well-conditioned game structure by regularizing the actor objective, which leads to the learning dynamics converging more directly to the equilibrium. This also explains why we observe improved performance with STAC and STDDPG-AL compared to AC and DDPG, but the performance gap between STSAC-AL and SAC is not as significant.
3. Experimentally, the actor as the leader always outperforms the critic as the leader. critic objective is typically a quadratic mean square error objective which results in a hidden quadratic structure whereas the actor’s objective typically is in the form of a hidden linear due to parameterization of the Q network and policy. As a result, the critic cost structure is more well-suited for computing an approximate local best response since it is more likely to be well-conditioned. Thus, the critic being the follower is a more natural hierarchical structure of the game.

---

Conclusion

The paper revisits the standard actor-critic algorithms from a game-theoretic perspective to capture the hierarchical interaction structure and introduce a Stackelberg framework for actor-critic algorithms. The rest of the paper, through theory and experimentation, shows that the Stackelberg actor-critic algorithms always outperform the existing counterparts when the actor plays the leader.

---

Other Relevant References:

1. https://hackmd.io/@FtbpSED3RQWclbmbmkChEA/rJFUQA1QO
2. http://proceedings.mlr.press/v119/fiez20a/fiez20a-supp.pdf
3. https://sci-hub.se/10.1007/978-1-4612-1029-0