{'fraction_non_alphanumeric': 0.04917847665292756, 'fraction_numerical': 0.007622381570775224, 'mean_word_length': 4.3125374925015, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Stochastic Model Predictive Control as an Iterated Function System

We present the observation that the process of stochastic model predictive control can be formulated in the framework of an iterated function system. The latter has a rich ergodicity theory that can hence be applied to study the former's limiting behavior. We present how such a framework can be realized for specific problems and illustrate the required conditions for application of the relevant theoretical guarantees.


Introduction
Consider a generic iterative process with the following steps: a system takes inputs in the form of a control and exhibits stochastic performance, i.e., its output is noisy and governed by some probability distribution. The control, in turn, is computed at each time step in an open loop to solve a stochastic optimization problem.
This can be formalized as a type of stylized map: where the first → indicates a solution to a stochastic optimization problem given the input state x(k), such that x(k + 1, ξ) = g(u, x(k), ξ), ∀ξ ∈ Ξ where ξ is a random variable sampled from the space Ξ and R(·) is a statistical aggregation operator, e.g., an expectation or an evaluation of a risk measure, f is a cost function and g describes some noisy dynamics.
In practice, typically (2) cannot be solved exactly but only by means of sample average approximation (SAA), wherein Monte Carlo (or other stochastic discretization) samples of ξ are taken and the optimization problem on the average is solved. SAA approximations satisfy the law of large numbers and are consistent (although biased) estimators (see, e.g., [13]). Generically, this can be written as that this first → in the schema (1) is a noisy operation, which we can consider as the stochastic error η. We note that, alternatively, one can solve a more conservative variant of (2), such as robust (finding the optimal for the worst case instance) or distributionally robust (finding the optimal for the worst case probability distribution among a set of possible ones) formulation. These methods would be solving a different problem, however, and are associated with their own advantages and disadvantages.
The second → in (1) corresponds to the stochastic realization of the subsequent state. Given the computed control u k := u(x(k), η k ) at the realization for iteration k, the next state satisfies the stochastic system equations x(k + 1, ξ k ) ∼ g(u k , x(k), ξ). Thus, with the distribution depending on the control u k the resulting output is another noisy function.
This generic procedure, although featuring in a variety of settings, can be described as Stochastic Model Predictive Control (see, e.g., [9]), the iterative management of some physical process that is subject to random noise with known statistical properties.
In this paper, we consider placing this process into the framework of an Iterated Function System (IFS, cf. e.g., [2,6]) to study the convergence behavior of MPC problems that can be stylized in the form (1).
Iterated Function Systems describe a sequential probabilistic selection of maps to define a sequence of states of a system. These systems have been studied under various settings, with their long run behavior studied through the lens of ergodic theory. This contrasts with standard notions of convergence of optimization problems and closed-loop stability, as considered in the traditional Model Predictive Control literature. These notions have proved challenging by their restrictiveness, and only recent results exist for stochastic problems, extending deterministic notions to the expectation [8]. Ergodic theory has a rich set of conceptual and algorithmic tools as evidenced by the powerful monograph [10]. Thus, in this paper, we consider modeling this process as an IFS, and applying the relevant results and guarantees to the Stochastic MPC procedure, indicating what control problem structure properties enable the application of theoretical results concerning the system ergodicity. To the best of the authors' knowledge, the link has not yet been explored. Note that we do not introduce any new algorithms or solution procedures, but present the scaffolding of a new potential means of analysis, which could provide understanding of the performance of existing algorithms which perhaps may provide insight into possible techniques for novel procedures.
To maintain a generic formalism, we consider that u and x both live in some Polish space X , and any use of a norm indicates its native norm. All functions considered, unless noted otherwise, for instance f and g in (2), will be considered to live in C 1 (X ). |A| is the cardinality of a set A.

Background
We begin introducing the more specific notion relevant here of a statedependent Iterated Function System (IFS). This is a process wherein there exist a set of maps {F i (x)} and associated probabilities p i (x) where, at each step in the sequence, given the current state x, some index i is chosen according to the probabilities {p i (x)} and subsequently the map F i (x) is applied to generate the next iterate. A first foray into studying the properties of these maps is given in [3], and subsequently the literature has considerably evolved.

Warm Up: Discrete Controls and Exact Stochastic Programming Solutions
Consider now the situation wherein the controls are discrete, i.e., there is a finite set U of possible inputs from which the control u(k) must be chosen at each iteration k. The stochastic optimal control problem (OCP) then amounts to taking the current given x(k) then computing an optimal u(k) ∈ U in order to minimize the relevant probabilistic quantity, with a resulting noisy x(k + 1, ξ), or alternatively, computing an optimal mixed strategy {p i } of probabilities to implement u i ∈ U with probability p i . (Note, since the expectation is a linear operator and we shall see that we require f to be convex, we would expect the optimal control to be deterministic, i.e., p i = 1 for some i, if only the expected outcome is to be minimized or maximized. On the other hand, any higher moments or risk measures could make the mixed control optimal). Formally, we aim to solve for p in∆, the unit simplex, such that with the control being implemented as u i among a set of finite controls, formally the set U, is chosen with probability p i .
Note that clearly we can then write p i (x(k)) as depending on the previous state x(k). The resulting state, x(k + 1, ξ, i) depends on the control chosen u i ∈ U according to i ∼ {p i }, thus we take F i (·) as the mapping from x(k) to x(k + 1, ξ, i), which is of course a stochastic quantity depending on ξ.
We shall now consider applying the results derive in [14] for state dependent IFS to (3). To begin with, we must show that p i (x) as defined satisfy the Dini condition, which states that there exists a ω : [0, ∞) → [0, ∞) continuous, non-decreasing and concave, with ω(0) = 0, such that 1 0 where ρ is the metric on the underlying space.
Indeed, if we re-write the problem as unconstrained, we can now use [1,Theorem 4.1] with the domain of the parameter set x(k) being any large enough compact set, which guarantees such a function ω(t) exists.
Note, however, that if R = E above, then the solution of the problem is clearly p i = 1 for i such that E[f (g(p i , x(k), ξ), u i , x(k))] is minimal, and this is a linear program, thus not strongly convex. This can be corrected simply by adding a regularization α i p 2 i to the objective. Second, we point out that this is a sufficient but by no means necessary assumption-it is our intention to open the field of analyzing SMPC with IFS, and results must by necessity begin with the most straightforward cases.
Finally, we use [14, Theorem 1] to prove the ergodicity of the resulting IFS, which we state below, Theorem 2.1 [14, Theorem 1] Let (S, p) be an iterated function system, i.e., there exist S i : X → X for i = 1, ..., N such that given x, with probability p i (x), the next state is defined by S i (x). Then if, 1. There is a Dini function of (S, p) The transformations S i : X → X are L(S i )-Lipschitzian for i = 1, ..., N and there exists λ S such that, Then the system (S, p) is asymptotically stable.
To apply the theorem, we must check the other two conditions. The first one implies that there is some p 0 such that for all possible states x, we have that p i (x) > p 0 . One sufficient condition for this to hold is that for all i, j ∈ [N ], we have some bound on the cost difference f (g(u i , x, ξ), u i , x) − f (g(u j , x, ξ), u j , x) that holds across x ∈ X , possible control selections i and noise ξ. Now let us consider the Lipschitzian (third) condition. In particular, it must hold that for all maps F i (·) from x(k) to x(k + 1, ξ, i) are Lipschitzian with respect to x(k), i.e., g is Lipschitzian with constant L i with respect to the second argument. In addition, it must hold that, for all possible x, formally, With this, we can now claim that the conditions of [14, Theorem 1] hold. Thus, we can conclude that the IFS system defined by the repeated stochastic OCP is asymptotically stable.

Set Up
Given the entire nested noise admixture of (1), even the state-dependent IFS form [14] as considered above is not sufficiently expressive to adequately model the stochastic MPC process. For this section we consider that states and controls arise in some Polish space X . Indeed, we cannot solve (3) directly, as we typically do not have the means to analytically compute the stochastically aggregated quantities. Instead, we take J samples {ξ j } ∼ Ξ, and denoting this finite set asΞ we solve for minimizing a sample average of the optimization, i.e., a SAA approximation, min Recall now the two sources of noise, when considered as a map from x(k) to x(k + 1). First, ξ j themselves are sampled from ξ j ∼ Ξ. The sampling affects the outcome of solving the optimization problem, i.e., u depends on the J samples, u({ξ j }). Next, the actual state x(k + 1) actually appears as by the physical realization of the distribution of Ξ again in the actual system, x(k + 1, ξ).
To model this, we must incorporate the notion of a continuous IFS [7][4], formally a pair (S, p) with probability map p(t, x) on state x with parameter t satisfying, for A ∈ B(X), the borel set on X . Procedurally, given a state x k , the probability density p(·, x k ) governs the realization of the continuously indexed map S(t k , x k ), which is itself deterministic.
To utilize the theoretical results associated with continuously-valued IFS, the process (1) must be appropriately linked to the underlying abstractions. Specifically, p(t, x) must incorporate both the SAA noise η and the output system noise ξ into the parameter t. Then the map S(t, x) corresponds to the output realization x(k + 1, ξ). Now we introduce several notions from [7] associated with an IFS (S, p) and its Markov kernel P .
Recall that the dual U of P is given by, where M f is the set of finite measures and B(X ) Borel measureable functions. The operator P is called Feller if U f ∈ C(X ) for f ∈ C(X ) and nonexpansive if P µ 1 − P µ 2 L ≤ µ 1 − µ 2 L for µ 1 , µ 2 ∈ M f . The desiderata associated with this operator are notions of stability, convergence and ergodicity -broadly speaking the limiting behavior of the probability distributions of the state.
A measure µ ∈ M f is stationary or invariant if P µ = µ. The operator P is asymptotically stable if there exists a stationary distribution µ * and constant q > 0 such that lim n→∞ P n µ − µ * q = 0 Denote the limit points of the sequence of measures defining the process by, ω(µ) = {ν ∈ M f : ∃ mn,n≥1 m n → ∞ and P mn µ → ν} Let C be the family of all sets C ∈ B(X ) for which there exists some finite cover of points with radius , i.e., ∃n and ∃{x 1 , ..., x n } ⊂ X such that 7 Definition 3.1 The operator P is semi-concentrating if for every > 0 there exists C ∈ C and α > 0 such that, Now let us consider explicitly the Markov operator for A ∈ B(X). and, with θ > 0 we have a stability result of the following form. Finally, an additional technical stopping time condition provides the sufficient mechanism to ensure asymptotic stability for P (S,p) .

Inferences and a Research Program
Consider now two possible initial states at k, x and y and a fixed set of realizations t = (η, ξ). Solving the optimization problem, subject to SAA noise, defines p(t, x(k)) as the distribution of chosen u(x(k), η) with the noise defining the homotopy with respect to t. This in turn induces the map S(t, x) as defined by g(u, x(k), ξ) once t, equivalently u, and hence p is chosen.
To consider the assumptions, if for all SAA realizations η, the optimization problem (5) is Lipschitz stable with respect to the input x(k) which holds, e.g., if the map R(x(k + 1, ξ p (η), u), u, x(k)) is strongly convex with respect to u, where we now write the subsequent state as a function of u (the reduced problem), then clearly this will hold globally. Otherwise, for nonconvex objectives with local minimizers satisfying second-order sufficient conditions for optimality, this condition holds locally.

Definition 3.2
The second order sufficient conditions for optimality conditions hold at u if for all ∆u = 0 it holds that, See the results of [12] for upper Lipschitz continuity of the optimal solution u as a function its parameters, which in this case corresponds to x(k).
Remark 3.1 In many cases, u is required to exist in some compact bounded set U. This introduces the necessity to consider active sets in the formulation of the second-order optimality conditions, which add additional notation without additional insight here. Note, however, that in [4] it is shown that if we are constrained to a compact convex set, the invariant measure has Hausdorff dimension zero.
Subsequently, if also g(u, x, ξ) being Lipschitz stable as a function of x as well for all ξ and u then we have achieved sufficient conditions for there being some L such that |p(x, t) − p(y, t)| ≤ Ld(x, y).
Open Problem: In order to utilize this approach, the techniques of upper Lipschitz continuity subject to perturbations (e.g., in the comprehensive monograph [5]) need to become quantitative, to obtain estimates of the moduli of continuity or appropriate scaling metrics.
Let us now turn to the other condition, given by (11). In the context of our stochastic OCP, this implies that certain distributions of noise t = (η, ξ) are inaccessible for some states x(k). Since η can be regarded as exogenous, or state independent, as determined by the samples generating the SAA, it must imply that for certain x(k), there are u that do not lie in the support of the distribution of solutions of the SAA problem across realizations η. Such a question cannot be answered without distributional information with respect to the noise structure of the dynamic process.
Open Problem(s): Taking into context the specific problem-dependent distributional information x(k + 1) ∼ g(u, x(k)), characterize the conditions of finite support of u * as a solution of the optimization problem defined by SAA sampling. 9 We performed a synthetic simulation to illustrate the ergodicity of states in stochastic model predictive control. We consider the four-state system, where Ξ is additive noise. The objective function is the standard MPC tracking objective with regularization: We generated the problem as follows: 1. To encourage contractive dynamics, we took Λ A = diag 1/5 1/8 1/10 1/12 generated a random orthonormal eigenbasis V and let A = V T Λ A V .
2. The tracking and regularization matrices Q and R were similarly made to be positive definite, with Λ Q = diag 5 6 9 15 and Λ R = diag 0.5 2 1 1.5 3. The control matrix B has entires drawn from a uniform random variable over [0, 1], ensuring w.p. one full rank. 6. We ran 20 trials (i.e., twenty such generations described) of 10000 iterations of stochastic MPC with N = 100 samples for each SAA problem. Each output x k+1 was computed from the system matrix with a random draw in Ξ.
It can be seen that, since the process is linear, with E[A + Ξ] = A, we can compute the exact control as the solution to, Thus, the state map satisfies, where η is the perturbation associated with solving the inexact SAA problem. For initial states x and y and given η we have, S(x, Ξ, η) − S(y, Ξ, η) implying that a sufficient condition for the contraction is: This is equivalent to a stable dynamic system for every possible stochastic realization. Thus the fact that it agrees with ergdocitiy of the long run stochastic behavior is indicative of a potential sea of relationships between the aggregation of point realization dynamics and statistically agglomorated dynamics of the system. We computed the cumulative empirical distributions of the states as follows: for all four states, we took the minimum and maximum values over ten thousand iterations and defined a set of equally spaced discretizations as a histogram-bin, counting the proportion of times each state appears in each bin. Figure 1 shows a representative run. It can be seen that the empirical distributions stabilize over the long run, suggesting the ergodicity of the process.

Conclusion
The framework of IFS presents a rich and powerful set of tools in the analysis of limiting statistics of iterative processes. Stochastic MPC can be formulated in this framework; under appropriate conditions, important results can be proven regarding its behavior. These results depend on the conditions that can be studied when one has accurate (either a priori, or data driven) distributional information on the process. This, in turn, suggests a comprehensive program of applied analysis of such problems.