{'fraction_non_alphanumeric': 0.05368263935354367, 'fraction_numerical': 0.00962478768850687, 'mean_word_length': 4.308743169398907, 'pattern_counts': {'":': 0, '<': 4, '<?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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Ergodic Control of Ensembles in the Presence of Non-linear Filters

In many sharing-economy applications, as well as in conventional economy applications, one wishes to regulate the behaviour of an ensemble of agents with guarantees on both the regulation of the ensemble in aggregate and the revenue or quality of service associated with each agent. Previous work [Automatica, Volume 108, 108483, arXiv:1807.03256 ] has developed guarantees of unique ergodicity when there are linear filters. Here, we extend the guarantees to systems including non-linear elements, such as non-linear filters.


Introduction
In an increasing number of sharing-economy applications, one wishes to regulate the stochastic behaviour of an ensemble of agents [14,7,20,9,13,21]. For example, in a virtual power plant [13], one may wish to regulate an ensemble consisting of distributed generation (rooftop photovoltaic panels) and interruptible loads (charging of electric vehicles), such that the overall load can be kept close to a constant over the imbalance settlement period within an electricity market. Each agent enrolled in such a demand-response aggregator provides -at best -probabilistic guarantees on its own response to a signal. At the same time, the agent would like to have some guarantees on its revenue (from the distributed generation) or quality of service (for interruptible loads, such as charging), conditional on its responses. Many other two-sided markets and multi-sided platforms [9] need to be balanced in the sharing economy, including networks of electric vehicles [3,4], ride hailing [9], and room rentals. More broadly, much of the reasoning about fairness in artificial intelligence [21] can be cast in this fashion.
Our work builds on a number of recent results in the area of the use of iterated random functions (IRF, see, e.g. [5]) for modeling the closed loop involving an ensembles of agents competing to acquire or use a shared resource [14,7,9,13]. The motivation for using iterated random functions in such applications is many-fold. First, IRF's have potential to model agent-level behaviour in many man-made systems. For example, IRF's are intuitively appealing for Figure 1: A feedback model employed in [7] and here. C denotes a controller (8); F denotes a filter (7); S i denotes agent i.
modelling ensembles of rational agents orchestrated by means of a feedback signal such as a price, and extensions thereof towards rational inattention. Intuitively, it is appealing to consider each agent picking one of pre-defined behaviours at random, conditional on a state. Notably, using iterated random functions allows us to deal with systems that are not quite large-scale enough to be considered a fluid, but are sufficiently large-scale to prohibit traditional microscopic modeling. Second, the use of IRF is very convenient from a modelling perspective. Surprisingly strong results exists for IRF's, and characterising the predictable and fair behaviour of shared-economy systems in terms of properties of a unique invariant measure is very natural. Finally, the use of IRF in a control setting allows for non-trivial insights: in [7], the difficulty in the use of PI control for regulating access in such settings is discussed. In particular, the loss of ergodicity when using controllers with poles on the unit circle is established. In [13], these phenomena are demonstrated in power-systems applications using standard simulators. Other uses of IRF in a systems-and-control context include the analysis of switched and hybrid systems [2,20].
The work presented here directly extends our original work in [7] by considering classes of nonlinear feedback architectures. In particular, we develop guarantees for the existence of a unique invariant measure in closed loops consisting of nonlinear controllers of ensembles with nonlinear filters, in contrast to the earlier work which restricted itself to linear controllers. This presents significant methodological challenges. Specifically, the techniques establishing ergodicity must be developed to accommodate the wider range of behavior of nonlinear control systems. A linear system has many properties that are invariant across the control and state space, which is distinctly not the case for nonlinear controllers, whose local and global behavior can be distinct. For-mally, ergodicity of IRF is straightforward to establish under iterate-to-iterate contraction guarantees, which naturally coincide with eigenspectrum-associated properties of linear systems.
The techniques establishing ergodicity in this work are founded on appropriately combining the seminal work on stability of nonlinear systems of Lohmiller and Slotine [12] together with tools for establishing ergodicity in IRF, e.g., as found it [15]. This requires a fundamentally different consideration of the random dynamics. Whereas for linear systems, behavior is averaged at every iteration and the individual distinctions across the functional maps can be abstracted away, for nonlinear systems, we rely on the concept of canonical trajectories that represent stable solution paths of each process by itself, and arguments must carefully incorporate how they could interact.

The Closed Loop as a State-Dependent IRF
Let K be a closed subset of R n with the usual Borel σ-algebra B (K ) consisting of all possible events. We consider a discrete-time-homogeneous Markov chain on K with the transition operator P as follows: for x ∈ K , G ∈ B (K ) Conditioned on an initial distribution ξ, the random variable X k is distributed according to the probability measure ξ k which is determined inductively by If there exists a probability measure ν on K which is a fixed point for the iteration scheme described by the equation (2), then ν is called an invariant probability measure with respect to the Markov process Further, ν is called attractive, if for all probability measure µ the sequence {ξ k } defined by (2) with initial condition µ converges to ν in distribution.
We assume there are w i ∈ N state transition maps W ij : R ni → R ni , j = 1, . . . , w i for agent i and h i ∈ N output maps H i : R ni → D i , = 1, . . . , h i for each agent i, where D i is the space defining agent i's behaviors (demands, in the shared economy case). The evolution of the states and the corresponding demands then satisfy: where the choice of agent i's response at time k is governed by probability functions p ij : Π → [0, 1], j = 1, . . . , w i , respectively p i : Π → [0, 1], = 1, . . . , h i , where Π ⊆ R c is a set of control signals, which themselves are governed by state dependent function π : X → Π. For brevity we use π(x(k)) and π(k) interchangeably and denote π as both an element of Π and a function whose domain is Π depending on context. Specifically, for each agent i, we have for all k ∈ N that Additionally, for all π ∈ Π, i = 1, . . . , N it holds that The outputs y i (k) depend on x i (k) and the signal π(k) only for all k. We shall denote the stochastic realization of the selected map as ξ(k) = ξ(x(k)) ∈ Ξ. We can stack the agents' state vectors together to define the filter and control system, C : If we denote by X i , i = 1, . . . , N, X C and X F the state spaces of the agents, the controller and the filter, then the system evolves on the overall state space where each of the maps F m is of the form and the maps F m are indexed by indices m from the set By the independence assumption on the choice of the transition maps and output maps for the agents, for each multi-index m = ((1, j 1 ), . . . , (N, j N ), (1, l 1 ), . . . , (N, l N )) in this set, the probability of selecting the corresponding function F m is given by p ili (π(k)) =: q m (π(k)). (12) Let us denote σ(k, Clearly, we have obtained an iterated random function with state dependent prob abilities.

Stability of Nonlinear Systems and Canonical Trajectories
Each composite map F m takes x(k) to x(k + 1) in a deterministically defined way, i.e., it corresponds to a particular filter and control action given the state x(k). As such it can be associated to a dynamic system in its own right, and we define some classical notions of stability for these systems. In the sequel we shall see that careful agglomeration of the associated quantities measuring and confirming stability for these maps shall endow ergodic properties of the composite IRF. We denote F (k) m (x(0)) to be k repeated applications of F m starting from x(0).
We present the definitions and propositions necessary for our development. The notions are classical in the literature, e.g. [12] and we leave the reader to consult references for definitions of specific technical notions, such as L and K L functions. In addition, we write F (k) m (x) = φ m (k, x, u m (·)) to indicate that the map F m (x) physically corresponds to a controlled system φ m with control law u m (x). We adjust the standard definitions accordingly. A significant property of a deterministic system is asymptotic incremental stability. Definition 1. (Uniform Asymptotic Incremental Stability) [12] The system F m is uniformly asymptotically incrementally stable in a positively invariant set X if there exists β ∈ K L such that for any pair of initial states x 1 (0), x 2 (0) ∈ X , for all k ≥ k 0 for some k 0 > 0, the following holds If X = R n , then the system F m is called uniformly globally asymptotically incrementally stable.
It is common that demonstrating the existence of a Lyapunov function is a technique used to demonstrate a system's stability. Here, we note the underutilized fact that the reverse also holds as well.

Proposition 2.
[10] If system F m (x) is uniformly globally asymptotically incrementally stable then there exist a smooth function V m : R d → R ≥0 , functions α 1 , α 2 ∈ K ∞ and α 3 : R ≥0 → R ≥0 positive definite such that there exists x (m) (k) such that for all x 1 , x 2 ∈ R n and trajectories of F (k) m (x(0)) denoted by x(k) the following holds: We shall define x (m) as the canonical stable trajectory associated with map F m .
In consideration of the IRF, we shall also make use of the notion of a stochastic Lyapunov function [16], and the associated condition for ergodicity. Finally, we will consider contractive systems, which guarantee stability for deterministic processes. Let M n (R) denote the set of all n × n matrices with real-entries. Given P, Q ∈ M n (R) be symmetric, we write P Q if and only if x P x ≤ x Qx ∀x ∈ R n . Definition 4. (Uniform Contraction) Assume that F m is continuously differentiable in x on a positively invariant set X ⊆ R n . Then the system is uniformly contracting in X if there exist a non-singular matrix-valued function ψ m : R d × R n → M n (R) and constants µ, η, ρ ∈ R + such that for all x(k) ∈ R n , we have ηI ψ m (u(x(k)), x(k)) ψ m (u(x(k)), x(k)) ρI, where the matrix M m (u, x) is defined as If X = R n , then we the system F m is uniformly globally contracting.

Main Result
For a linear controller and filter, we have established [7] conditions that assure the existence of a unique invariant measure for the closed loop. This is often referred to as the the "unique ergodicity" property in the language of [7]. Let us now consider non-linear controllers and non-linear filters and establish conditions that ensure unique ergodicity of the feedback system in Figure 1. We present our first Theorem on unique ergodicity as guaranteed by global stability properties of the nonlinear control systems {F m (x)}.
Theorem 5. Consider the closed loop stochastic feedback system described in Section 2. Furthermore, assume: (i) we have globally Lipschitz-continuous and continuously differentiable functions W ij and H ij such that each F m is globally Lipschitz with constant l m ; (ii) there are scalars δ, δ > 0 such that p ij (π) ≥ δ > 0, p ij (π) ≥ δ > 0 for all π ∈ Π and all (i, j). Furthermore, for all π ∈ Π the Markov matrix induced by p ij is irreducible.
(iii) the set Π is compact; (iv) for all m, F m (x(k)) is Uniformly Globally Asymptotically Stable and satisfies one of the following conditions: (a) max m l m (2 − |M|δ) < 1; (b) For all m, for all x, x ∈ X it holds that π(F m (x)) − π(F m (x )) ≤ κ x − x with κ < 1, i.e., π • F m is a contraction.
Then, the feedback loop has a unique, attractive invariant measure. In particular, the system is uniquely ergodic.
Proof. By the compactness of Π, there exists a limit point π of the sequence π(k) generated by the IRF. By the irreducibility of p ij (π ), it has an invariant distribution ν . Assumption (iv) and Proposition 2 imply the existence of a set {x (m) (k)} of canonical convergent trajectories together with Lyapunov function sequences V m satisfying Now define the stochastic Lyapunov function [16], Consider a trajectory for which withσ is such that π(k) = π regardless of x(k). It holds that, Taking expectations, recalling the stationary distribution ν * , we obtain that, and, which implies that x(k) driven by the process {Fσ (k) (x(k))} is stable in probability and that the IRF is ergodic. We now consider the IRF as proceeding with general π(k), i.e., not fixed at π * . We divide the argument into two cases as depending on which of condition iv above holds.
Case (iv-b) π • F m as a map from Π to Π is a contraction. Then by Kakutani's fixed point theorem [11], π k must converge to π * above and thus asymptotically σ behaves asσ.
Case (iv-a) Now consider a contraction argument involving two stochastic process paths of x(k) for the non-linear IRF, X(k) andX(k), denotingx(k + 1, π(X(k))) the stochastic step fromX(k) to k + 1 governed by the probability mappings of X(k) (i.e., π(X(k))): W 2 (X(k + 1),X(k + 1)) ≤ W 2 (X(k + 1, π(X(k))),x(k + 1, π(X(k)))) +W 2 (x(k + 1, π(X(k))),X(k + 1, π(X(k)))) ≤ m E X(k) l m π m (X(k))W 2 (X(k),X(k)) where W 2 is Wasserstein-2 distance [19] and the first inequality is just the triangle inequality. For the second inequality, for the first term the same π(X(k)) governs the probabilistic function selection and so the distances of the next iterate is the weighted, by the probabilities in π(X(k)), average over the corresponding distances for each of the F m , which are its Lipschitz constants. For the second term, considering the Wasserstein-2 distance is the distance corresponding to the optimal transference plan, recall by the assumptions that only for at most, 1 − |M|δ of the probability mass of π can result in a different map m to apply at k for π(X(k)) compared to π(X(k)), and if indeed a different map is chosen the distances of the two outputs are bounded as according to the Lipschitzianness of each F m with a bound max m l m . The coupling contraction now implies ergodicity.
It can be observed that the conditions are relatively strong, but they are the first and thus far the weakest, to the best of our knowledge, to establish unique probabilistic convergence in the nonlinear setting and as such can be considered the start of a research program. One of the main considerations for future work is in particular to relax the global Lipschitzianity conditions.
In addition, however, if the individual systems F m satisfy a uniform stability condition, guarantees could be shown in terms of a boundedness of the trajectory, without quantitative contraction assumptions. Theorem 6. Consider the closed loop feedback system in Figure 1 and formalized in Section 2. Assume that: (i) There exists a β, a region X , with x(0) ∈ X , and, for all m, there exists a trajectory x (m) (k), a positive definite metric M (m) = Θ T m Θ m centered at x (m) (k) such that for all x ∈ X , it holds that for (ii) There exists some R such that Then, there exists some D > 0 such that for all x(0) and , is the convex hull of all stable trajectories of {F m }, m ∈ M and dist(y,X) is the projection ontoX in the L 2 norm, i.e., min x∈X x − y .
Remark 7. Following [12, Section 5] the condition (i) above ensures that all neighbouring trajectories converge, i.e., the system dynamics exhibit global exponential convergence to a single trajectory.
Proof. Consider a set of trajectories {x (m) (k)} generated by repeated application of the map F m (·). By (i) and [12,Theorem 3], we have that any potential trajectoryx starting in X converges exponentially to x (m) (k). Thus, there exists a λ m < 1 such that and for any x, Since M is finite, there exists λ = max m λ m < 1. Consider any general trajectory x(k) generated by the IRF {F σ k (·)}. Note that, and so, since x(k + 1) = F σ k (x(k)) and now using (ii), which now implies, for all possible IRF realizations {σ k }, dist x(k + 1),X(k + 1) and the Theorem holds with D = λR (1−λ) .

Illustrations and Discussion
Let us now return to the example of the control of the ensemble mentioned in the introduction. There [17,3], we have a fleet of plug-in hybrid vehicles. The vehicles randomly select a mode of operation (electric, non-electric) at each time step based on a feedback signal (pollution levels). PI control is commonly used to regulate the aggregate air pollution emissions produced by the fleet, turning the internal combustion engines on and off. The filter considered is also non-linear, considering the maximum of the emissions recorded within a time window. This filter [14] is clearly non-linear, and only marginally stable in the realization of [14, Step 2 of the proof of In the margin, let us mention that one could also use incremental input to state stability, as suggested by [13].
We believe our results may be of use in the context of many further smartcity applications, for a number of reasons. Often, in such applications we often use a feedback signal (sometimes a price) to regulate access to a constrained resource of an ensemble of agents that (often) make binary decisions. In many such applications one employs an algorithm such as a PI control to regulate the price to orchestrate the behaviour of the ensemble towards some desirable outcome. Examples of such feedback loops can be readily found in the literature. For example in [8] agents stochastically bid for access to priority parking in a parking lot. In this application the feedback signal regulates the occupancy of the car park. Non-linearity may arise in the manner in which occupancy is filtered, or in order allocate access in a "fair" manner. Other examples include transmission losses in power-systems applications [13] and the Bureau of Public Roads (BPR) functions [14], which relate the travel time to the traffic flow in transportation research.

Conclusions
We have shown conditions under which non-linear filters allow for unique ergodicity within the control of ensembles. This has numerous applications in fields where the filters model non-linear physics of some underlying systems, such as water, transportation, and power systems.
In a companion paper [13], we show one more condition. In particular, in [13, Section V, Theorem 2], we show that for every incrementally inputto-state stable [1] controller and filter compatible with the feedback structure of Figure 1, the feedback loop has a unique, attractive invariant measure and hence the system is uniquely ergodic. Further conditions are left as a subject of further work. One could, for instance, consider further conditions following [10] and using the arguments of [18], which have shown that certain stability and contraction properties are equivalent, or using conditions of [6].