Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Authors: Eric Frankel
Kshitij Kulkarni
Dmitriy Drusvyatskiy
Sewoong Oh
Lillian J. Ratliff
Venue: ICML 2025 poster (2025)
Keywords: Stackelberg game
stochastic optimization
learning and games
stochastic tracking
Primary area: theory->game_theory
TL;DR: Finite-time convergence rates for stochastic Stackelberg games under distribution shifts resultant from reactive agents employing smooth algorithms.

Abstract: Decision-makers often adaptively influence downstream competitive agents' behavior to minimize their cost, yet in doing so face critical challenges:  $(i)$ decision-makers might not *a priori* know the agents' objectives; $(ii)$ agents might *learn* their responses, introducing stochasticity and non-stationarity into the decision-making process; and $(iii)$ there may be additional non-strategic environmental stochasticity. 
Characterizing convergence of this complex system is contingent on how the decision-maker controls for the tradeoff between the induced drift and additional noise from the learning agent behavior and environmental stochasticity. To understand how the learning agents' behavior is influenced by the decision-maker’s actions, we first consider a decision-maker that deploys an arbitrary sequence of actions which induces a sequence of games and corresponding equilibria.   We characterize how the drift and noise in the agents' stochastic algorithms decouples from their optimization error. Leveraging this decoupling and accompanying finite-time efficiency estimates, we design decision-maker algorithms that control the induced drift relative to the agent noise. This enables efficient finite-time tracking of game theoretic equilibrium concepts that adhere to the incentives of the players' collective learning processes.

Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Eric Frankel
Kshitij Kulkarni?
Dmitriy Drusvyatskiy'
Sewoong Oh"
Lillian J. Ratliff'
Abstract
Westenbrock et al., 2019). For example, recommendation systems deploy predictive models of engagement to encour- age user interactions (Calvano & Polo, 2021; Hardt et al., 2022), crowd-sourcing markets leverage incentives to elicit responses (Dasari et al., 2020; Hu et al., 2018; Scheid et al., 2024; Shah & Zhou, 2016; Xie et al., 2014), and in multi- agent systems, control policies influence outcomes of agent competition (Ho et al., 1982; Ratliff & Fiez, 2020; Yang et al., 2022). Common to these domains is the assumption that agent preferences are fully known and their behavior is stationary: the decision-maker knows how agents will react and expects them to react the same over time. Yet, in practice this assumption is frequently violated, particularly when competitive agents adapt their response to a decision- maker's 's action (Fiez et al., 2020; Liu & Ratliff, 2024; Miller et al., 2021; Narang et al., 2023; Perdomo et al., 2020).
Decision-maken often adaptively influence down- stream competitive agents' behavior to minimize their cost, yet in doing so face critical challenges: (i) decision-makers might not a priori know the agents' objectives; (ii) agents might learn their responses, introducing stochasticity and non- stationarity into the decision-making process; and (imi) there may be additional non-strategic envi- ronmental stochasticity. Characterizing conver- gence of this complex system is contingent on how the decision-maker controls for the tradeoff between the induced drift and additional noise from the learning agent behavior and environmen- tal stochasticity. To understand how the learning agents' behavior is influenced by the decision- maker's actions, we first consider a decision- maker that deploys an arbitrary sequence of ac- tions which induces a sequence of games and cor- responding equilibria. We characterize how the drift and noise in the agents' stochastic algorithms decouples from their optimization eиror. Leverag- ing this decoupling and accompanying finite-time efficiency estimates, we design decision- maker al- gorithms that control the induced drift relative to the agent noise. This enables efficient finite- time tracking of game theoretic equilibrium concepts that adhere to the incentives of the players' col- lective learning processes.
A natural abstraction between the mecision-maker and agents is a Stackelberg game, where the decision- maker takes the role of leader and the agents take the role of follow- ers (Stackelberg al., 1952). Stackelberg games can be viewed as bilevel optimization problem wherein the Eocision-maker seeks to optimize its objective subject to variational inequality that captures the equilibrium behavior of the agents. As a class of convex structured problems, monotone variational inequalities have garnered much at- tention in machine learning due to their application to clas- sical (Combettes et al., 2023; Ghadimi & Lan, 2015) and modern problems such as adversarial learning (Fiez et al., 2020; 2021a; Gidel et al., 2019; Goodfellow et al., 2014), ro- bust and multi-agent reinforcement learning (Foerster et al., 2018: Pinto et al., 2017; Zheng et al., 2022), auction the- ory (Syrgkanis et al., 2015), and recently to fine-tune large language models ( (Amini et al., 2024; Yang et al., 2024).
1. Introduction
mackiinn-making not only under uncertainty but also en- vironments with competitive learning agents arises quite naturally and frequently in machine learning applications (Cai et al., 2015; Dean et al., 2024; Kim & Perdomo, 2023;
In the setting we consider, the agents are learning and therefore adapting their behavior for any deployed decision- maker action. This alone makes the Docision-makerr objec- tive time- varying indeed, even for fixed decision-maker's action deployed over a time horizon, the agents' learning process may not have stabilized at an equilibrium, much less for a sequence of decision-maker actions. Moreover, the environment itself is also stochastic and is unknown to the decision-male beyond query access. Ignoring that the
'University of Washington, Seattle Universsiyy of Cali- fornia, Berkeley. Correspondence icsf@cs. wwt.ssashinnnnoonduu>>..
Eric Frankel <er-
Proceedings of the 4rnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
distribution shift arises from competing agents, the decision- maker's objective is reminiscent of stochastic tracking prob- lems (Borkar, 2009; Cutler et al., 2023; Kusher & Yin, 1997). Similarly. if the decision maker faces single, non-learning agent, this setting is reminiscent of performative predic- tion (Perdomo et al., 2020). A natural challenge is to design and analyze the combined learning processes of multiple competing agents and the pirission-mkee ensuring conver- gence to game-theoreticale meaningful equilibria.
training) that biased due to ignoring the reaction of agents. We show (cf. Section 4.1) convergence to an approximate performatively stable equilibrium in (log(1//) + o² /s) epochs where o² and & are the decision-maker gradient estimator variance and target accuracy, respectively. In- creasing the gradient information but at a computational cost, strategic decision-maker recognizes the agents are dy- namically responding, yet does not know the agents objec- tives. We devise derivative-fres method (cf. Section 4.2) that converges to an approximate Stackelberg equilibrium in OdP /&²) epochs. In both cases, the epoch complexity matches the optimal rate for their single player counter- parts. A key challenge we address is designing the epoch length to get an efficient an overall iteration complexity, where the per epoch rate is optimal for tracking problems.
Contributions. We analyze scenarios that reflect the decision-makers maker's 's ability to reason about the agents' behav- ior via different estimates of how it impacts their gradient. The agents update their actions by playing any one of a class of stochastic p-contracting algorithms. Experiments illustrating our theoretical results in practical scenarios are in Appendix D.
2. Preliminaries
Characterizing Drift-to-Noise Ratio in Agent Play. To un- derstand how the learning agents' behavior is influenced by the decision-maker s actions, we first analyze a decision- maker that obliviously deploys an arbitrary sequence of actions de that cause drift in the agents' stochastic algo- rithms and induce a sequence of games and corresponding equilibria. In Section 3, we identify regimes governed by the noitee ratio and characterize the agents' optimal play via non-asymptotic convergence guarantees. In par- ticular, we bound the equilibrium tracking error in each of the regimes and give high probability tracking bounds (Appendix H.3) that provide guarantees that hold in settings with irreversible drift such as learning with adaptive agents that strategically respond. 'hese efficiency estimates pose how the equilibrium error decouples from noise in the agents' learning process and time drift in the game: it is also integral to controlling the induced drift in the decision- maker dynamics (Section 4).
Throughout, we use I& to denote d-dimensional space with inner product (s, and the corresponding induced norm is given by ||=||| = v (a.z). For any set X' C R we denote the projection of a vector y onto X' as projx = argmingex ||ær y||. We also set [n] == nl.
2.1. Stackelberg Game Abstraction
The interaction between agents and the decision- makerr is Stackelberg game: a decision-maker takes actions which influences the behavior of n competitive agents.
Induced Agent Game Given a decision-makert ac- tion u E U C Rd, where U is some closed convex set, each player i E [n]] seeks to solve the problem ming, f." (2 x-1) where X, C I is the set of agent i's actions and f." (zt, denotes a C²-smooth loss func- tion of agent i induced by the decision-maker's action u. We use the standard notation := (2,, x);) E X = II, X C RT where x; is the action of agent i, x= is the joint action of all other agents, and m = -Ee(() m,.
Controlling Induced Drift in Agent Play. Given this de- coupling, we then design decision-maker epoch-based algorithms that control the induced drift relative to the agent noise and therefore enable efficient tracking of game the- oretic equilibrium concepts dependent upon the gradient information available. The key theoretical challenge is de- signing the epoch length such that the stochastic tracking error induced in the agent game can be bounded efficiently; for this we much leverage the novel analysis from Section 3 in combination with analysis of the bias-variance trade-off in the combined dynamics. We examine two natural set- tings, wherein for each setting we set the epoch length- x ([log(1/e7)) + /²/er), where o is the agents' noise parameter-by by cleverly setting the per-epoch agent toler- ance 6 using the drift-to-noise analysis.
The tuple Gu == (fr .ff fi) denotes the game induced by u E U. We say that G, is a C' -moooth convex game if, for each i E [nx]. the set X, is closed and convex, the function f (1) is convex in x; for all fixed (u, x.,)) E U x X and the partial gradient ViJ! (Zi4, x-;) with respect to xi exists and is continuous. A C' -smooth convex game is called j-sttrongly monotone for / >> 0 if the inequality (wr (x) (w'),, X C Rm, where the map wa = (ViSf.... ... V.S%) is the vector of individual gradients. Strongly monotone games arise in economics (e.g., Kelly auctions) as well as
2 1l| r'11 holds for all x x'
Duchi et al. (2013) improve the dependence on d with two- point estimator using two queries of the exact same environment; this is impossible in our setting, as agents irrevocably update their play in response to queries.
In the first setting, a naive decision-maker that recog- nizes there is distribution shift and opts for a stochastically queryable gradient estimator (i.e., stochastic repeated re-
2

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
in engineering and machine learning systems highlighted in Section I; further examples and commentary on the chal- lenges to relaxing monotonicity are in Appendix C.
2.2. Smooth Algorithmic Agents
Returning to the agents, we now define the class of stochas- tic algorithms the agents are employing. The decision- maker deploys action Ut for number of iterations E N within epoch t. For a fixed action ue, each agent E [n] independently updates their action according to a stochastic algorithm A,iic., -,t+1 = A4 u(+1) for k E [r] where the epoch-t initial condition is æş. := 2t, and by a slight abuse of notation, Ve == zi-1- That is Tt = A( U4) is the agents' collective response after running A = (AI...., An) for T timesteps. We consider a broad class of algorithms for the agents that adhere to the following definition.
The most natural solution concept for the induced game is a Nash equilibrium. Given a fixed action u E U, a strat- egy x² E X is a Nash equilibrium for Gu. if the condition holds: f (a x=;)) I f." (=xx,==]) for all 22 E X; and all E [n]. A Nash equilibrium x² E Eq(G)) satisfies (-wa(x"), - x²) I 0 for all x E X' (Rockafellar, 2018). Denote the set of Nash equilibria for G.. as Eq(Gu). To en- sure existence and uniqueness (Rosen, 1965), we adopt the following assumption (ef. Appendix F for more insight).
Assumption 2.1. We assume the following for each u E U: (i) the induced game 9u, is p-strongly monotone, (ti) the mappings z + V.fi" (Zzz x-1) are L, LipLsschiitz continu- ous, and (dit) V u/ llop is bounded.
Definition 2.3. Fix constants E (0, 0, E o0) and с > 0. A stochastic algorithm is p-contracting if, for fixed u E U. the inequality holds: E [|x/ - x (u) 12 <
p² E | x"I)]]? + c² (poa)² where x (u) E Eq.)).
Notably, Assumption 2.1 implies that the agents' equilib- rium response x² (-) is Lipschitz continuous; let the Lips- chitz constant be Leq. and define L == max Lg.
As show in Appendix G, there are many examples of al algorithms that satisfy Definition 2.3, including stochastic gradient play, asynchronous stochastic gradient play, best response dynamics, and even momentum-based gradient play in strongly convex-strongly concave zero-sum games.
Decision-Maker's Problem. The decision-maker seeks to minimize loss : U Z + R that depends on their action u E l and the decision-dependeed environment 2 (ar, {) E Z := X x E which comprises the joint action of the agents x E X' and a non non-strategic random variable & E E. We write x ~ D(u)= == D2 x (u) where captures the decision-dependens stochasticity of the agents' reactions and (.) captures non-strategic decision- dependent stochasticity. The latter arise in economies, e.g., based on external market factors such as seasonality (Miron, 1990) or economic growth (Davis et al., 2010). Further, the expected loss is denoted [(u)= = B.zD(.) [M,u,, 2)]-
2.3. Challenges in Equilibrium Tracking
Let us start by providing some intuition for the technical challenges. A decision maker's 's action sequence {uz} in- duces a timevaarying game Ga, and are trying to learn a time-vary equilibrium 27 E Eq(G..). For any p-contracting stochastic algorithm executed by the agents, Proposition 3.1 shows that their equilibrium tracking error decomposes as
ercision-maker's
E || - x7 11 S (1 (1- -0-11=) 11=001100-0000 mill2
2 -
(
A
The decision-maker aims to find an equilibrium of the stochastic hierarchical game wherein the agents are playing a Nash equilibrium of the induced game. The most salient solution concept here is a Stackelberg equilibrium: namely, (u".x"((") E U x X such that u² E argmin (Ee-D(()) E(u, (x ()) x² (") E Eq(G.))
where A. == max { [|ar - xx(-111) 112] is the drift and ds characterizes the noise.? The first term is exponentially decaying so that, as t + co, we are left with the drift and noise terms. This raises the following challenge:
Challenge Given the decision-make induced drift in the agents' stochastic game, what is the contraction p that optimizes the target accuracy?
} However, for any deployed action u, the agents are not nec-
essarily playing behavior consistent with x² (u) E Eq(G.). The agents are trying to adaptively learn the induced equilibrium x" (u) and may be employing a stochastic algorithm to do so. This necessitates the design of algorithms for the decision-maker that can control the induced drift and the stochasticity from the environment.
Section 3 contains results that characterizes the drift-to- noise regimes and corresponding optimal contraction rate for stochastic gradient play. These efficiency rates are cru- cial for analysis of decision-make algorithms in Section 4.
Turning now to the decision maker's perspective, even if the agents have equilibriated such that for any given w the agents play a "best response" x (u). the expected loss Bg-D(w) uu, =)] still depends the a priori unknown pref- erences of the agents. In practice, this means that the second
Remark 2.2. In the main body of the paper, we primarily concern ourselves with the setting in which (u) = D. (i.c.,& a stationary distribution) in an attempt to reduce nota- tional overhead. Throughout, we remark on the decision- dependent non- non-strategic setting (i.e. where De (u) is non- stationary) and defer proofs to the appendix.
Here, x and S indicate an equality and inequality, respec- tively, holding up to constant.
3

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
1.20
95000
0F0, c-0.00
Hul, -u u
1115
comceestyy
25000
1.10
20000
Special
1.06
10000
Stadeiltty boundayy
1.00
inver beund y- 56
5000
10
20
30 spach length
60
0.10
0.15
0.20
0.25
0.50
0.35
0.40
Agent Heactivtty (4:o)
Figure 1. The spectral radius of the local linearization J, (=","") parameterized by r-of the combined update. Stability attained only when 2 min(r' spec(J.. ,²)) D[0, c CJ. See Appendix D.4 for further details.
Figure 2. (left) A scenario where the performatively stable equilib- rium u lies in an e e-ball around u": (right) Approximate big-C sample complexity (Theorems 4.4 and 4.9) needed by the repeated- gradient (RGM) and derivative-fret free (DFM) methods to bring the decision-maker within of u" agent reactivity Leg grows. Be- cause RGM ignores the implicit term of the decision-maker gradient, the gap ||u x widens as Tee grows, shrinking its effective tolerance e' = E - || - -I and pushing its sample complexity past that DFM. See Appendix D.5 for additional details.
term in the decision maker's gradient
EzwD(u) V Vullu, 2) + ah EEWD(U) =()=z))u=ur
(l)
not directly computable.
Challenge 2: Can the decesion-maker algorithnically ex- ploit available gradient information converge game- theoretically meaningful equilibrium?
maker ensure that the agents equilibrate fast enough so as to control A relative to o? To address this, we introduce time-scale separation via epoch-based algorithms in the two aforementioned gradient information settings. To obtain finite-time rather than asymptotic convergence, it is nec- essary to allow the agents to update multiple times while the decision-maker remains relatively stationary. This is illustrated by analyzing the local stability of the dynamical system representing the combined update. For fixed step- sizes (1) 7) and gradient updates for the decision-maker and agents, respectively. at each fixed action u4 the agents update T steps and then the decision- maker updates. As il- lustrated in Figure 1, it required that r 2 1 for equilibrium convergence, meaning that the epoch-based algorithm struc- ture is necessary for finite-time guarantees. We describe the epoch length lower bound in more detail in Appendix D.4. In Section 4, for each of the gradient information settings, we optimize the epoch length to obtain non-asymptotic con- vergence by controlling A/o.
To address this nontrivial problem, set up hierarchy of reasonable interaction models that account for progressively more gradient information. There are two natural settings: the decision-make (i) naively employs repeated retraining that does not account for the second term in (1), and (ii) strategically employs a query-based method to estimate this term. In Section 4, we characterize which equilibrium concepts are achievable under these two approaches: namely, performatively stable equilibrium in (i) and Stackelberg equilibrium in (ii).
Further exacerbating the aforementioned challenge, be- cause the agents' learned play I, also evolves with the docision-makert s actions, the decision-maker also faces a time-varying objective. To illustrate this point, consider decision-make with a-strongly convex loss E(. 2) and de- fine u/ argmin, (E)) L(u, (2,, {.)}. Analogous to the agent decomposition above, if the decision-maker uses a stochastic gradient-basse based algorithm with stepsize 1), then
A last natural question centers on efficiency versus opti- mality. Recall that the iterates equilibrate different equi- librium concepts dependent upon the decision-maker 'e's es- timated gradient information. We show that the sample efficiency of the gradient method decreases as more of the gradient (1) is estimated (under the same information as- sumptions on the agents behavior), but is there an effect on the optimality of achievable equilibrium? Consider the scenario shown in Figure 2: a decision-make could use a derivative- frree method to reach within 0 of the Stack- elberg equilibrium u², or use the more efficient repeated gradient method to reach within e' = || - u²|l of the performatively stable equilibrium wra; in either case, the worst-case expected distance from u" is the same. This poses problem for the daccision-makee how to assess the
E 1|u,- - 11 x (1 - ) '1u0 - 2 + no2 a
(A)
(2)
where o² is the gradient estimator variance ("noise") and A := max ||u| 1 parameterizes the drift induced by the agents vare-na actions {a.). The aim is to opti- mize the right-hand side of (2) by controlling A/o. How- ever, recall that the decision- maker does not have a priori knowledge of the agents' objectives nor their update rules.
Challenge 3: Can we design algorithms to control the induced drift such that (we, xx) reaches an s-equilibrium in finite time?
The question of controlling the drift in finite-time reveals in- teresting al algorithm design questions: how does the decision-
4

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
tradeoff between performance degradation and sample com- plexiry? With this in mind, in Appendix I, we characterize the performance gap (Proposition I.4) in terms of proper- ties of the game- in particular, how dynamic agents are in reaction to the decision-maker.
Proposition 3.1 reduces to the following corollary, the for- mal version of which is given in Corollary H.4.
Corollary 3.2 (Informal), Under Assumption 2. 1, suppose agents are running stochastic gradient play (SGP) with step-
size S pf (2L2), and an unbiased estimator W, satisfying B[| - E, [T,]]l S o² for O2 E [0, 20). Then p² 1/(1 + +1) and c = V27, respectively, so that
3. Characterizing Drift-to-Noise Ratio
To understand the drift versus noise, we consider the setting in which decision-maker obliviously deploys sequence of actions } and passively observes how the agents' re- sponse } as generated by some set of algorithms A. Ex- amples include pricing or recommendations where periodic changes are made to interventions. The decision-maker's ss sequence of actions induces drift in the agents' equilibrium: =-:- x² (u.). Prior work has focused only on asymptotic guarantees for stochastic tracking in strongly monotone games assuming that the time-varying sequence of games being tracked equilibrates priori (Duvocelle et al., 2023). Given the induced drift A as identified in (1), a natural question is can we obtain a finite-time bound on the time to reach a target equilibrium, BI| - x 1| With the de- sign questions outlined in Section 2.3, taking a different tack than prior asymptotic work, we extend recent work in stochastic optimization, namely Cutler et al. (2023), to stochastic monotone games; this requires novel analysis as games generally do not admit a single cost function to which we can appeal in the analysis.
Eellz; - x7 2712 x (1- 11-1))' =
=tll + 2 + 2
Letting + xo, the optimization error tends zero, leaving only the noise and drift terms. Optimizing with respect to 7 leads to the optimal learning rate % == min (m/(222) (2A2/ 1/33 and asymptotic track- ing error e, := m00. {yoŻ/p + (Aa/(1n))*) Here 7, determines the interesting regimes. Indeed, set- ting /u/ (2L2) = (24 / ( and rearranging, we have two regimes for the drift-to-noise ratio: the low regime if Aa/oa < 1² (4L2), and otherwise the high regime.
In the high drift-to-noise regime, if agents run stochastic gradient play with 7 x (2(2)),, we have that
E I 11=--111 2112 S e. in i 3 log (1=0--)))) time steps. 2.
With high drift-to-noise the problem is essentially deter- ministic, and the rate in fact matches the deterministic set- ting (see, e.g., Chasnov et al. (2020a)). The low drift-to- noise regime is decidedly more interesting as the rate can be improved by controlling the combined drift and noise (cf. Section 4). Setting the step-size y x (2A) y 1/3 informally we have that
3.1. Bounding the Equilibrium Tracking Error
Suppose the decision-maker deploys actions or such that of is the induced equilibrium for the jusstrongly monotone game Gu.. which depends on u,, As long as the agents em- ploy a p-contracting stochastic method as in Definition 2.3, then it is possible to bound the expected equilibrium track- ing eгror with notable dependence on the noise da and induced drift A. := max (1 - =;,1)-
E ||,,~2111 Se. in S o? T.c.
log [ |ل===مāl"" c.
time steps.
The following proposition shows that if the agents employ stochastic gradient play in stages, then much like the single player time-invariant optimization problem (Kulunchakov & Mairal, 2019), the agents tracking error can be improved.
Proposition 3.1 (Informal). Under Assumption 2.1, suppose agents employ a p-contracting stochastic algorithm in the regime p E [0, 1). Then the estimate holds:
Proposition 3.3 (Informal). Suppose that induced time- varying agent problem is in the low drift-to-noist regime. There is an algorithm that proceeds by running stochastic gradient play (SGP) ) in K stages with T/ steps in each of the h: E [K] stages such that the total time satisfies T = Ek- La log [21|zo-zā]) + 6 ) + d2 and the expected
BII 27 12 & (1 --22)) 11=00 2011=
lco.) 2
T-p + + A
This result is formally stated in Proposition H.2 (Ap- pendix H). We exploit this decomposition of the tracking error to obtain efficiency estimates, thereby laying the foun- dation for efficient decision- maker algorithms.
1.2
tracking error satisfies E ||æ x*x 112 Se. Further, if the agents employ 7, then e = Ext
Indeed, do last-iterate convergent algorithms exist for the agents in this time-varying setting? ? To provide insight into the difficulty of the problem, we focus on natural learning rule, stochastic gradient play:
In Appendix H. we detail the construction of this algorithm, and give the formal statement in Proposition H.5. Essen- tially, the agents employ an algorithm that repeatedly runs stochastic gradient play in stages by reinitializing the al- gorithm at the previous stage and adjusting the stepsize by
Z1+1 -roj((++ Tar) W. := (V.f.' (z.)) (SGP)
x
5

---

a factor of 2- This progressively reduces the constant variance term. The iteration complexity clearly is com- posed of two terms: the classical deterministic complexity O(LL) log(1/e.) of gradient play, and the optimal complexity for stochastic gradient play in O(o ())ee))- Crucially, the regime is controlled by the decksion Aigorithm-siee Bl| - =t S Tee E ||+++ well so that A. S Lea as well as the agents' step-size which determines proximity to optimal. Bounds such as those in Proposition 3.3 are exploited (ef. Section 4) to design the epoch length in algorithms to control the agents' and and Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Algorithm 1 Epoch--asee Drift-to-Noise Control
del--p--oo exto 0.2to
Input: Alg, T, T)t, --1: ug. 7p
for /, = "....,To. do
for k= = 0..... Tt- - 1: query agents with
observe 2n - (A(z)-1, &.)
update u++1 = Al A1g Te, 9r)
end for
20
50
75
100
125
0.0
0.07
2006
11:05
0.10
0.12
teretion complexity.c ct EIK F 12 sc.
lagget BOCUrsEy
Figure 3. Iteration complexity and target accuracy of stochastic gradient play as function of drift-to-noise ratio. Switching to the optimal learning rate 7. (Section 3) and using stage based algorithm improves iteration complexity and lowers the achievable target error in the low drift-to-noise regime by decreasing the variance, while SCP is limited by the noise floor.
is a clear transition at 1a/o,,12/(4V)) if the agents adopt stage- based algorithm, then the target accuracy can be set arbitrarily small with modest impact on the iteration complexity. On the other hand, if a stage based algorithm is not employed, the agents risk hitting the noise floor da which will lead to a constant error in the decision- update.
after which,
therefore the decision-maker's eerro...
Remark 3.4 (Beyond Worst Case Tracking Bounds). The preceding results focus on the worst-case equilibrium ex- pected tracking error. In Appendix H.2, by assuming con- traction rate on the sequence [u.. we give a time-varying equilibrium tracking error. However, expected equilibrium tracking guarantees
We address these design and analysis questions in the sub- sequent sections, focusing on hierarchy of different gradi- ent information and epoch-based algorithms (Algorithm 1). We use bounds from Section 3 to set epoch lengths and the decision-maker's 's step-size to control the two aforemen- tioned two errors, respectively.
only meaningful if the dynamics run many times. Hence, in Appendix H.3, we give high probability bounds on the tracking error. Due to the strate- gic nature of agents, if the u,'s 's are deployed in real-time there will be irreversible drift, and thus high-probubility efficiency results are more meaningful as they characterize the performance if dynamics were executed only once.
4.1. Naive Decision-Maker
A common naive approach in machine learning is a stochas- tic repeated gradient method wherein the docision-maken periodically retrains given new data from the environment. Since the decision-maker does not have priori access to the agents' response mapping. it updates its loss using stochas- tic gradient estimate of (R,,D(u)) V.,(u, -...,,, only the part of the total gradient of L(u) with explicit dependence on u. We make the following regularity assumption.
4. Controlling for the Drift-to-Noise Ratio
Recall from Section 2 that the decision-maker seeks to solve a stochastic optimization problem with both uncer- tainty due to the response of the agents and stochasticity of the patrromment-namllyy they seek to minimize the loss L(u)= = P(, (u( =)] with respect to where D(u) is the stochastic observation that the decision-makes receives from the environment and abstracts the agents' (stochastic) decision process. Ultimately for ue to stabilize around some (appropriate) equilibrium w*, the decision- control ||x, - at! l and ||=ū - as these terms drive the induced drift and noise (and therefore bias and variance). Key questions center on 1) what types of algorithms enable controlling these two sources of error, and 2) given par- ticular algorithm, how long before the agents reach the low drift-to-noise regime, wherein the optimal target accuracy can be achieved? In Figure 3, for stochastic gradient play, we show the iteration complexity and optimal target accu- racy for the agents as a function of the drift-to-noise. There
Assumption 4.1. a. The loss E(. 2) is C*-smooth and a- strongly convex for any 2; b. The maps u + vul(u,²) and + Vul(u, 2) are L, and Lg Lipschitz continuous, respectively.
needs to
Equilibrium Baseline. The appropriate notion of an equilibrium in this case is that of a performatively sta- ble equilibrium of the "lifted" (n + 1l-player game fl. fa) (Narang et al., 2023).
Definition 4.2. The joint action (uP9, x (xP*)) is a per- formatively stable equilibrium if x= (uP)) E Eq(Gw)) and w argmin EgwDD(um) lu,, (x* (u))),
In Appendix I.1, we show the equilibrium exists and
6

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
is unique when a (Len + Lea) where Le is the Lipschitz parameter for the environment-nnmell Wi (u), Pa(w)) < Laallu w|ll (ef. Assumption 1.2). In the setting where (u( = De existence is guaranteed with a < T. Teq. and the performatively stable equilib- rium is a Nash equilibrium of the game (f, f........... fn): the decision-maker is playing a best response to the equi- librium response of the agents in expectation." 3 In Ap- pendix I.2, we analyze the performative gap which is de- (x=")=
Proposition I.5 contains the formal statement and proof. A key technical difficulty is bounding the induced drift (i.e., agents' equilibrium tracking error). We leverage results from Section 3 to set the epoch length via bounding the se- quential (epoch to epoch) initialization error IE [x = I?, and combine this with within epoch efficiency estimates for p-contracting algorithms (Appendix G). We also pro- vide a specialization to the case where the p-contracting algorithm is stochastic gradient play (Proposition 1.6). To provide more intuition on the effect of drift vs noise, we also specialize to the case where the p-contracting algorithm is deterministic (Proposition I.11); indeed, here agents do not need to run a stage-based based algorithm as there is no extra bias from their stochasticity. Finally, we also leverage the high probability tracking error results (Appendix H.3) to give stronger guarantees for irreversible induced drift (cf. Theorem 1.9, Appendix 1.3.1..
distance be- tween the Stackelberg and performatively stable equilibrium. Depending on the problem parameters, the performatively stable equilibrium is sub-optimal, yet the gap may be small (cf. Proposition I.4). is interesting to examine regimes in which the gap is small so that obtaining the Stackelberg is not worth extra sample complexity (cf. Figure 2).
fined as ||u* - u || || -
Stochastic Repeated Gradient Method. The repeated stochastic gradient method is given by
Given this t-step bound, the decision-maker may employ a staged method to obtain convergence to an approximate performatively stable equilibrium.
U1-1- = proj(u; -99))= 9t- = V Vul(ue, Ei)) (RGM)
u
Corollary 4.5 (Informal). Fix target accuracy E >> O. Under the assumptions of Theorem 4.4, suppose the decision maker runs the stochastic repeated gradient method in k = O,....K K super-epochs, for Tx epochs each with constant step-size Uk = =2 Ijo. and such that the last iterate of each super-epoch is the first iterate of the next. Fix constants
Assumption 4.3 (Finite Variance). Suppose there exists a filtered probability space FF, P) with filtration IF = (Fi)c20 such that Fo- = {0, 0}. 9t is mmcauuuure,, and there exists a constant σ > 0 satisfying E.11g. - E, I.gh,11 <
o² where E,- B[-1 Fil denotes the conditional expectation.
no = à K [1glog
(41.2] To = ano
2_ log 12B² }}. Ts =
1og((4) and
amp
Suppose that the decision-maker fixes its action ūt in round t for 7 time-steps, and the agents run a stage-based p- contracting algorithm (ef. Corollary G.2) A. Agents are incentivized to run stage- based algorithms: they aim to stabilize within the smallest neighborhood of x; as pos- sible, thereby requiring control of their own variance o²- In the remainder of this subsection, fix constants ā := a L. Lea > 0 (for existence and uniqueness, Theorem 1.3), and 1,2 : T22 + 122 (abusing notation).
+ logg ( Then E |ur u 12 S and
E | - x ("(e)) I1( S 2(c + Tegq e) in
T ΣK Th S o log ( (205) + a epochs.
The formal statement and proof is in Corollary 1.7. Note that since we run T iterations within each epoch, the total number of iterations is T T.. Analogous to Proposition 3.3, we progressively decrease the step-size to control the bias- namely, the drift in the agent game E || - x7|] I| and noise from their update E E| - x; until the desired accuracy is achieved. Reflecting back Figure 3, the target accuracy can be better optimized if the agents switch their step-size to the optimal 7. once in the low drift-to-noise regime. Hence, it is interesting to characterize the time T after which max E || - | ensures the agents are in the low drift-to-noise regime in expectation.
Theorem 4.4 (Informal). Suppose Assumptions 2.1, 4.1, and 4.3 hold, and that constants R >> ||ح_1 - x² (uo)ll and B > |lu0 - 1/2 are available. Further, suppose we are in the regime where a > LgLen and the decision-maker runs Algorithum I with Alg == RCM using step-size 1 S T1. and the agents employ a stage-based p-contracting algorithm A with p E 10 and 0= E (0, o0). Set :==00 R+
a
- + (4B+ af f111(11 -2??, ,, the tolerance 6, 0222
Proposition 4.6 (Informal). Under the assumptions of Corollary 4.5, the estimate max&sT E | u 1|
and epoch length T O (a-Tp log ( (t
(222)
6070²
+ (I-p-)err)
)² holds after T = Ek Th S O L2 log (2B²
Then, the following estimate holds:
az
+
2 epochs where s = 1 (p'o (4 L3)
E, 1/4 - 1 12 < (1 (1-
337 11u0
12 112
4ng"
We give the formal statement in Proposition I.10. Once in this region the agents are naturally incentivized to optimize their learning rates (i.e., selecting 7.) as it will enable them to more effectively stabilize the learning process.
'Performaively stable points in the single player setting (Per- domo et al., 2020) are equally interpretable as Nash when the environment comprises a stochastic hest responding agent whose reaction determined by a utility function.
7

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Remark 4.7 (Non-Strategic Environment Decision-Depen dence). As we show in Appendix 1.3.4, even if (e(u) de- pends on the results immediately extend. Indeed, sup- pose there exists Len < oo such that Wi (D, De(w)) I Tralll wIll and that a: > (rg(a.en + Tea) so an equilibrium exists (cf. Proposition I.3). Then, the results immediately apply replacing ā with a - L + Lea).
Assumption 4.8.d is common (ef. Agarwal et al. (2010)),
and implies the convex set lI is compact with a non-empty interior; otherwise, we can map U to lower dimensional space. Assumption 4.8.c requires the composition of the al- gorithm the agents' play and the loss & to be convex. We give examples of how this criteria may be met in Appendix J, and discussion of relevant literature (Dong et al., 2018; Miller et al., 2021; Perdomo et al., 2020; Ray et al., 2022). This assumption allows convergence to global optima; when it is not met, convergence is possible to local solutions; yet, as with non-monotone games, what constitutes an interesting solution is widely debated (Fiez et al., 2020; Jin et al., 2020; Mangoubi & Vishnoi, 2021). We explore local convergence numerically (Appendix D), and leave theory to future work.
4.2. Strategic Decision-Makee
A more strategic approach in low-information settings- i.... where the decision-mann makee knows that the agents are respond- ing to Ue yet still does not know the agents' objectives nor the algorithms they employ-is to estimate the effect of the agents' time-varying behavior via carefully designed stochastic queries to the environment.
Let (u", (u")) be the Stackelberg equilibrium. In the remainder of this subsection, let L := L, + L.
Equilibrium Baseline. The natural equilibrium baseline in this case is the Stackelberg equilibrium (cf. Section 2.1) since the decision-maker aims to optimize through the re- action of the environment including the agents' collective response. To do via gradient methods, the decision-make needs to estimate the full gradient of its loss as given in (I). Derivative free methods are one type of approach that enable estimation of the second term in (I) via stochastic samples of the loss at the queried environment state. The resulting gradient estimator tends to be inherently biased, prone to high variance, and is nominally sample inefficient; nonethe- less, Stackelberg equilibrium convergence is possible, opposed to suboptimal performatively stable equilibrium.
Theorem 4.9 (Informal). Suppose that Assumptions 2.1, 4.1, and 4.8 hold, and that a constant R> ||--11 x (wo) || is available. Further, suppose the decision-maker runs Al- gorithm I with Alg == DFM using step-size Te- = a(t+1) and query radius 5 < min ), and that the agents employ a p-contracting algorithm A with p [0. 1) and 0n E (0, xo). There exists a constant R < po such that if the tolerance is set to Er length t = O (T--p)) log 2n + (I-p")=E,
= =(o(t + 1)) with epoch
202 then the es-
max (222 B, o +
limate holds: E ||ue u²1l² 28 ((1 (1) ||x0"|| + 4))
8'6-((+1)
Derivative Free Method. Given that the environment is
For simplicity, the formal definition of R, which determines the required epoch length, is given in Appendix J.2; it is analogous to the constant in Theorem 4.4 in that it is derived from bounding the tracking error E ||ar. - x 2l using the drift-to-noii decomposition analysis in Section 3. We now characterize the iteration complexity to reach an approxi- mate Stackelberg equilibrium.
time-varying and responsive to the decision-maker's queries, we adapt a single point derivative free method (see. c.g., (Agarwal et al., 2010; Drusvyatskiy et al., 2022)) to the epoch-based framework outlined in Algorithm 1. Multi- point methods tend to have better complexity in terms of d, yet agents are responding and therefore it may not be possible to query the same static population repeatedly.
Corollary 4.10. Suppose the assumptions of Theorem 4.9 hold. Fix target accuracy < 4b2 ((1 (1+ (2) B + 4)²² and
For a fixed query radius 8 > 0 and epoch length r 2 1, the decision- makirr updates its action via
set 8 a</e/ (/////4/(((/ + L) + L) and ny. = 4/(a(t + 1)).
The iterates (u,, x²) converge to an approximate Stackelberg equilibrium: Eillu ==' |[9] I and E|| x² (w')) <
1
proj (u, m/ (1-5)4
(DFM)
2(e, + Loge) hold for all l Z 16 max(a' 8(E.d) + 1)(( + L)B + )
where, for a uniformly sampled vector U2 ~ $4, the gradient estimate is g. = fe(u, + ov, (A(x,-1, ur + dv,), E:) with g ~ D.. The challenge compared to classical analysis accounting for the additional bias from the agents' drift and noise. We require some regularity assumptions.
The formal statement is given in Theorem J.6 (Appendix J). An analogous statement to Proposition 4.6 which identifies the transition from high to low regimes as the decision- maker stabilizes is also provided. Observe that e may be selected arbitrarily small to control the agents' locality rela- tive to the equilibrium. Corollary 4.10 provides bound in terms of the number of epochs; the total iteration complex-
Assumption 4.8. The following hold: a. the loss f(u, bounded with l, == sup(v. (e(,,, 2)]; b. the map u b [2)( is LipLhchh continuous; c. the expected loss C(u) is ā strongly convex; d. 3 6, B > 0 such that BB C 2 C BB where B {u E R24
ity is E'= To x O [_t (log +))+)) If the agents are deterministic (0, = 0), this rate matches the rate of single
|||||| S 1).
8

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
12
16"
10
12"
12m
3000
10:0
12"
12"
Desstonn
(a) RGM with SGP agents.
(b) DEM with SGP agents.
Figure 4. Effects of decision-maker's choice of r on equilibrium convergence in a convex quadratic game. As expected, larger т produces smaller equilibrium error.
(a) Non-monotone
(b) Strongly Monotone
Figure 5. Phase portraits for the dynamics of decision-maker influenced Kelly auction. Markers indicate where (xr) 0 on i=t( and arrows represent the gradient flow. From (a) to (b), the agents' game transitions from non- non-monttone (admitting local Nash and saddle point) to strongly monotone (single stable Nash),
point derivative-fie convex optimization (Agarwal et al., 2010) up to log factors, where the log factor is precisely due to the agents running their algorithms for T time-steps. The rate for the derivative free method is decidedly worse than for the stochastic repeated gradient method, owing to the extra estimator bias, yet the latter converges to suboptimal equilibrium.
tone. It is natural to question whether or not the decision- maker can induce strong monotonicity. We explore this via a Kelly auction with m resources, where n agents submit bids x; E I for the resources, with the joint set of bids given by x = (f1,..., E Rmn. The 9,20 i-th agent receives Pij (2r) = ",+ my units of re- source j proportionate to their bid, and minimizes their loss (I; = (a=p)
Remark 4.11 -oon-Strategic Decision Deereinn-DDeeddenee)... As we show in Appendix J.3, if De()) (u) depends on u, the results in this section apply with minor changes to constants as long as l satisfies mixture dominance (ef. Assumption J.10) and W1 (u), (w)) S Leal u - wil (cf. Assumption I.2).
Iny) over X, {r; E RT Σ د Tay S b2}. A common auction con- trol mechanism is price floor u = (u1...., um) E R" regulation. Shown in Appendix C.5, if p = max; a; min, fg.u.)
5. Empirical Vignettes
E Ma EJ+ b,)² > O, then the agents' game is μ- strongly monotone. Figure 7 shows the drcision-maker's action changes the equilibrium landscape from multiple sta- tionary points to single stable Nash. It is interesting to consider incorporating a design constraint on the shape of the agent game. See Appendix D.2 for details.
In this section, we present some empirical results targeting some of the technical assumptions. These results elucidate the effect of the decision-maker on the "shape" of the agent game and convergence behavior. A broader set of experiments is contained in Appendix D.
algorithm design space
Selecting T. In many real-world settings the optimal r is unknown as some of the constants on which it depends are properties of the agents' algorithms. We study a represen- tative quadratic game examine the effects of a decision- maker's 's choice of 7. Indeed, many real-world problems (e.g. Bertrand/Cournot markets, multi-agent linear quaada-ua games, and revenue-maxin maximmeaxxiiiztiionn models (Narang et al., 2023)) can be cast as quadratic games (cf. Appendix C). Here, the i-th agent's 's cost formulated as
6. Discussion
We consider a novel class of stochastic time-varying Stack- elberg games. We present finite-timn efficiency estimates that are governed by the drift-to-noise ratio for the decision- maker influenced agent updates. We also identify two epoch- based algorithms that find two different notions of equilibria, the performatively stable Stackelberg equilibrium and the true Stackelberg equilibrium, and establish finite-time con- vergence rates. This work enables ample opportunities for future work. First, parameters intrinsic to the theoretical bounds are oft unavailable in practice, hence adaptive algo- rithms tuned to game theoretic settings may be especially useful. Second, future work might better capture the trade- off's in the performative gap and sample complexity. Finally, particularly interesting direction is to estimate agent dy- namics using techniques from adaptive control. Further discussion of these proposed directions are in Appendix B.
[i(,, = 1ut A.a; + ... xr + c. +,, u),
where di belongs to a quadratic family of incentives by which the decision-maker tries nudge agents toward a de- sired outcome (I²,u²) udd) (cf. Ratliff & Fiez (2020)). Figure 6 illustrates that several modest choices of T suffice: larger 7 results in faster convergence, yet the benefit of increasing 7 is marginal. See Appendix D.1 for further details.
Shaping the Landscape. Another assumption made throughout is that the induced game G., is strongly mono-
9

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Impact Statement
Cai, Y., Daskalakis, C., and Papadimitriou, C. Optimum statistical estimation with strategic data sources. In Con- ference Learning Theory, pp. 280-296. PMLR, 2015.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Calvano, E. and Polo, M. Market power, competition and innovation digital markets: A survey. Information Economics and Policy, 54:100853, 2021.
Acknowledgements
Cen, S. H., Ilyas, A., Allen, J., Li, H., and Madry, A. Mea- suring strategization recommendation: Users adapt their behavior to shape future content. arXiv preprint urXiv:2405.cm 05596, 2024.
We graciously thank (in alphabetical order) Gavin Brown, Scott Geng, Tiffany Liu, and Rui Xin for their helpful com- ments and feedback. SO and EF were supported part by NSF Awards 2019844, 21 12471, and 2229876, and Mi- crosoft Grant for Customer Experience Innovation. LJR and EF were supported in part by NSF CPS-1844729, and ONR YIP N00014-20-1-2571 EF is also supported in part by the NSF Graduate Research Fellowship Program. DD was supported by NSF DMS-2306322, NSF DMS-2023166, and AFOSR FA9550-24-1-0092 awards.
Chasnov, B., Ratliff, L., Mazumdar, E., and Burden, S. Convergence analysis of gradient-based learning in con- tinuous games. Uncertainty artificial intelligence, pp. 935-99999 9454944. PMLR, 2020a.
Chasnov, B., Ratliff, L. J., Mazumdar, E., and Burden, S. A. Convergence analysis of gradient-based learning with non-uniform learning rates in non-cooperative multi- agent settings. Proceedings of the Conference on Uncer- tainty in Artificial Intelligence (UAI), 2020b.
References
Abraham, R., Marsden, E., and Ratiu, Manifolds, lensor analysis, and applications, volume 75. Springer Science & Business Media, 2012.
Colson, B., Marcotte, P., and Savard, G. An overview of bilevel optimization. Annals of operations research, 153 (1):235- 256, 2007.
Agarwal, A., Dekel, O., and Xiao, L. Optimal algorithms for online convex optimization with multi-poin bandit feedback. In Colt, pp. 28-40. Citeseer, 2010.
Combettes, P. L.., Pesquet, J.-C., and Repetti, A. varia- tional inequality model for learning neural networks. In ICASSP 2023-2023 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5, IEEE, 2023.
Amini, A., Vieira, T., and Cotterell, R. Variational best- of-n alignment. Workshop Fine-Tuning in Machine Learning (NeurIPS)., 2024.
Conger, L., Hoffmann, F., Mazumdar, E., and Ratliff, L. Coupled gradient flows for strategic non-local distribution shift. arXiv preprint arXiv:2307. 00.00 166, 2023.
Başar, T. and Olsder, G. J. Dynamic noncooperative game theory. SIAM, 1998.
Coogan, S., Ratliff, L. J., Calderone, D., Tomlin, C., and Sastry, S. S. Energy management via pricing in lq dy- namic games. In 2013 American Control Conference, pp. 443 443-448. IEEE, 2013.
Bertsimas, D., Gupta, V., and Paschalidis, I. C. Data- driven estimation in equilibrium using inverse optimiza- tion. Mathematical Programming, 153:595 633, 2015.
Besbes, O., Gur, Y., and Zeevi, A. Non-stationary stochastic optimization. Operations research, 6355)::227-1244 2015.
Cutler, J.. Drusvyatskiy, D., and Harchaoui, Z. Stochas- tic optimization under distributional drift. Journal of Machine Learning Research, 24(147):1-56, 2023.
Borkar, V. S. Stochastic approximation: dynamical sys- 2009. tems viewpoint, volume 48. Springer, 2009.
Cutler, J., Díaz, M., and Drusvyatskiy, D. Stochastic approx- imation with decision-dependent distributions: asymp- totic normality and optimality. Journal of Machine Learn- ing Research, 25(90): 2024.
Bracken, J. and McGill, J. T. Mathematical programs with optimization problems in the constraints. Operations Research, 21(1):37-44, 1973.
Dasari, S., Kantarci, B., Pouryazdan, M., Foschini, L., and Girolami, M. Game theory in mobile crowdsensing: A comprehensive survey. Sensors, 20(7):2055, 2020.
Brown, G., Hod, S., and Kalemaj. I. Performative prediction in a stateful world. In International Conference on Artifi- cial Intelligence and Statistics, pp. 1045-6061. PMLR, 2022.
Daskalakis, C., Golowich, N., Skoulakis, S., and Zam- petakis, E. Stay-on-the-ridge: Guaranteed convergence
10

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
to local minimax equilibrium in nonconvex-noncoocave games. In The Thirty Sixth Annual Conference Learn- ing Theory, pp. 5146-5198. PMLR, 2023.
Fiez, T. and Ratliff, L. J. Local convergence analysis of gra- dient descent ascent with finite timescale separation. In Proceedings of the International Conference Learning Representation, 2021.
Davis, S. et al. The adverse feedback loop and the effects of risk in both the real and financial sectors. Federal Reserve Bank of Dallas Working Paper, 66, 2010.
Fiez, T., Chasnov, B., and Ratliff, L. Implicit learning dy- namics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In Interna- tional Conference on Machine Learning, pp. 3133-3144. PMLR, 2020.
Dean, S., Curmei, M., Ratliff, L.. Morgenstern, J., and
Fazel, M. Emergent specialization from participation dynamics and multi-learner retraining. In International Conference Artificial Intelligence and Statistics, pp. 343-351. PMLR, 2024.
Fiez, T., Jin, C., Netrapalli, P., and Ratliff, L. J. Minimax optimization with smooth algorithmic adversaries. arXiv preprint arXiv:2106.01483 2021a.
Dempe, S. and Zemkoho, A. Bilevel optimization. In Springer optimization and its applications. Vol. 161. Springer, 2020.
Fiez, T., Ratliff, L., Mazumdar, E., Faulkner, E., and Narang, A. Global convergence to local minmax equilibrium in classes of nonconvex zero-sum games. Advances in Neu- ral Information Processing Systems, 34:29049-29065 2021b.
Dong, J., Roth, A., Schutzman, Z.,, Waggoner, B., and Wu, S. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 55-70, 2018.
Foerster, J. N., Assael, Y. M., De Freitas, N., and Whiteson, S. Learning to communicate with deep multi-agent rein- forcement learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Dontchev, A. L.,, Rockafellar, R. T., and Rockafellar, R. T. Implicul functions and solution mappings: A view vrowfrom variational analysis, volume 616. Springer, 2009.
Fujita, S. and Fukao, T. Convergence conditions of dynamic stochastic approximation method for nonlinear stochastic discrete-time dynamic systems. IEEE Transactions on Automatic Control, 17(5):115-717, 1972.
d'Oro, S., Mertikopoulos, P., Moustakas, A. L.,, and Palazzo, S. Interference- based pricing for opportunistic multi- carrier cognitive radio systems. JEEE Transactions Wireless Communicationss 14(12):6536-654) 2015.
Ghadimi, S. and Lan, G. Variational inequalities for sup- port vector machines. In Proceedings of the 32nd Inter- national Conference Machine Learning (ICML), pp. 1011- 2015.
Drusvyatskiy, D. and Xiao, L. Stochastic optimization with decision-dependent distributions. Mathematics of Opera- fions Research, 48(2):954-998, 2023.
Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste- Julien, S. A variational inequality perspective on genera- tive adversarial networks. International Conference on Learning Representation, 2019.
Drusvyatskiy, D., Fazel, M., and Ratliff, L. J. Improved rates for derivative free gradient play in strongly monotone games. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3403-3408. IEEE, 2022.
Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial nets. Advances in neural informa- tion processing systems, 27, 2014.
Duchi, J. C., Jordan, M. I., Wainwright, M. J., and Wibisono, A. Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 11:2788-2806, 2013.
Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters. M. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp. 11 112_ 2016.
Duvocelle, B., Mertikopoulos, P., Staudigl, M., and Ver- meulen, D. Multiagent online learning in time-varying games. Mathematics of Operations Research, 48(2):114- 941, 2023.
Hardt, M., Jagadeesan, M., and Mendler-Dünner, C. Perfor- mative power. Advances in Neural Information Process- ing Systems, 35:22969-22981, 2022.
Facchinei, F. and Kanzow, C. Generalized nash equilibrium problems, 4or, 573):173- 2007.
Harvey, N. J., Liaw, C., Plan, Y., and Randhawa, S. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory. pp. 1579-1613. PMLR, 2019.
Facchinei, F. and Pang, J.-S. dimensiimml variational inequalities and complementarity problems. Springer, 2003.

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Hellemo, L., Barton, I,, and Tomasgard, A. Decision- dependent probabilitiess in stochastic programs with re- course. Compulational Management Science, 15:369- 395, 2018.
Lin, T., Zhou, Z., Ba, W., and Zhang. J. Doubly optimal no-regret online learning in strongly monotone games with bandit feedback. arXiv preprint arXiv:2112.02856, 2021.
Ho, Y-C.,, Luh, P. B., and Olsder, G. J. A control-theoretic view on incentives. Automatica, 18(2):167-179, 1982.
Liu, J. and Ratliff, J. Principal-agent bandit games with self-interested and exploratory learning agents. arXiv preprini arXiv:2412. 16318, 2024.
Hu, Z., Liang, Y. Zhang, J., Li, Z., and Liu, Y. Inference aided reinforcement learning for incentive mechanism design in crowdsoureing. Advances in Neural Information Processing Systems, 31, 2018.
Madden, L., Becker, S., and Dall' Anese, E. Bounds for the tracking error of first-order online optimization methods. Journal of Optimization Theory and Applications, 189: 437 457, 2020.
Huo, Z. and Huang, H. Asynchronous mini-batch gradient descent with variance reduction for non-convex optimiza- tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31 (1), 2017.
Maheshwari, C., Chiu, C.-Y., Mazumdar, E., Sastry, S., and Ratliff, L. Zeroth-order methods for convex-concave min- max problems: Applications decision deeendend risk minimization. In International Conference Artificial Intelligence and Statistics, pp. 6702-6734. PMLR, 2022.
Jin, C., Netrapalli, P., Ge, R., Kakade, M., and Jordan, M. I. A short on concentration inequalities for ran- dom vectors with subgaussian norm, 2019.
Maheshwari, C., Sasty, S., Ratliff, L., and Mazumdar, E. Convergent first-order methods for bi-level optimization and stackelberg games. arXiv preprint arXiv:2302.014221, 2023.
Jin, C., Netrapalli, P., and Jordan, M. What is local optimal- ity in nonconvex-nonee nonconcave minimax optimization? In International conference on machine learning, pp. 4880- 4889. PMLR, 2020.
Mangoubi, O. and Vishnoi, N. K. Greedy adversarial equi- librium: an efficient alternative to nonconvex noncooccaveee min-max optimization. In Proceedings of the 53rd An- nual ACM SIGACT Symposium on Theory of Computing, pp. 896-909, 2021.
Kelly, P., Maulloo, A. K., and Tan, H. Rate con- trol for communication networks: shadow prices, propor- tional fairness and stability. Journal of the Operational Research society, 49:237-252 1998.
Mendler-Dünnee C., Perdomo, J., Zrnic, T., and Hardt, M. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33: 4929-4939, 2020.
Kim, M. P. and Perdomo, J. C. Making decisions under outcome performativity. In 14th Innovations in Theoreti- cal Computer Science Conference (ITCS 2023). Schloss- Dagstuhl-Leibniz Zentrum für Informatik, 2023.
Kulunchakov, and Mairal, J. A generic acceleration framework for stochastic composite optimization. Ad- vances in Neural Information Processing Systems, 32, 2019.
Miller, J. P., Perdomo, C., and Zmnc, T. Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning, pp. 7710- 7720. PMLR, 2021.
Kusher, H. and Yin, G. Stochastic approximation algorithms and applications, 1997.
Miron, A. The economics of seasonal cycles, 1990.
Mokhtari, A., Ozdaglar, A., and Pattathil, S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020.
Kushner, H. J. and Yin, G. Stochastic approximation algo- rithms and applications. In Applied Mathematics, 1997.
Li J.. Yu. J., Liu, B., Nie, Y., and Wang, Z. Achieving hierarchy-free approximation for bilevel programs with equilibrium constraints. In International Conference Machine Learning, pp. 20312-20335 PMLR, 2023.
Monderer, D. and Shapley, L. S. Potential games. Games and economic behavior, 14(1):124-143, 1996.
Lian, X., Huang, Y., Li, Y., and Liu, J. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in neural information processing systems, 28, 2015.
Narang, A., Faulkner, E., Drusvyatskiy, D.,, Fazel, M., and Ratliff, L. J. Multiplayer performative prediction: Learning in decision- -eeeedenddeeendent games. arXiv preprint arXiv:2201.033% 2022.
12

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Narang, A., Faulkner, E., Drusvyatskiy, D., Fazel, M., and Ratliff, I., J. Multiplayer performative prediction: Learn- ing in decision-dependent games. Journal of Machine Learning Research, 24(202):1-56, 2023.
Sherali, H. D., Soyster, A. L., and Murphy, F. H. Mtackelbeggnash--ourre equilibria: characterizations and computations. Operations Research, 31(2):253-276 1983.
Perdomo, J., Zrnic, T., Mendler-Dünenn C., and Hardt, M. Performative prediction. In International Conference on Machine Learning, pp. 7599-7609, PMLR, 2020.
Stackelberg, H. V. et al. Theory of the market economy. Oxford University Press, 1952.
Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. Fast convergence of regularized learning games. Ad- vances in Neural Information Processing Systems, 28, 2015.
Pinto, I., Davidson, J., Sukthankar, R., and Gupta, A. Ro- bust adversarial reinforcement learning. In International conference on machine learning, pp. 2817-2826. PMLR, 2017.
Tatarenko, T. and Kamgarpour, M. Learning nash equilibria in monotone games. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 3104-3109. IEEE, 2019.
Ratliff, L. J. and Fiez, T. Adaptive incentive design. IEEE Transactions on Automatic Control, 66(8):3871-3878 2020.
Tse, D. and Viswanath, Fundamentals of wireless com- munication. Cambridge university press, 2005.
Ratliff, L. J., Coogan, S., Calderone, D., and Sastry, S. S.
Pricing in linear-quadratic dynamic games. In 2012 50th Annual Allerton Conference on Communication,, Control, and Computing (Allerton), pp. 1798-1805. IEEE, 2012.
Tsypkin, Y. Z. and Nikolic, Z. J. Adaptation and learning in automatic systems, volume 73, Academic Press New York, 1971.
Ray, M., Ratliff, L. J., Drusvyatskiy, D., and Fazel, M. Decision deeeedend risk minimization in geometrically decaying dynamic environments. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 8081- - 8088, 2022.
Tsypkin, Y. Z. and Polyak, B. Optimal recurrent algorithms for identification of nonstationary plants. Computers electrical engineering, 18(5):365-371, 1992.
Wardrop, G. Road paper. some theoretical aspects of road traffic research. Proceedings of the institution of civil engineers, 1(3):325 1952.
Recht, B., Re, C., Wright, S., and Niu, Hogwild!: A lock- free approach to parallelizing stochastic gradient descent. Advances in neural information processing systems, 24, 2011.
Westenbroek, T., Dong, R., Ratliff, I., J., and Sastry, S. S. Competitive statistical estimation with strategic data sources. IEEE Transactions on Automatic Control, 65(4): 1537-1551, 2019.
Rockafellar, R. Convex Analysis. Princeton University Press, 1970.
Rockafellar, R. T. Variational analysis of nash equilibrium. Vietnam Journal of Mathematics, 46(1):73-85, 2018.
Wood, K. and Dall' Anese, F. Stochastic saddle point prob- lems with decision-dependen distributions. SIAM J. Op- tim., 33:194331199 1967, 2022.
Rosen, J. B. Existence and uniqueness of equilibrium points for concave n- n-person games. Econometrica: Journal of the Econometric Society, pp. 520-534, 1965.
Wood, K. R. and Dall' Anese, E. Online saddle point track- ing with decision-dependent data. In Learning for Dy- namics and Control Conference, pp. 1416-1428, PMLR, 2023.
Ryu, E. K. and Boyd, S. Primer on monotone operator methods. Appl. comput. math, 15(1):3 43, 2016.
Xie, H., Lui, J. C.,, Jiang, W., and Chen, W. Incentive mechanism and protocol design for crowdsourcing sys- tems. 2014 52nd annual Allerton conference on com- munication, control, and computing (Allerton), pp. 140- 147. IEFF, 2014.
Scheid, A.. Tiapkin, D., Boursier, E., Capitaine, A., Mhamdi, E. M. E., Moulines, É.,, Jordan, M. I., and Dur- mus, A. Incentivized learning in principal-agent bandit games. International Conference on Machine Learning, 2024.
Yang, J., Li, A., Farajtabar, M., Sunehag, P., Hughes, E., and Zha, H. Learning to incentivize other learning agents. Advances in Neural Information Processing Systems, 33: 1520911529,, 2020.
Shah, N. B. and Zhou, D. Double or nothing: Multiplicative incentive mechanisms for crowdsourcing. Journal of Machine Learning Research, 17(165):1-52 2016.
13

---

Finite-Timg Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Yang, J., Wang, E., Trivedi, R., Zhao, T., and Zha, H. Adap- tive incentive design with multi-agent meta-gradient rein- forcement learning. Procedings of the 2t International Conference on Autonomous Agents and Multiagent Sys- tems (AAMAS), 2022.
Yang, T., Mei, J., Dai, H., Wen, Z.,,Cen Cen, S., Schuurmans, D., Chi, Y., and Dai, B. Faster wind: Accelerating iterative best-of-n distillation for Ilm alignment. arXiv preprint arXiv:2410.20727, 2024.
Zhang. G. and Wang. Y. On the suboptimality of negative momentum for minimax optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2098-2106. PMLR, 2021.
Zheng, L., Fiez. T., Alumbaugh, Z. Chasnov, B., and Ratliff, L. J. Stackelberg actor-critic: theoretc reinforcement learning algorithms. In Proceedings of the AAAI conference on artificial intelligence, pp. 9217-9224, 2022.
Zhou, Z., Mertikopoulos, P., Athey, S.,, Bambos, N., Glynn, P., and Ye, Y. Learning in games with lossy feedback. In Proceedings of the 32nd Conference on Neural Informa- tion Processing Systems (NeurIPS), pp. 1-11, 2018.
14

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Organization of Appendix
The appendix contains many sections, so here we provide a contents list to help the reader navigate the material.
Appendix SA: Related Work. This section contains discussion of related work
Appendix SB Extended Discussion. An extended discussion section containing implications for future work and proposed directions.
Appendix $C: Examples of Monotone Games. This section contains examples of monotone games.
Appendix $D: Numerical Experiments. Illustrative numerical experiments exploring both the limits of the theoretical results as well as semi-synthetic real-world simulations.
Appendix SE: Technical Lemmas. Technical lemmas used to prove the thcoretical results.
Appendix SF: Regularity of the Equilibrium Response. Exposition on the regularity assumption on the equilibrium response of agents.
Appendix &G: Contracting Agent Updates. Examples (and proofs) of p-contracting learning rules.
Appendix SH: Proof's for Oblivious Decision-Maker Setting. Proofs for all the theoretical results for the setting in which the decision-maker is obliviously deploying sequence of actions.
Appendix $I: Proofs for the Naïve Decision- Maker Setting. Proofs for all the theoretical results for the setting in which the decision-maker is naively deploying sequence of actions generated by running a repeated stochastic gradient method.
Appendix şJ: Proofs for the Strategic Decision-Maker Setting, Proofs for all the theoretical results for the setting in which the decision-maker is strategically deploying a sequence of actions that are selected via a derivative free stochastic method that allows the decision-makee to optimize through the smooth algorithmic response of the agents.
A. Extended Related Work
Asymptotic equilibrium tracking is a long studied problem in single player stochastic optimization and stochastic approxi- mation; see (Borkar, 2009; Kusher & Yin, 1997) and references therein. Our work focuses on obtaining convergence rates when the decision mobsionnmmake maker faces a time-varying stochastic optimization problem subject to equilibrium constraints that are themselves varying in time. Below we highlight the most relevant work in this broad field, focusing on recent developments.
Static Performative Prediction. The decision-maker's problem is analogous to the setting of performative prediction, first introduced in Perdomo et al. (2020), in the sense that the decision-maker faces a stochastic optimization problem where the distribution describing the environment depends on the actions of the decision-maker. Performative prediction, in turn, shares many features with the earlier work on stochastic optimization with decision- -eeeedend probabilities (Hellemo et al., al., 2020). Numerous recent papers have developed
2018) and strategic classification (Hardt et al., 2016; Mendler-Dünne algorithms and convergence guarantees in different performative prediction settings (Brown et al., 2022; Cutler et al., 2024; Drusvyatskiy & Xiao, 2023; Maheshwari et al., 2022; Mendler-Dünner et al., 2020; Miller et al., 2021; Narang et al., 2022).
In particular, Gendler-Dünnee et al. (2020) develops the first stochastic optimization algorithms within the performative prediction setting. The subsequent work by Drusvyatskiy & Xiao (2023) reveals that all the typical stochastic optimization algorithms used in the classical static setting extend directly to the performative setting with no loss in efficiency. The work Cutler et al. (2024) moreover shows that the basic stochastic gradient method asymptotically achieves the best possible sample complexity among any estimation procedures.
Recent work by Conger et al. (2023) extends the specific sub-problem known as strategic classification to functional spaces by way of optimal transport in order to analyze the effects of the entire distribution (as compared to the mean) as function of the decision-made maker's s action. Another interesting direction explored Narang et al. (2022) wherein the authors extend the performative prediction problem to multiple players and characterize the Nash equilibrium. Finally, work from Wood Dall' Anese (2022), which finds equilibrium points that are analogs to performatively stable points.
15

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Time-Varyine Stochastic Optimization & Performative Prediction. Of the recent work on performative prediction, the most closely related work focuses on performative prediction problems that change dynamically over time in response exogenous changes in the environment. This is in contrast to classical online tracking work (Fujita & Fukao, 1972; Kushner & Yin, 1997; Tsypkin & Nikolic, 1971; Tsypkin & Polyak, 1992), which, despite using several modern techniques and objectives such as accelerated gradients (Madden et al., 2020) and dynamic regret (Besbes et al., 2015) respectively, does not capture decision-dependence in the environment's 's drift.
Brown et al. (2022) introduced the notion of dynamics in the performative prediction problem through repeated risk minimization. Ray et al. (2022) introduce novel epoch-based algorithms for performative prediction when the environment is subject to geometrically decaying dynamics.
There has also been a recent surge on the empirical front in related fields such as recommendation design when the decision-maker recognizes that the user pool may be reactive (Cen et al., 2024). Cutler et al. (2023) provides convergence rates for gradient- based stochastic optimization methods over time-narying decision-dependent distributions. Wood & Dall' Anese (2023) develop a similar analysis for zero sum games, and provide bounds on tracking stochastic saddle point cquilibrium. Finally, (Cen et al., 2024) studies performative and strategic effects in recommendation systems, and provides a theoretical model to study user strategization along with an empirical study.
Of these, the analysis in (Cutler et al., 2023) is most closely related to our work, especially in the oblivious decision-maker setting. We extend the analysis in that paper to strongly monotone games. Further, none of these works considers the Stackelberg setting in which the decision-maker (leader) faces multiple competing agents (followers) who are themselves learning and adapting.
Bilevel Optimization & Stackelberg Games. There is vast work on bilevel optimization and Stackelberg games (Başar & Olsder, 1998; Bracken & McGill, 1973; Colson et al., 2007; Dempe & Zemkoho, 2020; Stackelberg et al., 1952); the specific work most related to this paper focuses on settings where the agent problem is an equilibrium problem or variational inequality. In this setting, the literature is specialized to mathematical programming with equilibrium constraints. Prominent examples include settings where leader optimizes over the outcome of a Cournot game (Sherali et al., 1983), or Stackelberg congestion games (Wardrop. 1952).
Typically it is assumed that the decision- maker has full knowledge of the agent game can control the agent game through multiple specialized queries such as in recent work (Li et al., 2023; Maheshwari et al., 2023). There has also been work on incentive design when facing multiple adaptive agents such as (Ratliff & Fiez, 2020; Yang et al., 2020; 2022); however, the can estimate the preferences of the agents, can compute
majority of this work makes the assumption that the the a priori optimal solution to use as a benchmark, gives asymptotic convergence guarantees, or provides empirical results. In contrast, our work does not assume that the decision-make has any knowledge of the agent preferences or update methods beyond belonging broad contractive update class.
B. Extended Discussion, Implications for Future Work, and Proposed Directions
We consider a novel class of stochastic Stackelberg games, where updates from the mecesion-maker and the agents induces a time-varying game for both parties. We present finite-time efficiency estimates that are governed by the drift-to-noise ratio for the agents' updates for settings where the decision-make sequentially deploys actions. The results motivate future work on better characterization of the tradeoffs in the performative gap and in sample complexity as this helps determine the most efficient class of algorithms to run in information limited settings.
We also identify two epoch-based algorithms that find two different notions of equilibria, the performatively stable Stackelberg equilibrium and the true Stackelberg equilibrium. We characterize the existence of the former equilibrium, and establish convergence rates. Illustrative numerical examples explore the theoretical assumptions and suggest many interesting directions for future work.
Performative Gap vs Sample Complexity. Indeed, the results motivate future work that captures the interplay between game theory, optimization, and learning. Better characterizing the tradeoffs in the performative gap. both in l4 as well as in cost, and in sample complexity is essential across a number of performative prediction settings. Additionally, having a better characterization the extent of performativity exists in a stochastic optimization system would enable decision decision-makers makers to determine which algorithmic approach (i.e., computationally expensive derivative free methods versus sub-optimal repeated
16

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
stochastic methods) is beneficial given the reactivity of its base.
Designing Adaptive Parameter Estimation Methods. Our theoretical results also depend on a number of intrinsic parameters such Lipschtiz constants which may not be readily available in practice. This suggests developing adaptive algorithms for learning in game-theoretic settings such as the ones explored in this paper. In the game theory literature, there are few adaptive methods in part because extending traditional methods from single-player optimization would require coordination, however, there is recent work on adaptive methods in distributed setting for monotone variational inequalities which can be leveraged.
Methods for Estimating Opponent/Agent Models using Adaptive Control. Finally, we examine the two extremes in terms of estimating the performative effects on the loss of the decision-maker. Indeed, recall the gradient decomposition from Equation 1:
E 2~D(u)
vullu,2)
E A(u, =)
de s~D(v)
where the second term is the derivative of the loss through the reaction of the agents (and the non-strategic decision-dependern component of the environment). We examine what happens when the decision- maker updates by ignoring the reaction of the agents in its gradient and, at the other end of the spectrum, when the mecision-maker estimates-via a derivative free method- the second term in (I). There is natural intermediate formulation in which the decision maker models the Duu) with sufficiently rich function class. For instance, in prior work by Ratliff & Fiez (2020), in the context of adaptive incentive design the authors model best responding agents via reproducing kernel Hilbert spaces (RKHs)-which are known have desirable properties such as persistence of excitation. particular, the cost functions of the agents' are estimated via RKHS. Then, using the estimated costs, they constrain the incentive design problem to ensure that the (estimated) game amongst the agents has positive definite Jacobian (Daw(x, u) > 0) which is sufficient condition for strong monotonicity. This requires an assumption on the model class being expressive enough to capture the true cost functions; the challenge here is that the model could course be miss-specified, and this assumption is not a priori verifiable. Hence, what is needed some uncertainty quantification or distributional robustness on top in order to give guarantees. This an interesting direction of future research.
C. Examples of Monotone Games
In this section, we provide several examples of strongly monotone games. Before diving into some examples, let us give some intuition for strong monotonicity via sufficient conditions, and discuss challenges related to relaxing this assumption.
C.1. Strong Monotonicity of Agent Game
Recall that Assumption 1.i Here we explore the strength of this assumption. In particular, this assumption requires that the decision maker is only deploying w's such that the agents game is strongly monotone. A sufficient condition for this game to be strongly monotone for a given u is that the game Jacobian is positive definite:
Vift
V12fT
V In
V21
Ja(x)= =
> 0.
fu (n- fu n-1
Nn(-1))
22 ru
is instructive to see what this implies via an example. Consider a revenue maximization game amongst the players
A 11..11
A
ft (x1, = (Ani; Ai.irr & + u.) x4+
here u, some demand signal to correct for the implicit bias agent á has about the demand.
For simplicity let's consider the player case:
Wh (x) (Vifi', V2f2) = ((2An +1 + E3 + un + A1232, (2Azz + >21) + Ea + u2 + A2121)
17

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Ju(x) = 2A11 +
Anl
A12 2A² + A21
A21
Then,
/ (Ju( 2A +
A12 + Ag 1 + A21 2A2 + X²
Then as long as the game when = 0 is strongly monotone, so is any induced game.
Prior work by Ratliff & Fiez (2020) on adaptive incentive design with simultaneous utility estimation incorporates this condition as a constraint on the optimization problem (for choosing the next uy). One direction for future work is specifying the space of U via a similar radial basis function method as in Ratliff & Fiez (2020), and then characterizing the additional constraint to be added to the spoch-based algorithms we propose herein. If this expansion results in a closed, convex set U, then our results will apply and the decision-maker will only be choosing actions u that retain strong monotonicity of the agents' game.
C.2. Challenges to Relaxing Strong Monotonicity
Relaxing the monotonicity assumption leads issues of not just non-uniqueness but especially non-existence of solutions (Facchinei & Pang, 2003; Rockafellar, 2018). To our knowledge there are not solution concepts for Stackelberg problems over monoooooe games. The rich literature on non-convex, non-concave zero sum games, especially in machine learning, is illustrative of the challenge which is only exacerbated by the lack of structure in general sum settings. In particular, there are many different local solution concepts and no one in particular that is widely accepted zero sum settings (Daskalakis et al., 2023; Fiez et al., 202 la;b; Jin et al., 2020; Mangoubi & Vishnoi, 2021), and very few in general sum settings (Fiez al., 2020).
There two natural methods of defining solutions:
1. assume a locally monotone structure, or
2. define solution concept with respect to the algorithm class (or regularizer) adopted by the agents.
The first option demands the novel analysis in this paper for monotone settings as that is what is exploited locally around the equilibrium to obtain convergence. The main technical concerns beyond the analysis in this paper are then ensuring saddle point avoidance and characterizing the lock in probability guaranteeing that the combined learning behavior remains in the appropriate local neighborhood- see the appendix of (Fiez et al., 2020) for asymptotic analysis that is illustrative. Essentially, it is necessary to bound the probability that iterates will get locked into neighborhood around the equilibrium which can be more difficult in general sum settings without a lack of the equilibrium landscape outside the region of attraction, itself a difficult concept to characterize without local structure (e.g., bounds on the game Jacobian (w)(
The second option arises from the fact that most methods for solving mon-monotone inequalities derive algorithms that leverage regularization (e.g., Tikhonov regularization popular (Tatarenko & Kamgarpour, 2019)), and then define a solution concept relative to a performance gap notion that depends on this choice of regularizer. This dissatisfying in game theoretic sense it requires the agents coordinate on the choice of regularizer and then it gives no guarantees with respect to the incentive structure of the agents objectives. That being said, there may be interesting future research on understanding the relationship between algorithms adopted by strategic or learning agents and their underlying objectives and incentives.
C.3. Quadratic Games
Consider the game defined by costs
fi(1,, x =
3z A B;
B
x;3
+
a;
T
(3)
2 x=
D:
x-i
b;
x-
where A; E Rd D; E xd- Bi E Rdd-xdd, a; E dd and b, E dR with A₁ = AT and D; DTT. Further, we assume that A; > 0 for each = 1, The Dj matrices penalize player based solely on x- and may often be negative or zero. Quadratic games are a useful approximation of the behavior of more complex games around an equilibrium. This game is strongly monotone if there exists μ E (0, 20) such that
(w)x) (((x), x - x') 2 1|| x'
18

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
where
w(x) (Vi/(c)), v.,n(x)) with V.fi(mi,z-:) Asrz + B.T x-s 04-
sufficient condition for strong monotonicity
Bu
A1
B12
Bin
B21
A2
Bi(i-1)
J(x) Vw(x)=
> 0,
where B;
Bi(i+1)
B(n-1)n
BA
B1(n-1)
An
Bin
There many important examples of quadratic games in economics and control theory. Below we highlight few.
C.3.1. OPEN LooP LINEAR QUADRATIC DYNAMIC GAMES
One important class in control theory is that of linear quadratic dynamic games in open loop strategies. For simplicity, we write out the details for a n player game; however, these derivations easily extend to arbitrary but finite n. To that end, consider a two player linear quadratic dynamic game with open loop policies V; = (vt,0.... U,, with costs
T-1
1 Tiz
A(V1, v2) Σ 1=0
T 2 2 R.n,a + - + 2
2
2++ = F& + G1 + G202,1 2 E R
Unfolding the dynamics and letting Z [20
2T T we have that Z Wiv1 + W2v2 + F20 where
0
0
G
0
FG:
G;
0
0
W
i i= 1,2,
FT-
FT-3G,
G;
0
FT-1G;
FT-2G;
FG;
G
and F = [I FT
(FT-1)T (F")
Define the following cost matrices:
Q = diag Qi Qi,)) E
R. diag( R R.) A.TxTT
R - = diag R......... Ri,-1) E RdTxd.IT
Player i's cost is
f(V1, = 1v, R.v, R. (Wiv, + W2v2 + F2o) T Q:(Wiv: + W2v2 + F2o).
Mapping back to the original quadratic cost form in (3), we have that
A; = R, + W.T. Q,W,
B, = (R.-i+ H.TTTTTWW.. D D==IIQW__
T 5o F Q.W,
bf = = F
The game Jacobian is given by
A B
BT
R + WTQ,WW W,
RR + VTQQ
(
Aq
(R2,1 + W.J Q2Wi)
RS + W. Q2
In typical linear quadratic regulator problem it is assumed that R, > 0 and Q, 2 in order for solutions to exist (there are conditions that weaken these assumptions), and hence A, > In this case A, non-degenerate for i 1,2, and hence
19

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
sufficient condition for the game Jacobian be positive definite is checking that either Schur complement is positive definite.
The goal of a decision- maker here might be to design 'pricing mechanisms' to influence the equilibrium; e.g., they may optimize over the matrices (R,, R -i) (Coogan et al., 2013; Ratliff et al., 2012).
C.3.2. COURNOT AND BERTRAND COMPETITION
Both Cournot and Bertrand oligopoly models are monotone games under certain conditions on the cost parameters. In the Cournot model, firms choose quantities in non-cooperative competition, and the market determines the price of each good. On the other hand, in a Bertrand competition, firms set prices, and the market determines its demand for each type of good.
To see that these games are both strongly monotone, consider a setting with firms.
Cournot Competition. Each firm supplies the market with a quantity I; E [0, B,] of some good or service where B, >> 0 is firm i's capacity for production. The market determines the price P(x) for the good, where the pricing mechanism here P(.) typically a decreasing function of the total supply to the market 1 [T> x >i= Iz. For example, a commonly adopted model is a linear pricing function of the form
P(x) 9
Σ Fbi
where r, 0.
(4)
The i-th firm aims to maximize their utility which is given by - P(x) - C, Here, the first term x; x;P(2) the revenue generated from selling 2; goods the market and the second term 6527 is the cost of production.
Consider the game with costs f((x) (x) over strategy spaces X; [0, B,]. The game is strongly monotone if there exists μ 0 such that
11 V(()) P(x) +a
P(x)) P(x)) +
(w)xx) w(x'), x2)
20 x
IA (T)(() - P(x) + co.
VnP(''
-P(x)) + cn
21 P(P)) + +
P(xx) + P(x')
, x'
TA v()))) + V. P(x) + P(a')
2 p - 1'|
Using the linear form of P(x) from (4), it is easy to compute
x1
x'
(w(x) - w(x'), x²)
+
In
xnn
2n z'n
Ei I2 E x
In
Σ (xt 11)2 + 4 Σ Σ (xy
23)( - 212)
2
=//l= 2'12 +
Σ (z+ - x1/)
-x1)
2 1/1x - 2112
so that the game is strongly monotone with μ > O. In a Cournot competition, the market reaches an equilibrium where all firms choose a quantity that is their best response to their competitors' quantities. This turns out to be an inefficient equilibrium, in that the equilibrium price is above the price in perfect competition and therefore firms earn a profit. third party (such as government entity) may intervene in the market by modulating the price P(z) or by taxing individual firms (thereby increasing the cost of production qæ2:) in order to move the market to an efficient equilibrium.
20

---

Finite-Tims Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Bertrand Competition. In Bertrand competition, where prices are the strategic variable, firms are incentivized set incentivized, they repeatedly drop the price until the
their price slightly lower than the competition. Since all firms price reaches the price in perfect competition wherein firms do not earn profit. A third party may intervene in this market to improve uncertainties related to forecasting demand. For example, often times demand depends on exogenous time varying quantity or signal, such as gross domestic product, for which an individual firm may not have a good (low variance) forecaster.
To illustrate this, consider again n firms, but now the strategies 24 E [0, B.] are the prices instead of quantities of production. The firms seek to maximize their revenue in this setting which is given by (2,,, - u) 2, F J- u) where F; is the marginal revenue function or demand curve given prices (Iz; x-)). Here is some exogenous signal as described above. Then, for fixed we have that
(w< u) w('', u), x') (-I, u) Fi(z, (- V-
Fi(x', u)), x->) x')
so that, just like with the Courno competition, if the marginal revenue is affine function with parameters (r, g) then the game is strongly monotone with μ q- The marginal revenue function, however, does not have to be linear for the game to be strongly monotone. Indeed a common form for the marginal revenue includes logarithmic terms (Bertsimas et al., 2015; Ratliff & Fiez, 2020). For instance consider marginal revenue function given by
(a, u) = log(z;; + 0 x + E + ui,
where (0;, Et) are parameters. Therefore we have that
<
- (logg(x)) ) + 20,,1 + -1,-11111) + (log(x1) + -201,1z4 + +01,-1
(w(xx,) u) - w(x', u), x²)
2 x
(log(r,)) 101,1 + 01,- - + (log(z))) + 20 + 0 On.-nz-n
sufficient condition for strong monotonicity is that the game Jacobian is positive definite. The game Jacobian is given by
--20,,
-01,2
01,m
m1
-02.1
-20,.2
v)(
6n,1
(n-nn 1)
28
For the game Jacobian to be positive definite the prices have to be strictly positive, and there are constraints on the parameters 9. One interesting question if there is a natural mechanism that a third party could use to shape the game in order to ensure is positive definite; in the example above, since u, enters linearly in the marginal revenue, it does not directly shape the game. However, e.g., u, was a tariff affine in z,, such as a,T, + b,, then the diagonal terms of the Jacobian would be and the third party could design a; ensure monotonicity.
-00,, 2a, zt
C.4. Strongly Convex Potential Game
game G = (fi....,fa) is called potential game (Monderer Shapley, 1996) if there exists a potential function
: X R such that
[( M((r(,=1)) ((1,, (1 ViE [n), Vr E X, of E X4.
If the potential function & is p-strongly convex, it follows from convex analysis that the game is p-strongly monotone (Rockafellar, 1970). The following is example of such game where there is natural decision maker influencing the outcomes.
Example: Power Control in Shared Wireless Channel. Another interesting class which has similar structure to the Kelly auction is power control for shared wireless channels (d' Oro et al., 2015; Duvocelle et al., 2023; Facchinei & Kanzow, 2007; Tse & Viswanath, 2005). Consider n wireless users that aim to transmit a set of packets to a common receiver over a set S of shared wireless channels (subcarriers). The aggregate received signal ys over the s S subcarrier is
yz
hi, +
21

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
where St, the transmitted signal of user over the s-th subcarrier, Ai. is the corresponding channel coefficient, and Rg is the aggregate interference-plus-noee
received from all sources not in [n] and for which we have that 2, (V, is Gaussian random variable. The average transmit power of user i on subcarrier is Zi,e B and each users total 0. Then the strategy space of user is
power 2; satisfies z; Σ. Fs,e I P. for some P, >
X; = 24 EE R
and EE. P
Vi,
SES
Each users transmission rate is given by Shannon's formula:
2= = Σ log (1 (t,())) = =
log (o? + wx(x)) - log
SES
SES
where (x) Eie(m] Me, Ti,s for each & E S and such that s/ is the channel gain of user over subcarrier s. Additionally, the term
|hr,0l2 Fi,s
(() o3 o2+ 22,,
is the signal-to-an to--nferennceandee and-noise ratio. The network operator (decision- maker)) aims to design a pricing scheme for the channel so as to induce an efficient equilibrium. For example, in a cognitive radio scenario the users described above are secondary users that are free riding on the network and cause interference on the primary users and therefore the the network operator needs to ensure that the system's 's users meet the quality service guarantees that they have already paid for typiccllyy in the form of minimum rate requirements or maximum interference tolerance per subcarrier. How this is achieved is by designing a pricing mechanism that consists of flat spectrum access price mo R RS R. and user specific price T, X, + R. Thus user i's utility is given by
(x) = (x) - (ww + xx;)))
where w = (Wi,.... W.).
This game admits an exact potential function (d'One Oro et al., 2015):
(xx) = Σ
log(o o + w.) - To(w) Σ T((x))
SES
KE[n]
To align with economic considerations on diminishing returns, it is common to assume that the pricing functions mo and each Iy is non-decreasing and convex in each of its arguments, and they are Lipschitz continuous. This ensures that ((x) is concave (though not necessarily strongly). Some regularization of the potential function would ensure its strongly concave but would induce different set of Nash equilibrium than optimizing It is interesting see how much regularization introduced impacts the difference between the induced sets of equilibrium.
C.5. Kelly Auction: Resource Allocation Mechanisms
Resource allocation problems are another interesting class of games that can be strongly monotone games. Consider a service provider with a number of divisible resources E S {1, 2,.... m). These resources could be things like server time, bandwidth, ad space, amongst many other divisible resources. Now, suppose there are agents which these resources can be leased. Each agent i submits a (monetary) bid (#:1..... Fim E R for the resources; call the joint set of bids 2n) E Rmm. The bids are non-negative and satisfy a budget constraint for each agent: E.es Li,s S b, for some b, E 0o).
common mechanism for allocating resources in this setting is the Kelly mechanism (Kelly et al., 1998). Under this mechanism, each agent receives an amount of resource in proportion their bid, pro-rata percentage of the other agents' bids. That is, each agent receives
Fi
P%. (x)
+
Σソ=1 Zio
units of the resource s. Here, the parameter g, is the total available units of resource s and ug is the barrier to entry for (uI...., Um) E mmm.
22

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
10"
10
10
10
10
10"
1
= 1000
== 1000
== 500
10
=
10
t= 10
== 10
1
|x
10
10
T=
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Ilerations
tteraioons
(a) RGM with SGP Agents for Different т.
(b) DEM with SGP Agents for Different 7.
Figure 6. Effects equilibrium convergence: explore the effect of the decision
cedision-maaer' maker's choice of the ultimate equilibrium a convex quadratic game. As expected the larger 7 is, the smaller the equilibrium error.
Altogether, can define the loss for each agent as
122
(21, =
Σ
(asp% (x) -is))
The strategy space of the i-th agent is X; = { E TRT Ex= Tis S b:}. Using analogous analysis to (Lin et al., 2021), easy to see that this game is j--ttoonlyy monotone with
min; { U.
max a;
3
E Ug + Σラ= by)
If the choice of the dicisiinnmmkee is the floor prices =u,).. then they can control whether not the game is strongly monotone.
D. Numerical Experiments
Code is available
In this section, we present numerical examples that are aimed at exploring the limits of the theory, and numerical examples that explore applying the theory semi-synthetic simulations based real-world data. In particular, data to create semi-synthetic experiments for price setting in ride-share markets. We explore two decision-maker actions: providing demand signal to shape the equilibrium outcome, and modulating the price (via taxes or incentives) to estimate the price elasticities.
real-worke
In the subsections that follow, we first explore the choice of which is a parameter that the decision-mann gets to set, depends on instance dependent quantities related to the agents' game which in practice may not be a priori known. We show that even if is set modestly, convergence is still possible. A future direction of research is developing adaptive methods estimate key quantities. Next, explore relaxing the regularity assumptions made the agents' game (monotonicity) and on the recision-maker loss (convexity). We show that the dacision-mmker can control whether not the agents' game is strongly monotone through their action, and that local convergence is possible in the absence of convexity. Future directions consider designing constraints on the decision-maker problem to ensure monotonicity, and local convergence results in the absence of convexity. We also comment on the key challenges that arise thcoretically when these assumptions on regularity are relaxed. Finally, we explore syniheynthetic real world examples that leverage data from ride-share markets.
D.1. Effect of Choosing 7 without priori Knowledge of Agent Game Parameters
In practice, the decision-maan maker may not have access to the precise constants that determine the theoretically correct choice of the epoch length since some of these constants are determined by the private cost functions of the agents. In this section,
23

---

and where (x, u) belongs to quadratic family of incentives, e.g., of the form 0z(2, u) = x xQ + x Rau + 9.f x. The goal of the decision maker to design the input u = (WI,..., un)) E R2 such that the agents converge to desired equilibrium (z*,, v²). For instance, if the decision-makke maker's loss is Eg ((u, {)), then (2 u²) may be defined as able control both and In the examples Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
explore the choice of on the tracking error of the agents' equilibrium relative the appropriate equilibrium-namel, the performatively stable equilibrium if the decision-maker employs the repeated gradient method (RGM) and the Stackelherg equilibrium if the perisioonmakee employs the derivative free method (DFM), To conduct this exploration, we generate random quadratic game instance where the decision-maker is deploying actions to with the objective of tracking a desired equilibrium. The decision-maker may not know the agent game-related hyperparameters a priori and thus may not be able to set r optimally as noted. Each player has cost
1 T A.,, B + cj x, (1, for i [m]].
fa(, = 2
the globally optimal tuple for the decision-maker loss as if they consider in this section, we let (x = be so defined for a randomly generated convex loss & and we let the decision-maker optimize the auxiliary loss Bę-D. [||=r 2²122 + ||u n x| where x is generate by the agents' algorithmic response to In the accompanying code-base, the parameters of the game can be changed.
Figure demonstrates that even if the recision-maker does not know the constants that define the optimal T (since these are related to the agent game instance), there are choices of for which the decision-maker's algorithm still converges. Perhaps surprisingly, it shows more specifically for the quadratic game instance we consider, that suffices to pick T meaning the agents only perform one update of their action in each round. That being said, the choice of impacts the convergence rate can be seen in the plots: larger results in faster convergence expected, but the benefit of increasing is marginal after a certain point. The reader can explore different game instances by modifying the provided code base.
D.2. Relaxing Regularity Assumptions
We also consider numerical examples from Kelly auctions from economics. Here, we explore synthetic Kelly auction between two players participating in the auction, where the amount bid is influenced by the marginal utilities of the competitors as well as the actions from the decision-maker.
1.2.1. KELLY AUCTION GAME FORMULATION
Consider a service provider with a number of divisible resources E = (1, m]. These resources could be things like server time, bandwidth, ad space, amongst many other divisible resources. Now. suppose there are n agents which these resources
be leased. Each agent i submits (monetary) bid xı (Ia1,-..; Fim) E T for the resources; call the joint set of bids (Zi,..., Z..) mmm The bids are non-negative and satisfy budget constraint for each agent: E.es Ti,s I b; for some b, E [0,
common mechanism for allocating resources in this setting is the Kelly mechanism (Kelly et al., 1998). Under this mechanism, each agent receives an amount resource in proportion to their bid, as pro-rata percentage of the other agents' bids. That is, each agent receives
Lo 2j=1
Pid (i.(
Ug
Zj
units of the resource s. Here, the parameter 9s is the total available units resource s and u, is the barrier to entry or floor price for u = (u,,..., um) E 1
Altogether, can define the loss for each agent as
f1, - Σ (a.pH -.te).
The strategy space of the i-th agent is X; {a; RT Σ. Iis b.). Using straightforward analysis of the eigenstructure of the game Jacobian (x), it is easy to see that this game is u-strongly monotone with
min, (g.u.)
# max 03
Eme + Σラ= by)
24

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
(aice Boor ant)]
01 jpice snt] I
My O price foor s- p
2g 02 (pice bo 6.3 10
1.0
100
unsiabbe
02
XL: bilyyrr amount on 611]
FL1 pilyerr anouun on 271]
Ph:: [pbyer1 aroount on 1-1]
AL: briyer a aamounton p013
(a)
(b)
(c)
(d)
Figure 7. Decision-maker equilibrium landscape design in a two-player Kelly auction: projected phase plot for the dynamics of the induced game. The markers indicated different candidate equlibriummnameed where (a) = - for E int((²). Arrows indicate the arrows are pointing towards an equilibrium, then those are
the direction of the gradient flow relative to the equilibriumnnmmely gradient directions which are attracted to the equilibrium. The magnitude is indicated by the color spectrum. In this example, explore saddle node bifurcation in terms of varying U1. In (a-b), U1 is negative, making the agents' game not strongly monotone; here, we find local optima, single stable Nash and a saddle point. In (c-d), as un becomes non-negative, the problem becomes strongly monotone, with only a single stable Nash. This demonstrates how the choice of decision-maker action can control the equilibrium landscape.
This has been shown in prior works including that of Lin et al. (2021). If the choice of the decision-maker the floor prices M (ux,) s: then they can control whether or not the game is strongly monotone.
On the decision-maker side, there are many potential cost functions that reasonable. For example, the auctioneer may care about maximizing their revenue and therefore their cost is
7
Lee (u)
FisPi.(
Alternatively, the dacesion-maker may care about the total agent welfare in which case their cost is given by
Lwett (u) (x) - --) Σ Σ (aip%, (x) xis).
We note that in general, the dacksion s objective is not strongly convex in u; accordingly, this makes simple Kelly auctions useful framework for characterizing the strength of our various assumptions.
D.2.2. EFFECT OF DECISION-MAKER ON MONOTONICITY AND AGENTS' EQUILIBRIUM LANDSCAPE
A decision-maker may alter the structure of the auction for example, changing the barrier to entry or levying a subsidy or tax on the agents-to encourage behavior that aligns with desired outcome. such as revenue maximization for the auctioneer or welfare maximization for the participants. Indeed, let us demonstrate how a deccision-maken action can induce monotonicity. Within the notation of our example, consider a setting where the decision- selects u; in other words, the decision-maker intervenes by changing the barrier to entry (floor price) in the auction. In this synthetic example, we consider Kelly auction of m resource types and define the auction's 's parameters as
a = ] 1]. q = 1].
and b = [10 10]
Accordingly, the constraints on the agents' action space can be characterized as E. 2z,e S b, and 2i,8 2 0 Vi, Recall that the Kelly auction strongly monotone when
min, (g.
max aj - (u) + U2 + by + 62
> 0.
Define the decision-maker's maker's action i1 controls strong monotoncity. Figure 7 demonstrates the degree to which the game monotonicity (and thus,
maker's action u as u = [ui 1]. and note that min, ( = min (u, 1). Accordingly, the decision-
25

---

Finite-Timg Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
DFO vs. RGM, Revenue
Price Ficor, Revenue
-0.50
DFD RGM
DFO RGM
-0.75
1.8
-1.00
Proce Ploor
-1255
1.4
-1.00
-1.75
1.2
-2.00
Run
Run
1.0
25
50
100
125
150
175
26
50
75
100
125
150
175
Epochs
Epochs
(a) Optimizing Lev: Losses.
(b) Optimizing Levi price floors.
DFO RGM, Welfare
Price Floor, Welfare
0.2
RGM
2.05
RCM
0.0
-0.2
Loss
-0.4
Run
1.90
Run
1.85
Run 4
Avg.
1.80
-0.8
125
Epochs
Epochs
(c) Optimizing Leer: Losses.
(d) Optimizing Cuett: price floors.
Figure Local convergence in non-convex Kelly Auction optimizing for agent welfare or auctioneer revenue. We simulate convergence over five distinct random seeds. In (a), we find that DFO tends to find local Stackelberg equilibria with lower cost than local performatively stable Stackelberg equilibria found by RGM when optimizing Lev, and (2) confirm that these equilibria are distinct. For similar experiments optimizing the social welfare Lear, (c-d) demonstrate that while again finding distinct solutions, RGM finds local performatively stable Stackelberg equilibria with lower cost than local Stackelberg equilibria found by DFO.
the equilibrium landscape), even in simple setting, depends the decision-maket action. We see that ij varies from -0.1 to 0.2 we start from having single stable Nash and saddle point and eventually only single stable Nash so that through the choice of u the decision-maker can control the equilibrium landscape.
An interesting direction for future work would be including a constraint the decision-makes 's optimization problem that ensures the induced game amongst agents strongly monotone. However, this paper, we consider settings where the decision-maker priori has no information the cost functions of the agents. Prior work in the asymptotic regime has exampled the use of methods from adaptive control to estimate the cost functions and then the estimated cost functions to incorporate constraint that the game is strongly monotone (Ratliff & Fiez, 2020). A natural question, therefore, is whether or not we can develop utility estimation techniques in the -symmttpioiic regime and whether its worth the additional sample complexity. In fact, such techniques might interpolate between the nave and strategic settings considered this paper.
D.2.3. LOCAL CONVERGENCE NON-CONVEX DECISION MACKSION-MAKER LOSS
In general, the cieission-makerr cost could be non-convex in As a result, while the auction played by the agents might be strongly monotone with a single stable Nash equilibrium, established convergence and sample complexity guarantees for the Stackelberg game need not hold. Accordingly, use this setting to empirically investigate the convergence properties of our algorithms when the decision-maker has a non-convex cost. In our synthetic example, we consider Kelly auction over m = 3 resource types and auction parameters
1
1
q 9= [
2 3
b b
1.5
2
1
26

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Here, we restrict the decision-maker's action space to U {u R$ 1 u, S 2.5 Vs [3]] and compare the repeated gradient method (RGM) and the derivative free method (DFO) in two settings: minimizing frev and L We display our results in Figure 8. Here, in simulations run over five distinct seeds, we find that our algorithms nonetheless converge at the predicted rate, but to distinct local Stackelberg equilibria. In Figure 8(a), when optimizing Levv DFO generally outperforms RGM though takes longer to converge, a finding consistent with our results in the strongly convex case; Figure 8(b) likewise demonstrates that RGM and C converge to distinct local solutions in the -aaker's objective. In contrast, Figure 8(c-d) indicates that optimizing Leer with RGM can result lower cost than DFO. In other words, the cost local performatively stable equilibria can be lower than that of local Stackelberg equilibria obtained from the same initialization. Formal theoretical characterizations of the equilibrium dynamics and convergence rates in non-convex settings remains an interesting line of future work.
D.3. Quadratic Ride-Sharing Game: Semi-Synthetic Simulations
We consider an example from ride-sharing markets. Demand signals may be used create more efficient ride share markets without reducing individual revenue streams by enabling information-limited firms to recover latent demand. Using an analogous set up as in Narang et al. (2022), we explore semi-synthetic competition between two ride-share platforms secking to maximize their revenue given that the demand they experience is influenced by their own prices as well as their competitors. The data we use is from a prior Kaggle competition.*
Game Formulation. Each firm divides rides into $5 price bins ranging from $10 to $30, and then chooses additive surge on top of that price as described in Narang et al. (2022). The social cost is given by
[(u)=
E. (2), (2)) E~DO
where each firm i's cost is given by
E (.,. v.0)
2 x4
| 11
2
Notice that each firm's cost is decision-dependent in that the distribution on 2; depends on not only xi but also the actions of the other firms and the decision-maker (x_., u). The action x; is a vector of additive surge prices to each $5 dollar bin and across the eleven different physical locations, and the term z x;; represents the added revenue across bins achieved via surge pricing, The term 2 || 2 is regularizer: namely, firm i does not want to charge too high of surge prices and prefers to spread the surge prices it charges across the locations. The random variable capturing the demand vector for firm i's service is modeled as
: E + A,, + -i, u4
where the vector A, : [Ar, - contains the price elasticity parameters for firm i; in particular, A is the price elasticity of demand for firm i's service given changes in firm i's price z; and A, is the price elasticity of demand for firm i's service given changes in all other firms' prices --g. In the simulations, we set these in the same manner as described in Narang et al. (2023). Here, the dacision-maker's action is given by u (#1, u2) where acts demand signal informing the firm i about latent demand. The regularization parameter X; serves to reduce the surge multiplier; that is, the firm does not want to inadvertently set the price too high.
1. ESTIMATION OF PRICE ELASTICITIES
In many applications. decision-makee may want estimate the reactivity of agents. For example, a local government may seek estimate the price elasticity of agents-in in this case ride-share companies-in a ride-share market that they can then subsequently set taxes subsidies on these agents or even the other side of the market (passengers).
In the context of the ride-share market example above. if a decision-makes aims to estimate each of the A,'s-i.c. the price elasticities of players-the then they can run online least squares where in each round f they first query the environment and observe
I,, = Er, + A where A, = [A A.-:].
*Data is publicly available:
and- lyff-daatase-bostto--ooo
27

---

Finite-Tine Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Then, they perturb the prices with actions n, for each player, and observe
Jt.i = (1 + Ut,i) Ch,s-
With these two queries, the decision maker updates their estimate of the price elasticities as follows:
A411,5 = A + velau. 21,1 - A
where U/ is the step size.
In Narang et al. (2022), the authors show that if multiple firms are running a stochastic gradient method while simultaneously estimating their own price elasticities, then the joint strategy of the firms converges the Nash equilibrium and the estimates of the price elasticities converge to the true values as long as the firms inject noise satisfying the following assumption.
Assumption D.1. independent of the previous random vectors {ual s < t}. Moreover, there exists constants c₁, R and Cu,i > for each i [n] such that for all 2 0 and i [n] the random vector U/ Ui,0 satisfies
The sequence u, = (U un,t) E Id is zero-mean random vector that is independent of zt, and
c E(vay,],
E
1lll S Cu,s, and [[llu://ez0)] RTE(v.,))
In our setting, it is an external third party that is injecting "noise" (which can be interpreted here as random demand signal) and they are decaying that noise over time with the goal of obtaining an approximate estimate of the price elasticities and then leaving the base system close to the nominal Nash equilibrium. The firms in this case are assumed to know their price clasticities A, There is tradeoff between how quickly the noise is decaying and the accuracy of the price elasticity estimates as well as where the agents actions end up relative to the nominal Nash equilibrium i.e. the Nash equilibrium of the game Gu where = O.
Indeed, fixing À 10 and some horizon T, suppose that the decision-maker samples in from N/ o, L2) where Ot-1 = >o, Then, in Assumption D.I we have
X XToo.
Ca.s di, and R² =3 max d₃.
q
iE(n)
From Lemma 21 of Narang et al. (2022), we have that
max (1
2B² o
|| A |
x E Tr Tr(Eo,))on
E ÄT Al S
T
2
XTor
where Eo,- =
J.
To bound the effect on the firms we analyze how injecting i, impacts the convergence the nominal Nash equilibrium. In this case, the firms are running stochastic gradient play with noise
St.i = Ei. A
where Ei, ~ Do and u4, ~ .N(0, 0t.s Ia). Hence, in the proof of the one step contraction for stochastic gradient play (cf. Lemma G.4), we have that
(Ga + 0z)² P
E.Eell xell
(a. + \ooo)²
M/lE xx|
201
2n
2
so that, after some algebra, we have that
202 (o. + Xooo²
Eel10441- - 12 1 7/44
100 - 101-11112
1 1 7/4
Another interesting example would be having firms that are simultaneously estimating A, and looking at the combined effects of injecting noise by the decision-maker and the firms. If multiple entities are injecting noise it could he the case that the combined effect reduces the time for convergence or makes worse depending on the injected noise distributions.
28

---

Figure 10 illustrates the players' behavior when there is no intervention by the decision-maker (i.e., 0) and when the decision- makorr intervenes with the socially optimal intervention (i.c., = u²)). In particular, Figure 10(a) shows that stochastic gradient play converges to the Nash equilibrium under u = and to the social optimum under u = = We Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
10"
10
hhoorcooll bound
16
10"
[Au-Auu
10
Ix-X1
10
10"
10"
10
10"11
10'
2000
4000
0000
8000
10000
2000
4000
6000
5000
10000
2000
4000
6020
8200
10000
fleratioss
ilerations
Perstions
(a) Estimation error.
(b) Equilibrium tracking error.
(c) Theoretical bound vs. tracking error.
Figure 9. (a) Estimation error for the price clasticities AI, A1,,, A2, and Å2. (b) Agent tracking error. (c) The black dashed line the thcoretical bound tracking error versus number of iterations, and the purple trajectories are the actual tracking error. For each of the plots, we run ten different random seeds and show the mean, the mean 1 standard deviation, and the actual trajectories using lower opacity. Note that although the magnitude of noise injected into the game by the decision-make decays over time, the decision- maker still has sufficient information to estimate the price elasticities.
We know that if the firms run stage-wise stochastic gradient play with some target accuracy & > O, then the agents obtain a Nash equilibrium in total of T iterations where given in Corollary G.5. Here T is fixed a priori, so order obtain an estimate for E, consider that the total number of iterations satisfies
K
T
T
k=0
21.2
2R
K
1
1
log
+ Σ
1
log(4)
22
122
k=1
(-4=L2 + Ep? + 8(0, + A 02) log(2) + Eu² log (5.+ oo))
21
2R
=1.g
+
log
+
log(
12
Ex² log 2)
212
2R
+ (1
412
8(0, + )0))
+ log((ns + XToo) (2
+
log
1
en²
log(2)
2R
(oa + XT
0
log
E
pree
Hence, terms of fixed T, the firms achieve an gy Nash equilibrium where
(0a + XToo)² o002
eT
2
D.3.2. SOCIALLY OPTIMAL DEMAND SIGNAL PROVISIONING
Recall that the social cost is L(u) EE (ST (w) + (x)). Define the socially optimal intervention be
20 == argmin L(u).
nell
In this numerical example, we explore the effect of the decee intervening with the socially optimal demand signal versus no intervention. To this end, we compute = using a symbolic solver (e.g., Mathematica) and then simulate stochastic gradient play on the player objectives f!(" (z))
plot this for a single location and price bin, both of which can be changed in the code base. The simulations show that when provided with the optimal demand signal, the firms are induced to increase their prices which indicates that user are
29

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
15000
Lyft
8
Uber NE
12500
Lyft SO
6
Uber SO
10000
p700e
7500
Lyft S0
Uber S0
Lyft NE
2500
Uber
0
1000
2000
3000
4000
5000
S10
$15
$20
$25
$30
Iterations
(a) Surge prices in S10 price bin.
(b) Utilities social optimum Nash.
Figure 10. (a) Surge prices the 510 price bin given no intervention i..., u = O and the socially optimal intervention i.e the optimal demand signal n argmin,, C(u). With intervention the agents converge the Nash equilibrium (NE) of their nominal game; with the socially optimal intervention, the agents converge to the socially optimal (SO) equilibrium. (b) Welfare for each firm in each of the price bins under the Nash equilibrium and socially optimal equilibrium.
willing to pay more for the service and competition between services actually drives prices down. One interesting question pertains exploring social cost that includes the cost users, incorporating elements such of alternative means of transportation such as public transit; unfortunately this data set does not include such information and would need be augmented so we leave that to future work.
Figure 10(b) shows that the welfare for each firm is higher in all the price bins under the social optimum, though more marginally as the price increases. This demonstrates that a decision-maker who is able to provide optimal and informative demand signals may be able to improve the welfare of the ridesharing marketplace, even under competition by the firms, since both the prices are lower (thereby increasing the demand and cost to passengers) and the revenue is higher for all players. also interesting observe that the smaller player the market-namely Lyft which has less demand in the data set-has larger marginal gain than the larger player (Uber) in the market.
D.4. Lower Bound on Epoch Length
To construct the example seen in Figure 11 (and Figure 1), we build the following quadratic, two-player game. Let TI, 22 gd be the leader's and follower's actions respectively. For simplicity, consider two player quadratic Stackelberg game with costs
1 ST Dr + x TCu.
(u, .)) = 2" Au + u Ba, and S2(u, x)
We demonstrate that in order obtain finite time convergence guarantees, in many games it is necessary have epoch length 2 1. Indeed, it is possible to randomly generate quadratic games of the form described above such that the following hold:
1. There exists unique performatively stable equilibrium--ee, xx A > 0 and D2fa(u", x (u))
O.
2. The gradient update is not strongly monotone operator: i.e., for some ((x; u), (x', u²)). we have that
(0(z, u) g( u'), (x, (x', u where g(z, u) (u D2fa(u,x)).
3. The equilibrium not stable when the agents and decision-maker simultaneously update-i.e., spec(T - nJ) g Dio, 1] c for any (n, 7) pair and Re(spec(-)) c Rxn where
B
J =
20
2
30

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Progression of maximum eigenvalue megnilude with
Progrosako of maximum digenvalue magritudo with
Medimum ergennauee magnitdde
Slabilty boundaty
Lower bound
56
1.15
1.02
1.01
1.10
0.82
0.88
Stablity boundary
Lower bound =
(a) Maximum Eigenvalue: seed=6188
(b) Maximum Eigenvalue: seed=301
Elpervduue mabiic
Eqpendaes
650
0.50
0.00
40.00
473
4.79
4.75
(c) Spectrum: seed=648
Eqervalan d' orginal raftc 1
Sgarneup bet 1
Egennases for 2-3
Egenaake for +5
Egamaike for 1-5
0.5
020
4.20
0.25
82
(d) Spectrum: secd=301
Figure Lower bound examples: (a-b) Maximum eigenvalue for the combined dynamics as the epoch length T increases; (c-d) the spectrum of the combined dynamics for selected values of 7. From (a-b), we see that the shape of the curve tracing out the maximum cigenvalue of the combined dynamics as function of highly non- non-linear and depends upon the game structure. Panels (c-d) illustrate the eigenvalues relative to the unit disc in the complex plane, where eigenvalues inside the unit disc indicate the system is stable. Future work would construct guard map for the unit disc the complex plane, and determine an instance dependent lower bound on 7 ensuring stability of the combined dynamics.
4. The epoch based dynamics, which take the form
rz+1
A 0
B
(1 (T-2
0 c
I
Ut+1
are stable for some + 2 1.
This means that there many instances of games such that it is necessary have time-scale separation introduced via an epoch-based algorithms in order to obtain convergence rates without making asymptotic assumptions on the learning rate schedules. The precise construction of the instance-dependen lower bound on 7 remains open question; we conjecture that tools analogous to the "guard map" for stability used by Fiez & Ratliff (2021) can be leveraged to derive this construction and moreover extend the lower bound analysis to even non-convex settings.
D.5. Interplay Between Sample Complexity & the Performative Gap
This section summarizes the setup for Figure 2, wherein we characterize the relationship between the expected tracking error, sample complexity, and the performative gap as parameterized by the agents' reactivity parameter Leg- To generate this plot, we fix constants related to the decision-maker's problem as follows:
I 10, J, 1, a = 5, 1.0, a = 1, d 2, B
and & 0.09.
31

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Algorithm 2 Geometrie Decay Schedule
1: Input: yo E IRd C. CD > O, 6n E (0, 1), estimate 2 hyy)), accuracy
0, algorithm A(y, 6, 7) satisfying (7)
2: Initialize: Set yo = A(yo, on, To) with To ((66) log (2A))
3: Set K = [1 [1+ log, ( )
4: for k == 1..... K do
5: Set y/ A(yk- Ōk, Tx)
with 0g = 2_ Tk-
v(62) logg(CC)
6: end for
7: Return: уk.
We then vary Leq. and check that for each value the following satisfied (otherwise throw out that value of Leq as there would not exist games meeting these criteria and our assumptions):
1. Existence of performatively stable equilibrium: LeqLs <
2. Existence of convex, smooth decision-maker cost: a Lu + Li
Then for each valid value of Leq. we compute the "big-O" sample complexity and plot this on the y-axis for each method RGM and DFO. Here, fix 0.09 while defining s : ||upe u²' In doing so, we characterize the worst-case sample complexity needed for or e' approximation, defined as in Figure 2.
What we can see from this numerical example is that there is tradeoff between sample complexity and performance for the decision-maker as a function of how reactive the agent is (as measured by Leg). If the decision-maker had access to Leg they could determine whether or not is worth it to run a more sample efficient algorithm like RGM versus alternatives.
E. Technical Lemmas
Throughout, use I to denote d-dimensional space with inner product (+--) and the corresponding induced norm is given by ||>||| = (a,,a)) For any set X' C Rd, we denote the projection of a vector y onto X' pr)ix = argmingexx x || yll Finally, for convex set X, we denote its normal cone at z E X' as (x = {u E R (0, - I) S 4 X To simplify notation, we set [n] = [1....,n).
E.1. Technical Lemmas for Convergence Analysis
We need the following standard technical lemma for convergence of sequences and high tiath--robbbiitty guarantees.
Lemma E.1. Consider sequence w. 2 0 0. 1 2 1 and constants to 2 0, satisfying
a++1 & (1
2
+ (t to)
(5)
t
Then the following estimate holds:
m1x to)
a; <
Vtz
(6)
to
We also restate the following Lemma, adapted from (Drusvyatskiy & Xiao, 2023).
Lemma E.2 (Lemma B.2, (Drusvyatskiy Xiao, 2023)). Suppose we have stochastic algorithm A(yo, 5, T) such that as long as 80, the method generates a point satisfying
B[h(Yr)] s - (6) h(po) + DS.
where h is non-negative function, C, > O, and óg E (0, 1) are constants specific to the algorithm, and v) is a function mapping [0, 86) into (0, 1). The point y returned by Algorithm 2 satisfies E[](yk)) S e with the efficiency estimate
K
2CA
K
log (4C)
Σ Tk
log
+
v((o))
(2 k60)
k=
A
32

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Note that this does not immediately apply our general case: is generally a fixed non-negative function, such as h(y) = lly =|| the distance some fixed equilibrium 5. However, in case, our target equilibrium is changing depending on the action u, from the decision-maker. A short corollary, however, gives us the desired result.
Lemma E.3. Suppose we have a stochastic algorithm A(yo. 6) such that as long as < ög, the method generates a point satisfying
E ElyT
yř 11 S C(1 - (6))" 1150 voll + DI
for C.D, bg and vo as defined above. Then the point y returned by Algorithm 2 satisffes E 11 yilll S with the efficiency estimate
K
(2CA4)
2CA
log(40) (2-
Th
log
(5()
c
k=0
Proof. For posterity, we include short proof. Suppose that our target accuracy is 2D5. Then note that it would be sufficient to run our algorithm for To iterations such that
C(1 (66) 1y00 vōl = D8.
Note that since (d) E (0, 1), we have that - logg(1 (b)) > (60), so
C'|130 - yōl 2|
log
S To-
(6)
D6
By the concavity of log, it is in fact sufficient to chose
Cl| vōl13 To-
log
(6)
Then we proceed just as that of Drusvyatskiy & Xiao (2023, Lemma B.2).
E.2. Technical Lemma for Decomposing the Decision-Maker's Tracking Error
Recall in Section 2.3, we made the claim that the error, drift and noise term. In this section, we formally prove this claim.
tracking error could be decomposed into a optimization
Lemma E.4. Consider setting in which the decision-maker's loss is a-strongly convex in u, define us E argminn, (() E(u, (Ie, {))}, where It is the agents' response from stochastic algorithm A, and define g(u) = v. ((D f(u, ())) Suppose is T.-Lipshcitz continuous. If the decision-maker employs a stochastic gradient-based algorithm with stepsize 17 and unbiased gradient estimator for, then
) 111 ug + 70²
E Blu 111?? S (1-
+ 20
a
where 2² is the gradient estimator variance and max; ||u] 1 is the worst-case drift.
Note that the mecision-maker could also be employing a repeated gradient method where we alternatively define up E argmin, (eggiin,EEee.., (B(z),))D((uz E(u, (2x, })}} and replace in the statement above V. (B(eL)))D(u) l(u, (xx, {))) with V. (E())))))(())) E(u, (Iz, E)). An analogous decomposition argument holds.
Proof of Lemma E.4. For a stochastic gradient method, we have that
1
20
Eellu441 will < 1+ (m))
||u,
2/ 112
1 arj
Indeed, let dc be the unbiased gradient estimator, and g(u) be the expected gradient evaluated u E U. Then, we have that the map > bllu - n9. 21|2 is a 1-strongly convex function over 2. Hence, we have that
2 |1-11
=² < 1 n/: 2 11 2 lue - nāe - -u+1ll²
S |lue u 12 n9,,, u++1 - -4²)
1
llue
u 1 n/,r,, Us ui)
|1+1 well 2 1/(ee, ue+1 ut).
2
33

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Taking expectations, have that
1
1
Ee Me41
0/ utll r/ U2 -o-1 u/))
Ex ule1 - urll -1nl2 (gt we+1 us)
2
2
2
1
1
2 1/ee- utll" 11 n(g(ue), 24 u,])
-
[u u1l12= TylEa (ge, we+1 us)
2
1
2 wi utll 1| - x) (u++)))) u6+1 - ut) 18,
0/llluc11 - uell
2
Ex (ā: g(ua), ue we+1) +n Bx(g(ue) -((e+())) ur ue+1)
=
=:
Since the game is a-strongly convex, we have that
(g(ue+1), uc+1 ut) 2 (g(ue+1) g(u)), uc+1 u/) 2 alluct1 u1l
This in turn implies that
1 + 2nj
1
1 IB Belllect uel1 rp(P + P2).
|1e+1 - u1l1 11 -,,ll
2
2
Employing Young's inequality, we upper bound P1 as follows:
Pi S o
in En 11l411111-uu well
2
2
Applying Young's 's inequality, we bound P2 as follows:
Eell((ue) g(ue+1)l1
Ey |1++1 ufl1
Ps s
212
L LE, liee Ue+1 11:
12
2V2
2
so that
1 2ma -1111
2 Eg |ue11 uēl1² S _ llue -ut11 +
1
o²
(1
mL'L
mpp1)
E2
Ue+1
uel??
2
Setting 1/2 = a and 1/ = 11 T.2/ / we have that the last term on the right hand side is zero, and since 7) S a
2T2 we have
that v1 2 2n
1. indeed,
1 < 21 -2 so that 1/1 = 1 21
Therefore
2n
2n
2n
1
202202
Elllu441 uz <
1lue
ut 112 +
1 naa
1 - (7)
as claimed.
Now observe that
|lu241 u6+111
||ue+1 u1,1 + 1luE ui+1 12 2(1441 - ui, ui+1)
< ||ue+1 - u1112 + 11/2 - wit1 12 + 21| - villluu ui+all
< 1 + 4 ||uc+1 - uill2 + 1 an
4
||u - u/tzll 1|2
where the last inequality follows from Young's ' inequality. Since 1
na T4.70
< 1
21, we have that
E, [1411
ui+2 11
< (1
na
((1
7a l|ue - -u,1 + 2172 202
(1-
na )
1 +
4
u/+1 112
4
na
<
1
yal
Ille
ui 112 + 20 (1
70
+
1
2
4
4
1jcx
34

---

Finite-Tine Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Iterating, we have that
1e114411-1 - 21+1l1
na
6+1
uill2
+8 +
no? +
20
A 2 QT7
a
which concludes the proof.
F. Regularity of the Equilibrium Response
Recall that w., (x) = (Viff,,... ...., v..f)). Strong metric regularity allows for Lipschitz continuity of solutions wiy (2) (x) to be Lipschitz continuous. The following proposition is formal statement of the discussion in Section 2.
Proposition F.1 (Inner Problem Regularity: Polyhedral Constraints). Under Assumption 2.1.i-iii, suppose that, for any fixed E U, the Jacobian of (w( with respect to a is non-degenerate and the Jucobian with respect u has finite operator n.mm-iee. det (D,, + and ||),w,(())ll oc. Then Wa r-metrically regular with with : (uU((,)))xxx))) D (2))l(
This proposition follows precisely from Dontchev et al. (2009, Chapter 2.F, Chapter 3); indeed, the strong metric regularity parameter this case is equivalent to the Lipschitz continuity parameter of the implicit function.
To give some intuition, we can consider the case where X' the whole Fuclidean space TR this section alone, we define w(,,z) æ) = (x) for the purpose of clarity on the derivatives herein. this case, by the fact that the joint strategy space X' unconstrained, for any fixed u Ut assuming det (aat (u, 2)) O, the Nash equilibrium x (u) is defined implicit function (cf. Abraham et al. (2012)) that solves w(u, x= (u)) = O. By the implicit function theorem, the derivative Dx* (u) is given by
DE Dx*(u) = (uw(u, x² (u)) (u)) Dew((u, x (u)).
We have the following lemma which provides sufficient conditions for x² (u) be Lipschitz by assuming suitable bounds on [u, oop and (,, ooll Lemma F.2. Suppose that (u, 2 μn and (uww( olo S u2 for all E X and set Leg == ks Lipschiit
#2,
Then x² (u)
Proof. We realize that by the mean value theorem,
(// Dr Dr A)u + Xed)) (u ww)
|| (u) x= (2')) (1))
< sup x=(0.1)
||xx ((1 A)u + Au 1opp) lopp/uu u'll
By the assumption, we have [D,w(u, x² (w))1I 2 μn and D,w((u, x² (u))l S μ2 for all U, then we have that
sup XE[0.1]
Dr A) Xx') s P22
= Legs
P1
which concludes the proof.
Again, in the polyhedral constraint case, the analysis above is almost identical; see, e.g., Dontchev et al. (2009).
G. Contracting Agent Learning Algorithms
In this section, show that several natural learning dynamics are p-contracting for some p E [0, 1). The following is modified version of Assumption 2.1 where remove the decision-maker for simplicity. Assumption G.I. The following hold:
1. The game = (f1, ..... fn) is C² -m-soooth convex game and p-strongly monotone;
2. The mappings x; Vifa(x;, =)) are Li-ischciizz continuous;
3. The game G is k-strongly metrically regular.
In this section, set (xx) = (Vifixx)..... Vnfa(r)), and recall that we have set L.g = mmxxe(n)) L4-
35

---

Finite-Tims: Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
G.1. General p-contracting Updates
Before getting into specific examples, let us analyze stage-based algorithms such as Algorithm 2 applied to a general p-contracting algorithms (cf. Definition 2.3).
First, we iterate on the contraction for steps to get
Eg [ x²11 1 +2
S p² 20-2 x²1 + p + &o
$ 11=0 x x²11 + c00
2.
k=1
$ $1 11:00 x²1| + e 2 p²
p²
The following corollary shows how Lemma E.2 (and Algorithm 2) applies to p-contracting algorithms.
Corollary G.2 (Stage-wise Stochastic p-Contracting A). Consider some target accuracy > and suppose we have a
constant R ||:00 112 Define 1b(7) 1 % C == 1, and D 1-p Set 7mo p². Then running Algorithm 2 with stochastic p contructing algorithm as A, guarantees that E ||++ x²112 S & after
c²,²"
K
2R
Tk
log
+
log(4)
p
1 - 2
km
Am
022202 (1-p")=
)
total iterations where K :=
+ logz
G.2. Stochastic Gradient Play and Asynchronous Gradient Play
Consider first players updating according to the stochastic gradient method given by
Tt-1 proj(*: (xx))
(8)
x
where (xx)) = ((rz). This is stochastic gradient play.
Assumption G.3. Suppose that there exists constant og > 0 satisfying
(x;) - w(x;))1 o².
Given the above assumption on the variance of the estimator @ of the vector of individual gradients, we have the following lemma showing that stochastic gradient play is p-contracting.
Lemma G.4. Under Assumptions G.1 and G.3, suppose that players update according to stochastic gradient play with Then, the dynamics satisfy
S 1
2T.
27202
|| - x² x²1 S
121 + 1 1 7p
1 M7
so that (8) is p-contracting with p² 1tp7 and c /24
Proof. Observe that
2 11 - (xx)) 211 is 1-strongly convex function over X. Hence we deduce that
1 11= - (Z(xz) - x1+111²
2 Te+1
x"1 00112= <
| - (xx)) x²122 - 2
| x= (3(r)) x++1
x - -x*)
2 || x2el2
1
|| x 111 (0
xx x²)
|
xrl2 (10 1, xz).
36

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Taking expectations, have that
F+
[1+1 - x=1 <
2 af - -- (x) 54 -4-="")
Re Fell - xell? - - (1) (1x)); It+1 xx))
2
2
1
- | x=11² 112 --(((x)) F2 - x²)
Er || x² x011 - s1+1 m²)
1
laaee x² 112 FB, (2 11, 3241 x²)
R 11 sill
y (x(00(x))) - w(x)), de 2141) ty E. ty
(x((1) w(x++1). x I(+1)
P
Since the game is ju-strongly monotone, we have that
(w( - x²) 2 (w(xe+1)
Jt+1 - x²) 2 M1| - x1²
This in turn implies that
21 +
1 BB 1 xz11 r(P1 + P2).
F1+1 - -11 2 2²112
2
2
2
Employing Young's inequality, we upper bound P1 as follows:
Pi S of
v E,
11+11 - 2el1?
201
2
Applying Young's 's inequality, we bound P2 as follows:
E, (1re - w(
U2E, | - x²1
Ps 5
212
2
I T I|:re - 114111
12Ee
0141
x=1
2012
2
so that
1 27/11 - 7/2
Ee Be|1a141 x² 2² |1,0
x²1l² 112
yo?
(1 --,3,3 -7m1)
Eellao41 - xxll2.
2v1
Setting 1/2 and 1/1 = LL3 μ.. we have that the last term on the right hand side is zero, and since 7 S ztz we have
that 2 1. 2-
indeed,
1 x 1 2y
22
so that 1/1 =
21
1
1
Therefore
1
24
27
20202
E, 11111111 - x11 S
100
x= + 1 Jyy
1 + 7M
which concludes the proof.
The following corollary demonstrates how agents could use stage-based algorithm to decrease the bias in their tracking eπror estimate and achieve target accuracy.
Corollary G.5 (Stage-wise Stochastic Gradient Play). Consider some target accuracy > and suppose have constant R 2 ||z - 122 Define bb)) == 1 1 Iopq C := 1, and D = 20 Set "
_ 2I
Then running Algorithm 2
with stochastic gradient play as A, guarantees that E ||are 112 S & after
K
[1+
2L 222
2R
K
[(
2 12
Σ Tx =
log
+ Σ
(1+
log(4)
42
k=0
A=
[ log,
2
total iterations where K :
37

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Proof. Note that from Lemma G.4, we iterate further get that
2
E2 - x= x²1 v
2 - =2" +
1 1+ Wny
1+ Mny
2
2
10 x²11²
+
720
1 + Mn
1+ Mny
1 Moy
1 pay
1
1150 - x=11² 20²22
14
(1+ jry)
s=1
1
20
11/0- - x=12 +
+ joy
H
1 - (1
(1- 1+ pny )) )1,)
20
E |1000
x=
+
Letting (7) 1+u7 C 1, and D 20 invoking Corollary E.3 and running Algorithm 2 with the specified parameters gives the desired result.
Asynchronous Updates. In practice, it may not be the case that the agents observe data actions synchronously, and as result they may not have the requisite information to update their action in every time step. A natural model to capture asynchronous updates is one in which agent i receives sufficient information to update its decision yi with probability pi. For instance, this means that
proj (oi, - Vi.la w.p. Pr Di,t.
01++1
w.p. (1 - p:)
Let Phax == maX P; and Pain == minge[y] P:- Then as described (Narang et al., 2022), this can be dealt with using techniques from preconditioning in optimization-see e.g., (Chasnov et al., 2020b; Huo & Huang, 2017; Lian et al., 2015; Recht et al., 2011; Zhou al., 2018) and references therein.
The analysis in Lemma G.4 does not change much; the primary difference is that the Lipschitz constant L, is rescaled by Pnax and the strong monotonicity constant y is rescaled by Pain. The reason this works out is that we can simply perform the exact same analysis using modified inner product as has been performed in prior literature- we simply perform the analysis in the inner product [z, y] = (P-la) x, y) where P = diag(pt....,
G.3. Momentum Updates: Strongly Convex-Strongly Concave Zero-Sum Games
Consider a strongly convex, strongly concave zero sum game (f, -f) where player one seeks to minimize f with respect to 21 and player two seeks to maximize f with respect to .22. It is known that such games are strongly monotone. Momentum based updates such as optimistic gradient descent-ascent (OGDA) and negative momentum are p contracting for such games. This family of updates is given by
Ittl = (1 + B)x, - BI,-1 - 7(11 + a))();)) aw(x;-1)),
(10)
where a is the extrapolation parameter, 3 is the momentum parameter, and
Vif(21, (2)(21,
w(x)
For example, standard gradient descent-ascent is equivalent to setting (a, = (0, 0). OGDA is given by (a, (1,0) and negative momentum is given by (a, .3) = (0,3) for some 3 < 1.
Let k := La/m. Gradient decent ascent commonly studied update and has been shown to be p-contracting with p 0(1 x 22 (Ryu& & Boyd, 2016). Mokhtari al. (2020) study both OGDA and proximal point methods for this
38

---

Finite-Tinn Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
class of games. They show that OGDA is p-contracting with p O(1 -))), and that proximal point methods also p-contracting with p (1 7/4) and c 0 in both cases. Zhang & Wang (2021) show that the negative momentum based update is p-contracting for strongly convex, strongly concave zero games, which are known to be strongly monotone. Specifically they say that negative momentum is suboptimal, but nonetheless, still p-contracting with p = 1 @(x=1.)).
G.4. Best Response Dynamics
Now, show that the best response dynamics converge linearly to the Nash equilibrium of the game. This result is commonly known and the proof is analogous to Theorem 1 in Narang et al. (2023), with one exception where we obtain tighter bound on the regime where linear convergence is guaranteed. Nevertheless, we include it for convenience. Define
BR(x)) == {x' E X': dy is best response to x'_, Vi E [n]]-
That is, unrolling notation, given a current decision vector 2t, the updated decision vector 2++1 is such that
2i,++1 argmin ((1,,--1))) ViEi [n]. x,EX
(11)
Lemma G.6. Under Assumption G.I, set p p= Lavn-I and suppose that we are in the regime where p 1, and that players update according to (11). Then, the game admits unique Nash equilibrium x² E X and the best response process converges linearly:
| - xx1x= pllo x*1l V120. O.
Proof. Since the game is strongly monotone, we have that
(V.f((u) - Veli(w',, ut) 2 pullu 1212
(12)
We will show the map BR(-) is Lipschitz continuous with parameter p. To this end, consider point w X and set = BR(w). For each i [n], first order optimality conditions for x; guarantee that
(V.fe(z,, 1 x)= x 0 V N,
Strong monotonicity implies that, for any n;; of X, have that
(V.f(lz,, w.)) V.fi w :), x3 21) 2 p||2; 2//l for each i E [n]. Indeed this follows from (12) bx letting a (Ig, 1 -;) and u' (ot, w) :) for each E [n]. Hence
n| x/11² < (V.si w-:) V Vili ur .), a S (- Veli(aly, w w);;, ar xa))-
Since this holds for any 24 we can replace xy with x; to get that
Ir 2 (V.f( w w.)) xx)
Since x² is Nash equilibrium, we have that
(wox*)) 50 V
Hence, we deduce that
n
111x - 1- <
Vifilz;, w 1) xz),
(w(x;; w_ w(x'), ) x - x))
S || w-)) w(x [>l")l "|||2" ||0" x11.
< La 10 - x
I x"
La (M1, w2).
39

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
where #1 (1a= 21 ||, ..... || Fyp II) and u2 [[|w-1 x= -11:--.... I|-- x == Letting ||20 x= ||, we have
that Ç² ||w-i x=ill ||:0= x3 11 for each i [n]. Observe that
1/2
u2
Σ |w=s x= x-,11
1/2
Σ
2²
||1, x31??
1/2
|<l
|100 1i 12²
22
K[vn- 1.
Therefore, we deduce that
M|| x²11² S (u1, u2) S La Lallu1 = Lav n 1/1
x²' x"|||<>"
x|
so that by dividing through we have
2 - x²1 S Lavn w -
Since this holds for any w and corresponding y = BR(w) we have that
Lavn
| - --+1 S p. || x²1 where p
as claimed. The rest of the result follows immediately from the Banach fixed point theorem.
H. Oblivious Decksion-Maker
In this section we prove the bounds on the equilibrium tracking error and the dynamic regret of the agents given oblivious mecesion-maker who deploying a sequence of actions {r.)__ that are of bounded variation and sufficiently contracting.
H.1. Worst-Case Expected Equilibrium Tracking Error.
The first natural question in this setting relates to bounding the time to track the time-varying equilibrium in expectation given the drift A, = ||=| - si+1l where ot E Eq(Gu,) where Gu, := ((K That is, given that the decision-maker obliviously deploying sequence {ue).=o
how long does it take for 1| x; 2 to be less than some error tolerance and how to we optimize that error?
We make the following assumption on the stochasticity.
Assumption H.1. There exists probability space (S2, P,P) with filtration (Fi)r20 such that Fo -0, 223. Iterates and corresponding Nash equilibrium, Iz, 2 Ω + Rmm are Fi-measurable.
Proposition H.2 (Formal Statement of Proposition 3.1). Suppose that Assumption H.1 holds. that agents employ p- contracting update (Definition 2.3), and we are in the regime P E [0, 1). Then, the expected equilibrium tracking error satisfies
(1-
8+1 11:0 - 2012 2(co,)² p²
As +6
2
E. B x 12
2
1 p²
where A. := max([1=7=1 =111).
Since the agents' updates are p-contracting with constants (c, σa), following the analysis in Appendix G.I, we have that
Proof.
F Eall4411 2; < 0² 1|
x;ll ( where ē: 1/(1 pp²)
40

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Now observe that
Eellee+1 1 12+1l1
| 2;11² + ||| -
27 rit1)
< Eg [ - 2;122 + ||=] -
- 1/+1112 2E, || - f1llla xit1l
- (1 + A) -e||=111-100 - =;|l² + (1+ X-1) Bellat - xitall 11?
- (1 + X) (0² - =; + p² (ēox)) )²) + (1+ I || - 2|t1l1?
where the second to last inequality holds since ||||||||| - >||a|l + x - |aa| for any À >
0. For algebraic convenience, let
0² = (1 - r) for some variable т > 0. Setting X = z.4 we have that
Eallxt11 - xi+1l12 = [ + - ((1 7) || - x;11 + (1 (1-11) (1-r) (coa)2) +
1+
2
E. | - xi+11l 11:
2 ||ا - x 112 + (1- (īoa)² +
|+ 2
A
where A²- = max{1lz; - xi+1 [|]]. Iterating this expression, we have that
E, |x(41 - 2;+2l! 1|2 $ (1- ;) ((1 (11-2) 2 || - - 112 (1-2) (2o,)² +
2 432
+ (1 - r ; (ōo₂) + (1 7)
2
22
S (1 )
1+1
|200 x1l1² + Σ (oo,)² 12
1+1
(1
T k
+ A
1+ Σ
(1- 7
2
2
k=
k=0
< <11 ?)
2(20,) )2
2
2 - 2(1
5) + (1-
120 z1ll²
+ +3
1+
T
7
(1 T> H+
2(00.)²
2
2
2
100 x
A
1+
T
T
Observe that (1 +1++0 we have that
w ))
<
2(2+w) w
<
6 for w E (0, 1]. In the regime where S 1 we have that 7 = 1 - p² S 1. Hence, 2²
S (1 (1-3) 1) 1+1
2(00,)²
2 2
-
2)
|120 = +
4
1+
$ (1 - ])
i-1
|1z0 - x1]12
2(005a²
+ 6
A
2
7
Since 7 : (1 p²), we have that
(1_(())
(1 (1-p²) 2 11:0 z511 +
t+1
2(o0a)² )
A.
Be - <
24+1
+ 6
1 p²
1- p2)
This concludes the proof.
Let us specialize to the stochastic gradient play setting. wi, == (xt), St. == wa, - Tie and :==== (Si.t...,,
Define also w/ : (Wi,t.... Wn,)). Here Çe is the noise of the vector of individual gradients.
Assumption H.3. Suppose there exists A2,0, > such that the following hold:
a. The drift Aa, : || - x;1 || is such that E 22 S 2 for all I;
b. The gradient noise Çe satisfies E || 12 < o?:
C. The gradient noise Çe : Ω + Rd is Fi+ 1 measurable with F[G]FFF 0.
Recall that A == max(1lu-1 uill) and A. S Teeq A.
41

---

Finite-Tims Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Algorithm 3 Projected Stochastic Gradient Play
1: Input: Step-size 7 S # 2
initial condition zp; decision-maker input sequence {u=)==o
2: for k = 1,...,t- . - 1 do
3: for E [n] do
4: Set Ti,++ proj (Zi,k (win))
A E [n] where Wi,b := V.S." (IR)
X4
5: end for
6:
end for
Corollary H.4 (Formal Statement of Corollary 3.2). Under the assumptions of Proposition 3.1 and Assumption H.3, suppose that the agents are running stochastic gradient play (Algorithm 3) with Y S p/(2)))) Then p² that
1
and c v2 so
147p
Eellxe+1 11+1 S (1
17)
1+1
I1:0
8702 + 24 =512 +
(eag) 2
7:
Given Lemma G.4, the proof of the above corollary follows an identical argument to Proposition 3.1.
Proof. From Lemma G.4, we have that
1
27²02 2
-e|10241-x*11- S
|:02 x01 +
1+ yp
1 1 joy
Now observe that
E2 f| - 21+1 = |, - x=111 ||0| - x 112 + 2F, (me+1 - 22, - 2(+1)
< E Eel1 =111² + ||2 - -x,,1l' + 2B 1 x7 ||| xt+ill
< (1 + >) Eel - + (1 + 2ー Ex 1 11/+
1
2
(Toa)² ) (1 +1+17 (1+ Bellx; - +(+1ll 11:
A1 1) 1+
| | 11 +
+ μn
where the second to last inequality holds since
||a ||b|||||||| S \|1a||
+ x 1612 for any À > 0. Observe that
1 =1 1+ My
py
1 M4
1 Juy
2
Using this fact and setting x = H7,
4. we have that
Belle++1- 12+111 5 1 + 47)
((1
14)
2 ||,| - x1,1 + (1-12) (V210a)²) + (1+
4 /
E Bella7 - -2i+1l??
4
2
$ (1
mn
I,, =,,1² + 2 (1- 4 41- (10g)² )2 + (1+
1
a
4
where 42 = max (110; xi+1 [|2]] Iterating this expression, we have that
E. E.112 - 21+1112 5< (1- (T) ||ا - =111==++ + 2 (1- 4 (705)² + 11+
4
s (1 4 11) ((1 117) ||
1 + (1- 117) (3y²)) + (1+
4 ) 43)
My
+ (1 47)
(7 )2 +
|
4
A2
4
HY
< (1 (nn 1+1
1000 - =0012 +
1+1
22
(1-44)
(-41)) k
+ +
1 4 (1=11
Σ (1 (1- *
4
4
m k=
k=1
< 2(1 (77 1+1
702
(Aa (
2
|00 - 21l12 +
24
1
m7
42

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
which concludes the proof.
The preceding corollary shows that in order obtain last iterate convergence guarantees there is clear tradeoff between the step-size and the drift-to-noise ratio. Using Corollary 3.2, define the asymptotic tracking error of Algorithm and the optimal step-size follows:
8 + 24
A8 jay
6 2
1/3
x =
min (2
and 7/ = min
222
1
that the high and low regimes are determined by
64
1/3
A
11²
A
2L2
6. 23 23
3 21
4v3
L
Fa
Therefore the high drift-to-noin regime is T. into Ex, we have that
A.
4²
and otherwise in the low drift-to-nois regime". Plugging
d
4/3-1
0²
96
if
4
T
4v3
L
E.
(A.02
2/3
12
12-6 6//
otherwise.
the decision-maker is the high drift-to-noise regime. this case, running Algorithm with y+ x xx/(212) results a point xe such that
High drift-to-noise regime. When A
2
de
4/33-
L2 log
- 1 - 2gl13)
E
xi1 S 6 in 1 1 1
time steps.
E+
This case less interesting as the decision-maker is deploying sequence {ug) such that the drift (i.e., change in the equilibrium corresponding the induced sequence of games) is higher than the stochastic noise in the game. Here, the agents must a learning rate y that is as large the deterministic setting and therefore, achieve expected tracking error within a constant factor of
A
L2
Low drift-to-noise regime. The more interesting regime results when the deployed sequence causes low drift relative to the noise level-i.e. when d./a, < /²/ (4v3 L2). In this case, it is possible that the agents can choose a step-size such that the tracking error is within a constant factor of e.. Indeed, with 7 x (622/ (uo?)) 1/3 its straightforward to show that stochastic gradient play (Algorithm 3) finds a point v, E X' such that
- 2711 Se. in ts of log p²c.
[ - - x7
E a| -
time steps.
Ex
The following proposition (formal statement of Proposition 3.3 from the main body) shows that there is an algorithm (a super algorithm that consumes stochastic gradient play) that proceeds in stages to obtain a stronger convergence guarantee. Proposition H.5 (Formal Statement of Proposition 3.3: Expected Tracking Error for Induced Sire-Varying Game.). Suppose that Assumptions 2.1, H.I, and H.3 hold and that the decision-maker deploys a sequence {ua)s satisfying A_/o, < / (4v3. I2).. Set constants
7/ = (6A2/(uo2)) 1/3
and s. == (A.02/1222/3
"Ohserve that this bound in terms of the induced equilibrium drift; it is equivalent restate in terms of the decision-maker action sequence drift follows: the high drift-to-noise regime we have used the bound A Aeg
n² and otherwise in the low drift-to-noise regime, where
4/3-12
43

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Suppose that there is a constant available such that R 2 1|
=ill..
Further, constants To
and
21-2
1/3
]
8L2 12a
L2R o
7k-1
74
4log (4)
K 1+
log2
To
log
7h
2
p47k
for forall 2 1. Consider running stochastic gradient play (Algorithm 3) k O..... ., K-1 stages. Then Tot. +T satisfies
L T S 1
L2R
6
L
o
log
S
log
0²
112
E,
p.
and the expected tracking enror satisfies E IK - x 11? E.. E..
In the above corollary (-)+ ma, We this operator since some of the logarithmic terms can be negative depending the size of constants.
Proof. Set to == and for each stage index k, let 4 == Ek-1 T, be the total cumulative time up to stage k. Let oj be the Nash equilibrium of the induced game qu.g and set
A 117
EN == T2o2 +
Recall that 7 2 %x Corollary 3.2 implics that
E |
2/41l² 15 (1
147k)
E 1 xill?
8 P
(nod +3
A? un6
4
S e
1TH Ta
E
||
x1ll 11? + ex-
We claim that E 1| 2ł112 < 2 for all A 2 1. The argument proceeds by induction. The base case holds since
8L2
L R
To
log
T²
implies that
112
8L2 log
0² 122 )) 11:0 x1l1² + + 5 o3
E [|| - 2111 Se e
-2a 1|200 =0 + S exp
+ eD S 260-
2T2
1
T2
Suppose that the claim holds for some k 1-i.e,, the estimate E
||
=2l12 < 2 holds for some fixed k. Then,
4ingf4) wrk
have that e Pie e -A have that
4. <
Further, its easy to deduce that 1 S 24. Hence, putting these facts together,
1 E Flaa xill + cx
E
2 < -
E 2|
xill cx
| 2 Ex 2cks
2c
by the induction hypothesis E ||>
x1 < 2c--1- i. In particular, this implies that E |z - 12 2ck-1-
Now, we need show that the claimed efficiency estimate holds. That is, we need to show that 6 X E.. Observe that for
44

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
some constants that we will set later, the following is true:
2 A 2
2/3
A
2/3
fk-1 -
112
7k 10
+3
am
c
n1²
1/3
o²
A
2/3
7k- 1k-10 +3
62/3
C
a
8
A
1/3
2/3
-k- + 3
6202
112
80?
A
1/3
1/3
1k-1 + 3
6202
8
Thus by setting c === 12- 61/3 we have that
6k-1 12.
62/3 12/61/3
A
2/3
80
(TK - 7/s)
80
70
74
54 $
A
2/3
= Ex.
n12
1
1
2K
11²
Indeed, this inequality holds since
(61 A2 /1o 1/3
8o
70
%
80
2L
/
2K
#
di A7
1/3
L.2 2/3
61/3 2/3
12021 2/3
111/3
2L3
1113322
2/3
A
2/3
8L2
1
62/3 2/3
122
212
11213002 2/3
2 2
2/3
62/3,
8 L2 2/3
112
10/3022
2/3
A A
2/3
< 4
n22
S Exs
where we used the fact that Therefore, we have that
(021)
1/3
).
P.
K = +
loga
L3
A3
(
(An02 x E+-
2/3
E || - =xx11 < 2(1 + 12/61/3)
112
What remains is to show that the total time T satisfies the claimed bound. Recall that we set
o²u
1/3
K 1+
loga
L2
A2
Observe that
T < I22
I
1
K-1
1
log
+
112
02
14
7kk
km
45

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
We need to show that the sum on the left asymptotically proportional to
To this end, observe that
21
K-1
21
2. 2.2
Σ
2 2
2
2 2-1
7
A=1
1=1
Using the definition of K, we have that
2k =2
loga
/1
1/3
A
Hence, we deduce that
K
2-2
2.21.
2.
1
1/3
(
02
1/3
4o
(
/Aa02
-2/3
d
<
=
4
7k
1
L
A?
A?
11² Me
as claimed. This completes the proof.
H.2. Beyond Worst Case Expected Tracking Error
The preceding results provide a "worst-case" bound in the sense that A = max - = is the largest difference in the decision maker's s actions. Here, we want to understand what happens when we make "reasonable" assumptions on the For
behavior of A, := ||u++1 - 1y For instance, one reasonable assumption that the decision- maker is employing some stochastic gradient method with a convergence guarantce of the form E ||u - u²1 v O((t + 1) )22). Here u" might be a locally optimal point for L or argmin f(u) given that players are playing a Nash (u) E Eq(Gw) or even some other solution concept-e.ge e.g. in Section 4.1 we introduce the notion of performatively stable Stackelberg equilibrium. Note that
E | 1 < O(( 1)-2a)
2a) means there exists constant Ca 0 such that E | uell? S (.+Īpp
Proposition H.6. Suppose that Assumptions 2. H.I, and H.3 hold and that the decision-maker deploys sequence of actions such that E ||u++1 11 < (E+1)
Gy zu for some (0, 1/2] and absolute constant ca 0. Set " u(t44o)3 for some E (0, 1] and integer to 2 and consider agents running stochastic gradient play with time varying stepsize " Then, the iterates satisfy
E 22, x;l1? & max((1 + to)l - 45.12,ca ca) {
(1+4))= bb (t 1/2-12
otherwise,
80
5
where Ca = n²
+
Proof. Let Aa,t := || - 2tll- We know from the proof of Lemma G.4, that stochastic gradient play is p-contracting. Moreover, for a fixed un which induces 2t E Eq(Gu.., we have that
1
27202 1 74
Fellz41--033 - S
x,,12 +
1 1 7/
Now observe that
||x 2
|| 21 + || - #1+1l1 1| 2(x 12,57 x2+1)
< || 2:11 + || x 112 + 2|| x1]l1a attill
< 4
17) ||041 x 1+
4
|| - 2ttal?
46

---

Finite-Timg Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
where the last inequality follows from Young's inequality. Since 1
2/4 147p4
<
47 2
we have that
EaI|da-11 - 11+111 = (1 7/14 ((1
7/6)
2 ) || - 2211 + +2720 (1-0221-1) (1-22) ))
2
4
+ 1+ 7/
| x1+1l 1?
S (1 4)
7/4
|| - =1 + 27 (1-
-1-2
7H 4
+ (1+ 7/1
+
4
A
$ (1 7P)
4 ||ا - - + +
5
L2g
1141 - Ue 1|2
jyy
The agents are engaging in stochastic gradient play given the induced sequence of games gv, with 7t M Hence, plugging Yt in to the above bound, we have that
2
80
5(t + to)
Ee| - 2it1l125 S
1
1 - 11
Leg Salleee - -u 1|
(1 +
(0)
1t + to) )2
8
2
8
5(t + tt)
c
1
1
| - x1
(t to
1² (t + to 28
(t + to 2a
2
_
5 L2
cd
1
|||| 2
(t + to)b)
12 + to 2b
8
(t + to
2a
Define D, : E ||2 - x; ||. Then there are two cases to analyze.
Case 1: If > Ga, then the above bound reduces to
Eg Eell20+1 - xi+il? S 1 (1-((=(((1)))) to)6
| 11-e- x;71 +
Co (t+ )6
(t
Then we claim that
m1 + Do) ca) (t + tb
D S
Indeed, it clearly holds for t = 0. Hence we may induction conclude the argument. Suppose it holds for some fixed t 2 1. Then, we have that
2
Ca (t + to
Ca
D S
1
+
(t+ tn)h
(t + to 2b
1
Ca
S
(t + to)
(t+ to) 2b
(f + to 26
S
(t + to)
(t+ to) 25
Ca
I (t + + to)6
where the last inequality holds since (1+10)* This verifies the claim.
((++o) (1+to)3) )+
1
1
(x+1+es)" for any t 2 and b (0, 1].
(++ta)28
Case 2: Suppose now that b < 3a. Then the bound on Do+1 reduces to
D S 11- (1(++t to)6
D. + (t
(t+ S (1-
Co
to)o-b/2 (t
D. + (t + to) 2a-z
(t
where the last inequality holds since b < Fa. Using completely analogous argument to case 1, we have that
D < max (1 + D1.
(t + b/2
Therefore, putting the two cases together, concludes the proof.
47

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
As noted in the main, this proposition shows that if the decision-maker is employing reasonably well-behaved sequence of actions (i.e., that is stabilizing sufficient rate), then the agents can utilize time varying step-sizes to control the drift and obtain expected tracking error bound that is decaying in time. The rate of decay however highly depends the behavior of the decision maker's 's sequence. For instance, if a 1/2, then choosing b = 1 leads to rate of (1/tt. Here, not just a reasonable rate for stochastic gradient method for the decision-maker as we will see in Section 4, but likely the best we could hope for. However, if the agents choose much slower rate such as < 1/3, then even with a = 1/2 the tracking error decays at a rate of (16/2-1/2) so that, somewhat counter intuitively, the rate is much slower as > This because the rate of the decision-makee dominates.
1/2 is
H.3. High-Probability Guarantees
The above results are characterized terms of the expected tracking error; accordingly, characterizing the guarantees of the algorithm are only meaningful if run multiple times. Instead, if our algorithm were deployed in real-time with irreversible drift, would like high-proaability efficiency results characterize the performance of our algorithm if it were executed only once. Here, present high-probability guarantees for the tracking error. We require the following tail assumptions on the equilibrium drift and gradient noise.
Assumption H.7 (Sub-Gaussian drift and noise). There exist constants A., 0a > 0 such that the following two conditions hold for all f 2 0:
(a) The drift 43, is sub-exponential conditioned F, with parameter A3:
E 2xxx)(AA2,)1 Fi] S exp(>A3) for all 05A=
(b) The gradient noise & is norm sub-Gaussian conditioned on J, with parameter oi:
P 2 Fi) S 2exp(-22" /o2) for all < 0.
Note that Assumption H.7 implies Assumption H.3 under the with the same constants D.. Oa. We need the following (albeit simplified) proposition from (Cutler et al., 2023), which is an extension of Claim D.1 from (Harvey et al., 2019).
Proposition H.8 (Simplified version of Proposition 29, (Cutler et al., 2023)). Consider a sealar stochastic process (Vi, X on a probability space with filiration H4 such that V, is nonnegative and H.-measurable, and satisfies
V4+1 S V2 + X, Kit
for deterministic constant 0q (-oo, 1]. Suppose that the moment generating functions of Xt conditioned on H. satisfy
Elexp(AXx)) Hi] S exp(Aut) AOA 1
14
for constant U4 > O. Then the inequality
E(exp(AVV+1)) & exp(A EE)E (exp (Aare Vc)]
1-a. holds for all 0 SSSS <
20
Proof. For any index i and scalar A 2 0, the tower rule of expectations implies that
E(exp(AV(++)) S Elexp(A(avVi + x,)] = E (exp(Aa, Vi) I[eex(AXX,) H.]]. By assumption, we have that ((exx((XX)) H.] S exp()et) for 0 S S 20. Thus, we have that Ejexp(AV(+1)) s E [exp(Aa; Vi) E(ex)(AXX)) H.]l < exp(Aeı) (exx((AaxV)))
which completes the proof.
Given this proposition, we have the following high probability bounds.
48

---

Finite-Tingn Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Theorem H.9 (High probability tracking errot.). Suppose that Assumptions 2.1, H.I, and H.7 hold and that the decision- maker deploys sequence {u=)'=o satisfying - u²
o, 1//313 so that the agents are in the low drift-to-noise regime. Let {
be the iterates produced by stochastic gradient play (SGP) with 7 S a
21.2' There exists an absolute constant c >> such that
for any specified N and ò E (0, 1), the following estimate holds with probability at least 1 1- à:
ITe - = $ (1 4) 11:0 =āl12
Aa N47
log (
Proof. By Young's inequality, we have that
| ritil 11 | 2=112 + || x141 1 2(0 - oj x4t1)
< |,441 - x/11² + +|x] xit1 12 + 2/| - =;llll - oz+1l|,
$ (1 + 2) || - =11 + (1+1-1) | -x/4111
for some A. Observe that + 2 aa - (xx) ==|2 is 1-strongly convex function over X. Therefore, we deduce that
2 |1t+
2;11² - 1 - (0x,) 11 2 2, - -x0(z) - x1+1l1
5
dr 2 112 (a)r))
2441 x++1 - -zi) 1 || =zel?
1
2 | 21 ) x1)
-10((()) zz). || zel2 -11--180 -0l3--7(00
Next, we have that
1
2 |
x7112 <
2 || - x² ((()))))))))
Tz+1 - xzll - ((0(2t)) x141 xz),
2
1
5
1/ - ot 11 ((w()))) x - x7t)
2
|,+1 - x²12 - (T) de+1 xx),
|0 2 1/ (w 1
x1)
|| rell?
+ 7 (a(z)) w(x))))))))))) 2 +7 (w) w(1441), 27 ret1)
=PP
Since each induced game G. is is ststrongly monotone, have that
(w(FL1), x/} 2 (w(x+11) w(x)), x1+1 x²) 2 p1|x0411 - x;
This in turn implies that
+ 27
| - 2;112 < |1: 111 || - 2r.12 + (Pi + P2).
2
Applying Young's inequality, we have that
|1&.122 20
M1 Millæ111 - =22l
P <
2
and analogously, we have that
Pg < [(((xz)) - w w(f++1)11
+ 02l x;,1?
21/2
2
L2 I 21+11l 1|2
22 P2/1 - 121
2u2
2
49

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Combining these two bounds, have that
1+ 27p - -22
||&lll
"3y=" - -221) I 2x11?
r++1 xill" 2 2
21
x21l²+ +
2
2
2
Setting and in = = - T.2/1u nr, we have that the last term on the right hand side is zero, and since 7 S 213 we have
that v11 2 1: indeed,
1 S 2-2 so that 1/1 = 212
1
Applying these bounds on the constants V and
27'
27
27
V2, we have that
1//116.11 x=11²=
- -
1,
1 1p
+ MT
Thus, we have that
|x x 113 = | - 211l + || x/+1111 2(2 - 27,17 - x7+1)
< | 2 + || x 11 2 2|| 21|l|zt zi+1ll
1
2y [(all)))
s (1++A) a)
1++7/1 |0, x1 112
+ +1+ ||=| - x/+1l1
+ Mn
$ (1+ 2)
(1 117)
||,0 x
117
>2115-112) + (1 + + || - x2+1l1
2
m7) || - 2; 11? + 2 (1- 4T) 72 11Eal1 + 1+ _
$ 4
ur 22.
where we have set À = 47, and A., = |, zi+1ll Bounding the last two terms, we have that
2411 2441-114111 < (1 47) ||= xil1² + 11 +
5 My A2
(13)
Under Assumption H.7, there exists an absolute constant 2 1 such that ||C=]| is sub-exponential conditioned on F, with parameter co and & is mean-zero nab-Gaussian conditioned on Fr with parameter co for all t (cf. Lemma 3 from Jin et al. (2019)). Assumption H.7 also implies that A2, a,t is sub-exponential conditioned on F. with parameter A3 Given (13), we apply Proposition H.8 with parameters
1/2 = | =;,? D. 0, X, = 12
2 at = 1 xn
14y
K4 = 0. and is = 27 +
5 A. Hoy
4
This yields the estimate
Elexp(A|ize11 = S exp () (22,2002
147 ) E exp (2 47) I| =
(14)
for all
< 5 2(2;2co3 + 543/(17))
(15)
Since (1 11-#% 477 E E(0, 1] and V2 non-negative random variable (almost surely), Jensen's 's inequality implies that
Ejexp(AVi+1)] S exp (Av)) E [exp (1
I exp (Av)) E (exp (1-7)
50

---

Finite-Times Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Iterating this expression, we have that
E [xxp(\|<2; - =,,111 = exp ((20702
542
Σ (1 ---")")) (Blexp(Allz0 x1(13)1) (1 --Mr/4)
2-1
M4y
(((1-
542 t-1
exp(dei) exp
{
42)
4
||00 - xīl12+ + 200 +
Σ 1 4
m=1
A <(11 117
547
1-1 Σ
(1- 47) ))
$ exp
|1:00 xāl12 + (200/ 2
==0
S exp
A ((1
(4)
| - xz 1
+
20
(1r7)²
for all À satisfying (33), where the equality holds since ||.0 that and nyy that
xīll is a constant, Let v == 32(nn,)
+ 20
[ p4y
Recall
8070 11
2012 (nr72
Sv
and
1
1
1
S min
v (2>(ca,)² 2 + 20/2 (1m22)
32 . c2 2 + 5 (//11)))
Hence, we have that
(>
x;11 (1112-
177)
11:00 - 20112) =dii)) 1 exp((v)) A SYSOAA 4
E exp
Rewriting this expression, we have that
E exp (2 (IaTe
2t11? -2--)-(11-12) 11:00 - ==61()) 1
exp(Av)
Applying Markov's inequality, we have that
Pr exp ( (x(1e [100 (10e-x071 12112= [101-= (1-477 |1:00 - -ril2) r)(lz)) N
exp(Av)
exp () (1::0-=03)) - 22112 -(1 -22)² 11:00 - ==01²))
<
exp(Av)/6
Therefore, setting x 1. with probability 1 - 6, we have that
|1 - x;11? s (1-14) (1-11)² 11:00 zôl1+ +
(3((00)
20 (Aa) 2) /4
)) log (9)
(16)
claimed.
The above theorem can be translated time-to-track high probability result.
Corollary H.10 (Time track with high probability.). Suppose that the assumptions of Theorem H.9 hold so that we are in the low drist-to-noise regime, and there is a constant Rt available such that R. || 2 Suppose that the agents are running SGP in k O....,K K - stages (cf. Lemma E.2) with constants constants
1/3
P
)
1
log2
T2
A2
No
2T2
51

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
and
8L2 12
L. a²
Tk-1 7
+
4log(12) (12)
To
log
7h
Th
for all k
pr7ph
Then T = To ... + Tk- satisfies
1
R.
+
2²
1
R
T T
log
+
S
log
u²e.
11²
E.
p
for any given 8 E (0, 1), the tracking error satisfies | x2 112 S log
(3) with probability at least 1 - 8.
Proof. Set lo == 0. For each k; let Ls = To + ................................ + Tk-1, let of be the Nash equilibrium of the game gu,, and set
Thoa +
A
Ex == c
14
where 2 is absolute constant satisfying the bound (16). Since y 2 7++ Theorem H.9 implies that for any specified index k and 5 E (0, 1), the following estimate holds with probability at least 1 d:
| 2b+11 s ==(1- 177
Th 1
=z11² +
ooT +
log
(7)
E
4
S e Ce-MTeTe/11aa - 22 + E& log
5)
We claim that induction indued argument yields the following: for each & 1, the estimate holds with probability at least 1 - 8 for all 5 E (0, To see the base case, observe that
|| - x S AE log(e//))
11²
8L2
L.R 0
o² T.
a²
p 1100 =o11² S exp
log
|1000
4 2T2
112
7,2
and
2007
o²
A
30
30
Eg = c
+
2
+
2
c
2
147
2L2
p070
4L2
4L2
since "ik 2 % and c 2 1, and we are in the regime where
A
<
2 41.
Therefore we have that
d2 L2
e - =111 -
<
Ev.
3
Hence
||:] - xi11? S e 10 -2012-1--2--0 + En log
e
<
C Eo log (+) = 3EE log (7)
3
since log(e/8) 2 1, and where we take the bound in the last inequality to simplify constants.
Now, suppose the claim holds for some index k 2 and let 5 E (0, 1); then
|| -
- 211² < 3 log (2e/0) with probability
at least 1 - 8/2. Since
- < exp (-1r%
[llog(12)
S
12'
also have that
2e
| - 12-1 (e
12 + Ex log
1
(ec)
<
11 - xill? Ex log
12
8
Ex
(20
Es log
6E4-1
<
3
Ex log
(20)
(2c)
+ Ex log
2e
6
52

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
with probability at least - 6/2. Taking a union bound, have that
|| #x+11l2 - 2
3 Fig log
(2e] (2²)
S 3Fg log
( (
with probability at least 1- 6. This completes the inductive proof. Hence, fixing ò E (0,1), we have that || - xx 11 S 3Ex-1log(e/4) with probability at least 1 8.
Recall that we are in the regime where A <
and we have set constants = (642 ( 1/3 and e, =
4v31g
Observe that for some constant C. the following is true:
2 FR- C
A A 112
2/3
2
A 2
2/3
Tk
C
1
m
112
2
7k 2
A
1/3
0
C
A
2/3
1
110 2
62/3
112
20
A
1/3
2/3
7k-1 +
C
62
|1
112
20
A
1/3
C
A
1/3
Yk-1
+
62022
2
With this expression in hand, setting C := 7 (2))
1/3
we have that
2 EK Ek-1-77 -7
7-)
(
1/3
A
2/3
20
20
70 7
2
2/3
12
(7K-1 -7+)
11
2K-1
112
6.
Therefore, we deduce that
( 1/3)
2/3
Ek-1 S
1+7.
9 (9)
log
e
2
n12
so that
E [KK - xi S 3EK- log (3) s
3.c 1 7.
(
2
1/3
A
2/3
(0) e. log (9)
log
2
112
What remains is to show that the total time T satisfics the claimed bound. To this end, recall that
1/3
K=1+
log2
L2
A2
and observe that
1 42a
I.R
K-1 +
1
1
T S
log
/4
7
k=1
Here, we need to show that the sum on the right is asymptotically proportional to o2/ Indeed, we have that
K- Σ
21
K-1
2L
2-2L2 2 K
Σ
2
<
2k
11
11
1=1
k=1
so that by using the definition of K, we have
1/3)
2 =2
logg
P
1/3
L2
A?
53

---

Finite-Tine Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Hence, deduce that
2.2L3
2.2L2 μ
2.
1/3
0 A
1/3
40
(Aa03 4
-2/3
0
2k-1
4
7
A
ue
as claimed.
This completes the proof.
Algorithm 4 Epoch-Basse Basee Algorithm Framework for Stochastic Stackelberg Games
Input: decision maker algorithm gan horizon T, stepsize schedule {m,) initial parameter 11 U, and query radius 8 (if A1 dm DFM)
2: for t = 1....,... T do
3: if' Al DFM then
4:
Sample U2 S uniformly at random
/+ i.e., derivative free method +/
5: Set û, = 4t ou, and U = (1 8y4
6: else if' Ad = RGM then
7:
Set û, u, and U
/* i.e., repeated gradient method
8:
end if
9: for k = ..... Ti do
10: Query agents with ūz
18 1.s., agents update with any p contracting method
11: end for
12:
Decision-maker observes (ū:)
13:
if Aag DFM then
14:
Set Sr. = 3 f(ūr (x77 (ūe), E))e
else if Algan RGM then
16:
Set V (M (x (ū,).
17:
end if
18:
Update u++1 proj(u: m:3t)
19:
end for
I. Naïve Decision-Maker
In Algorithm 4 we state the main algorithm structure the epoch based methods including the naive decision-maker. In this appendix section, we provide the formal statements for the results Section 4.1 and the proofs. To reduce notation in places, we let Le denote the overall Lipschitz parameter for (u, 2) (V,,(u, =), (Ql(u,2)).
L.I. Existence of Performatively Stable Stackelberg Equilibrium
Recall that performatively stable Stackelberg equilibrium are precisely the fixed points of the map
pseq(l') = E El: u optimal for E (~Delw))
f(u, (x" (u(), and x" (x') E Eq(G
Lemma L1. Fix a function 8 Bd Z R such that E(.,2) 2) is C¹ for all z Z and the map z + Vullu, 2) is L -ipschhttt E P(2) such that E(u,) -) is both vs and integrable for all u.
continuous for any u E Rdd Fix now any measures Then we may exchange differentiation and integration V V.E.r z) E,,, V. Voluu, z) and the estimate holds:
sup V. l(u, 2) V.Esne, l(u, 2) S L2 (1(,)
Assumption 1.2 (Lipschitz Distributions). There exists Lea 0 satisfying
w (i(Duuu), 5 Lon (luu-w)) w|l for all u, w u.
54

---

Finite-Tims: Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Theorem 1.3 (Bxistence & Uniqueness of Performatively Stable Equilibrium). Under Assumptions 2.1, 4.1 and 1.2 and when 1 < (T._(TTee Taa)), there exists unique performatively stable equilibrium. When the non-strategic decision- dependent component is stationary-ia i.e,, De(u) = for stationary distribution De- -eeexistence and uniquness is guaranteed if a/ Leg and Assumption 1.2 is no longer required.
Proof. We show that pseq(-) is Lipschitz continuous with parameter A. Since the induced game 9, is je strongly monotone for any u E U by assumption, there is a unique induced Nash equilibrium x* (u) E Eq(G.) for each u. Consider two points u and u' and set w = pseq(u) and = =psequu"). First order optimality conditions for w and w/ guarantee
(g)(w), w') s and (gw(w'),, w' w) S 0,
where go (v/) = (v) V.E(v', (a* ()) Since the loss ((,,z) is a-strongly convex for any E Z, we have that ||W - w/11 (mn(w) - Iu (w')
w²)
s (w') ) Iu (w'),,, (w'), ) w²) s llo (w') - (w'))) ||| -1|w - w'll
E Vul(w', (x" (u'), EnD.lu)
E Vullw', (+ 1100 w/ll
(wD)(())
< LeeL + Lan)llu' - w|l --l--wl. fwwwwll w'll
Dividing through by ||w w'll guarantees
|| w'll [[pse(()) pseq(u')) L. Lz(Lig - Loaa)
||u u'll-
Observe that Leq + Len characterizes the total reactivity of the environment due to decision from both the induced agent behavior and environmental stochasticity. In the regime where (Leg + Lea) < L. then À E [0, 1) so that that pseq(-) indeed contraction as claimed. The result follows immediately from the Banach fixed point theorem.
1.2. Characterization of Performative Gap
In this section, we characterize the notion of the performative gap-i.e., the gap between the performatively stable equilibrium and the Stackelberg equilibrium. We also introduce a toy example to see the implications of this gap on the losses for the decision-maker.
Proposition 1.4 (Performative Equilibrium Gap.). Under the assumptions of Theorem 1.3, if 2) is Lg Lipschitz continuous in 2, then
LLg[Leg + Lren)
||u" u05 + || (u") x² (uP*)| S (1 + (Te))
L, (Leq Lea
When the non-strategs decision-dependen component stationary-ie. De(u)= = De stationary distribution DD-the bound reduces to
LzLing L Leg
||u" uPa (u)) x² (uFP))] S (1 Teeg)
and Assumption 1.2 is no longer required.
Proof of Proposition 1.4. First observe that
||u" - u + "1x=(("") x'(PP)) S (1 + Loag)llu - u00
(17)
Recall that
E (u) (w))
Vallu, (x" (x(),
55

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Next, since is a-strongly convex in u, have that
alIu* 1 v (G Gura (ut"), u - )
- uP8)
)²""""=== S Ga - Gu- (u") + Gw- (u"), u² - -uP
S (a. (u" ) u² upp) + E
Vull(",(=""u(")) (x*(u)))))
E (x"((, _
(wDe(w))
S (Gar (u"); u² - -u + L1 (Leg + Lan)lles - upal1.
Now, since n" is optimal for min, C(u), have that
O E G. (u-) + d E dw (enDa(w)
Elu", (0 (x"(w),
I +Nu(u").
w=w-
=
By Lipschitz conitnuity of é in and of x² (-), we have that ||인1| S Liz (zeq + Lan). Therefore, combining the above results, we have that
||ue - 11 Le(Leg + Leaa)
LLe + Leaa)
so that
La(Leg + Lea) a Lo Lioq Lonn)
||u" - u + [1(=0(()) (u") x (1p*)] S (1
Lea) Lea)
as claimed.
Informative Toy Example: Implications of the Performative Gap in Quadratic Games. Figure in the main paper explores the sample complexity and performative gap tradeoff in terms of the equilibrium strategies. Indeed, if the reactivity of the agents is small and the dependence of the cost for the decision-maker on the agents is also "small", then the performatively stable equilibrium will be near the Stackelberg equlibrium. It is also natural to ask what the implications are for the utility of the decision-maker. Here we provide concrete example of Stackelberg games where the gap in utility between the Stackelberg equilibrium and performative stable equilibrium is large or small.
Consider quadratic game with a linear "tariff" Φx(x, u):
1 =² b,n, ca, + d2 u) and (x u4 fori 1,2
fi ( x..)
And let the decision-maker cost is something simple like
f(x, u) = ||u 12 ||xx((1) - 1112
for some "desired" xd) Supposing the game constants are such that the game Jacobian is invertible, the Nash is given by
b
ci C2
w(x, u) (I) + biæ2 + CI, 32 bari 02) (0, 0) x'
b2
Then matter what is the Nash equilibrium stays the same. And, we have that uP u² ud since x:" (u) is constant. So not only are the performatively stable equilibrium and Stackelberg equilibrium "close" but the change in mecision-maker cost is also small (zero in this case).
Now, consider a quadratic game with a slightly different linear "tariff': (z, u) u,d, + Cc. Thus the Nash equilibrium given by
w(x u) = (01 + bi + u1, 22 + by21 + (2) = (0, = x²(n) =
b
u1
b2
U2
Hence, if
1
||A|| S b1b - max v /,b2,, 1 vbbb2)
56

---

Sinite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
small (u) does not change much if does change much. We again have that w u² for the performatively stable equilibrium and for the Stackelberg equilibrium have that
2(u -
(o-="")= u²") + 2 (Au - u u0== ATA) A AAxx
so that u² * u Then (20E, (PS) ||Aud xd1 112 and
(x"("), 1 A) A)
+A - + |A + AT + A ATx x²12
12
We know that ((2p0 uP=) 2 l(x (u*), =²) just from the basics of optimization. Depending on the size A (i.c., the size of the agent reactivity Leq = || the losses can be very close or very far apart. So in this case determines both the closeness of the equilibrium and the differences in losses.
If the decision-maker places more less emphasis on the term via weighting term X, then that can cause the decision- makers utility to change more significantly. For example, consider (u x²)) = ((1, 1). 1)) for simplicity. And let bj b2 = 0.5 and (2,, u) = A|Iua w²1l2 + || - 1²1 Then y = (1, 1). Then (relatively speaking) we have a small change in both l and x² when x = 1:
& (1ps, ) 6 (x=,,²)) 1.71 and (uP*) x= (u*))² 0.72.
On the other hand, we have a large change in l with small change in x" when X = 5:
(x uPe) ls(x", u²) )= = 22.67 and || (uP*) x" (u (n²)]l 0.19.
Thus, even in simple quadratic settings it is possible to get variety of outcomes in terms of the decision-maker's loss depending on the reactivity of the agents' (Leq) and how reactive the decision-maker's maker's loss is to changes in the agents' behavior (Iz).
I.3. Naïve Decision-Maker: Stationary Non-strategic Environment
Given the preceding technical lemma, we know prove Theorem 4.4. Let's restate it more formally.
Theorem I,5 (Formal Statement of Theorem 4.4). Suppose that Assumptions 2.1, 4.1, and 4.3 hold, that we have available constants R ||=-1 xx (un)ll and B > Ilu0 I and that are in the regime where a >> IigLee so that there is unique performatively stable equilibrium. Further, suppose the decision-maker runs Algorithm 4 with Alg == RGM using step-size S 1E3(1+E2,) where ā == a Le and the agents employ p p-contracting algorithm A with E [o. 1) and oa E (0, oo). Suppose the agents run their p-contracting algorithm stage-wise via Algorithm 2. In this case, set the epoch length to
1
2R ET
1 k
Tk
log
+
log(4)
(18)
p2
(
p2200 (1-pejer
and tolerance 6, 02 where K
1 1 + log2
and
20 +6
1
4
:: R
4B +
(19)
1 p²
(1 (1-p21) p2)z
[.
L2
where 3 = (11pp)) (²). Then, the following estimate holds:
Eelluc+1 u2al (1- an7
[u0
21
4no
Recall from Corollary G.5, that if the agents run stochastic gradient play in stages then we are able to characterize precisely the number of iterations required to hit a particular specified error tolerance. This is where the epoch length in (41) is derived.
57

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Proof of Theorem 1.5. Define the following objects:
9t. V V,E(ur, 1,, where & ~ Doi
(u())) E
Vul(ue, (:
D.Da
(20)
G. (ux) == E
Vul(ue, (x" (we). E));
8~
Gpa(1)) = Vul(ue, (x (x(*), ))
ENDDa
Also note that E [g]] = (wx) i.e. the gradient estimate dr is an unbiased estimate of the time varying expected gradient Gr-and
u argmin
E
luu 2) so that (Gpo(uP)), u u 0 vueu.
NEll >~D((ar))
Fix two constants V1, 1/2 > 0 to be specified later. Noting that 4441 is the minimizer of the 1-strongly convex function M + U1 - 19t uI|2 over U, we deduce that
ue+1 uPe uPo =
179: uP 112
11ue Th9t
Mc+1/12.
Expanding the squares on the right hand side and combining terms yields
1
1 |lue11 - uell
2 1141 - upe113 -
ue - uP0112 17, (e, ue+1 - upe)
2
2
1
uu uPo 112 n/ 24 - uPa) |luct uel1 799, ue41 - me).
2
Using the fact that Ee[ge] = (ut,, we successively compute
1
E,
22
x
144
uP=| (E 4 - -uP²)
Ey Bellu411 wel1 -1,E, u6+1 - Ut)
2
2
2
1
1/4 1 1| (VGG((u))) u4 -uP9)
- TEx FEllutt+ - uell 2 17Th (gt, 14-1 - ue),
2
1/4e
_8 11 n),E (C. (we+ 1), Ux41 - -uee -2 BBllluct1 - uell
+ 17 E, (gt G:(u)), ue - u441) +he (v) - G. (u(u1)),, up= -1+1)
P.
Recall that for any the loss f(u, 2) is a-strongly convex in that
(1e41) u4+1 uPa) 2 (Gpa (up((u)1)) - Gpa(u u441 uPa) 2 aalu44111111 up811
Therefore, adding and subtracting Gps (u++), ), we have that
E, (G.+)))))) u141 uPa) E, PGp u4+1 uPS) + E, (G,(4))))) - Gps (u++1), we+1 upa
Now, the second term is upper bounded follows:
(U,(1) Gpo(uet1), u411 uP8 < L.Leq [ 11441 w
Then, rearranging the above expression, have that
1 1 + 21ja E, |1++1 11 < 11u, uPa112 - Bu
uel1
(P( P2).
(21)
Applying Young's inequality PL, we have that
E, llg. 12(1))12
uell
Exlllu441 wel
P <
+
<
(22)
201
201
2
58

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
We have the following upper bound for P2:
Er Ex]]Gr(w+) -ue+ 12Er|/uPe u1+1l
P2 Σ
21/2
2I, [1,) G. (u:)l (IE,/IG,(vr (wx) G. (ue++))
12Belluee 1e+ 1|2
21/2
2E, [[) (u,)ll + 21 L2g) 21 uet1l
12 1u 11++ 11
21²
The first term in the first fraction can be bounded as follows:
(ul)Gr(we) G. (u,))² E,1l E
Vul(ue, (1)))-1)
E g~D,
Vullue, (x" E),)
END
(23)
< L u4) (w))ll
This shows we have time varying bias component our gradient estimator. Here, we aim to show that E, (2 x" (u))ll S e r/²0² where each epoch agents running p contracting algorithms for steps. In order obtain the target accuracy bound in epoch f, we need that the agents' initial condition to be bounded at the start of this epoch. To obtain a bound on the initial condition in expectation we need to perform an inductive argument to show that -1 x [1 < R where R is defined in (19). Let us suppose for the time that this bound holds for each t.
u.)
Recall that
2R
K
(1
T
log E,
Σ
1
log(4)
1 p2
2-k
total iterations where K
1 + logz
/P:20? (1-D-)er
) In this case, deduce that
Lier
21 + L2g ||ue ue+1ll
L2g)
MylE, ||u ue+1
Pa
1/2
2V2
Coming back to the bound in (37), we have that
+ 2njō
1
1 _Belluet u0l1 1ul12+ +
0²
well?
Eg [u411
up2112
uu
2
2
201
2
I2Cr
2L + L2g)llus ue+1
1|2
up
26+1 112
+ 17
+
1/2
212
2
so that
1 + 2nj
71/2
E, 1141 1
< 2 Ilu - uPe 1
+ n0²
+
1ier 1 1 213(1 + L2g
7u
E, 1141 - ue
2
2
1/2
2
21)(1+22) and 1/2 ā ensures that the last term the right is zero. By assumption that 7 S (11+)12)) we have that 417(1+22) so that v1 2 1. indeed, we claim that
Letting
V1 n
27y
21 L2
2 2n
1
Rearranging, this equivalent to showing that
21 L2
2
Now we can lower bound the left-hand side as follows:
2L3 + L2
2L (1 I22
7)
>
4L2(1 + L2
ā
2
2
59

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
That shows that claim. Hence have that
1 + n1a E /11c1111
uP 12 11 PF + 17²0²= 2=+
1
ET
4(1 + Log)
- 2 14 uP0112 + 1+ 4(1 + Lig
1f"0"
$ 2
114
uPel 11? + 0²
where the second to last inequality holds since E, o² Thus, have that
1
4
Eg |u4 - u//112 2
2e
11
+
o²o?
n/
1 n/cr
Recursively iterating the above expression, we have that
1
Eg fe|luc+1 - 1/
(1 11 - u up +
11²02)
+
11 0
1 + yj
1 + nja
1 + njci
+ nja
1
1+1
1+1
11100 1/2 + +472202
+ 17ā
1 + 1+nā nā
1
1+1
+ 4n 0² 1
|uo0
1
+ nj
17
Given the choice of 77 S &
we have that
42z
Eu/lutt1 1es < ām)
(1
1+1
1e + 4no
[uo
Bounding the initial condition via constructing the constant R. Recall from (29), that for each epoch t, the error decomposition for the decision maker contains a term E. [|A(x 1, ue) - x² (u.)l? This means that we need bound on the per epoch tracking error which as noted above depends on the initial condition being bounded. Let us argue by induction that the value of R defined in (19) is such that [[[[ xx (ux)l1
R as long ||z-1 x" (ux))l2 R.
Consider ||ug- 1| < B and || x² (1o)1l2 & R. Set 6, = 2 throughout. We will construct a sequence RG that determines the epoch length
1
2R Er
1 (1-2-kp²) log(4)
Tt
log
k=1
needed order to hit e, target accuracy given the per-epoch initial condition bound || - x' (wx)l1 < R Our goal is determine R2 inductively and then show that there is in fact R, R, i.e. an absolute bound based on problem constants.
Base Case. Starting with i 0, the aim is choose (Ro, To) such that E [|A((==1, (no)==((mo)l1""" E I|20 xx (vo))l er.
Indeed, given that the agents run p-contracting algorithm in stages for To total iterations where
2R E,
To
2
log
+ Σ
1
k
log(4)
with Ro = R. we have that
E 11AA(1-1, un) ) xx" x->0<o0 (uo)
E 1|00
x (uo))1 S
60

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Warm-up Inductive Step. Let us examine the expected tracking error for the decision maker. For 1, have that
1 na
E 120 xx (uo))l
Bllui
u 12
U0o - 11=112 + r220²
2
4(1 + 220)
2 Ilu0 - u2=11 + 17 1700²
ET
4(1 + Log
2 1lu0 - u 109112 + 1 + 4(1 + L2 )
n7 n/²d?
2 1lu0 - 1ea113 13 + 21700²
which implies that
17²02
|[ - -² -
1110 uPa112 +
(24)
1 np
1 1 n/
More generally, from the above analysis, we have that
1 +++ nJ
E 1lue -200012 + 1/²0² + E 1| - x² (u.)
E l1441 - uP=1/2 S 2
2
4(1 + Lzg)
For 1. = =2 if B(|m1 - x² (ui) [[ S e with & = {1|=0
x² (11)11 - R1 we have that
+
7j
E U2
v u
v
E
u1 u 1|2 + 7 +
E | - (u1))2
2
2
4(1 + I'aa)
1 E
1
$
u1
1 + 1
2
4(1 + L2g)
1
< E Bllu 2a 1|2 + 2n²
Hence, we need to select (R1, TI) such that this holds. Here we appeal to the nrist-to-noise analysis in Section 3. Shifting indices that analysis as appropriate for this setting, we have that
1-
A2 1-p2 p2
20
E E|a - x² (21))11 S
||- - (=(u))11
+6
2
- p2-1
1 0²)
20²02
1.2
R +
+6
2
1-p² p²
(1 - p2)2
20
L2 L2Ai
< R
+6
1 Ø
p1-
(1 - 1²)2
where A7 = E, Ilui - uoll2 and x- is the given initial joint action profile of the agents. Using (24), we have that
417²02
E f| - w0ll2 < 2||u0
129132 +
22
11-1/2 < 2B 2
B +
+ nj
so that it suffices to set
20202 Ri R+ 1 0
T
4B + 16 no²²)
20202
I
4B + 8 n0?
+6
> R
+6
(1- 20
ā
1 22
(1 22)²
where we upper bounded 217² // (11 + na) S 27 0² E.0, 1/(1+na)+ S n0 and also multiplied the variance term by two (the reason for which will be come clear shortly). Moreover, note that 1) a/ (/([Le(1 + I(2g)) and Rú > Ro R.
&
For t = 3, we have that
+
1)0K
E [33
22 5
1 E uluu22
1/ + 202 +
E 11 x² (uz))l
2
2
4(1 12a)
61

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
and
(1-1-p)
2c²00² +6
L2g max 4
E [1 x² 2'(u2)11
(1-1111
1 - x² (uo))l +
2
- p²
(1 - p2)2
20202
Leg max452 A
< R +
+6
where A = E2 | wk- 11?
p
(1 - (1-p2)2
This means we need a bound on
A for each & < t - 1. Let's examine the t = 3 case in which we have
E llu2 u111² < 2
U22
u
1|
+ 2
|lu|
1
4
2
2- 2-rroa2
< 2
E flu
1) 1202
Ilo
+
+ nj
1 +
nj
1
+ na
1 nj
1
1
2m1202
4
112 + 4n
$
1000
u
2
+
n²=22
+
1lub
1 + nj
1 + nja
1 1 na
+ nj
1 + na
1 + 17
2
4nj²0²
2B
+ +11/ 0²
2
(1 + āml)
(1 + (1+ā)))
(1 + kn)
8
8n
< <4B+ +
+
ā
(1 (1+00 an)
16n0²
<4B + ā
where the second inequality holds by (24) (since we showed that E 1|200 - (uo))l e, =1/=2) and ān S a2/(4
For good measure, let us consider ( = 3. Here, we need to bound maxa33 I ||ue ux-1ll2 which in turn means we need to bound the following term:
E [u3 u2 2
E
|13
112 + 2 |u2
11
1
2n
EE |222
11
+ 22 uu- upe
+ 1j
1 + TJ(k)
2
1
211202
2 2-11222
E ||-1
- 11
+
+
+
||u - -p0s12+
+
1 + 170
+ 1702
+ 11(
1 + nj
+ Tja
1 + nj
1
3
3
11 0²20
2
2
17 1)²02
2
11:00
112
+
+
||u0 - u 11 +2.4)
1+ π/²
(1 + nā)
1 nā
(1 + (1+
8=1
< 4B + 16 1102
20"0" T-p-
L2 [B + 16 = -R1. We claim at this point that R. R for all t, and we
so that we set R2 = + argue this claim holds via induction.
+6
Induction Step. For any f, to obtain a bound on the E
| - x² (u:)ll we simply observe that
1
412²
1
t-1
4n2o0 (1 + nax)
E 1lu 11 2
1110-
1 +
2
2 +
+ na
+ n/as
1 nçx
< 4B + 16 no²
for any t.
ā
Moreover, we have that max; E |uu
U4 4-11 112 5 4B + n6 for all t. Now since 7) S a/(4L](1 + L2g), setting
20
I
402
R 1 p²
+6
4B + L3 + 122)
(1
22)2
results in the expected tracking error being bounded by 6, = 1/2 as claimed. This completes the proof.
62

---

Finite-Timg Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
This proof utilizes an arbitrary p-contracting stochastic method for the agents. It useful to see what the statement for some particular methods. Let us start with stochastic gradient play.
Proposition L6. Suppose that Assumptions 2.1, 4.1, and 4.3 hold, that we have available constant R> ||20 x² (uo)ll and that we are in the regime where o L. Leg so that there is unique performatively stable equilibrium. Further, suppose the decision-mate the agents employ a stochastic gradient player as A with p E [0, 1) and 0a E (0, oo). Suppose the agents run stochastic gradient play stage-wise via Algorithm 2. Set the epoch length to
runs Algorithmm 4 with Alg RGM using step-size
(/L) (1 + L2g)) where ā - Leg and
K
(
21 122
2R
K
2
Th
=
1+
log
1
log(4)
(25)
112
k=
A=
and tolerance E, = 0²² where K
I + 10g2 (-+T))
and
470 +6 6
4LLe (u7)²
402
: R+
AB + L7 + 1
Then the following estimate holds:
Eglluz 11 - 1221 S (1-
t 1--)) u
+ 4n02
2 1100
112
Notice the only change is the constants for the stage-based algorithm.
As noted in the main possible to employ any number of stage-based methods from stochastic optimization in order to obtain convergence to an e-performatively stable equilibrium. The following is a more formal statement of Corollary 4.5 from the main body.
Corollary 1.7 (Formal Statement of Corollary 4.5), Under the assumptions of Theorem 4.4, consider running the stochastic
repeated gradient method in l O, ........ KK super-epochs, for Ta epochs each with constant step-size Ti 2 =2-*1jo and such
that the last iterate of each epoch 1e is used as the first iterate in stage k 1. Fix target accuracy > 0 and suppose the
decision-mane has B 2 1lu0- uPa l|. Set nu- = a/ (A/3 + 12n)).
2 log
2B2
].
2 log(44
0²
To- =
Th =
for k 2 1, and K = 1+
in7j
L + 12 8
Then ||uT uPS 112 S e and IP | x² (1 s 2(c + Leqe) in a total number of epochs
K T
[3((1 12n))
2B²
> T
0
log
+
E
62e
Proof. The proof follows immediately from applying Lemma E.3 with A = RGM in Algorithm 2. Indeed, set constants
an
4
ā 4T + T22))
((n)
C= D
1o
so that
K T =
8L 12g)
2n
K
8L3 12g log(4) 2 x²
T3
a² log
+
k==
k=
and K is given in the corollary statement. Applying Lemma E.3 gives us that EE ||ur
u00 1 < e in T total stages. Then
E | x² (12 < 2E| x (ur))l 2 ||00 (WT) x" (122)112 < 2(er + Loge);
where 6, is given in the Theorem 1.5.
63

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
1.3.1. HIGH PROBABILITY RESULTS FOR NAIVE DECISION-MAKER
In the preceding analysis we utilized the expected tracking error bounds for the agents problem from the oblivious setting (Section 3, Appendix H). These results hold only in expectation meaning that the decision-makee would need to be able to deploy ue several times to be confidence in each epoch the results hold in the practice. On the other hand, it is more reasonable to leverage the high probability results from Appendix H.3 since these convergence results state that with probability (1 - 5) that a single deployment of de in epoch / ensures that ||,; - = I < log(e/6). Let us state such a theorem. Indeed, if the decision-make deploys their algorithms in real-time with irreversible drift, high-probabillyy efficiency results are desired in order to characterize the performance of the algorithm if were executed only once.
In addition to Assumption H.7 for the agents, we require the following tail assumptions on the equilibrium drift and gradient noise for the decision-maker.
Assumption L8 (Sub-Gaussian drift and noise). There exist constants A, a > 0 such that the following two conditions hold for all t 2 0:
(a) The drift A is sub-exponential conditioned on Fr with parameter A
E(exp(A43) Fi] I exp(>A²) for all 0 A 2
(b) The gradient noise de is norm sub-Gaussian conditioned on F. with parameter o²: P(|o::l 2 <l Fi) S 2
for all <> 0.
Note that Assumption H.7 implies Assumption H.3 with the same constants A and a.
Theorem 1.9. Suppose that Assumptions 2.1, 4.1, 4.3, H.7, and 1.8 all hold, there exists b, B >> O such that bB u C BB where IB- = {u E TR41| ||u||| I 1}, we have available constants R2 > ||x-1 - x² (uo))l2 and R., > I| 1p 2 and we are in the regime where a >> LLgbe so that there is a unique performatively stable equilibrium. Further, suppose the decision- runs Algorithm with Alg == RGM using step-size 1) S ã/ a/(AL](1 L'aa)) where ā == a - L, Leq and the agents employ stochastic gradient play (via Algorithm 2) A with o E (0, 20). There exists an absolute constant > 0 such that for any specified E N and E (0, 1), the equilibrium tracking error across epochs satisfies || x 112 S c log(e/0)
with probability al least 1 ō where e 0²² the epoch length is
K
[1+
2L2 112
2R
K
2 L2
Th =
log
log(4)
(26)
112
k=
k=
with K = 1 + logo (.
and
32((o,))
22eeaB 2)
e
R: R==R,++
+ 20
log
11
107
8z
so that the following estimate holds with probability at least (1 11-5) 5)3
||ue uPa 12 < (1
(1-2)
1700) 1 11u0 - -u20122 + (162 + (162+1)mg 1)no² 2
1
1 2(1 + L2g )) log? (9).
ā
The proof of this theorem follows Theorem 1.5, replacing the expected bounds on the equilibrium tracking error for the agent initializations-al i.e., E || 2 2 high probability statements. Analogous statements to Proposition 1.6 and Corollary 1.7 hold as well in this high probability setting, simply by replacing the appropriate constants.
Below, let us highlight the key steps.
Proof of Theorem 1.9, Recall the gradient definitions in (00) from the proof of Theorem I.5. Fix two constants v/, V2 > 0 to be specified later. Noting that u4+1 the minimizer of the 1-strongly convex function u ++ 1 |lue n9. - u||2 over U, we deduce that
1 11
2 11441 - 12
2 1/4 199 - -
719 2111
2
64

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Expanding the squares on the right hand side and combining terms yields
1 2 [141 - uP81|3= -
2 ue - u 17. (r: u(+1 - uPe) 1
2 =1lu411 - uell
1
ut uPe 112 n/ ut up0) ||uc41 - 79g, u441 - ue).
2
Using the fact that Eg(gs] = (ut),, we successively compute
2 14+1 - 1/ -
2 1/1e 1 - 11( - -u |141 uzll² 7)B2/99 U++1 - ut).
2
1
-
1 up 112 - -n(Gi((e)) us - -uP))
||lu441 - - 2el1 2 - n/ge, ue+1 - we).
2
1
|
u 112 (1G.(u441): ue+1 wPa)
|| uell
+ 17 (g. Ge(we), us - u++1) tie (G((ue) -
upe -u+1)
1/2
Recall that for any the loss f(u, 2) is a-strongly convex in so that
(Gpa (u++1), M4+1 - uP²) 2 (M4+1) - Gpa(u u++1 uPe) 2 aalut411 u
Therefore, adding and subtracting Gpa (Ue+11 }), we have that
(G.(11)) M141 w²²)) = (Gpa (we+ 1), ux41 - uP ) + (ue+1) Gpa (ue+ 1), U2+1 - uPa)
Now, the second term is upper bounded as follows:
(G. - Gpa(urz); u4+1 uPo) S Le Leggluu411111 uP/11
Then, rearranging the above expression, we have that
+
2 |ee+1 u/0112 2 511u 1p2112
21j
-
2 |luet1 - n(p + P2).
(27)
Applying Young's 's inequality to Pi and invoking Assumption 1.8, we have that
9: G.(w))l? + Mn villur+1 - wrl1
11
in /1llu+111111 uz 11
P1
2 x
+
(28)
201
2
2
We have the following upper bound for Py:
P2 < (G((v)) G. (ue+)))
12 - u1+1l1
202
2
(u,) - (w,))l (14) G. (u
+ vellupe u4t1l" 112
201
2
21]G](mu) - (u,)l
21 +
12g)11u +1gg)+22))1
uetil? v2llupe 11411
2
2
The first term in the first fraction can be bounded as follows:
(G,) (2+)ll < L3
(29)
This shows there is a time varying bias component in the gradient estimator. Here, we need to show that |[( u.) x" (2))l2 < e, log(e/52) with probability 1 5. for any 5, E [0, 1].
This is good point to lay out the proof structure from here forward. Define the events
& (IIA((+-1. u.) x (ut)l < e log(e/5.) /5)) and Eo = {1|xt-1 x3(4))13 s R).
65

---

Finite-Tims: Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
where we will specify what R is shortly. The aim here is then lower bound
Pr(E.) Pr(& (r( Pr(Ea)-
We know from the analysis of contracting algorithms, that within a r-length epoch conditioned &a, will have Pr(E&]Eo) 2 - 8g where is defined with respect to R. Hence, we need to bound the probability of the initial condition event Eg. This is where we use the high probability tracking error bound analysis from Appendix H.3. Indeed, for some absolute constant Cr. with probability - Eg,, we have that
||--1 - x (wm)ll S (1- ||--1 x= x0(u)]) 32(cc0a)²
2) (2 H1y
)
+
log
(30)
14
82
where we have bounded the drift (w=(()) xx (ue-))l S Leg Vegllue u1-1ll all t. Immediately", that we
2Leg B due to the fact that us u C BB for
32(cx0a) + +0
2Log B
c
:: R2 +
log
My
6m
Now, coming back to the analysis of llue uP81], we now have that Pr(E,) = Pr(EclE)) Pr(Eo) 2 (1 - 82)2. In this case, we deduce that
< Lie, log(e/8)
21 + 1:2g)11 114e
414111
M2lluPs u U++11 12
U2 Pr
2u2
Coming back to the bound (37), we have that
1 + 2na
|1 villuc+1 - Uz 1=112
|1e+1
uP21 $
11 1101122
211u uel 2ell22 +17
2
211
I3Cr log(e/0)
2T,3(1 + I
llee
u4+1l 112
U 12llure
26+111 112
+ 17
+
1/2
2//2
2
so that
2na - 1712
wr 12 + no²2
+ [[ge)oo(())
1- 1-222(1- + L )mp
||u111 - 2 < 2
wrll?
2
2v
2
Letting 01 = -1111221, 21 + 1/2g// /a and 122 ã ensures that the last term on the right is zero. By the assumption
- (4L + L)g)), we have that > 4L3 (1 + L/g)/ā so that 2 .y Hence we have that
+ nā
1 u
] 11ue Th 12 + 111. log(e/6z) 4(1 + L2a)
[u411
2
so that
2n²
1 c, log(e/55)
|141
12
||u - w
wpal +
11
+
1jα
1 n/
1 nā 4(1 + 1.2g)
(31)
(1
2 1 1|2 21bb
+ 1 nā 4(1 + L2n)
1 6 log (0/()))5))
Under Assumption 1.8, there exists an absolute constant 2 such that || is sub-exponential conditioned on F, with parameter o0 and Φt is mean-zero sub-Gaussian conditioned on F, with parameter ëo for all / (cf. Lemma 3 from Jin et al. (2019)). Assumption 1.8 also implies that A is sub-exponentia conditioned on F, with parameter 2
|||-- - x ("o))) thereby allowing It to be a function Note that we could reduce this term by more specifically bounding (1 47) current iteration instead of using the fixed bound ||--1 - x. (uo)) < R..
66

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Given (31), we apply Proposition H.8 with
6 log f. 0-
nja
1 6 log 1 )
Vi= |luee 1P= X, 11x + 1 na 4(1 L2g
20
02
V1
2
+ na 4(1 + Lea
D2 0, and K2 O. This yields the estimate
Elexp(\|lue=1 exp (x(2 (2ar202 0²=
1 c log(
og
EE exp (2(1- n/
1 - - -
(32)
+ n/ 4(1 + 1.2
for all
(33)
202 + I+ma 4(++2))
log(e/6.)
Since (1 - ) E E(0, 1] and V2 is a non-negative random variable (almost surely), Jensen's 's inequality implies that
Ejexp(AV<<1)] S exp (Au,) E exp (AV,) (2-
S exp (hyy F. (eeep
Iterating this expression, we have that
E [exp(AVV)) S exp (2znoo + 1 1/ē 4(1 + 12gg
1 e, log(
1-1
"²)")
) (Fleep(AVo))) 1-
Σ
1
2
5=
= =exp(Nu) exp
{ (1(1-
nā² 1
Vo
22rr²0²
+
e, log(
Σ
1-1
(1
nā
2
1 na 4(1 L2g
2
s=1
I exp
A ((1-
nā
Vo +
2212202
+
1
e, log( e.)
Σ
(1 (1-
nā
2
1 + 1já 4(1 + 120))
2
==0
A ^(1
nā
2 c, log 8,
< exp
Vo
+
2
(na)² 4(1 L2g))
for all À satisfying (33), where the equality holds since |lvo
112 is a constant. Recall that ē E 1 and ny S 1 so that
4npo
e, loolo( x-r
162002
2 e, loglll f-)
+ (na)² 4(1 + )2g)
=v==
ā
ā
(nā)² 4(1 + L
and
1
ā e, log(
ā
min
16 ōno 201202 + 2 log(
16ē1j02
2
a 41+ 1m)
na 4(+12)
Hence, we have that
E exp (x (x
1
1221 (1
1jā
1 - uPs 122 {)) < exp(>v) TSYToA
2
Rewriting this expression, we have that
E exp (2 (lu4- 1/ - -(1 ) Il10 up9l12))
S 1.
exp(>v)
67

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Applying Markov's inequality, have that
Pr exp (> [1ue- -2-112- -1- n/a) 1
11200 - 2 -2911)) exp(Ar)
ou 1uo -u9l13))]
E exp (> (1lue-wPal1 - (1 2
ná
S du.
exp(Ae)/05 pu
Therefore, setting À = 8. with probability 1 - our we have that
||u4 112 = (1
n/a
11u0 uP0112 +
162r102
+ (nā)² 4(1 + Loa)
2 Er logg (0))
log 8
(34)
2
conditioned on the event & holding. Setting 4 = 02² (34) becomes
||ue 11 < (1
11 + (162+ + 1)no²
1 2(1 + L2g (1+
))
}
c
c
|luo
max 1, 1,
log
(35)
2
á
8z
8y
Then all together we have we have that (35) holds with probability (1-6,)( 5,)2 With 8n = dg = 8 for some E [0, 1] the claim holds.
1.3.2. BOUNDING THE TIME THE Low DRIFT-TO-NOIST REGIME IN EXPECTATION
Reflecting back Figure 3, the target accuracy can be better optimized if the agents switch their step-size to the optimal 7+ once in the low drift-to-nat to-noise regime. Hence, it is interesting to characterize the time T after which max;-r E [ Ug ensures the agents are in the low drift-to-noise regime in expectation.
The following is the formal statement of Proposition 4.6.
2:00 Proposition I.10. Under the assumptions of Corollary 1.7, the estimate maxest E 1lu ux- 112 S
holds
4.v3Lo
after T = Ex Th S ( log
12B2)
aPc) epochs where = = (/²oa//44// Lea LeaL
Once in this region the agents are naturally incentivized to optimize their learning rates (i.e., selecting y.) will enable them to more effectively stabilize the learning process.
Proof. We aim to show that
2
12.0.
max B Ut 1-
4v3 Teeq 1.2
Let us first bound the sequence of differences for any particular l. Observe that
1u4- - 14-11² 1|2 $ 2( [1 - u| + 1|44-1 - uP* 2)) for any 2 1.
Choose (s, T) such that ||u - 112 < E. Then, we know that since ur+1 an update from the (K + 1)-th stage, we have that
E |ur++1 up5112 (1- a1/) E |rr
Av
12
1
āTT+1
402
á²
< +
1 + 2x+1 4.((14111122)
62
22K (4. [ + 1222)²
402
2K+1 44 (. + 122
ā²
22K (4 12 + L2g ))
2.4
Set
1 2k 4 I + 12
40² 12 + D
1
02 .4.4 4 17 + 12g)
28
68

---

Finite-Timi Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Hence, by setting = (1
u0o (/33L
2
we have that
2
1² Lee L2
E |14+1 wrl1
4/3
This holds for any T. Thus by setting
K T
L1 + 12
2B²
o²
Tk T o
log
+
σ²
a2c
1=1
L3 +
L2a
12B²
(4v3. Loeg 12)
60 1
=0
log
2
(p²og)2
a²(HPoa)
we have that the drift-to-noise ratio is the low regime in expectation.
I.3.3. NAÎVE DECISION- MAKER: DETERMINISTIC AGENT ALGORITHMS
Additionally, agents may run some deterministic algorithm. In this case the agents do not need to run stage-wise algorithm since they do not introduce the additional bias due stochasticity of their algorithm into the decision-makers problem.
Proposition 1.1. Suppose that Assumptions 2.1, 4.1, and 4.3 hold, that
sup B[[ + E)I] & Ius (v,x))uxxX
that we have available a constant B |100- x= (uo)ll, and that we are in the regime where a > LgLea so that there is a unique performatively stable equilibrium. Further, suppose the decision-maker runs Algorithm 4 with Alg: == RGM using step-size 1) S 113(+112
where ā : a LLgg and the agents employ a deterministic p-contracting algorithms (i.e.
Ja 0). Let the epoch length be given by
2L3 ānoz
))
log
(
R
1 1-p
1og(1/p2)*
Then the following estimate holds:
Bellu411 upa112 <
(1-
am)
2 1120
u2a + 4no
To prove this proposition, need technical lemma the contractive deterministic dynamics.
Technical Lemma. For both the na've and strategic settings, we will need the following technical lemma on the behavior of the stochastic agents play. Recall that in each epoch the agents initialize their algorithm at x 27-1 and that, by an abuse of notation, 2o =.--
Recall that when the agents' algorithms are deterministic, Definition 2.3 reduces to R+I - x² ||
x00 (will² & p²1|2 - (u,)..
so that
|| k+1 - (u+)) S p||= - x" (ur)ll-
The following lemma will be used in the proof of Theorem I.5 when the agents are deterministic.
Lemma 1.12 (Deterministic Agent Contraction). Suppose that the decision-maker is running Algorithm 4 with Alg == RGM using step-size y) and under the assumption that suP(v.a)euxxx (((u,x))) < I. Further, suppose agents use p- contracting update (Definition 2.3) with E [0, 1) and a. = O. Under Assumption 2.1, the following bound holds:
[ - x= (1+)l s 0² (p--11100 x"(o)) 1 Lou
p
69

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Proof. Given Definition 2.3, we have that
--=)))x)) S pاا=م (wx) - x (w))l
Iterating this expression we have that
20 (us) - (u=ll) S p 11x_1(u=-1) x² (u+)l
Adding and subtracting appropriate terms we have that
|| (ux) - (u=)ll S p² --1 (u²-1) - x (u--1) + x² (u--1) x² (u+)
S p² | (u--1) - x² (u-1)) + p Leal|ur - uel
Continuing in this fashion we have that
|| (ue) - x² (u+) & p [ - x (u--1)) + p" Leq 1 11:41-100 well
1 p² (p" 2 (1(2) x' (uc-2)l + p Leg uu- - ue-1 + p" Leallue- uell
$ p² p² 1-1 -1100 - x² (wo)ll + Leap" Σ - - u1-0-1l
$ p 1 x' (wo) || + Log Lall
where in the second last inequality that u4-1 V/ VV 2-1) and (u.((,z)) [[V.[(u,=)] s Ly-
the fact that p" S p for any 1, and in the last inequality we use the fact
Proof of Deterministic Case. Now we are ready to prove the deterministic agent case.
Proof of Proposition 1.1. The proof is the same as for Theorem I.5 up to bounding the bias due to the agents updates.
Given our assumption on the deterministic contractive dynamics of the followers, by Lemma I.12, we have that
(m)))((u+) Gps(uul)) S L2B,
|| A| (f:11 u.) - x² (u=)ll
< 23 p' - xuu))) + nlog In 2
1 p
p||z0 x (uo)ll + n Lu
< 2. 2-
P
Therefore
L3 C2)
212(11
1:2g)l(r u4t1l12
12 - uet1ll
P2 <
+
122
2012
2
Coming back to the bound in (37), we have that
1 + 2nā
1
(
0²
Er
/ul11 u1l 112
E, al
uPa
<
1/
- Eyl [1411 - 2ell2++ +
+
2
2
2
2
L
[2 + L2g)
Er
llue
ue+1
D2 PeEellupe
We+ 11
(2p² 222=52 C2) +
+
1]
112
1/2
so that
1 + 21jā
1//2
E, Bullut11
u <
11 - 1
1
+ 1]
2T.
2
-21
221
1/2
1 - 2I
+ 122 Mup - 1721
E2 |1411 u/.1
2
70

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
2 and 12 = â ensures that the last term on the right is zero. By our assumption that indeed,
Letting V1 17-
we have that z (2)
n S 412(1+12))
so that V1 2 2n
21 + 12n
41 229) 21 + 12g 21 + L
ā
ā
ā
211
Hence we have that
1 170
21
E, u141
22
u10 + +1"00² + 11
Now, choose stated in the theorem to ensure that np²r
22,0²
0n Indeed, this inequality is equivalent to
21302 )
āmo²²
22
1
T log p² & log
T - log āmo?
log(1/p2)²
which is precisely the stated lower bound on Hence, have that
4
E, Blllee11 11
llue 1
n/a²
1 nj
1 nja
Recursively iterating the above expression, we have that
4
4
Eg [lluu411 - 1/21122
(1 11111111111111 uP
2 2
20
1 + 7/
I + 7/
1 nj
na
1
|luo - 112 + 41720²
+ n/
+ 117
1
|luo 122 417²0²
1 1/cr
+ njo
Given the choice of 7) S
we have that
(1)
Bellu4+1 1pal12 S (11-
âr) 2
|110 upal12 +
4no²
ā
as claimed.
1.3.4. NAIVE DECISION-MAKER NON-STATIONARY NON-STRATEGIC ENVIRONMENT
Now generalize the case where De (u) now depends that the non-strategic component of the environment is also deeeeden- This requires the additional assumption that the distribution D. is L -ipschitt continuous (Assumption I.2), and we also need that < (L + Leg) which is already required for existence and uniqueness of the performatively stable equilibrium.
Theorem 1.13 (Naive Repeated Gradient Method with Non- Non-Stationary Non-Strategic Environment). Suppose that As- sumptions 2.1, 4.1, 1.2 and 4.3 hold, that we have available constant R > 1|z0- - x" (ua) and B >> ||u00 wpa and that a < Lz(Lan + Lea) so that a unique performatively stable equilibrium exists. Further, suppose the decision-maker runs Algorithm 4 with Alg == RGM using step-size 1) S +1, where == a - L (Len + Lea), and the agents employ a p-contracting algorithm A with p E [0, 1) and a, E (0, oo). Suppose the agents run their p-contracting algorithm stage-wise via Algorithm In this case, set the epoch length to
K
2R
K
[
log(4)
Tx
log
+
(36)
0
1
1-2 2 p2
k=0
Am
71

---

Finite-Timg Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
0 (1-p²1z)
and tolerance = o² where K
1 + log2
and
20
Lin
0²
:: R+
6
4B +
8
fa
[1 + 1
Then the following estimate holds:
Ballu411 - 11 1 (1- 2
11 + ano²
1110
Recall from Corollary G.5, that if the agents run stochastic gradient play stages then we are able to characterize precisely the number of iterations required hit a particular specified error tolerance. This is where the epoch length in (41) is derived.
Proof of Theorem 1.5. Define the following objects:
9r Vullue, (17 ())), where &- De(ue);
Ge(ue)== = E (nDe(u))
Vul(ue, (2) (ux)
G,(ue) == E
Vul(ue, (x (ux).
(~De(uu)
Gue( == E (~DD(um))
Vul(ur, (alluu;(""'( (xP)),,
Also note that EE, [gc] Gr(w)) (.. ie., the gradient estimate dr is an unbiased estimate of the time varying expected gradient G Fin
_8
argmin well
E
((u,)) so that
u wes 0 Vueu.
Fix two constants V1, V2 0 to be specified later. Noting that u4+1 is the minimizer of the 1-strongly convex function + 2 19:- - =u|2² over U, we deduce that
1 2
1
M1t uPs 13
179: -upe
1/u, 7.9
11+1112.
Expanding the squares on the right hand side and combining terms yields
- u141 - up <
1
2 Ue -uss (T<ge, uc+1 upe)
1
2 ||uet1 - uell
1
2
uu uP=1|2 n/(c, 2 - ups)
|| - -4112 179, u441 - ux)
2
2
Using the fact that Ee[ge] = G..)) we successively compute
Ee 2/l/u - u2
<
[u pa (E.st, Ue wPa)
Bell Belluct1 - wel1 2 17Bx ue41 - we),
2
16
2
17
1/4 2 2 ((G((uu), ue - -up) 2
[Ell|uce - -uell - 171EE (ge, ue-1 - ue),
n),, (ue+1): u4+1 ups) ] Relluc41 11l2
||u,
2
+ 1 E, (g: Gr(u:), u Uet1) +M (,) - G. G.(++)) up -1++1)
13
Recall that for any 2, the loss C(u, 2) is atrstolglyy convex in that
(Gpa(ut43) U1+1
uPs) 2 (Gps (oc(+))) Gpa(upp (uPe), u441 - uPs) 2 allutt1 - 12
72

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Hence, adding and subtracting appropriate terms, have that
- (G. (uc+1), u++1 ) - (G, (uc-1) Gpa u141 2Pm) - (Gpe (u(+1)) ue+1 uPa).
The first term is upper bounded as follows:
-(G+(u++1) - (pt(4)))) 441 - 5
- Lz L - u
The second term is upper bounded using a a-strong convexity of in u as noted above. Therefore, as in the proof for the stationary non-strategic environment, we have that
1 2na E. ||uet1 uP5 _ |1ue u/2112
1
(uel - uell + (P( P2).
(37)
Applying Young's inequality Pl, we have that
E, 11:: G,(u))l1
E,
11+1
uel1
o²
2 E, || 11+1 - uel
Pi
(38)
2/1
2
2/1
2
We have the following upper bound for P2:
(u)) - (.(411l 1y - - 112
Pa S
2V2
2
2E,l[Ga(ue) - (u,)l + 2E, (u,) - G. (2
+ 22 ||ups
ue+1
12
2/2
2
2E.l[G((ue) (u))l + 2L2 + L2g + Laa) u411
|I
ue+1 112
+
2v²
2
The first term in the first fraction can be bounded as follows:
G.(() G. (1=)l
Eg (EED. Vullur ()) - (w)) Vullu, 1( ue) x (u.)l?.
This shows we have a time varying bias component in our gradient estimator. Recall that
2R E
Tk 1 p²
log
2 p2 log(4)
k=1
total iterations where K := 1 log2
[2c-02 [1-p2)e)
Moreover, the decision-make sets e, = 07202 Therefore, we deduce
that
L3e,
21 + L3 + L2a)
u4+1ll²
D2 Elpe u141l1
+
U2
202
Coming back to the bound (37), we have that
+
2njā
1 11:
1 1Pell2
0²
v u0+1 uell
Eg [141111
112 <
BBlluu44 - 2012 +
EBll
2
2
2
221
2
D2cr
21 + 1 + I22
112
V2E, 12E,11upe
2e 1 112
+ 17
1/2
202
2
so that
1 - 2nj
1122
E,
upol12 <
1/1 - 18
1102
+
T.7tr
2
2v1
1
2T +
I2
+ 2 )mp, -1p1
Er Belluct1 wr|1
73

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Letting V1 =1] 211(+22++22 +22)) and 1/ â ensures that the last term on the right is zero. By assumption that n S 112 +22))
we have that 1 4 11+ + so that V1 2 1 indeed, we claim that ā
2n
21 + 69
+ 12
21
Rearranging, this is equivalent showing that
2L Leg + L
1
2
Now we can lower bound the left-hand side as follows:
2L] (1 + L L
41 L + L
21 +
L2
L2
21
=
2
2
That shows that claim. Hence we have that
nā
Bellue+1
112
1 1
112
17
2 G
2
2
Then since 6 = -7²0², we have that
1
4
Eg (141
11
2:
112
+
120
na
n/a
Recursively iterating the above expression, we have that
4
4
Eg Bullu411 115113 v
(1/26-1 12
1²002
+
n²0²
1 nā
11 nj
nj
na
1
1
|luo u21112 + 41720²
+ 1j(
1 + 1-a
1
Iluo 1
+ +17=00²
+ nā
170
Given the choice of 17 41 J
have that
u1llu+11 - 11 + nā
uPel
x²
S
s11-2)
017 )
| - 2011
4n
T.
+ L2 +
L2
ā
The choice of constant R follows from the same proof in Theorem I.5. This completes the proof.
Note that T12(1 I2g + I.2.)) can be replaced with 122 + T2 T.2,.) for more precise Lipschitz constants.
J. Strategic Decision-Maker
In this appendix section, we put all the formal analysis for the strategic decision-maker. Let us introduce some needed notation. Let
C) u-Bd
E [5-D.
[e(ur + du,, A(xr, or + 80x), +3)]
denote the smoothed expected loss at time f, and let
L (u)
[e(u + do,, x= (u: + +vx) + E)]
ENDD
denote the smoothed expected risk. The smoothed expected risk is evaluated when the strategic agents are at the Nash equilibrium x (w + 6v;) for the reported value i, + -ō,, The estimate ği is an unbiased estimate of VL2 -.ci. Ep [
v L. (w.).
74

---

Finite-Ting Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
J.1. Technical Lemmas
The following series of lemmas allow to bound the error between the true gradient of C(u) and the zeroth-order gradient estimate gr-
Lemma J.1. Suppose that Assumptions 2.1 and 4.1 hold, The smoothed expected risk (u) satisfies [V((u) L8, where T. == Le(1 + Teq))
Proof. For any points u, u' U, successively estimate
[V) (w')ll
E w~B
VV
8uo) VL(uu dwo)ll Tl u
Therefore V is L-Lipschitz continuous. Next, we have that
[[V](u) - (w)l
E [VL(6w) VL(u))I S L5 E
|
S Lő,
w
w-B
which concludes the proof.
Lemma J.2. Under Assumptions 4.1 and 4.8, by choosing d S cá Larfor any (0, 1) the smoothed decision-dependent risk
(u) is (1 - cjä-strongly convex.
Proof. We first define h(u) == (u) Vl(u). Observe that Vh(u) = EwAB V u + 5w) V V²L( Since
u - (LL(() is Lx-Lipschitz continuous, we deduce that
[V((w)lop < E [ kw) VZL(u)llop S dhn E waB
||l|| S ōTn.
w~3
We therefore compute that
(VC (c v/) = -V
n(wu),() el) 2 (a Lad)]lu =2113
which concludes the proof of the first statement.
Now, let u² be the optimal point for & over U, and let u be the optimal point of L on (1 8y44 Lemma J.3. Suppose Assumptions 4.1 and 4.8 hold. Choose any ò < min(r, }.. Then the estimate holds:
8L + 1/u6 w01l
88L (ar
ā ā +8 ||0*||
Proof. There are two sources of perturbation: one replacing 4 with (1 - 804 and the other replacing L. with L
Set ø = 8 and ū be the optimal point for C on dil Thus 0 E V + (N) Then
||u - u6l S I|u" ū|| u w61l-
The first term is bounded as
allū Φu" || s dist(0, VL(ou") + Nau("d")
since Vl(u) + (u)((u) is ā strongly convex. For the second term, since u" is optimal, have that VL(u") + (u) Since (cu((""))= (u"), we have that
dOs VL(bu") + Nou(ou")) dist(0, VL(du") + Nu()))) [V((du") VL(u")] < 811|2"1|.
We therefore have that
||u" al| < | - <
[+ ã
||"")
Since is optimal, we have that
(-VC(ū)), u-10),,--00) -)) 50, Vu dll.
75

---

Finite-Timn Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents Analogousty, since u is also optimal we have that
(-VC' u u²) 00, Vu L.
Therefore
a|ا u211 S (VL(T) Vl("), ū u²)
$ (VL (u v((u),, i -c))
$ V (w²) - VL(u ) 11'l
2 Lö u²l
Combining the bounds yields the claim.
The next lemma bounds the error between the converged strategies z (u,) and the equilibrium x" (24) as a function of the previous iterates.
Lemma J.4. Suppose the agents are employing deterministic algorithms satisfying Definition 2.3 with E [0, 1) and 0. Under Assumptions 2.1, 4.1, and 4.8, the estimate holds:
[I((2,, we) - x= (we)l S p" (D-11100 xx (uo)l + plre 5(1 p)
t.d
Proof. Given Definition 2.3, we have that
| (u+) - x² (ux)l S p||x;- (we) x (we)ll
Iterating this expression we have that Adding and subtracting appropriate terms have that
|| (ue) x (u+)l S p² || (
(u-1) - x (u+)l
|| (we) x² (ut) S p² 1x (w--1) x² (u--1) + x (u-1) - x (w:)l
p" a ( (w)-)) x= (u-1))l || Lea baallut-1 u.
Continuing in this fashion we have that
[27 (u.) x= (u=) _ p² - (wr-1) - xx (wt-1)l 1)1l + p" Loa 1oal1 well
S p² (p -->1|> (u+-) - x (u-=))l + pat-
Leallu422 Leg-t
u--1ll 11) + p² Leg 1l1 Ut
$ p² p 1 120 x (uo)ll + Legp"
p² ouulu u----1l
1=1
where in the last inequality we use the fact that p² s p for any T 2 1. Using the update for the decision maker, we have that
l,d
[T+]((e) - x² (w+)l S pr ||= x² (ui)l + pLea
pd 2h 1-8
==0
t,d
p" 1000 x (uo)l) + pLeg 700 5(1 p)
where we used the fact that vio 2 Th- for all > 1. This concludes the proof.
Next, we use Lemma J.4 to bound the error between the gradient of the smoothed expected risk (u) and the smoothed loss C. (w+).
76

---

Finite-Tinn Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Lemma J.S. Suppose the agents are employing deterministic algorithms satisfying Definition 2.3 with p [0, and 0g Under Assumptions 2.1, 4.1, and 4.8, the smoothed expected risk and the smoothed loss satisfy
(ue)l Li (
Le (0'1 ='(o))
8(1 pp) ))
Proof. We have that
(w)) (C'(l S E
E [Vl(u + be,, oy (we + 804) + +)
u-3dd
E-D.
Vllue dv, (u+ + σv) |
S Le
unddd [1 + dv,) (u+ + o0,)11.
Hence applying Lemma J.4 gives the result.
The above lemmas give main result, which establishes that the decision-maker's updates converge the optimal parameter u' 22 (and correspondingly, the agents' updates converge the Nash equilibrium x= (u")).
Let us define useful quantity that we will use in the remaining proof:
Ci(o,) = (1=1 x² (uo)ll + Leqgto
8(1 8(1-p) + poac.
(39)
(1 p)2
so that
(V) s Li (cC((0) + posc 2
1-p1
J.2. Derivative Free Method for Stochastic p-Contracting Agents
We now state formal version of Theorem 4.9 and provide proof.
Theorem J.6 (Formal Statement of Theorem 4.9). Suppose that Assumptions 2.1, 4.1, and 4.8 hold, and that we have available a constant > || - x= (u2) Further, suppose the decision-maker runs Algorithm with Alg == DFM using step-size T7 a(t+1]' query radius ô < min(b, i, and the agents employ a p-contracting algorithm A with p E [0, 1) and aa E (0, Suppose the agents run their p-contracting algorithm stage-wise via Algorithm In this case, set tolerance 6, 8(1+Ty, constant e = 16(E.d² + 1), and the epoch length to
1 p2
12R log
1 k-k0²
T
Th
log(4)
(40)
ET
p2cF0 [T-p-yer
where K
1 + log2
and
20202
12 f2
mmax(402 B2, 16(Ld +1)
452 ((+
T
1
R+
+6
B
+
8²2
ā
Then the following estimate holds:
max max(2á (2ā262/1uu -2(13,c) 8² 1)B
202 ((1
L
E
un 2²
||"*||
The proof follows a similar structure to that of Theorem 4.4 (see Theorem 1.5 for the longer version).
77

---

Finite-Tinn Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Proof. Consider the error ||u441 u²1 Add and subtract u², and apply the triangle inequality and Lemma J.2 to get the following estimate:
2
[441 - u²1 = |lu+11 u0112 + I|us u²1 2 114+1 - u²112 +
8L (Oz α
+
8L (oz ā
+ + [1'1l)
Now, to bound the error ||4411 - 4 1|, we note by the nonexpansiveness of the projection mapping that
E [1|14+11 - u u²|1²] < Elllu, - us 97
I El[ - u²112 - 2n, Egr - + 11 ||
[Bll - u²112- BV un u²) v2 E 19
where we use the fact that [E[g]] = in the last inequality, and the expectation is taken over the randomness & and ot up to time
Next, add and subtract V (u,) from the middle term to get that
(VL)(u)), u ut) (VL' u4 =2> + (VL)(u.)- - (C)) u u0)
- 2 पن 1 1012 + (c) - VL (us), u²),,
where we have used the fact that L (xx is (1 c) strong convex with c 1/2 (Lemma J.2). Hence, we deduce that
Elllu+11 - u01191 - Blllu, - u n: 2|
s Billu u 10 2n B (VV L (we); u4 =²)
21 B(V c7 (ue) v (u.), ur u²) + The |1
Lgd
< (1 ) B[[lur w1'19] 2m E, E.VL (w.) - VL'( -u)) + 11 282
The agents are running stage- based p contraccning algorithms. For the moment suppose our choice of R is correct. In this case, we set 6, = (62 + 1) and choose
K Th =
1+
2L2 112
log
2R
+
Σ
K
(1+
2
122
log(4)
112
k==0 0
R=
and K 1 loga
Then have that
D2c,
11113- 5 (1
Bil 4e a u0119 + 8 + 1)2
&lG
8
U141
2
x² 82 + 1)2
8
1
Bill 4u 11119 + (Ldd +1
t + 1
a²8 + 1)2
Next, we claim that
max(a?82|| 1011,,8EE66 + +1)
E [44
(t+2(++1)
To this, let D. E[[lu | so that need to show the above claim given that
(1-221)
2 2) D. + (e +1)
8 at + 1)2
Det1 5
lt+1
78

---

Finite-Tine Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Clearly the claim holds for Suppose it holds for some fixed / 1. Then have that
8
D++1 1
1
D. (e.d +1)
t+1
a282 + 1)
2
8(E.d +1)
(Ldd +1) at82 1)2
t t+1
(t+((++1)
8l +1)
8262
(++1) 1++)
alL.d + 1)
1
82
(t+22
Therefore
E 1i4e u 1/1 = max (4a² 14p - u 10112, 16( + +1) + 28²
((1+2))(e 1|
(t
Finding the constant Rt. What remains is to show that we set R correctly. The proof follows an analogous proof to the repeated gradient method (Theorem 1.5). Recall that
E 1lue u²1 max{4a 8 B², 16 + +1) -28² 28
L
B
1aa(t+11
Hence, obtain bound on the E |1:111 x² ( simply observe that for any
2 1, have
E 1144-444 u441112 max 16(E + + + 45²
((+
L
- L
B
8²a2
ā
Moreover, this implies that
max
+1)]
+ 402 211+
B B+
max E A:t
lug
2x-1112
for all
8²
so that
20
L2 B32
max maax/402022 42 16(e +1]
(1++ B +
:: R+
+
6
+ 45
B
0²0²
where 3 = =11-1²) This completes the proof.
Observe that we replace the expected value bound on the drift with high probability statement as in Theorem 1.9. Essentially, where we have bounds like E || xx (w))l S 6,, we replace them with bounds ||x,-1 x² (ut)ll < 6 log(e/0) which hold with probability at least (1 5) for any selected d E (0. 1).
Theorem J.6 allows us to obtain the following convergence guarantee.
Corollary J.7. Suppose the assumptions of Theorem 4.9 hold. Fix target accuracy < 462 (1++)) and set 8 áv e/a L)B + L) and n) 4/(ā(! 1)). The iterates (u, xx) converge to an approximate Stackelberg equilibriam: Biilu- 11] [| < and [[]|x x (2' ) < 2(e, LegE) hold all 16 max{āateB ,(L,d + 1)((a+
L)B ())))(
In the proceeding corollary, the lower bound on t in terms of the number of epochs. In terms of total iterations Σ To the rate is O (g (log (1/r)) + oo./ o2//,)). This rate is equivalent to O(T-1/2) in terms of iteration complexity where Σi= T..
79

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
Proof of Corollary 4.10. The assumed upper bound directly implies that d s <a/(2lg) and å < b. Applying Theo-
rem J.6 yields
max 20 u0 11 28
((1+2)
L 2 | |1 + ②
Bl[ x²1]
(2 1)
max max(8a* B², 4c + I. + 1))
+ 2
Eā (t 1)
Setting the right-hand side to e and solving for I, concludes the proof.
We can also specialize the result to the case where agents run stochastic gradient play (in order to better understand the constants).
Corollary J.8. Suppose that Assumptions 2.1, 4.1, and 4.8 hold, and that we have available constants R> I x² (wo) ||2 and B= > llu0 u²I??. Further. suppose the decision maker runs Algorithm I with Aig := DEM using step-size t7 a(++1) query radius 8 < min(b; b, and the agents employ stochastic gradient play as A with p E [0, and 0a E (0, 20). Suppose the agents run their algorithm stage-wise via Algorithm 2. In this case, set tolerance == 16(L,d + +1), and the epoch length to
5(1+1) constant
1 p2
2R Er
1 1 2- 0²
Tx
log
log(4)
(41)
where K
1 log2
0
Then the following estimate holds:
E [1 - w²1 maxx(2028)) uug
u² 11 cf
||" (1++)) 4
28²
( 115
The proof is identical to that of Theorem J.6 and hence we omit it. Moreover, a corollary completely analogous to Corollary J.8 immediately follows.
J.2.1. STRATEGIC DECISION-MAKER DETERMINISTIC AGENT ALGORITHMS
We can also specialize the case when the agents use deterministic algorithm. In the latter case, much like the repeated gradient method, the agents do not need to run stage based method.
Proposition J.9. Suppose that Assumptions 2.1, I, and 4.8 hold, and that we have available a constant || - xx (uo) I|- Further, suppose the recision-maker runs Algorithm I with Aig := DEM using step-size de ब[++] query radius
i < min }.). and the agents employ p-contracting algorithm A with algorithms (i.e., o = 0) and the decision-maker receives noisy observation A(I ue) + in each round where & is zero mean and finite variance. In this case, set the epoch length such that t 2 log( /nald Tog(1/p>> constant 32f.d and agent tolerance 4 C.(0))p. Then the following estimate holds:
[0,, 1) The agents employ deterministic
max(2a² 82 121lum 121 + 20
(1+
L ||
L -/4
E [1
u u²112
8taa + 11$
Proof. The proof proceeds in a similar fashion to Theorem J.6.
Consider the error |lu+41 - u² 112 Add and subtract u and apply the triangle inequality and Lemma J.2 to get the following estimate:
1
(
8L +
8L +8 [1"1))
2
|u4t1
u²1 1 |lu141 20112 +llus u²1 < |lue11 - u 20112 +
2
Now, to bound the error | 111 11, we note by the nonexpansiveness of the projection mapping that
E Elllue+1 - u 1 < E[]lu - n 71901191
< Bi[1 u²112 - 27 E Egt,, - -u²) + + El 2|
< Blllue - dd112 22, c. (wr), us w²² Mp L8
80

---

Finite-Time: Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
where we the fact that Elga] V (u²) in the last inequality, and the expectation is taken over the randomness in g and oe up to time t.
Next, we add and subtract (u,,), from the middle term to get that
(VL)( ut u²) (ue), ue w²) + (VC)(ue) - (ue), ur u0)
S 2 4n - 111 + (u)) - V (ue), 24 u²),
where we have used the fact that L (x) is (1 c) strong convex with 1/2 (Lemma J.2). Hence, deduce that
Elllu++1 uull31 - Blllu u 7.9. n. 2|
- Billu - u =0113] - 2n E V Ld (wx). ut - =²)
2m, (VV VL (u,, 21 u²) + mp E 11
< (1 n Fl[1 r611]] 27 E(V 2 (u.) VL u²) + 111 28
Now, we bound the term (VC - VC*(u), u - u8) and we apply Young's ' inequality to this term to get that
E (V VC (u,), ue u²)1=
E EVV
VC
(u.) (u.))
E llue u 10112
201
1
E llue - u0113 1 (L (P)))))
+
201
2
where we have that 0 so that
0 11:00 x² (uo)ll + No oold
O. =
5(1 p)
Setting 11 == a/2, we deduce that
Bl|ue+1 11122 s (1 -naa
ma) E[| - 10 =11
2171
1
(L. (p
+ A
l u²11))
282
2
(1 2
T771) Elllu= u + E2.2
+ 21
L (p=O.)²)
282
Hence, if it is the case that
2m
Th Lad
1 pT C <
(42)
282
then we conclude
Bl|we+1 u²11 < (1 11
11: 2
á
Elllu: u0 12 1
Ed 82
(43)
Indeed, the bound in (42) is equivalent to
Talad ā 482
1
log(p") < log
- r log
1.771
log(1/p))
which is precisely the assumed bound on r.
Recall that 7)-
|ा. Hence we apply Lemma E.1 to obtain the final bound in this case. Indeed, we have that
E 1|4 11 max(4a2 82 I10- =111 32
L (1++
L =
282
|
|| +
(44)
a²02(t+1))
à
as claimed.
A completely analogous corollary to Corollary H.4 directly follows.
'Young's inequality for inner product spaces says that for two vectors u. V where V is inner product space, we have in
(u, v) S 1 |lull + 2x ||nl| for any À > O.
81

---

Finite-Time Convergence in Stochastic Stackelberg Games with Smooth Algorithmic Agents
J.3. Strategic Pocision-Makers Non-Stationary Non-Strategic Environment
Recall the gradient deviation lemma (Lemma I.1) and the assumption on the environment distributions being Lipschitz continuous (Assumption 1.2) from Appendix 1.1. The following assumption implies convex ordering the non-strategic decision-dependent random variable which the loss is dependent.
Assumption J.10. The probability measures (u) and loss satisfy mixture dominance-i.e., i.e., for any (u, E u X and À [0, Il, the following inequality holds:
E (1))
E E(u, (I, (-12D(()-11-)))poo))
E(u, (x,{)) for all v, U.
Under these additional assumptions- namely Assumption 1.2 and -10-Theorem J.6 and Corollary J.8 immediately follow. The only change is to the gradient estimator and the Lipschitz constant for the gradient of the expected loss. Indeed, we have the modified costs
(u,) = E
E
[e(u + 8er, (A(zi, un + 50x). E>>]
5 aowdd (or
and the modified smoothed expected loss at time 1, and let
C (ux) = 8 vn-ad (usttt))
E [e(u: + ouz, (ux + 80x), E))]]
denote the smoothed expected risk. The smoothed expected risk is evaluated when the strategic agents are at the Nash equilibrium x" (u,+ + ōvt) for the reported value ut + du, The estimate is an unbiased estimate of VL2 V.g-ii.. ie.. E [gc] V V.f((u) Further, we replace L. with L = Teg T:z [Tzq + Ieen)
82


Reviews:
[{"review_id": "HPr3Hx1uGz", "reviewer": "Reviewer_GNfd", "summary": "The paper explores a learning problem in the context of Stackelberg games with single leader (decision-maker) and multiple followers (agents). The authors consider a setting where both the agents and the decision-maker are learning. The agents are learning, for any action taken by the decision-maker, the Nash equilibrium of the game induced by such an action. The decision-maker aims at playing a sequence of actions ensuring the convergence to a Stackelberg equilibrium. Both the algorithm employed by the agents and the stochastic environment are unknown to the decision-maker.\n\nFirst, the authors characterize the equilibrium tracking error of the agents, highlighting the contribution of the noise and the \"drift\" induced by the sequence of leader's actions. Then, they analyze the convergence rate of a simple decision-maker that ignores the fact that the agents are responding to it. Finally, they devise a more powerful decision-maker which adopts a derivative-free method that converges in $O(1/\\epsilon^2)$ to an $\\epsilon$-approximate equilibrium.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our paper, and acknowledging some of the strengths of the paper.\n\n**Qs for Authors:**\n\n**Re1.**: No, the decision-maker **(DM)** doesn't know the algorithm or $\\mathcal{D}\\_e$ *a priori*. \n- **Algorithm**:  In Line 396, DM doesn't know $\\mathcal{A}$. From the environment, it receives a sample of $\\ell$ evaluated at the agents' response. In practice this means that the DM deploys action $u_t+\\delta v_t$, observes $(\\mathcal{A}(x_{t-1}, u_t+\\delta v_t),\\xi_t)$ and then computes $\\ell(u_t+\\delta v_t,(\\mathcal{A}(x_{t-1}, u_t+\\delta v_t),\\xi_t))$ so as to compute $g_t$. It only needs to know its own loss and be able to query the environment.  \n- **Environment**: Analogous to the above point, the decision-maker doesn't know $\\mathcal{D}\\_e$. We assume that they can stochastically query it. \nWe will add further discussion to clarify.\n \n**Re 2.** Here, we are defining the problem the DM aims to solve if the the agents were not responding to $u_t$ but were at equilibrium. This forms the **in equilibrium** benchmark: i.e., the point to which the DM aims to converge depends on the environment stochasticity even when the agents are stochastically best responding. We show convergence to this stationary equilibrium so that we don't need a time-varying benchmark like many of the existing works on time-varying games. We exploit problem structure to get *stronger* convergence guarantees as compared to bounding stochastic tracking errors (e.g., we bound $\\Vert u_t-u^\\ast\\Vert^2$ vs $\\Vert u_t-u_t^\\ast\\Vert^2$ where $\\{u_t^\\ast\\}$ is some time-varying \"optimal\" sequence given the drift induced by the agents).\n\n**Re 3.** Thanks for catching this: it is a typo that should read $x\\_{i,t}^{k+1}=\\mathcal{A}\\_i(x_t^0,x_t^1,\\ldots, x_t^k,u_t)$. Here, we should have the notation $x_{i,t}^{k+1}=\\widetilde{\\mathcal{A}}\\_i(x_t^0,x_t^1,\\ldots, x_t^k,u_t)$ where $\\widetilde{A}\\_i$ are $\\rho$ contracting algorithms, and then define $x_t=\\mathcal{A}(x_{t}^0,u_t)$ as the $\\tau$ time joint algorithm since in the analysis that follows we treat $\\mathcal{A}$ as the $\\tau$ time response of the agents. We will update this notation to be consistent. \n\n**Re 4.** We are not aware of any lower bounds in terms of iterations for Stackelberg games employing epoch-based algorithms, and so it is not clear if it is optimal in terms of total iterations. We discuss lower bounds further below.\n\n**Re 5.** It is equivalent when Def 4.2 is restated in terms of the lifted $(n+1)$ player simultaneous play game as noted in the paper; e.g.,  consider $(\\mathbb{E}_{\\xi \\sim \\mathcal{D}_e(u^{ps})}\\ell(u,(x,\\xi)), f_1(x,u), \\ldots, f_n(x,u))$ over the joint action $(u,x)\\in \\mathcal{U}\\times \\mathcal{X}$, then the performatively stable eq (PSE) $u^{ps}$ is a Nash eq of this game where the environment noise is fixed at $u^{ps}$. The difference between this equilibrium and Stackelberg (SE) is two-fold:  the DM is not optimizing through the dependence of $u$ in  the agents' best response $x^*(u)$ as in a SE, nor in the environment distribution $\\mathcal{D}\\_e(u)$. This is why it is the natural equilibrium concept for Sec 4.1  -- i.e., the DM is only using stochastic queries of $\\mathbb{E}\\_{z\\sim \\mathcal{D} (u)}$ $\\nabla_u\\ell(u,z)$ instead of the full gradient  $\\mathbb{E}\\_{z\\sim \\mathcal{D} (u)}$ $\\nabla_u\\ell(u,z)+$ $\\frac{d}{dv}\\mathbb{E}\\_{z\\sim \\mathcal{D}(v)}\\ell(u,z)$ as detailed in Sec 2.3  and the discussion at the top of Sec 4.1. To find an optimal point for $\\mathbb{E}\\_{z\\sim \\mathcal{D}(u)}\\ell(u,z)$ the DM needs to optimize through $z(u)=(x^\\ast(u),\\xi(u))\\sim \\mathcal{D}_x(u)\\times \\mathcal{D}_e(u)$. Yet, it doesn't know the agents' preferences nor the environment distribution, but can query it. Sec 4.2, on the other hand, aims to estimate $\\frac{d}{dv}\\mathbb{E}\\_{z\\sim \\mathcal{D}(v)}\\ell(u,z)$ so that SE is the right benchmark.\n\n**Re: \"Other... Weaknesses\":**   \n- **Lower Bounds** are open and interesting, but beyond the scope. We comment on a special sub-case: \n    - In zero-sum settings, which is a special case of our problem, the ODE method in stochastic approximation provides some lower bounds. The continuous-time limit translates to a time-scale separation $\\tau$ [1]. Here, there are lower bounds in terms of eigenvalues of the game Jacobian block matrices; this could be any $\\tau>0$. It's possible to extend this to general sum settings, however, the game Jacobian doesn't have a nice structure like zero-sum games so it's hard to meaningfully interpret these bounds. This suggests, however, that $\\tau>0$ is necessary and that its precise value is problem dependent.\n\nThanks for the suggestions; we will incorporate them.\n\n- [1] Fiez & Ratliff. \"Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation\", ICLR 2021", "claims_and_evidence": "The claims in main paper are supported by proofs in the Appendix, albeit I did not check their correctness. The results are plausible given the assumptions, and the high-level idea of the algorithms employed is convincing.", "methods_and_evaluation_criteria": "There are no typical benchmarks for this setting. Nonetheless, the authors provide experiments on some typical economics settings (e.g., Kelly auctions) and a quadratic game inspired by real-world data. They also investigate the performance of their algorithms in settings where the theoretical assumptions are not perfectly met.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "I did not check the validity of the experiments.", "relation_to_broader_scientific_literature": "Stackleberg games have been extensively studied in offline settings. This work considers a learning setting, and is built upon previous works on Stochastic Optimization, especially the work of Cutler et al. (2023). While in (Cutler et al. 2023) the loss function depends only on the decision-maker action, this paper considers also the presence of other strategic agents that influence the loss.", "essential_references_not_discussed": "The authors discuss all the relevant related works.", "other_strengths_and_weaknesses": "Strengths: the paper addresses a novel learning problem, where both the leader and the followers are learning in a Stackelberg game. They provide an in-depth analysis of two different algorithms for the leader's problem and briefly discuss when one approach is preferable to the other.\n\nWeaknesses: it is unclear what exactly the decision-maker has to learn, and what they know in advance (see questions).\nThe authors do not provide any lower bound on the convergence rate (in terms of iterations) achievable in this problem.", "other_comments_or_suggestions": "Suggestion: after Corollary 4.5, the authors discuss the fact that the total number of iterations is $T\\tau$. To complete this discussion, it would be useful to provide the formula to compute $\\tau$ (up to constants) given the target accuracy $\\epsilon$. The same holds for Corollary 4.10.", "questions_for_authors": "1) Does the decision-maker know the agent's algorithm? Line 160 (right) states that the algorithm is unknown, yet it is employed at line 396 left. Similarly, is the noise distribution $\\mathcal{D}_e$ known in advance?\n2) At line 138 left, why is $x$ drawn from a distribution $\\mathcal{D}_x(u)$, rather than being computed by the agent's algorithm based on both $u$ and the previous $x$?\n3) At line 117 right, why does $x^{k+1}_{t+1}$ depend on the sequence of joint actions $x^1\\_t,\\dots, x^k_t $ rather than the sequence $x^\\tau\\_{t}, x^1\\_{t+1}, \\dots, x^k\\_{t+1}  $?\n4) Line 67 (right) states that the epoch complexity of your algorithms is optimal. Is it also optimal in terms of iterations?\n6) Is the notion of performatively stable equilibrium  in Definition 4.2 equivalent to the one of (Narang et al., 2023)? Why is it the appropriate notion of equilibrium for Section 4.1?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FLzptKDc9r", "reviewer": "Reviewer_ffEi", "summary": "This paper proposes an algorithm for a game in which there is one leader and $n$ followers. The leader chooses an action and the followers play a Nash equilibrium which is influenced by the leader's action. The solution concept is that of  a Stackelberg equilibrium. The game is static but is repeated during the algorithm. The main challenge is the fact that the agents are adjusting their behavior to the leader's actions. The authors provide convergence guarantees for their algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. Below we respond to your questions. Please let us know if this has clarified things.\n\n**Questions For Authors:**\n\n1. *Can you comment on the difference between Definition 4.2 and the notion of Stackelberg equilibrium on page 4 (left column)? How is this definition different and why is it necessary to introduce it?*\n\n    **Response**: The difference is that the decision maker is not optimizing through the dependence of $u$ in the agents best response $x^*(u)$; instead it is evaluated a the fixed point of the given $\\arg\\min$ expression. We introduce this because it is the natural equilibrium concept when the decision-maker does not optimize through  $x^*(u)$, but rather performs updates relative to the gradient of $\\ell(u,z)$ (where $z\\sim \\mathcal{D}(u)$) with respect to the explicit dependence on $u$ -- namely stochastic samples of $\\mathbb{E}\\_{z\\sim \\mathcal{D}(u)}\\nabla_u\\ell(u,z)$ instead of the full gradient $\\mathbb{E}\\_{z\\sim \\mathcal{D}(u)}\\nabla_u\\ell(u,z)+\\frac{d}{dv}\\mathbb{E}\\_{z\\sim \\mathcal{D}(v)}\\ell(u,z)|_{u=v}$ as detailed in Section 2.3 (cf Equation (2) and discussion thereafter) as well as the discussion at the top of Section 4.1.\n\n2. *Can you please provide sufficient conditions to guarantee that Assumption 4.3 holds?*\n\n    **Response**: This is a standard assumption in optimization for online stochastic gradient methods in games and otherwise (see [1--3]). For example, the assumption says that stochastic gradient methods that use gradient estimates $g_t=\\nabla_u \\ell(u_t,z_t)$ satisfy\n    $$\\mathbb{E}_t[\\Vert\\nabla_u \\ell(u_t,z_t)-\\mathbb{E}\\_{t}[g_t]\\Vert^2]\\leq \\sigma^2<\\infty,\\quad\\text{where}\\ \\mathbb{E}_t[\\cdot\\mid \\mathcal{F}_t]$$ i.e., the estimator has finite variance conditioning on all the previously seen data (which is the filtration part in Assumption 4.3). This is just stating that the gradient noise has bounded variance, given data to time $t$.    One sufficient condition for this is that the environment distribution from which we sample $g_t$  has finite variance -- i.e. $\\mathbb{E}[\\Vert g_t\\Vert^2]<\\infty$.   \n    As is standard the size of the variance can be controlled via stepsize choices, batching amongst other techniques.\n\n[1] Cutler et al \"Stochastic Optimization under Distributional Drift\" JMLR 2023\n[2] Narang et al \"Multiplayer Performative Prediction: Learning in Decision-Dependent Games\" JMLR 2023\n[3] Besbes et al \"Non-stationary Stochastic Optimization\", 2014", "claims_and_evidence": "The claims and the proofs are relatively clear.", "methods_and_evaluation_criteria": "Yes, they make sense.", "theoretical_claims": "I did not check the proofs in detail but the ideas seem fine.", "experimental_designs_or_analyses": "I checked the ones in the main body. They seem fine to me.", "relation_to_broader_scientific_literature": "It seems fine to me.", "essential_references_not_discussed": "Not as far as I know.", "other_strengths_and_weaknesses": "Nothing specific.", "other_comments_or_suggestions": "Nothing specific. There are a few typos such as \"inquality\".", "questions_for_authors": "1) Can you comment on the difference between Definition 4.2 and the notion of Stackelberg equilibrium on page 4 (left column)? How is this definition different and why is it necessary to introduce it?\n\n2) Can you please provide sufficient conditions to guarantee that Assumption 4.3 holds?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NLdytVbNIJ", "reviewer": "Reviewer_t2tf", "summary": "This paper focuses on learning in Stackelberg games under the setting where the agents might learn their equilibrium gradually. First, the author provides the equilibrium tracking error for the learning agents for a given sequence of the decision-maker’s actions. Then, a learning algorithm for the decision-maker, which can address this tracking error, is proposed. Convergence results for the proposed method are also provided, demonstrating the effectiveness of the approach.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper, and pointing out some of the novelties in your review. Below we focus on the key queries in your review which we believe should address your concerns.   **Please let us know if there are further clarifications**. \n\n**Theoretical Claims:** We label each of these points 1,2,3. \n\n**Re 1.** For clarity, Def 2.3 is stating that **within an epoch** (i.e. since $u$ is fixed and therefore $t$ is fixed for the decision-maker), the agents contract at a rate $\\rho$ to the equilibrium $x^*(u)$ of the induced game. That is $k$ here is indexing the steps within the epoch, and $t$ is the fixed index of the epoch. \n\nNow, we reflect on Prop 3.1 and *Cor* 3.2 and Prop. H.2: These are **across epoch results**. The confusion we believe comes from the fact that $\\rho^\\tau\\leq \\rho$ for $\\tau\\geq 0$ and $\\rho\\in(0,1]$. We have applied this to arrive at $\\mathbb{E}\\_t\\Vert x_{t+1}-x_t^\\ast\\Vert^2\\leq \\rho^2\\Vert x_t-x_t^\\ast\\Vert^2+\\rho^2(c\\sigma_a)^2$ from the expression in Def 2.3. \n\nIn Section G.1 of the supplement, we show that a \"one-step\" within epoch contraction translates to a \"one-step\" across epoch contraction; here is where we use the fact that $\\rho^t\\leq \\rho$ for any $t\\in (0,1]$. Note that in this section, since it is stated for general update rules (independent of the existence of a decision-maker choosing $u$'s that influence the behavior), we have dropped the $k$ notation and are just using $t$ for an iteration. For clarity, the statements in G.1 would look like the following: fix epoch $t$ and action $u_t$, then \n$$\\mathbb{E}[\\Vert x_t^\\tau-x^*(u_t)\\Vert^2] \\leq \\rho^{2\\tau}\\Vert x_t^0-x^*(u_t)\\Vert^2+c^2\\sigma_a^2\\frac{\\rho^2}{1-\\rho^2}\\leq \\rho^{2}\\Vert x_t^0-x^*(u_t)\\Vert^2+c^2\\sigma_a^2\\frac{\\rho^2}{1-\\rho^2}$$\n     Coming to the statement at the beginning of Proposition H.2: we have that there is a $\\rho$ and $c$ such that $$\\mathbb{E}\\Vert x_{t+1}-x_t^\\ast\\Vert^2\\leq \\rho^2 \\mathbb{E}\\Vert x_t-x_t^\\ast\\Vert^2+c^2\\cdot(\\rho\\sigma_a)^2\\quad\\text{where}\\ \\ x_t^\\ast := x^*(u_t)$$\n     We were a little loose with the notation between the one-step within epoch and one-step across epoch results, and will update the statement (Prop H.2) in the appendix to make this clear; for instance, if Definition 2.3 holds for some say $c_1$, then the above across epoch inequality holds for  any constant $c$ satisfying $c^2\\geq c_1^2/(1-\\rho^2)$ -- e.g. for stochastic gradient play $c_1^2=2\\gamma^2$ and $c^2=2c_1^2$. In particular, its just the constant $c$ that changes between the two.  Formally, nothing changes in the proposition and corollary in Section 3 as they are stated using the notation $\\lesssim$ which absorbs constant scalings; though we will adjust this to make the relationship more clear in the main body.\n\n**Re 2:** As noted above, this is just context switching: since the results in Appendix G hold independent of the decision maker's existence, we dropped the epoch notation and are only expressing things in terms of iterations. That being said, we can switch the $t$ to a $k$ to make it more clear and add a note, as well as making the other suggested changes for clarity.\n\n**Re 3**: As noted in the paper, this is an informal statement stated as such for brevity. As we state below Prop 3.3, the formal statement is given in Prop H.5 which details all the assumptions. Given the context of the subsection, the statement holds under the assumption that the agents are running a $\\rho$ contracting algorithm, and further (as detailed in Prop H.5) under assumptions on the constants of the decision-maker's algorithm. We will add clarifications to this point.\n\nHopefully this clarifies the questions on notation and assumptions. Please also see the response to Reviewer MjEv for additional discussion/clarification on technical novelties.\n\n---\n\n**Methods And Evaluation Criteria & Experimental Designs Or Analyses:**\n\n**Response:**\n\n- We will use the extra page in the final version to incorporate a subset of the numerics in the main body that explore the main theoretical results and their assumptions. \n- All the examples of monotone games (Kelly Auctions, quadratic games, and ride-sharing) used in experiments have appeared before in the prior literature, which we cite, just in different experiments. The nonlinear examples are intended to explore the boundaries of the theoretical results. That being said, we still utilize the Kelly Auction for the agent game, but incorporate non-convex social costs which are common in the literature (including social welfare and revenue maximization).", "claims_and_evidence": "The claims are generally supported by mathematical proofs.", "methods_and_evaluation_criteria": "The learning algorithm discussed in Corollary 4.5 and Proposition 4.6 involves three nested loops: super-epoch, epoch, and iteration for the agents. This triple-loop structure could potentially lead to slow convergence in practical applications. It would be beneficial to include experimental results in the main body of the paper to demonstrate the practical convergence rate and effectiveness of the proposed algorithm.", "theoretical_claims": "The paper utilizes techniques from variational inequalities and stochastic approximation to establish the theoretical results.  However, some aspects of the theoretical analysis are unclear:\n\n- In Section 2.2, the agents are assumed to update their actions for $\\tau$ iterations. However, Propositions 3.1 and 3.2 seem independent of $\\tau$, and the proof of Proposition H.2 utilizes an inequality that differs slightly from Definition 2.3, $\\mathbb{E}\\_t\\\\|x_{t+1} - x_t^{\\ast}\\\\|^2 \\leq \\rho^2 \\\\|x_t - x_t^{\\ast}\\\\| + \\rho^2 (c\\sigma_a)^2.$ Did the author assume $\\tau=1$ in Proposition 3.1?\n- Similarly, the (SPG) algorithm appears to update $x_t$ over $t$ rather than $k$. Clarification on the update rules and how they align with the theoretical results would strengthen the paper.\n- Regarding Proposition 3.3, it is unclear whether it holds for any $\\varepsilon$ or under specific conditions. Providing more details on this point would enhance the clarity of the theoretical contributions.", "experimental_designs_or_analyses": "The experimental results are presented only in the supplementary material. While these results showcase the empirical performance of the proposed method, it is not clear if the selected benchmark problems are standard within the Stackelberg game community.", "relation_to_broader_scientific_literature": "The setting where the agents might learn and thus the objective function of the decision-maker can be time-varying seems novel.", "essential_references_not_discussed": "The paper appropriately cites relevant prior works on learning in Stackelberg games.", "other_strengths_and_weaknesses": "My main concerns and questions are outlined in “Theoretical Claims”.", "other_comments_or_suggestions": "Please see “Theoretical Claims”.", "questions_for_authors": "Please see “Theoretical Claims”.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IYV8TglOnb", "reviewer": "Reviewer_MjEv", "summary": "The paper studies the stochastic Stackelberg game and characterize the complex dynamics between the decision maker and learning agents. The drift, noise and optimization errors of the learning agents are decoupled and algorithms are proposed to control each components.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the review. Given space constraints, we focus on related literature and technical novelties. \n\n**Referenced work**:\nThe results don't exist in prior works, nor do they easily extend from analysis in referenced papers. \n- ZhaoEtAl2023, YuChen2024, different in game structure and theoretical approach, study **stationary** Stackelberg games with **side information** (i.e., omniscient follower) and are interested in manipulation strategies.  Additionally, YuChen2024 studies 2-player finite action games with bounded noisy rewards (i.e, $r_t\\in[0,1]$).  Both study regret analysis for UCB style algorithms, i.e., very different than our setup where we study time-varying stochastic continuous action games with no side information. Yet, we will add these to related work. \n- [LinEtAl21], [DuvoEtAl23] study strongly monotone simultaneous play games and have no \"leader\" and thus a different eq concept; our Stackelberg game is not assumed to be strongly monotone (only the induced agent games $\\mathcal{G}_u$ are):\n    -  [LinEtAl21] studies stationary games and employs self-concordant barrier function algorithm. We use a smoothed single point zeroth-order estimator for the DM. Hence the analysis doesn't apply to our algorithms.\n    - [DuvoEtAl23] employs an **asymptotic** analysis. We have a decision-maker **(DM)** which controls the sequence of games $\\mathcal{G}_{u_t}$; they assume $\\mathcal{G}\\_t \\to \\mathcal{G}\\_*$ or obtain asymptotic tracking results for Nash (!=Stack). \n\n**Specific Results**\n- **Prop 3.1, 3.3** don't follow from  the **asymptotic** analysis in [DuvoEtAl23], which doesn't imply a drift-to-noise decomposition (which is essential for our setting).  e.g., S1-S3 are asymptotic assumptions on stepsizes, gradient deviations (i.e. $R_{i,t}$), and bias and variance.  We provide a non-asymptotic analysis that determines the optimal error as a function of the drift-to-noise ratio (fundamentally different from [DuvoEtAl23]). This exposes how the DM can control the agents' dynamics via **choosing** $\\tau$ and $\\eta$.\n\n- **It is not possible for Thm 4.9 to result from analysis in [LinEtAl21], [DuvoEtAl23]**. We already noted differences to [LinEtAl21]. [DuvoEtAl23] have a similar zeroth-order alg (with the exception of a pivot point), yet, as noted they **rely on asymptotic assumptions**. These assumptions are not well-suited to our objective wherein one player aims to control the learning behavior of others in *finite time* and still converge to a Stack eq. (!=Nash). Their asymptotic convergence to Nash *assumes* $\\mathcal{G}\\_t\\to\\mathcal{G}\\_{*}$ whereas for us the DM **controls** $\\mathcal{G}\\_t$ in finite time.\n\n**Technical Novelties**: \n- We study stochastic Stackelberg games s.t. the leader's problem is time-varying from follower agents' learning:  the agent eq $x_t^\\star=x^\\ast(u_t)$ are **induced by** DM actions (vs a random stablizing seq. as in [DuvoEtAl]).  Each induced $\\mathcal{G}_u$ is strongly monotone but not necessarily the Stack game itself.\n- **Aim**: design an alg to control the drift-to-noise ratio to ensure finite time stabilization of agent behavior while converging to a static Stack eq (or PSE).: i.e., DM  chooses $\\tau$ and $\\eta$ to ensure finite time within epoch error $\\epsilon_\\tau \\propto (\\eta\\sigma)^2$ and then control the noise. The epoch length (a DM design feature) **alleviates drift**;  while $\\tau$ depends on agent regularity params, it can be estimated via adaptive algs as suggested in future work.\n-  To this end, we analyze $\\Vert u_t-u^\\star\\Vert^2$ by decomposing  $\\Vert x_{t}^\\tau-x^\\ast(u_t)\\Vert^2$ into a stochastic optimization and a drift error.   The within epoch contraction gives\n$\\mathbb{E}\\Vert x_{t}^\\tau-x^\\ast(u_t)\\Vert^2\\lesssim \\rho^{\\tau}\\mathbb{E}[\\Vert x_{t}^0-x^\\ast(u_t)\\Vert^2]+\\rho^2\\sigma_a^2$. \nFor the DM to set $\\tau$ s.t. RHS$\\lesssim \\epsilon_\\tau \\propto \\eta^2\\sigma^2$, we bound the sequence of *epoch initial conditions* $\\mathbb{E}[\\Vert x_{t}^0-x^\\ast(u_t)\\Vert^2]$. The \"trick\" is to exploit the across epoch results (Sec 3) to bound \n$$\\mathbb{E}\\Vert x_{t}-x^\\ast(u_t)\\Vert^2\\lesssim \\left(1-\\frac{1-\\rho^2}{2}\\right)^t\\Vert x_{0}-x^\\ast(u_0)\\Vert^2+\\frac{\\sigma_a^2}{1-\\rho^2}+\\left(\\frac{L_{eq}\\Delta_u}{1-\\rho^2}\\right)^2, \\text{where} \\ \\Delta_u:=\\max_{s\\leq t}\\Vert u_{s}-u_{s-1}\\Vert;$$  $\\Delta_u$ is controlled by $\\eta$. \n- Allowing for epoch-based algorithms doesn't make it easier: we conjecture it is necessary. To illustrate this point, see Rev GNfd on lower bounds and ref [1] therein.\n\nOverall, the approach is novel, not appearing in or simply derived from prior work, especially in Stackelberg games, to our knowledge. \nWe exploit a drift-to-noise decomp (e.g., a need the [DuvoEtAl23] doesn't have as there is no leader) to design novel algs and prove convergence of $(u_t,x_t)$ to Stack eq.  **We will utilize the extra page to incorporate these comparisons and clarify technical novelties.**\n\nHappy to discuss further.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "No. But they seems to be valid to me.", "experimental_designs_or_analyses": "Yes, I checked appendix D.", "relation_to_broader_scientific_literature": "The paper studies the Stackelberg game and learning agents. The results helps advance the understanding of leader-follower dynamics in Stackelberg and and could have broader impacts on general machine learning algorithms that can be modeled with Stackelberg game dynamics.", "essential_references_not_discussed": "The paper should discuss existing works on online learning in Stackelberg games, e.g. Zhao et al 2023, Yu and Chen 2024 and their followup works. \n\nZhao, G., Zhu, B., Jiao, J., & Jordan, M. (2023, July). Online learning in stackelberg games with an omniscient follower. In International Conference on Machine Learning (pp. 42304-42316). PMLR.\n\nYu, Y., & Chen, H. (2024, July). Decentralized online learning in general-sum stackelberg games. In Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence (pp. 4056-4077).", "other_strengths_and_weaknesses": "One strength is that the paper provides a general receipt for analyzing Stackelberg games. Different algorithmic approaches (naive decision maker and strategic decision maker) are provided. The assumptions (e.g. Definition 2.3) are also mild so that a large class of algorithms are included.\n\nWhile the general framework provided by the paper is useful, it is not clear to me what are the technical contributions. For example, it is not clear whether Proposition 3.1 and Proposition 3.3 can be non-trivially extended from the analysis of Theorem 2 Duvocelle et al 2023. Or whether Theorem 4.9 is a mere combination of the analysis used in Lin et al. 2021 and Duvocelle et al 2023.", "other_comments_or_suggestions": "While I appreciate the fact that the paper is very self-contained, I am not sure if the length of the paper will hinder the readability for ICML readers. It is hard to see such length is necessary for this work and the length of the paper  makes it hard for the reader to identify the technical contributions/ make followup contributions. I suggest to assume some appropriate prior knowledge of the readers and cite previous papers for relevant background (instead of restating them), e.g.  cite previous work that introduce examples of strongly monotone games, cite previous works for gradient estimators for bandit feedback.", "questions_for_authors": "1. Could you elaborate the technical contributions of this paper? Can we obtain the drift, noise and optimization error decomposition from existing works? \n2. One significant difference between the Stackelberg game considered by this work and that considered by previous works (e.g. Zhao et al 2023, Yu and Chen 2024) is the introduction of the epoch length. While it seems reasonable (and realistic) to me introduce the epoch length, I am not sure whether the epoch length makes the problem much easier. As the epoch length is not controlled by the leader's algorithm, but rather a parameter for a centralized planner to choose, it seems that the epoch length would make the problem significantly easier. Due to this, I am also not sure if previous works did not choose to decompose the drift and noise because of this setting difference. Could you elaborate on the difference between the two settings?\n\nI would be happy to raise my score if more discussion with existing papers on learning in Stackelberg games.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "guV6MRP9fh", "reviewer": "Reviewer_dNEQ", "summary": "This paper studies the convergence problem of the stochastic Stackelberg games. Specifically, this paper makes the following contributions. It analyzes different scenarios that reflect the decision-maker's ability to reason about the agents' behavior via different estimates of how it could impact the gradient. The paper also conducts a thorough analysis of different drift-to-noise ratios in the game. Last but not least, it also analyzes the effect of induced drift.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper. Below we respond to the topics you brought up in sections of the review. \n\n**Other Strengths And Weaknesses:**\n*Strength. The theoretical analysis is thorough and solid. For example, in section 4, the paper conducts a theoretical analysis for the naive and strategic decision-makers.\nLimitation. Empirical experiments would significantly strengthen the paper.*\n\n**Response**: Thank you for the acknowledgment of the theoretical strengths of the results. Regarding numerical experiments, we have included fairly extensive numerical experiments in the supplement. Due to page limitations and the theoretical nature of the paper, we ultimately decided to leave them to the supplement, however, given the additional page afforded by the final paper submission process, we would include some portion of the numerics in the main body.\n\n---\n\n**Questions For Authors**:\n*Have you tried to extend the proposed estimation to scenarios when the decision-maker could assume that the agent will also be strategic to the reverse direction of the decision-maker following certain constraints?*\n\n**Response**: This is a very interesting question. We have not considered agents who are strategically adversarial against the decision-maker. This would go beyond the model and corresponding results we have in the paper. This is definitely challenging since one would want to know the unintended consequences (e.g., to which equilibrium do the agents and decision-maker converge if at all) and then design mitigation strategies on the part of the decision-maker. Also one would want to know what kinds of manipulation strategies are possible. This is an interesting future direction.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes. I only checked the theoretical claims in the main paper, and they seem to be sound.", "experimental_designs_or_analyses": "No empirical experiments.", "relation_to_broader_scientific_literature": "Yes, the problem abstraction (Stackelberg game) is deeply connected with the previous work.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strength.\nThe theoretical analysis is thorough and solid. For example, in section 4, the paper conducts a theoretical analysis for the naive and strategic decision-makers.\n\nLimitation.\nEmpirical experiments would significantly strengthen the paper.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Have you tried to extend the proposed estimation to scenarios when the decision-maker could assume that the agent will also be strategic to the reverse direction of the decision-maker following certain constraints?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper explores a learning problem in the context of Stackelberg games with single leader (decision-maker) and multiple followers (agents). The authors consider a setting where both the agents and the decision-maker are learning. The authors characterize the equilibrium tracking error of the agents, highlighting the contribution of the noise and the "drift" induced by the sequence of leader's actions. Then, they analyze the convergence rate of a simple decision-maker that ignores the fact that the agents are responding to it. Finally, they devise a more powerful decision-maker which adopts a derivative-free method.

The paper analyzes a novel setting and provides an in-depth analysis of the proposed algorithms. The main idea is clear. Anyway, the exposition is sometimes confusing and can be improved so that the readers can get the main message and understand the technical merits from the main pages, leading to a not full support for acceptance. Still, I also dive in the details of the paper, and in my opinion the merits of the paper overcome its drawbacks, and for this reason I feel myself confident in suggesting acceptance.
Decision: Accept (poster)