Online Performative Gradient Descent for Learning Nash Equilibria in Decision-Dependent Games
Authors: Zihan Zhu
Ethan X Fang
Zhuoran Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: Performative Prediction
Nash Equilibrium
Reproducing Kernel Hilbert Space
Online Learning
Stochastic Gradient Methods

Abstract: We study the multi-agent game within the innovative framework of decision-dependent games, which establishes a feedback mechanism that population data reacts to agents’ actions and further characterizes the strategic interactions between agents. We focus on finding the Nash equilibrium of decision-dependent games in the bandit feedback setting. However, since agents are strategically coupled, traditional gradient-based methods are infeasible without the gradient oracle. To overcome this challenge, we model the strategic interactions by a general parametric model and propose a novel online algorithm, Online Performative Gradient Descent (OPGD), which leverages the ideas of online stochastic approximation and projected gradient descent to learn the Nash equilibrium in the context of function approximation for the unknown gradient. In particular, under mild assumptions on the function classes defined in the parametric model, we prove that OPGD can find the Nash equilibrium efficiently for strongly monotone decision-dependent games. Synthetic numerical experiments validate our theory.

Online Performative Gradient Descent for Learning Nash Equilibria in Decision-Dependent Games
Zihan Zhu Duke University
Ethan X. Fang
Zhuoran Yang Yale University
Duke University
Abstract
We study multi-agent games within the innovative framework of decision- dependent games, which establishes a feedback mechanism that population data reacts agents' actions and further characterizes the strategic interactions among agents. We focus on finding the Nash equilibrium of decision-deependen games in the bandit feedback setting. However, since agents strategically coupled, classical gradient- based methods are infeasible without the gradient oracle. To over- model the strategic interactions by general parametric
come this challenge, model and propose a novel online algorithm, Online Performative Gradient Descent (OPGD), which leverages the ideas of online stochastic approximation and projected gradient descent learn the Nash equilibrium the context of function approx- imation for the unknown gradient. In particular, under mild assumptions on the function classes defined in the parametric model, we prove that the OPGD algorithm finds the Nash equilibrium efficiently for strongly monotone decision-dependen games. Synthetic numerical experiments validate our theory.
Introduction
The classical theory of learning and prediction fundamentally relies the assumption that data follows a static distribution. This assumption, however, does not account for many dynamic real- world scenarios where decisions classification (Hardt et al., 2016; Dong et al., 2018; Miller et al., 2020) and performative prediction (Perdomo et al., 2020) offers variety of examples where agents are strategic, and data is performative. For instance, in the ride-sharing market, both passengers and drivers engage with multiple platforms using various strategies such as "price shopping". Consequently, these platforms observe performative demands, and the pricing policy becomes strategically coupled.
influence the data involved. Recent literature performative
In this paper, we explore the multi-agent performative prediction problem, specifically, the multi- agent deeenden-dependent games, proposed by Narang et al. (2022). We aim to develop algorithms to find Nash equilibria with the first-order oracle. In this scenario, agents can only access their utility functions instead of gradients through the oracle. Finding Nash equilibria in decision-dependen games is challenging task. Most existing works primarily focus on finding performative stable equilibria within the single-agent setting, an approach that approximates the Nash equilibrium and is relatively straightforward compute Mendler-Dünne et al., 2020; Wood et al., 2021; Drusvyatskiy and Xiao, 2022; Brown et al., 2022; Li and Wai, 2022).
There are two major challenges associated with this problem: (i) the distribution shift induced by performative data, and (ii) the lack of first-order information for the performative gradient. To address these two challenges, we propose a novel online gradient-based algorithm, Online Performative Gradient Descent (OPGD). In particular, our algorithm employs general parametric framework to
Depaatment of Statistical Science, Duke University. zihan zhu@duke. edu I Depaatmeen of Biostatistics and Bioinformatics, Duke University. xingyuan fangoduke. edu DDpartment of Statisties and Data Science, Yale University, zhuoran yangdyale... edu
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

model the decision-depender distribution, which provides an unbiased estimator for the unknown gradient, and leverages online stochastic approximation methods to estimate the parametric functions.
1.1 Major Contributions
Our work provides new fundamental understandings of decision-dependeen games. Expanding upon the linear parametric assumption in Narang et al. (2022), we propose a more comprehensive parametric framework that models decision-dependent distributions of the observed data. We also derive sufficient conditions under this parametric framework that guarantee a strongly monotone decision-dependent game, thereby ensuring a unique Nash equilibrium.
From the algorithmic perspective, we propose OPGD, the first online algorithm to find the Nash equilibrium under linear and kernel parametric models. The core problem in decision-dependenn games is estimating the performative gradient. We remark that the existing algorithm only handles the linear case and cannot be extended to the non-linear parametric model (Section 3), and OPCD uses an essentially different method to learn the strategic interaction. To elaborate, under the proposed parametric framework, learning the Nash equilibrium decision-deppnndett games can be formulated as a bilevel problem, where the lower level is learning the strategic model and the upper level is finding equilibriums. The OPGD algorithm leverages the ideas of online stochastic approximation for the lower problem and projected gradient descent to learn the Nash equilibrium. Moreover, we acknowledge this learning framework bridges online optimization and statistical learning with time-varying models.
We further prove that under mild assumptions, OPGD converges to the Nash equilibrium. For the linear function class, OPGD achieves convergence rate O(1-)), matching the optimal rate of SGD in the strongly-convex setting, where / represents the number of iterations. For the kernel function class H. associated with a bounded kernel K. we posit that the parametric functions reside within the power space H. and evaluate the approximation error of OPGD under the a-power norm, where represents the minimal value that ensures the power space Hd possesses a bounded kernel. We present the first analysis for online stochastic approximation under the power norm (Lemma 4), in contrast to the classical RKHS norm (Tarres and Yao, 2014; Pillaud- Pilaud-Vivien et al., 2018; Lei et al., 2021). The difference between the RKHS H and the power space 7t makes the standard techniques fail under the power norm, and we novel proof steps to obtain the estimation error bound. We demonstrate that OPGD leverages the embedding property of the kernel K to accelerate convergence
and achieves the rate of Ot (-++)) ). Moreover, OPGD can handle the challenging scenario, where parametric functions are outside the RKHS. See Section 4.2 for more details.
1.2 Related Work
Performative prediction. The multi-agent decision-dependent game in this paper is inspired by the performative prediction framework (Perdomo et al., 2020). This framework builds upon the pioneering works of strategic classification (Hardt et al., 2016; Dong al., 2018; Miller et al., 2020), and extends the classical statistical theory of risk minimization to incorporate the performativity of data. Perdomo et al. (2020); Mendler-Diinner al. (2020); Miller et al. (2021) introduce the concepts of performative optimality and stability, demonstrating that repeated retraining and stochastic gradient methods converge the performatively stable point. Miller et al. (2021), in pursuit of the performatively optimal point, model the decision-dependens distribution using location families and propose two-stage algorithm. Similarly, Izzo et al. (2021) develop algorithms to estimate the unknown gradient using finite difference methods. More recently, Narang et al. (2022); Piliouras and Yu (2022) expand the performative prediction to the multi-agent setting, deriving algorithms to find the performatively optimal point.
Learning in continuous games. Our work aligns closely with optimization in continuous games. Rosen (1965) lays the groundwork, deriving sufficient conditions for a unique Nash equilibrium in convex games. For strongly monotone games, Bravo et al. (2018); Mertikopoulos and Zhou (2019); Lin et al. (2021) achieve the convergence rate and iteration complexity of stochastic and derivative- free gradient methods. For monotone games, the convergence of such methods is established by Tatarenko and Kamgarpour (2019, 2020). Additional with bandit feedback settings, zeroth-order methods (or derivative-free methods) achieve convergence (Bravo et al., 2018; Lin et al., 2021; Drusvyatskiy et al., 2022: Narang et al., 2022), albeit with slow convergence rates (Shamir, 2013; Lin et al.. 2021; Narang et al., 2022). Relaxing the convex assumption, Ratiff et al. (2016); Agarwal et al. (2019); Cotter et al. (2019) study non-convex continuous games in various settings.

---

Learning with kernels. Our proposed algorithm closely relies on stochastic approximation, utiliz- ing online kernel regression for the RKHS function class. Prior research investigates the generalization capability of least squares and ridge regression in RKHS De Vito et al. (2005); Caponnetto and De Vito (2007); Smale and Zhou (2007); Rosasco et al. (2010); Mendelson and Neeman (2010).
Meanwhile, extensive works study algorithms for kernel regression. For instance, Yao et al. (2007);
Dieuleveut and Bach (2016); Pillaud- Vivien et al. 2); Lin and Rosasco (201 7); Lei et al. (2021)
propose offline algorithms with optimal convergence rates under the RKHS norm and L2 norm using early stopping and stochastic gradient descent methods, while Ying and Pontil (2008); Tarres and Yao (2014); Diculeveut and Bach (2016) design online algorithms with optimal convergence rates, The convergence of kernel regression in power norm (or Sobolev norm) is studied in Steinwart et al. (2009); Fischer and Steinwart (2020); Liu and Li (2020); Lu et al. (2022), with offline spectral filter algorithms achieving the statistical optimal rate under the power norm (Pillaud- Vivien et al., 2018; Blanchard and Mücke, 2018: Lin and Cevher, 2020; Lu et al., 2022).
Notation. We introduce some useful notation before proceeding. Throughout this paper, we denote the set 1, ... n by [nx] for any positive integer For two positive sequences {un JneN and {bn) weNN, we write a, (bn,) or an S bn if there exists a positive constant C' such that a, S C by- For any integer d, we denote the d-dimensional Euclidean space by R with inner produce (, and the induced norm ||-|| -V:---( For Hilbert space H. let || be the associated Hilbert norm. For a set X' and probability measure px on N, let C22 be the L space on X' induced by the measure px. equipped with inner product (x) and L norm || Ilpx = v(., ()xx For any matrix A = (ar)), the Frobenius norm and the operator norm (or spectral norm) of A are ||Al|r (Ei, o22)² and ||Aollop = 0 (A), where a (A) stands for the largest singular value of A. For any square matrix A = (ay)), denote its trace by tr([A) = Σ; ag. For any y E Rd. we denote its projection onto a set X IR by (v) = arg min || y|l. The set denoted by Nx(x)) represents the normal cone to convex set X at xr X. namely, Nx (2) = (u Rd (v. y z) S 0, Vy X}. For any metric space Z with metric d(.,,), )), the symbol TP( () will denote the set of Radon probability measures on
V...)).
2 with finite first moment Ez~p [d(2, zo)] oo for some 2g E Z.
2 Problem Formulation and Preliminaries
We briefly introduce the formulation of n-agent decision-dependent games based on Narang et al. (2022). In this setting, each agent i E [r]] takes the action xi E X; from an action set X, C Rd. Define the joint action x == (I1, -2,... ... , .nn) ). E X' and the joint action set X = Xi X... Xr C Rd where d Ei= dj. For all E [n]. we write x (=), where x denotes the vector of all coordinates except v,. Let L, : X + R be the utility function of agent i. In the game, each agent i seeks to solve the problem
min L, where (,(x)= = E (xx E,EX,
(1)
=x),((a)
Here 2, E Z, represents the data observed by agent i, where the sample space Z, is assumed to be Z, = R' with p E N throughout this paper. Moreover, D, : X + P(Z,) is the distribution map, and 6, Rd Z, - R denotes the loss function. During play, each agent performs an action a; and observes performative data ~ (x))), where the performativity is modeled by the decision- dependent distribution (z). In the round t, the agent only has access to 2/- ..... 22 t-1 as well as x²_ _'1 and seeks to solve the ERM version of (1). We assume the access to the first-order oracle, namely, loss functions l; are known to agents but distribution maps Dj are unknown.
Definition 1. (Nash equilibrium). In the game (I), a joint action x² = =xr,, x.. .z.... ,x",), is a Nash equilibrium (Nash Jr, 1996) all agents play the best response against other agents, namely,
arg min (, = arg min ExEX:
f((x,, xz,,,,",,))))))
Vi E [n].
(2)
2,EX; =,
In general continuous games, Nash equilibria may not exist or there might be multiple Nash equilibria (Fudenberg and Tirole, 1991). The existence and uniqueness of Nash equilibrium in continuous game depend on the game's structure and property. In general, finding the unique Nash equilibrium is only possible for convex and strongly monotone games (Debreu, 1952).
Definition 2. (Convex game). Game (1) is a convex game if sets X, are non-empty, compact, convex and utility functions Li(x,, =i) are convex in I; when x= are fixed.
3

---

Suppose that utility functions L; are differentiable, we use (z(((z) to denote the gradient of L (x) with respect z; (the i-th individual gradient). We say the game (1) C' -mooth if the gradient (xC((r) exists and is continuous for all i E [n]. Using this notation, we define the gradient H (x) comprised of individual gradients
H(x) = (VILi(t), (n)n(x))-
Definition 3. (Strongly monotone game). For constant T 2 C' -smooth convex game (1) is called r-strongly monotone if it satisfies
(H(x) - Hx'),,)) x') 2 1||x - x'11; for all x, x. E Ex
Note that r-strongly monotone game (T 0) over compact and convex action set X' admits unique Nash equilibrium (Rosen, 1965). According to the optimal conditions in convex optimization (Boyd et al., 2004), this Nash equilibrium x² is characterized by the variational inequality
0 (x=)) + (x
(3)
We briefly talk about the challenges and our idea of designing the algorithm. In decision-dependent games, the classical theory of risk minimization does not work. The primary obstacles to finding the Nash equilibrium in the game (1) include: (i) the distribution shift induced by performative data, and (ii) the lack of first-order information (gradient). To make clear, standard methods, such as gradient-based algorithms, necessitate the gradient (x). However, (x) is unknown since distributions D, unknown, and estimating H(x) is complex due to the dependency between Di(r) and æ. Mathematically, assuming C -smoootthssss, the chain rule directly yields the following expression for the gradient
V(((E11-22) d du, (..,2
v,L((x)
E (xr
E
Lx ((I,;
(4)
0,=2,
where (zl, z.) denotes the gradient of (1 z;) with respect to I., The main difficulty is estimating the second term in (4) due to the absence of closed-form expressions.
To estimate the unknown gradient (xx, we impose a parametric assumption on the observed data 2 and model the distribution maps D; using parametric functions. Note that the linear parametric assumption was first proposed in Narang et al. (2022). In this paper, we extend this assumption to a general framework and show that under the parametric assumption, the gradient H H()) has a closed-form expression, which yields an unbiased estimator for (xx).
Assumption 1. (Parametric assumption). Suppose there exists a function class I and p-dimensional functions fa X ++R Rd over the joint action set X such that fü FP and
D.(x) + 24 f((x) + Ei. Vi E [m].
where G E RD are zero-mean noise terms with finite variance o², namely, Ec; = 0 and B||G|| < 0².
Under Assumption 1, assuming that fi are differentiable and letting P, be the distribution of the noise term es, we derive the following expression for the utility functions (x) = (x) = Bawp, (z, fxx + eq). Then the individual gradient would be v,C,(z) = V
[. (EEND, (xx fx( + c.). Consequently, the chain rule directly implies the following expression
(Ofilm)
v,C,(x)= E 2xl(I, =T-DD((1)
E Der-Da
(24(2,2),
(5)
where Va, Lx, z)) denotes the gradient of lz(2, zi) with respect to z;. Given a joint action æ, each agent i observes data 2; ~ Dz( Equation (5) suggests the following unbiased estimator for H (z):
Axx = (v.c()))))))) tE(n] (viel(o..))
(of((e)) dr,
(6)
iE[n]
However, direct computation of (z) is infeasible because f. are unknown. To overcome this challenge, we approximate the unknown functions fi with the function class PP. In fact, the estimation of fi can be formed as a non-parametrie regression problem, namely,
arg min
JELP xx2 -|2:- f(: Vi E [m],
where Ps is the joint distribution of (z, 2)) induced by x ~ px and z ~ D.(x). Here px is a user-specified sampling distribution on X.

---

3 The OPGD Algorithm
In this section, we consider # to be the linear and kernel function classes and derive gradient-based online algorithms to find the Nash equilibrium in the game (1), namely, the Online Performative Gradient Descent (OPGD). In each iteration t, assuming that z' == (z1 x²t1 is the output of the previous iteration, OPGD performs the following update for all E [n]]
(i) (Estimation update). Update the estimation of Sa by online stochastic approximation for (7).
(Individual gradient update). Compute the estimator (6) and perform projected gradient steps
++1 projxx (a) 1/t (.))()))), Vi E [n].
Linear Function Class. Let & be the linear function class, namely, f((x) = A₂æ for i E [m]. where A; E IRpxd are unknown matrices. Then (7) becomes the least square problem A; = arg min ACRoxa B(u,. lly - Aru,l with random variables u, ~ Px.Mi D(u)). We use the gradient of the least square objective IR A, A,u;ll derive the online least square update: Anew A-A - v(Au, y) (Dieuleveut al., 2017; Narang et al., 2022). In each iteration t, suppose that A! is the estimation of A; from the previous iteration, OPGD samples ut px and v (uf) and performs the following estimation update:
1 A! D1 (A7- vt) (T))
(8)
Recalling (5), the individual gradient is V,C,(r) = BENDD, [.l, 2,) + &x, = where A 0f (z) E RRxd, denotes the submatrix of A, whose columns are indexed by the agent i. After step (i), DPGD draws sample of ~ De(x²) and compute the estimator (6) to perform the projected gradient step:
= projx, (xi - T1 (Vili(z', 2/) + (At)) T Va Val 2)))
Kernel Function Class. Now we consider & as the kernel function class, namely, we suppose fi E (H)P, where H is RKHS induced by Mercer kernel K X' x X' + R and user- specified probability measure px. By the reproducing property H. fa can be represented as f((z) (fi, Øz) R.. where 6 X + H is the feature map, i.e. 6, = K(..r) E H for any E X. Therefore, (7) becomes the kernel regression arg min E E(,,,r)=a 11y: (f. ou.) lul² space, the aforementioned regression problem
However, as H is generally an aefinite-dimensee might lead to ipo-ed solutions. Consequently, we consider the regularized kernel ridge regression arg min fe Eu )=pp: is the estimation of f. from the previous iteration, the OPGD algorithm samples of ~ pxx, v (u() and takes gradient steps on the kernel ridge objective llv| - (J. Φuy x11 the online kernel ridge update (Tarres and Yao, 2014; Diculeveut and Bach, 2016):
11y, (f, > 2 + Xell Il.. In each iteration i, we suppose that f!-1
2 /2 + >rll/'llee i.e. it takes
i 1- -t [T - vi) oug- + AxSt
[
(10)
We suppose that the kernel K is 2-differentiable, i.e., K E (X, X). Define 0.6 X H as the partial derivative of the feature map á with respect to z4. namely, 0, 0,K(x,)) (x(xx)) //0r Steinwart and Christmann (2008, Lemma 4.34) shows that 0, exists, continuous and 0,0- H. By the reproducing property 0f (z)))/Ox; = a(fi, (zfi,)z)P dz) /zz = (fi, d,0a).. the individual gradient (xC,(x has the form (zL,(z) E.,,D, [zl, 2)) + ((fr, 0())))) Ve,l(2, 21)] After step (i), OPGD draws sample 2f Dx(x*) and performs the projected gradient step:
+1 + proj (af ne (V,4(=', 24) + (1)) 0,))) T (o,,,('',
(11)
We remark that the gradient steps T),, Vs and regularization terms X should be chosen carefully to ensure convergence (see Theorem 2). Specifically, the regularization terms ) must shift 0 gradually. If X, is a constant, ff in (10) converges to the solution of a regularized kernel ridge regression, which is biased estimator of f.. Thus (11) fails to converge because the gradient estimation has constant bias. We present the pscudocode of OPGD for the linear setting as Algorithm I and for the RKHS setting as Algorithm 2 in Appendix A.
5

---

Comparison with Narang et al. (2022). We clarify the difference between OPGD and the Adaptive Gradient Method (AGM) proposed in Narang et al. (2022). To elaborate, AGM samples 2f (a(x') at current the action and let agents play again with an injected noise u² to obtain of ~ (2'x The algorithm is based on the fact that Ely - 2 Jul x²] A,u', which is not related to x². Thus, A, can be estimated by online least squares. We remark that E Eig. - 2/ x²) depends on agents' actions in the non-linear (RKHS) cases, because Elg - =2flu², x²]
(fi; O2t D2t)H- H- Thus, the change of action will bring additional error that makes the cstimation fail to converge. In contrast, DPGD lets agents play of px explore the action space and learn the strategic behavior of other agents. OPGD estimates the parametric function by solving the ERM version of (7) using online stochastic approximation (8) and (10). This learning framework can be applied to RKHS and potentially beyond that, such as overparameterized neural networks using the technique of neural tangent kernel (Allen-Zhh et al., 2019).
- f((x') +x"
Theoretical Results
We provide theoretical guarantees for OPGD in both linear and RKHS settings. We first impose some mild assumptions. Similar assumptions are adopted in Mendler-Dünner et al. (2020); Izzo et al. (2021); Narang et al. (2022); Cutler al. (2022).
Assumption 2. (T-strongly monotone). The game (1) is T-strongly monotone.
Assumption 3. (Smoothness). H (z) is L-Lisschitz continuous:
H(x1) H (x2) S =| x211. Vι 22 E X.
Assumption 4. (Lipschitz continuity in 2). Define D Dr x D2 x ..... Dr X - where Z the sample space Z = Zi x Z2 x x Zn. For all i [m]. E X, there exists a constant > 0,
N2,(I, 23 8
Assumption 5. (Finite variance). There exists a constant <> 0.
E
(i,,,(((,, 23 Vi ( X,
where V &i denotes the gradient of (1 2;) with respect to x; and
We remark that Assumption 3 is the standard smoothness assumption for the utility functions (x) (Boyd et al., 2004: Nesterov et al., 2018). Since X' is compact set within Ed Assumption holds if (x, 2;) is Lipschitz continuous in 2; and the gradient Vz,4, (ar, =:) is continuous in x, and Assumption 5 holds if (xr, z;) is Lipschitz in x and 2; (thus Vi (2, 2;) has a bounded norm). Assumption implies that the variances of (z,, z;) and V & 2:) are both bounded by <² for any X and z, Dz( We provide sufficient conditions for Assumption in Appendix B.1.
4.1 Convergence Rate in the Linear Setting
We introduce two assumptions necessary to derive thcoretical guarantees for the linear function class. Assumption 6. (Linear assumption). Suppose that the parametric assumption holds (Assumption 1) and f((r) = A₁æ for i [n], where A, Rpxd are unknown matrices.
Assumption 7. (Sufficiently isotropic). There exists constants 4,,2,, R > 0 such that
4 = Euxox uu
Eu-px 1ull < l2, Euspx [|lu[]2ux uu
= REu uu
Assumption has been studied in the literature on online least squares regression (Dieuleveut et al., 2017: Narang al., 2022). Essentially, this requires the distribution px be sufficiently isotropic and non- singular, and ensures the random variable ui ~ Px in the online estimation update step (8) can explore all the "directions" of R". A simple example that satisfies Assumption 7 is the uniform distribution px = 24[0, 1], in which case I = l2 = 1/3, R = 3/5.
The next theorem provides the convergence rate of OPGD under the lincar setting.
Theorem 1. (Convergence in the linear setting). Suppose that Assumptions 2, 3, 4, 5, 6, and 7 hold. Set = 2/(7(t + to)), Pt 2/(1(t + to)), where to is constant that satisfies to 2 21 ft. For

---

all iterations t 2 1, the x' generated by the OPCD algorithm in Section 3 for linear function class satisfies
Bl|a - x² x²112 (4D1 + 2D2 + (to + + (to + 1) + (to + 1) xz
(12)
72 + to)
(t + to)2
where Dj and D2 are constants that
D2 =2:=20 20 M : 260 T 2i-1 ||.4 1
A
8nl2o² + 2)
Dj = ( iE(m]
(oo + 1)3
Pf + 1)2
We refer the reader to Appendix C.I for complete proof. Next, we illustrate the parameters involved in Theorem 1: 7 is the strongly monotone parameter of the game (1), 11,42, I are intrinsic parameters describing the isotropy of the distribution px (Assumption 7), o² is the variance of the noise term E; defined in Assumption 1, and 5 describe the continuity of f; (Assumption 4, 5), to is sufficiently large value, AQ is the initial estimation of A, x² is the initial input. Theorem 1 is a combination of Lemma and Lemma where Lemma 2 is the statistical error of the online approximation step (8) and Lemma is the one-step optimization error of the projected gradient step (9). Theorem 1 implies the convergence rate of OPGD in the linear setting is O( which matches the optimal rate of stochastic gradient descent the strongly-convex setting.
4.2 Convergence Rate in the RKHS Setting
Suppose that K X' X R is continuous Mercer kernel, by Mercer's theorem, has the spectral representation K = D sa e; where { are eigenvalues, {ei are eigenfunctions, and
@ denotes the tensor product. Moreover, {ez ] is an orthogonal basis of L and {1r (////2 e is 2x
the orthogonal basis of H. which induces the representation H = (Eiz a:j. Definition 4. (Power space). For a constant a 2 O, the a-power space of an RKHS H. defined by
1/2 e; {a,) E)..
8
a/2e, ai4 e, {at E }
H
equipped with the a-power norm 11-11a and inner product (: where 1E 0:j0 eella = (E:1 at) and Ei a:p//2 eis Ei bil4," 0/2 ei)a = = a,b..
/
0/2
We remark that: (i) H. H. and H c HD for any 3, (ii) |1-111 = Il-Ilx and I1-1lo (iii) 7e is an RKHS on X' with kernel K = Di= e&e @ e; and measure px- We review more properties of RKHS and power spaces in Appendix Sections B.3 and B.4.
11 and
We present assumptions on the kernel function class, similar assumptions can be found in the literature on kernel regression and stochastic approximation (Caponnetto and De Vito, 2007: Steinwart et al., 2009; Dicker et al., 2017; Pillaud- et al., 2018; Fischer and Steinwart, 2020).
Assumption 8. (Source condition). Suppose Assumption I holds and there exists an RKHS, H. with bounded differentiable Mercer kernel, K, and constants B, k 0 such that supaex K(I, x) S R² and f. e (H²)² for all i [n).
Assumption 9. (Embedding property). There exist constants & E (0, 1]. A >>>> 0 such that K K = Ee e ( S A?, for all x E X.
Assumption 10. (Lipschitz kernel). Suppose Assumption 9 holds and there exists E > 0 such that |0,0% < E for any E [n] and x E X. where &5 : X - Ho is the feature map of the kernel K
Assumption 8 holds when K is bounded, differentiable, and each coordinate of parametric functions fa lies in the power space HPS When 3 < 1, Assumption 8 includes the challenging scenario, namely, la & (H)?. Assumption holds if there exists a power space 7 such that the kernel K is bounded. Thus, Assumption 9 holds with a = for any bounded kernel K. We further propose Proposition 1 as sufficient conditions for the embedding property following Mendelson and Neeman (2010). Recalling the definition of partial derivative 0, X + H. (Section 3), Assumption 10 holds 0,0,4aK" (z,x) x) = |0,00 ? < E for any X. i.c. it holds for any Lipschitz kernel K
7

---

Proposition 1. (Sufficient conditions for Assumption 9) Suppose there exist constants C, D, >>pp0 0 and q (0, 1) such that
sup
1 le:lllo SC and p4 Di EEN
where Il denotes the L norm. Then Assumption 9 holds for any 2p + 9-
Proposition 1 follows from the inequality: s (xxxxx) suPRex Ei=1 (ufe: (x)) p < Ca 2p Σi=1 (a-22)) < oo. We refer readers to Appendix B.4 for examples that satisfy these assumptions. Next, we provide the convergence of the proposed algorithm under the RKHS setting.
Theorem 2. (Convergence in the RKHS setting). Suppose that Assumptions 2, 3, 4, 5 hold, Assump- tion 8 holds for some B E (0. 2]. and Assumptions 9, 10 hold for some E (0, 1] and o < B. For all iterations
and positive constant o, define i == + lo, where to a constant that satisfies to 2 (ak² 1)?. Set the gradient steps and regularization terms as
11 = (T]) 14 = =
7-043
X = B-0+2
Ifo= < a 2)/(8
2 the x' generated by the OPGD algorithm in Section using kernel K for online estimation steps (10) and projected gradient steps (11) satisfies
2//8-a2)/(B-a(tt (to + 1)/(to + 2)x²
2A-
B| x²11 - Ot 8-0+2
E
(13)
See Appendix C.2 for complete proof. We remark that bounding the estimation error ElI - fill under the 7y-oowr norm for some y E [a, 3) and < 1 (Lemma 4) plays a key role in the proof of Theorem 2, and regard this lemma the most challenging part of our theory. Lemma 4 extends the classical theory of online stochastic approximation under the RKHS norm 11 æ into a continuous scale. For 33 > and y = 1, this rate would be ((t-00-1/(6-1) and matches the optimal rate under the RKHS norm Ying and Pontil (2008); Tarres and Yao (2014). If the embedding property (Assumption 9) holds for some
to achieve faster rate (((-(6-a))(B-e) ())++)) (which further leads to Theorem 2). To prove Lemma 4, we derive novel proof steps, where we decouple the power norm by considering semi-population iteration and recursive decomposition, we refer the reader to Appendix E. for more explanations.
1, we choose
We demonstrate the parameters involved in Theorem 2. Parameters a, 3, K, T, are intrinsic: B, n, A are determined by source condition (Assumption 8), a is determined by embedding property (As- sumption 9), and 7 is the strongly monotone parameter. Parameters a, to are user- sper-specified: to is a sufficiently large value, a is characterized by the inequality a < vB3 - a + 2)/(3 a)(lo + 1)/(1o + 2) when to determined, a smaller leads larger constant term in (13). Theorem 2 implies that OPGD leverages the embedding property (Assumption 9) to obtain better convergence rates. For any bounded kernel, Assumption holds for 1, thus Theorem guaran- tees the rate O $тे), ). Moreover, suppose that the kernel satisfies some good embedding property, that is, a < since larger
a leads to faster convergence rates. In that case, we obtain better rate O1- x-o+2) ) by setting the gradient steps and regularization terms Mt; d corresponding a, 8. Besides, OPGD can handle the challenging scenario (Ji & (H)² < 1) when the embedding property of kernel holds for < B.
5 Numerical Experiments
In this section, we conduct experiments on decision-dependent games in both the linear and the RKHS settings to verify our theory. All experiments are conducted with Python on laptop using 14 threads of a 12th Gen Intel(R) Core(TM) 17-12700H CPU.
Basic Setup. We consider two-agent decision-dependent games with 1-dimensional actions. Namely, for all i [2]. define the game
min (x),, ZEž
21) where Lx(x) = (x)
(14)
where X' [0. 1] 00, 11,
E and (1 21) is the loss function be determined. Let the distribution map be (x) ~ A (ff((z)) 0.2), where fi is the parametric function determined by the specific function class. Then the game (14) follows the parametric assumption (Assumption 1) with 2 = fi(x) + 6; where 4 ~ \/ 0.2) the independent Gaussian noise term.
8

---

Comparison of rate
Comparison of rate
Theoretical rate
Simulation rasult
Theoratical rate
Simulation resut
10-1
10-7
log
10
10
10a
10a
10
10a
10a
10
10a
log (lteration)
log (lteration)
(a)
(b)
Figure 1: (a) Linear setting: The X-axis represents the iteration from to 10, 000, while the Y-axis
represents the norm cerm-square error of x' to the Nash equilibrium x (1/2, 1), averaged over 20 random seeds. The blue solid line represents the output of OPCD and the orange dashed line represents the theoretical rate (t (b) RKHS setting: The X-axis represents the iteration from 10, 000, while the Y-axis represents the norm-squared error to the Nash equilibrium x² = 1/2, averaged over 400 random seeds. The blue solid line represents the output of OPGD and the orange dashed line represents the theoretical rate O 1/2).
Linear function class. Let the loss function be (x, 2,) = + x? and set the linear parametric function (I:
A&æ: + 6; where A1 = [1 0] and A2 = 10 2). The the game (14) has the gradient Hx)) = (2x1 1, 2x² - 2). therefore, the game (14) is convex, C'-smooth, 1-strongly monotone and the Nash equilibrium is xx (1/2, 1). We set the sampling distribution as px = ( 1] x 2[00, 1]. the initial point as x px. and the initial estimation as zero. Moreover, letting to 10, we set the gradient step sizes as 7/- = 6/(t- + to), 1 = 6/(1 + to).
and f2(2:) 2r², namely, the parametric model is
Kernel function class. Let X [0. [0, Px u100 1] U 1]. and define the kernel Q((x1,x2), (11, 92)) = K(11, y1) (x2, y2) as the product kernel of K(I, y) = 400;((x y}).
Suppose that H is the RKHS on X' induced by the kernel Q and the distribution px. Set the parametric function as the product of two 3-order Bernoulli polynomials, namely, f(x1, = Ba(x1)
B2(2z) = (x, - 3xf 2 2xx2 -32 322/2+22 22+22/22 Set (1 2,) - + cos(2 cos(2 cos(2rxz) (2Tx) cos (2Tx2) for E [2]. Then the gradient of this game is ((x) = (2x, 1, 1,2 1), thus, this game is convex. C² -smooth, 1-strongly monotone and the Nash cquilibrium is x² = (0.5, 0.5). Following Example 1, Assumption 8, 9, 10 hold for any 3 > 1 and any a > 1/4. Set tu = 10, a = 7, T = tt), 1/ = at(t+ 3/44 and X₂ = 1/(a(t+tt))/4) Following Theorem 2, the convergence rate is O(t-1/2).
H; + 2 and let f(())
cos(
Results. We perform experiments for both parametric settings to verify the convergence rates and compare the theoretical and simulated rates, as shown in Figure 1, where both X and Y axes take the log scale. Figure ((a) shows the converge rate of the linear setting within 10, 000 iterations, the simulated rate matches our prediction. i.e. it is close to O(t )). Figure 1(b) shows the convergence rate of the RKHS setting, it implies that the simulated rate is close to the theoretical rate (t-1/2) when the iteration é larger than 1, 000. These results validate Theorems and 2.
Conclusion and Discussion
In this paper, we study the problem of learning Nash equilibria in multi-agent -eeeeden games with access to the first-order oracle. We propose a parametric assumption to handle the distribution shift and develop a novel online algorithm OPGD both the linear and RKHS settings. We derive sufficient conditions to ensure the decision-dependent game is strongly monotone under the parametric assumption. We show that OPGD converges to the Nash equilibrium at a rate of O(t-l)
in the linear setting and O 3-0+z) in the RKHS setting.
A Acknow ledgement
We would like to thank the area chair, and three anonymous reviewers for their very helpful comments, which help us substantially improve our paper. E. X. Fang is partially supported by NSF DMS- 2230795 and 2230977.797.

---

References
Abramowitz, M., Stegun, I. A. and Romer, R. H. (1988). Handbook of mathematical functions with formulas, graphs, and mathematical tables.
Adams, R. A. and Fournier, J. (2003). Sobolev spaces. Elsevier.
Agarwal, N., Gonen, A. and Hazan, E. (2019). Learning in non-convex games with optimization oracle. In Conference on Learning Theory. PMLR.
Allen-Zhu, Z., Li, Y. and Liang. Y. (2019). Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32.
Blanchard, G. and Mücke, N. (2018). Optimal rates for regularization of statistical inverse learning problems. Foumdations of Computational Mathematics, 18 971-1013.
Boyd, S., Boyd, S. P. and Vandenherghe, I.. (2004). Convex optimization. Cambridge university press.
Bravo, M., Leslie, D. and Mertikopoulos, P. (2018), Bandit learning in concave n-person games. Advances in Newral Information Processing Systems, 31.
Brown, G.. Hod, S. and Kalemaj. I. (2022). Performative prediction in a stateful world. In International Conference on Artificial Intelligence and Statistics. PMLR.
Caponnetto, A. and De Vito, E. (2007). Optimal rates for the regularized least-square, algorithm. Foundations of Computational Mathematics, 7 331-36..
Cotter, A., Jiang, H. and Sridharan, K. (2019). Two-player games for efficient non-convex constrained optimiza- tion. In Algorithmiic Learning Theory. PMLR.
Cucker, F. and Smale. S. (2002). On the mathematical foundations of learning. Bulletin of the American mathematical society, 39 1-49.
Cutler, J., Díaz, M. and Drusvyatskiy. D. (2022). Stochastic approximation with decision-dependent distribu- tions: asymptotic normality and optimality. arXiv preprint arXiv:2207.04173.
De Vito, E., Rosasco, L.. Caponnetto. A., De Giovannini, U., Odone, F. and Bartlett P. (2005). Learning from examples inverse problem. Journal of Machine Learning Research, 6.
Debreu, G. (1952). A social equilibrium existence theorem. Proceedings of the National Academy of Sciences, 38 886-899
Dicker, L. H., Foster, D. P. and Hsu, D. (2017). Kernel ridge principal component regression: Minimax bounds and the gualification of regularization operators. Electronic Journal of Statistics, 11 1022 1022-1047,
Dieuleveut, A. and Bach, F. (2016). Nonparametric stochastic approximation with large step-sizes. The Annols of Statistics, 44 1363 1399.
Dieuleveut, A., Flammarion, N. and Bach, F. (2017). Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research, 18
Dong, J., Roth, A., Schutzman, Z., Waggoner, B. and Wu, S. (2018). Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference on Economics and Compulation.
Drusvyatskiy, D., Fazel, M. and Ratliff, I. J. (2022). Improved rates for derivative free gradient play in strongly monotone games. In 2022 IEEE 61st Conference Decision and Control (CDC). IEEE.
Drusvyatskiy, D. and Xiao, L. (2022). Stochastic optimization with decision-dependen distributions. Mathe- matics of Operations Research.
Fischer, S. and Steinwart, I. (2020). Sobolev norm learning rates for regularized least-squares algorithms. The Journal of Machine Learning Research. 21 8464-8501.
Fudenberg, D. and Tirole, J. (1991). Game theory. MIT press.
Hardt. M.. Megiddo, N., Papadimitriou. C. and Wootters. M. (2016). Strategic classification. In Proceedings of the 2016 ACM conference on innovations theoretical computer science.
Izzo, Z., Ying, L. and Zou, J. (2021). How to leamn when data reacts to your model: performative gradient descent. In International Conference Machine Learning. PMLR.
10

---

Lei, Y., Hu, T. and Tang, K. (2021). Generalization performance of multi-pass stochastic gradient descent with convex loss functions. The Journal of Mackine Learning Research, 22 1 145-1185.
Li, Q. and Wai, H.-T. (2022). State dependent performative prediction with stochastic approximation. In International Conference on Artificial Intelligence and Statistics. PMLR.
Lin, J. and Cevher, V. (2020). Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms. The Journal of Machine Learning Research, 21 5852 5914.
Lin, J. and Rosasco, L. (2017). Optimal rates for multi-pass stochastic gradient methods. The Journal of Machine Learning Research, 18 3375-3421.
Lin, T., Zhou, Z., Ba, W. and Zhang, J. (2021). Optimal no-regret learning in strongly monotone games with bandit feedback. arXiv preprint arXiv:21
Liu, Z. and Li, M. (2020). On the estimation of derivatives using plug-in krr estimators. arXiv preprint arXiv:2006.011 01350.
Lu, Y.. Blanchet. J. and Ying. L. (2022). Sobolev acceleration and statistical optimality for learning elliptic equations via gradient descent. arXiv preprint arXiv:2205.07331.
Mendelson, S. and Neeman, J. (2010). Regularization in kernel leamning. Annals of statistics, 38 326-565.
Mendler-Dünnen C., Perdomo, J., Zraic, T. and Hardt, M. (2020). Stochastic optimization for performative prediction. Advances in Neural Informaioon Processing Systems, 33 4929-4939.
Mertikopoulos, P. and Zhou, Z. (2019). Learning in games with continuous action sets and unknown payoff' functions. Mathematical Progronuming, 173 465-507.
Miller, J., Milli, and Hardt, M. (2020). Strategic classification is causal modeling disguise. International Conference on Machine Learning. PMLR.
Miller, J. P., Perdomo, J. C. and Zmic, T. (2021). Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning. PMLR.
Narang, A., Faulkner, E., Drusvyatskiy, D., Fazel, M. and Ratliff, L. (2022). Multiplayer performative predic- tion: Learning in decision-dependent games. arXiv preprint arXiv:2201 03398..
Nash Jr, J. (1996). Non-cooperative games. In Essays on Game Theory, Edward Elgar Publishing, 22-33.
Nesterov, (2018). Lectures on convex optimization, vol. 137. Springer.
Perdomo, J., Zmic, T., Mendler-Dünner, C. and Hardt, M. (2020). Performative prediction. In International Conference on Machine Learning. PMLR.
Piliouras, G. and Yu, F--Y. (2022). Multi-agent performative prediction: From glohal stability and optimality chaos. arXiv preprint arXiv:2201.1443:
Pillaud-Vivien, L., Rudi, A. and Bach, F. (2018). Statistical optimality of stochastic gradient descent hard learning problems through multiple passes. Advances Neural Information Processing Systems, 31.
Ratliff, L. J., Burden, S. A. and Sastry, S. (2016). On the characterization local nash equilibria in continuous games. JEEE transactions on automatic control, 61 2301-2307.
Rosasco, L., Belkin, M. and De Vito, E. (2010). On learning with integral operators. Journal of Machine Learning Research, 11.
Rosen, J. B. (1965). Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society 220-534,
Shamir, O. (2013). On the complexity of bandit and derivative-free stochastic convex optimization. In Conference on Learning Theory. PMLR.
Smale, S. and Zhou, D.-X. (2007). Learning theory estimates via integral operators and their approximations. Constructive approximation, 26 153-172.
Steinwart, I. and Christmann, A. (2008). Support vector machines. Springer Science & Business Media.
Steinwart, I. Hush, D. R., Scovel, C. et al. (2009). Optimal rates for regularized least squares regression. In COLT.

---

Steinwart, I. and Scovel, C. (2012). Mercer's 's theorem on general domains: On the interaction between measures. kernels, and rkhss. Constructive Approximation, 35 363-417.
Tarres, P. and Yao, Y. (2014), Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEP. Transactions on Information Theory, 60 5716-5735.
Tatarenko, T. and Kamgarpour, M. (2019). Learning nash equilibria in monotone games. In 2019 IEEE 58th Conference on Decision and Control (CDC), IEEE.
Tatarenko, and Kamgarpour, M. (2020), Bandit online learning of nash equilibria in monotone games. arXiv preprint 04X45:2009.02558
Triebel, (1995). Interpolation theory, function spaces. Differential Operators.
Triebel, H. (2010). Theory Function Spaces. Modern Birkhäuser Classics, Springer Basel.
Wahba, G. (1990). Spline models for observational data. SIAM.
Wood, K., Bianchin, G. and Dall' Anese, E. (2021). Online projected gradient descent for stochastic optimization with decision-depender distributions. IEEE Control Systems Letters, 1651.
Yao, Y. Rosasco, L. and Caponnetto, A. (2007), On carly stopping in gradient descent learning. Constructive Approximation, 26 289-315.
Ying. and Pontil, M. (2008). Online gradient descent learning algorithms. Foundations of Computational Mathematics, 561-596.
12


Reviews:
[{"review_id": "6CXxuX6oqx", "reviewer": "Reviewer_AyUq", "summary": "The authors focus on the analysis of learning the Nash equilibrium (which is unique) in strongly monotone games that are decision-dependent. They provide a definition of decision-dependent games generalizing a recent work of Narang et al. Intuitively speaking, if an agent chooses an action, he gets an observation (that depends on a distribution that is parametrized of everyone's actions) and his utility depends on the observed data (bandit setting) and everyone's actions. The authors provide an algorithm that converges to the Nash equilibrium in a rate of 1/t when the observed data depend linearly in the actions (linear regression type dependent-game), i.e., the focus is linear function classes. Further they focus on function kernel classes and provide similar type rates on convergence to the Nash equilibrium.", "questions": "What is the main technical challenge of your work?", "limitations": "Not applicable", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The idea of decision-dependent games is interesting, though it was firstly defined in another paper.", "weaknesses": "The algorithm (projection type gradient descent with also updating the estimate on the A matrix) and the analysis seems not novel and not surprising. I think the paper would be more interesting if the authors could argue for monotone and not only strongly monotone games or even going beyond that (e.g., games that satisfy MVI for example).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your time and effort in reviewing our paper. We have summarized the contribution and innovation of our paper over Narang et al. (2022) in the global response. In the following, we address other comments not covered in that response.\n\n**\"I think the paper would be more interesting $\\cdots$\":** \nThanks for this insightful question. We acknowledge that our work can be used to solve general monotone game or even games with weak MVI condition. The reason is our method features estimation of the performative gradient, which can be incorporated into other first-order methods for solving games [1]. We consider the strongly monotone games as an initial step for studying decision-dependent games. Extending to a more general class of decision-dependent games will be an important future direction.\n\n**\"What is the main technical challenge of your work?\":** \nThe technical challenges lies in three aspects: 1. we propose a general learning framework for decision-dependent game; 2. we introduce a dynamic regularization term $\\lambda_t$ in the online estimation to insure convergence; 3. we bound the estimation error of online stochastic approximation (10) under the power norm (Lemma 4). We refer the reviewer to **Novel I**  and **Novel II** in the global response for the demonstration on technical challenges of 1 and 2. We have summarized our result for 3 in **Novel III** and **Interpretation of Results in the RKHS Case**, now we provide a detailed explanation for the technical challenge of Lemma 4.\n\n**Technical Challenges of Lemma 4.** In the following, we use the notation defined in Appendix E. Intuitively, the main challenge to derive power norm bounds for iteration (75) (i.e. $f_t$) under the norm $\\lVert\\cdot\\rVert_\\gamma$ arises from the differing properties between the power space $\\mathcal{H}^\\gamma$ and the RKHS $\\mathcal{H}$. To elaborate, the standard method to derive error bounds under $\\lVert\\cdot\\rVert_\\mathcal{H}$ decomposes the error $f-f_t$ based on the operator $I-\\nu_t(L_t+\\lambda_tI)$ (such as Theorem 3.1 in [2]), and the analysis is based on the fact that $I-\\nu_t(L_t+\\lambda_tI)$ is a contraction map on $\\mathcal{H}$. This is because the sampling operator $L_t$ is compact, self-adjoint, and positive-semidefinite on $\\mathcal{H}$, thus, the spectral theorem implies $\\lVert I-\\nu_t(L_t+\\lambda_tI)\\rVert_{\\mathcal{H}\\rightarrow\\mathcal{H}}\\leq 1-\\nu_k\\lambda_k$. However, this operator does not exhibit the same behavior on the power space $\\mathcal{H}^\\gamma$. By the definition that $L_t=\\phi_t^*\\phi_t$, for any $h_1,h_2\\in\\mathcal{H}^\\gamma$, $L_t(h_i) = h_i(x^t)\\phi_t=\\langle h_i,\\phi_t^\\gamma\\rangle_\\gamma\\phi_t$ and $\\langle L_th_1,h_2\\rangle_\\gamma\\neq\\langle h_1,L_th_2\\rangle_\\gamma$ (here we lift the domain of $L_t$ from $\\mathcal{H}$ to $\\mathcal{H}^\\gamma$). Thus, $L_t$ is not self-adjoint or positive-definite on $\\mathcal{H}^\\gamma$ and the spectral norm $\\lVert I-\\nu_t(L_t+\\lambda_tI)\\rVert_{\\mathcal{H}^\\gamma\\rightarrow\\mathcal{H}^\\gamma}$ might larger than 1.\n\n**Our Approach.** To overcome the aforementioned obstacle, our approach has four steps: \n1. Since $L_t$ is stochastic and hard to analyze under the power norm, we consider the covariance operator $L_K$ and decompose the error $f-f_t$ by $L_K$ and $L_K-L_t$ ($L_K$ is the mean operator of $L_t$). We define the semi-stochastic population iteration (76) (i.e. $g_t$), which replaces $L_t$ with $L_K$ and remains the stochastic term $y_t\\phi_t$. We further decompose the error $f-f_t$ (Lemma 6 and Remark 2) and aim to derive the power norm bounds of $f-f_{\\lambda_t}$, $f_{\\lambda_t}-g_t$, and $f_t-g_t$.\n2. For the term $\\lVert f-f_{\\lambda_t}\\rVert_\\gamma$, we obtain the error bound by spectral decomposition (Lemma 7). We remark that $f_{\\lambda_t}$ is the solution of the kernel ridge regression with regularization $\\lambda_t$ (line 763) and $f$ minimizes the unregularized kernel regression. Intuitively, $\\lVert f-f_{\\lambda_t}\\rVert_\\gamma$ converges to zero if $\\lambda_f\\rightarrow0$.\n3. For the term $\\lVert f_{\\lambda_t}-g_t\\rVert_\\gamma$, we leverage $L_K$ to bridge the analysis between power norm and RKHS norm. Our estimation (Lemma 9) is based on the observation that $L_K$ is commutative with the operator $\\Pi_i^j$ (defined in (81)). This crucial property allows us to combine the martingale decomposition (81) with the fact $\\lVert f_{\\lambda_t}-g_t\\rVert_\\gamma = \\lVert L_K^{(1-\\gamma)/2}(f_{\\lambda_t}-g_t)\\rVert_{\\mathcal{H}}$ (Lemma 18) and derive the error bound under the RKHS norm.\n4. For the term $\\lVert f_t-g_t\\rVert_\\gamma$, we decompose $f_t-g_t$ by applying semi-stochastic decomposition (86) recursively. We observe that the iteration of $f_t-g_t$ (87) has a similar structure with $f_t$ (76), thus, we repeat the method in step 1 and consider the semi-stochastic population iteration of $f_t-g_t$, namely $r_t^{(0)}$ (line 842). We find that $f_t-g_t-r_t^{(0)}$ also has the same iteration structure as $f_t$ and $f_t-g_t$ (line 844). As a result, we repeat this procedure and define a sequence of noise process $\\{r_t^{(k)}\\}$ (Intuitively, we decompose $L_K-L_t$ by this recursive decomposition. See line 837 and more explanation in Appendix F6.2) and prove that $f_t-g_t$ can be written as a finite sum of noise processes (Lemma 16). Moreover, since each noise process is updated by $r_t^{(k)} = (I-\\nu_t(L_K+\\lambda_t I))r_{t-1}^{(k)}+\\nu_t(L_K-L_t)r_{t-1}^{(k-1)}$, we leverage the commutability between $L_K$ and $(I-\\nu_t(L_K+\\lambda_t I))$ and use the same technique in step 3 to obtain the power norm bound of each noise process(Lemma 14).\n\n[1] Pethick, T., Fercoq, O., Latafat, P., Patrinos, P., & Cevher, V. Solving stochastic weak Minty variational inequalities without increasing batch size. arXiv preprint arXiv:2302.09029,2023.\n\n[2] Tarres, P. and Yao, Y. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Transactions on Information Theory,2014."}, {"review_id": "DyQfSJ72gQ", "reviewer": "Reviewer_jNzm", "summary": "This work studies the framework of decision dependent games, where the actions of the agents in the game do not only affect the utilities of the players but also the distribution of population data observed by them. The critical challenge of this type of games is that the data population sampling process is not in general differentiable with respect to the parameters of the agents. The authors circumvent this by proposing a noisy stochastic differentiable model of the sampling distribution. The model itself is parametric and the authors propose OPGD an algorithm that learns both a the model parameters and the players strategy. The authors analyze both the linear and the RKHS setting for strongly monotone games.", "questions": "Is it possible for the players to first approximately learn the parameters of $f$ through the bandit feedback and then armed with that knowledge play the monotone game? If this is the case, how do the proposed algorithms compare to this baseline?", "limitations": "Limitations are addressed by the authors.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors have clearly explained the proposed framework and the necessary background to understand the challenges involved. While elements of the linear model setting existed in Narang et al, at least the RKHS component is to the best of my knowledge novel. The experimental results may be helpful to practitioners and may lead to practical (in addition to the theoretical) impact.", "weaknesses": "I think the differentiation between Narang et al and this work should be made more clear throughout. More specifically, what is the unique insight that allowed this work to arrive at the novel results?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive feedback and the time spent reviewing and understanding our paper! We have added more explanation on the contribution and innovation of our work in the global response. We address the other comments as follows:\n\n**\"I think the differentiation between Narang et al $\\cdots$\":**\nWe have highlighted our contribution over Narang et al. (2022) in the overall response. We refer the reviewer to **Novelty I** for our innovation of the parametric model and a statement of the difference between OPGD and Algorithm 1 in Narang et al. (2022). We refer to **Novelty II** for an explanation of the difficulty in the RKHS case and our approach. We refer to **Novelty III** for our theoretical contribution of the convergence analysis under the power norm, we interpret Lemma 4 and Theorem 2 in **Interpretation of Results in the RKHS Case** for better understanding.\n\nIn addition to the aforementioned contributions, we briefly demonstrate the technical challenge of bounding the estimation error under the power norm (Lemma 4) and our approach. Generally speaking, the standard method for convergence analysis under the RKHS norm fails in bounding the power norm [1]. Intuitively, the main difficulty arises from the differing properties between the power space $\\mathcal{H}^\\gamma$ and the RKHS $\\mathcal{H}$. For the online estimation step (75) (we will use the notation in Appendix E in the following text), the standard methods depend on the fact that $I-\\nu_t(L_t+\\lambda_tI)$ is a contraction map on $\\mathcal{H}$ (because the sampling operator $L_t$ is compact, self-adjoint, and positive-definite on this space). However, for the power space $\\mathcal{H}^\\gamma$, $L_t$ is not self-adjoint or positive-definite. Because for any $h_1,h_2\\in\\mathcal{H}^\\gamma$, by the definition of $L_t$ (here we lift the domain from $\\mathcal{H}$ to $\\mathcal{H}^\\gamma$), we have $L_t(h_i) = h_i(x^t)\\phi_t = \\langle h_i,\\phi_t^\\gamma\\rangle_\\gamma\\phi_t$ and $\\langle L_th_1,h_2\\rangle_\\gamma\\neq\\langle h_1,L_th_2\\rangle_\\gamma$.\n\nTo handle this problem, we use novel proof steps and decompose $L_t$ by the covariance operator $L_K$ (which is the mean operator of $L_t$) and $L_t-L_K$. To elaborate, we consider the semi-stochastic population iteration $g_t$ (76) and decompose $f_t-f$ by $f_{\\lambda_{t}}-f$, $g_t-f_{\\lambda_{t}}$, and $f_t-g_t$, where $f_{\\lambda_t}$ is the solution of the kernel ridge regression (line 762). Compared with $f_t$ (75), iterations of $g_t$ replace the stochastic operator $L_t$ with $L_K$ and remain the random term $y_t\\phi_t$.\n\nIntuitively, $f_{\\lambda_t}\\rightarrow f$ if $\\lambda_t\\rightarrow 0$, because $f$ is the minimizer of the unregularized regression (7). We obtain the power norm bound for $f_{\\lambda_t}-f$ by spectral decomposition (Lemma 7).\n\nTo analyze $g_t-f_{\\lambda_{t}}$, we derive the martingale decomposition (81) and observe that $L_K$ is commutative with the operator $\\Pi_i^j$. This allows us to use Lemma 18 ($\\lVert f_{\\lambda_t}-g_t\\rVert_\\gamma = \\lVert L_K^{(1-\\gamma)/2}(f_{\\lambda_t}-g_t)\\rVert_{\\mathcal{H}}$) to transfer the analysis of power norm bound to RKHS norm bound (Lemma 9).\n\nFor the term $f_t-g_t$, which is mainly characterized by the sampling error operator $L_K-L_t$, we use semi-stochastic decomposition (86) recursively to decompose this term. To elaborate, we observe that $f_t-g_t$ has the same iteration structure as $f_t$ and thus consider its semi-stochastic population iteration $r_t^{(0)}$. We further consider the error $f_t-g_t-r_t^{(0)}$ and use semi-stochastic decomposition recursively to define a noise process $\\{r_{t}^{(k)}\\}$ (86). We prove that $f_t-g_t$ can be written as a finite sum of $\\{r_{t}^{(k)}\\}$ (Lemma 16) and obtain the power norm bound of $r_{t}^{(k)}$ (Lemma 14).\n\n**\"Is it possible for the players to first approximately learn $\\cdots$\":** \nTo begin with, we remark that agents in decision-dependent games are very likely to face an online decision process: when the agents take action, the distribution of observed data changes. Thus, we want to play and learn the game simultaneously. Besides, it is indeed possible that we first learn the parametric model by offline data and plug it in to find the Nash equilibrium. In this case, $f_i$ can be estimated by the sampled version of the non-parametric regression (7) and the sample efficiency of the data-collection process might be an important concern. As a result, it may be helpful to study the optimal design to derive efficient offline algorithms. Generally speaking, the comparison of sample complexity and computational cost between offline and online algorithms depends on particular data-generation assumptions and would be a future direction for research.\n\n[1] Tarres, P. and Yao, Y. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Transactions on Information Theory, 2014."}, {"review_id": "DzQTd3SqYo", "reviewer": "Reviewer_QMrd", "summary": "This work proposes stochastic approximation-based Online Performative Gradient Descent to compute the Nash equilibrium of multi-agent decision-dependent games with bandit feedback. To this end they extend the work of Narang et al. (2022) in two ways: 1. The work uses stochastic approximation method to estimate the best linear operator $A_i$ to approximate the distribution map whereas Narang et al. (2022) assumes $A_i$ to be known. 2. Extend the result to the RKHS setting.", "questions": "If you could clarify your novelties over Narang et al. (2022), I would love to reconsider my score.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The work studies a relevant and interesting problem. \n\n2. The experimental results are promising. \n\n3. Extension of results from Narang et al. (2022) to RKHS extend the applicability of the results.", "weaknesses": "The theoretical novelty compared to Narang et al. (2022) seems inadequate and flawed to some extent. \n\n1.I am concerned about the use of $u_i^t$ to approximate $A_i$. The main challenge of problems with decision-dependent distribution is that the distribution depends on the *decisions* that is $x_i^t$ which makes estimation of $A_i$ difficult. OPGD assumes access to random samples from the distribution $\\rho_X$, and observes corresponding $y$ and use that to estimate $A_i$. If one assumes access to a separate sample $(u_i,y_i)\\sim \\rho_i$ then estimating $A_i$ is a simple stochastic approximation procedure and the corresponding theory is well-known in the online SGD and stochastic approximation (eqn (27), (28)). Combining these results with the ones (Theorem 6) in Narang et al. (2022) directly gives Theorem 1.  \n\n2. Say it was indeed possible to query such a point $u_i$. Then how to estimate $A_i$ is already explored in Section 6.3 of Narang et al. (2022) and it's almost the same method as OPGD with same theoretical rate (Theorem 7). \n\n3. The extension to RKHS increases the applicability but the proof techniques are almost the same, albeit involve more tedious calculations, as the linear case which is expected since it is after all a linear setting. The authors concur as well (line 310). \n\n4. Minor point: Assumption 7 is satisfied by Gaussian distn but here $\\rho_X$ is supposed to have a compact support since $X$ is compact. So $\\rho_X$ can't be Gaussian. But anyway, Assumption 7 can be satisfied by other distribution and it's not a major concern.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your detailed and valuable review. We have outlined the contribution of our work in the global comment. Next, we will address the questions not included in that particular response.\n\n**\"I am concerned about the use of $\\cdots$\":**\nThanks for this question. We regard the use of $u_i^t$ as proper. Intuitively, an agent taking the action $u_i^t$ can be viewed as an exploration of the action space. In more detail, to learn the strategic behavior of other agents, it is feasible for agents to explore the space under certain personalized rules, namely, taking actions under the user-specified sampling distribution $\\rho_{\\mathcal{X}}$. A major benefit of considering $u_i^t$ and $\\rho_{\\mathcal{X}}$ is that we can extend the algorithm to the non-linear function class,  while the method in Narang et al. (2022) fails, we will explain this in the next answer. As a result, our learning framework can be generalized to larger function classes such as RKHS or even beyond that, such as overparameterized neural networks using the technique of neural tangent kernel.\n\n**\"Say it was indeed possible to query $\\cdots$\":** \nWe remark that our method is essentially different from Narang et al. (2022). Since the linear assumption is restrictive, a major motivation of our work is learning decision-dependent games with a non-linear parametric model, which is more applicable. However, the method in Narang et al. (2022) fails for the non-linear parametric model. To elaborate, we briefly summarize the sampling strategy in Narang et al. (2022) Algorithm 1: In iteration $t$, sample a $z_i^t$ at current the action $z_i^t\\sim\\mathcal{D}_i(x^t)$ and let the agent play again with an inject noise $u^t$ to obtain a sample $q_i^t\\sim\\mathcal{D}_i(x^t+u^t)$. \n\nNarang et al. (2022) leverages the difference between $z_i^t$ and $q_i^t$ to estimate the unknown parametric matrix $A_i$, their approach is based on the fact that $\\mathbb{E}[q_i^t-z_i^t|u^t,x^t] = A_iu^t$. Since $\\mathbb{E}[q_i^t-z_i^t|u^t,x^t]$ is not related with $x^t$, $A_i$ can be estimated by ordinary least square. We remark that this approach depends on the linear parametric assumption and cannot be generalized to the non-linear case. In more detail, consider this sample strategy in the RKHS case, we have $\\mathbb{E}[q_i^t-z_i^t|u^t,x^t] = f_i(x^t+u^t)-f_i(x^t) = \\langle f_i,\\phi_{x^t+u^t}-\\phi_{x^t}\\rangle_{\\mathcal{H}}$. Thus, $\\mathbb{E}[q_i^t-z_i^t|u^t,x^t]$ depended on agents' actions, and the estimation of $f_i$ is related to the dynamics of $\\{x^t\\}$ (approximate $f_i$ not a simple non-parametric regression because the pattern of $\\{x^t\\}$ is influenced by the project gradient descent). Intuitively, the change of agents' actions in different iterations brings additional errors and makes the estimation difficult and even fails to converge. \n\n**\"The extension to RKHS increases the applicability $\\cdots$\":** \nWe apologize for the confusion in line 310: \"The proof is similar to that of Theorem 1.\" Due to the limitation of pages, we omit the sketch of proof for Theorem 2 and here we aim to convey that the structure of proof for Theorem 2 is similar to the linear case, namely, Theorem 2 is guaranteed by the estimation error (Lemma 4) and the one-step error (Lemma 5). However, bounding the estimation error (Lemma 4) is not trival and we acknowledge this key lemma as a major contribution of our paper. Briefly speaking, we study the estimation error of the online stochastic approximation (10) under the power norm $\\lVert\\cdot\\rVert_\\gamma$ and obtain a fast rate $\\mathcal{O}(t^{-(\\beta-\\gamma)/(\\beta-\\gamma+2)})$, in contrast to the classical minimax optimal rate of one-pass SGD $\\mathcal{O}(t^{-(\\beta-1)/(\\beta+1)})$ under the RKHS norm $\\lVert\\cdot\\rVert_{\\mathcal{H}}$. \n\nWe remark the standard techniques of online stochastic approximation under the RKHS norm fail in the power norm, the main difficulty arises from the differing properties between the power space $\\mathcal{H}^\\gamma$ and the RKHS $\\mathcal{H}$. For the online estimation step (75) (we will use the notation in Appendix E in the following text), the standard methods depend on the fact that $I-\\nu_t(L_t+\\lambda_tI)$ is a contraction map on $\\mathcal{H}$ (because the sampling operator $L_t$ is compact, self-adjoint, and positive-definite on this space). However, for the power space $\\mathcal{H}^\\gamma$, $L_t$ is not self-adjoint or positive-definite. To obtain the error bound under the power norm, we take a series of novel proof steps, such as considering the semi-stochastic population iteration $g_t$ (76) and applying the semi-stochastic decomposition recursively (86) to decompose the semi-stochastic sampling noise $g_t-f_t$. We refer the reviewer to Appendix E (Specifically, Page 26) for the proof outline.\n\n**\"Minor point: Assumption 7 is satisfied by $\\cdots$\":** \nThanks for pointing out the mistakes! We will revise this example in the revision. In fact, we use $\\rho_{\\mathcal{X}} = \\mathcal{U}[0,1]$ in the numerical experiments, which satisfies the assumption.\n\n**\"If you could clarify your novelties over Narang et al. (2022) $\\cdots$\":**\nWe present the novelties in the global response. We refer the reviewer to **Novel I** for the comparison of OPGD and Algorithm 1 and Narang et al. (2022). We refer to **Novel II** for the explanation that extending the linear algorithm into the non-linear (RKHS) case is not trivial and our approach (introduce the dynamic regularization term $\\lambda_t$). We summarize our contribution to the convergence analysis under the power norm in **Novel III** and present a detailed explanation for Lemma 4 and Theorem 2 in **Interpretation of Results in the RKHS Case**. Also, we present addition experiments on multi-agent decision-dependent games, and compare linear OPGD, kernel OPGD, and AGM (Algorithm 1 in Narang et al. (2022)) in **supplemental_experment.pdf**. "}, {"review_id": "qDbL7XGDdn", "reviewer": "Reviewer_sLZ8", "summary": "The authors study multi-agent decision-dependent games. Due to strategic interactions among agents, classical gradient-based methods cannot be directly applied in computing Nash equilibrium. Instead, the authors propose using parametric models to model the agents' interactions and the resulting OPGD algorithm. The authors show that, For strongly monotone such games, OPGD converges to NE under (mostly) standard assumptions, including those on the function classes used in defining the parametric models. Numerical experiments on toy game instances complement the theoretical findings.", "questions": "- The experiments are on very simple instances, on which the algorithms seem to degenerate to known online regression algorithms. Are there specific reasons (technical difficulty or otherwise) that the authors decide not to include any experiments with $\\geq 2$ agents? It would be helpful to have these experiments and ideally compare with existing algorithms (e.g., Section 4.3 Repeated Stochastic Gradient Method in https://arxiv.org/pdf/2201.03398.pdf). I believe for linear parametric models, OPGD would outperform those as it makes uses of this structure.\n\n- The linearity assumption (Assumption 6) is quite restrictive. However, as a first step toward understanding the convergence behavior of OPGD, this looks ok. It would be valuable to know, via experiments, that the algorithm (Eq. (8) and (9)) still runs and could give high-quality approximate NE even if linearity of the parametric model does not hold. Would you be able to empirically verify this too, by constructing multi-dimensional games such that $f_i(x)$'s are not linear in $x$? More generally, I would try to have new sets of experiments with less structured $f_i$'s, and compare the \"linear OPGD\", the \"kernel function OPGD\", and an existing (likely rudimentary) baseline algorithm to demonstrate the benefit of incorporating parametric models.\n\nRegarding the above two questions, for the rebuttal period, it would be sufficient to provide a plan for new experiment setups instead of results. Although it would be great to have preliminary results.\n\n- Line 118: It may help the reader understand the setting further if the authors can add a sentence after the last sentence of this paragraph, stating that (or similar): In round $t$, of the game, each agent $i$ only has access to realized $z_i^{1}, \\dots, z_i^{t-1}$, and solves the sampled (aka ERM) version of the optimization formulation (1).\n\n- For (5), if $\\mathcal{D}_i(x)$ is a continuous distribution, then exchanging differentiation and integration/expectation requires further (boundedness) assumptions. Please verify if existing assumptions are sufficient and point this out.\n- In Theorem 1, $D_1$ involves $t$ and should *not* be a constant? Maybe $t$ should be $1$ instead (since $t\\geq 1$)?", "limitations": "The authors have stated the limitations in terms of technical assumptions. I do not see any potential negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Simple and implementable algorithms for a new problem setting.\n- The convergence rate results use mostly reasonable assumptions that are common in stochastic optimization and online regression.\n- Proof sketches are informative and help understand the proof ideas.", "weaknesses": "- Strong linearity assumption and simple, 1-agent experiments which seem to be the same as known online regression problems.\n- \nSee **Questions** for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and kind suggestions! We clarify our novelty over Narang et al. (2022) in the global response. We refer the reviewer to **Novel I** for the comparison of OPGD and Algorithm 1 and Narang et al. (2022). We refer to **Novel II** for the explanation that extending the linear algorithm into the non-linear (RKHS) case is not trivial and our approach (introduce the dynamic regularization term $\\lambda_t$). We summarize our contribution to the convergence analysis under the power norm in **Novel III** and present a detailed explanation for Lemma 4 and Theorem 2 in **Interpretation of Results in the RKHS Case**. In the following, we provide responses to your questions.\n\n**\"Strong linearity assumption and simple $\\cdots$\":**\nWe propose OPGD for both the linear and kernel function classes. In fact, linear OPGD (Algorithm 1) depends on the linear assumption (Assumption 6) and Assumption 7, and the kernel OPGD (Algorithm 2) depends on Assumption 8, 9, 10 and does not require Assumptions 6 or 7. In more detail, the parametric assumption of kernel OPGD is Assumption 8, which assumes $f_i\\in(\\mathcal{H}^\\beta)^p$. The power space $\\mathcal{H}^\\beta$ is non-linear, thus, the kernel OPGD can address the non-linear parametric model. Besides, we can potentially extend the kernel OPGD to larger function classes, such as overparameterized neural networks using the technique of neural tangent kernel [1].\n\n**\"The experiments are on very simple instances $\\cdots$\":**\nWe present the supplemental experiments on multi-agent decision-dependent games (2-agent games) in **supplemental_experiment.pdf**. Figure 1 shows that the linear OPGD matches the theoretical rate $\\mathcal{O}(t^{-1})$. Figure 2 compares the linear OPGD with Repeated Stochastic Gradient Method (Narang (2022) Section 4.3, which is the baseline algorithm in performative prediction to find the stable equilibrium) and Adaptive Gradient Method (Narang (2022) Algorithm 1). Figure 2 shows that Linear OPGD has the same convergence rate with Adaptive Gradient Method, and Repeated Stochastic Gradient Method fails to find the Nash equilibrium because it does not leverage the parametric model.\n\n\n\n**\"The linearity assumption (Assumption 6) is quite restrictive $\\cdots$\":**\nThe kernel OPGD is capable of finding the Nash equilibrium in non-linear models. We present the result of a 2-agent decision-dependent game with the non-linear parametric model in **supplemental_experiment.pdf**. Figure 3 shows that the kernel OPGD matches the theoretical rate $\\mathcal{O}(t^{-1/2})$. Figure 4 compares the kernel OPGD with Linear OPGD and Adaptive Gradient Method. Figure 4 shows that kernel OPGD converges to the Nash equilibrium as our theory predicts, but Linear OPGD and Adaptive Gradient Method fail to find NE.\n\n**\"Line 118: It may help the $\\cdots$\":**\nThanks for your helpful advice! In the round $t$, the agent $i$ only has access to $z_i^1,\\cdots,z_i^{t-1}$ and $x^1,\\cdots,x^{t-1}$. We will explain the oracle of agents in this paragraph for better understanding. \n\n**\"For (5), if $\\mathcal{D}_i(x)$ is $\\cdots$\":**\nWe view interchangeability as a basic assumption in our paper (we will clarify this in the revision). Here we derive a sufficient condition for this assumption. Under the parametric assumption, $\\mathcal{L}_i(x)$ can be rewritten as\n\n$\\mathbb{E}_{\\epsilon_i\\sim\\mathcal{P}_i} \\ell_i(x,f_i(x)+\\epsilon_i)$ (line 156). Since we have assumed $\\ell_i,f_i$ are continuous and have continuous partial derivatives, then to ensure the differentiation and expectation are interchangeable, we need additional assumptions such as $\\ell_i(x,f_i(x)+\\epsilon_i)$ is integrable with respect to the measure $\\epsilon_i\\sim\\mathcal{P}_i$ for any $x\\in\\mathcal{X}$ and the improper integral $\\int\\partial\\ell_i(x,f_i(x)+\\epsilon_i)/\\partial x_i~d\\mathcal{P}_i$ converges uniformly with respect to $x$. As a result, a sufficient condition is: $\\ell_i$ is Lipschitz continuous in $x$ and $z_i$, and $f_i$ is Lipschitz in $x$, which is the same sufficient condition for Assumption 4 and Assumption 5.\n\n**\"In Theorem 1, $\\cdots$\":**\nWe apologize for the typo, the true expression is $D_1 := 4\\zeta^2(1+2(M/(t_0+1)+\\sup_{i\\in[n]}\\lVert A_i\\rVert_F^2))$, where $D_1$ is a constant and not related to iteration $t$. We will correct this typo in the revision.\n\n[1] Allen-Zhu, Z., Li, Y., & Liang, Y. Learning and generalization in overparameterized neural networks, going beyond two layers. NIPS, 2019."}, {"review_id": "ZCTkExvVir", "reviewer": "Reviewer_wDhV", "summary": "This paper studies the problem of multi-agent performative game. The authors generalize the existing assumption in (Narang et al., 2022) from linear cases to generalized linear cases, and proposed algorithms consisting online stochastic approximation of the link function and individual gradient updates. They prove convergence rates of linear function class and kernel function class, with numerical experiments validate their theory. ", "questions": "Some notations are wrong or at least confusing: \n\n  Page 4, assumption 1: Is the second $\\mathfrak{F}^{p}$ actually $\\mathfrak{F}$?\n\n  Page 4, Line 162: Would it be better to use another notation (i.e., $\\hat{f}_i$) on the left-hand-side in (7), since $f_i$ already denotes the ground-truth function of player $i$?\n", "limitations": "No. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem statement is clear, and the solution is intuitive. The authors were the first to discuss how to estimate the unknown structure of the distribution in multi-agent performative games, which is a definitely important topic in the machine learning literature. ", "weaknesses": "The authors should elaborate more about their technical contribution. The current recipe of the proofs mostly follows (Narang et al., 2022), with the accurate parameter of distribution map replaced by an estimated version, which further generates similar error terms that can be controlled via similar techniques in bounding existing terms. It would be better if the authors could emphasize their technical contributions on the way to their theoretical results. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review and suggestions. We have explained our novelty over Narang et al. (2022) in the global response. We refer the reviewer to **Novel I** for the comparison of OPGD and Algorithm 1 and Narang et al. (2022). We refer to **Novel II** for the explanation that extending the linear algorithm into the non-linear (RKHS) case is not trivial and our approach (introduce the dynamic regularization term $\\lambda_t$). We summarize our contribution to the convergence analysis under the power norm in **Novel III** and present a detailed explanation for Lemma 4 and Theorem 2 in **Interpretation of Results in the RKHS Case**. We will address the remaining questions in the following text.\n\n**\"The authors should elaborate more about their technical contribution $\\cdots$\":**\nWe apologize that the technical contribution was not highlighted clearly in the initial submission. Although the proof strategy for the linear case is similar to Narang et al. (2022), the proof in the RKHS case (Theorem 2) is non-trivial, specifically, we derive the first convergence analysis for online stochastic approximation under the power norm in Lemma 4 (which is the most challenging part of our work).\n\nWe will demonstrate the technical challenges and our approach for deriving the estimation error bound (i.e. Lemma 4, which is the key lemma to obtain Theorem 2) in the following text. To begin with, we refer the reviewer to the explanation of our results (**Novel III**) in the global response for better understanding.\n\n**Technical Challenges of Lemma 4.** With the notations set out in Appendix E, the primary obstacle in establishing power norm bounds for iteration (75) ($f_t$) under the norm $\\lVert\\cdot\\rVert_\\gamma$ comes from the difference between the power space $\\mathcal{H}^\\gamma$ and the RKHS $\\mathcal{H}$. To explain further, the standard technique to derive error bounds under $\\lVert\\cdot\\rVert_\\mathcal{H}$ decomposes the error $f-f_t$ using the operator $I-\\nu_t(L_t+\\lambda_tI)$ (as seen in Theorem 3.1 in [1]), with the analysis based on the fact that $I-\\nu_t(L_t+\\lambda_tI)$ is a contraction map in $\\mathcal{H}$. In more detail, $L_t$ is compact, self-adjoint, and positive-semidefinite on $\\mathcal{H}$, leading to $\\lVert I-\\nu_t(L_t+\\lambda_tI)\\rVert_{\\mathcal{H}\\rightarrow\\mathcal{H}}\\leq 1-\\nu_k\\lambda_k$. However, this operator does not have the same property in the power space $\\mathcal{H}^\\gamma$. By the definition $L_t=\\phi_t^*\\phi_t$, for any $h_1,h_2\\in\\mathcal{H}^\\gamma$, we have $L_t(h_i) = h_i(x^t)\\phi_t=\\langle h_i,\\phi_t^\\gamma\\rangle_\\gamma\\phi_t$ and $\\langle L_th_1,h_2\\rangle_\\gamma\\neq\\langle h_1,L_th_2\\rangle_\\gamma$, and therefore, $L_t$ isn't self-adjoint or positive-definite on $\\mathcal{H}^\\gamma$. This makes the spectral norm $\\lVert I-\\nu_t(L_t+\\lambda_tI)\\rVert_{\\mathcal{H}^\\gamma\\rightarrow\\mathcal{H}^\\gamma}$ possibly larger than 1.\n\n**Our Approach.** To overcome the aforementioned obstacle, our approach has four steps: \n1. Given that $L_t$ is stochastic and challenging to analyze under the power norm, we leverage the covariance operator $L_K$ (which is the mean operator of $L_t$) and decompose the error $f-f_t$ by $L_K$ and $L_K-L_t$. We observe that $L_K$ has some good properties under the power norm (see step 3) and $L_K-L_t$ can be further decomposed by semi-stochastic decomposition (step 4). We define the semi-stochastic population iteration (76) ($g_t$), which replaces $L_t$ with $L_K$ and keeps the stochastic term $y_t\\phi_t$. We further decompose the error $f-f_t$ by $f-f_{\\lambda_t}$, $f_{\\lambda_t}-g_t$, and $f_t-g_t$  (Lemma 6 and Remark 2).\n2. For the term $\\lVert f-f_{\\lambda_t}\\rVert_\\gamma$, we obtain the error bound by spectral decomposition (Lemma 7). We remark that $f_{\\lambda_t}$ is the solution of the kernel ridge regression with regularization $\\lambda_t$ (line 763) and $f$ minimizes the unregularized kernel regression. Intuitively, $\\lVert f-f_{\\lambda_t}\\rVert_\\gamma$ converges to zero if $\\lambda_f\\rightarrow0$.\n3. To analyze the term $g_t-f_{\\lambda_{t}}$, we derive the martingale decomposition (81) and notice that $L_K$ is commutative with the operator $\\Pi_i^j$. This commutativity allows us to use Lemma 18, expressed as $\\lVert f_{\\lambda_t}-g_t\\rVert_\\gamma = \\lVert L_K^{(1-\\gamma)/2}(f_{\\lambda_t}-g_t)\\rVert_{\\mathcal{H}}$, to transfer the analysis from power norm bounds to RKHS norm bounds (Lemma 9).\n4. For the term $f_t-g_t$, which is primarily characterized by the sampling error operator $L_K-L_t$, we use semi-stochastic decomposition (86) recursively to decompose this term. Specifically, we observe that the iteration structure of $f_t-g_t$ is identical to that of $f_t$. We thus consider its semi-stochastic population iteration $r_t^{(0)}$. Further, we examine the error $f_t-g_t-r_t^{(0)}$ and use semi-stochastic decomposition recursively to define a noise process ${r_{t}^{(k)}}$ (86). We then prove that $f_t-g_t$ can be written as a finite sum of ${r_{t}^{(k)}}$ (Lemma 16) and obtain the power norm bound of each $r_{t}^{(k)}$ (Lemma 14).\n\n**\"Page 4, assumption 1: Is the second $\\cdots$\":**\nWe apologize for the confusion. The function $f_i$ defined in Assumption 1 is a p-dimensional vector function, here we assume each coordinate of $f_i$ belongs to the function class $\\mathscr{F}$. We will revise this sentence for better understanding.\n\n**\"Page 4, Line 162: Would it $\\cdots$\":**\nThanks for your suggestion! We will use $\\hat{f}_i$ instead of $f_i$ in the revision.\n\n[1] Tarres, P. and Yao, Y. Online learning as stochastic approximation of regularization paths: Optimality and almost-sure convergence. IEEE Transactions on Information Theory, 2014."}]

Author rebuttal:
In the following, we present a detailed explanation of our novelty over Narang et al. (2022).

**Novelty I.** We extend the linear model (Assumption 6) in Narang et al. (2022)  (which assumes agents share a common parametric matrix $A = [A_i~A_{-i}]$) into a general framework (parametric functions $f_i$ are different among agents). We derive sufficient conditions for the game to be strongly monotone (Proposition 2). We propose OPGD for the linear function class and extend it to the kernel function class (the extension is non-trivial and we refer to **Novelty II** for explanations). 

The core problem in decision-dependent games is estimating the performative gradient, and OPGD uses a different method for this compared with Narang et al. (2022). To elaborate, Algorithm 1 in Narang et al. (2022) samples $z_i^t\sim\mathcal{D}_i(x^t)$ at current the action and let agents play again with an injected noise $u^t$ to obtain $q_i^t\sim\mathcal{D}_i(x^t+u^t)$. Their approach is based on the fact that $\mathbb{E}[q_i^t-z_i^t|u^t,x^t]=A_iu^t$,which is not related to $x^t$. Thus, $A_i$ can be estimated by online least square. 

However, this method cannot be generalized to non-linear (RKHS) cases, because $\mathbb{E}[q_i^t-z_i^t|u^t,x^t]=f_i(x^t+u^t)-f_i(x^t)=\langle f_i,\phi_{x^t+u^t}-\phi_{x^t}\rangle_{\mathcal{H}}$. Thus, $\mathbb{E}[q_i^t-z_i^t|u^t,x^t]$ depends on agents' actions and the change of action will bring additional error that makes the estimation fail to converge. Besides, there is a minor issue that $x^t+u^t$ might go out of the compact action space.

OPGD lets agents play $u_i^t\sim\rho_{\mathcal{X}}$ to explore the action space and learn the strategic behavior of other agents. OPGD estimates the parametric function by solving the ERM version of (7) using online stochastic approximation (8), (10). This learning framework can be extended to RKHS and potentially beyond that, such as overparameterized neural networks using the technique of neural tangent kernel [1].

**Novelty II.** The major difficulty in the RKHS case is that an RKHS generally has infinite dimensions, and solving the ERM version of (7) leads to ill-posed solutions. Mathematically, by Mercer's theorem, the covariance operator $L_K$ has the spectral decomposition (23) and its eigenvalues satisfy $\mu_i\rightarrow0$. Thus, $L_K-\ell_1I$ is not a positive operator for any $\ell_1>0$ and $L_K\succeq\ell_1I$ does not hold. As a result, Assumption 7 is not satisfied in the RKHS case and $u_i^t\sim\rho_{\mathcal{X}}$ cannot sufficiently explore the action space.

To handle this problem, we introduce the regularization term $\lambda_t$ and aim to solve a kernel ridge regression (line 190). Since the kernel ridge has a biased solution $f_{\lambda_t}$, we let $\lambda_t$ shrink to $0$ gradually to ensure $f_{\lambda_t}\rightarrow f$. We remark that the change of $\lambda_t$ will bring drift error $f_{\lambda_t}-f_{\lambda_{t-1}}$, which is closely nested with the estimation error $f_t-f$. We choose $\nu_t$ and $\lambda_t$ carefully to let $f_{\lambda_t}-f$ and $f_t-f_{\lambda_t}$ converge simultaneously (Lemma 4). 

**Novelty III.** We study the convergence rate of the online stochastic approximation for linear function class (Lemma 1) and kernel function class (Lemma 4) and our technical contribution mainly lies in the kernel case. We derive the first convergence analysis for online stochastic approximation under the power norm $\lVert\cdot\rVert_{\gamma}$ and obtain a fast rate $\mathcal{O}(t^{-(\beta-\gamma)/(\beta-\gamma+2)})$ (Lemma 4), in contrast to the classical minimax optimal rate for one-pass SGD under the RKHS norm $\mathcal{O}(t^{-(\beta-1)/(\beta+1)})$ [2][3]. To elaborate, we leverage the embedding property (Assumption 9) to show that one can choose the power norm properly to achieve faster convergence rates (we reiterate our results in the next paragraph). To obtain the estimation error bounds under the power norm (Lemma 4), we use novel proof steps such as considering the semi-stochastic population iteration $g_t$ (76), deriving the martingale decomposition (81), and decomposing the semi-stochastic sampling noise $g_t-f_t$ by applying the semi-stochastic decomposition recursively (86).

**Interpretation of Results in the RKHS Case.** Lemma 4 presents the error bound of online stochastic approximation (10) under the power norm $\lVert\cdot\rVert_\gamma$, our result includes the classical theory under the RKHS norm $\lVert\cdot\rVert_{\mathcal{H}}$ and extends it in a continuous scale. In more detail, for any $\gamma\in[\alpha,\beta)$ and $\gamma\leq1$, Lemma 4 describes how to choose the step-sizes $\nu_t$ and regularization term $\lambda_t$ properly (line 598) to insure convergence under $\lVert\cdot\rVert_\gamma$ with the convergence rate $\mathcal{O}(t^{-(\beta-\gamma)/(\beta-\gamma+2)})$. For $\beta>1$ and $\gamma=1$, this rate would be $\mathcal{O}(t^{-(\beta-1)/(\beta+1)})$ and matches the optimal rate under the RKHS norm. If the embedding property (Assumption 9) holds for some $\alpha<1$, we choose $\gamma=\alpha$ to achieve a faster rate $\mathcal{O}(t^{-(\beta-\alpha)/(\beta-\alpha+2)})$ and further derive Theorem 2. Besides, while classical theory assumes Assumption 8 holds for $\beta>1$ (i.e. $f_i\in(\mathcal{H}^\beta)^p\subset(\mathcal{H})^p$), our result relaxes this assumption to $\beta>\alpha$ and allows $\beta\leq 1$. Intuitively, this implies that the online stochastic approximation can address the misspecification case $f_i\notin(\mathcal{H})^p$ if $\alpha<1$.

[1] Allen-Zhu, Z., Li, Y., & Liang, Y. Learning and generalization in overparameterized neural networks, going beyond two layers. NIPS,2019.

[2] Ying, Y. and Pontil, M. Online gradient descent learning algorithms. Foundations of Computational Mathematics,2008.


[3] Lin, J. and Cevher, V. Optimal convergence for distributed learning with stochastic gradient methods and spectral algorithms. The Journal of Machine Learning Research,2020.

Meta-review: This paper examines the convergence of gradient descent in games with decision-dependent randomness (also referred to as multi-agent performative prediction). The authors consider a nonlinear model for the dependence of the randomness on the players' decision, and they analyze a kernel-based version of the online performative gradient descent (OPGD) algorithm, providing asymptotic rates of convergence for strongly monotone games.

This paper was discussed extensively by the reviewers, area chairs and senior area chairs. Initially, the reviewers were reluctant and raised a number of concerns, several of which were addressed by the authors' rebuttal, leading to a positive final assessment by the reviewers. At the same time, some concerns did remain, mostly regarding the paper's novelty over previous work by Narang et al.

The setting of Narang et al. is similar to the authors' except for the nonlinearity in the randomness, so the main issue was the degree of generality provided by the authors' model, and the new insights offered by the authors' analysis. Of the three novelties argued by the authors - different parametric dependence across agents, treating the infinite-dimensional RKHS setting, and the new convergence rates - the most significant ones concerned the intricacies of the RHKS treatment and the changes that this entails on the convergence rate of OPGD. In this regard, the program committee would urge the authors to focus their paper on introducing the Kernel version (section 4.2) and be clear that their main novelty is extending the prior linear parameterization case to a kernel-based one (which is what they analyze).

Another issue that came up in the discussion is that, contrary to the authors' claim in the abstract and the introduction, they do not treat the derivative-free / bandit feedback setting, as their algorithms requires access to a (possibly stochastic) first-order oracle. [By contrast, Narang et al. do treat the bona fide bandit feedback case] The discussion with the authors confirmed this point, so the authors would have to clarify that they are taking a first-order, oracle-based approach, not a zeroth-order, loss-based one.

Finally, even though the paper has been written in an overall clear manner, it lacks an in-depth discussion of applications relevant to ML. In this regard, the program committee would urge the authors to lay out a concrete application which can be based on examples from prior works, but which emphasizes the benefit of the kernel variant in an application context (e.g., maybe nonlinear pricing in a ride-share market...).

Despite the above limitations, the paper's analysis and results provide a number of fruitful insights into an active research field. In view of this, and conditioned on the above changes and revisions, I am happy to recommend acceptance.
Decision: Accept (poster)