Performative Control for Linear Dynamical Systems
Authors: Songfu Cai
Fei Han
Xuanyu Cao
Venue: NeurIPS 2024 poster (2024)
Keywords: Performative prediction; Policy-dependent Dynamics; Disturbance-action control policy; Stochastic control
Primary area: optimization

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

Performative Control for Linear Dynamical Systems
Songfu Cai", Fei Han", Xuanyu Cao Department Electronic and Computer Engineering The Hong Kong University of Science and Technology eesfcai Celccci@us...i. @ust.kk, fhanac&connect. ukt eexcaolust. hk
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 sequence of policy-dependent system state data with policy-dependent tem- poral correlations. Following the recent literature on performative prediction [21], introduce the concept of performatively stable control (PSC) solution. We first propose sufficient condition for the performative control problem to admit a unique PSC solution with problem-specific structure of distributional sensitivity propagation and aggregation. We further analyze the impacts of system stabil- ity on the existence of the PSC solution. Specifically, for almost surely strongly stable policy-dependent dynamics, the PSC solution exists if the sum of the distri- butional sensitivities is small enough. However, for almost surely unstable policy- dependent dynamics, the existence of the PSC solution will necessitate tempo- rally 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.
Introduction
Control theory fundamental field study in engincering and mathematics that centers on co- ordinating 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 desired manner time dy- namically. The linear state space model is a powerful tool for representing dynamical systems, which employs 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, 31, 7, 17, 28, 32] developed based on the key assumption that the system state transition model is static. However, in many real world applications, such a static dynamics assump- tion 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 ac- tions of the general public investors, resulting in famed investment gtratey-ddependee 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 be- tween prcision-making and decision-dependeen system dynamics is a pervasive phenomenon in multitude of domains, including finance, transportation, and public policy, among others.
changes to
Most of the existing works 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,
"Equal contribution.
Conresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

where policy optimization methods are employed to find the optimal control policy that minimizes quadratic costs [10, I, 11. 8]. This type of problem also includes the control of linear systems with additive dependenn 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, respec- tively. 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 hongenoogge Markov process. However, in all these works, the changes of the system model are unrelated to the control policy.
Performative prediction provides 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 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 perfor- mative 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-dependee 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 imput to the learning algorithms are independently generated based on the decision deeeeden distributions. No temporal correlation is considered or exploited between two consecutive sets of input data. However, in the context of control, the situa- tion is different as the changing system dynamics introduce various additional complexities. This is state
because the data of the system state at each time the step will depend on the decision-dependee 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 more general than the frame- work of performative prediction, and that can accommodate sequence of Decision-dependenn data with temporal correlations, where the temporal correlations are again decision deeeeddnn..eedde...
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 be- tween 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 a control-policy -epeecde 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 as- sociated 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 sen- sitivity 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 un- stable, the proposed sufficient condition for the existence of the PSC solution will place a necessary requirement temporally backwards decaying of the distributional sensitivi- ties.
We propose a repeated stochastic gradient descent (RSGD) scheme and analyze its conver- gence towards the PSC solution. We show that the scheme is convergent under the same
2

---

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 ( 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.
1.1 Related Work
Performative Prediction. The notion of performative prediction is initiated by [21], where per- formative 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 growing literature analyzing the performative prediction problem and studying the convergence of learning algorithms to the performative stable point [18, 5, 3, 13, 29J.There 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 of system state and control costs also have decision-dependen temporal correlations. Such a two- layer decision-dependen structure cannot be incorporated into the existing performative prediction framework.
data
There are some very recent works on performative reinforcement learning, where Markov deci- sion process (MDP) 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 decision-dependent linear transition kernel and decision-dependerr costs. But both the state and action space are continuous and there are infinitely many admissible state-action pairs, which beyond the scopes of [16, 24].
Stateful Performative Prediction. Note that most of the existing performative prediction works 121, 18, 18, 5, 13, 29, 5, 3, 13, 29] are non-stateful in the sense that, for any deployed policy 0, the data sample follows static distribution D (0), i.e., Z ~ D (0). 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 I (.). Specifically. the observed data distribution in [3] is time-varying and depends the history of previously deployed polices, i.c., Di+1 If (D,, 0t). Consequently, in comparison to the conventional non-stateful performative prediction works [21, 18, 18, 13. 5,3, 13, 232,, this framework is capable of encapsulating the phenomenon of strategic Docisiionmaking with outdated information, and serves as a foundation for investigations of the disparate effects of performativity (please refer 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 the disturbance-actto action control policy, which chooses the action 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-dependee nonstationary dynamics.
2 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 per- formative prediction framework of [3].
Connections between Static Stateful Distribution Transition Maps and LDS. The LDS model- ing 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 static stateful distribution transition map f (-) with D.+1 = (Dr, 0t). VI 2 To facilitate the analysis, we use a perfor- mative data sample Ze D, to equivalently characterize the performative distribution D,. If the
3

---

properties of (-) are nice enough, then from the perspective of random variables, there will exist corresponding mapping f (.) such that
Z++ - (Z. Zet1 D4+1, De, Vt 20,
(1)
where denotes equal in distribution. Linearizing f() some equilibrium point (2, with Z and ignoring the higher order terms will lead to
Zet d AZ. Bd, wW
where
ar ad (d.0) and
05 80 (2.0)
are the static Jacobin matrices at the equilibrium point
(d,0) and w f ( AZ B8. Consider the performative data sample Z,, the deployed
policy 8, and the residual w in (2) as the state variable x,, the control input action and the
additive system noise W, 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 by
X Ax; + Bu; + Wt-
Extension to Performative Stateful Distribution Transition Maps via Performative LDS. Fur- ther consider more complicated case of performative distribution transition maps fo, (-) with Di+1 Se. (De, 0,), Vt 2 O, where the specific form of the distribution transition map fo, is time-varying and depends the delployed policy 0z. Employing similar linearization for So. (-) and neglecting the higher order terms, we obtain
Zt+1 A Z, + BB, 0; + Wa.
(4)
[aee,]
@8o.
where Ao.
= ad (a.0)
and Bg,
the performative Jacobin matrices, and W;
80
(2.0)
Fo. (2 -Ao,2 7 Bo, 8. This results in an equivalent performative LDS given by
X++1 A,, x, Bu, + W...
In contrast to (3), where the system dyanmics are static, the state transition matrix Au,, control input gain matrix Bu, and additive noise Wu, in (5) are all performative and depend on the deployed control policy u,
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 result, our proposed performative LDS framework has the potential to enhance the understanding of general performative prediction.
3 Problem Setup
We consider the control of a linear dynamic system with per stage cost c (Xe, uz). control policy a mapping w IRd x1 - Rd which maps the system state x; the control action u, i.e. u, = π (xt). For each control policy π, we attribute a finite time horizon expected cost defined as
C = (xo,((A). (Ae). Σa ce (x,, u,)
(6)
where X,+1 = A,x; + Bu, + w,, the initial system state Xy follows a general distribution of DRo with bounded support ||xol| S zo. and (Ex. represents the expectation over Xo, the entire policy-dependee state transition matrix sequence {A,, 1 T) and the entire disturbance sequence [w,,1 < < 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 construct our performative LDS theoretical framework upon

---

the performative state transition matrix A,, while maintaining the control input gain matrix B and additive disturbance w, as non-pent non-porformative. This facilitates us to streamline the theoretical analysis and consolidates the system design insights.
We have the following assumption on the additive disturbances {wr, 1 111S)
A1 The additive disturbance per time step W, is bounded, i.idd and zero-mean with lower bounded covariance i.e., W. ~ D Dw: E[[s]] = 0, B(w,w, ž I²I, w| & AO I < T, and UlW, w b O, v0 - 1 + 12 T.
Disturbance-AAtton Control Policy. We work with the following class of disturbance-actton con- trol policy throughout this paper, which commonly used in nonstochastic control [10, 11, to address general convex control cost functions.
Definition (Disturbance-Action Policy). For a disturbance-action control policy, the mapping и, vo S t < T, is uniquely characterized by a set of matrices (MM(), .M At every time step such disturbance-action control policy assigns a control action u,M) in the form of
H
u; M) = x (xx)= = Kx, +
Σ M ( WL-1=
- KX, + (W
(7)
where M [ M .... M belongs to a convex set M with bounded support |[M]] F
S
M, [-]-1 short for [wT-.:-.. W < T is a constant and w, 0 for all i 0.
In the disturbance-action policy (7), we adopt a class of linear controller K defined as follows.
Definition (Strongly Stabilizing Linear Controller [1, 10. 11, 8)). Given A and B, a linear con-
troller K is (k,,) almost surely strongly stable for real numbers k 1,7 < 1, if K K, and
there exists matrices Q and such that A = A BK == QLQ with ||||| < ? and |QQl, 1l
is worth noting that the disturbance-action policy is only parameterized by the matrix M. Whereas the state feedback gain K, which is fixed matrix, is not part of the parameterization of the policy. As pointed out in [2], a typical choice of the parameter H is = =- log(T<²)). With an appropriate choice of the policy M, the control action u. 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 [10, 1, 11, 8).
Policy-dependent Dynamics. Without loss of generality, at any time step 4, the impact of the cesturbance-action control policy (M) to the dynamics of the linear system is modeled as policy- dependent additive perturbation A, a common state transition matrix A.
A2 (Policy-dependens State Transition Matrix). The distturaaneeacctionoolleee sition matrix A, takes the form of
state tran-
A =
A, ~ vO
(8)
where A is the mean value of A,, and A, is the policy-dependent state transition perturbation with zero mean and bounded support, i.e., E[A,]=0 and there exists a bounded constant & such that |A || < &. v0 < 1 < T. For different time steps i and l2, At, and A., are mutually independent. Besides, (A,, 0 (.SSS(T) T) and (wr, 0 Sttss T) are mutually independent.
Remark (Non-zero Mean D1). If the mean of the disturbance is non-zero and time-varying, i.e., E [ O., we will have a new equivalent A; A + O, with zero mean disturbances. We only need choose a new linear controller K2 such that A BK; is (Me, "te) ser-syroyyyy stabilizing. As result, without loss of generality, we assume Ds is mean throughout this paper.
5

---

Remark 2 (Policy-dependent Control Input Gain Matrix B). Note that under the DAP (7), the disturbance-action is given by BM which is linear in policy M. Such kind of linear disturbunce-action control policy has various nice theoretical performance guarantees substan- tiated in [10, 1, 11, 8J. the other hand, if B is also performative, we will have generalized which can be possibly nonlinear in policy M. Such kind of
disturbance-action B, (M)MM(( generalized nonlinear disturbance-action control policy has received very few research attention, and it can serve as very interesting future research direction.
We make the following sensitivity assumption on the distributions (D, (M),05<<1)
A3 (e-Sensitivity). For any = 0, 0, , 1, there exists a constant E, > 0 such that W (Dr (M), D, (M') S | M' VM, M,
where W (D, denotes the Wasserstein-1 distance between the distributions D and D'.
Assumption A3 imposes a regularity requirement on the distributions {D, (M), T). Intu- itively, if the disturbance-action control policies made according similar policy parameteriza- state transition perturbations should
tions M. then the resulting distributions of the also be similar.
System State Evolutions. Under the disturbance-action policy (7), the following lemma shows that the system state x, V1 S t < T, can be uniquely determined by Xu. A, M, {A,, 0 s t < T} and {Wi, H St T}.
Lemma Given a disturbance-action policy M, the system state X6, AI S S T, can be repre- sented as
f-1 A A+
1-1
A.
X + Σ II II
(Ā (A+ + +===I] BM (w (10)
X, = X;
i=0
1=0 j=it1
Σ
(1j4)
(A a5+ + )jlll) Wi.
j=it1
Besides, let the K in DAP (7) be a strongly stabilizing linear controller, the norm of x, is upper
bounded as ||xe|| < zon²a; + x² W ([]B]] HM + 1) Br, where at = -11-00 (1 7 + Rx) and
B. - D.= I| (1ja (1 - + R3 +1,=).
The performative optimal control (POC) problem can therefore be formulated as:
T Σ
(
min MEM
CM
E Ex. A. De (M)).(we)
Ce
x
(M) , i
(11)
The POC problem (11) comprises of a stochastic objective function with policy-dependent distri- butions. Due to non-convexity, the performative optimal solution P to (11) is usually difficult to obtain. Alternatively, in this paper, we are interested the performative stable control (PSC) solution:
T
PS PS = (SMP)) = arg min Ex (xoo(AA (MP)), (we) McM
Σ [=u
ce
M) x
un
(12)
Notice that PS is defined to be fixed point of the map +. Compared to the POC (11), the distribution A, in PSC (12) changes from A, ~ D, (M) to A, ~ D, (MP5). vo < T. The existence and uniqueness of PS 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 1 (0; Z), where 0 is the de- cision variable. Then the relationship between data samples Z and decision 0 is parameterized

---

Algorithm Repeated Stochastic Gradient Descent (RSGD)
Input: Step sizes {7,, S N), parameters K, H. Define MI {M: |M S M). Initialize
Mo E M arbitrarily.
1: for n = 0, ... N, do
2: Initialize J = 0.
3: fort 0,. ,T - 1, do
4: Use control u, Kx, + M, [-
5: Observe A,, Xt+1; compute noise W, = Xt-1 A,X, Bu..
6: Compute the gradient VM, Ct (Xe, U1) and update VJr t- VJr + VM, et (Xt, Ub).
7: end for
8: Update M,+1 Proje (M, 1/n JJ)-
9: end for
by fixed distribution Z ~ D (0) with fixed sensitivity E. However, in our work, the relation- ship between system state data samples x, and policy M is characterized by time-varying dis- tribution X2 ~ fe (Do (M), ..... Di-1 (M)) with a time-varying sequence of joint sensitivities (So.... _ 4A < / T. The total cost Et= Ct depends all the poliey-dependent distri- butions (Da (M), ..... Dr (M)) with a collection of sensitivities {Eo, (fo,--., These key differences lead to more complicated analysis in our work.
RSGD Scheme. We propose a repeated stochastic gradient descent (RSGD) scheme in Algorithm I to find PSC solution to (12). The metric of the projection in line 9 of Algorithm I is the ma- trix Frobenius norm. Specifically, Projæ [M} arg minMMeM |M M' Note that such projection is computationally tractable because the Frobenius norm square minimization is a con- optimization problem. The RSGD scheme first computes the stochastic gradient of the total cost w.r.t. policy Ei= M, Ct (x,, uz) and then perform stochastic gradient descent on M. The detailed steps for computation of the stochastic gradient V VM,, (x,, u,) are provided in Appendix B.
4 Main Results
This section investigates the existence of a PSC solution MSS to (12) and the convergence of the RSGD scheme to MPS. We require the following assumptions the per stage cost et [1, 10, 1, 11, 8].
A4 (Strongly Convex). The per stage cost function et (x, 1) is p-strongly convex such that
C (x1, u1) 2 a (x2, u2) + VI ct (x2, U2) (x1 x2) V (X2, U2) (ur U2) 11
[|x] - xx11= + ||u | Vxi, X2 R un U2 Rdd..
2
A5 (Smoothness). The per stage cost function ca (x, u) is smooth such that x|V (x1, un) - Vxce (x2, uz)ll || + V ue (x1, uz) Vuce (x1, uz) (||x: xx2l + In u2ll) VX, X2 e dd. u1 U2 E gdd
A6 (Boundedness). There exists a positive constant such that [|Vx0 u)]l Vuce (x, u)ll GD, | ||||| S D.
The above Assumptions A4-A6 on the per stage cost function et (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 as
T
(M) u. m
Or (M; = Exp, (A....
Σ m
ca
7

---

where, under policy M, the distribution of D, (M) to A. Dr (M') 40 f < T. For the rest of this paper, unless otherwisespecified, VCr (MMM) denote the gradients taken w.r.t. the first argument M.
perturbation is changed from A
Our main results rely on the strong convexity of the expected total cost CT [M;M] with respect its first argument M. However, the strong convexity of the per stage cost function (x, u) over the state-action space Assumption A4 does not by itself imply the strong convexity of the expected total cost CT (M; M') over the space of policies M. This is becasue the policy M, which maps from space of dimensionality
x dz X dy that of d₂ + dus 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.
necessarily full column-rand
Lemma Under AI-A6. fix any M' M, the expected total cost OT (M; M') is ji-strongly convex in its first argument M such that vM1, M2 E Md
Cr Cr (M;; Cr (M2; M\) Tr ((VCT (M2; (Mi -Ma)
/ |M Malli
(13)
where jı min {
(T- =1 (T' (T-H+13uo?
61k
For concise presentation of the smoothness of expected total control cost, we next define a collec- tion of constants as follows:
G = d 3 W (1 + (k² + R²) [BI]) (N² + +=))(1 (1-
C2 d.H
(n* nd) | c3 (HM BI 11W,, HW (1 7) c1.
05 HW (n² + +**) 71) C1-
The smoothness of the expected total cost CT (M; M') is summarized below.
Lemma 3 Under Al-A6, the expected total cost CT is smooth in the sense that, for any
M,M,, MI, M2 E M and V1 SIST, T, the following inequality holds
V (M; VCT (M2; M2)lF
T-1
|M M2ll
Σ
Et
Σ
14 JM AM-MIIA M
(14)
where d1 a (c4 +c) (c: + c2Bi) (Igez + c33:)) ;,),, 11 S tts T, and we recall that
ar = II:: (1-7+ x2,,) and 3: =
(1 (1 - 7 + x2E,) + +1,=1) from Lemma
1, which characterize the growth of the norm of system state ||x,||
Existence and Uniqueness MPS. Our first main result establishes sufficient condition for the existence and uniqueness of the performative stable policy PS that solves the PSC problem (12).
Lemma 4 Under A1-A6, consider the fixed-point iteration
M = (M,). Vn 2 0,
(15)
where the map & is defined in (12). If the following condition is satisfied
T
T
Σ
E
Σ
V
< Tt
(16)
1=
1=t+1
then iterates M,, converge to unique performatively stable point PSS at a linear rate, i.e.,
Σt-1
M, - -M < p
Et
log 1 - MP FF)
8

---

The sufficient condition (16) delivers fact that that the existence and uniqueness of M is jointly determined by all the sensitivities {E,, 0 < T in the temporal domain. The sensitivity E, at the 1-th time step is propagated starting from time step f. + to the last time step T with se- quence of weights [V++1,... vr). The aggregated impact all the policy-dependent disturbances [A,, 0 I & < } is captured by total sum in L.H.S. of (16). This is very different from the existing performative prediction works [21, 18, 3, 13, 29, 12, 19, 25], where only one distribution and one sensitivity are involved.
The sufficient condition (16) also implies that it is preferable for the initial policy-dependent distur- bance Au 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 stabil- ity on the existence and uniqueness of the performative stable solution M which are summarized below.
Proposition 1 (Almost Surely Strongly Stable Case) Let A1-A6 hold. If policy--dependent state tran- sition matrix A₁ is (K. n²² -strnngyy stable for real numbers 1, k²,, 1, v0 S < T,
almost surely. Let Ç max { 7 x2 Er,
v0 <. T), then M exists and is unique if
H. TT, where f7 min ET- & Φ0 T
2 2 and @ some positive constant.
2
G
Proposition I points out that when the policy-dependent dynamics are almost surely strongly stable, we only need make sure that the sum of all the sensitivities (st, < T} is below certain threshold.
Proposition 2 (Almost Surely Unstable Case) Let A1-A6 hold. If the policy-dependent state tran- sition mairix A, is almost surely unstable, ie., there exists a posilive constani Ç 1 such that ||A|| $
R. 2² 40 < <t<k T. In this case, guarantee the sufficient condition (16) can be satifised, we must have 1 v4 < T, where T is some positive constant.
1--1-1
For unstable policy-dependent dynamies. condition (16) will impose necessary requirement on the temporally backwards decaying of the sensitivities. Particularly, more restrictive requirements are placed the the sensitivies in the early time steps, i.c., smallt, which should decay exponentially fast w.r.t. the control time horzion T.
For more general applications, where A, be either stable unstable for different time steps, the weighted sum requirement of the sensitivities {E,, 0 < < T3 (16) is sufficient to guarantee the existence and uniqueness of the performative stable solution PS
Convergence of RSGD Scheme. Our next theorem establishes the convergence rate of the proposed RSGD algorithm.

---

Surely Dyanmics
Surely Dyanmics
General Dyanmics
10'
05 Error
PS Error
2011
Erroor
randorn escent E:
random
30
random
10'2
ascent &
ascent &
101
10
10
101
10
10
10a
101
10
10
Iterations
Iterations
Iterations
Figure PS Error
My M
Expected lotal Control Cost
450
Almost Surely Stable Dyanmics
random &
Expected Total Control Cost
Almost Surely Unstable Dyanmics
Expected Total Control Cost
200
Generel Dyanmics
rendom
3000
ascent
600
aso
descent
descent 4;
descent
aco
250
ac0
2200
300
150
1002
200
100
1c0
30
Iterations
Iterationn
Iterations
Figure 2: Expected Total Control Cost Or (Mx; My)
Theorem 1 Choose two positive constants Φ1 > O and Φ2 2 conditions satisfied simualmeeusly
such that the following two
j --- (ct (EEEt
Φ1 < min
1
(17)
22
2 ET= i=
de + Et=
Et Ei=ct v)) 1 Σtz
(e 1s)
2
2
(18)
1+
Ee ET= 1/5 Et=o
T-1
92
Consider sequence of non-negative step sizes 9n n+02"
$1
n 0}. Then, the iterates gener-
ated by RSGD admit the following bound for any N 2 1:
[IIM - -MP5 [1
(Z- (E+ Eistto M: 1) || - -M + IN
Ø3
Se
N (19)
where Dr = K (HHW +x²) x. [B] +1) (sear + c3Br) + GHWM (k3 + 11) VI, 5Is
TTT 83
T, and d3 = 7- --- 2h)
is a positive constant.
Note that, under the sufficient condition (16) in Lemma 4, there always exists pair of (Ø1, 22) that satisfies (17) and (18) simultancously by letting Φ2 be sufficiently large. The first term on the R. H. of (19) decays at the rate O(e ΣN (ī Et= (s. Σlz4 *))) m))) and scaled by the initial error E M M The second term is fluctuation term that only depends the variance of the stochastic gradient, which decays the rate O (1/N). For more general types of step sizes and the associated nonasymptotic convergence rate analysis, please refer to Lemma in the appendix G.I.
5 Numerical Experiments
We consider an application of stock investment risk minimization problem to verify our algorithm and theoretical results. Consider an investor trading total number of stocks over a period of T 60 trading days. The detailed system setups are described in Example I in Appendix
10

---

A of the supplementary. We compare the performative error (PS error) MN M [ and the expected total cost CT (My; Mx) against the iteration number N, respectively. We consider fixed distributional sensitivity value set e = fes, i = 0, . T patterns of the sensitivity sequence εд descend (e), E. = ascend (e) and &, random (E) in descending, ascending, and random order, respectively, over the time steps. We first observe from Figure/ (left) and Figure (left) that when the policy-dependent system dynamics A,, 44 S t < T, are almost surely strongly stable, the gap |M - M three different patterns Ed, Ea and all decay at O (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 only requires that the sum of the distributional sensitivities -1=0 E, is small enough, and the temporal order of each E, is negligible. We next observe from Figure (middle) and Figure (middle), that when the Ar, V0 S t < T, are almost surely unstable, the iterates M,, of both Ed and E, diverge. The expected total control costs associated with éa and Er are significantly larger than that of ea. This is because large initial distributional sensitivities in Ea and E, rule out the existence of MPS, which matches Proposition 2. For the general case of A, in Figure I (right) and Figure 2 (right), all three cases converge due to the relatively mild sufficient condition (16).
1). We assign three different
Conclusion
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 temporally backwards decaying of sensitivities for almost surely strongly stable and almost surely unstable systems, respectively. We have also proposed
the sum of the distributional sensitivities and the
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 [ef. A4], will be explored in future work.

---

References
[1] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111- 119. PMLR, 2019.
[2] Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Ad- vances in Neural Information Processing Systems, 32, 2019.
(3] Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in a stateful world. In International conference artificial intelligence and statistics, pages 6045-6061. PMLR, 2022.
[4] Hugo Carlos, Jean-Bernard Hayet, and Rafael Murrieta-Cid. An analysis of policies from stochastic linear quadratic gaussian in robotics problems with state-and control-dependent noise. Journal of Intelligent & Robotic Systems, 92(1):85-106, 2018.
[5] Dmitriy Drusvyatskiy and Lin Xiao. Stochastic optimization with decision-depenndnt distribu- tions. Mathematics of Operations Research, 48(2):954-99) 998, 2023.
[6] TE Duncan and B Pasik-Duncan. Stochastic linear-quadratic control with state dependent fractional brownian noise and stochastic coefficients. PTAC--PppesOOnLin,, 50(2):199-222 2017.
[7] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International conference on machine learning, pages 1467-1476. PMLR, 2018.
[8] Udaya Ghai, Arushi Gupta, Wenhan Xia, Karan Singh, and Elad Hazan. Online nonstochastic model-free reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
[9] Benjamin Gravell, Peyman Mohajerin Esfahani, and Tyler Summers. Learning optimal con- trollers for linear systems with multiplicative noise via policy gradient. IEEE Transactions on Automatic Control, 66 1):5283-5298 2020.
[10] Ben Hambly, Renyuan Xu, and Huining Yang. Policy gradient methods for the noisy lin- ear quadratic regulator over a finite horizon. SIAM Journal on Control and Optimization, 59(5):3359-339. 2021.
[11] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorith- mic Learning Theory, pages 408-421. PMLR, 2020.
[12] Zachary Izzo, Lexing Ying, and James Zou. How to leam when data reacts your model: performative gradient descent. In International Conference on Machine Learning, pages 4641- 4650. PMLR, 2021.
[13] Qiang Li and Hoi-To Wai. State dependent performative prediction with stochastic approxi- mation. In International Conference on Artificial Intelligence and Statistics, pages 3164-3186. PMLR, 2022.
[14] Qiang Li, Chung- Yiu Yau, and Hoi-To Wai. Multi-agent performative prediction with greedy deployment and consensus seeking agents, 2022. URL https://arxiv. org/abs/2209.038) 03811..
[15] Rui Liu, Guangyao Shi, and Pratap Tokekar. Data-driven distributionally robust optimal control with state-dependent noise. In 2023 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 9986-99911 IEEE, 2023.
[16] Debmalya Mandal, Stelios Triantafyllou, and Goran Radanovic. Performative reinforcement learning. In International Conference on Machine Learning, pages 23642-23680. PMLR, 2023.
[17] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
12

---

[18] Celestine Mendler-Düiner, Juan Perdomo, Tijana Zmnic and Moritz Hardt. Stochastic opti- mization for performative prediction. Advances Neural Information Processing Systems, 33:4929 2020.
[19] John P Miller, Juan C Perdomo, and Tijana Zrnic. Outside the echo chamber: Optimizing the performative risk. In International Conference on Machine Learning, pages 7710-7720. PMLR, 2021.
[20] Stefanos Nikolaidis, Swaprava Nath, Ariel D Procaccia, and Siddhartha Srinivasa. Game- theoretic modeling of human adaptation in human-robot collaboration. In Proceedings of the 2017 ACM/EEEE international conference on human-robot interaction, pages 323-331, 2017.
[21] Juan Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt. Performative pre- diction. In International Conference on Machine Learning, pages 7599-7609, PMLR, 2020.
[22] Huyên Pham, Marco Corsi, and Wolfgang Runggaldier. Numerical approximation by quan- tization of control problems finance under partial observations. In Handbook of Numerical Analysis, volume 15, pages 325-360. Elsevier, 2009.
[23] Joaquin Serfoonero-Candele Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2022.
[24] Ben Rank, Stelios Triantafyllou, Debmalya Mandal, and Goran Radanovic. Performative re- inforcement learning in gradually shifting environments. arXiv preprint arXiv:2402.09838, 2024.
[25] Mitas Ray, Lillian J Ratliff, Dmitriy Drusvyatskiy, and Maryam Fazel. Decision-dependen risk minimization in geometrically decaying dynamic environments. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8081-8088 2022.
[26] Benjamin Recht. A tour of reinforcement learning: The view from continuous control. Annual Review of Control, Robotics, and Autonomous Systems, 2:253-279, 2019.
[27] Roberto Renò. Nonparametric estimation of stochastic volatility models. Economics Letters, (0(3):3903995, 2006.
(28) Harish K Venkataraman and Peter J Seiler. Recovering robustness in model-free reinforcement learning. In 2019 American Control Conference (ACC), pages 4210-4216. IEEE, 2019.
[29] Killian Wood, Gianluca Bianchin, and Emiliano DallAnese. Online projected gradient descent for stochastic optimization with decision-dependee distributions. IEEE Control Systems Let- lers, 6: 1646-1651, 2021.
[30] Farnaz Adib Yaghmaie, Fredrik Gustafsson, and Lennart Ljung. Linear quadratic control using model-free reinforcement learning. IEEE Transactions on Automatic Control, 68(2):737-752, 2022.
[31] Peng Zhao, Yu-Hu Yan, Yu-Xiang Wang. and Zhi-Hua Zhou Non-stationary online leam- ing with memory and non-stochastic control. The Journal of Machine Learming Research, 24(1):98119990) 2023.
[32] Hongyu Zhou, Zirui Xu, and Vasileios Tzoumas. Efficient online learning with memory via wolle optimization: Algorithms with bounded dynamic regret and applications to control. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 8266 9266-8273, IEEE,
2023.
13

---

A Application Example and Experiment Detail.
In this section, we elaborate 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 (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 period of trading days. The observed market price s) of the n-th stock at the t-
th day follows a stochastic volatility model log ( = log (1)
(o.
T + (.
VT 0,Y1
t < <,, S S L, where r >> 0 is the riskless interest rute per day, Ut independent random volatility process and the constant initial stock price associated with the 1-th stock, respectively [22, 27]. Let (1) and q) be the the total return at the t-th day before the market opens and the initial investment associated with the 1-th stock, respectively. The investor maintains a portfolio for each Di which is parameterized by a row vector in [m²l
(1) and 8 are the unobservable
: ;' mm with m² [0,1]]v] v1 S i S L, being the weight of allocation and Eimmm' = 1. Specifically,
at the 1-th day when the murket opens, the investor immediately allocates qi proportionally to buy the N stocks according to the weight vector m!!), The total systemic risk associated with gi during the period between the t-th day right before market opening and the +t+ 1)-th day right before market opening is Eí (m'"w( h)) + +1- wi+1 (24 (24-h), where w is the per hour risk associated with the i-th stock in the 1-th day and h is the total number of trading hours per day. is Slim! (1-2 + + (1)
VT )
)--
The investor then spends all this amount to buy
back the 1-th stock and then the 1-th trading day ends. Each stock in the porifolio suffers from proportionate random ii.d systemic risk wi per hour, i.e., holding the i-th stock with ratio of me in a portfolio for a total number of h trading hours in the t-th day will incur a systemic risk of
me-" h. Denote the mean-shifted return r. = q: - [qr] and let Xx
Pt
qi
The evolution of x, can be characterized by the canonical form of
X++1 (A + A.) X + u, (M)
+ W.,
(20)
u, MW:11 with B = I,K 0, <t<
(M)
(21)
where
M
(L) Wi-1
(24 h) w
(1)
w
(L)
T
W;
W,
E [we]
the state transition matrix A I2LX2L and the
state tran-
sition perturbation A is given by (22) and (23).
(M)
V -E (M))
E
IXLL
A,
(22)
v((M)
0 O11L
Ix
{
(1)
+
v.M) diag
Σ
mlide
(23)
The investment risk minimization problem can thus be casted as
[[, xel12 [ OrxI] u (M) (()
min MEM
CM -E
8.l. (20)
- (23).
Tackling (11) leads to an optimized stock investment policy M which takes the effects of policy- dependent random perturbations to the dynamics of stock returns into account.
14

---

In the simulation, we set the number of stocks L = 10 and the number of trading days T = 60. The initial policy Mo is randomly chosen within the feasible set M (M >i= m 1, v1 < I S 10}. The entries of noise term W, are independently and uniformly drawn from the interval
[0, 1]. For each 1 S - 10 and each 0 S 60, we first obtain et by sampling from a Gaussian distribution, i.e., 02 ~ N (log(E))), 0.2), where E, denotes the sensitivity at I-th trading day. The ot is then projected to the interval [-0.6, 0.6] to obtain ot in (23). We let the total number iterations N 1000, and the stepsize 7/ in Algorithm is set to be 0.01, VO S n S 1000.
The sensitivities are shown as follows:
Sensitivities with Ascending Sequence.
<,=[11257997776607 5.03189910c-07 1.13217730e-
06 2.01275964c-06 3. 3.14493693--06
4.52870919c-06
6.16407639c-06
8.05103855c-66
101895957c-05 1. 1.25797477c-05 1.52214948--05 1.81 181148367c-05 2.1597777005 2.46563056e-
05
2.83044324e-05
3.22041542e-05
3.63554710e-05 4.07583827e-05
4.54128893e-05
5.03189910e-05 4.66004175e-03
5.35796616e-05
6.12231163e-03
6.95609731e-03 7.86234234e-
03 8. 8.84406585e-03
9.90428699e-03
1.10460249e-02
1.22722987e-02 1.35661276-002
1,49905306e-02
1.64885270--02
1.88831388-002
1.97773762e-02
2.15742674--02 2.34768284e-
02 2.54880785e-02
2.76110367e-00
2.98487222e-02
3.22041542e-02
4.335043976-02
4.66004175e-02 5.00089002e-02 5.357966 5.73164756e-02 6.12231163e-02 6.53033575e-
02 6.95609731e-02 7.39997371e-02
7.86234234--02
8.34358059e-02
8.84406585e-02
9.36417552c-02 9,90428699c-02 1.04647776e-01
1.10460249e-0
1.16484061e-01
1.22722987e-
01 1.29180801c-01 1.35861276-011
Sensitivities with Descending (aguueece..6l(11386811111111
1.29180801e-01 1.22722987e-01
1.16484061e-01 1. 1.10460249--01 1.04647776e-01 9.90428699e-02 9.36417552e-02 8. 8.84406585e-
02 8.34358059e-02 7.86234234e-02 7.39997371e-02 6.95609731e-02
6.53033575e-02
6.12231 112231163ee 163e-02 5.73164756e-02 5.35796616e-02 5.00089002e-02 4.660041155-02 4.335043977
02 3. 3.22041542e-02
2.98487222e-02
2.761 10367e-02
2.54880785e-02 2.34768284e-02
2.15742674e-02 1.97773762e-02 11888883358-022
1.64885270e-02 1.99903306e-00
1.35861276e-
02 1.22722987e-02
1.10460249e-02
9.90428699e-03
8.84406585e-03
7.86234234e-03
6.95609731c-03 6.12231163e-03 5.35796616e-03
4.66004175e-03 44571966666444444444444400030033
5.339990005 4.54128893e-
05 4.07583827c-05
3.63554710e-05 3.22041542e-05 2.83044324e-05
2.46563056c-05
1.15977776-055 1811483667-055
1.52214948e-05 1.25797477--05 L01895957c-05 8.05103855e-
06
6.16407639e-06 4.52870919e-66
3.14493693e-06
2.01275964e-06
1.13217730e-06
5.031 103189910e-07 T.T.0.....777771 1.25797477e-07)
Sensitivities with Random Sequence.
c,=12.548807856-02 3.63554710e-05
2.34768284e-
02 1.64885270e-02 1.257974776-07
9.36417552e-02 1.10460249e-02
6. 666447669--06
2.761103674 5.00089002e-02 1.16484061e-01 1.04647776c-01 2.15742674e-02
2.65633566-
05
3. 3.14493633--06
4.66004175e-03 4.54128893e05 3,22041542e-02
1.227229876-02
4.33504397c-02 8.84406585e-03
6.95609731e-03
5.03189910e-0S 1.01895957c-05 7.39993371c
02 1.97773762--22
7.86234234c-02
1.35861276e-02
8.84406585e-02
1.22722987c-01
4.07583827c-05 8.05103855e-06 2.98487222c-02 9,90428699c-03
6.95609731e-02 8.33550059
02 6.12231163e-03
1.81148367e
1.5.:05551111111111111 1.52214948e-05
2.12597737e-05
6.53033575e-02
5.031 5.03189910e 89910e-07 5.35796616e-03 9. 9,90428699e-02 7.86234234e-03
1.10460249e-01 4.66004175e-
02
2.83044324e-05 2.01275664-066 3.22041542e-05
1.13217730e-06
6.12231163e-02
5.35796616e-02 1.49905306e-02 1.25797477e-05 1.80831358e-02 4.52870919e 1.35861276e-
01 29188801e-01 5.73164756e-02]
The non-ordered lists of sensitivity values in epsilon Ea,Ed, and e, are the same. The state trajectory
x₁ and control action u, are generated according to (20)- (23) based on the above system parameter configurations.
B Auxiliariy Lemmas for Per Stage Cost Function
In this part, we provide several lemmas to characterize the gradient properties and the smoothness of
(x(M) .,
(M)
(M)
the per stage cost ct. We first summarize a collection of notations. We denote Vx
and Vuci (x, (x(M) u, (M)) as the gradient of & w.r.t. the system state x (M) and control action
15

---

ui (M), respectively. We denote VM (x(<), u ) as the gradient of et w.r. the variable M
in x, (M) and u (M) under any given realization of the policy-dependent state transition perturbations [A,, 0 <i<t).
Based on the chain rule and the relationship between M and the pair (xt, uz) in (7) and (10), the expression of MMG (x!_ u, m is given by
VM x2 : u. )
(24)
II (مجز A (A+ + +1)=d) B 1=++1
Vxa x
_ m (Iw](-))
K Il (i (A+ + 11 B
Vuci Ex/mauf u(mo) (lwl(1)
jmit1
+ Vuce MM ,
(w](- )
For the ease of notation, without ambiguity we also occasionally use the notation C. M: (A: Josiet) to denote C (x(M) .u (M) under a sequence policy-dependent state transi-
tion perturbations {A,,0 0 S < f) this case, VMC, (M; (Aitosie) the first argument M.
denote gradient taken
Moreover, the total cost function can be represented as
T = Ea (M: (M:loiiosict)
JT (M; (At
(25)
1=0
is clear that
CT (M:
Jr (M; (Aetogeer)
(26)
Unless otherwise specified, VJT (M: (M: (M: and VCT (M; M') denotes the gradient taken w.r.t the first argument M. Convexity. Denote the per stage expected cost
fe (M; M,) = Exo, Exo,(A,,D, (Ma)) [a ( (aitsscc))) v1 ST
where the distribution of policy-dependent perturbation is changed from A, D, (M) to A;
D, (M2). YO < <
We have the following lemma characterizing the convexity of (M; vI VI
Lemma B.1 The per stage expected cost ft (M: is a convex function of M, YM, e MI, VI
Proof. We prove this lemma following the convex property of the function e (x, u) in Assumption A 4. Let 0 < 0 and M,, M2, M' E M. Consder the weighted policy 0M, + (1 0) M2,
16

---

have
[-) 1-1
(0M (1
II
(A+
Σ II (1jce (A+ + ()-rd B (27)
xo +
1=U
1=0 j=it1
(MM) + (1-
M2) M
Σ
II (1jer (A+ + +1,-1) w;
j=i=1
0
A+ ,.) Xo +
I j0
1عac (A+;;) + ) BM, [w],-
1i3t A + wi + +(1-0)
-=+
A A.)
Xb + II (1ęce (A (A+ + +15=1l BM2 [w]
==j==it
Σ II 1ist A + و,) + +1 wi
1= f=1+1
= 0x M + (1 - 0) x M.
As result,
(0M, 01 M2
(28)
xx] (xMM+(1-0)MM)
u, (Mi (M1
(1-0))2)
(DxMi + +1 - () MM Au + (1 0) u
(D (28.a)
< Exo. (MO fwasoia Ocs (xM1 , uM! + (1 - 0) (xM²* m.Mi
= =0 (M,; M + (1 0) fe (M2;
where inequality (28.a) holds becasue of the convexity of (x, u).
We next have a key lemma characterizing the strong convexity of ft (M: IA S1ST.
Lemma B.2 The per stage expected cost Je M') is min { M, VM, M' E M, HH T.
2O22² 64
-strongly convexfunction
Proof. We prove this lemma following the strong convexity of the function e, (x, u) in Assumption A 4. Let M,, M2, M' E Ml. Consider time step such that H < l T. For any given realizations of ( (Ai) where A; ~ D, (M'), vO < i < I, we have
(x) (Mi) (M1) ai (x, (Ma)
u, (Ma))
u;
(29)
(29.a)
Vxce
(a)
us (Ma))
1
T
x (M,)
(M²) (M,)
x (2)
(Ma)
2
x;
x
Vuct
(M2) un (Ma) x;
u,
u,
(Ma)
+
2
(M)
u1 (M))
where inequality (29.a) holds because of the strong convexity assumption of c, in Assumption A4.
17

---

Based on the representations of the pair (x,, uz) in (7) and (10), it follows that
xi
(i))
x
(M2)
Σ
II
(15c
A + )1) 1)=(1) B (M1 M2) [w];-1
(30)
i=0 j=it1
1-1 1-1
u1
(Mi)
11,
(M2)
Σ
II (jjct (A + A5) + +11=11) B (M1 - -M2) [w]
(31)
==0 ==
+ (MI M2) [w]
Therefore, we obtain
Vxce xi
(M2) (M2))
x (M2) u, (M.)
(M1)
x,
(32)
Vuce (Mb) ui (M2))
u, (M2)
1-1
cx x
(112)
ui )
(1jcs (A * + +1,=t) B (M, - M2) /w],"]
1=
1-1
VITco ct
{x M2) 1 )(Misl
Σ
II (1K3r (A+ + +1 B (M1 M22 (
1=0
+ (M1 M22 (w]
[-1 II (1jze (A (a+ + +)==I) B (M1 -Ma)
w Vi (x: (M)) (Ma)
= =Tr
u,
j=it1
t-1
+ Ir
[w]
11
o (xttai)) (Ma)) u, (Ma))
K II (1jce (A+ + +1,=d) B
s=it1
[w] |-1
H
V.l ct
x
(M2)
u n(Ma))) (M1 10--M -Ma)
TT
ViM.et
Cr
{
(M2)
u ((aa (M, M2))
Substitute (32) back into (29), we have
(Mi) ae ( ue ((Ma.i) es (x(Ma)) u, (Mao)
>Tr (Vir ct (x(Ma), u ((aaa)) (M1 - M2))
(33)
/ [xx x1
(Mm) { in (iw u. (Mab)
2
Taking full expectation on both sides of (33), it follows
fe (M, fo (M: 2 IF (V f (M;; M' (M, - -M²)
(34)
+ 11 "xxo. "xo.(A,
|| (MMM)) x (2) ((2b) + 11 u
(Mi)
(M.) 19]
2
18

---

We next analyze the last term in (34). Consider the conditional expectation on {w; hos as follows
x [ xi {(Mw)) + | | u
(M:)
(M.))
Ex., (MM)) losici ( (wetosict
(35)
| (M(MM)) - -x, x(Ma))? + | (ufuar) u {mai)
-Biwclasset
(wstoster
w
2 B( B(wilasser
X4
(Mi)
x
(aai)
(w: (wilosies
+ Bx0 (iDD
ui ((11) - u; (wetosics)
(Maa
2
(35.c)
Eiwilosiet
Σ A'B
AMBM. (M, M2) [w] -Ma)
+ K 1-1 _ A'B (M,
M2) w| (M1 M2) W 11
where (35.a) holds becasue E | v0 St TT
We next consider each term on R.H.S. of (35.a). We notice that
VCc
Σ
h-1
AMB - M2) [b]
Σ (ww)=-)) )'o & (A'B) vee (M, vM,(M,
-M2) (36)
Therefore.
E(wilogier
Σ
AM, M2) [w] [w]
(37)
Σ (w](-1)
(A'B)
Σ
(w](-,) ) (A'B)
8M
= 3M
An (A"-LB)
A 1
2 E [.w.]] dM
J (((I & B v (IH s B)) & E (..,]) δM:
where 5m vee (M1 M2), A HRH with [Aele 1 if and only if - j I and otherwise
and V/- = E1 Eig=1 (An & (A Ab-1B)
Using similar approach, we can obtain
B Bowchossee
K AB M&) [w]]"] (M, - M2) [
(38)
1=0
=oM ((IH (111BBB) v (In & B (In s B) - (In @ B B + +IH.
TT
8 E [[:ww.]]] 8m.
T
where T Ei Eiy=1
(Ai-ts & (KĀ" K BB) and
(IN 2 K &
(ELLA 1, 00 (A (A-IB)
Substitue (38) and (37) back into (35), it follows that
|x4 |x(Mi) (M))
x; [Ma)]1
+ nn (M.) (22) 1
(MooMMM))rroeoett (wibogrer
m
(39)
= 55 (Ω & E W.w,]] 8M.
19

---

where
Ω = (Ix BB)
(IH B) (I B v [I B
(40)
- (TH @ B) [I & B θ T + Idd.-
Based on Lemma F.I and F.2 [2], we have, AH S S U
Tn Ina, and |||]| S ~ー
1
Therefore, if || < B|| 2 4x then
(
M 4xa
Htds
64x Hdz
(41)
4x²
Otherwise, if || 00 B|
4x then
Ω Itd.
- 0
(I
B)
(In
B o 1
BOOTT,
(42)
| ž 1 - - 1
7
(43)
4x
4x 2
Combine (41) and (43), we have ||ai|| 2 min
(2
:क j. As result,
22
Ex.. (MM
|| x, (Ma)
2
+ 11 (MM))
(1(aai-- - ((Ma)1 -u
(44)
{ o2 7202
} |IM Mall
-M (2 & E [ww, 5M 2 sm //2/ o² min
2 64k
Substitue (44) back into (34), it follows that
ft (M1; M') - fe (M1; M') 2 Tr (V fe (M;;M) (M, - M2))
(45)
min
2 "h
M M22lE
2
Therefore, Lemma B.2 is proved.
Properties of Gradient. The following lemma provides upper bounds for the norm of gradients
Vxce Xi : [ and Vncce (x (M)
(M)
u, (M))
(x(M), u, .nf))) VI S T, satifies
Lemma B.3 The gradients of the per stage cost et
VzG
x .
(M)
(M)) s ann GW (| HM 1) 3r,
(46)
Vuce
Xt
(M)
_ m | S won' Goy + +W (B HM + 1) 3, + GMHW,
u
(47)
where 1 (1 - - (x) and Br E 11 (1jer (1 - - + x x²) + 15=t)
Proof. obtain
We first provide upper bounds for |xell and ||ue|| From the evolution of x, in (10), we
1-1
A + -.) x + E
|x,
<
II i=0
[1jc
AA + )3) + +1,-1) BM (W
(48)
1= j=it1
H- 1-1
[-1
+
Σ
(1ر3)
A + +1f=رl) wi
5 x
(I - + 2 ||A.I)
j=it1
i=0
H 1-1
+ 2 W
B
HM + 1)
Σ II |a (1 - 2
A I|)
+ 1 1
0= j=1+1
| || < Φ | || + MHW.
(49)
20

---

Lemma B.3 follows by noting that || A S Se. v4 S T.
vM E M, and whenever |xxel: | -
D, we have
Vxcr
[x (M)
u
(M)
|| Vucr (x+ (M)
u (M) S GD.
(x/ in m is bounded.
We next prove that the variance of the gradient VMG
Lemma B.4 There exists 0, > 0, LA < T, such that
Ex.. (Mo V/Ver (x(o0) un )
(50)
VMMCE (x3 (x)
un ((a)) )11
S de.
-
Proof. Based on the expression of VMG (x; u, m(ae) in (24), we have
Vinc (x:
)
(51)
B HW
Σ
II 1i3c A (A+ +,) + +1-=11)
Vxee (x(M) un (iy)
1m+t1
+ [B]
1isce (A (A+ + +1==1)
|| (x) un ,uf )
1=
+HW Vucee
(M)
xx
S x2 [B]| HW 3t |x02
(x{ u aMMi) (N** [n= BB| By + HW Vuci (xfa u )
(51.))
< (ss B| HW B. + x B|| Br + (Io Ga + K GW (| HM + +)
+ (M* B B. + GMHW,
where inequality (51.a) holds becasue of the gradient norm bounds in Lemma B.3.
Further note that
E || VMic (x(00) , 1 (nl - E [ViCe (M) u ((M)
)11 SE E || (x(M), .u ((a))
122
(52)
VMC (MM)) in (M))) )(²
s de HE
The desired result follows by substituting (51) into (52) and letting
0. H ((x [B| HWS, + x [BB] B 1) G Ga, &W B HM 1))
(53)
3 B + 1) GMHW))
The next lemma characterizes the difference between the gradients under any two different polices M and M'.
21

---

Lemma B.5 For any given two policies M. M' E M. the differences between the gradients satify,
A1 ST.
Xx (x) .ul m -xxe Xi an ( (M),
(M')
+ Vuce (xxM²) u. ) - Vuce (xx (M))
x (
: u )
(54)
$ ((1 + x)) H.?.. + HW) |IM M'I
+ + x) x² (1 (1- (snae ([]B]| HM HM 1) (.)
Σ IIA - Alll,
where A; and A 4O S < t, denotes the policy-dependent state transition perturbations under the policy M and M', respectively.
Proof. Recall the smoothness of the cost function a (x, u) in A 5, i.e.,
Vxxe (x1, uz) - Cxct (x2, uz)Il + V/uce (x1, uz) - Vuce (x2, u2) S (||xI x2|1 + | u2
(55)
To prove Lemma B.5, it suffices to quantify
(Mr) (M) x;
and (M) 11
(M))
Based on the evolution of the system state x;
MM)
we have
X x;
(M)
(M')
Fr + F2 + Fs,
(56)
where
(A+ +.)
- II
AA -i(():))) xo.
E
(57)
1=0
==0
Σ II (1 A + 1i) +1,-d) BM [M[WW
Eg-
(58)
j=it
Σ
II (1ر²
(A+ + +1 BM (w
b=
A A)+ + )
II j=it1
(1,4 (A+ + 11=11) w. (59)
j=+t1
We next analyze each term in (56) one by one. Specifically,
II 1=0
(A+ 4:)
| xо
A + A.)
(60)
1=0
A + A.+ + 1 (A. A (AI-))) II A
< <00
(Ao
2-2
+ A!) (A 46-1 1
+...
1=0
t-1
+-1
S sngh (1-7)-1
(1 11 + x26,
Σ
A - AIl
i=
1=0
1-1
znhi" (1 - -1
A ALI
1=0
22

---

For the term Eg, we use the similar approach for analyzing E₁ in (74) and obtain the following bound
E2ll
(61)
A ,1) +1 B(M M')ww""
BMM-M')
1jar A ( +1
II (1 (A+ + 11-1)) BM [w] j=i+1
j=i+1
HWB, IM M'
+ +|| MHW
II
[1 A + 4,) + (==d
II
(1 A (A+ + +1
=++1
j=++1
(61.))
I HW3 | M + x (1 --) MHW 3:
A All,
where inequality (61.a) is obtained by using (76).
Finally, still using (76), an upper bound of || || obtained as follows
|| F3
SW
Σ
f-1
II j=i+1
(A+ + A;) +1,-1)
II j=++1
[-1
(1 (A A3) + 15=1)
(62)
W Be 1-1
SK² (1->)
-IA.-A
1=0
It follow directly that
(M) (M')
x x
1 |E + ||SS|| + ||al||
(63)
R HWB, M - M + (1-1)~1 (ooa, [[ HM 1) WB,) Σ | All
We next observe the relationship
(M)
u,
(M))
=
- Kx (M)
+ KX (M') + M [w]]" - MM' [w]"
(M')
(64)
< K
x
(M)
xi
(MM')
HW -MMMII
Therefore, follows that
x x, +
(M) (M')
+ u un [Mr)
(M)
S 511 xz)
x. x,
(Mr)
HW | -MIl
(65)
S ((1 + k) 152 HHWB+ HW) I|M-M MM
1-1 -
(1 + k) n (1- -1-7) -) (ooar + B HM 11)
Σ
-
1=0
Combining (65) and (55), obatin the desired result.
Smoothness: We analyze the smoothness of the per stage cost and the per stage expected cost the following Lemma B.6 and B.8, respectively.
23

---

Lemma B.6 The per stage cost function et (M: (Arlosses) 11 S is smooth the sense
that
Virce (M: (1: (Aississ
Vniree (M'; ( (o0sks)))
(66)
A | | M
Σ
| -illp
==
where
A = W (1+ [B]| (K + x*) ((<2 + n²) 3r 1)),
(67)
d, H <HW (1 |B| (K² + k²)) (k² + n²)) (1 -) + G (1-))
(68)
(k* + xx²) HW [B]] B,) (Tna, + (|] HM + +1)W3,),
and A; and A,, policy M and M', respectively.
40 < < t, denotes the policy-dependent state transition perturbations under the
Proof.
We prove this lemma based on the smoothness of the cost function et (x, u) in 5, i...
Vxxe (x1, u1) - Uxct (x2, uz)ll + Vuu (x) Vuce (x1, u2)l
S (1|x xx2l + |u uzll)
(69)
Based on the expression of Me (M: (A, (ososse))) in (24), it follows that
Me (M: (D (olosss)) - V.r.ce (M: I Fi F2 F2 F3,
(70)
where
T
[-1
II (1s< (A+ + +1 B أ=ا=
Vxce ()) un (M))
F
(71)
0
T
II (Izce A (A+ + +1 B
(M')
u. _(ar))) (lw)"1))
Vxc x
j=it1
1-1 K II (1ier (A+ + 1)=n)
Vxce (xx_)) (
F2
(72)
j=i+1
KKK I[ (1jec (A+ + 1 B
Excr x u ((()))
(Ma))
(wm)"-))
j=i+1
x (Mi)) Vuc (M)) . u (bre)) (w))t))
F3 Vuct (M) u
(73)
24

---

We next analyze each term in (70) one by one. Specifically,
T
|i
(1icr (A+ +ljaol) B
Vxer (x(M)) un )
(74)
j=i+1
I
[トري (A ( +,, + I===1] B
Exar x; (NT) uu ((rr))
Vxc (MI' ui (m²))
(1jst (A+ +lj=r) B
/=++
T
1 A 11) + +1,=1) B
Vxa xx (MM)) in _(orr)
(wm)"1))
(74.a) < HW [B] x2 31 Vza (x(M), u; mM Vxa
(M²)
. ((rr)))
(M)
X
HW
B 2 Goo + GW (|[B) HM + 1) Bc)
Σ
I 1 (Ą+ + +1,-!) - II
(1jar AĀ + 2/) +1
j=+t
where inequality (74.a) holds due to the definition of B, and the upper bound of Vxce x, (Mr) , u )
provided in Lemma B.3.
25

---

For the last term in (74), we first observe that
t-1 II
πI /=1+1
jest
A (A+1/)
(1sst A ( + 15-11)
(75)
s=i+1
(A/m)) Ait1)
II (Ijet A + 43) + 1== j=H+2
(A A.11 (A/12 A1t2)
II (1iec A + A3) + +1 +...
jmi43
1+1#
+
II
[Rae A A1) Is-el) ( (Aitit4t1- - -A+1+441)
II j=++1+142
(1jar (A +1) + 1--11)
k=i+1
t-2
1ket (A+ As+) + + 1
k=++1
(1yer (1-7+ x²t;) + 1 (K²1 Amill (1-7+ + x² ((+1))
-
+1+1+1 - A 1+11444) (1 7 + x² *++++411 +...
A ||1// (1-7+ + 122 (1)) )
1-1
(Lier (1- + 11=1)
Σ
x² (1-7) (1-7)~1114 - A
|=
kmi+1
1-1
II (List (1-7+ + 1
Σ =1 | - Axll-
|=
k=0
As result,
[-1
1 jja A A + +1
II
[ij A A,) 1==1)
(76)
j=itl
Σ
II (1je( (1 - n²E5)) 11=11)
Σ x2 (1 -) 114 -Ae1)
1-1
= (1 (11-))= 7) 3e Σ - - -il..
==0
Substitue (76) into (74), it follows
|| SHW [B]| [B|| 23,3, 3,
(1TTse) (x(M)) u. mM) VxCr
(M)
(M) (M))
xx
, u ((or)) )
(77)
[-1
Σ |a - A.l)
+ Gzo + GW B| HM + 1) B.) 32) (1 -
==
The upper bounds for |E and |Es] can be readily obtained as follows
|E < kHW
B B, ()) V (x(m²)
(M) . uu
Vxcr
(MM)
[ , ,u _,(( (1m)
(M')
(78)
t-1
+ (I + GW [|] HM + 1) R2 (1- 7)
Σ | - A.1l
0
26

---

and
Vnce (M u, ) Vncct
(M) (Mr')
|aall v HW
xx
u
(79)
Substitute (77), (78) and (79) into (70), have
VMcce (M: (Aslogiee) Virce (M': ( (osice))
(80)
s (1 + |B]] (1² + 1² HW (/|scc (x(_e), _n, ((M))
(x(rrt i (
(M²)
Vxct
X,
+ Vuce [x, u w Vuct u (())
1-1
+ 3c
Σ
| A.l
t=0
where 3. = 01 -1- (x=2 ( x5) HW [B]] Br (on + GW (I HM - 1))
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].
Lemma B.7 (Kantorovich-Rubiin and only for all M.M' E M.
(Lemma D.3 in (21])) A distribution map D (-) is e-sensitive
sup [ A(MM)) L (A)] AAADDM l (A')): : Rd.xd, &R.g Lipschitz M |
(81)
The smoothness regarding the expected per stage cost is summarized below.
Lemma B.8 For any M,M, M2 E M and 41 S S T, the following inequality holds
VMC. (M: (Aitosstttt
(Dx (wiheree
(82)
Viva (M'; (A (ADosis)
-xxo (A)
Joster (wr
A | M'
6 |M M2lle.
Proof.
The norm of the gradient difference in (82) can be expanded
E MeC
(M; { ( (Aioosec)
]
VMNG (M': (A (osiei)
(83)
M: ( )osiee) VMG (M', [A: )]1
MMC
+
E M
M'' (Mr((iiosier)
VMrc: M'. A ( (ADissse )isiee) )
E
MM', | (Aitesies)
Virce MM', 1 Josisa (A (Ai)ttssee
E
VM
(M', (A A
- (M', (A))sii
where we drop the subscript in E [:] since the associated randomness is clear from the context.
27

---

We next analyze a general term in R.H.S. of inequality (83). Specifically,
B Varae (M', (3 JosisK-1 : (Aitssi))
Vmrc MM, ( Aosossss (AIR)
(84)
= E E [VVra (M', (4 (AjJoSisk-1 As: (Ai)
Mrc M', [A A (AAAAAttiicii )
<B E Varce (M', (A' JUSiSk-1 A.. A Aijttssie)
-UMc (M', ( (Ajtosiss- A (A : :tAeensse
Given josiskss--1 (Athttsii) }: for notation conciseness, we abbreviate
VNN.C (M', {11) o As: k: (A: Aitttssee) and V (M', VMr (M', Ab) and VM (M', A)), respectively, follows that
A/. (Ai)
|L [Mr (M', Ax) M (M', A Alll
(85)
Tr (EIVVMG (M', A E V C (M', A() T (E (M', A+)l - E ( (M', Ab)
|E M. (M', A+) M (M', Illl Tr (V E V (M, Ax) E (M', A!)
where
E & (M, A+) E V (M', Ail
V
|V =
(86)
|E V (M', A MMG (M',
Based on Lemma B.6, given
( )4tsiii) the conditional gradient
V EE [ (M', Ax)] is v,-Lipschitz in A.. Further note that As Ds (M1) and A DE (M2), which are both e se-sensitvve. Applying Lemma B.7, it follows that
Tr (V E & (M', Ax) v E (M', A!) I ME |M Mells
(87)
Substitute (87) into (85), it follows that M. (M', Ax) Virc, (M', Aill, Me& |M M2llg
(88)
Using the similar approach, we can obtain
E V
MC;
(M; (iiussee) VNrc (M' A.I.Aitosie SAMI AMIM-MM'la
(89)
E Mi [M', ( - VMC (M' MM,AAAAAA (Aihsse S |M, - Mell;;
(90)
E Virce (M' A.-) VMra (M', (A (o0see))))
< M1E111 M M2ll
(91)
Combining (83), (89)-(91), it follow inequality (82).
C Properties of the Total Cost Function
We define a total cost function JT as
JT (M; (a (Ailster))
= =a (Mdloii))
(92)
1=
28

---

It is clear that
CT Mi) =
Jr (M: 1 Aclosee))
(93)
We next analyze the gradient properties and the smoothness of the total cost function Jr M: (Alosseer) We again note that V.rr M: (Ailusser) denotes the gradient taken w.r.t. the first argument M.
Lemma C.1 The variance of the gradient of the total cost function satisfies
VJr (M: (M:(Aelssee) VCT (M:M)
S
03.
t=1
(94)
Proof. Note that J. (M; Ao) VM (Xo, Un) VMCu (Xu, Kxx)) then follows directly from the norm triangular inequality:
Inequality (94)
[JJ (M: (M::seoss )1l?
E
Jr M: (Arlosee))
(95)
T
||| |/ (x/ -. (.fa))
T
Exo: (MM
VMC (M))) u. )
Exo: (A, (MM
(95.a)
T
02
1=1
where inequality (95.a) holds becasue of Lemma B.4.
D Proof of Lemma 2
Denote fa (M; M1) Exo (A, (Mi)ooseer (w. Josies cx (M: [M:(A) (Ai)osic) the per stage ex-
pected with the distribution of policy-dependen perturbation is shifted from A: D, (M) to
A ~ D, (M1), 40 <itt.
From the convexity of per stage expected cost in Lemma B.I. we know that, V1 < t1 H, fú, (M;M,) is a convex function of M. follows that
fn (M;M) ZG (M' + Tr ((V. (M) (M (M-M') , 11
(96)
where the gradient ft, (M'; M,) is taken w.r.t. the first argument M'.
From stong convexity of per stage expected cost in Lemma B.2, we know that, HA T, -strongly convex function of M. Therefore, it follows
fi, (M:M)) is min _ "
64xc0
fg (M; 2fc, MM) + TF ((V (M') (M (M-M))
(97)
2102 u2202
+ min 2 64
|M - 2 1MM-M
4H S l2 T.
29

---

Sum up (96) from 1 = to = H-- and (97) from 22 H to t2 T, we obatin
Σ
Jn (M:M))+ +
Σ
Sa (M: 2
Σ Sa (M;
Σ
Su (M;
(98)
1==
1=
((-
H-1
T
Ju (M) )) (M - My)
Σ
Ju M1)
Σ
(M-
(M-M')
b=#
n
M M
+ 2
Inequality (13) follows directly by noting that
H-1
CT (M: Σ far (M: +
Σ fa. (M:M),,
(99)
1==
VCr (M':)) v
Σ
Su
+
Σ 1=
Sn (M' (i)
(100)
4=
E Proof of Lemma' 3
Note that VCa (1) = Vr E [ce (Xo, un)] = MM [cr (Xo, -xx)] = O. Therefore, inequal-
ity (14) follows directly by combining the norm triangular inequalityand the results in Lemma B.6.
|vCr (M;M)) VCr (M; M
(101)
Exo. (.. Moggeeee [VMG (M: { (A Aslosiee)
Ex (A/DD((M2) uusier (wilossee
VNNGe (M'; (
T
1-1
A
[M M ||
11
E
|M - M2llr
1=0
MM-M'
Σ
Σ
14
|M - -M2l
iit+11
F
Proof of Lemma 4
Proposition 3 (First-order optimality condition in [18]). Let F(x) be convex and let X be a closed convex set on which F(x) is differentiable, then
x' arg ainFFin(((:) xEA"
if and only if
(y -'->)>> V 0, Vy X".
VF
Fix any M, M' E M. applying the first order optimality condition in Proposition 3, the optimality condition to (15) implies that
(VCr ( (M): M)) (M') 4 (M)) 2 0, (VCr (2 (M') M'), 4(M) - +>2((())) 2 0, (102)
where the gradients are again taken w.r.t. the first argument in the function Cr (s.)). Observe the fact
0 < (VC7 ( (M)) VCT (o (M) M) $6 (M) - +b (M').
(103)
30

---

Adding and subtracting the term VCr ( (M) M') implies the equality
Tr
- J a (M) M)) ( (M) 1 (M'')
(104)
2 Tr (VCr (M) M') vCr ( (M'; M)) ( (M) + (M))).
Recall that Cr ( (M): M') is ji-strongly convex w.r.t. & (M), follows
(VCr ( (M) M - VCr ( (M) M)) (Φ (M) (Mr))
(105)
M 2 (M) 4 (M')lI
Meanwhile, applying Lemma 3 to the left hand side of (104) gives
Tr
(VCr ( (M); :M) - VCr ( (M) :M)) (Ø (M) (M'))
(106)
T-1
T
IM M MMM - (M))
1=
i=++1
Combining (104), (105) and (106), it follows
Et=o Et C vi
c (M) - +b (M))
|| - M'I
(107)
We note that M + (M,) ) by the definition of (15), and M d (M*5) by the definition of performative stability. Applying (107) yields
Et= Es Ciizt v1)
Mn MP 0 (Mn-1) - + (MP)) S
M M
(108)
Ei=o
Eg
T Ei=e1 us)
Mo - M
Mo MPS to be most p and solving for completes the IT- (er Σ E(stt ())
"
Setting proof.
G Convergence Analysis of Algorithm
G.1 Non-asymptomatic Convergence Analysis for Algorithm 1 with General Step Sizes
We have the following Lemma 5 regarding the convergence results of the proposed RSGD in Algo- rithm
Lemma Under Al-A6. Consider a sequence of non-negative step sizes [ma, n 2 0} satisfy
-T- T-1 (ox Ei=4+1
sup th S min n20
(109)
2 (Et de + DT- -T-
21 Et (t 11))
ET-
(Es ET Bi
and
T-1
T
mm-11 m
On
< |
1 -
Σ
Et
Σ U
(110)
Mh+1
1=0
i=t+1
31

---

for any 2 O. Then, the iterates generated by RSGD admit the following bound for any N 2 1:
N-1
T-1
T
1)
| - -M B
II
1 1/22
j1
E |
M [²] (111)
n=0
t=
+++1
N
T 2/t=1 0²
- Σ 2i=1+1 V4
where 0, = R²G ((HW + x²² k: B B + 1) (Igas + c3B,) + MHWM (v + 1)s
Proof.
Since projecting onto convex can only bring two iterates closer together, follows that
E M, 17 Jr (Mn: { (A AcloseeT) M [
E || M F
(112)
< 11 + 12 + 1s.
where
1 = E
M MMP(12
(113)
12 = 22 E Tr (MMn MM T VJr MM, (Ac)oster))]
(114)
VJJ MM,; (Arooserr )|
I3 E
(115)
and A. ~ D. (M,). . 4A t <
We first analyze the term /z. Let En [:] be the conditional expectation on Mn. We have
E, Tr (M,, -MP) J. M ( (osose)) ))] =Tr (MM,. (M MM T VCr (M, M,.)
(116)
2 TT (M, - -MP) (VCr M.) VCT (M,; MPS))
+ Tr (M,, -M5) T (vCr
M VC, (M'S MPM))
where we use the first order optimality condition in Proposition 3 that (VCr (MPS; (MPS:MPS) M,
M 2 0 in the last equality of (116).
Applying the Cauchy- Schwarz inequality and Lemma 3, we obtain
Tr (M,, - MPS) T
(VCr (Mn; Mn) - VCT (M.; M PPS))
(117)
2
Mn, - |
M
Σ
1/
M M
1=0
i=1+1
T-1
T
Et
Σ
M,
PS
F
i=++
Meanwhile, based on strongly convexity of Cr in Lemma 2, we have
Tr TMM, 1 -MP)) T (VCr M VCr (M (MMSsMP)) (PP)) Mr, P
(118)
Substitute (117) and (118) into (116) and take the full expectation, follows that ln satisfies
T-1
T
) E M, - -MP
1 < 22
7
Σ
Et
Σ vi
(119)
t=o
i=++1
32

---

We next analyze the term 1z. We observe the following equivalent expression for 13
11: VJr (Mai fA (oolor)e)
VJr MM: (A JoSIeT)
VCr (M)
(120)
VCr VOr (MP:MMP) |1
Therefore,
JT (M.; ( ( (A)OostTT) ) [
E
(121)
11: 8
2E
V [M: 1 H bosset) VCT (M,; M,)
||VC (M,: M,) M,) - VCT (M : 11
+ 2E
According to Lemma C.I, an upper bound of the variance of VJr (M,i i Aeloster) is given by (94). Moreover, based on Lemma we have
E
VCT (M,; M,) - VCT
(122)
T
2
P |
Et
E
t=0
i=++1
Substitute (94) and (122) back into (121), follows
T
T
T
Vi ))
2
13 S AT Σ 8. +
2mh
Σ
Et
Σ
E
M, - MPS
(123)
t=1
1=++
Now subtitute (119) and (123) back into (112), obtain
T
T
E M - PS < E
Mn
-M
PS
12]
2mm
Σ
Vi
(124)
t=0
i=
E
Mn,
MM
[F]
-21//
E3
Σ
Vi
E
M,.
MM
2n T
Σ 03
t=l
0=
imt+1
T-1
T
T
T
T
m. ())
24mn
Σ
Et
Σ
2m
Et
Σ
E M, - -M
i=t+1
i=(+1
T
+
21
2T
02.
(&t (i-ET-' (s+
(i)1))))
Let
T/n
be
choosen
such
that
1/a
20/2
EE de + Eta Et Ei=(t v1.
Then inequality (124) is reduced
T-1
Σ 1/1 ))
MM111- - [M++1-MM112]] <
1- 17n
E1
E Mn MPS (125)
imt+l
T
+ 21 T
03
[=l
33

---

Therefore.
N-1
T-1
T
))
E
M - -
-
1
T/o
j - Σ Σ
23
Vi
E
Mo
M
[r]
(126)
n=0
t=0
i=t+1
T-1
1li
#
Ft
Vi
2
T
Σ
07.
i=++1
Let
7
<
(ct
c vi)
Based
on
Lemma
6 in
[14],
if
(1+
21=0
Eτ 2 Vi
Ma+1)
for any n 2 0, then
N
N-1
T-1
T
IJ
Et
Σ
Vi
2AN
AA 2 1.
i=+1
i=++1
11
Et= (
(127)
Substitute (127) into (126), we obtain the desired result.
Based on the step size requirements in Lemma 5, RSGD converges when the aggregated sensitivity E (E: Ei 1/1 is strictly below the threshold jú defined in Lemma 4, i.e., the same sufficient condition that guarantees the existence of MP
The first term on the R. H. S. of (111) decays sub-geometrically and is scaled by the initial error [| M 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 (MN-1)-
G.2 Convergence Analysis of Algorithm 1 with Diminishing Step Sizes
We select the diminishing step sizes 7/, n+ Vn 2 0. where &1 and Φ2 satisfy (17) and (18) simultaneously. We can verify that condition (109) in Lemma 5 is reduced (17) in Theorem 1. Besides, condition (110) in Lemma can be further simplifed as
d1
T
7n
1 + Ø2
Φ1 1 + Φ2
<
1
+
14
St
Vi
(128)
7-
2
+-
t=
1=
which is equivalent to
T
T
n + 1 02
1
(129)
n + d2
2
1=0
1=t+1
Note that Vn 2 0, to guarantee (129) holds, we only need to let
2
0102
Φ1
(130)
j 7 T- Ex El..r 13:)
1 1 02
1
1
02
which coincides with condition (18) in Theorem
Lastly, not that 1 1+ x S et for all x >> 0, we can verify the first term in R.H.S. of (111) can be upper bounded as
N-1
T Σ
T
1)) E [IM
1 - 1m
Σ
1/2
M
n=0
1=0
1=++
Σ Th ( Eو= - (cr Emm v/ 3))B E
Mo 1MP
e
ΣN=1
( -
(s. Eie m))
| - 1|
c
Se EN اي (i- E. 1
| MPS
(131)
Therefore, Theorem 1 follows by combining (130) and (131).
34

---

H Proof of Proposition
Since
|A,|| v 1 - 7 + Ex - Ç 1, ] < T, follows directly that at
I (1- 11-7+ x²)))) - II:20 C = C and 3, = Ei= I3=141 (1zea (1 - 7 + xg) + ===1) S 1-C
I-C
Further calculation yeilds 7 = (c1 + c23:) (roar czB1)) - (c1+ 20 +
As result, the sufficient condition (16) for the existence and uniqueness of M is reduced to
(at (ato1-
1 )
) 20 + C3
(El (T t)) < i..
(132)
1=0
This equivalent to (c
30 C3 co
El - < 14, where /
no² _²²a²" 2 64x
min
As a result, to guarantee condition (132) holds, it is sufficient to ensure that y.
T-1
H
1 -1 (1t0211
- {
1 (1000000000
ID + 100 - -
E E
1
c1
02
T
1=
Proposition 1 is thus proved by choosing o (a +2)+))))) (20+ (20+
I Proof of Proposition 2
Since ? < ||A+|l s 1 7 + x²G,, YO S t < T, for some a positive constant Č > 1,
it follows directly that an IT: (1 (1-7+ 7 x()) 2 at 2 I 5 and Be
(Ij4 (1 7 n²S) + ت-1
Further calculation yeilds Pt (c + c233)) (x cg3i)) 2 (a + c2 (20 + c2²²-1) Therefore,
T Σ
T
1/ 2 (1 + cses
0203 +
t=++1
1=++1
2T- 2-1
= 1o + (C10s + C20s + cg20) 2-1)
(133)
As result, to guarantee the sufficient condition (16) can be satifised, we must have
rr- -
Σ
Ex (crna + (cicg + c203 + cguo) =-1
n.
(134)
T H +1 0
( --1
This means that
T T - (3-1)
π
6,
(135)
C1 + (c) C2cs + c320) (-1
21-1-1
7-1
As result, Proposition 2 is proved by letting awot(arstaaattonnn
35

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:[Yes
Justification:
The abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:[Yes]
Justification:
We have discussed the limitations of the work in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The au- thors should reflect 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, c.g., if the approach was only tested on few datasets or with 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 ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because 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 ad- dress problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

Justification:
The paper has provided the full set of assumptions and a complete and correct
proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We have disclosed all the information needed reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation,
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
37

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification:
The paper does not provide open access to the data and code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.cm cc/
Serrides/CooeSSumiissttee
for more details.
While we encourage the release of code and data, understand that this might not be possible, so No is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / wwwppscccppbllll//p httpppuwwwwppppp/p/ppppppppaaeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specifyy all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper has specified all the training and test details (e.g., data splits, hy- perparameters).
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper has provided appropriate information about the statistical signifi- cance the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
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 enror bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 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 еπτог rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer[[No:
The paper does not provide the type of compute workers, memory, or time of execution.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 well 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 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neur/: htcpppblicctthhccciiieeeeeeeeeee
Answer: [Yes]
Justification: Ethics.
The research conducted in the paper conform with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., - if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
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.
39

---

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), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 mitiga- tion strategies (e-g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions to access the model or implementing safery 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
40

---

If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswith www.hhh.......oo.oooooooooooeeee com/datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemoodel as part of their submissions structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection. cura- tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper deseribe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "UVgEYqtGVA", "reviewer": "Reviewer_wfwc", "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.", "questions": "Can you highlight the challenge the is unique to linear dynamical system compared to MDP with finite numbers of states and actions?", "limitations": "There is not particular limitations for the paper to address.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper offers a thorough theoretical examination of the conditions required for the existence and uniqueness of performatively stable control solutions in the linear dynamical system.", "weaknesses": "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. \n\nMoreover, 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. \n\nFinally, 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.  \nIn 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$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments which inspired us to explore our contributions more.\n\n**Weaknesses:**\n\n**[W1] \"I feel I does not get the punchline...\":** We want to clarify that the reviewer has a significant misunderstanding of our work compared to the original performative prediction (PP). \n\n**1. Convexity**: **We only assume the per stage cost $c_{t}(\\mathbf{x},\\mathbf{u})$ is $\\mu$-strongly convex for the state-action pair $(\\mathbf{x},\\mathbf{u})$ in Assumption A 4. This does not by itself imply that expected per stage cost $\\mathbb{E}[c_{t}(\\mathbf{x},\\mathbf{u})]$ is strongly convex w.r.t. our optimization variable $\\mathbf{M}$** (i.e., the disturbance-action policy). We have highlighted this key point after Lemma 2. \n\nEven if $c_{t}(\\mathbf{x},\\mathbf{u})$ is $\\mu$-strongly convex w.r.t. $(\\mathbf{x},\\mathbf{u})$, $\\mathbb{E}[c_{t}(\\mathbf{x},\\mathbf{u})]$ can be non-strongly convex w.r.t. $\\mathbf{M}$ when $t<H,$ where $H$ is the time horizon of $\\mathbf{M}$ defined in Definition 1. \n\nEven if in the cases that $\\mathbb{E}[c_{t}(\\mathbf{x},\\mathbf{u})]$ is indeed strongly convex w.r.t. $\\mathbf{M}$, the strongly convex constant is **not $\\mu$, but min{$\\frac{\\mu\\sigma^{2}}{2},\\frac{\\mu\\sigma^{2}\\gamma^{2}}{64\\kappa^{10}}$}** as we have established in Lemma B.2, where $\\kappa$ and $\\gamma$ are related to the dynamical system parameters $\\mathbf{A},\\mathbf{B}$ and $\\mathbf{K}$. **This is totally different from the original PP paper, where one can directly assume $\\mathbb{E}[c_{t}(\\mathbf{x},\\mathbf{u})]$ is $\\mu$-strongly convex w.r.t. $\\mathbf{M}$ without any problem-specific theoretical analysis.**\n\n\n**2. Gradient Descent**: To guarantee convergence of our gradient descent algorithm, the designing of the step sizes relies heavily on the problem-specific strongly convex constant min{$\\frac{\\mu\\sigma^{2}}{2},\\frac{\\mu\\sigma^{2}\\gamma^{2}}{64\\kappa^{10}}$} and the distributional sensitivity propagation and aggregation $\\mathbf{M}^{PS}$ existence condition. These are unique to our performative dynamical systems, and have never been exploited in the original PP paper. \n\n**[W2] \"Moreover, despite the existing MDP...\":** A unique and serious challenge posed by the linear dynamic model is the existence of the optimal solution to the MDP. In particular, for MDPs with finite state space, it is known that optimal strategies exist for a wide range of costs. In contrast, for dynamical systems with infinite state space, optimal solution may not exist [Line 2-5, Abstract, R1]. This unique challenge has been discussed in detail in the Response to **Question** below. \n\nIt is worth noting that there are methods for embedding a linear dynamical model into an MDP with finite action and state spaces, e.g. [R2], where the state transition matrix will have certain restrictions to keep the states in the finite set. However, the linear model-based MDPs with infinite action and state spaces will have more general state transition matrices.\n\n**[W3] \"Finally, ... by allowing for any linear shift represented by $\\mathbf{B}$\":** Great and inspiring comments! We completely agree with the reviewer's opinion that our work has the potential to improve the community's understanding of general performative prediction. Inspired by the reviewer, our work's generalizations to the original PP framework include:\n\n• Distribution map with small perturbations. When the perturbation $\\mathbf{A}\\_{t}(\\mathbf{M})\\mathbf{x}\\_{t}$ is small, a linear shift of the policy represented by $\\mathbf{B}$ will increase the insensitivity of the distribution map to the perturbations.\n\n• Distribution map with temporal correlations. If the perturbation $\\mathbf{A}\\_{t}(\\mathbf{M})\\mathbf{x}\\_{t}$ is large, we will have a sequence of temporal correlated distribution maps introduced by the dynamical model. We have explored the unique sensitivity temporal propagation and aggregation structure for establishing the existence condition of a performative stable solution.\n\nWe believe that the above generalizations are part of the strengths, novelties, and contributions of our work, rather than a weakness.\n\n**Answer to the Question**: We highlight a unique challenge on the existence of optimal solution to the MDP [Line 2-5, Abstract, R1].\n\nConsider an illustrative example of standard 1-dimensional linear quadratic optimal control problem (P1):\n\\begin{align}\n\\min\\_{u\\_{t}}  \\limsup_{T\\rightarrow\\infty}\\frac{1}{T}\\sum\\_{t=0}^{T-1}\\mathbb{E}[x\\_{t}^{2}+u\\_{t}^{2}]\\\\\ns.t. x\\_{t+1}=A\\_{t}x\\_{t}+B\\_{t}u\\_{t}+w\\_{t},\\forall t\\geq0. (P1)\n\\end{align}\n\nFrom the linear dynamical system (LDS) perspective, the state and action spaces are infinite, i.e., $x\\_{t},u\\_{t}\\in\\mathbb{R},$ $w_{t}\\sim\\mathcal{N}(0,1)$ is the Gaussian additive noise, the state-action transition kernel is given by the constraint in (P1). It is well-known that the optimal control action $u_{t}^{*}$ exists if and only if the following Riccati recursion converges as $t\\rightarrow\\infty$:\n\\begin{align}\nP_{t+1} & =A_{t}(B_{t}B_{t}+P_{t}^{-1})^{-1}A_{t}+1,P_{0}=1,\\forall t\\geq0.\n\\end{align}\nIf $A_{t}$ and $B_{t}$ keep time varying, the limit of $P_{t}$ may not exist, which results in the non-existence of optimal solution\nto the MDP.\n\nFor MDP with finite state and action spaces, where $x_{0}=1$, $x\\_{t}\\in$ {1,2}, $u\\_{t}\\in${$1,10^{6}$}, $w_{t}=0, A_{t}=1,B_{t},$ fluctuates based on the pattern of 1, 0, -1,  $\\forall t\\geq0,$ the optimal solution exists and is given by $u_{t}^{*}=1$. \n\nFor scenario considered in this paper, where $A_{t}$ is performative, the situation will be even more complicated and challenging.\n\n[R1]. Kiefer S, Mayr R, Shirmohammadi M, et al. How to play in infinite MDPs, 47th International Colloquium on Automata, Languages and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Germany, 2020: 1-18.\n\n[R2]. Relund Nielsen L, Jørgensen E, Højsgaard S. Embedding a state space model into a Markov decision process. Annals of Operations Research, 2011, 190: 289-309.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6sHyhdplCn", "reviewer": "Reviewer_JGbs", "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.", "questions": "- How is policy-depended temporal correlation in this work different from existing performative prediction works? this needs to be covered to highlight novelty\n- 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?\n- 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)?\n- The projection step assumes projecting into feasible set M is computionally tractable. How is it justified based on M structure?\n- RSGD is relatively straightforward, why it over other potential optimization methods for finding the psc solution?\n- 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.\n- 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": "- 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.\n- 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.\n- The validation of the framework heavily relies on numerical simulations rather than empirical testing with real-world data.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Work addresses gap in traditional control theory via introduction of performative control\n- Provides theoretical foundation with sufficient conditions for performative stable control solutions\n- Paper provides application of the framework via numerical examples\n- Provides insights into system stability under different conditions\n- Development of custom stochastic gradient descent (rsgd) tailored to this new pscs control framework", "weaknesses": "- The concepts and algorithms introduced may be complex for practical implementation without extensive customization\n- Reliance on numerical examples vs extensive empirical data might limit how the framework will perform on real-world conditions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your insightful comments and kind suggestions!\n\n**Weaknesses:**\n\n**[W1] \"The concepts and algorithms introduced...\":** Our primary focus is the thorough theoretical investigation\nof performative dynamical systems. The low complexity customized implementations\ncan be exciting future research topics.\n\n**[W2] \"Reliance on numerical examples...\":** We fully agree with the reviewer's suggestion. In the revised paper,\nwe will try to verify our developed theory using the stock market\nexample in the appendix based on the real-world data of stock prices.\n\n**Questions:**\n\n**Q1. How is policy-depended temporal correlation...this needs to be covered to highlight novelty.**\n\nA1. In existing performative prediction works [3,5,12,14,15,20,22,25], the data input\nto the learning algorithms are independently generated based on the\ndecision-dependent distributions. No temporal correlation is considered\nor exploited between two successive sets of input data. However, our\nwork considers a linear dynamical systems, where the policy-dependent\ntemporal correlation is introduced via the performative state transition\nmatrices.\n\n**Q2. As per A4, A5 and A6, the cost function is assumed to be strongly convex... can we relax this for cost functions in this control setting?**\n\nA2. If we intend to find the performative stable control solution, we\ncannot relax these assumptions for cost functions. However, if we\nonly need to find a stationary control policy, we can relax these\nassumptions, such as allowing the per stage cost to be non-convex,etc.\n\n**Q3. The RSGD Algorithm 1 has a projection step $\\text{Proj}\\_M$ - what metric is used for this projection? How is \nupdated if the calculated $\\mathbf{M}\\_{n+1}$ falls outside of $\\mathbf{M}$? Also, is it reasonable to expect access to the true matrices in practice to compute the gradient eqn (17)?**\n\nA3. The metric of the projection in Algorithm 1 is the matrix Frobenius\nnorm. If $\\mathbf{M}\\_{n+1}$ falls outside of $\\mathcal{\\mathbb{M}},$\nwe update the projection as $\\mathrm{Proj}\\_{\\mathcal{\\mathbb{M}}}${ $\\mathbf{M}\\_{n+1}$}=$\\arg\\min\\_{\\mathbf{M}\\in\\mathcal{\\mathbb{M}}}||\\mathbf{M}\\_{n+1}-\\mathbf{M}||\\_{F}^{2}$.\nFor the computation of the gradient in (17), we can first obtain $\\mathbf{A}\\_{t}=\\mathbf{A}+\\mathbf{\\Delta}\\_{t}$\nbased on the known disturbance sample $\\mathbf{\\Delta}\\_{t}$ associated\nwith $\\mathbf{M}\\_{n}$. We next follow the conventions in non-stochastic\ncontrol [1,8,10,11] to compute noise as $\\mathbf{w}\\_{t}=\\mathbf{x}\\_{t+1}-\\mathbf{A}\\_{t}\\mathbf{x}\\_{t}-\\mathbf{B}\\mathbf{u}\\_{t}$\nbased on $\\mathbf{A}\\_{t},$ current state $\\mathbf{x}\\_{t}$ and control\ninput $\\mathbf{u}\\_{t}$. \n\n**Q4. The projection step assumes projecting into feasible set M is computationally tractable. How is it justified based on $\\mathbf{M}$ structure?**\n\nA4. We have assume that the feasible set $\\mathcal{\\mathbb{M}}$ is a\nbounded convex set. Therefore, the projection is computationally tractable\nas a Frobenius norm square minimization problem with a convex constraint.\n\n**Q5. RSGD is relatively straightforward, why it over other potential optimization methods for finding the psc solution?**\n \nA5. We use the RSGD because it is a simple and commonly used algorithm\nin performative prediction works [3,5,12,14,15,20,22,25]. We agree with the reviewer\nthat there may be other potential optimization methods such as the\nlow complexity zeroth-order stochastic projected gradient descent [R1,R2].\n\n**Q6. 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.**\n\nA6. We fully agree with the reviewer's suggestion. We will compare the\nactual convergence speed and efficiency of the proposed RSGD over\nother candidate algorithms, e.g., the low complexity zeroth-order\noptimization methods [R1,R2].\n\n**Q7. 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 convergence properties should be discussed.**\n\nA7. In fact, Algorithm 1 uses the stochastic gradients of the cost function.\nThe impact of the variance of the stochastic gradients has been characterized\nin the convergence speed in Theorem 1. Specifically, the second term\nin R.H.S. of (12) depends on the variance of the stochastic gradient\n$\\nabla J_{T}(\\mathbf{M};\\mathbf{M})$ $\\mathcal{O}(T\\sum_{t=1}^{T}\\vartheta_{t}^{2}),$\nwhich decays at the rate as $\\mathcal{O}(\\eta_{N-1})$.\n\n**Limitation:**\n\n**\"Assumes the per stage cost function is strongly convex...\":** We only assume the per stage cost function is strongly convex and smooth w.r.t. the state-action pair $(\\mathbf{x},\\mathbf{u})$. However, the justification of the strongly convex and smooth w.r.t. our optimization variable $\\mathbf{M}$ (i.e., the disturbance-action policy) needs further problem-specific theoretical derivations. Besides, if we only need to find a stationary control policy, we can relax these assumptions, such as allowing the per stage cost to be non-convex, etc.\n\n**\"The implementation of the proposed repeated stochastic gradient...\":** This paper's primary focus is the theoretical investigation of performative dynamical systems. The development of low complexity implementation\nalgorithms, e.g., the zeroth-order methods [R1,R2], can serve as interesting future research topics.\n\n**\"The validation of the framework heavily ...\":** We will try to verify our developed theory using the stock market\nexample in the appendix based on the real-world data of stock prices\nin the revised paper.\n\n[R1]. Golovin D, Karro J, Kochanski G, et al. Gradientless descent: High-dimensional zeroth-order optimization[J]. arXiv preprint arXiv:1911.06317, 2019.\n\n[R2]. Liu S, Li X, Chen P Y, et al. Zeroth-order stochastic projected gradient descent for nonconvex optimization[C]//2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP). IEEE, 2018: 1179-1183.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MyUglBP6Pf", "reviewer": "Reviewer_nkz4", "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.", "questions": "Could the authors motivate why they assume that A_t is performative but B is time invariant?\n\nWhy are the performative disturbances for A_t assumed to all be zero mean? \n\nIn L171, what is \\tilde{A?}? Is this just A? Or A - BK?\n\nIn Lemma 1, is K assumed to be strongly stable? If so, could you please make that explicit?\n\nIn 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\n\nL205: there is a mistaken reference, the authors reference A1-6, but only A4-6 are about the costs\n\nWhy 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.\n\nTheorem 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).\n\nWhat is reference 13 it doesn’t seem to have an author? Reference 18 was published in a conference.", "limitations": "These issues have been discussed to the extent necessary.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The idea of connecting performative prediction and linear control is very exciting, and to the best of my knowledge novel. I really enjoyed this idea that the very choice of control policy might actively influence the underlying system dynamics, and hence we should start to think about new models that explicitly account for this feedback. The technical results seem solid, although I wasn’t able to go through the proofs line by line. I also enjoyed the insights regarding how sensitivities need to be smaller at the beginning of the time horizon versus at the end.", "weaknesses": "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. \n\nThis 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. \n\nLastly, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are glad that the reviewer liked our paper and recognized our exciting idea.\n\n**Weaknesses:**\n\n**[W1] \"While the motivation...\":** Thank you for recognizing and appreciating our key idea that control policies affect dynamics. To fully develop this idea, we have moved the main illustrative example of the stock market from the appendix to the main body of the paper. We have elaborated and discussed the intuitions behind how control policies can affect the dynamics in detail in the main body of the paper using this stock market example. \n\n**[W2.1] \"Why the policy only affects the state matrix $\\mathbf{A}$?\":** The key motivation for letting only matrix $\\mathbf{A}\\_t$ be performative is that our work adopts the linear disturbance-action control policy initiated in the framework of **non-stochastic control** [1,8,10,11] by Elad Hazan et al, where the disturbance-action $\\mathbf{B}\\mathbf{M}[\\mathbf{w}]_{t-1}^{H}$ is linear in policy $\\mathbf{M}$. Such kind of linear disturbance-action control policy has various nice theoretical performance guarantees as substantiated in [1,8,10,11].\n\nOn the other hand, if $\\mathbf{B}$ is also performative, we will have a generalized disturbance-action $\\mathbf{B}\\_t(\\mathbf{M})\\mathbf{M}[\\mathbf{w}]_{t-1}^{H}$, which can be possibly nonlinear in policy $\\mathbf{M}$. To the best of our knowledge, such kind of generalized nonlinear disturbance-action control policy has received very few research attention, and it can serve as a very exciting future research direction.\n\nTo the best of our knowledge, this paper is the very first work to investigate the control of performative dynamical systems, and we intend to provide a thorough theoretical investigation and aim at establishing various new theoretical results. Therefore, we choose to build our work on the linear disturbance-action control policy (i.e., policy only affects the state matrix $\\mathbf{A}$ and not affects matrix $\\mathbf{B}$), whose nice theoretical performance guarantees would facilitate and consolidate our theoretical analysis.\n\n**[W2.2] \"Why all policy induce disturbances that are zero-mean?\":** The non-zero mean and zero mean cases are mathematically equivalent. The mean value of the disturbance can be absorbed into the original state transition matrix $\\mathbf{A}$, which is equivalent to a new $\\mathbf{A}^{\\prime}$ ($\\mathbf{A}^{\\prime}$ equals $\\mathbf{A}$ plus the mean of disturbance) with zero-mean disturbances. We only need to choose a new controller $\\mathbf{K}^{\\prime}$ such that $\\mathbf{A}^{\\prime}-\\mathbf{B}\\mathbf{K}^{\\prime}$ is $(\\kappa,\\gamma)$-strongly stabilizing as specified in Definition 2. In this way, the non-zero mean performative disturbances are converted equivalently to the zero-mean case. \n\n\n**[W2.3] \"Why the disturbances between time steps are uncorrelated for the same policy?\":** From the application perspective, we have used the widely adopted uncorrelated truncated lognormal distributions of the stock price model [23,27] in the stock market example to justify the temporal uncorrelated disturbances for the same policy. From the theoretical perspective, the performative disturbances are the data samples, which are assumed to be i.i.d. distributed according to a certain distribution map under a same policy in the existing framework of performative prediction [3,5,12,14,15,20,22,25]. In this work, we followed this convention.\n\n**[W3] \"Lastly, I think the paper suffers from...\":** We have gone through the paper thoroughly to make sure all the quantities are well defined. We have not claimed that \"performative stability implies performative optimality\". In fact, the performative stable solution $\\mathbf{M}^{PS}$ and performative optimal solution $\\mathbf{M}^{PO}$ converge to a same value $\\mathbf{M}^{*}$ as the magnitudes of all the sensitivities {$\\{\\varepsilon_{t},0\\leq t<T\\}$} approach 0.\n\n**Questions:**\n\n**Q1. Could the authors motivate why they assume that A_t is performative but B is time invariant?**\n\nA1. The motivations have been clarified in Response to **[W2.1]**.\n\n**Q2. Why are the performative disturbances for A_t assumed to all be zero mean?**\n\nA2. The justifications have been clarified in Response to **[W2.2]**.\n\n**Q3. In L171, what is \\tilde{A}? Is this just A? Or A-BK?**\n\nA3. In L171, $\\mathbf{\\widetilde{A}}$ is $\\mathbf{A}-\\mathbf{B}\\mathbf{K}$,which has been defined in Definition 2 in L144.\n\n**Q4. In Lemma 1, is K assumed to be strongly stable? If so, could you please make that explicit?**\n\nA4. In Lemma 1, $\\mathbf{K}$ is a strongly stabilizing linear controller.\n\n**Q5. In L182: the authors claim...**\n\nA5. The justifications have been clarified in Response to **[W3]**.\n\n**Q6. L205: there is a mistaken...**\n\nA6. We have changed the reference citation from \"A1-6\" to \"A 4-6\" in L205.\n\n**Q7. Why do the authors refer..**\n\nA7. To avoid potential confusion, we have rephrased the wording \"almost surely stable\" in Proposition 1 to \"strongly stable\",\nwhich has been defined in Definition 2. The \"strongly stable\" condition is indeed stronger and places requirements on the operator norm of matrices. Specifically, we let $\\mathbf{A}\\_{t}^{\\pi}$ be $\\left(\\kappa,\\gamma-\\kappa^{2}\\xi_{t}\\right)$-strongly stable for real numbers $\\kappa\\geq1,\\gamma-\\kappa^{2}\\xi_{t}<1$, $\\forall0\\leq t<T.$ The technical results in Proposition 1 then follow directly by letting $\\zeta$=max{$ 1-\\gamma+\\kappa^{2} \\xi\\_{t},\\forall 0\\leq t<T$}.\n\n**Q8. Theorem 1 is not very readable...**\n\nA8.  Theorem 1 has a complex form because of its strong capability to accommodate general step size rules. Nevertheless, we respect and follow the reviewer's suggestion to plug in the specific diminishing step size and stated formally the associated final convergence rate. The technical results on the general step size have been moved into\nappendix.\n\n**Q9. What is reference 13 it doesn’t seem to have an author? Reference 18 was published in a conference.**\n\nA9. We have revised reference 13 and 18.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tNy0b32YQD", "reviewer": "Reviewer_e5pZ", "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.", "questions": "The assumption that the disturbance w is available for determining the control action u, is practically severe.  Could the authors relax the assumption?\n\nLemma 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?\n \nThe 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": "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.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "The concept of performative control is nicely motivated in Introduction.  The control policy, design method, and convergence analysis are stated mathematically rigorously.", "weaknesses": "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your work in reviewing our manuscript, and for providing thorough feedback. We address your concerns as follows.\n\n**Weaknesses:**\n\n**[W1] \"The disturbance-action policy...\":** We want to clarify that the reviewer has a misunderstanding regarding the measuring of disturbance $\\mathbf{w}\\_{t}.$ \n\nThe measuring of the disturbance $\\mathbf{w}\\_{t}$ is practically not severe and is commonly advocated in the framework of non-stochastic control [1,8,10,11] initiated by Elad Hazan. The methods for measuring $\\mathbf{w}\\_{t}$ are mature and have been extensively studied for LTI systems with static $\\mathbf{A}$ and $\\mathbf{B}$ [1,8,10,11] and LVI systems with time-varying $\\mathbf{A}\\_{t}$ and $\\mathbf{B}\\_{t}$ ([Chapter 7, R1]). \n\nThe control policy we adopt in our paper is the disturbance-action policy, which is popular and widely used in non-stochastic control applications [1,8,10,11]. There is no application limitation as suggested by the reviewer. \n\n**[W2] \"The results of this paper rely heavily...\":** We want to clarify that our work does not relies on the results from work [22]. In contrast, compared to [22], our work has totally different convexity assumption and convergence analysis, which are summarized below.\n\n**1. Convexity Assumption**: For the original performative prediction work [22], one can directly assume the objective function $\\mathbb{E}[c_{t}(\\mathbf{x},\\mathbf{u})]$ is $\\mu$-strongly convex w.r.t. optimization variable $\\mathbf{M}$ (i.e., the disturbance-action policy) **without any problem-specific convexity analysis**. \n\nHowever, for the convexity in our work, we only have a mild assumption that the per stage cost $c_{t}(\\mathbf{x},\\mathbf{u})$ is **$\\mu$-strongly convex** for the state-action pair $(\\mathbf{x},\\mathbf{u})$. We provide rigorous theoretical analysis that $\\mathbb{E}[c_{t}(\\mathbf{x},\\mathbf{u})]$ is strongly convex w.r.t. $\\mathbf{M}$ and the strongly convex constant is **not $\\mu$, but min{$\\frac{\\mu\\sigma^{2}}{2},\\frac{\\mu\\sigma^{2}\\gamma^{2}}{64\\kappa^{10}}$}** , where $\\kappa$ and $\\gamma$ are problem-specific parameters related to the dynamical system parameters $\\mathbf{A},\\mathbf{B}$ and $\\mathbf{K}$. **This is totally different from the results in [22]**.\n\n**2. Convergence Analysis**: To guarantee convergence of our proposed gradient descent algorithm, the designing of the step sizes relies on the problem-specific strongly convex constant min {$\\frac{\\mu\\sigma^{2}}{2},\\frac{\\mu\\sigma^{2}\\gamma^{2}}{64\\kappa^{10}}$} and the distributional sensitivity temporal propagation and aggregation $\\mathbf{M}^{PS}$ existence condition. **These are unique to our performative dynamical systems, and have never been exploited in [22]**.\n\n**Questions:**\n\n**Q1. The assumption that the disturbance w ...?**\n\nA1. As we clarified in the Response to [W1], the measuring of the disturbance $\\mathbf{w}\\_{t}$ is practically not severe at all, and is commonly advocated in the framework of non-stochastic control [1,8,10,11] initiated by Elad Hazan. The control action $\\mathbf{u}\\_{t}^{(\\mathbf{M})}$ in our paper is the disturbance-action policy, which is also popular and widely used in [1,8,10,11]. \n\n**Q2. Lemma 4, the convergence condition...?**\n\nA2. **The interpretation of the condition (11) has already been provided in Line 238 -Line 246 right after condition (11)**. Condition (11) reveals the effects of the sensitivity propagation and aggregation, which are unique to our performative dynamical systems, and have never been exploited in the existing performative prediction works. \n\n**Q3. The reviewer cannot agree the statement ... ?**\n\nA3. Our statement is that **\"most prior studies\"** consider the static transition model. Of course, there are several\nother papers on time-varying transition model, such as the paper suggested\nby the reviewer and the papers on jump linear systems [R2, R3], etc. We have included more survey on time-varying transition models.\n\nHowever, the key message we want to deliver is that the system state\ntransition model can be changed by control policies has not been considered\nin existing literature, either for static or time-varying transition\nmodels. To the best of our knowledge, our paper is the first work\nto consider such performative state transition model for linear dynamical\nsystems.\n\n**Response to Limitation:** We want to clarify that the disturbance-action control policy adopted in our paper is not proposed by us. Instead, it was initiated by Elad Hazan et al. in the framework of non-stochastic control [1,8,10,11]. The methods for measuring $\\mathbf{w}\\_{t}$ are mature and have been extensively studied in [1,8,10,11]. Particularly, in [R4], the disturbance-action control policy is applied to the case of imperfect modelling on the state transition, where the underlying state transition model is unknown.\n\n[R1]. Hazan E, Singh K. Introduction to online nonstochastic control[J]. arXiv preprint arXiv:2211.09619, 2022.\n\n[R2]. Zhang L, Leng Y, Colaneri P. Stability and stabilization of discrete-time semi-Markov jump linear systems via semi-Markov kernel approach[J]. IEEE Transactions on Automatic Control, 2015, 61(2): 503-508.\n\n[R3]. Cheng J, Xie L, Zhang D, et al. Novel event-triggered protocol to sliding mode control for singular semi-Markov jump systems[J]. Automatica, 2023, 151: 110906.\n\n[R4]. Elad Hazan, Sham M. Kakade, and Karan Singh. The nonstochastic control problem. In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT), pages 408--421, 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for recognizing that our paper provides a thorough and mathematically rigorous theoretical investigation of performative linear control, where control policies can directly affect the dynamics of the system (reviewers wfwc, JGbs, nkz4, e5pZ), which fills a gap in traditional control theory (reviewer JGbs), is very exciting (reviewer nkz4), and is a good step towards improving the understanding of general performative prediction (reviewer wfwc). We would now like to address frequently raised comments, which we believe will clarify any previous concerns:

**1.Assumption of strong convexity.** For the existing performative prediction works [3,5,12,14,15,20,22,25], **one can directly assume the objective function $\mathbb{E}\left[c_{t}\left(\mathbf{x},\mathbf{u}\right)\right]$ is $\mu$-strongly convex w.r.t. optimization variable $\mathbf{M}$ (i.e., the disturbance-action policy)** without any problem-specific theoretical convexity analysis. However, in our work, **we only have the freedom to assume the per stage cost $c_{t}\left(\mathbf{x},\mathbf{u}\right)$ is $\mu$-strongly convex for the state-action pair $\left(\mathbf{x},\mathbf{u}\right)$**, which does not by itself imply that expected per stage cost $\mathbb{E}\left[c_{t}\left(\mathbf{x},\mathbf{u}\right)\right]$ is strongly convex w.r.t. our optimization variable $\mathbf{M}$. We provided rigorous theoretical analysis that $\mathbb{E}\left[c_{t}\left(\mathbf{x},\mathbf{u}\right)\right]$
is strongly convex w.r.t. $\mathbf{M}$ and the strongly convex constant
is **not $\mu$, but min{$\frac{\mu\sigma^{2}}{2},\frac{\mu\sigma^{2}\gamma^{2}}{64\kappa^{10}}$}**, where $\kappa$ and $\gamma$ are problem-specific parameters related to system dynamics.

**2. Existence and uniqueness of performative stable solution.** Our sufficient
condition for existence and uniqueness of performative stable solution
has a **distributional sensitivity temporal propagation and aggregation
structure, which is unique to the performative dynamical systems**.

**3. Convergence analysis.** To guarantee the convergence of our proposed
algorithm to the performative stable solution, the designing of the
step sizes relies heavily on the strongly convex constant min{$\frac{\mu\sigma^{2}}{2},\frac{\mu\sigma^{2}\gamma^{2}}{64\kappa^{10}}$}, and the distributional sensitivity temporal propagation and aggregation
condition. **These are unique in our performative dynamical systems,
and have never been exploited in existing performative prediction works** [3,5,12,14,15,20,22,25].

**4. Generalization to the existing performative prediction framework.**
Our proposed framework can effectively accommodate distribution maps with perturbations and temporal correlations, which is a meaningful generalization of the standard distribution maps considered in existing performative prediction works [3,5,12,14,15,20,22,25].

Meta-review: 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.
Decision: Accept (poster)