Convex-Concave Zero-Sum Markov Stackelberg Games
Authors: Denizalp Goktas
Arjun Prakash
Amy Greenwald
Venue: NeurIPS 2023 poster (2023)
Keywords: Stackelberg games
Equilibrium Computation
Policy Gradient
TL;DR: We develop policy gradient methods to solve zero-sum stochastic Stackelberg games from observed play, and apply our methods to solve reach avoid problems.

Abstract: Zero-sum Markov Stackelberg games can be used to model myriad problems, in domains ranging from economics to human robot interaction. In this paper, we develop policy gradient methods that solve these games in continuous state and action settings using noisy gradient estimates computed from observed trajectories of play. When the games are convex-concave, we prove that our algorithms converge to Stackelberg equilibrium in polynomial time. We also show that reach-avoid problems are naturally modeled as convex-concave zero-sum Markov Stackelberg games, and that Stackelberg equilibrium policies are more effective than their Nash counterparts in these problems.

Convex-Concave O-Sum Markov Stackelberg Games
Denizalp Goktas Brown University, Computer Science deni zal wow.ppottattbbronn..omoommmo edu
Arjun Prakash
Brown University, Computer Science
prejun_praaahhbbroo edu
Amy Greenwald Brown University, Computer Science
any_ggreanaalddbrom....c
Abstract
Zero-sum Markov Stackelberg games be used to model myriad problems, in domains ranging from economics to human robot interaction. We develop a policy gradient method which prove solves these games in continuous state, continuous action settings, using noisy gradient estimates computed from observed trajectories of play. When the games are convex-concave, we prove that our algorithm converges to Stackelberg equilibrium in polynomial time. We also prove that reach-avoid problems are naturally modeled as cuivex-concave zero-sum Markov Stackelberg games, and show experimentally that Stackelberg equilibrium policies are more effective than their Nash counterparts in these problems.
Introduction
Markov games [28, 65, 70] are a generalization of Markov decision processes (MDPs) comprising multiple players simultaneously making decisions over time, collecting rewards along the way depending on their collective actions. They have been used by practitioners to model many real- world multiagent planning and learning environments, such as autonomous driving [31, 59], cloud computing [77], and telecomunications [3]. Moreover, theoreticians are beginning to formally analyze policy gradient methods, proving polynomial-time convergence to optimal policies MDPs [2. 16), and to Nash equilibrium policies [53] in zero-sum Markov games [24], the canonical solution concept. While Markov games are a fruitful way to model some problems (e.g.. robotic soccer [46]), others, such reach-avoid [48], may be more productively modeled as sequential-men move games, where some players commit to moves that are observed by others, before they make their own moves. To this end, study two-player zero-sum Markov Stackelberg [74] (i.e., sequential-move) games. While polynomial value-iteration (i.e., planning) algorithms are known for these games assuming discrete states [36], we develop policy gradient method that converges Stackelberg equilibrium in polynomial time in continuous state, continuous action games, using noisy gradients based only on observed trajectories of play. Furthermore, we demonstrate experimentally that Stackelberg equilibrium policies are more effective than their Nash counterparts in reach-avoid problems.
A (discounted discrete-time) zero-sum Markov Stackelberg game [36] is played over infinite horizon f = 0, 1.... between two players, a leader and a follower. The game starts at time = 0, at some initial state 5(0) ~ E (S) drawn randomly from a set states At each time step t = 1,2, ... the players encounter state (()) E S, where the leader takes its action (*) first, from its action space A(s(!), after which the follower, having observed the leader's action, makes own move (t), chosen from feasible subset (t)()), a (t) determined by the leader's action (!))
A full and current version of the paper can be found at: https: btt.ps://arxiv.rrrt abse//////////aaaaa/a/aa 12433 12437
37th Conference on Neural Information Processing Systems (NcurIPS 2023), New Orleans.

---

of its action space ((s ((s()), After both players have taken their actions, they receive respective rewards, -r(s(t), at), b(t) and r(s(t) aa)),, b(O)). The game then moves to time step t + 1 and
transitions either to new state 1(++1) p(- s(t), a b()) with probability called the discount factor, or the game ends with the remaining probability. Each player's goal to play a (potentially history-dependent) policy that maximizes its respective expected (cumulative discounted) payoffs.
-E [o ( ,A(1), B( and E [Σr= 7'
7 ((((t), A B())]
In zero-sum Markov Stackelberg games, when the reward functtio (a, b) + r(s, a,b) b) is continuous and bounded, for all s E S, and the correspondence E C(s. a) is continuous, well as non-empty- and compact-valued, a recursive (or Markov perfect) [49] Stackelberg equilibrium is guaranteed to exist [36], meaning stationary policy profile (i.c., a pair of mappings from states to the actions of the leader and the follower, respectively) specifying the actions taken at each state s.t. the leader's policy maximizes its expected payoff assuming the follower best responds, while the follower indeed best responds to the leader's ' policy. In other words, the aforementioned assumptions guarantee the existence of a policy profile π'' = (Ta πT),, with Ta : S + A and _ S + B, that solves the following coupled min-max optimization problem:
min
max Ty T 8:
E
Σ
rr((s Ta T (T (T)
(I)
VaES (x)),,, (s))
where the expectation is with respect to ((0) ~ μ and g(++1) ~ p(- |((t), TT (S())) The
problem is "coupled"' because the players' actions sets constrain one another; in particular, the set of actions available to the follower at each state is determined by the leader's choice.
In spite of multiple compelling applications, including autonomous driving [29, 43), reach-avoid problems in human-robot interaction [10]. robust optimization in stochastic environments [15], and resource allocation over time [36]. very little is known about computing recursive Stackelberg equilibria in zero-sum Markov Stackelberg games. version of value iteration is known to converge in polynomial time when the state space is discrete [36], but this (planning) method becomes intractable large or continuous state spaces. Furthermore, nothing is known, our knowledge, about learning Stackelberg equilibria from observed trajectories of play. We develop an efficient policy gradient method for convex-concave zero-sum Markov Stackelberg games, and we show that reach-avoid problems naturally lie in this class of games.
Contributions.
Equation (1) reveals that the problem of computing Stackelberg equilibria in zero- sum Markov Stackelberg games is an instance of a coupled min-max optimization problem. Goktas and Greenwald [33] studied coupled min-max optimization problems assuming an exact first-order oracle, meaning one that returns a function's 's exact value and gradient at any point in its domain. As access to an exact oracle is an unrealistic assumption in Markov games, we develop first-order method for solving these problems, assuming access to stochastic first-order oracle. which returns noisy estimates of function's value and gradient at any point in its domain. We show that our method converges in polynomial-time (Theorem 3. in large class of coupled min-max optimization problems, namely those which are convex-coneave
We then proceed to study zero-sum Markov Stackelberg games, providing sufficient conditions on the action correspondence C S A + B, the rewards S A B R, and the transition probabilities S x A B + R_ to guarantee that the game is convex-coneet conccve, Furthermore, we develop a policy gradient algorithm that provably converges to Stackelberg equilibrium in polynomial time when such games are convex-concave (Theorem 4.1). the first reinforcement learning algorithm of this kind. Our method specializes to continuous state, continuous action zero-sum Markov games; as such, we provide provably-convent convergent policy gradient method for these problems as well. Finally, we prove that our framework naturally models reach-avoid problems, and run experiments which show that the Stackelberg equilibrium policies learned by our method exhibit better safety and liveness properties than their Nash counterparts.
"To simplify notation, we drop the dependency of action spaces AA and B on states going forward, but our thcory applics in this more general setting. Unlike (1) and (0), which are deterministic actions because they depend on a realized history of states and actions encountered, ((t) and (()) are random variables, because they might depend on random history.

---

2 Preliminaries
Notation. All notation for variable types, c.g., vectors, should be clear from context; if any confusion arises, see Appendix A. Unless otherwise noted, we assume| ||-|| is the Euclidean norm, I1-11z- We let A. = {0 E + Ei= 2i 1} denote the unit simplex in IR". and (A), the set of probability distributions on the set A. We also define the support of any distribution f E A (X²) as supp(f)= = {a E X: f(x) > 0}. We denote the orthogonal projection operator onto a set C by Hc. i.c. [lc(2) = arg miny yeC || yll². We denote by 1c(x)) the indicator function of a set C, with value if æ C and 0 otherwise. Given two vectors 2, y I", we write 2 y or > y to mean component-wise 2 or >, respectively. For any set C, we denote the diameter by diam(C) = meaxe.erellec-o c'Il. Given a tuple consisting of a sequences of iterates and weights (fx(1) Je, Jt).
the weighted average of the iterates is given by .n Σ, 00)
Σ.
Mathematical Concepts. Given X' C R", the function f X - y is said to be L --iipcchitz
x2 If R, then f is continuous w.r.t. norm |-||| iff Va, 22 E X, f[((()))) f(xgg] S Lg [
convex (resp. concave) iff for all X (0, 1) and æ, x' EX ʃ(xx + (1=A)a² I (resp. 2) Aʃ(z) ({)) (1 (1-A) ) For any V, if the relation holds with equality, then ʃ is called affine. A &wo-sided function h X' x y + 2 is biasfine if æ + f(x, y) is affine for all y E V/ and + h(2, y) is affine for all æ E X. f is p-strongly convex if f(x1) 2 f(x22) + (22)(=))) 21 x22) + 1/2||21 a 1l For convenience, we say that an I-dimensional vector-valued function g X + ) C R' is log-convex, convex, conccee, or concave, respectively, if gl is log-convex, convex, log-concave, or concave, for all & E [1] A correspondence Z X' + ) is concave if for all A E (0,1) and x, x' E X, z(Aar + (1 - A)a=) C (Z + (1 - 2) (z) ), assuming Minkowski summation [22, 57].
We require notions of stochastic convexity related to stochastic dominance of probability distributions [7]. Given non-empty and convex parameter and outcome spaces W and O respectively, a conditional probability distribution w + p(- w) E (O)) is said to be stochastically convex (resp. stochastically concave) in w W if for all continuous, bounded, and convex (resp. concave) functions O - R.
A E (0, 1), and w', wt W s.t. w Xw + (1 A)wi, it holds that Ee- (m) [e(O)] < (resp 2) À (o-pp(/w")) [u[O]] + (1 A) Eo-pt-ppo)) [e((O]]
3 Coupled Min-Max Optimization Problems
A min-max Stackelberg game, denoted V g). is two-player, zero-sum game, where one player, called the leader, first commits to an action a E X from its action space X' C R", after which the second player, called the follower, takes action y 2(x) y from subset of of his action space y C R. determined by the action correspondence Z IR = Y As is standard in the optimization literature, we assume throughout that the follower's action correspondence can be equivalently represented via a coupling constraint function {y E 3' g(, y) 2 0). An action profile (æ, y) E X x ) comprises actions for both players. Once both players have taken their actions, the leader (resp. follower) receives a loss (resp. payoff) f(æ,, y). defined by an objective function f R" x R + R. We define the marginal function (x( = maxye2(a f(x, y), which, given an action for the leader, outputs its ensuing payoff, assuming the follower best responds. The constraints in a min-max Stackelberg game are said to be uncoupled if Z(x)= y, for all æ E X. A min-max Stackelberg game is said to be continuous iff the objective function is continuous; 2. the action spaces X' and y are non-empty and compact; and 3. the action correspondence 21 is continuous, non-empty- and compact- valuuct-valued."
R" x RTm + R. s.t. Z(x)= =
Stackelberg Equilibrium. (c, -tStkkkkelb equilibrium ((s, 6)-SE, or SE if = ó = 0), an action profile (x" ",,""" y²) ) E X' x y s.t. [[g. [g("", "y"")" S 6 and exi (x= + 2 f("" , yy" Z maxyez(a-) / f(= y) 8, for E. 2 0. As a straightforward corollary of Theorem 3.2 of Goktas and Greenwald [33], a SE is guaranteed to exist in continuous Stackelberg games. Moreover, the set of SE can be characterized as solutions to the following coupled min-max optimization problem: min maxyez(a)) f(x, y).
The canonical solution concept for min-max Stackelberg games is the
*See Theorem 5.9 and Example 5.10 of Rockafellar and Wets [63] for conditions that guarantee the continuity of Z Section of Goktas and Greenwald [33].
'For 5 > 0, this definition of an (e. SE is more general than the one introduced by Goktas and Greenwald
[33], as it allows for the coupling constraints to be satisfied only approximately. which is necessary in this paper.
the coupling constraints can only be accessed via stochastic oracle.
3

---

An alternative but weaker solution concept previously considered for min- max Stackelberg games [71] is the E-generalized Nash equilibrium (s-GNE, or GNE if 0), i... (x", .y) E X' x (xx*) s.t. mingex J' (æ., y² )-
2 f' y²) 2 maxy f( .y) - E, for some & > 0. In general, the set of GNE and SE need not intersect; as such, GNE are not necessarily solutions of min ma [ y) (see, Appendix A of Goktas and Greenwald [33]). Furthermore, there is no GNE whose value is less than the SE value of a game, When a min max Stackelberg game's constraints are uncoupled, a(n e-)GNE is called a(n e)-saddle point, or a(n e-)Nash equilibrium, and is also an SE. Finally, a saddle point is guaranteed to exist [67. 73] in continuous min-max Stackelberg games with uncoupled constraints, convex-coneave objective f, and convex action spaces X' and y. in which case such games have traditionally been referred to as convex-concar min-max (simultaneous move) games saddle-point problems [13].
Convex-Concave Games. min-max Stackelberg game is said to be convex-concave if, in addition to being continuous, 1. f is convex; 2. y + f(x,y) y) is concave, for all æ E X; 3. X' and Y are convex; and 4. Z convex-valuee (simuitancous-move) game, because in such games, the marginal function f is necessarily convex when f is convex, by Danskin's 's theorem [23]. Assuming access to an exact first-order oracle, an (e, 6)-SE of convex-concave min-max Stackelberg game can be computed in polynomial time when and are Lipschitz-conie continuus [33], while the computation is NP-hard in continuous min-max Stackelberg games, even when X' and ) are convex, f is sanvex-concave and g is affine [47].
This definition generalizes that of convex-concave min-max
All the conditions that define a convex-coneat namely (. g)g), and are well uell-understood (see, for instance Section 5 of Rockafellar and Wets [63]. with the exception of the condition that the marginal function f be convex. While it is difficult to obtain necessary and sufficient conditions on the game primitives that ensure the convexity of f", one possibility is to require f to be convex in (x, y) and Z to be concave." 7 The following sufficient conditions, which also guarantee concavity, were introduced by Goktas and Greenwald [33].
Stackelberg game depend on the game primitives.
Assumption 1 (Convex-Conce y). and concave in for all x E X; 2. the action correspondence Z is concave; 3. the action spaces X and y are convex.
Assumptions). 1. The objective function f(x, y) is convex in
As these assumptions are only sufficient, they are not necessarily satisfied in all applications of convex- concave min-max Stackelberg game. Hence, the convexity of the marginal function must sometimes be established by other means. We thus provide the following alternative set of sufficient conditions, which we use to show that the reach-avoid problem we study in Section 5 is convex-coneave.
Assumption 2 (Alternative Convex-Coneee Concave Assumptions). 1. (Convex-concave objective) The objective f(x. y) is convex in æ, for all y E y. and concave in y. for all x E X: 2. (log-conven concave coupling) the coupling constraint g(x y) is log-convex in x for all y E Y, and concave in for all x E X; and 3. the action spaces X' and y are convex.
Computation. We now turn our attention to the computation of (c. 8)SE in convex-coneet min-max Stackelberg games, assuming access to an unbiased first-order stochastic oracle (F, G.F,)) com- prising random functions F: R" x Rm x θ + R and G R" x Rm x $ - Rd and sampling distribu- tions F E (@) and G E A (b) s.t. [e==[[((x y: 0) f(x, y). Eg-- [G yi Φ)] g(x, y). Eo V ( F(x y; 0)] = V [(x, y), and Eep V (a a)) G(x y: Φ)) = Vg y). The following as- sumptions are required for the convergence of our methods.
Assumption 3. 1. (Lipschitz game) f and g are tipxchitt-comtinnoou:; 2. (concave representation) the coupling constraint function y + g(x,y)) is concave for all x E X; 3. (Slater's condition) dx E X E y s. gx. ÿ) > 0; and 4. (stochastic oracle) there exists an unbiased first-order
stochastic oracle (F, G, F,9) with bounded variance s.I. v(x, y) E Xx (1) y; [)]?]] S og. (e,,)
EIIVV (w.z) F(x, y: ²) < ow f. and V ( G(z y: +) < ov for v. VV 2 0. In the sequel, we rely on the following notation and definitions. For any action I E X of the leader, we can re-express the marginal function in terms of the Lagrangian f(y,>:a0 = f(x, 3) + (X.g(z, y)) (see, for instance, Section 5 of Boyd et al. [17]) as follows: (x) = max minxeRę lly. x)) Further, we define the follower's best-response correspondence
'A GNE is guaranteed exist in continuous min-max Stackelberg games when the objective function f is the action spaces A and B are convex, and the action correspondence is convex-valued [4]. 'See Section 2 of Nikodem [57] and Chapter 36 of Czerwik [22] for conditions on g which guarantee that Z is concave and/or continuous and/or valuxe.

---

(*(x) = arg yy men Ely ); and the KKT multiplier correspondence A (x) - arg meR max Eyy X: Ø). With these definitions hand, under Assumption 3, we can build
an unbiased first-order stochastic oracle L(y, a, 9, Φ) F(zx, y: + < X, (z. y: Φ) > for the Lagrangian é s.t. () (C(y, X; x 0, Φ)}. where the expectation is taken over (0, Φ) F g.
Algorithms. Assuming access to an exact first-order oracle (f.g), a natural approach to comput- ing SE in convex-concave min-max Stackelberg games with uncoupled constraints games (i.e., saddle-point problems) is to simultaneously run projected gradient descent and projected gra- dient ascent on the objective function f w.r.t. x E X and y E V. i.e., for t = 0, 0,1, . ,,)")), a method known under Uzawa, primal-dual, and (simultaneous) gradient descent ascent (GDA) [5, 6]. Intuitively, any fixed point of GDA in such games, i.e., (x",v") E X x y s.t. "]]l O, satisfies the necessary and suffi- cient optimality condition for an action profile to be SE. More generally, in convex eanex--concvee max Stackelberg games (without coupled constraints). this approach fails, as the neces- sary and sufficient optimality condition for an action profile (x", .y") E X y be a SE is [|(x" -xxxxxxxxxx> [ax,, "y") (-v
(xxt++)) (++ + Ixxxy(<!") .y()) + (-V V f (xx(",
the names of
I1a=", y²* [Ixxxy((a> ("="""") ))" ) (- V (zz),, yy"
V Vys(a" .y" yy"))]l 0, where, for any leader action = ((y (z), (T); for some (y" (+) E (*)
& X, (z) ential envelope theorem [33]. The observation that any subgradient of V I" depends the optimal KKT multipliers motivates first-order method based on the gradient of the Lagrangian.
(z), by the subdiffer-
min-max Stackelberg game can be seen as a three-player game m maxyez(x) f(x, y) min ex ex
maXyey minxeR4 E A; æ). where the z-player moves first, and the y- and X X-players move second, simultaneously. because strong duality holds under Assumption 3 (Slater's con- dition [68]) for the inner min-max optimization problem, i.e., maXyey minxeRs {(y,;; >; = minxeR4 maxyey Eyy x)) The problem of computing an SE can thus be reduced to the min-max optimization min(z x maxyey Ely, A; A; which might hope to solve by running GDA on E x:)) w.r.t. (x. A) and y over X Ry and y, respectively. Although y E(y x; concave, (a, A) + (yy x) is not convex, and its stationary points (i.e., points ( xx) s.t. [| x²)=)) - II x xxx x²)==*)= + - -V, (y()xy", X²; x=)== 0) do not necessarily coincide with SE even in simple conexv- max-max Stackelberg games [35].
As GDA fails in these games, Goktas and Greenwald [33] de- veloped nested GDA, nested first-order method for computing an 8)-EE, which solves the in- ner maximization problem by run- ning GDA on w.r.t. y and X over constraint sets y and R4 until convergence to a 8-saddle point (ū, A). Then, exploiting the convexity of the marginal function f", the algorithm runs descent step on f w.r.t x. in which, for any leader action X. a subgradient V., approximated by (x)
Algorithm Saddlle-PinntOracee SGD/Nested SGDA
Inputs: X. F, G,F, F, 9, (0), Tm {1T Jr, (+ for nested SGDA:) A, y (0)) X Ty. (nb (t) }r
(1(()
Outputs: (t A (z
Tu
1: for t 0............. . Ta do
2: if Saddle- Point- Oracle SGD then
3: Find (t) (1) y Rd s.t.
4:
max (g) (0)) min fly, x()) S AERd
yEY
5: Nested SGDA then
6: for O,..., Ty do
7:
Sample 0 ~ F, g y ((++1) Hl (0) 1a
(z) V [(g X(() (0.00.000000 ④)
8:
( x; In this paper, we replace the exact first-order ora- cle used by nested GDA with stochastic one, the gradient de- scent step with step of stochastic gradient descent (SGD), and GDA with stochastic GDA (SGDA), us- ing in both cases the stochastic Lagrangian oracle Σ. We call our method nested stochaste gradient descent ascent (nested SGDA).
9:
X ((++1) II \()) 1/
(5) V 2(y X (1) 20 0)
10:
Average iterates (g X (t) + ( X
11: Sample 0 ~ F. Φ
12:
x (++1) 1Ix x( -me
(t) V. (z) (0)) 0, 0,
13:
return (I y (Tm), A (Ta))
5

---

We begin by presenting saddle-point-orace stochastic gradient descent algorithm (saddle-poing oracle SGD, Algorithm 1), whose analysis we build on to develop our primary contribution, nested SGDA. Following Goktas and Greenwald's [33] max-oracle gradient descent algorithm, saddle-point- oracle SGD runs SGD on f" assuming access to an oracle, which, for any leader action a E X, returns a 8-saddle point of (y, A) - E(y, X; a)). Our second algorithm, nested stochastic gradient descent ascent (nested SGDA, Algorithm 1), follows the same logic as
SGD, but implements the saddle-point oracle by running SGDA. The following theorem establishes conditions under which both of our algorithms converge to an (e + ó, 6)-SE in a number of oracle calls that is polynomial in 1/e and 1/a.²
Theorem 3.1. Let (X.Y.f. f.g) be a convex-concave min-max Stackelberg game for which Assump- tion 3 holds. For any E, 2 if nested SGDA (resp. sudle--piit--on that satisfy for all t E &N+, (t) (t)
SGD) run with inputs T1 E @ and outputs (x', y , ;')), then in expectation over all runs of the algorithm (i.e., sample paths of 0 and Φ). the action profile (x*, .y") is an (E + 5, 63-SE after 0()22)) (resp. 0(1/2)) oracle calls. If, in addition, f c-stronglyyconvex. then (ax,, . y²) is an (c + 6, 6)E after (1fe6)) (resp. ((f/c) oracle calls.
4 Policy Gradient in Convex-Concal Zero-Sum Markov Stackelberg Games
In this section, we reduce the computation of Stackelberg equilibrium in zero-sum Markov Stackelberg games to a coupled min-max optimization problem, which enables us to derive a policy gradient method for these games based on our nested SGDA algorithm.
We consider zero-sum Markov Stackelberg games M = (I, n. m, S, A, pu, 7) with state space S C IR and action spaces A C I- and B c I for the leader and follower, respectively, where the follower's actions are constrained by the leader's via vector-valued state-dependent coupling
constraints g : -S I x Rm + Rdd s.t. that define a correspondence C(s, a) = {b E B g(s,a, as,aa.b b) 2 0}. We define the set of states with non-trivially coupled constraints N - {s E S
b) < 0). A Markov policy for the leader (resp. for short is one that is history independent, and thus mapping from states to actions T S - A (resp. T. : S + B). A policy profile π (T nT)) E AS x BS is a tuple comprising policies for the leader and follower, respectively. The follower's feasible policy correspondence is given by 2(Ta) n S - B Vs E g(s, (+)) 2 0}.
3(a. b) E
B, g ...)..))
hereaffte policy
A continuous action zero-sum sum Markov Stackelberg game is game where 1. for all states s E S, the reward function (a. b) + r(s, a, b) continuous and bounded, i.e., [|r S Tmmxx < oc, for some r maax E R+: 2. the action spaces A and B are non-empty and compact; and 3. for all states 8 E S, the correspondence a B C(s, a) is continuous, non-empty-, and compact-valued. A continuous state zero-sum Markov Stackelberg game is game where S is non-empty and compact and 2. the reward function r is continuous and bounded, i.e., ||rl < cc.
A history h E (S x A x B) of length т E N is sequence of state-action tuples h = (slt), a!),, ((1)),())) Given a policy profile π and a history of play h of length T, we define the discounted history distribution as (h) stt), al",b()))) I policy π HT, = supp(u=.T). ie.. the set of all histories that occur with non-zero probability. For convenience, we denote by i = =,,,000 and by H = (tt) B()),, any randomly sampled his- tory from 'TTH Finally, we define the discounted state-visitation distribution under any initial state dis- tribution μ as 5% (s) Die EnErT -st (() 11 s*(((s(k)) s (kk-1), ((k--)).
u(s(0) IT= ('p(s(t+)) | b(O). Define the set of all realizable trajectories :T of length 7 under
Given policy profile π. the istate-Jvalue fanction n.'h 8 -> IR and the action-value function 9T Sx Ax x B + R are defined in terms of n T (s) = EH | - r (S(t), A BB()) (()) = s] and qTT (s.a.b) = En |Et= T (S(t), A ())) St() = s, A = a, (0) = bj respec- tively. The cumulative payoff function u : A x B + R is then defined in terms of the value function as u( TT,) Es- [u* (5)), i.e., the total expected loss (resp. gain) of the leader (resp.
(()),
$ Wee include detailed theorem statements and proofs the full version of the paper. A should be chosen as superset of all optimal KKT multipliers, ie., U C A (see Appendix C).

---

follower). Additionally, the marginal action-value function (s. a) = maXpeC(s.a) 9" (s, a, b) is the payoff when play initiates at state with the leader taking action a, after which the follower best responds (at state 8 only), with both players playing according to a thereafter. Finally, for any leader policy a E AA, we define the marginal (state-value) function u² (Ta) ) = maxm, E2(m,) "(
Tt).
Recursive Stackelberg Equilibrium. A policy protile x = (Ta TT) E A x B is called an (e, 6)- recursive (or Markov perfect) Stackelberg equilibrium iff Vs E S, |[Tp (g(s, TT" (s)]] S ó and ( .Tb) (8)-ô S vx (s) I min EAS m v (T =bb (s) +E. A recursive SE is guaranteed to exist in continuous state, continuous action zero-sum Markov Stackelberg games [36]. A policy profile π = (T TT)) E A x Z(T2) is called an (E, Marakoov perfect GNE iff vs E S, max,, E.(T..) (T = (s) 5 " (s) S min EAA V "T (": +
Convex-Concave Markov Stackelberg Games. As we have shown (Theorem 3.1). Stackelberg equilibria can be computed in polynomial time in convex-concave min-max Stackelberg games, assuming access to an unbiased first order-stochastic oracle. We now define an analogous class of Markov Stackelberg games, namely zero-sum Markov Stackelberg games in which the min-max Stackelberg game played at each state is convex-concave. A conver-concave zero-sum Markov Stackelberg game is a continuous state, continuous action zero-sum Markov game where, for all policy profiles π E A x BS, I. the marginal action-value function (s. a) + qaa (s, a) is convex, 2. the action-value function (s, b) + q= a,b) is concave, for all 3. the state and action spaces S, .A and B are convex, and 4. the action correspondence C is convex-valued We note that any continuous state, continuous action convex-concave zero-sum Markov game, i.e., 1. . = 2. (s. a) + r r(s, a. b) is convex, for all b E B. 3. (s. b) + r(s, a, b) is concave, for all a E A. (8, + p(- 8, b), is stochastically convex, for all E B; and 5. (8. b) + p(- 8, a, b) is stochastically concave, for all a E A. is a convex-concave zero-sum Markov Stackelberg game for which the set of Markov perfect generalized Nash equilibria a subset of the recursive SE.
As our plan is to use our nested SGDA algorithm to compute recursive Stackelberg equilibria, we begin by showing that zero-sum Markov Stackelberg games are an instance of min-max Stackelberg games. Assume parametric policy classes for the leader and follower, respectively, namely Px {TT= S 15-+4 x E E C A and Py- { S B y E y) S B for param- eter spaces X' C I2d and y C TRd. Using these parameterizations, we redefine v(æ.9) - (
(( = ( ) u( y) = u( Tyy), etc., and thus restate the problem of computing recur- sive SE as finding (æ, y) E X'x y that solves min maxy
(ff for all states s e S. As this optimization problem is infinite dimensional for continuous state games, we optimize the objective and satisfy the constraints, both in expectation over the initial state distribution μ. thereby reducing the problem to the min-max Stackelberg game min ex maxye (m)) u),
In Appendix D. assuming 1. biaffine parametric policy classes, i.c., (s, x) + n (s) and (s. y) + Ty (8) are biaffine, and 2. non-empty, compact, and convex parameter spaces X' and V, we show that the min-max Stackelberg game associated with any convex-concave zero-sum Markov Stackelberg game is also convex-concave (Lemma 4). We also provide sufficient conditions on the primitives M of any zero-sum Markov Stackelberg game to ensure that it is convex-concanl (Lemma 5 and 6). At a high level, our results allow us conclude that a zero-sum Markov Stackelberg game is convex-comcave if the 1. reward (resp. transition probability) function is concave (resp. stochastically concave) in the state and the follower's action; 2. the reward (resp. transition probability) function is convex (resp. stochastically convex) in the state and the leader's follower's 's actions; and 3. the follower's action correspondence is concave.
Computation. We now turn our attention to the computation of recursive SE in convex-concave zero-sum Markov Stackelberg games. Mirroring the steps by which policy gradient has been show to converge in other settings [24], we first define an unbiased first-order stochastic oracle for zero-sum Markov-Stackelleer games, given access to an unbiased first-order stochastic oracle for the reward and probability transition functions. We then establish convergence of nested SGDA in this setting by invoking Theorem 3.1 under the following assumptions.
Assumption 4 (Convergence Assumptions). The parameter spaces X and y are non-empty, compact, and convex; 2. the policy parameterizations are biaffine, i.e., (s, x) + na (s) and (s,y) Try (8)()) are biaffine; 3. the set of non-trivially constrained sets is finite N, i.e. ||]]| co;
7

---

4. (Slater's condition) for all s E N and a E A. there exists b E reward r. probability transition p. and coupling constraint g functions are tipschitz-contimonn
B
s.t. g a. 6) > 0; and 5. the
Stochastic nested GDA relies can use to obtain unbiased first-order stochastic estimators of u and g. Since the constraints are deterministic, we simply set G(æ,, 8) = (g(s, n. (8),
unbiased first-order stochastic oracle (F, F.F. which
(s))))es and ((s) - p(s), for any Ty (
distribution E (S)) over the state space to obtain an unbiased first-order stochastic oracle for the constraints 9. While for simplicity we define G as such, G is tractable to compute (i.e., finite- dimensional) only when A is finite. When N is infinite, our theoretical results generalize by setting (ar 8) = (min.ex (s Th (s): Ty (8) [e]]): however, in practice, this estimator might be intractable, in which case one might choose to abandon our theoretical guarantees in favor of the biased estimator (zz y; 8) = g(s, n (8), ) Ty (s)). In all cases, the definition of V ((..v) follows directly, since G is deterministic. Now, for any history h of length т, define the cumulative payoff estimator R(T: h) = ET ((s(0)) I[ 7 (*p(s((++))) s(t), π )r(ss ())))))). We then construct an estimator for u using uusingfirst-ore first-order gradient estimator [69], i.e., we set F(xx, y; h; = R(TT= Ty: h.), and V ( Fxx y: h) V (x.,)) Tyi ht). Regarding the variances of this oracle model, as G and V (Iz G are deterministic, they have bounded variance. Moreover, if the policy and the reward and transition probability functions are Lipschitz-comtimuuus, then R and V (aa.y) R are also Lipschitz-continuuus if their domains are compact (i.e., if S, A, and B are compact). Hence F and F likewise must be Lipschitz-comtimuous, which implies that their variances must be bounded, e.g., there exists 5 E I s.t. E. III y; h))? < | F(z y; h ) = σ where the middle expression is well-defined since v F Lipschitz-
over its compact domain.
With all of this machinery in place, we can now extend nested SGDA to compute recursive Stackelberg equilibria in zero-sum Markov Stackelberg games (Algorithm Appendix C). In the usual case, when the policy parameterization does not represent the space of all policies A x BS, this result should be understood as convergence the recursive Stackelberg equilibria of a game in which the players' action spaces are restricted to the parameterized policies.
Theorem 4.1. Let M be a convex-concave zero-sum Markov Stackelberg game. Under Assumption for any e, 8 Z O, if nested policy gradient descent ascent (Algorithm 2, Appendix C) is run with imputs that satisfy for all over all runs of the algorithm (i.e., sample paths of a and Φ). the policy profile ( Tyy) is an
(t) (t) O (1/v4I), and outputs (x* .y" x²), then in expectation N+. na The
(e + recuusvve SE after 0(1/23) oracle calls.
5 Application: Reach-Avoid Problems
In this section, we endeavor to apply our algorithms to a real-world application, namely reach-avoid problems. In reach-avoid problem (e.g.. [29, 32]), an agent seeks to reach one of a set of targets- achieve liveness- while avoiding obstacles along the way- have myriad applications, including network consensus problems [42], motion planning [21, 41], pursuit-evasion games [30, 44], autonomous driving [43], and path planning [80], to name a few.
safety. Reach-avoid problems
The obstacles in reach-avoid problem are not necessary stationary; they may move, either randomly or deliberately, around the environment. When the obstacles' movement random, the problem can be modeled as MDP. But when their movement is deliberate, so that they are more like rational opponent than a stochastic process, the problem is naturally modeled as a zero-sum game, where the agent-the the protagonist-aie aims reach its target, while an wraggonnstt-epreseeettt obstacles-see to prevent the protagonist from doing so. Past work has modeled these games as simultancous-move (c.g.. [29], [32]). imposing what should be hard constraint thht the agent cannot collide with any of the obstacles as a soft constraint in the form of large negative rewards.
the
Using the framework of zero-sum Markov Stackelberg games, we model this hard constraint properly. with the leader as the antagonist, whose movements impose constraints on the moves of the follower, the protagonist. We then use nested policy GDA to compute Stackelberg equilibria and simultaneous SGDA to compute GNE, and show experimentally that the protagonist learns stronger policies the sequential (i.c., Stackelberg) game than in the simultancous.
8

---

A (discrete-timg discounted anfinit-hhorizon continuous state and action) reach-avoid game (1, V. A. B, p.r, r.r.)))))))) h)) comprises two players, the antagonist (or a playeer) and the protagonist (or b-player), each of whom occupies state Sa Sb E S in a state space & C R', for some / E N. The protagonist's goal is to find path through the safe set C S x S that reaches a state in the target set Tc V. while steering clear of the avoid set V = S x S \ V. This safe and avoid set formulation is intended to represent capture constraints, which have been the focus of the reach-avoid literature [80].
Initially, the players occupy some state s00) μ E (VV) drawn from an initial joint distribution over all states, excluding the target and avoid sets. At each subsequent time-step & E N+, the antagonist (resp. protagonist) chooses (*) E AA (resp. b(t) E B) from a set of possible directions A S IR' (resp. B C R') in which to move. After both the antagonist and the protagonist move, they receive respective rewards -r(s((), al!), b(t)) and r r(s(t), a (t)), b(()). Then, either the game ends, with probability 1 7. for some discount rate y E (0. 1), or the players move to new state g(t++) = h(* a. b) = ha (saa),
(t) a), ho (s} b) as determined by their respective displace-
ment functions ha SSx x A + S and hs S x B + S. We can express this deterministic transition as the following probability transition function p(s' 8, a b) (h, a, b)).
We define the feasible action correspondence C(s, a) = (b B a a. b) 0} via vector- valued safety constraint function a: S S x S - Rd. which outputs subset of the protagonist's actions in the safe set, i.c., for all (8, a) E S x A, C(s,a) S {6 E B h b) E V}. Note that we do not require this inclusion to hold with equality; in this way, the protagonist can choose to restrict itself to actions far from the boundaries of the avoid set, thereby increasing its safety, albeit perhaps at the cost of liveness. Overloading notation, we define the feasible policy correspondence C ( = ( S + B T (8) E C(8, T (s)), for all & E S).
We consider two forms of reward functions. The first, called the reach probability reward, (s,a,b) = 17(5,), is indicator function that awards the protagonist with payoff of 1 if it enters the target set, and 0 otherwise. Under this reward function, the cumulative payoff function (i.e., the expected value of these rewards in the long term) represents the probability that the protag- onist reaches the target, hence its name. The second reward function is the reach distance reward function, r(s, a, b) = min - s'1??, which penalizes the protagonist based on how far away it is from the target set. With all these definitions in hand, we can now cast the reach-avoid game zero-sum Markov Stackelberg game (21, d, A, B, r, P.
The next assumption ensures that 1. under the reach probability reward function, a reach-avoid game is a convex-non-concaa zero-sum Markov Stackelberg game (i.c., the marginal function æ -> u² (x) is convex, and the cumulative payoff function y + u x, y) is non-concave, for all x E 2); and 2. under the reach distance reward function, reach-avoid game is convex-concave zero-sum Markov Stackelberg game. Furthermore, a Markov perfect GNE is guaranteed to exist under this assumption, assuming the reach distance reward but not under the reach probability distance." 10
To state this assumption, for convenience, we model the leader's policy T (8) = x8 as parameter- ized by æ E X C ! and the follower's policy T (s) = ys, as parameterized by E ) C | Note also that we assume decentralized, play, meaning the players learn only from their own state and rewards, and maintain their policies independently of one another.
Assumption 5 (Convex-Concave Reach-Avoid Game). 1. The state space S and the target set T are non-emply and convex; 2. the action spaces A, B are non-emply, compact and convex; 3. the displacement functions ha hy are affine; 4. a + a(s, a, is log-convex for all b E B, and b - asss, a. b) for all (s, a) E S x A; 5. the players' parameter spaces X and y non-empty, compact, and convex; and 6. the players policies are biaffine, i.e., n (s) = xx and n. (s) = xs,-
Part is a standard assumption commonly imposed on reach-avoid games (see, for instance Fisac al. [29]). Part 3 is satisfied by natural displacement functions of the type h(s, a, b) + B(a, b). for some 3 E R. which is a natural characterization of all displacement functions with constant | = 1). Part 4 is satisfied by various action correspondences. such as ax,s, a, b) = exp( mii V (ha (s.. a), s,) - s' - 1 - ho (5, s,. b) s,ll. which shrinks
velocity B. when A B C {z S
"he existence of Markov perfect GNE, and hence GNE, is guaranteed by straightforward generalization of Shapley's 's [65] result the existence of Markov perfect Nash equilibria in zero-sum Markov games.
9

---

the space of actions exponentially as the protagonist approaches the antagonist, and can thus be interpreted as describing a safety-conscious protagonist. The following theorem states the convex- concavity properties of reach-avoid games, and shows polynomial-tine computability of recursive SE under Assumption 5. Note that for the reach probability reward function, is not possible to obtain a polynomial-time convergence result, result since the rewards are not even continuous.
Theorem 5.1. Under the reach distance (resp. reach probability) reward function, any reach-avoid game for which Assumption 5 hold is convex-concave (resp. convex-non-concvve Moreover, a is musccitz-continuuu. then nested SGDA is guaranteed to converge in such games to recursive SE policies in polynomial time.
Experiments. We ran a series of experiments on reach-avoid problems," !l which were designed to assess the efficacy of policies learned in a Stackelberg game formulation compared to those learned in a simultancous-move game formulation, assuming complex, i.c., neural, policy parameterizations.
We consider a variant of the two-player differential game introduced in Isaacs [38], played by two Dubins cars. A Dubins car is a simplified model of a vehicle with a constant forward speed v and a constrained turning radius w. We model both the protagonist and antagonist as Dubins cars [38] moving around 2-dimensional state space. The target set is select subset of the state space, while the avoid set, which defines the safe set, is ball around the antagonist.
We experiment with only the reach distance, not the reach probability, reward function. In all safe states, the reward is actually a penalty, measuring the protagonist's distance to the target set, while bonus awarded upon reaching target, which point the game ends. This reward function suffices for our Stackelberg game setup, which enforces the hard constraint that the protagonist cannot move into the avoid set. In our simultancous-move game setup, we achieve a similar effect by enhancing the aforementioned reward function with a large penalty (-3) whenever the protagonist touches the avoid set. As in the case of reaching the target, touching the avoid set ends the game,
We note that this reach-avoid game is not actually a continuous game, as there is a discontinuity in the reward function when the target is reached. Additionally, it is possible for the antagonist to be "cornered," " meaning left with an empty set of feasible actions (in which case the game ends). For these reasons, recursive SE are not guaranteed to exist in our setup.
Our experiments were run on a 7x7 square grid, with the target set Ta closed ball of radius centered along the lower edge, and the avoid set V a closed ball of radius 0.3 around the antagonist. We set the bonus (resp. penalty) for reaching the target (resp. avoid set) 8 = 200, = 30 and v = 0.25.
Using this experimental setup, train two agents by playing two games, the Stackelberg and simultaneous-move variants of the reach-avoid game, using nested policy GDA and SGDA, respec- tively. We evaluate the protagonists' policies to assess their safety and liveness characteristics.
To assess liveness, we ran our agents against an opponent
Match-up
Outcome
Mean win length
Loss/draw length
GNE random
47 W, 18 L,, 35
23.23
7.53
33.71 19.31
SE vs. random
95 W, 2 L, DD
18.16 1 3.69 N/A
33.0 1 20.8
that plays actions
sampled uniformly random. To assess safety, we ran our agents against opponent who chases them, always taking actions that minimize their distance. Table I reports the number of wins (W), losses (L), and draws (D), and average game lengths, of 100 games against each opponent. An agent, playing the role of the protagonist, wins when it reaches the target set. A GNE agent loses if it enters V, while a Stackelberg agent loses if it finds itself cornered. The game is a draw if neither player wins or loses within 50 time steps.
GNE vs. chaser
0 W. 100 L. O
8.53 1 1.90
SE vs. chaser
63 W, 361.,, DD
21.63 + 5.04
11.06 + 7.71
Table 1: Game results summary for GNE and SE agents.
We find that the SE agent outperforms the GNE agent by a large margin. The SE agent wins almost all of its games against random, and roughly 7/3 of its games against the chaser, while the GNE agent wins only half of its games against random, and none of its games against the chaser. Moreover, even when the SE agent loses draws, it tends to stay alive longer than the GNE agent. Not only does our Stackelberg approach outperform GNE, it is tractable as well. Our methods thus seem to offer a promising path to further progress solving the myriad of robotic applications of reach-avoid.
II Our code found at: ht :/t:://g/iii /ttpttbb..btt///////////.tt... com/ jun- wtwp:/asssssttteeeaaeeeeee wwwckteeeceeeeeeeeeee reachr-vvirccc-.iidd
10

---

Acknowledgments
Denizalp Goktas was supported by JP Morgan Al fellowship. Arjun Prakash was partially supported by ONR N00014-22-1-2592 and the Quad Fellowship.
References
[1] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. Optimality and approxi- mation with policy gradient methods in markov decision processes. In Conference Learning Theory, pages 64-66. PMLR, 2020. 26
[2] Alckh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. 22(1), jan 2021. ISSN 1532-4435. 1, 26
[3] Eitan Altman. Flow control using the theory of zero sum markov games. IEEE transactions on automatic control, 39(4):8144 818, 1994. 1
[4] Kenneth Arrow and Gerard Debreu. Existence of equilibrium for competitive economy. Econometrica: Journal of the Econometric Society, pages 265-290, 1954.
[5] Kenneth J. Arrow and Leonid Hurwicz. On the stability of the competitive equilibrium,
i. Econometrica, 26(4):522 552, 1958. ISSN 00129682, 14680262. URL http: /www.
sstor.org/stabble/997733
[6] Kenneth Joseph Arrow, Leonid Hurwicz, and Hirofumi Uzawa. Studies in linear and non-linear
programming. 1958. 5
[7] Alp E. Atakan. Stochastic convexity in dynamic programming. Economic Theory, 22(2): 447-455, 2003. ISSN 09382259, 14320479. URL http:://tt//t http://www.....tooooo//.o www.jjstorrrr... stable/
25055693. 3, 26
[8] Yu Bai, Chi Jin, Huan Wang, and Caiming Xiong, Sample-efticient learning of stackelberg equilibria in general-sum games. Advances in Neural Information Processing Systems, 34: 25799-25811 1,, 2021. 16
[9] Stefan Banach. Sur les operations dans les ensembles abstraits et leur application aux equations integrales. Fund. math, 3(1):133-118) 1922. 25
[10] Somil Bansal, Mo Chen, Sylvia Herbert, and Claire Tomlin. Hamilton-jacobi reachability: A brief overview and recent advances. In 2017 IEEE 56th Annual Conference Decision and Control (CDC), pages 2242-2253. IEEE, 2017. 2
[11] Richard Bellman. On the theory of dynamic programming. Proceedings of the National Academy of Sciences of the United States America, 38(8):716, 1952. 24, 25
[12] Alain Bensoussan, Shaokuan Chen, and Suresh P Sethi. The maximum principle for global so- lutions of stochastic stackelberg differential games. SIAM Journal on Control and Optimization, 53(4):1956-198) 1981, 2015. 16
[13] Dimitri Bertsekas. Convex optimization theory, volume 1. Athena Scientific, 2009. 4
[14] Dimitri Bertsekas. Dynamic programming and optimal control: Volume I, volume Athena
scientific, 2012. 24
[15] Dimitris Bertsimas, David B Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464-501 2011.
[16] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv: 00066.0076.... 2019. 1
[17] Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[18] Steven J Bradtke and Andrew G Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22:33-57, 1996. 24
[19] Yanling Chang, Alan Erera, and Chelsea White. leader-follower partially observed, multiobjective markov game, Annals of Operations Research, 235(1):103-128, 2015. 16

---

[20] Ly Chen and Yang Shen. On new paradigm of optimal reinsurance: stochastic stackelberg differential game between an insurer and a reinsurer. ASTIN Bulletin: The Journal of the IAA, 48(2):905-96)) 2018. 16
[21] Mo Chen, Zhengyuan Zhou, and Claire J Tomlin. Multiplayer reach-avoid games via low dimensional solutions and maximum matching. In 2014 American control conference, pages 1444-1444 1449. IEFE, 2014. 8
[22] Stefan Czerwik. Functional equations and inequalities in several variables. World Scientific, 2002. 3, 4
[23] John M. Danskin. The theory of max-min, with applications. SIAM Journal on Applied Mathematics, 14(4):641-664, 1966. ISSN 00361399. URL http: httt:://ww... jswor. org/ stable/294611
[24] Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020. 7,7
[25] Victor DeMiguel and Huifu Xu. stochastic multiple-leader stackelberg model: analysis, computation, and application. Operations Research, 57(5):1220-132 1235, 2009. 16
[26] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International conference on machine learning, pages 1467-1476. PMLR, 2018. 24
[27] Anthony V Fiacco and Jerzy Kyparisis. Convexity and concavity properties of the optimal value function in parametric nonlinear programming. Journal of optimization theory and applications, 48(1):95-126,, 1986. 19, 25
[28] Arlington M Fink. Equilibrium in stochastic n-person game. Journal of science of the hiroshima university, series ai (mathematics), 28(1) 28(1):89-88) 1389993,1111 1964.
[29] Jaime F. Fisac, Mo Chen, Claire J. Tomlin, and S. Shankar Sastry. Reach-avoid problems with varying dynamics, targets and constraints. In Proceedings of the 18th International Conference on Hybrid Systems: Computation and Control, HSCC '15, page 11-20, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450334334, doi: 10. 2,.145//728600.2228666 2, 8.9
11..0...111110 2111114//2222662222 URL https: / 0tt.o/.orgg/...11/27888333333310
[30] James Flynn. Lion and man: the general case. SIAM Journal Control, 12(4):581-597, 1974. 8
[31] David Fridovich-Kan Keill Ellis Ratner, Lasse Peters, Anca D Dragan, and Claire J Tomlin, Efficient iterative quadratic approximations for nonlinear multi-player general-sum differential games. In 2020 IEEE international conference on robotics and automation (ICRA), pages 1475-1481. JEEE, 2020. 1
[32] Yan Gao, John Lygeros, and Mare Quincampoix. On the reachability problem for uncertain hybrid systems. IEEE Transactions on Automatic Control, 52(9):157--1586 2007. 8
[33] Denizalp Goktas and Amy Greenwald. Convex-concave min-max stackelberg games. Advances in Neural Information Processing Systems, 34, 2021. 2, 3, 4, 5, 6, 16, 20
[34] Denizalp Goktas and Amy Greenwald. Robust no-regret learning in min-max Stackelberg games, 2022. 16
[35] Denizalp Goktas and Amy Greenwald. Gradient descent ascent in min-max stackelberg games. arXiv preprint arXiv:2208.0960 09699, 2022. 5
[36] Denizalp Goktas, Sadie Zhao, and Amy Greenwald. Zero-sum stochastic stackelberg games. Advances in Neural Information Processing Systems, 35:1 15:11658-11672 2022. 1, 7, 16
[37] Xiuli He, Ashutosh Prasad, and Suresh P Sethi. Cooperative advertising and pricing in dynamic stochastic supply chain: Feedback stackelberg strategies. In PICMET 2002000 Portland International Conference on Management of Engineering and Technology, pages 1634-1649. IEEE, 2008 16
[38] Rufus Isaaes. Differential Games I: Introduction. RAND Corporation, Santa Monica, CA, 1954.
10
12

---

[39] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020. 24
[40] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning.
In Proceedings of the Nineteenth International Conference on Machine Learning, pages 267- 274, 2002. 26
[41] Sertac Karaman and Emilio Frazzoli. Sampling- cumpling-based algorithms for optimal motion planning. The international journal of robotics research, 30(7):846-894, 2011. 8
[42] Ali Khanafer, Behrouz Touri, and Tamer Basar. Robust distributed averaging on networks with adversarial intervention. In 52nd IEEE Conference on Decision and Control, pages 7131-7136.
IEEE, 2013. 8
[43] Karen Leung, Sushant Veer, Edward Schmerling, and Marco Pavone. Learning autonomous vehicle safety concepts from demonstrations. arXiv preprint urXiv:2210.02761, 2022. 2, 8
[44] J Lewin. The lion and man problem revisited. Journal of optimization theory and applications, 49:411 1-430, 1986.
[45] Tao Li and Suresh P Sethi. A review of dynamic stackelberg game models. Discrete and Continuous Dynamical Systems-B, BB, 22(1): 2017. 16
[46] Michael Littman. Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the Eleventh International Conference on International Conference Machine Learning. ICML' 94, page 157-163, San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc. ISBN 1558603352.
[47] Songtao Lu, Joannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications. IEEE Transactions Signal Processing, 68:3676-3691, 2020. doi: 10.1109/TSP.2000.99888 29886663...996..... 4
2020.
[48] Kostas Margellos and John Lygeros. Hamilton-Jacobi Formulation for Games. IEEE Transactions on Automatic Control, 5669)::849-1161,
Differential August 2011. ISSN 1558-
2523. doi:
[49] Eric Maskin and Jean Tirole. Markov perfect equilibrium: I. observable actions. Journal of Economic Theory, 100(2):191-219, 2001.
[50] Francisco S Melo and M Isabel Ribeiro. Q-learning with linear function approximation. In International Conference on Computational Learning Theory, pages 308-322 Springer, 2007.
24
[51] Ashkan Mohammadi. Penalty methods to compute stationary solutions for constrained opti- mization problems. arXiv preprint arXiv:2206. 04020, 2022. 19
[52] Ashkan Mohammadi, Boris S Mordukhovich, and M Ebrahim Sarabi. Variational analysis of composite models with applications continuous optimization. Mathematics of Operations Research, 47(1):397-426, 2022. 19
[53] John F. Nash. Equilibrium points in <i>n</i>-person games. Proceedings of the National Academy of Sciences, 36(1 4:44-49, 1950. doi: 10. N0.1073/pmaa.36.1.45 URL https: /www.
pnas.ors doi abs / 0. 1073 /pp///aas..e. 3............... 1.88.
[54] Angelia Nedić and Asuman Ozdaglar. Approximate primal solutions and rate analysis for dual subgradient methods. SIAM Journal Optimization, 1777)1757 2009. 19
[55] Angelia Nedic and Asuman Ozdaglar. Subgradient methods for saddle-poin problems. Journal of optimization theory and applicationss 142(():205-22) 200,5-2282220 2009. 19
[56] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal optimization, 19(4): 1574-1609, 2009. 20
[57] Kazimierz Nikodem. K-convex and K-concave set-valued functions. functioons Wydawnietwo Politechniki Lodzkiej, 1989. 3.4
[58] Bernt Oksendal, Leif Sandal, and Jan Uboe. Stochastic stackelberg equilibria with applications to time-dependent newsvendor models. Journal of Economic Dynamics and Control, 37(7):
I 1284-1299, 2013, 16
13

---

[59] Praveen Palanisamy. Multi-agess agent connected autonomous driving using deep reinforcement learning. In 2020 International Joint Conference on Neural Networks (IJCNN), pages 1-7.
IEEE, 2020.
[60] Matteo Papini, Damiano Binaghi, Giuseppe Canonaco, Matteo Pirotta, and Marcello Restelli. Stochastic variance-reducee policy gradient. In International conference on machine learning, pages 4026-4035. PMLR, 2018. 26
[61] Giorgia Ramponi and Marcello Restelli. Learning in markov games: can we exploit general- sum opponent? In The 38th Conference on Uncertainty in Artificial Intelligence, 2022. 16
[62] Sean C Rismiller, Jonathan Cagan, and Christopher McComb. Stochastic stackelberg games for agent-driven robust design. International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, volume 84003, page AILATIAA33 American Society of Mechanical Engineers, 2020. 16
[63] Tyrrell Rockafellar and Roger J-B Wets. Variational analysis, volume 317. Springer Science
and Business Media, 2009. 3, 4
[64] Sailik Sengupta and Subbarao Kambhampati. Multi-agent reinforcement learning in bayesian stackelberg markov games for adaptive moving target defense. arXiv preprint Stti:2000.10455:
2020. 16
[65] Lloyd S Shapley, Stochastic games. Proceedings of the national academy of sciences, 39(1)):
1095-1 100, 1953. 1.9
[66] Zebang Shen, Alejandro Ribeiro, Hamed Hassani, Hui Qian, and Chao Mi. Hessian aided policy gradient. In International conference on machine learning, pages 5729-5738. PMLR, 2019. 26
[67] Maurice Sion. On general minimax theorems. Pacific Journal of mathematics, 8(1):171-176,
1958. 4
[68] Morton Slater. Lagrange multipliers revisited. Cowles Foundation Discussion Papers 80,
Cowles Foundation for Research in Economics, Yale University, 1959. URL https://
EconPapers repec. org/ RePEc cwl cwldpp: 80.
[69] Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake. Do differentiable simulators give better policy gradients? In International Conference on Machine Learning, pages 20668- 20696. PMLR, 2022.
[70] Masayuki Takahashi. Equilibrium points of stochastic non-cooperative n-person games. Journal of Science of the Hiroshima University, Series Al (Mathematics), 28(1):95-99) 999 1964.
[71] Ioannis Tsaknakis, Mingyi Hong, and Shuzhong Zhang. Minimax problems with coupled linear constraints: Computational complexity, duality and solution methods. arXiv preprint
arXiv:2110.11210. 2021. 4
[72] Deepanshu Vasal. Stochastic stackelberg games, 2020. 16
[73] John von Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1): 295-320, 1928. 4
[74] Heinrich von Stackelberg. Marktform und gleichgewicht. J. springer, 1934.
[75] Yevgeniy Vorobeychik and Satinder Singh. Computing stackelberg equilibria in discounted stochastic games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26,
pages 1478-1484, 2012. 16
[76] Quoc-Liem Vu, Zane Alumbaugh, Ryan Ching, Quanchen Ding, Arnav Mahajan, Benjamin Chasnov, Sam Burden, and Lillian J Ratliff. Stackelberg policy gradient: Evaluating the performance of leaders and followers. In ICLR 2022 Workshop Ganification and Multiagent Solutions, 2022. 16
[77] Yuandou Wang, Hang Liu, Wanbo Zheng, Yunni Xia, Yawen Li, Peng Chen, Kunyin Guo, and Hong Xie. Multi-objective workflow scheduling with beep-q-network reinforcement learning. IEEE access, 7:39974-39998 2019.
multi-agent
[78] Yu Yuan, Zhibin Liang, and Xia Han. Robust reinsurance contract with asymmetric information in stochastic stackelberg differential game. Scandinavian Actuarial Journal, pages 1-28, 2021.
16
14

---

[79] Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Basar. Global convergence of policy gradient methods (almost) locally optimal policies. SIAM Journal on Control and Optimization, 58 (6):3586-3612, 2020. 26
[80] Zhengyuan Zhou, Jerry Ding, Haomiao Huang, Ryo Takei, and Claire Tomlin. Efficient path planning algorithms in reach-avoid problems. Automatica, 19,28-36, 2018. 8,
15


Reviews:
[{"review_id": "xFHydGfMvY", "reviewer": "Reviewer_gXac", "summary": "The paper considers the setting of convex-concave zero-sum stochastic Stackelberg games. In these games, there are two players, a leader and a follower. The leader's strategies constrain the feasible strategy set of the follower. First, the leader commits to a certain strategy, and then, the follower best-responds to that strategy using a strategy that is feasible.\n\nPrevious work mainly focuses on the static version of that game where the utility of the two players is monotone (convex-concave games). The authors define what is a convex-concave stochastic zero-sum stochastic Stackelberg game and then use some machinery from min-max optimization to solve the problem of computing a Stackelberg equilibrium.\n\n---\n\nI acknowledge that I have read and evaluated the rebuttal. The rebuttal answered my concerns and reinforced with my initial positive assessment.", "questions": "* Is the assumption of convexity-concavity necessary to prove convergence? Could some other assumption guarantee it?\n* Do you believe that the convergence rates are optimal? Could you use some other optimization method to get better rates?", "limitations": "* The main limitation in my opinion is the fact that convexity-concavity is assumed. I think the authors could elaborate more on the justification of such an assumption. (It could also be the case that this assumption is a necessity though.)", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The exposition of previous work and motivation is clear.\n* The paper uses standard methods and indicates a good understanding of the min-max optimization and constrained optimization literature.\n* The guarantees are for the stochastic setting (i.e., no full information gradient is needed.)", "weaknesses": "* Assumption on convexity concavity seems restrictive. Is there any other way to ensure the existence of Stackelberg equilibria AND convergence?\n* The results seem a little straightforward given the existing machinery in the literature of min-max optimization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n**Regarding the weaknesses.**\n\nBeyond convex-concave domains, convergence to a Stackelberg equilibrium unfortunately becomes NP-hard [1]. As global convergence guarantees to (recursive) Stackelberg equilibrium have not been obtained for more general zero-sum (stochastic) Stackelberg games under the assumption of a stochastic first-order oracle, we chose to restrict our attention to convex-concave domains.\n\nWe want to push back slightly on your comment that our results are straightforward. Although extensions of the convergence guarantees provided by Goktas et al. [2] to a setting with a stochastic first-order oracle may be straightforward, we want to note that our main contribution is regarding the convergence of nested policy gradient methods in zero-sum stochastic Stackelberg games, and their application to reach-avoid problems. Our results in this direction, make use of novel assumptions (based on the extensively studied notion of convex stochastic dominance) and proof techniques, to develop suitable assumptions under which zero-sum stochastic Stackelberg games can be shown to be convex-concave w.r.t. to the parameters of the leader and follower’s policy parameters, allowing us to obtain convergence to a recursive Stackelberg equilibrium. Our assumptions, proof techniques, and results open the door to proving the convergence of policy gradient methods in a new class of continuous state-discrete action space MDPs/Markov games.\n\nPerhaps more importantly, in Appendix C, we show that the well-established class of reach avoid problems [3] can be modeled as convex-concave zero-sum stochastic Stackelberg games (see Theorem C.1. in Appendix C). Using this characterization of reach-avoid problems, we are able to obtain novel polynomial-time solution methods for these problems, which, as we show in experiments, outperform known solutions/methods (i.e., Nash equilibrium).\n\n**Regarding your questions.**\n\nWe refer you to part (2) of our response to common reviewer concerns.\t\n\nWe believe that our convergence rates are “nearly” optimal, in the sense that, excluding the use of Nesterov’ momentum or other acceleration methods, our method is optimal. Our convergence rate could be improved by an order of magnitude by using acceleration, but to keep our paper accessible, e.g., to roboticists, and potentially be more impactful, we chose to not present such an algorithm. Additionally, we want to note that the nested nature of our algorithm is essential, because single loop algorithms cannot converge to Stackelberg equilibria in convex-concave zero-sum Stackelberg games with coupled/dependent action spaces (See Example 3.3 in [5]).\n\n\n**References**\n\n[1] Tsaknakis, Ioannis, Mingyi Hong, and Shuzhong Zhang. \"Minimax problems with coupled linear constraints: computational complexity, duality and solution methods.\" arXiv preprint arXiv:2110.11210 (2021).\n\n[2] Goktas, Denizalp, and Amy Greenwald. \"Convex-concave min-max stackelberg games.\" Advances in Neural Information Processing Systems 34 (2021): 2991-3003.\n\n[3] Jaime F. Fisac, Mo Chen, Claire J. Tomlin, and S. Shankar Sastry. Reach-avoid problems with time-varying dynamics, targets and constraints. In Proceedings of the 18th International\nConference on Hybrid Systems: Computation and Control, HSCC ’15, page 11–20, New York, NY, USA, 2015. Association for Computing Machinery\n\n[4] Badithela, Apurva, et al. \"Synthesizing reactive test environments for autonomous systems: testing reach-avoid specifications with multi-commodity flows.\" 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.\n\n[5] Goktas, Denizalp, and Amy Greenwald. \"Gradient Descent Ascent in Min-Max Stackelberg Games.\" arXiv preprint arXiv:2208.09690 (2022).\n\n\n"}, {"review_id": "hVLJmc6XOJ", "reviewer": "Reviewer_yZL6", "summary": "The authors propose a policy gradient method to solve the zero-sum stochastic Stackelberg game from noisy gradient estimates computed from observed trajectories of play. When the games are convex-concave, the authors prove that the proposed algorithms converge to Stackelberg equilibrium in polynomial time.", "questions": "See above.", "limitations": "See above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors have completed a thorough theoretical analysis of the proposed policy gradient method and prove it converges to Stackelberg equilibrium in polynomial time assuming the game is convex-concave.", "weaknesses": "1. The authors claim they solved the convex-concave zero-sum Stackelberg problem but also restrict the application to a reach-avoid problem. The authors mention that \"We also prove that reach-avoid problems are naturally modeled as convex-concave zero-sum stochastic Stackelberg games.\" in the abstract but in fact do not really PROVE it in the manuscript.\n\n2. Besides, as the author mentioned, the reach-avoid game is usually formulated as a single-agent problem and there exist some works formulating it as a two-player zero-sum game.  Why do the authors not address standard zero-sum problems like pricing or allocating goods across agents and time as in reference [25]? Experimenting merely on a reach-avoid game is not enough to demonstrate the effectiveness or superiority of the proposed approach compared to existing methods like Nash equilibrium.\n\n3. The authors make several critical assumptions like convex-concave, convergence assumptions, etc. How feasible these assumptions are in reality and how to validate them are missing. The authors should address these limitations and discuss potential extensions to more realistic scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n**Regarding the weaknesses.**\n\nWe did include a proof of reach-avoid games being an instance of convex-concave zero-sum stochastic Stackelberg games in Appendix C (see Theorem C.1. and the ensuing proof). However, it seems like we failed to add a forward reference to this theorem in the main body of the paper; we will correct this oversight in the camera-ready version. And in the meantime, we are happy to answer any questions you might have about this result, or its proof.\n\nThe reason why we do not use our algorithm to solve, for example, the zero-sum stochastic Stackelberg resource allocation game introduced in [1] is because that game is not convex-concave, and as such it lies beyond the scope of our theory and paper. We focused specifically on reach-avoid problems, as they *are* naturally convex-concave (Theorem C.1.).\n\nWe refer you to part (2) of our response to common reviewer concerns.\n\nWe do provide one simple way of validating the convex-concavity of games, which we use in Appendix C to prove the convex-concavity of reach-avoid problems. In particular, it suffices to check that the problem satisfies Assumption 2.\n\n**References**\n\n[1] Denizalp Goktas, Sadie Zhao, and Amy Greenwald. Zero-sum stochastic stackelberg games. Advances in Neural Information Processing Systems, 35:11658–11672, 2022 \n\n[2] Tsaknakis, Ioannis, Mingyi Hong, and Shuzhong Zhang. \"Minimax problems with coupled linear constraints: computational complexity, duality and solution methods.\" arXiv preprint arXiv:2110.11210 (2021).\n\n[3] Goktas, Denizalp, and Amy Greenwald. \"Convex-concave min-max stackelberg games.\" Advances in Neural Information Processing Systems 34 (2021): 2991-3003.\n\n[4] Jaime F. Fisac, Mo Chen, Claire J. Tomlin, and S. Shankar Sastry. Reach-avoid problems with time-varying dynamics, targets and constraints. In Proceedings of the 18th International\nConference on Hybrid Systems: Computation and Control, HSCC ’15, page 11–20, New York, NY, USA, 2015. Association for Computing Machinery\n\n[5] Badithela, Apurva, et al. \"Synthesizing reactive test environments for autonomous systems: testing reach-avoid specifications with multi-commodity flows.\" 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.\n"}, {"review_id": "nETVZceRPY", "reviewer": "Reviewer_sSzA", "summary": "This paper considers a convex-concave  min-max Stackelberg game and proposes algorithm which converges to the Stackelberg equilibrium. The paper also proposes a policy-gradient based mechanism which also converges to the Stackelberg equilibrium for the Markov game.", "questions": "1. The paper uses policy-gradient approach. However, it relies on the generator model where a state-action pair is drawn from the state-action occupancy measure? Is it practical? Further, the paper seems to work on continuous state-space. The convergence result is for finite state-space only, while limited results exist for function approximation setup (severely relies on the realizability assumption). However, this paper does not consider such. Does the policy-gradient algorithm have any convergence guarantee? Is the action-space also continuous? Standard policy-gradient does not work with the continuous action. \n\n2. Two-time scale approximations are usually employed for Stackelberg game to reduce the sample complexity. Can it be done in this case as well. For example, see the recent work [A2, A3]\n\n[A2]. Li, Haochuan, Farzan Farnia, Subhro Das, and Ali Jadbabaie. \"On convergence of gradient descent ascent: A tight local analysis.\" In International Conference on Machine Learning, pp. 12717-12740. PMLR, 2022.\n\n[A3]. Lin, Tianyi, Chi Jin, and Michael Jordan. \"On gradient descent ascent for nonconvex-concave minimax problems.\" In International Conference on Machine Learning, pp. 6083-6093. PMLR, 2020.\n\n3. Are Theorems 3.1 and 4.1 correct? In the averaging of $y$, why the numerators are multiplied by $\\eta_x$ instead of $\\eta_y$? I tried to find it in the proof, however, I could not. Can the authors point where it has been shown that the average is done over $y_t$?", "limitations": "Not as such.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Stackelberg game is an important problem in multi-agent setup and also for hyper-parameter tuning. Thus, this paper seeks to address some interesting questions and close the gap. The results are clean and thus have value. ", "weaknesses": "1. The contribution part is not clear and it seems that they are minor. There are recent works on First-order methods for Stackelberg-game [A1]. However, the paper has not compared with those approaches. \n\n[A1]. Maheshwari, Chinmay, S. Shankar Sasty, Lillian Ratliff, and Eric Mazumdar. \"Convergent first-order methods for bi-level optimization and stackelberg games.\" arXiv preprint arXiv:2302.01421 (2023).\n\n2. The paper has made a lot of Assumptions in order to achieve results (specially for MDP). However, can they be satisfied in practice? Specially, it seems that the action correspondence  is concave in $x$ is very strong assumption. Why $f(x,y)$ is convex in $y$ means that it must be affine?\n\n3. For general simultaneous game, average gradient descent average converges to the saddle point for min-max game. This result also shows that average indeed converges to max-min solution. Discussion with the simultaneous game and the technical difficulties must be included. Further, the algorithm seems to avoid simultaneous game complications by finding the solution or the saddle point $(y, \\lambda)$ for the lower-level game (assuming a saddle-point solver or simultaneous game setup whose results are kind of well-known). Hence, technical contributions seem to be limited. Further, there is no last-iterate convergence guarantee where the min-max game (simultaneous play) already have achieved that (using extra gradient, or optimistic gradient)\n\n4. All the algorithms seem to have large sample complexity, given the fact that it relies on finding the lower-level solution for each upper-level point $x$. How this algorithm can be implemented in practice? Will leader just pause in updating its strategy while followers updating their strategies?\n\n4. The paper is not very well-written. For example, the MDP setup is not at all clear. Does the leader and follower take decisions in turn at the same state? Does the state transition to the next state after both the leader and follower take actions? \n\n5. The numerical setup should also be expanded.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! \n\n1) Our model is not captured or covered by [A1], because in [A1], the action space of the followers does not depend on the leader’s action. Due to space limitations, we were unable to include a discussion of bi-level optimization more broadly; however, we can use the additional page in the camera-ready version to provide further context.\n\n2) The assumptions that we present are specifically satisfied by reach-avoid problems (see Appendix C and Theorem C.1.). Reach-avoid problems are important because of their applicability to robotics problems, such as autonomous driving. The fact that our assumptions capture this important class of problems substantiates their utility. Further, these assumptions enable polynomial-time computational guarantees, and thus open the door to roboticists to build practical solutions for this important class of problems. \n\n3) $f$ is assumed to be convex in (x,y) and concave in $y$; as such $f$ must also be affine in $y$.\n\n4) Although we agree that proving convergence in last iterates would be of interest, even in simultaneous settings, assuming access only to a stochastic first-order oracle, convergence in last iterates is *not* known. The results for extragradient descent ascent hold only for *exact* first-order oracle settings [1]. \n\n5) Additionally, although our proof techniques are an extension of the convergence technique provided by Goktas et al. [2] to a setting with a stochastic first-order oracle, we want to note that our main technical novelty pertains to the convergence of nested policy gradient methods in zero-sum stochastic Stackelberg games, and their application to reach-avoid problems. \nThe algorithm by nature is sequential, meaning that the leader has to wait for the follower to best respond, so as to converge to a (recursive) Stackelberg equilibrium. Our experiments suggest that our algorithm is sample efficient in practice. \n\n6) The leader and follower take action sequentially. The leader first commits to an action, after which the follower, having observed the leader’s action, takes its own action. Once both players have made their moves, the game moves to a new state. This description can be found in lines 29-33. For more explanation of such dynamics, we refer you to the introduction of Goktas et al. [2].\n\n**Regarding your questions.**\n\n1. Our generator model is not based on the state-action visitation distribution, but rather the history distribution. This model is realistic, since simulating a trajectory of the game is possible given the policies of both players. Additionally, we note that our convergence results apply to both continuous and discrete state spaces, but not to continuous action spaces.\n\n2. Two-time scale approaches do not allow for convergence to a Stackelberg equilibrium, when the leader’s action determines the action space of the follower (See Example 3.3. in [4]).\n\n3. This is a typo. The $\\eta$ in the numerators should match the variables. Note that the average-iterate convergence result for $\\mathbf{y}^{(t)}$ is due to Theorem 3.15 of Nemirosvki [3] as described in lines 768-770 of Appendix E. We realize this point may not be clear to the reader, so we will add an explicit reference in the camera-ready version.\n\n**References**\n\n[1] Golowich, Noah, et al. \"Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.\" Conference on Learning Theory. PMLR, 2020.\n\n[2] Goktas, Denizalp, and Amy Greenwald. \"Convex-concave min-max Stackelberg games.\" Advances in Neural Information Processing Systems 34 (2021): 2991-3003.\n\n[3] Nemirovski, Arkadi, et al. \"Robust stochastic approximation approach to stochastic programming.\" SIAM Journal on optimization 19.4 (2009): 1574-1609.\n\n[4] Goktas, Denizalp, and Amy Greenwald. \"Gradient Descent Ascent in Min-Max Stackelberg Games.\" arXiv preprint arXiv:2208.09690 (2022).\n\n\n\n\n\n\n\n\n\n"}, {"review_id": "xNz4TwVuWU", "reviewer": "Reviewer_5fZF", "summary": "This paper develops policy gradient methods using stochastic gradient estimates from the trajectories of play for computing in polynomial time Stackelberg equilibria in convex-concave games, most notably including a certain class of reach-avoid problems. The authors also demonstrate through experiments the benefit of Stackelberg equilibria over their simultaneous-move counterparts in reach-avoid problems.", "questions": "Some minor issues: \n1. Line 12: Missing space before the first set of references\n2. Line 50: A Stackelberg equilibria -> A Stackelberg equilibrium\n3. Lines 59-60: Technically this is a pseudo-polynomial time algorithm since the dependence on $1/\\epsilon$ is polynomial\n4. Why are you using the notation $\\mathbb{N}_+$ instead of just $\\mathbb{N}$? (those are presumably the same sets)\n5. Lines 132 - 134: The game being convex-concave is surely not the only condition that makes the problem amenable to first-order methods\n6. Theorem 3.1: then, in expectation over all runs of the algorithm, then (I would remove the second repetition of the word \"then\")\n7. Line 673: Missing dot\n8. Line 694: as as\n9. There are many overfull equations in pages 21-23 of supplementary; I strongly encourage to fix those\n10. Overall there are missing punctuation marks in the equations throughout the entire paper\n11. Line 839: the argument is incomplete\n12. It would be helpful to introduce the notion of stochastic convexity since it is quite non-standard\n", "limitations": "The authors have adequately addressed all limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Prior work by Goktas and Greenwald [23] addressed the problem of computing Stackelberg equilibria in a certain class of min-max optimization problems using an exact gradient oracle. The present paper extends those prior results by providing polynomial-time guarantees even when only stochastic gradient estimates from the trajectories of play are available, filling a gap that was left in prior work. Moreover, the paper nicely motivates the underlying problem, providing a number of concrete applications, especially with the experiments of Section 5 that demonstrate the benefit of computing Stackelberg versus Nash equilibria in a certain class of problems. Overall, the paper addresses an important problem with a theoretically sound approach, and provides non-trivial improvements over the prior state of the art.\n\nThe paper is also well-written, and the ideas and concepts are clearly exposed. The results are also accurately placed into the existing literature.\n", "weaknesses": "The main weakness of this paper is that the overall contribution is arguably somewhat incremental in light of prior work, especially papers [23] and [25]. The techniques employed to extend the analysis from exact to stochastic gradient information are overall standard, and the main results are certainly not surprising. That being said, the paper closes a theoretical gap left from prior work, and I do believe that the technical contribution is non-trivial.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, and for taking the time to point out several minor issues! \n\n**Regarding the weaknesses.**\n\nAlthough our results are an extension of the convergence guarantees provided by Goktas et al. [1] to a setting with a stochastic first-order oracle, we view our main contribution to be the convergence of nested policy gradient methods in zero-sum stochastic Stackelberg games, and the applicability of these methods to reach-avoid problems. Our results in this vein make use of novel assumptions (based on the extensively studied notion of convex stochastic dominance) and proof techniques, to prove that under suitable assumptions zero-sum stochastic Stackelberg games can be shown to be convex-concave w.r.t. to the parameters of the leader and follower’s policy parameters, thereby allowing us to obtain convergence to a recursive Stackelberg equilibrium. Perhaps more importantly, in Appendix C, we show that the important class of reach avoid problems [2] can be modeled as convex-concave zero-sum stochastic Stackelberg games (see Theorem C.1. in Appendix C). Using this characterization, we obtain novel polynomial-time solution methods for these problems, which as we show in experiments, outperform known solutions/methods (i.e., Nash equilibrium).\n\n**References**\n\n[1] Goktas, Denizalp, and Amy Greenwald. \"Convex-concave min-max stackelberg games.\" Advances in Neural Information Processing Systems 34 (2021): 2991-3003.\n\n[2] Jaime F. Fisac, Mo Chen, Claire J. Tomlin, and S. Shankar Sastry. Reach-avoid problems with time-varying dynamics, targets and constraints. In Proceedings of the 18th International\nConference on Hybrid Systems: Computation and Control, HSCC ’15, page 11–20, New York, NY, USA, 2015. Association for Computing Machinery\n"}]

Author rebuttal:
We would like to thank all the reviewers for their time!

**Summary of our contributions**: We present polynomial-time first-order methods to compute Stackelberg equilibrium in convex-concave min-max Stackelberg games, assuming access to only a first-order gradient oracle (Theorem 3.1). We then introduce the class of convex-concave zero-sum stochastic Stackelberg games, provide sufficient conditions to validate convex-concavity (Lemma 1 and Lemma 2), and obtain polynomial-time convergence guarantees to recursive competitive equilibrium via a policy-gradient-type algorithm in discrete/continuous state and discrete action convex-concave zero-sum stochastic Stackelberg games (Theorem 4.1). Finally, we show that reach-avoid games [1], which have found important applications in robotics, can be modeled as convex-concave zero-sum stochastic Stackelberg games (Appendix C, Theorem C.1, part 1). Using this result, we obtain polynomial-time solution methods for such games (Appendix C, Theorem C.1, part 2.), and run experiments using neural policy classes.

**Summary of common concerns of reviewers**:
1) Reviewers gXac, sSzA, and 5fZF suggested our contributions could be seen as incremental.
2) Reviewers yZL6 and gXac requested additional motivation for the assumption of convex-concavity.

**Answer to common concerns**:
1) While our results and proof techniques necessitate extensions of Goktas et al.’s [2] results to a setting with a stochastic first-order oracle, we do not consider these extensions to be the main contribution of our work. Rather, our main contribution is the convergence of nested policy gradient methods in a novel class of zero-sum stochastic Stackelberg games, and their application to reach-avoid problems.
Our main results make use of novel assumptions (based on the extensively studied notion of convex stochastic dominance) and proof techniques, to prove that under suitable assumptions, zero-sum stochastic Stackelberg games can be shown to be convex-concave w.r.t. to the parameters of the leader and follower’s policy parameters, allowing us to obtain convergence to a recursive Stackelberg equilibrium in discrete/continuous state and discrete action space games. Our assumptions, proof techniques, and results imply convergence of policy gradient methods in a new class of MDPs, and open the door to proving the convergence of policy gradient methods in a new class of continuous/discrete state and discrete action space Markov games.
Even more importantly, we provide one of the first polynomial-time convergence guarantees for the well-studied class of reach-avoid problems [1] by modeling these problems as convex-concave zero-sum stochastic Stackelberg games. We are hopeful that our techniques might be picked up by roboticists who build robots to navigate real-world environments.

2) Beyond convex-concave domains, convergence to a Stackelberg equilibrium is NP-hard [3]. As global convergence guarantees to (recursive) Stackelberg equilibrium have not been obtained for more general zero-sum (stochastic) Stackelberg games under the assumption of a stochastic first-order oracle, we chose to restrict attention to convex-concave domains. It may also be possible to prove a local convergence result; however, such a result would overlook the fact that the popular class of reach-avoid problems [1] can be naturally formulated as convex-concave zero-sum stochastic Stackelberg games (Appendix C, Theorem C.1.), implying that we provide efficient solutions to these problems. A number of other problems of interest have also been shown to satisfy the convex-concavity assumptions (see for instance [4] or [5]) further motivating the class of convex-concave zero-sum stochastic Stackelberg games.

**References**

[1] Jaime F. Fisac, Mo Chen, Claire J. Tomlin, and S. Shankar Sastry. Reach-avoid problems with time-varying dynamics, targets and constraints. In Proceedings of the 18th International
Conference on Hybrid Systems: Computation and Control, HSCC ’15, page 11–20, New York, NY, USA, 2015. Association for Computing Machinery.

[2] Goktas, Denizalp, and Amy Greenwald. "Convex-concave min-max Stackelberg games." Advances in Neural Information Processing Systems 34 (2021): 2991-3003.

[3] Tsaknakis, Ioannis, Mingyi Hong, and Shuzhong Zhang. "Minimax problems with coupled linear constraints: computational complexity, duality and solution methods." arXiv preprint arXiv:2110.11210 (2021).

[4] Badithela, Apurva, et al. "Synthesizing reactive test environments for autonomous systems: testing reach-avoid specifications with multi-commodity flows." 2023 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2023.

[5] Goktas, Denizalp, and Amy Greenwald. "Gradient Descent Ascent in Min-Max Stackelberg Games." arXiv preprint arXiv:2208.09690 (2022).



Meta-review: A polynomial-time algorithm is developed for zerosum stochastic Stackelberg games in the convex-concave case (as exemplified by the reach-avoid game). The key contribution is to identify a nontrivial class of games that possesses the convex-concave property, which allows the theoretical analysis of policy gradient algorithms to carry over (which on its own is incremental without the structural result). After a thorough discussion among reviewers, we have reached a consensus that the structural result is novel and passes the acceptance bar by a small margin.
Decision: Accept (poster)