Finite-Time Convergence Rates in Stochastic Stackelberg Games with Smooth Algorithmic Agents

Thank you for taking the time to review our paper. Below we respond to the topics you brought up in sections of the review.

Other Strengths And Weaknesses: 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. Limitation. Empirical experiments would significantly strengthen the paper.

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.

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?

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.

Thanks for the review. Given space constraints, we focus on related literature and technical novelties.

Referenced work: The results don't exist in prior works, nor do they easily extend from analysis in referenced papers.

• 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.
• [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):
  • [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.
  • [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).

Specific Results

• 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$.

• 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.

Technical Novelties:

• 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.
• 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.
• 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 $\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$. For 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 $\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$.
• 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.

Overall, the approach is novel, not appearing in or simply derived from prior work, especially in Stackelberg games, to our knowledge. We 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.

Happy to discuss further.

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.

Theoretical Claims: We label each of these points 1,2,3.

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.

Now, 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.

In 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 $\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}$ 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)$ 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.

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.

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.

Hopefully this clarifies the questions on notation and assumptions. Please also see the response to Reviewer MjEv for additional discussion/clarification on technical novelties.

Methods And Evaluation Criteria & Experimental Designs Or Analyses:

Response:

• 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.
• 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).

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.

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?

   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.

2. Can you please provide sufficient conditions to guarantee that Assumption 4.3 holds?

   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 $\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$.
   As is standard the size of the variance can be controlled via stepsize choices, batching amongst other techniques.

[1] Cutler et al "Stochastic Optimization under Distributional Drift" JMLR 2023 [2] Narang et al "Multiplayer Performative Prediction: Learning in Decision-Dependent Games" JMLR 2023 [3] Besbes et al "Non-stationary Stochastic Optimization", 2014

Thanks for reviewing our paper, and acknowledging some of the strengths of the paper.

Qs for Authors:

Re1.: No, the decision-maker (DM) doesn't know the algorithm or $\mathcal{D}\_e$ a priori.

• 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.
• Environment: Analogous to the above point, the decision-maker doesn't know $\mathcal{D}\_e$. We assume that they can stochastically query it. We will add further discussion to clarify.

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).

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.

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.

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.

Re: "Other... Weaknesses":

• Lower Bounds are open and interesting, but beyond the scope. We comment on a special sub-case:
  • 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.

Thanks for the suggestions; we will incorporate them.

• [1] Fiez & Ratliff. "Local Convergence Analysis of Gradient Descent Ascent with Finite Timescale Separation", ICLR 2021