Performative Control for Linear Dynamical Systems

Authors: songfu  cai
fei  han
xuanyu  cao
Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-25 08:40:52

Abstract: We introduce the framework of performative control, where the policy chosen by the controller affects the underlying dynamics of the control system. This results in a sequence of policy-dependent system state data with policy-dependent temporal correlations. Following the recent literature on performative prediction \cite{perdomo2020performative}, we introduce the concept of a performatively stable control (PSC) solution. We first propose a sufficient condition for the performative control problem to admit a unique PSC solution with a problem-specific structure of distributional sensitivity propagation and aggregation. We further analyze the impacts of system stability on the existence of the PSC solution. Specifically, for almost surely stable policy-dependent dynamics, the PSC solution exists if the sum of the distributional sensitivities is small enough. However, for almost surely unstable policy-dependent dynamics, the existence of the PSC solution will necessitate a temporally backward decaying of the distributional sensitivities. We finally provide a repeated stochastic gradient descent scheme that converges to the PSC solution and analyze its non-asymptotic convergence rate. Numerical results validate our theoretical analysis.

Main paper: 
 introduction: 
 Control theory is a fundamental field of study in engineering and mathematics that centers on coordinating the behaviors of dynamical systems. It has extensive applications in aerospace, robotics, manufacturing, economics, natural sciences, etc. It provides a framework for designing control policies that regulate the system states, enabling them to evolve in a desired manner over time dynamically. The linear state space model is a powerful tool for representing dynamical systems, which employs a set of difference equations to describe the Markovian system state process with a linear state transition model. Many of the existing works on control of linear dynamical systems (LDSs) [26, 9, 31, 7, 17, 28, 31, 32] are developed based on the key assumption that the system state transition model is static. However, in many real world applications, such a static dynamics assumption usually does not hold because system state transition model can be changed by control policies. For instance, in the stock market, the investment policy of well-known investors can impact the actions of the general public investors, resulting in famed investment strategy-dependent changes to the dynamics of stock prices. Another example is autonomous vehicle (AV). A deployed AV might change how the pedestrians and other neighboring cars behave, and the resulting traffic environment might be quite different from what the designers of the AV had in mind [20] . Such interplay between decision-making and decision-dependent system dynamics is a pervasive phenomenon in a multitude of domains, including finance, transportation, and public policy, among others.Most of the existing works on the control of linear systems with non-static state transition model are primarily focused on the additive random perturbations to the system state transition matrix, where policy optimization methods are employed to find the optimal control policy that minimizes quadratic costs [10, 1, 11, 8] . This type of problem also includes the control of linear systems with additive state-dependent noise [15, 6] or action-dependent noise [30, 4] , which is equivalent to having additive perturbations on the state transition matrix or the control input gain matrix, respectively. Some other works on jump/switched linear systems formulate the variation of system model as stochastic model jumps among multiple linear modes, where the jumping law is governed by a finite time-homogeneous Markov process. However, in all these works, the changes of the system model are unrelated to the control policy.Performative prediction provides a systematic way to model the interaction between decision-making and data via decision-dependent data distribution maps [23] . The pioneering work by [21] has led to a growing body of research dedicated to performative prediction problems. Most of these studies are focused on establishing the conditions for the existence and uniqueness of the performative stable point and designing learning algorithms with provable convergence to such a unique performative stable point [13, 14, 5, 3, 18, 29, 25] , or algorithms to find a stationary solution of the performative risk [12, 19, 25] .An open question follows: Can the idea of performative prediction, which tackles decision-dependent data in the learning/prediction domain, be employed to address the decision-dependent dynamics in the control domain? Notice that in all the aforementioned performative prediction works [21, 13, 14, 5, 3, 18, 29, 25, 12, 19, 25] , the data input to the learning algorithms are independently generated based on the decision-dependent distributions. No temporal correlation is considered or exploited between two consecutive sets of input data. However, in the context of control, the situation is different as the changing system dynamics introduce various additional complexities. This is because the data of the system state at each time the step will depend on the decision-dependent state transition matrices in all previous time steps. The expected total cost function to be optimized will depend on all the decision-dependent state transition matrices across the entire control time horizon. This implies that we need a framework of performative control that is more general than the framework of performative prediction, and that can accommodate a sequence of decision-dependent data with temporal correlations, where the temporal correlations are again decision-dependent.In this work, we provide an affirmative answer to the above question. Our idea hinges on adopting the concept of performative stable solution [21] , which is a fixed point solution for the interplay between the controller and the system dynamics that react to the controller's decisions. The condition for the existence of such a performative stable solution is obtained by analyzing the propagation and aggregation of sensitivities associated with the distributions of policy-dependent system dynamics over the entire control time horizon. In particular, we follow existing studies [1, 11, 8] and focus on the disturbance-action policy, which allows the consideration of general convex control costs instead of only quadratic control costs.To the best of our knowledge, this paper provides the first study and analysis of performative control of linear systems where the system dynamics are constantly changing in a control-policy-dependent manner. We highlight the following key contributions:• We introduce the notion of performative control, where the deployed control policy affects the underlying dynamics of the control system. We provide sufficient conditions for the existence and uniqueness of the performative stable control (PSC) solution. The sufficient condition is expressed in terms of a weighted sum of all the distributional sensitivities associated with the policy-dependent system state transition matrices over the entire control horizon. An interesting finding is that the sufficient condition exhibits a structure of sensitivity propagation and aggregation, implying that it is preferable for sensitivities to be relatively small in the early stages of the system state evolution. • We analyze the impacts of system stability on the existence and uniqueness of the PSC solution. We show that when the policy-dependent dynamics are almost surely strongly stable, the PSC solution exists if the sum of all distributional sensitivities is below a certain threshold. On the other hand, when the policy-dependent dynamics are almost surely unstable, the proposed sufficient condition for the existence of the PSC solution will place a necessary requirement on a temporally backwards decaying of the distributional sensitivities. • We propose a repeated stochastic gradient descent (RSGD) scheme and analyze its convergence towards the PSC solution. We show that the scheme is convergent under the same sufficient condition for the existence of the PSC solution. With an appropriate step size rule, the expected squared distance between the PSC solution and the iterates decays as O 1 N , where N is the iteration number.Finally, we conduct experiments on policy-dependent stock investment risk minimization problem. The numerical results validate the effectiveness of our algorithm and theoretical analysis.Performative Prediction. The notion of performative prediction is initiated by [21] , where performative stability is first introduced, and a sufficient and necessary condition is provided so that the performative stable point can be reached via iterative risk minimization algorithms. Since then, there has been a growing literature analyzing the performative prediction problem and studying the convergence of learning algorithms to the performative stable point [18, 5, 3, 13, 29] .There are also some other papers that find algorithms that converge to a stationary solution of the performative risk [12, 19, 25] . Our problem poses entirely new challenges because the decision-dependent data of system state and control costs also have decision-dependent temporal correlations. Such a twolayer decision-dependent structure cannot be incorporated into the existing performative prediction framework.There are some very recent works on performative reinforcement learning, where a Markov decision process (MDP) is considered and the deployed policy not only changes the costs but also the underlying state transition kernel [16, 24] . However, these works only considered the tabular MDP, where the state and action space are finite. The LDS considered in our work may also be viewed as a Markov decision process with a decision-dependent linear transition kernel and decision-dependent costs. But both the state and action space are continuous and there are infinitely many admissible state-action pairs, which are beyond the scopes of [16, 24] .Stateful Performative Prediction. Note that most of the existing performative prediction works [21, 18, 18, 5, 13, 29, 5, 3, 13, 29] are non-stateful in the sense that, for any deployed policy θ, the data sample Z follows a static distribution D (θ) , i.e., Z ∼ D (θ) . The seminal work [3] generalizes the stateless framework of [21] and proposes a more general framework of stateful performative prediction via a stateful distribution transition map f (•). Specifically, the observed data distribution in [3] is time-varying and depends on the history of previously deployed polices, i.e., D t+1 = f (D t , θ t ). Consequently, in comparison to the conventional non-stateful performative prediction works [21, 18, 18, 5, 13, 29, 5, 3, 13, 29] , this framework is capable of encapsulating the phenomenon of strategic decision-making with outdated information, and serves as a foundation for investigations of the disparate effects of performativity (please refer to Examples 1-3 in [3] for more details). The interconnections and generalizations between our work and the stateful performative prediction will be substantiated in Section 2.Nonstochastic Control. Another line of relevant works pertains to non-stochastic control, which is initiated by [1] . Various applications of non-stochastic control can be found in [10, 1, 11, 8] . At the core of non-stochastic control is the disturbance-action control policy, which chooses the action as a linear map of the past disturbances [11] . Such a disturbance-action policy facilitates efficient algorithms for control problems with arbitrary additive disturbances in the dynamics and arbitrary convex control costs instead of quadratic costs only. In this paper, we adopt the disturbance-action control policy for analysis. However, in contrast to [1, 10, 1, 11, 8] , where the system dynamics are static, our analysis involves policy-dependent nonstationary dynamics. 
motivations: 
 In this section, we discuss the key motivations for our performative linear control framework. We also outline the key connections and generalizations of our proposed framework to the stateful performative prediction framework of [3] .The LDS modeling via control theory in our work is closely aligned with the static stateful distribution maps within the state performative prediction framework [3] . Let us first consider a static stateful distribution transition map f (•) with D t+1 = f (D t , θ t ) , ∀t ≥ 0. To facilitate the analysis, we use a performative data sample Z t ∼ D t to equivalently characterize the performative distribution D t . If the properties of f (•) are nice enough, then from the perspective of random variables, there will exist a corresponding mapping f (•) such thatEQUATIONwhere d = denotes equal in distribution. Linearizing f (•) at some equilibrium point Z, θ with Z ∼ D and ignoring the higher order terms will lead toEQUATIONwhereA = ∂ f ∂d (d,θ) and B = ∂ f ∂θ (d,θ)are the static Jacobin matrices at the equilibrium point d, θ and w = f Z, θ -AZ -Bθ. Consider the performative data sample Z t , the deployed policy θ t and the residual w in (2) as the state variable x t , the control input action u t and the additive system noise w t ∼ w of an LDS, respectively. The linearized static stateful distribution map model in ( 2) is thus precisely connected to a LDS with system dynamics given byEQUATIONExtension to Performative Stateful Distribution Transition Maps via Performative LDS. Further consider a more complicated case of performative distribution transition maps f θt (•) with D t+1 = f θt (D t , θ t ) , ∀t ≥ 0, where the specific form of the distribution transition map f θt is time-varying and depends on the delployed policy θ t . Employing a similar linearization for f θt (•) and neglecting the higher order terms, we obtainEQUATIONwhereA θt = ∂ f θ t ∂d (d,θ) and B θt = ∂ f θ t ∂θ (d,θ)are the performative Jacobin matrices, andw t = f θt Z, θ -A θt Z -B θt θ.This results in an equivalent performative LDS given byEQUATIONIn contrast to (3), where the system dyanmics are static, the state transition matrix A ut , control input gain matrix B ut and additive noise w ut in (5) are all performative and depend on the deployed control policy u t .In conclusion, the LDS modeling presented in our paper allows for the performative transition maps of performative distributions, thereby extending the technical results previously obtained for fixed performative distribution transition maps in the stateful performative prediction work [3] . As a result, our proposed performative LDS framework has the potential to enhance the understanding of general performative prediction. 
problem setup: 
 We consider the control of a linear dynamic system with per stage cost c t (x t , u t ). A control policy π is a mapping π : R dx×1 → R du×1 , which maps the system state x t to the control action u t , i.e., u t = π (x t ). For each control policy π, we attribute a finite time horizon expected cost defined asEQUATIONwhere x t+1 = A t x t + Bu t + w t , the initial system state x 0 follows a general distribution of D x0 with bounded support ∥x 0 ∥ ≤ x 0 , and E x0,{At},{wt} represents the expectation over x 0 , the entire policy-dependent state transition matrix sequence {A t , 1 ≤ t ≤ T } and the entire disturbance sequence {w t , 1 ≤ t < T }.To the best of our knowledge, this paper is the very first work to investigate the performative LDS, and we intend to provide a thorough theoretical investigation and aim at establishing various new theoretical results. Therefore, we opt to construct our performative LDS theoretical framework upon the performative state transition matrix A t , while maintaining the control input gain matrix B and additive disturbance w t as non-performative. This facilitates us to streamline the theoretical analysis and consolidates the system design insights.We have the following assumption on the additive disturbances {w t , 1 ≤ t ≤ T } .The additive disturbance per time step w t is bounded, i.i.d, and zero-mean with a lower bounded covariance i.e.,w t ∼ D w , E[w t ] = 0, E[w t w ⊤ t ] ⪰ σ 2 I, ∥w t ∥ ≤ W, ∀0 ≤ t < T , and E[w t1 w ⊤ t2 ] = 0, ∀0 ≤ t 1 ̸ = t 2 < T .Disturbance-Action Control Policy. We work with the following class of disturbance-action control policy throughout this paper, which is commonly used in nonstochastic control [10, 1, 11, 8] to address general convex control cost functions.Definition 1 (Disturbance-Action Policy). For a disturbance-action control policy, the mapping π, ∀0 ≤ t < T , is uniquely characterized by a set of matrices M (1) , • • • , M (H) . At every time step t, such a disturbance-action control policy assigns a control action uEQUATIONwhere M = M (1) , M (2) ,• • • , M (H) belongs to a convex set M with bounded support ∥M∥ F ≤ M , [w] H t-1 is short for w ⊤ t-1 , • • • w ⊤ t-1-H⊤ , H < T is a constant and w i = 0 for all i < 0.In the disturbance-action policy (7) , we adopt a class of linear controller K defined as follows.Definition 2 (Strongly Stabilizing Linear Controller [1, 10, 11, 8] ). Given A and B, a linear controller K is (κ, γ) almost surely strongly stable for real numbers κ ≥ 1, γ < 1, if ∥K∥ ≤ κ, and there exists matrices Q and L such thatA := A -BK := QLQ -1 , with ∥L∥ ≤ 1 -γ and ∥Q∥, Q -1 ≤ κ.It is worth noting that the disturbance-action policy is only parameterized by the matrix M. Whereas the state feedback gain K, which is a fixed matrix, is not part of the parameterization of the policy. As pointed out in [2] , a typical choice of the parameter H is H = γ -1 log(T κ 2 ). With an appropriate choice of the policy M, the control action u (M) t in ( 7) is capable of approximating any linear state feedback control policy in terms of the total cost suffered with a finite time horizon of H [10, 1, 11, 8] .Policy-dependent Dynamics. Without loss of generality, at any time step t, the impact of the disturbance-action control policy u (M) t to the dynamics of the linear system is modeled as a policydependent additive perturbation ∆ t to a common state transition matrix A.). The disturbance-action policy-dependent state transition matrix A t takes the form ofEQUATION)where Remark 2 (Policy-dependent Control Input Gain Matrix B). Note that under the DAP (7), the disturbance-action is given by BM[w] H t-1 , which is linear in policy M. Such kind of linear disturbance-action control policy has various nice theoretical performance guarantees as substantiated in [10, 1, 11, 8] . On the other hand, if B is also performative, we will have a generalized disturbance-action B t (M)M[w] H t-1 , which can be possibly nonlinear in policy M. Such kind of generalized nonlinear disturbance-action control policy has received very few research attention, and it can serve as a very interesting future research direction.AWe make the following sensitivity assumption on the distributions {D t (M) , 0 ≤ t < T } .EQUATIONwhere W 1 (D, D ′ ) denotes the Wasserstein-1 distance between the distributions D and D ′ .Assumption A3 imposes a regularity requirement on the distributions {D t (M) , 0 ≤ t < T } . Intuitively, if the disturbance-action control policies are made according to similar policy parameterizations M, then the resulting distributions of the policy-dependent state transition perturbations should also be similar.System State Evolutions. Under the disturbance-action policy (7) , the following lemma shows that the system state x t , ∀1 ≤ t ≤ T, can be uniquely determined by x 0 , A, M, {∆ t , 0 ≤ t < T } and {w t , -H ≤ t < T } .Lemma 1 Given a disturbance-action policy M, the system state x t , ∀1 ≤ t ≤ T , can be represented asEQUATION+ t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I w i .Besides, let the K in DAP (7) be a strongly stabilizing linear controller, the norm of x t is upper bounded as∥x t ∥ ≤ x 0 κ 2 α t + κ 2 W (∥B∥ HM + 1) β t , where α t = t-1 i=0 1 -γ + κ 2 ξ i and β t = t-1 i=0 t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t .The performative optimal control (POC) problem can therefore be formulated as:EQUATION)The POC problem (11) comprises of a stochastic objective function with policy-dependent distributions. Due to non-convexity, the performative optimal solution M P O to (11) is usually difficult to obtain. Alternatively, in this paper, we are interested in the performative stable control (PSC) solution:EQUATIONNotice that M P S is defined to be a fixed point of the map Φ. Compared to the POC (11), the distribution of ∆ t in PSC (12) changes from ∆ t ∼ D t (M) to ∆ t ∼ D t M P S , ∀0 ≤ t < T. The existence and uniqueness of M P S will be dicsussed in Lemma 4.Comparison to Existing Works. Most of the existing performative prediction works [21, 13, 14, 5, 3, 18, 29, 25, 12, 19, 25] consider the cost in the form of l (θ; Z) , where θ is the decision variable. Then the relationship between data samples Z and decision θ is parameterized by a fixed distribution Z ∼ D (θ) with fixed sensitivity ε. However, in our work, the relationship between system state data samples x t and policy M is characterized by a time-varying distributionx t ∼ f t (D 0 (M) , • • • , D t-1 (M)) with a time-varying sequence of joint sensitivities {ε 0 , • • • , ε t } , ∀0 ≤ t < T . The total cost T t=0 c t depends on all the policy-dependent distributions{D 0 (M) , • • • , D T -1 (M)} with a collection of sensitivities {ε 0 , • • • , ε T -1 }.These key differences lead to a more complicated analysis in our work.RSGD Scheme. We propose a repeated stochastic gradient descent (RSGD) scheme in Algorithm 1 to find a PSC solution to (12) . The metric of the projection in line 9 of Algorithm 1 is theAlgorithm 1 Repeated Stochastic Gradient Descent (RSGD) Input: Step sizes {η n , 0 ≤ n ≤ N }, parameters K, H. Define M = {M : ∥M∥ ≤ M } . Initialize M 0 ∈ M arbitrarily. 1: for n = 0, • • • , N, do 2:Initialize ∇J T = 0.3:for t = 0, • • • , T -1, do 4: Use control u t = -Kx t + M n [w] H t-1 .Observe A t , x t+1 ; compute noise w t = x t+1 -A t x t -Bu t .Compute the gradient ∇ Mn c t (x t , u t ) and update ∇J T ← ∇J T + ∇ Mn c t (x t , u t ) .end for8: Update M n+1 ← Proj M {M n -η n ∇J T }. 9: end for matrix Frobenius norm. Specifically, Proj M {M} = arg min M ′ ∈M ∥M -M ′ ∥ 2 F. Note that such a projection is computationally tractable because the Frobenius norm square minimization is a convex optimization problem. The RSGD scheme first computes the stochastic gradient of the total cost w.r.t. policy T t=0 ∇ Mn c t (x t , u t ) and then perform stochastic gradient descent on M. The detailed steps for computation of the stochastic gradient ∇ Mn c t (x t , u t ) are provided in Appendix B. 
main results: 
 This section investigates the existence of a PSC solution M P S to ( 12) and the convergence of the RSGD scheme to M P S . We require the following assumptions on the per stage cost c t [1, 10, 1, 11, 8] .A4 (Strongly Convex). The per stage cost function c t (x, u) is µ-strongly convex such that c t (x 1 , u 1 ) ≥ c t (x 2 , u 2 ) + ∇ ⊤ x c t (x 2 , u 2 ) (x 1 -x 2 ) + ∇ ⊤ u c t (x 2 , u 2 ) (u 1 -u 2 ) + µ 2 ∥x 1 -x 2 ∥ 2 + ∥u 1 -u 2 ∥ 2 , ∀x 1 , x 2 ∈ R dx , u 1 , u 2 ∈ R du .A5 (Smoothness). The per stage cost functionc t (x, u) is ς smooth such that ∥∇ x c t (x 1 , u 1 ) -∇ x c t (x 2 , u 1 )∥ + ∥∇ u c t (x 1 , u 1 ) -∇ u c t (x 1 , u 2 )∥ ≤ ς (∥x 1 -x 2 ∥ + ∥u 1 -u 2 ∥) , ∀x 1 , x 2 ∈ R dx , u 1 , u 2 ∈ R du .A6 (Boundedness). There exists a positive constant G such that∥∇ x c t (x, u)∥ , ∥∇ u c t (x, u)∥ ≤ GD, ∀ ∥x∥ , ∥u∥ ≤ D.The above Assumptions A4-A6 on the per stage cost function c t (x, u) are quite standard, which hold for broad classes of costs such as the quadratic costs.To facilitate our discussions, we define an expected total cost with distribution shift asC T (M; M ′ ) := E x0,{∆t∼Dt(M ′ )},{wt} T t=0 c t x (M) t , u (M) t ,where, under policy M, the distribution of policy-dependent perturbation is changed from∆ t ∼ D t (M) to ∆ t ∼ D t (M ′ ), ∀0 ≤ t < T.For the rest of this paper, unless otherwisespecified, ∇C T (M; M ′ ) denote the gradients taken w.r.t. the first argument M.Our main results rely on the strong convexity of the expected total cost C T (M; M ′ ) with respect to its first argument M. However, the strong convexity of the per stage cost function c t (x, u) over the state-action space in Assumption A4 does not by itself imply the strong convexity of the expected total cost C T (M; M ′ ) over the space of policies M. This is becasue the policy M, which maps from a space of dimensionality H × d x × d u to that of d x + d u , is not necessarily full column-rank. Our next lemma, which forms the core of our analysis, shows that this is not the case using the inherent stochastic nature of the policy-dependent dynamics.Lemma 2 Under A1-A6, fix anyEQUATIONwhereµ = min (T -H+1)µσ 2 2 , (T -H+1)µσ 2 γ 2 64κ 10.For a concise presentation of the smoothness of expected total control cost, we next define a collection of constants as follows:c 1 := d x ςH 3 2 W 1 + κ 2 + κ 3 ∥B∥ κ 2 + κ 3 (1 -γ) -1 , c 2 := d x H 3 2 W G (1 -γ) -1 κ 4 + κ 5 ∥B∥ , c 3 := (HM ∥B∥ + 1) W, c 4 := HW (1 -γ) c 1 , c 5 := HW κ 2 + κ 3 -1 (1 -γ) c 1 .The smoothness of the expected total cost C T (M; M ′ ) is summarized below.Lemma 3 Under A1-A6, the expected total cost C T is smooth in the sense that, for any M, M ′ , M 1 , M 2 ∈ M and ∀1 ≤ t ≤ T, the following inequality holdsEQUATIONwhereλ t = c 1 (c 4 β t + c 5 ) , ν t = (c 1 + c 2 β t ) (x 0 α t + c 3 β t ) , ∀1 ≤ t ≤ T,and we recall thatα t = t-1 i=0 1 -γ + κ 2 ξ i and β t = t-1 i=0 t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t from Lemma 1, which characterize the growth of the norm of system state ∥x t ∥ .Existence and Uniqueness of M P S . Our first main result establishes a sufficient condition for the existence and uniqueness of the performative stable policy M P S that solves the PSC problem (12) .Lemma 4 Under A1-A6, consider the fixed-point iterationEQUATIONwhere the map Φ is defined in (12) . If the following condition is satisfiedEQUATIONthen iterates M n converge to a unique performatively stable point M P S at a linear rate, i.e.,M n -M P S F ≤ ρ for n ≥   1 - T -1 t=0 ε t T i=t+1 ν i µ   -1 log 1 ρ M 0 -M P S F .The sufficient condition ( 16) delivers a fact that that the existence and uniqueness of M P S is jointly determined by all the sensitivities {ε t , 0 ≤ t < T } in the temporal domain. The sensitivity ε t at the t-th time step is propagated starting from time step t + 1 to the last time step T with a sequence of weights {ν t+1 , • • • , ν T }. The aggregated impact of all the policy-dependent disturbances {∆ t , 0 ≤ t < T } is captured by total sum in L.H.S. of ( 16). This is very different from the existing performative prediction works [21, 18, 5, 3, 13, 29, 12, 19, 25] , where only one distribution D and one sensitivity ε are involved.The sufficient condition ( 16) also implies that it is preferable for the initial policy-dependent disturbance ∆ 0 to be small because it propagates and aggregates for the longest time steps of T .Impacts of System Stability. The sufficient condition ( 16) also reveals the impacts of system stability on the existence and uniqueness of the performative stable solution M P S , which are summarized below.Proposition 1 (Almost Surely Strongly Stable Case) Let A1-A6 hold. If policy-dependent state transition matrixA t is κ, γ -κ 2 ξ t -strongly stable for real numbers κ ≥ 1, γ -κ 2 ξ t < 1, ∀0 ≤ t < T , almost surely. Let ζ = max 1 -γ + κ 2 ξ t , ∀0 ≤ t < T , then M P S exists and is unique if T -1 t=0 ε t < ϕ 1 -H T µ, where µ = min µσ 2 2 , µσ 2 γ 2 64κ 10and ϕ is some positive constant.Proposition 1 points out that when the policy-dependent dynamics are almost surely strongly stable, we only need to make sure that the sum of all the sensitivities {ε t , 0 ≤ t < T } is below a certain threshold.Proposition 2 (Almost Surely Unstable Case) Let A1-A6 hold. If the policy-dependent state transition matrix A t is almost surely unstable, i.e., there exists a positive constantζ > 1 such that ζ ≤ ∥A t ∥ ≤ 1 -γ + κ 2 ξ t , ∀0 ≤ t < T.In this case, to guarantee the sufficient condition ( 16) can be satifised, we must haveε t < ϕ(T -H+1)µ ζ T -t -1, ∀0 ≤ t < T, where ϕ is some positive constant.For unstable policy-dependent dynamics, condition (16) will impose a necessary requirement on the temporally backwards decaying of the sensitivities. Particularly, more restrictive requirements are placed on the the sensitivies in the early time steps, i.e., smallt, which should decay exponentially fast w.r.t. the control time horzion T .For more general applications, where A t can be either stable or unstable for different time steps, the weighted sum requirement of the sensitivities {ε t , 0 ≤ t < T } in ( 16) is sufficient to guarantee the existence and uniqueness of the performative stable solution M P S .Convergence of RSGD Scheme. Our next theorem establishes the convergence rate of the proposed RSGD algorithm.Theorem 1 Choose two positive constants ϕ 1 > 0 and ϕ 2 ≥ 1 such that the following two conditions are satisfied simualtneouslyEQUATIONEQUATION)Consider a sequence of non-negative step sizes η n = ϕ1 n+ϕ2 , n ≥ 0 . Then, the iterates generated by RSGD admit the following bound for any N ≥ 1:EQUATIONwhereϑ t = κ 3 G HW + κ 2 κ ∥B∥ β t + 1 (x 0 α t + c 3 β t ) + GHW M κ 3 β t + 1 , ∀1 ≤ t ≤ T, and ϕ 3 = 4ϕ1T T t=1 ϑ 2 t µ-T -1 t=0 (εt T i=t+1 νi) is a positive constant.Note that, under the sufficient condition (16) in Lemma 4, there always exists a pair of (ϕ 1 , ϕ 2 ) that satisfies (17) and (18) simultaneously by letting ϕ 2 be sufficiently large. The first term on the R. H. S. of (19) decays at the rate of O(e-N n=1 ϕ 1 n ( µ-T -1 t=0 (εt T i=t+1 νi))) and is scaled by the initial errorE M 0 -M P S 2 F .The second term is a fluctuation term that only depends on the variance of the stochastic gradient, which decays at the rate O (1/N ). For more general types of step sizes and the associated nonasymptotic convergence rate analysis, please refer to Lemma 5 in the appendix G.1.  
numerical experiments: 
 We consider an application of stock investment risk minimization problem to verify our algorithm and theoretical results. Consider an investor trading a total number of 10 stocks over a period of T = 60 trading days. The detailed system setups are described in Example 1 in Appendix A of the supplementary. We compare the performative error (PS error) M N -M P S 2 F and the expected total cost C T (M N ; M N ) against the iteration number N , respectively. We consider a fixed distributional sensitivity value set ε = {ε i , i = 0, 1, . . . , T -1}. We assign three different patterns of the sensitivity sequence as ε d = descend (ε), ε a = ascend (ε) and ε r = random (ε) in descending, ascending, and random order, respectively, over the time steps. We first observe from Figure 1 (left) and Figure 2 (left) that when the policy-dependent system dynamics A t , ∀0 ≤ t < T, are almost surely strongly stable, the gap M N -M P S 2 F of three different patterns ε d , ε a and ε r all decay at O 1 N as N → ∞, and the expected total control cost also converges. These coincide exactly with Proposition 1 and Theorem 1, where the existence of M P S only requires that the sum of the distributional sensitivities T -1 t=0 ε t is small enough, and the temporal order of each ε t is negligible. We next observe from Figure 1 (middle) and Figure 2 (middle), that when the A t , ∀0 ≤ t < T, are almost surely unstable, the iterates M n of both ε d and ε r diverge. The expected total control costs associated with ε d and ε r are significantly larger than that of ε a . This is because large initial distributional sensitivities in ε d and ε r rule out the existence of M P S , which matches Proposition 2. For the general case of A t in Figure 1 (right) and Figure 2 (right), all three cases converge due to the relatively mild sufficient condition (16) .In this work, we have introduced the framework of performative control and studied the conditions under which a PSC policy exists. We have analyzed the impact of system stability on the existence of the PSC policy, and proposed a condition on the sum of the distributional sensitivities and the temporally backwards decaying of sensitivities for almost surely strongly stable and almost surely unstable systems, respectively. We have also proposed an RSGD algorithm that converges to the PSC policy in a mean-square sense. The extension of our current results to general control policies and general control costs [cf. A4], will be explored in future work.In this section, we elaborate a concrete example of stock market risk minimization to justify the policy-dependent state transition model in (8) . We also conduct numerical experiment based on this example to demonstrate the efficacy of our developed theory.Example 1 (Stock Market Risk Minimization). We describe a risk minimization problem for stock market investment to illustrate the application of (11) . Consider an investor trading a total number of L stocks over a period of T trading days. The observed market price s (l) t of the n-th stock at the t-th day follows a stochastic volatility model of log s(l) t+1 = log s (l) t + r-1 2 v (l) t 2 T + v (l) t √ T , s (l) 1 > 0, ∀1 ≤ t < T, 1 ≤ l ≤ L, where r > 0 is the riskless interest rate per day, v (l)t and s (l) 1 are the unobservable independent random volatility process and the constant initial stock price associated with the l-th stock, respectively [22, 27] . Let q (l) t and q (l) 1 be the the total return at the t-th day before the market opens and the initial investment associated with the l-th stock, respectively. The investor maintains a portfolio for each q (l) t , which is parameterized by a row vectorm (l) = m l,1 , • • • , m l,M with m l,i ∈ [0, 1] , ∀1 ≤ i ≤ L,being the weight of allocation and L i=1 m l,i = 1. Specifically, at the t-th day when the market opens, the investor immediately allocates q (l) t proportionally to buy the N stocks according to the weight vector m (l) . The total systemic risk associated with q l t during the period between the t-th day right before market opening and the (t + 1)-th day right before market opening isL i=1 m l,i w (i) t h + 1 • w (l)t+1 (24 -h) , where w i t is the per hour risk associated with the i-th stock in the t-th day and h is the total number of trading hours per day. isL i=1 m l,i e r -1 2 v (i) t 2 1 T + v (i) t 1 √ T q l t .The investor then spends all this amount to buy back the l-th stock and then the t-th trading day ends. Each stock in the portfolio suffers from a proportionate random i.i.d. systemic risk w i t per hour, i.e., holding the i-th stock with a ratio of m l,i in a portfolio for a total number of h trading hours in the t-th day will incur a systemic risk of m l,i w (i) t h. Denote the mean-shifted return as r t = q t -E [q t ] and let x t = r t q t. It follows that the evolution of x t can be characterized by the canonical form ofEQUATIONEQUATION)whereM = h 24-h m (1) ; • • • ; m (L) , w t-1 = (24 -h) w (1) t , • • • , w (L) t T , w t = w t -E [w t ] w t, the state transition matrix A = I 2L×2L and the policy-dependent state transition perturbation ∆ t is given by ( 22) and (23) .EQUATIONEQUATION)The investment risk minimization problem can thus be casted asEQUATION.Tackling (11) leads to an optimized stock investment policy M which takes the effects of policydependent random perturbations to the dynamics of stock returns into account.In the simulation, we set the number of stocks L = 10 and the number of trading days T = 60.The initial policy M 0 is randomly chosen within the feasible set M = {M : 10 i=1 m l,i = 1, ∀1 ≤ l ≤ 10}. The entries of noise term w t are independently and uniformly drawn from the interval [0, 1]. For each 1 ≤ i ≤ 10 and each 0 ≤ t < 60, we first obtain ṽ(i) t by sampling from a Gaussian distribution, i.e., ṽ(i) t ∼ N (log(ε t ), 0.2), where ε t denotes the sensitivity at t-th trading day. The ṽ(i) t is then projected to the interval [-0.6, 0.6] to obtain v(i)t in (23) . We let the total number iterations N = 1000, and the stepsize η n in Algorithm 1 is set to be 0.01, ∀0 ≤ n ≤ 1000.The non-ordered lists of sensitivity values in epsilon ε a ,ε d , and ε r are the same. The state trajectory x t and control action u t are generated according to (20)-( 23) based on the above system parameter configurations.In this part, we provide several lemmas to characterize the gradient properties and the smoothness of the per stage cost c t . We first summarize a collection of notations. We denote under any given realization of the policy-dependent state transition perturbations {∆ i , 0 ≤ i < t} .EQUATIONBased on the chain rule and the relationship between M and the pair (x t , u t ) in ( 7) and (10) , theexpression of ∇ M c t x (M) t , u (M) t is given by ∇ M c t x (M) t , u (M) t (24) = t-1 i=0   t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B   ⊤ ∇ x c t x (M) t , u (M) t [w] H i-1 ⊤ - t-1 i=0        K t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B   ⊤ ∇ u c t x (M) t , u (M) t [w] H i-1 ⊤      + ∇ u c t x (M) t , u (M) t [w] H t-1 ⊤ .For the ease of notation, without ambiguity we also occasionally use the notationc t M; {∆ i } 0≤i<t to denote c t x (M) t , u (M) tunder a sequence of policy-dependent state transition perturbations {∆ i , 0 ≤ i < t} . In this case, ∇ M c t M; {∆ i } 0≤i<t denote the gradient taken w.r.t. the first argument M.Moreover, the total cost function can be represented asEQUATIONIt is clear thatEQUATIONUnless otherwise specified, ∇J T M; {∆ t } 0≤t<T and ∇C T (M; M ′ ) denotes the gradient taken w.r.t. the first argument M.Convexity. Denote the per stage expected costf t (M; M 1 ) = E x0,{∆i∼Di(M1)} 0≤i<t ,{wi} 0≤i<t c t M; {∆ i } 0≤i<t , ∀1 ≤ t ≤ T,where the distribution of policy-dependent perturbation is changed from∆ i ∼ D i (M) to ∆ i ∼ D i (M 1 ), ∀0 ≤ i < t.We have the following lemma characterizing the convexity of f t (M; M 1 ) , ∀1 ≤ t ≤ T.Lemma B.1 The per stage expected cost f t (M; M ′ ) is a convex function of M, ∀M, M ′ ∈ M, ∀1 ≤ t ≤ T .Proof. We prove this lemma following the convex property of the function c t (x, u) in Assumption A 4. Let 0 < θ < 1 and M 1 , M 2 , M ′ ∈ M. Consder the weighted policyEQUATION• (θM 1 + (1 -θ) M 2 ) M [w] H i-1 + t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I w i = θ   t-1 i=0 A + ∆ i x 0 + t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I BM 1 [w] H i-1 + t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I w i   + (1 -θ) •   t-1 i=0 A + ∆ i x 0 + t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I BM 2 [w] H i-1 + t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I w i   = θx M1 t + (1 -θ) x M2 t .As a result,EQUATION= E x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t c t x (M1+(1-θ)M2) t , u (M1+(1-θ)M2) t = E x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t c t θx M1 t + (1 -θ) x M2 t , θu M1 t + (1 -θ) u M2 t (28.a) ≤ E x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t θc t x M1 t , u M1 t + (1 -θ) c t x M2 t , u M2 t = θf t (M 1 ; M ′ ) + (1 -θ) f t (M 2 ; M ′ ) ,where inequality (28.a) holds becasue of the convexity of c t (x, u). □We next have a key lemma characterizing the strong convexity of f t (M; M ′ ) , ∀H ≤ t ≤ T.The per stage expected costf t (M; M ′ ) is a min µ 2 , µσ 2 γ 2 64κ 10 -strongly convex function of M, ∀M, M ′ ∈ M, ∀H ≤ t ≤ T .Proof. We prove this lemma following the strong convexity of the functionc t (x, u) in Assumption A 4. Let M 1 , M 2 , M ′ ∈ M. Consider a time step t such that H ≤ t ≤ T. For any given realizations of {∆ i } 0≤i<t , where ∆ i ∼ D i (M ′ ) , ∀0 ≤ i < t, we have c t x (M1) t , u (M1) t -c t x (M2) t , u (M2) t (29) (29.a) ≥   ∇ x c t x (M2) t , u (M2) t ∇ u c t x (M2) t , u (M2) t   T x (M1) t -x (M2) t u (M1) t -u (M2) t + µ 2 x (M1) t -x (M2) t u (M1) t -u (M2) t 2 ,where inequality (29.a) holds because of the strong convexity assumption of c t in Assumption A4.Based on the representations of the pair (x t , u t ) in ( 7) and (10) , it follows thatEQUATIONEQUATION+ (M 1 -M 2 ) [w] H t-1 .Therefore, we obtainEQUATION) = t-1 i=0 ∇ ⊤ x c t x (M2) t , u (M2) t   t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B (M 1 -M 2 ) [w] H i-1   + t-1 i=0 ∇ ⊤ u c t x (M2) t , u (M2) t   -K t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B (M 1 -M 2 ) [w] H i-1 + (M 1 -M 2 ) [w] H t-1 = Tr     t-1 i=0 [w] H i-1 ∇ ⊤ x c t x (M2) t , u (M2) t t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B   (M 1 -M 2 )   + Tr     - t-1 i=0 [w] H i-1 ∇ ⊤ u c t x (M2) t , u (M2) t K t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B + [w] H t-1 ∇ ⊤ u c t x (M2) t , u (M2) t (M 1 -M 2 ) = Tr ∇ ⊤ M2 c t x (M2) t , u (M2) t (M 1 -M 2 ) .Substitute (32) back into (29), we havec t x (M1) t , u (M1) t -c t x (M2) t , u (M2) t ≥Tr ∇ ⊤ M2 c t x (M2) t , u (M2) t (M 1 -M 2 ) (33) + µ 2 x (M1) t -x (M2) t 2 + u (M1) t -u (M2) t 2 .Taking full expectation on both sides of (33), it followsf t (M 1 ; M ′ ) -f t (M 1 ; M ′ ) ≥ Tr ∇ ⊤ f t (M 2 ; M ′ ) • (M 1 -M 2 ) (34) + µ 2 E x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t x (M1) t -x (M2) t 2 + u (M1) t -u (M2) t 2 .We next analyze the last term in (34). Consider the conditional expectation on {w i } 0≤i<t as followsE x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t x (M1) t -x (M2) t 2 + u (M1) t -u (M2) t 2 (35) = E {wi} 0≤i<t E x0,{∆i∼Di(M ′ )} 0≤i<t x (M1) t -x (M2) t 2 + u (M1) t -u (M2) t 2 {w i } 0≤i<t ≥ E {wi} 0≤i<t E x0,{∆i∼Di(M ′ )} 0≤i<t x (M1) t -x (M2) t {w i } 0≤i<t 2 + E x0,{∆i∼Di(M ′ )} 0≤i<t u (M1) t -u (M2) t {w i } 0≤i<t 2 (35.a) = E {wi} 0≤i<t   t-1 i=0 A i B (M 1 -M 2 ) [w] H i-1 2 + K t-1 i=0 A i B (M 1 -M 2 ) [w] H i-1 -(M 1 -M 2 ) [w] H t-1 2   ,where (35.a) holds becasue E [∆ t ]=0, ∀0 ≤ t < T.We next consider each term on R.H.S. of (35.a) . We notice thatvec t-1 i=0 A i B (M 1 -M 2 ) [w] H i-1 = t-1 i=0 [w] H i-1 ⊤ ⊗ A i B vec (M 1 -M 2 ) (36)Therefore,E {wi} 0≤i<t   t-1 i=0 A i B (M 1 -M 2 ) [w] H i-1 2   (37) = δ ⊤ M E {wi} 0≤i<t   t-1 i=0 [w] H i-1 ⊤ ⊗ A i B ⊤ t-1 i=0 [w] H i-1 ⊤ ⊗ A i B   δ M = δ ⊤ M t i1=1 t i2=1 Λ i1-i2 ⊗ A i1-1 B ⊤ A i2-1 B ⊗ E w t w ⊤ t δ M = δ ⊤ M I H ⊗ B ⊤ Ψ (I H ⊗ B) ⊗ E w t w ⊤ t δ M ,where δ M = vec (M 1 -M 2 ), Λ t ∈ R H×H with [Λ l ] i,j = 1 if and only if i -j = l and 0 otherwise andΨ = t i1=1 t i2=1 Λ i1-i2 ⊗ A i1-1 B ⊤ A i2-1 B .Using similar approach, we can obtainE {wi} 0≤i<t   K t-1 i=0 A i B (M 1 -M 2 ) [w] H i-1 -(M 1 -M 2 ) [w] H t-1 2   (38) = δ ⊤ M I H ⊗ B ⊤ Ψ I H ⊗ B ⊤ -Θ (I H ⊗ B) -I H ⊗ B ⊤ Θ ⊤ + I Hdu ⊗ E w t w ⊤ t δ M , where Ψ = t i1=1 t i2=1 Λ i1-i2 ⊗ K A i1-1 B ⊤ K A i2-1 B and Θ = (I H ⊗ K) ⊗ t i=1 Λ -i ⊗ A i-1 BSubstitue (38) and (37) back into (35), it follows thatE x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t x (M1) t -x (M2) t 2 + u (M1) t -u (M2) t 2 (39) = δ ⊤ M Ω ⊗ E w t w ⊤ t δ M .whereΩ = I H ⊗ B ⊤ Ψ (I H ⊗ B) + I H ⊗ B ⊤ Ψ I H ⊗ B ⊤ (40) -Θ (I H ⊗ B) -I H ⊗ B ⊤ Θ ⊤ + I Hdu .Based on Lemma F.1 and F.2 in [2] , we have, ∀H ≤ t ≤ T, Ψ ≥ 1 4κ 4 I Hdx and ∥Θ∥ ≤ γ -1 κ 3 . Therefore, if ∥I H ⊗ B∥ ≥ γ 4κ 3 , thenEQUATIONEQUATION)Combine ( 41) and (43), we have ∥Ω∥ ≥ min 1 2 , γ 2 64κ 10 . As a result,E x0,{∆i∼Di(M ′ )} 0≤i<t ,{wi} 0≤i<t x (M1) t -x (M2) t 2 + u (M1) t -u (M2) t 2 (44) = δ ⊤ M Ω ⊗ E w t w ⊤ t δ M ≥ δ M ∥Ω∥ σ 2 ≥ min σ 2 2 , γ 2 σ 2 64κ 10 ∥M 1 -M 2 ∥ 2 F .Substitue (44) back into (34), it follows thatEQUATION+ min µσ 2 2 , µγ 2 σ 2 64κ 10 2 ∥M 1 -M 2 ∥ 2 F .Therefore , uEQUATIONEQUATIONwhereα t = t-1 i=0 1 -γ + κ 2 ξ i and β t = t-1 i=0 t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t .Proof. We first provide upper bounds for ∥x t ∥ and ∥u t ∥ . From the evolution of x t in (10), we obtain EQUATIONE x0,{∆i∼Di(M)} 0≤i<t ,{wi} 0≤i<t ∇ M c t x (M) t , u (M) t (50) -E x0,{∆i∼Di(M)} 0≤i<t ,{wi} 0≤i<t ∇ M c t x (M) t , u (M) t 2 F ≤ ϑ t .Proof. Based on the expression of∇ M c t x (M) t , u (M) tin (24) , we have Further note thatEQUATIONE ∇ M c t x (M) t , u (M) t -E ∇ M c t x (M) t , u (M) t 2 F ≤ E ∇ M c t x (M) t , u (M) t 2 F (52) ≤ d 2 x HE ∇ M c t x (M) t , u (M) t 2The desired result follows by substituting (51) into (52) and lettingEQUATION+ κ 3 ∥B∥ β t + 1 GM HW .The next lemma characterizes the difference between the gradients under any two different polices M and M ′ .Lemma B.5 For any given two policies M, M ′ ∈ M, the differences between the gradients satify, ∀1 ≤ t ≤ T,∇ x c t x (M) t , u (M) t -∇ x c t x (M ′ ) t , u (M ′ ) t + ∇ u c t x (M) t , u (M) t -∇ u c t x (M ′ ) t , u (M ′ ) t (54) ≤ ς (1 + κ) κ 2 HW β t + HW ∥M -M ′ ∥ + ς (1 + κ) κ 2 (1 -γ) -1 (x 0 α t + (∥B∥ HM + 1) W β t ) t-1 i=0 ∥∆ i -∆ ′ i ∥ ,where ∆ i and ∆ ′ i , ∀0 ≤ i < t, denotes the policy-dependent state transition perturbations under the policy M and M ′ , respectively.Proof. Recall the smoothness of the cost function c t (x, u) in A 5, i.e.,∥∇ x c t (x 1 , u 1 ) -∇ x c t (x 2 , u 2 )∥ + ∥∇ u c t (x 1 , u 1 ) -∇ u c t (x 2 , u 2 )∥ (55) ≤ ς (∥x 1 -x 2 ∥ + ∥u 1 -u 2 ∥) .To prove Lemma B.5, it suffices to quantify x(M) t -x (M ′ ) t and u (M) t -u (M ′ ) t .Based on the evolution of the system state x (M) t, we haveEQUATIONwhereEQUATIONEQUATION)We next analyze each term in (56) one by one. Specifically,∥E 1 ∥ ≤ x 0 t-1 i=0 A + ∆ i - t-1 i=0 A + ∆ ′ i (60) ≤ x 0 (∆ 0 -∆ ′ 0 ) t-1 i=1 A + ∆ i + A + ∆ ′ 0 (∆ 1 -∆ ′ 1 ) t-1 i=2 A + ∆ i + • • • + t-2 i=0 A + ∆ ′ i ∆ t-1 -∆ ′ t-1 ≤ x 0 κ 2 (1 -γ) -1 t-1 i=0 1 -γ + κ 2 ξ i t-1 i=0 ∥∆ i -∆ ′ i ∥ = x 0 κ 2 (1 -γ) -1 α t t-1 i=0 ∥∆ i -∆ ′ i ∥ .For the term E 2 , we use the similar approach for analyzing E 1 in (74) and obtain the following bound∥E 2 ∥ (61) ≤ t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B (M -M ′ ) [w] H i-1 + t-1 i=0   t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I - t-1 j=i+1 1 j<t A + ∆ ′ j + 1 j=t I   BM ′ [w] H i-1 ≤ κ 2 HW β t ∥M -M ′ ∥ + ∥B∥ M HW t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I - t-1 j=i+1 1 j<t A + ∆ ′ j + 1 j=t I (61.a) ≤ κ 2 HW β t ∥M -M ′ ∥ + κ 2 (1 -γ) -1 ∥B∥ M HW β t t-1 i=0 ∥∆ i -∆ ′ i ∥ ,where inequality (61.a) is obtained by using (76).Finally, still using (76), an upper bound of ∥E 3 ∥ is obtained as follows∥E 3 ∥ ≤W t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I - t-1 j=i+1 1 j<t A + ∆ ′ j + 1 j=t I (62) ≤κ 2 (1 -γ) -1 W β t t-1 i=0 ∥∆ i -∆ ′ i ∥ .It follow directly thatx (M) t -x (M ′ ) t ≤ ∥E 1 ∥ + ∥E 2 ∥ + ∥E 3 ∥ (63) ≤ κ 2 HW β t ∥M -M ′ ∥ + κ 2 (1 -γ) -1 (x 0 α t + (∥B∥ HM + 1) W β t ) t-1 i=0 ∥∆ i -∆ ′ i ∥ .We next observe the relationshipu (M) t -u (M ′ ) t = -Kx (M) t + Kx (M ′ ) t + M [w] H t-1 -M ′ [w] H t-1 (64) ≤ κ x (M) t -x (M ′ ) t + HW ∥M -M ′ ∥ .Therefore, it follows thatx (M) t -x (M ′ ) t + u (M) t -u (M ′ ) t ≤ (1 + κ) x (M) t -x (M ′ ) t + HW ∥M -M ′ ∥ (65) ≤ (1 + κ) κ 2 HW β t + HW ∥M -M ′ ∥ + (1 + κ) κ 2 (1 -γ) -1 (x 0 α t + (∥B∥ HM + 1) W β t ) t-1 i=0 ∥∆ i -∆ ′ i ∥ .Combining ( 65) and (55), we obatin the desired result. □We analyze the smoothness of the per stage cost and the per stage expected cost in the following Lemma B.6 and B.8, respectively.The per stage cost function c t M; {∆ i } 0≤i<t , ∀1 ≤ t ≤ T, is smooth in the sense that∇ M c t M; {∆ i } 0≤i<t -∇ M ′ c t M ′ ; {∆ ′ i } 0≤i<t F (66) ≤ λ t ∥M -M ′ ∥ F + ν t t-1 i=0 ∥∆ i -∆ ′ i ∥ F ,whereEQUATION)ν t =d x √ H ςHW 1 + ∥B∥ κ 2 + κ 3 κ 2 + κ 3 (1 -γ) -1 + G (1 -γ) -1(68)• κ 4 + κ 5 HW ∥B∥ β t (x 0 α t + (∥B∥ HM + 1) W β t ) ,and ∆ i and ∆ ′ i , ∀0 ≤ i < t, denotes the policy-dependent state transition perturbations under the policy M and M ′ , respectively.Proof. We prove this lemma based on the smoothness of the cost function c t (x, u) in A 5, i.e.,EQUATIONBased on the expression of ∇ M c t M; {∆ i } 0≤i<t in (24) , it follows thatEQUATIONwhereEQUATION)We next analyze each term in (70) one by one. Specifically,∥F 1 ∥ = t-1 i=0      t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B   ⊤ ∇ x c t x (M) t , u (M) t (74) -   t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B   ⊤ ∇ x c t x (M ′ ) t , u (M ′ ) t +   t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I B   ⊤ ∇ x c t x (M ′ ) t , u (M ′ ) t -   t-1 j=i+1 1 j<t A + ∆ ′ j + 1 j=t I B   ⊤ ∇ x c t x (M ′ ) t , u (M ′ ) t    [w] H i-1 ⊤ (74.a) ≤ HW ∥B∥ κ 2 β t ∇ x c t x (M) t , u (M) t -∇ x c t x (M ′ ) t , u (M ′ ) t + HW ∥B∥ κ 2 (x 0 Gα t + GW (∥B∥ HM + 1) β t ) • t-1 i=0 t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I - t-1 j=i+1 1 j<t A + ∆ ′ j + 1 j=t I ,where inequality (74.a) holds due to the definition of β t and the upper bound of∇ x c t x (M ′ ) t , u (M ′ ) t provided in Lemma B.3.For the last term in (74), we first observe that t-1 j=i+11 j<t A + ∆ ′ j + 1 j=t I - t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I (75) = ∆ ′ i+1 -∆ i+1 t-1 j=i+2 1 j<t A + ∆ ′ j + 1 j=t I + A + ∆ i+1 ∆ ′ i+2 -∆ i+2 t-1 j=i+3 1 j<t A + ∆ ′ j + 1 j=t I + • • • + i+1+l k=i+1 1 k<t A + ∆ k + 1 k=t I ∆ ′ i+1+l+1 -∆ i+1+l+1 t-1 j=i+1+l+2 1 j<t A + ∆ ′ j + 1 j=t I + • • • + t-2 k=i+1 1 k<t A + ∆ k + 1 k=t I ∆ ′ t-1 -∆ t-1 ≤   t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t   κ 2 ∆ ′ i+1 -∆ i+1 1 -γ + κ 2 ξ i+1 -1 + • • • + κ 2 ∆ ′ i+1+l+1 -∆ i+1+l+1 1 -γ + κ 2 ξ i+1+l+1 -1 + • • • + κ 2 ∆ ′ t-1 -∆ t-1 1 -γ + κ 2 ξ t-1 -1 ≤   t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t   t-1 k=i+1 κ 2 (1 -γ) -1 ∥∆ ′ k -∆ k ∥ ≤   t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t   t-1 k=0 κ 2 (1 -γ) -1 ∥∆ ′ k -∆ k ∥ .As a result,t-1 i=0 t-1 j=i+1 1 j<t A + ∆ ′ j + 1 j=t I - t-1 j=i+1 1 j<t A + ∆ j + 1 j=t I (76) ≤ t-1 i=0 t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t t-1 k=0 κ 2 (1 -γ) -1 ∥∆ ′ k -∆ k ∥ = κ 2 (1 -γ) -1 β t t-1 i=0 ∥∆ ′ i -∆ i ∥ .Substitue (76) into (74), it follows∥E 1 ∥ ≤HW ∥B∥ κ 2 β t ∇ x c t x (M) t , u (M) t -∇ x c t x (M ′ ) t , u (M ′ ) t (77) + (x 0 Gα t + GW (∥B∥ HM + 1) β t ) κ 2 (1 -γ) -1 t-1 i=0 ∥∆ ′ i -∆ i ∥The upper bounds for ∥E 2 ∥ and ∥E 3 ∥ can be readily obtained as followsEQUATIONSubstitute ( 77), ( 78) and ( 79) into (70), we have∇ M c t M; {∆ i } 0≤i<t -∇ M ′ c t M ′ ; {∆ ′ i } 0≤i<t (80) ≤ 1 + ∥B∥ κ 2 + κ 3 HW ∇ x c t x (M) t , u (M) t -∇ x c t x (M ′ ) t , u (M ′ ) t + ∇ u c t x t , u (M) t -∇ u c t x t , u (M ′ ) t + β t t-1 i=0 ∥∆ ′ i -∆ i ∥ ,whereβ t = (1 -γ) -1 κ 4 + κ 5 HW ∥B∥ β t (x 0 Gα t + GW (∥B∥ HM + 1) β t ) .Applying Lemma B.5 to (80) leads to the desired result. □Before we proceed to analyze the gradient difference of the expected per stage cost, we cite the following tool lemma in [21] .EQUATIONThe smoothness regarding the expected per stage cost is summarized below.Lemma B.8 For any M, M ′ , M 1 , M 2 ∈ M and ∀1 ≤ t ≤ T, the following inequality holdsEQUATION-E x0,{∆ ′ i ∼Di(M2)} 0≤i<t ,{wi} 0≤i<t ∇ M ′ c t M ′ ; {∆ ′ i } 0≤i<t F ≤ λ t ∥M -M ′ ∥ F + ν t t-1 i=0 ε i ∥M 1 -M 2 ∥ F .Proof. The norm of the gradient difference in (82) can be expanded asE ∇ M c t M; {∆ i } 0≤i<t -∇ M ′ c t M ′ ; {∆ ′ i } 0≤i<t F (83) ≤ E ∇ M c t M; {∆ i } 0≤i<t -∇ M ′ c t M ′ , {∆ i } 0≤i<t F + E ∇ M ′ c t M ′ , {∆ i } 0≤i<t -∇ M ′ c t M ′ , ∆ ′ 1 , {∆ i } 1≤i<t F + • • • + E ∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , {∆ i } k≤i<t -∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k , {∆ i } k+1≤i<t F + • • • + E ∇ M ′ c t M ′ , {∆ ′ i } 0≤i<t-1 , ∆ t-1 -∇ M ′ c t M ′ , {∆ ′ i } 0≤i<t-1 F ,where we drop the subscript in E [•] since the associated randomness is clear from the context.We next analyze a general term in R.H.S. of inequality (83). Specifically,E ∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , {∆ i } k≤i<t -∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k , {∆ i } k+1≤i<t F (84) = E E ∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , ∆ k , {∆ i } k+1≤i<t -∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , ∆ ′ k , {∆ i } k+1≤i<t ∆ ′ j 0≤j≤k-1 , {∆ i } k+1≤i<t F ≤ E E ∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , ∆ k , {∆ i } k+1≤i<t -∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , ∆ ′ k , {∆ i } k+1≤i<t ∆ ′ j 0≤j≤k-1 , {∆ i } k+1≤i<t F . Given ∆ ′ j 0≤j≤k-1 , {∆ i } k+1≤i<t, for notation conciseness, we abbreviate∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , ∆ k , {∆ i } k+1≤i<t and ∇ M ′ c t M ′ , ∆ ′ j 0≤j≤k-1 , ∆ ′ k , {∆ i } k+1≤i<t as ∇ M ′ c t (M ′ , ∆ k ) and ∇ M ′ c t (M ′ , ∆ ′ k ) , respectively. It follows that ∥E [∇ M ′ c t (M ′ , ∆ k ) -∇ M ′ c t (M ′ , ∆ ′ k )]∥ 2 F (85) = Tr (E [∇ M ′ c t (M ′ , ∆ k )] -E [∇ M ′ c t (M ′ , ∆ ′ k )]) ⊤ (E [∇ M ′ c t (M ′ , ∆ k )] -E [∇ M ′ c t (M ′ , ∆ ′ k )]) = ∥E [∇ M ′ c t (M ′ , ∆ k ) -∇ M ′ c t (M ′ , ∆ ′ k )]∥ F Tr V ⊤ E [∇ M ′ c t (M ′ , ∆ k )] -V ⊤ E [∇ M ′ c t (M ′ , ∆ ′ k )], whereEQUATIONBased on Lemma B.6, givenEQUATIONSubstitute (87) into (85), it follows thatEQUATIONUsing the similar approach, we can obtainEQUATIONEQUATION. . .EQUATIONCombining ( 83), ( 89)-(91), it follow inequality (82). □We define a total cost function J T asEQUATIONIt is clear thatEQUATIONWe next analyze the gradient properties and the smoothness of the total cost function J T M; {∆ t } 0≤t<T . We again note that ∇J T M; {∆ t } 0≤t<T denotes the gradient taken w.r.t. the first argument M.Lemma C.1 The variance of the gradient of the total cost function satisfiesEQUATIONProof. Note that ∇J 0 (M; ∆ 0 ) = ∇ M c 0 (x 0 , u 0 ) = ∇ M c 0 (x 0 , -Kx 0 ) = 0. Inequality (94) then follows directly from the norm triangular inequality: EQUATIONDenote f t (M; M 1 ) = E x0,{∆i∼Di(M1)} 0≤i<t ,{wi} 0≤i<t c t M; {∆ i } 0≤i<tas the per stage expected cost with the distribution of policy-dependent perturbation is shifted from∆ i ∼ D i (M) to ∆ i ∼ D i (M 1 ), ∀0 ≤ i < t.From the convexity of per stage expected cost in Lemma B.1, we know that,EQUATIONwhere the gradient ∇f t1 (M ′ ; M 1 ) is taken w.r.t. the first argument M ′ .From stong convexity of per stage expected cost in Lemma B.2, we know that, ∀H ≤ t 2 ≤ T, f t2 (M; M 1 ) is min µσ 2 2 , µγ 2 σ 2 64κ 10 -strongly convex function of M. Therefore, it followsEQUATION+ min µσ 2 2 , µγ 2 σ 2 64κ 10 ∥M -M ′ ∥ 2 F , ∀H ≤ t 2 ≤ T.Sum up (96) from t 1 = 1 to t 1 = H -1 and (97) from t 2 = H to t 2 = T , we obatinEQUATION+ Tr   ∇ H-1 t1=1 f t1 (M ′ ; M 1 ) + T t2=H f t1 (M ′ ; M 1 ) ⊤ (M -M ′ )   + µ 2 ∥M -M ′ ∥ 2 F .Inequality (13) follows directly by noting thatEQUATIONEQUATIONE Proof of Lemma 3EQUATIONfollows directly by combining the norm triangular inequalityand the results in Lemma B.6.EQUATION≤ T t=1 E x0,{∆i∼Di(M1)} 0≤i<t ,{wi} 0≤i<t ∇ M c t M; {∆ i } 0≤i<t -E x0,{∆ ′ i ∼Di(M2)} 0≤i<t ,{wi} 0≤i<t ∇ M ′ c t M ′ ; {∆ ′ i } 0≤i<t F ≤ T t=1 λ t ∥M -M ′ ∥ F + T t=1 ν t t-1 i=0 ε i ∥M 1 -M 2 ∥ F = T t=1 λ t ∥M -M ′ ∥ F + T -1 t=0 ε t T i=t+1 ν i ∥M 1 -M 2 ∥ F .Fix any M, M ′ ∈ M, the optimality condition to (15) implies thatEQUATIONwhere the gradients are again taken w.r.t. the first argument in the function C T (•, •). Observe the factEQUATIONAdding and subtracting the term ∇C T (Φ (M) ; M ′ ) implies the equalityTr ((∇C T (Φ (M) ; M ′ ) -∇C T (Φ (M) ; M)) • (Φ (M) -Φ (M ′ ))) (104) = Tr ((∇C T (Φ (M) ; M ′ ) -∇C T (Φ (M ′ ) ; M ′ )) • (Φ (M) -Φ (M ′ ))) . Recall that C T (Φ (M) ; M ′ ) is µ-strongly convex w.r.t. Φ (M), it follows Tr ((∇C T (Φ (M) ; M ′ ) -∇C T (Φ (M ′ ) ; M ′ )) • (Φ (M) -Φ (M ′ ))) (105) ≥ µ ∥Φ (M) -Φ (M ′ )∥ 2 F .Meanwhile, applying Lemma 3 to the left hand side of (104) givesTr ((∇C T (Φ (M) ; M ′ ) -∇C T (Φ (M) ; M)) • (Φ (M) -Φ (M ′ ))) (106) ≤ T -1 t=0 ε t T i=t+1 ν i ∥M -M ′ ∥ F ∥Φ (M) -Φ (M ′ )∥ F .Combining (104), ( 105) and ( 106), it followsEQUATIONWe note that M n+1 = Φ (M n ) by the definition of ( 15), and M P S = Φ M P S by the definition of performative stability. Applying (107) yieldsM n -M P S F = Φ (M n-1 ) -Φ M P S F ≤ T -1 t=0 ε t T i=t+1 ν i µ M l-1 -M P S F (108) ≤   T -1 t=0 ε t T i=t+1 ν i µ   n M 0 -M P S F . Setting T -1 t=0 (εt T i=t+1 νi) µ n M 0 -M P SF to be at most ρ and solving for n completes the proof.We have the following Lemma 5 regarding the convergence results of the proposed RSGD in Algorithm 1.Lemma 5 Under A1-A6. Consider a sequence of non-negative step sizes {η n , n ≥ 0} satisfyEQUATIONfor any n ≥ 0. Then, the iterates generated by RSGD admit the following bound for any N ≥ 1:E M N -M P S 2 F ≤ N -1 n=0 1 -η n µ - T -1 t=0 ε t T i=t+1 ν i E M 0 -M P S 2 F (111) + 4η N -1 T T t=1 ϑ 2 t µ - T -1 t=0 ε t T i=t+1 ν i , where ϑ t = κ 3 G HW + κ 2 κ ∥B∥ β t + 1 (x 0 α t + c 3 β t ) + GHW M κ 3 β t + 1 , ∀1 ≤ t ≤ T.Proof. Since projecting onto a convex set can only bring two iterates closer together, it follows thatE M n+1 -M P S 2 F ≤ E M n -η n ∇J T M n ; {∆ t } 0≤t<T -M P S 2 (112) ≤ I 1 + I 2 + I 3 ,whereEQUATIONEQUATIONEQUATIONand∆ t ∼ D t (M n ) , ∀0 ≤ t < T.We first analyze the term I 2 . Let E n [•] be the conditional expectation on M n . We haveE n Tr M n -M P S ⊤ ∇J T M n ; {∆ t } 0≤t<T = Tr M n -M P S ⊤ ∇C T (M n ; M n ) (116) = Tr M n -M P S ⊤ ∇C T (M n ; M n ) -∇C T M n ; M P S + Tr M n -M P S ⊤ ∇C T M n ; M P S -∇C T M P S ; M P S ,where we use the fact that ∇C T M P S ; M P S = 0 in the last equality of (116).Applying the Cauchy-Schwarz inequality and Lemma 3, we obtainTr M n -M P S ⊤ ∇C T (M n ; M n ) -∇C T M n ; M P S (117) ≥ -M n -M P S F T -1 t=0 ε t T i=t+1 ν i M n -M P S F = - T -1 t=0 ε t T i=t+1 ν i M n -M P S 2 F .Meanwhile, based on strongly convexity of C T in Lemma 2, we haveEQUATIONSubstitute ( 117) and ( 118) into (116) and take the full expectation, it follows that I 2 satisfiesEQUATIONWe next analyze the term I 3 . We observe the following equivalent expression for I 3EQUATION+ ∇C T (M n ; M n ) -∇C T M P S ; M P S 2 F . Therefore, E ∇J T M n ; {∆ t } 0≤t<T 2 F (121) ≤ 2E ∇J T M l ; {∆ t } 0≤t<T -∇C T (M n ; M n ) 2 F + 2E ∇C T (M n ; M n ) -∇C T M P S ; M P S 2 F .According to Lemma C.1, an upper bound of the variance of ∇J T M n ; {∆ t } 0≤t<T is given by (94). Moreover, based on Lemma 3, we haveE ∇C T (M n ; M n ) -∇C T M P S ; M P S 2 F (122) ≤ T t=1 λ t + T -1 t=0 ε t T i=t+1 ν i 2 E M n -M P S 2 F .Substitute (94) and (122) back into (121), it followsEQUATIONNow subtitute ( 119) and (123) back into (112), we obtainE M n+1 -M P S 2 F ≤ E M n -M P S 2 F -2η n µ - T -1 t=0 ε t T i=t+1 ν i (124) • E M n -M P S 2 F + 2η 2 n T t=1 λ t + T -1 t=0 ε t T i=t+1 ν i 2 E M n -M P S 2 F + 2η 2 n T T t=1 ϑ 2 t =   1 -2η n µ - T -1 t=0 ε t T i=t+1 ν i + 2η 2 n T t=1 λ t + T -1 t=0 ε t T i=t+1 ν i 2   E M n -M P S 2 F + 2η 2 n T T t=1 ϑ 2 t . Let η n be choosen such that η n µ - T -1 t=0 ε t T i=t+1 ν i ≥ 2η 2 n T t=1 λ t + T -1 t=0 ε t T i=t+1 ν i 2 .Then inequality (124) is reduced toE M n+1 -M P S 2 F ≤ 1 -η n µ - T -1 t=0 ε t T i=t+1 ν i E M n -M P S 2 F (125) + 2η 2 n T T t=1 ϑ 2 t .Therefore,E M N -M P S 2 F ≤ N -1 n=0 1 -η n µ - T -1 t=0 ε t T i=t+1 ν i E M 0 -M P S 2 F (126) + N -1 n=0 N -1 i=n+1 1 -η i µ - T -1 t=0 ε t T i=t+1 ν i 2η 2 n T T t=1 ϑ 2 t . Let η 0 < 2 µ-T -1 t=0 (εt T i=t+1 νi) .Based on Lemma 6 in [14] , ifEQUATIONSubstitute (127) into (126), we obtain the desired result.Based on the step size requirements in Lemma 5, RSGD converges when the aggregated sensitivity T -1 t=0 ε t T i=t+1 ν i is strictly below the threshold µ defined in Lemma 4, i.e., the same sufficient condition that guarantees the existence of M P S .The first term on the R. H. S. of (111) decays sub-geometrically and is scaled by the initial errorE M 0 -M P S 2F . The second term is a fluctuation term that only depends on the variance of the stochastic gradient, which decays at a slower rate as O (η N -1 ).We select the diminishing step sizes η n = ϕ1 n+ϕ2 , ∀n ≥ 0, where ϕ 1 and ϕ 2 satisfy ( 17) and ( 18) simultaneously. We can verify that condition (109) in Lemma 5 is reduced to (17) in Theorem 1. Besides, condition (110) in Lemma 5 can be further simplifed asEQUATIONwhich is equivalent toEQUATIONNote that ∀n ≥ 0, to guarantee (129) holds, we only need to letEQUATIONwhich coincides with condition (18) in Theorem 1.Lastly, not that 1 + x ≤ e x for all x > 0, we can verify the first term in R.H.S. of (111) can be upper bounded asEQUATIONTherefore, Theorem 1 follows by combining (130) and ( 131).Since ∥A t ∥ ≤ 1 -γ + κ 2 ξ t ≤ ζ < 1, ∀0 ≤ t < T, it follows directly that α t = t-1 i=0 1 -γ + κ 2 ξ i ≤ t-1 i=0 ζ = ζ t and β t = t-1 i=0 t-1 j=i+1 1 j<t 1 -γ + κ 2 ξ j + 1 j=t ≤ 1-ζ t 1-ζ . Further calculation yeilds ν t = (c 1 + c 2 β t ) (x 0 α t + c 3 β t ) ≤ c 1 + c 2 1 1-ζ x 0 + c 3 1 1-ζ .As a result, the sufficient condition (16) for the existence and uniqueness of M P S is reduced toEQUATIONThis is equivalent to c1 + c 2 1 1-ζ x 0 + c 3 1 1-ζ T -1 t=0 T -t T -H+1 ε t < µ, where µ = min µσ 22 , µσ 2 γ 2 64κ 10 . As a result, to guarantee condition (132) holds, it is sufficient to ensure thatEQUATIONAs a result, to guarantee the sufficient condition ( 16) can be satifised, we must haveEQUATIONThis means thatEQUATIONAs a result, Proposition 2 is proved by lettingϕ = ζ-1 c1x0+(c1c3+c2c3+c3x0) ζ -1 .NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: The paper does not provide the type of compute workers, memory, or time of execution.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The research conducted in the paper conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Justification: There is no societal impact of the work performed.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: The paper does not use existing assets. Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix:  


Decision: The paper establishes an interesting and novel connection between performative prediction and linear control. The paper also provides theoretical analysis for stable control solutions in this framework, propose an algorithm, and illustrate the approach and results with a numerical example. Although there has been some divergence on the appreciation of the technical contributions, all reviewers appreciate the novelty of the framework. I believe this paper can inspire further research. Indeed, during the review process, the authors have shown their work also generalizes recent seminal work on this area. 

The reviewers highlighted some improvements that must be addressed for the camera ready version.

Reviews: review: paper_summary: paper_summary: The paper introduces the framework of performative control in the context of linear dynamical systems, where the control policy chosen by the controller impacts the underlying system dynamics. This interaction results in policy-dependent system states with temporal correlations. Inspired by the concept of performative prediction, the authors define a performatively stable control (PSC) solution and provide conditions for its existence and uniqueness. Specifically, they analyze how system stability affects the existence of the PSC solution, showing that for almost surely stable dynamics, the PSC solution exists if the sum of distributional sensitivities is sufficiently small. Conversely, for almost surely unstable dynamics, the existence of the PSC solution requires a backward decay of these sensitivities. The paper also introduces a repeated stochastic gradient descent (RSGD) algorithm that converges to the PSC solution, with theoretical analysis of its non-asymptotic convergence rate. Numerical experiments validate the theoretical findings, demonstrating the practical applicability of the proposed framework in scenarios such as stock investment risk minimization.
strength_weakness: strength_weakness: I feel I does not get the punchline of the paper. Many of the convergence results appear standard: if your problem is convex and sufficiently smooth ($\epsilon$-sensitivity), gradient descent is the obvious approach. This observation is well exploited since the original performative prediction paper. 

Moreover, despite the existing MDP literature typically considering finite action and state spaces, it is not clear to me that the linear model presents a serious challenge. 

Finally, I would like to add I believe the model presented in the paper has potential to enhance our understanding of general performative prediction. Albeit this is not the primary intention of the paper.  
In the most abstract sense, the distribution map $\mathcal{D}$ depends on the controller's action $u$ (or policy $M$). I wonder if we can interpret this paper's model as having a distribution map that includes a linear term $Bu_t$ along with a small perturbation $A_t(M)x_t$. In this context, we might say this paper generalizes the original performative prediction framework, which requires the distribution map $\mathcal{D}$ to be insensitive to the controller's actions, by allowing for any linear shift represented by $B$.
questions: questions: Can you highlight the challenge the is unique to linear dynamical system compared to MDP with finite numbers of states and actions?
limitations: limitations: There is not particular limitations for the paper to address.
paper_summary: paper_summary: The work presents a new approach for linear dynamical systems and highlights how control policies can directly affect the system’s dynamics thereby resulting in policy-dependent changes in system states. It also outlines specific conditions under which a stable control strategy can be achieved and introduces a method based on repeated stochastic gradient descent to reach this solution. The authors support their theoretical claims with relevant empirical results.
strength_weakness: strength_weakness: - The concepts and algorithms introduced may be complex for practical implementation without extensive customization
- Reliance on numerical examples vs extensive empirical data might limit how the framework will perform on real-world conditions
questions: questions: - How is policy-depended temporal correlation in this work different from existing performative prediction works? this needs to be covered to highlight novelty
- As per A4, A5 and A6, the cost function is assumed to be strongly convex, smooth and have bounded gradients respectively. These are common assumptions in optimization, can we relax this for cost functions in this control setting?
- The RSGD Algorithm 1 has a projection step Proj_M - what metric is used for this projection? How is $M_n$ updated if the calculated M_n+1 falls outside of M? Also, is it reasonable to expect access to the true $A_t$, $w_t$ matrices in practice to compute the gradient eqn (17)?
- The projection step assumes projecting into feasible set M is computionally tractable. How is it justified based on M structure?
- RSGD is relatively straightforward, why it over other potential optimization methods for finding the psc solution?
- the RSGD convergence rate is analyzed but the work will benefit from an emperical results comparing the actual convergence speed & efficiency of rsgd over other candidate algo.
- Algo 1 assumes access to true gradients of the cost function, in practice they need to be estimated. So, impact of noisy gradient estimates on the convergance properties should be discussed
limitations: limitations: - Assumes the per stage cost function is strongly convex, smooth, and bounded. These assumptions may not hold for all types of control costs, limiting the applicability of the results.
- The implementation of the proposed repeated stochastic gradient descent and other algorithmic strategies may involve high computational costs, particularly as system dimensions and data volumes grow.
- The validation of the framework heavily relies on numerical simulations rather than empirical testing with real-world data.
paper_summary: paper_summary: The authors introduce the problem of performative linear control whereby one aims to control the evolution of a linear dynamical system whose dynamics are influenced by the choice of control policy. Apart from defining the problem, they define the concept of a performatively stable controller, extending the definition of performative stability introduced by Perdomo et al for the supervised learning setting. Given their model, their main technical results are results showing existence and uniqueness of a performatively stable controller under specific conditions, and a convergence result that illustrates how repeated stochastic gradient descent will converge to stability in this new setting at a O(1/T) rate.
strength_weakness: strength_weakness: While the motivation regarding how control policies might influence the dynamics is exciting, I find that it is quite underdeveloped in the paper. The main illustrative example the authors have is this stock market example. The intuition behind how control policies can affect the dynamics is plausible to me, but I would have liked to see it written out in detail in the main body. The primary exposition of this example is deferred to the appendix and I felt that it lacked clarity. 

This underdeveloped motivation then makes the formal model itself hard to interpret and justify. I didn’t quite understand why the policy only affects the state matrix A, why all policy induce disturbances that are zero-mean, or why the disturbances between time steps are uncorrelated for the same policy. It would be helpful if the authors spent more time explaining the model and how it maps onto the high level ideas explained in the introduction. 

Lastly, I think the paper suffers from a lack of clarity in the technical writing. Several quantities are referenced without being previously defined and there are some claims in the paper than are unsubstantiated (specifically, the idea that performative stability implies performative optimality in this new control model). Please see below for a full list of comments and questions.
questions: questions: Could the authors motivate why they assume that A_t is performative but B is time invariant?

Why are the performative disturbances for A_t assumed to all be zero mean? 

In L171, what is \tilde{A?}? Is this just A? Or A - BK?

In Lemma 1, is K assumed to be strongly stable? If so, could you please make that explicit?

In L182: the authors claim that the PSC is approximately performative optimal, why is that?  In L236 they cite [22], but the result in [22] is shown in a different model with different assumptions

L205: there is a mistaken reference, the authors reference A1-6, but only A4-6 are about the costs

Why do the authors refer to the condition that the operator norms of the matrices are <1 as almost surely stable? I usually understand stability in linear control as the condition that the spectral radius (not the operator norm) is smaller than 1. Assuming that the operator norm is smaller than 1 is a strictly stronger condition.

Theorem 1 is not very readable. Please write this out as a lemma in the appendix and state the result formally with the step sizes plugged in so that the reader can appreciate the final convergence rate (stated formally).

What is reference 13 it doesn’t seem to have an author? Reference 18 was published in a conference.
limitations: limitations: These issues have been discussed to the extent necessary.
paper_summary: paper_summary: This paper presents the new framework of performative control based on the performantive prediction concept.  The performative stable control (PSC) problem is formulated and its solvability conditions are derived. This paper also presents the algorithm of finding the PSC solution and addresses the convergence analysis.
strength_weakness: strength_weakness: The disturbance-action policy defined in Definition 1 implicitly assumes that the disturbance w is measurable.  This assumption is practically severe and limits the application of the control policy.

The results of this paper rely heavily on the performative prediction results from the work [22].  Under many practically severe assumptions, the authors provide a new control policy and convergence analysis.
questions: questions: The assumption that the disturbance w is available for determining the control action u, is practically severe.  Could the authors relax the assumption?

Lemma 4, the convergence condition, is technically correct.  However, the reviewer cannot find any interpretation of the condition (11).  Could you give some remarks on the interpretation?
 
The reviewer cannot agree the statement of Introduction, "Most prior studies on control of linear dynamical systems rely on the key assumption that the system state transition model is static".  The pioneering works on state-space-based theory by R. E. Kalman, published 1960, handle time-varying system, meaning the transition is time-dependent.  Could you give more surveys on classical control problems?
limitations: limitations: The limitations of the proposed control policy such as measurable disturbance and perfect modeling on the state transition are not adequately stated in this paper.

Comments: title: Key differences between our PP on linear dynamical system and performative prediction results from the work [22]
Summary of key differences between our work and existing PP works (original PP, PP on MDP with finite states and stateful PP)
Seeking Your Feedback
Seeking Your Feedback
Seeking Your Feedback
seeking feedback from reviewers
comment: Dear Reviewer wfwc,

Thank you for participating in the discussion and your thoughtful comments. We hope we have addressed your concerns, and we would be happy to provide additional explanations and insights as needed.

Warmest regards,

Authors
Dear Reviewer JGbs,

Thank you very much for your valuable comments and suggestions in the rebuttal period.

We will follow your comments to validate our developed theory on more examples using real-world data.

Warmest regards,

Authors
Thank you for answering all my comments. The responses on Q5 and Q6 align with my initial comments and addresses that. I went through all the answers and I have no further questions at this point. I believe the weakness highlighted in W1, W2 and empirical validation still remains critical for this work. I hope the authors can leverage context in the rebuttal answers and verify the developed theory on more examples.
Dear Reviewer nkz4,

We are very glad that you liked our paper. Thank you for the many valuable and insightful comments and discussions in the rebuttal period, which help us to motivate our contributions much better. Many thanks for raising the score.

In the revision, we will pay special attention to all your comments and do our best to improve the clarity of the technical writing.

Warmest regards,

Authors.
Amazing. This I think would be a much much better motivation for the linear dynamical system model than the stock market example. I would encourage the authors to make this connection between stateful distribution maps and linear dynamical systems front and center of their paper. I have updated my score. Please pay attention to all my comments in the revision and take special care to improving the clarity of the technical writing.
Dear Reviewer e5pZ,

Thank you for participating in the discussion. 

**[W2] "The results of this paper rely heavily..." The reviewer finds some novelty of the work compared with the previous work [22]. However, he/she believes the contribution is insufficient, particularly not enough to be accepted at a high-level conference like NeurIPS.**：

We thank the reviewer's comments. We believe there may be some misunderstandings regarding the contributions of our work. 
We summarize some key contributions that distinguish our work from the standard PP work [22].

**$\bullet$ Strong Convexity Analysis**: The standard PP work [22] brute-forcely assumed that the optimization variable is strongly convex in the policy without any problem-specific theoretical analysis. However, in our paper, **we provide a linear-system-dynamics-dependent strong convexity analysis**, which is unique to our performative linear dynamic systems.

**$\bullet$ Stateful vs Non-stateful**: The distribution map in the standard PP work [22] is non-stateful, where all the data samples follow a simple and static distribution $Z\sim\mathcal{D}(\theta).$ However, in our work, **we consider a more complicated stateful performative maps, where observed data distributions depend on the history of previously deployed polices**. 

**$\bullet$ Promote understanding of general PP**:  Our PP via linear dynamical system modeling is closely connected to the linearized general stateful distribution map in the seminal work of stateful PP [R1]. **Our work allows performative transition maps of performative distributions** and **extends** the technical results of the **fixed performative distribution transition map** in the stateful PP work [R1]. As a result, **our work has potential to enhance the understanding of general performative prediction**.

The above three key differences serve as strong evidence that clearly justifies our contributions and distinguishes our work from standard PP work [22].

[R1]. Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. In International conference on artificial intelligence and statistics, pages 6045–6061. PMLR, 2022.
**6. "Illustrating some connection (even if not completely precise
and exact) between LDS's and stateful performative prediction (as
initiated by Brown et al AISTATS 2022) would really go a long way
in terms of motivating the author's contribution":**

Thank you very much for your suggestion. We illustrate some connections
between our LDS and the seminal stateful PP work by Brown et al AISTATS
2022 [3] as follows.

**$\bullet$ Performative Prediction in a Stateful World by Brown et al AISTATS
2022 [3]**: This seminal work introduces a transition map $f\left(\cdot\right)$
to model the stateful distribution as 
\begin{align}
 & D\_{t}=f\left(D\_{t-1},\theta\_{t}\right),\forall t\geq1. \quad  (2)
\end{align}
Similar as our response to Comment 5, after linearization and ignoring
the higher order terms, equation (2) can be represented as 
\begin{align}
d\_{t} & \overset{\mathrm{d}}{=}\mathbf{A}d\_{t-1}+\mathbf{B}\theta\_{t}+\mathbf{w}, \quad (3)
\end{align}
with $\mathbf{A}=\left[\frac{\partial\widetilde{f}}{\partial d}\right]\_{\left(\overline{d},\overline{\theta}\right)},$
$\mathbf{B}=\left[\frac{\partial\widetilde{f}}{\partial\theta}\right]\_{\left(\overline{d},\overline{\theta}\right)}$
and $\mathbf{w}=\widetilde{f}\left(\overline{d},\overline{\theta}\right)-\mathbf{A}\overline{d}-\mathbf{B}\overline{\theta}.$ 

**$\bullet$ Our LDS**: View the state $\mathbf{x}\_{t}$ of LDS as a random variable,
we have 
\begin{align}
 & \mathbf{x}\_{t}\overset{\mathrm{d}}{=}\mathbf{A}\_{t}\left(\mathbf{M}\right)\mathbf{x}\_{t-1}+\mathbf{B}\mathbf{u}^{DAP}\left(\mathbf{M}\_{t}\right)+\mathbf{w}\_{t},\quad (4)
\end{align}
where 
\begin{align}
 & \mathbf{A}\_{t}\left(\mathbf{M}\right)=\mathbf{A}-\mathbf{B}\mathbf{K}+\mathbf{\Delta}\_{t},\mathbf{\Delta}\_{t}\sim\mathcal{D}\_{t}\left(\mathbf{M}\_{t}\right).\quad (5)
\end{align}

**$\bullet$ Connections between our LDS and the stateful PP by Brown et al AISTATS 2022 [3]**:

**$\quad 1. $  If $\mathbf{\Delta}\_{t}=\mathbf{0}$**, i.e., there is no performative
disturbance to LDS state transition matrix $\mathbf{A}$: The performative
distribution of $\mathbf{x}\_{t}$ will depends on $\mathbf{M}\_{t}$,
but the randomness comes solely from the system noise $\mathbf{w}\_{t}$.
In this case, if we let $\mathbf{A}$ and $\mathbf{B}$ in our LDS
be random matrices and satisfy 
\begin{align*}
 & \mathbf{A}-\mathbf{B}\mathbf{K}=\left[\frac{\partial\widetilde{f}}{\partial d}\right]\_{\left(\overline{d},\overline{\theta}\right)},\mathbf{B}=\left[\frac{\partial\widetilde{f}}{\partial\theta}\right]\_{\left(\overline{d},\overline{\theta}\right)},
\end{align*}
our LDS model in (4) matches the linearized stateful distribution map model in Brown et al AISTATS 2022 [3], i.e., Equation
(3).

**$\quad 2. $ If $\mathbf{\Delta}\_{t}\neq\mathbf{0}$**: Our LDS model in (4) will correspond to a linearized stateful distribution map with performative
functional $\widetilde{f}\_{\mathbf{M}\_{t}}$ (rather than a fixed
$\widetilde{f}$ or a fixed transition map $f\left(\cdot\right)$
in Brown et al AISTATS 2022 [3]), where 
\begin{align*}
 & \mathbf{A}\_{t}\left(\mathbf{M}\_{t}\right)=\left[\frac{\partial\widetilde{f}\_{\mathbf{M}\_{t}}}{\partial d}\right]\_{\left(\overline{d},\overline{\theta}\right)}.
\end{align*}
This means that our LDS model can also correspond to the linearized
case of 
\begin{align*}
 & D_{t}=f_{\theta_{t}}\left(D_{t-1},\theta_{t}\right).
\end{align*}
This generalizes the static transition map $f\left(\cdot\right)$
in Brown et al AISTATS 2022 [3] to the more general case of performative
transition map, i.e., the form of transition map  $f\_{\theta\_{t}}$ will depend on the deployed policy $\theta\_{t}.$

**7. “Sorry for asking this so late in the window, but any insight into this last question would be very helpful in my review.”**

Thank you so much for the great and insightful question! We have provided brief discussions on: (1) connection between general stateful distribution maps $D\_{t}=f\left(D\_{t-1},\theta\_{t}\right)$ and our linear dynamic
model; and (2) the connection between LDS and the seminal work by
Brown et al AISTATS 2022 [3]. We hope that these discussions will be satisfactory and address the reviewer's concerns.
**5. "I think this paper would be incredibly impactful if it
could show and argue why the linear dynamical system framing can connect
with learning under stateful distribution maps. More concretely, the
most general setting for stateful performative maps, is to let $D_{t}=f\left(D_{t=1},\theta_{t}\right),$
where $D_{t}$ is the distribution over states (data) at time . Do
the authors have a way of showing that by appropriately considering
some Jacobin linearization of this map f, one could arrive at their
linear dynamical system model?":** 

Great and inspiring comments! Let us consider a general setting for
stateful distribution maps $D\_{t}=f\left(D\_{t-1},\theta\_{t}\right),\forall t\geq1.$
To facilitate the analysis, we use a random variable $d\_{t}\sim D\_{t}$
to equivalently characterize the distribution $D\_{t}.$ If the properties
of $f\left(\cdot\right)$ are "nice“ enough, then from the perspective
of random variables, there will exist a corresponding mapping $\widetilde{f}\left(\cdot\right)$
such that 
\begin{align*}
 & d_{t}\overset{\mathrm{d}}{=}\widetilde{f}\left(d_{t-1},\theta_{t}\right),d_{t}\sim D_{t},d_{t-1}\sim D_{t-1},\forall t\geq1,
\end{align*}
where $\overset{\mathrm{d}}{=}$ denotes equal in distribution. Linearizing
$\widetilde{f}\left(\cdot\right)$ at some equilibrium point $\left(\overline{d},\overline{\theta}\right)$
with $\overline{d}\sim\overline{D}$ and ignoring the higher order
terms will lead to
\begin{align}
d_{t} & \overset{\mathrm{d}}{=}\widetilde{f}\left(\overline{d},\overline{\theta}\right)+\left[\frac{\partial\widetilde{f}}{\partial d}\right]\_{\left(\overline{d},\overline{\theta}\right)}\left(d\_{t-1}-\overline{d}\right)+\left[\frac{\partial\widetilde{f}}{\partial\theta}\right]\_{\left(\overline{d},\overline{\theta}\right)}\left(\theta_{t}-\overline{\theta}\right)\\\\
 & \overset{\mathrm{d}}{=}\mathbf{A}d\_{t-1}+\mathbf{B}\theta\_{t}+\mathbf{w}, \quad (1)
\end{align}
where $\mathbf{A}=\left[\frac{\partial\widetilde{f}}{\partial d}\right]\_{\left(\overline{d},\overline{\theta}\right)}$
and $\mathbf{B}=\left[\frac{\partial\widetilde{f}}{\partial\theta}\right]\_{\left(\overline{d},\overline{\theta}\right)}$
are the Jacobin matrices at the equilibrium point $\left(\overline{d},\overline{\theta}\right)$
and $\mathbf{w}=\widetilde{f}\left(\overline{d},\overline{\theta}\right)-\mathbf{A}\overline{d}-\mathbf{B}\overline{\theta}.$ 

We can view $d\_{t}$ in (1) as the random state
variable $\mathbf{x}\_{t}$ of the linear dynamical systems in our
paper, $\theta\_{t}$ as the input policy (i.e., $\mathbf{M}\_{t}$
in our case) and $\mathbf{w}$ as the additive system noise (i.e.,
$\mathbf{w}\_{t}\sim\mathbf{w}$ in our case). In this way, as suggested
by the reviewer, after Jacobin linearization of $\widetilde{f}\left(\cdot\right)$
(corresponding to $f\left(\cdot\right)$ from the perspective of distribution),
one can arrive at our linear dynamical model with $\mathbf{A}=\left[\frac{\partial\widetilde{f}}{\partial d}\right]\_{\left(\overline{d},\overline{\theta}\right)}$
and $\mathbf{B}=\left[\frac{\partial\widetilde{f}}{\partial\theta}\right]\_{\left(\overline{d},\overline{\theta}\right)}.$
In the most general case, $\mathbf{A},\mathbf{B}$ are random matrices,
and $\mathbf{A},\mathbf{B}$ will be static if the equilibrium point
$\left(\overline{d},\overline{\theta}\right)$ is chosen as constant.
Dear Reviewer nkz4,

Due to writing space constraints, we're now typing the answers for the questions

**5. I think this paper would be incredibly impactful if it
could show and argue why the linear dynamical system framing can connect
with learning under stateful distribution maps. More concretely, the
most general setting for stateful performative maps, is to let $D_{t}=f\left(D_{t=1},\theta_{t}\right),$
where $D_{t}$ is the distribution over states (data) at time . Do
the authors have a way of showing that by appropriately considering
some Jacobin linearization of this map f, one could arrive at their
linear dynamical system model?**

**6. Illustrating some connection (even if not completely precise
and exact) between LDS's and stateful performative prediction (as
initiated by Brown et al AISTATS 2022) would really go a long way
in terms of motivating the author's contribution.**

in the next official comment. Could you please wait several minutes? Thank you so much.  

Warmest regards,
Authors.
With regards to point 4, could you provide a more detailed answer illustrating a precise connection between stateful performative prediction models and the linear dynamical system setting you consider?
Thank you very much for your precious time to participate in the discussion. And thanks a lot for the many inspiring comments with deep insights.

**1. "I appreciate how making the B matrix performative complicates..rather than an explicit modeling decision.":** We will follow this comment to clarify the assumption on $\mathbf{B}$ in the revised manuscript.

**2. "Why all policy induce disturbances that are zero-mean?... Is this still the case if the mean of the disturbances
varies by time step? (the system is time invariant here no?)":** Yes, this is still the case if the mean of the disturbances varies
by time step. Specifically, suppose the mean of the disturbance is $\mathbb{E}[\mathbf{\Delta}\_{t}]=\Theta_{t},$ which is
time-varying. Same as the constant mean case, this is equivalent a new $\mathbf{A}\_{t}^{\prime}=\mathbf{A}+\Theta\_{t}$ with zero mean disturbances. We only need to choose a new linear controller $\mathbf{K}\_{t}^{\prime}$ such that $\mathbf{A}\_{t}^{\prime}-\mathbf{B}\mathbf{K}\_{t}^{\prime}$ is $\left(\kappa\_{t},\gamma\_{t}\right)$-strongly stabilizing. We
then let $\kappa=$max{$\kappa\_{t},0\leq t<T$} and $\gamma=$max{$\gamma\_{t},0\leq t<T$}, and all of our technical results still hold.

**3. "W3. In L182, you claim that stable controllers 'approximately solves the POC (6)'. I read this as a claim that stability
implies optimality which as far as I can see, is not shown in this model.":** To avoid any potential confusion, we will revise the phrase "approximately solves the POC" to a more specific statement that "the performative stable solution $\mathbf{M}^{PS}$ and performative optimal solution $\mathbf{M}^{PO}$ both converge to a common value $\mathbf{M}^{*}$ as the magnitudes of the sensitivities {$\varepsilon\_{t},0\leq t<T$} approach 0."in the revised manuscript.

**4. "I like this paper because I think it takes a step in the
right direction in establishing technical transfers of knowledge between
performative prediction and other fields which study with learning
dynamical systems. On this note, one of the core problems in performative
prediction is how to confront the fact that the observed data distributions
$D\left(\theta_{t}\right)$ is just not just a function of $\theta\_{t}$
but are stateful and depend on the the history of previously deployed
models.":** It is our great pleasure that the reviewer liked our paper. We firmly
agree with the reviewer's point of view that one of the core problems
in PP is how to deal with the stateful data distributions. The stateful
distributional map setup in our paper also distinguishes our work
from the existing PP works, including the original PP work [22].
Thanks for the reply comments.  

[W1] "The disturbance-action policy..."
The reviewer understands that the problem setting on the measurable disturbance is commonly used in some works (thanks for raising the literature again).  

[W2] "The results of this paper rely heavily..."
The reviewer finds some novelty of the work compared with the previous work [22].  However, he/she believes the contribution is insufficient, particularly not enough to be accepted at a high-level conference like NeurIPS.
Hi, 

Sorry for the delay. Thank you for taking the time to answer my questions. Very helpful.

I appreciate how making the B matrix performative complicates the analysis since it not as straightforward to use tools like the disturbance action control policies. It would be good for the authors to clarify in the manuscript that this assumption comes out of a technical necessity rather than an explicit modeling decision. 

"Why all policy induce disturbances that are zero-mean?": I see how this might be the case if the disturbances have non-zero mean, but this mean is constant throughout all time steps. Is this still the case if the mean of the disturbances varies by time step? (the system is time invariant here no?)



W3. In L182, you claim that stable controllers "approximately solves the POC (6)". I read this as a claim that stability implies optimality which as far as I can see, is not shown in this model.

I like this paper because I think it takes a step in the right direction in establishing technical transfers of knowledge between performative prediction and other fields which study with learning dynamical systems. On this note, one of the core problems in performative prediction is how to confront the fact that the observed data distributions $D(\theta_t)$ is just not just a function of $\theta_t$ but are stateful and depend on the the history of previously deployed models. 

I think this paper would be incredibly impactful if it could show and argue why the linear dynamical system framing can connect with learning under stateful distribution maps. More concretely, the most general setting for stateful performative maps, is to let 

$D_{t} = f(D_{t=1}, \theta_t)$ where $D_t$ is the distribution over states (data) at time $t$. Do the authors have a way of showing that by appropriately considering some Jacobian linearization of this map f, one could arrive at their linear dynamical system model? 

Illustrating some connection (even if not completely precise and exact) between LDS's and stateful performative prediction (as initiated by Brown et al AISTATS 2022) would really go a long way in terms of motivating the author's contribution. 

Sorry for asking this so late in the window, but any insight into this last question would be very helpful in my review.
As suggested by Reviewer wfwc, we here recap the key differences between our work and the existing PP work [22].

**Original PP work [22]**: We first point out that the original PP does not involve temporal correlated performative sample data in the cost $\mathbb{E}[l(\mathbf{\theta};Z)]$, where all the data samples follow a static distribution $Z\sim\mathcal{D}(\theta).$ 

**PP on on linear dynamical system (our paper)**: In addition to the **linear-system-dynamics-dependent strong convexity analysis**, the linear dynamic system will introduce a unique challenge
of **temporally correlated performative state sample data $\mathbf{x}\_{t}$
and $\mathbf{u}\_{t}$ in the cost $\mathbb{E}[c\_{t}(\mathbf{x}\_{t},\mathbf{u}\_{t})]$**, which cannot be covered by the above Original PP work [22]. Specifically,

**$\bullet$** The cost $\mathbb{E}[c\_{t}(\mathbf{x}\_{t},\mathbf{u}\_{t})]$ is a function of policy $\mathbf{M},$ the form of which will depend on linear dynamics (i.e., $\mathbf{A},\mathbf{B}$ and $\mathbf{K}$). As a result, the linear dynamics will directly affect the strongly convex constant of $\mathbb{E}[c\_{t}(\mathbf{x}\_{t},\mathbf{u}\_{t})]$ in $\mathbf{M}$. 

**$\bullet$** The primary cause of the temporal correlation of the performative state data sample $(\mathbf{x}\_{t},\mathbf{u}\_{t})$ is also the linear dynamics (i.e., $\mathbf{A},\mathbf{B}$
and $\mathbf{K}$).
As suggested by Reviewer wfwc and Reviewer nkz4, we here recap the key differences between our work and the existing PP works.

**Original PP [22]**: We first point out that the original PP is **non-stateful**, where all the data samples follow a static distribution $Z\sim\mathcal{D}(\theta).$ Besides, **strong convexity is directly assumed without any problem-specific analysis**.

**PP on MDP with finite states [R1]**: The authors first introduced an occupancy measure $d(s,a)$ for each state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}.$ Since the number of states and actions is finite, the Markovian temporal correlation
of the performative states is then modeled as a linear function of the concatenated occupancy measure $d=[d(s,a)]\_{(s,a)\in\mathcal{S}\times\mathcal{A}.}$ **The strong convexity is artificial**. The authors further added a regulation term in the optimization objective function to guarantee the strong convexity in $d$ and then obtained the performative stable solution $d^{PS}.$ However, this method is not applicable to our case because: 

**(1)** $d(s,a)$ and $d$ cannot be constructed for MDP with infinite states; 

**(2)** We cannot artificially add a regulation term to make the optimization objective function strongly convex. 

**Stateful PP [R2]**: This seminal work considers the **stateful distribution map**, where the observed data distribution is stateful and depends on the the history of previously deployed polices. But the **strong convexity is also directly assumed** as in original PP [22] without any problem analysis.

**PP on linear dynamical system (our paper)**: We provide problem-specific **linear-system-dynamics-dependent strong convexity analysis**. Our work enables the **stateful performative transition maps of performative distributions** and **extends** the technical results of the **fixed performative distribution transition map** in the stateful PP work [R2]. 

The **stateful performative transition map modeling via linear dynamical systems** in our paper has potential to enhance the understanding of general performative prediction.

[R1]. Mandal D, Triantafyllou S, Radanovic G. Performative reinforcement learning, International Conference on Machine Learning. pages 23642–23680. PMLR, 2023.

[R2]. Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. In International conference on artificial intelligence and statistics, pages 6045–6061. PMLR, 2022.
**3. Additional Question.**

Thanks for your additional question. In a high level sense, consider
a class of application scenarios involving a group of linear stochastic
dynamic sub-systems, where each sub-system has a random state transition
matrix. If we construct a new system state by linearly mixing the
states of all the sub-systems using a weight matrix $\mathbf{M}$ (policy),
then the performative state transition matrix of this new system will
respond to the policy $\mathbf{M}$ instead of the action $\mathbf{u}_{t}.$
Our Example 1 is also constructed based on this intuition.

**Detailed explanation for Equation (15) and (16).** In Example 1, we can view each stock as a sub-system with a random state transition, where the evolution of price of $i$-th stock follows the stochastic volatility model [R3, R4] of 
\begin{align*}
 & \log s_{t+1}^{\left(i\right)}=\log s_{t}^{\left(i\right)}+\left(\frac{r-\frac{1}{2}\left(v_{t}^{\left(i\right)}\right)^{2}}{T}+\frac{v_{t}^{\left(i\right)}}{\sqrt{T}}\right),\ s_{1}^{\left(i\right)}>0,\forall1\leq t<T,
\end{align*}
or equivalently
\begin{align*}
 & s_{t+1}^{\left(i\right)}=e^{\left(\frac{r-\frac{1}{2}\left(v_{t}^{\left(i\right)}\right)^{2}}{T}+\frac{v_{t}^{\left(i\right)}}{\sqrt{T}}\right)}s_{t}^{\left(i\right)},\ s_{1}^{\left(i\right)}>0,\forall1\leq t<T.
\end{align*}

We next construct a new state, i.e., the return for the $j$-th portfolio
$q_{t}^{\left(j\right)},$ using a couple of linear mixing weights $\left[m^{j,1},\cdots,m^{j,N}\right],$
i.e., the investment strategy for the $N$ stocks.

The concatenated return vector $\mathbf{q}\_{t}$ for all portfolios under investment policy $\mathbf{M}$ is given by
\begin{align}
 \mathbf{q}\_{t+1}=\mathbf{V}\_{t}^{(\mathbf{M})}\mathbf{q}\_{t}, (1)
\end{align}
where performative state transition matrix $\mathbf{V}\_{t}^{\left(\mathbf{M}\right)}$ is a diagonal matrix with the $j$-th diagonal element given by 
\begin{align*}
 & \left(\mathbf{V}\_{t}^{\left(\mathbf{M}\right)}\right)\_{j,j}=\sum\_{i=1}^{N}m^{j,i}e^{\left(\frac{r-\frac{1}{2}\left(v_{t}^{\left(i\right)}\right)^{2}}{T}+\frac{v_{t}^{\left(i\right)}}{\sqrt{T}}\right)}
\end{align*}

Equations (15) and (16) in Example 1 are used to illustrate the performative
state transition matrix for the concatenated state $\mathbf{x}\_{t}=\left[\begin{array}{c}
\mathbf{r}\_{t}\\\\
\mathbf{q}\_{t}
\end{array}\right]$, where $\mathbf{r}\_{t}=\mathbf{q}\_{t}-\mathbb{E}\left[\mathbf{q}\_{t}\right]$
is the mean-shifted return. Based on (1), it follows immediately that the performative state transition matrix associated with
$\mathbf{x}\_{t}$ is

$$ \mathbf{A}\_{t}\left(\mathbf{M}\right)=\left[\begin{array}{cc}
\mathbb{E}\left[\mathbf{V}\_{t}^{\left(\mathbf{M}\right)}\right] & \mathbf{V}\_{t}^{\left(\mathbf{M}\right)}-\mathbb{E}\left[\mathbf{V}\_{t}^{\left(\mathbf{M}\right)}\right]\\\\
\mathbf{0}\_{N\times N} & \mathbf{V}\_{t}^{\left(\mathbf{M}\right)}
\end{array}\right].
$$

Equations (15) and (16) then hold by choosing ${\mathbf{A}}=\mathbf{I}\_{2N\times2N}$
and noting that $\mathbf{\Delta}\_{t}=\mathbf{A}\_{t}\left(\mathbf{M}\right)-\mathbf{A}.$

[R3]. Huyên Pham, Marco Corsi, and Wolfgang J Runggaldier. Numerical approximation by quanti- zation of control problems in finance under partial observations. In Handbook of Numerical Analysis, volume 15, pages 325–360. Elsevier, 2009.

[R4]. Gallant A R, Hsieh D, Tauchen G. Estimation of stochastic volatility models with diagnostics[J]. Journal of econometrics, 1997, 81(1): 159-192.
Thank you very much for participating in the discussion and providing us with plenty of valuable comments. 

**1. "While the author seems to emphasize that the strong convexity aspect is the more challenging part, the reviewer acknowledges this but does not find it particularly compelling.":** 

We thank the reviewer for acknowledging that we are indeed emphasizing the **linear-system-dynamics-dependent strong convexity analysis** of $\mathbb{E}[c\_{t}]$ in $\mathbf{M}$. 

As discussed in our paper above Lemma 2, the strong convexity of $c_{t}(\mathbf{x},\mathbf{u})$
over the state-action space $(\mathbf{x},\mathbf{u})$ does not by itself imply the strong convexity of $\mathbb{E}[c\_{t}]$
over the space of policies $\mathbf{M}$. This is because the policy
$\mathbf{M}$, which maps from a space of dimensionality $H\times d\_{x}\times d\_{u}$
to that of $d\_{x}+d\_{u}$, is not necessarily full column-rank. 

Under the conditions: (1) general $c\_{t}$ that is strongly convex in $(\mathbf{x},\mathbf{u})$; (2) general linear dynamics (i.e., $\mathbf{A},\mathbf{B}$ and $\mathbf{K}$) in Definition 2; and (3) general performative disturbances {$\mathbf{\Delta}\_i$}$\_{0\leq i<T}$ with general distributional maps {$\mathcal{D}\_i(\mathbf{M})$}$\_{0\leq i<T}$ in Assumption A2 and A3, identifying the strong convexity constant min{$\frac{\mu\sigma^{2}}{2},\frac{\mu\sigma^{2}\gamma^{2}}{64\kappa^{10}}$} of $\mathbb{E}[c\_{t}]$ in $\mathbf{M}$, where $\kappa$ and $\gamma$ are linear system dynamics-dependent, requires delicate linear-system-dynamics-dependent strong convexity analysis that is unique to performative linear dynamical systems. 

**2. "Difference from existing approach... ":** 

We thank the reviewer for giving us the opportunity to highlight the unique challenge in our PP for linear dynamical systems. 

**Original PP**: We first point out that the original PP is **non-stateful** because all the data samples follow a static distribution $Z\sim\mathcal{D}(\theta).$

**PP on MDP with finite states [R1]**: The authors first introduced an occupancy measure $d(s,a)$ for each state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}.$ Since the number of states and actions is finite, the Markovian temporal correlation
of the performative states is then modeled as a linear function of the concatenated occupancy measure $d=[d(s,a)]\_{(s,a)\in\mathcal{S}\times\mathcal{A}.}$ The authors further added a regulation term in the optimization objective function to guarantee the strong convexity in $d$ and then obtained the performative stable solution $d^{PS}.$ However, this method is not applicable to our case because: 

**(1)** $d(s,a)$ and $d$ cannot be constructed for MDP with infinite states; 

**(2)** We cannot artificially add a regulation term to make the optimization objective function strongly convex.

**PP on linear dynamical system (our paper)**: In addition to the **linear-system-dynamics-dependent strong convexity analysis**, the linear dynamic system will introduce **a unique challenge of stateful performative transition maps of performative distributions**, which cannot be covered by the above original PP and PP on MDP with finite states. Specifically,

**$\bullet$** When there is no performative disturbance to the state transition matrix $\mathbf{A}$, our **PP via linear dynamical system modeling** can be reduced to the **linearized general stateful distribution map** in the seminal work of **stateful PP [R2]**. 

**$\bullet$** If there exist performative disturbances to $\mathbf{A}$, our **PP via linear dynamical system modeling** will **uniquely introduce stateful performative transition maps of the performative distributions**. This **extends** the technical results of **fixed performative distribution transition map** in the stateful PP work [R2]. 

Therefore, compared to existing works (the original paper on PP, PP on MDP with finite states and stateful PP), our PP on linear dynamical system **has the unique potential** to enhance the understanding of general performative prediction.


[R1]. Mandal D, Triantafyllou S, Radanovic G. Performative reinforcement learning, International Conference on Machine Learning. pages 23642–23680. PMLR, 2023.

[R2]. Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. In International conference on artificial intelligence and statistics, pages 6045–6061. PMLR, 2022.
**Convexity:**  The *convexity* of $c_t$ in $M$ follows quite straightforwardly from the convexity of $c_t$ in $x_t$.  While the author seems to emphasize that the *strong convexity* aspect is the more challenging part, the reviewer acknowledges this but does not find it particularly compelling.

**Difference from existing approach**  The reviewer acknowledges that a linear dynamic model differs from an MDP with finite states.   Maybe a more accurate question is **Can you highlight the challenge the is unique your problem on PP on linear dynamical system compared to existing works (the original paper on PP and PP on MDP)?**  Upon closer examination, the proof structure appears similar to the original PP framework [22]. Could you elaborate on this beyond what was addressed in your response to Reviewer e5pZ?


**Additional Question** The reviewer wants to understand when the system responds to the policy $M$ instead of action $u_t$.  In particular, the system does not have direct access to $M$, but only $u_t$ in each round.  Can the author provide examples to illustrate this? Or explain Equation (15) and (16) in example 1?
Dear Reviewer e5pZ,

We appreciate your time and effort in reviewing our submission. We have now provided further clarification, explanation, and discussion to address your concerns. We hope you've had a chance to review them, consider whether our response addresses your concerns, and reevaluate your score accordingly. Please let us know if you have any further questions or need clarification. Thank you very much.

Warmest regards,

Authors
Dear Reviewer nkz4,

We appreciate your time and effort in reviewing our submission. We have now provided further clarification, explanation, and discussion to address your concerns. We hope you've had a chance to review them, consider whether our response addresses your concerns, and reevaluate your score accordingly. Please let us know if you have any further questions or need clarification. Thank you very much.

Warmest regards,

Authors
Dear wfwc,

We appreciate your time and effort in reviewing our submission. We have now provided further clarification, explanation, and discussion to address your concerns. We hope you've had a chance to review them, consider whether our response addresses your concerns, and reevaluate your score accordingly. Please let us know if you have any further questions or need clarification. Thank you very much.

Warmest regards,

Authors
Dear AC,

We thank all reviewers for their valuable time in reviewing our paper. The discussion period will end in a few days, but we have not received any feedback from the reviewers regarding our rebuttal. We have addressed all concerns of the reviewers and hope to discuss with them and know if there are any further clarifications to be made. Could you please kindly remind them to respond to our rebuttal? Thank you very much.

Best regards,

Authors