Online Control in Population Dynamics

Authors: noah  golowich
hazan : zhou
dhruv  rohatgi
y jennifer sun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:27:19

Abstract: The study of population dynamics originated with early sociological works but has since extended into many fields, including biology, epidemiology, evolutionary game theory, and economics. Most studies on population dynamics focus on the problem of prediction rather than control. Existing mathematical models for population control are often restricted to specific, noise-free dynamics, while real-world population changes can be complex and adversarial. 

To address this gap, we propose a new framework based on the paradigm of online control. We first characterize a set of linear dynamical systems that can naturally model evolving populations. We then give an efficient gradient-based controller for these systems, with near-optimal regret bounds with respect to a broad class of linear policies. Our empirical evaluations demonstrate the effectiveness of the proposed algorithm for population control even in non-linear models such as SIR and replicator dynamics.

Main paper: 
 introduction: 
 Dynamical systems involving populations are ubiquitous in describing processes that arise in natural environments. As one example, the SIR model [26] is a fundamental concept in epidemiology, used to describe the spread of infectious diseases within a population. It divides the population into three groups -Susceptible (S), Infected (I) and Removed (R). A susceptible individual has not contracted the disease but has the chance to be infected if interacting with an infected individual. A removed individual either has recovered from the disease and gained immunity or is deceased. The population evolves over time according to three ordinary differential equations:EQUATIONfor constants β, θ ą 0 representing the infection and recovery rate, respectively. Numerous extensions of this basic model have been proposed to better capture how epidemics evolve and spread [8] .Beyond epidemiology, population dynamics naturally arise in many other fields, notably evolutionary game theory [23] , biology [14, 7] , and the analysis of genetic algorithms [39, 25] . For any dynamical system, it is natural to ask how it might best be controlled. For instance, controlling the spread of an infectious disease while minimizing externalities is a problem of significant societal importance.In many natural models, these dynamics tend to be nonlinear, so the control problem is often computationally intractable. Existing algorithms are designed on a case-by-case basis by positing a specific system of differential equations, and then numerically or analytically solving for the optimal controller. Unfortunately, this approach is not robust to adversarial shocks to the system and cannot adapt to time-varying cost functions.˚MIT. nzg@mit.edu.: Google DeepMind & Princeton University. ehazan@princeton.edu.; Princeton University. zhoul@princeton.edu. § MIT. drohatgi@mit.edu. ¶ Princeton University. ys7849@princeton.edu.A new approach for population control. In this paper we propose a generic and robust methodology for population control, drawing on the framework and tools from online non-stochastic control theory to obtain a computationally efficient gradient-based method of control. In online non-stochastic control, at every time t " 1, . . . , T , the learner is faced with a state x t and must choose a control u t . The learner then incurs cost according to some time-varying cost function c t px t , u t q evaluated at the current state/control pair, and the state evolves as:x t`1 :" f px t , u t q `wt ,where f describes the (known) discrete-time dynamics, x t`1 is the next state, and w t is an adversarially-chosen perturbation. A policy is a mapping from states to controls. The goal of the learner is to minimize regret with respect to some rich policy class Π, formally defined byEQUATIONwhere px π t , u π t q is the state/control pair at time t had policy π been carried out since time 1. As with prior work in online control [1] , our method is theoretically grounded by regret guarantees for a broad class of Linear Dynamical Systems (LDSs). The key algorithmic and technical challenge we overcome is that prior methods only give regret bounds against comparator policies that strongly stabilize the LDS (Definition 4). Such policies force the magnitude of the state to decrease exponentially fast in the absence of noise. Unfortunately, for applications to population dynamics, even the assumption that such policies exist -let alone perform well -is fundamentally unreasonable, since it essentially implies that the population can be made to exponentially shrink.A priori, one might hope to generically overcome this issue, by broadening the comparator class to all policies that marginally stabilize the LDS (informally, these are policies under which the magnitude of the state does not blow up). But we show that, in general, it is impossible to achieve sub-linear regret against that class -a result that may be of independent interest in online control: 6Theorem 1 (Informal statement of Theorem 25) . There is a distribution D over LDSs with state space and control space given by R, such that any online control algorithm on a system L " D incurs expected regret ΩpT q against the class of time-invariant linear policies that marginally stabilize L.For general LDSs, it's not obvious if there is a natural "intermediate" comparator class that does not require strong stabilizability and does enable control with low regret. However, systems that model populations possess rich additional structure, since they can be interpreted as controlled Markov chains. 7 In this paper, leveraging that structure, we design an algorithm GPC-Simplex for online control that applies to LDSs constrained to the simplex (Definition 3), and achieves strong regret bounds against a natural comparator class of policies with bounded mixing time (Definition 6).Throughout this work, we model a population as a distribution over d different categories, evolving over T discrete timesteps. For simplicity, we assume that u t is a d-dimensional real vector.Theoretical guarantees for online population control. We introduce the simplex LDS model (Definition 3), which is a modification of the standard LDS model (Definition 9) that ensures the states px t q t always represent valid distributions, i.e. never leave the simplex ∆ d . Informally, given state x t P ∆ d and control u t P R d ě0 with }u t } 1 ď 1, the next state is x t`1 " p1 ´γt q ¨rp1 ´}u t } 1 qAx t `Bu t s `γt ¨wt , where A, B are known stochastic matrices, γ t P r0, 1s is the observed perturbation strength, 8 and w t P ∆ d is an unknown perturbation. The perturbation w t can be interpreted as representing an adversary that can add individuals from a population with distribution w t to the population under study. Intuitively, u t represents a distribution over d possible interventions as well as a "null intervention".For any simplex LDS L and mixing time parameter τ ą 0, we define a class K τ pLq (Definition 6), which roughly consists of the linear time-invariant policies under which the state of the system would mix to stationarity in time τ , in the absence of noise. Our main theoretical contribution is an algorithm GPC-Simplex that achieves low regret against this policy class: Theorem 2 (Informal version of Theorem 7) . Let L be a simplex LDS on ∆ d , and let τ ą 0. For any adversarially-chosen perturbations pw t q t , perturbation strengths pγ t q t , and convex and Lipschitz cost functions pc t q t , the algorithm GPC-Simplex performs T steps of online control on L with regret Õpτ 7{2 ? dT q against K τ pLq.Finally, analogously Theorem 1, we show that the mixing time assumption cannot be removed: it is impossible to achieve sub-linear regret (for online control of a simplex LDS) against the class of all linear time-invariant policies (Theorem 8).Experimental evaluations. To illustrate the practicality of our results, we apply (a generalization of) GPC-Simplex to controlled versions of (a) the SIR model for disease transmission (Section 4), and (b) the replicator dynamics from evolutionary game theory (Appendix H). In the former, closed-form optimal controllers are known in the absence of perturbations [27] . We find that GPC-Simplex learns characteristics of the optimal control (e.g. the "turning point" phase transition where interventions stop once herd immunity is reached). Moreover, our algorithm is robust even in the presence of adversarial perturbations, where previous theoretical results no longer apply. In the latter, we demonstrate that even when the control affects the population only indirectly, through the replicator dynamics payoff matrix, GPC-Simplex can learn to control the population effectively, and is more robust to noisy cost functions than a one-step best response controller.Online non-stochastic control. In recent years, the machine learning community has witnessed an increasing interest in non-stochastic control problems (e.g. [1, 38, 19] ). Unlike the classical setting of stochastic control, in non-stochastic control the dynamics are subject to time-varying, adversarially chosen perturbations and cost functions. See [21] for a survey of prior results. Most relevant to our work is the Gradient Perturbation Controller (GPC) for controlling general LDSs [1] . All existing controllers only provide provable regret guarantees against policies that strongly stabilize the system.Population growth models. There is extensive research on modeling the evolution of populations in sociology, biology and economics. Besides the pioneering work of [33] , notable models include the SIR model from epidemiology [26] , the Lotka-Volterra model for predator-prey dynamics [32, 40] and the replicator dynamics from evolutionary game theory [23] . Recent years have seen intensive study of controlled versions of the SIR model -see e.g. empirical work [10] , vaccination control models [13] , and many others [15, 12, 30, 17] . Most relevant to our work is the quarantine control model, where the control reduces the effective transmission rate. Some works consider optimal control in the noiseless setting [27, 5] ; follow-up work [34] considers a budget constraint on the control. None of these prior works can handle the general case of adversarial noise and cost functions. 
definitions and setup: 
 Notation. Denote S d :"! M P r0, 1s dˆd : ř d i"1 M i,j " 1 @j P rds) as the set of d ˆd columnstochastic matrices. For a ą 0, define S d a :" ta ¨M : M P S d u and S d ďa :"Ť 0ďa 1 ďa S d a 1 . Let ∆ d denote the simplex in R d . Similarly, we define ∆ d α :" α ¨∆d and ∆ d ďα :" Ť 0ďα 1 ďα ∆ d α 1. Given a square matrix M P R dˆd , let M ¨,j denote the jth column of M . We consider the following matrix norms: }M } denotes the spectral norm of M , }M } 2 2,1 :"ř d j"1 }M ¨,j } 2 1is the sum of the squares of the 1 norms of the columns of M , and }M } 1Ñ1 :" sup xPR d :}x} 1 "1 }M x} 1 .The standard model in online control is the linear dynamical system (LDS). We define a simplex LDS to be an LDS where the state of the system always lies in the simplex. This requires enforcing certain constraints on the transition matrices, the control, and the noise: Definition 3 (Simplex LDS). Let d P N. A simplex LDS on ∆ d is a tuple L " pA, B, I, x 1 , pγ t q tPN , pw t q tPN , pc t q tPN q, where A, B P S d are the transition matrices; I Ď ∆ d ď1 is the valid control set; x 1 P ∆ d is the initial state; γ t P r0, 1s, w t P ∆ d are the noise strength and noise value at time t; and c t : ∆ d ˆI Ñ R is the cost function at time t. These parameters define a dynamical system where the state at time t " 1 is x 1 . For each t ě 1, given state x t and control u t P I at time t, the state at time t `1 isEQUATIONand the cost incurred at time t is c t px t , u t q.Note that since the set of possible controls I is contained in ∆ d ď1 , the states px t q t are guaranteed to remain within the simplex for all t. In this paper, we will assume that I " Ť αPrα,αs ∆ d α , for some parameters α, α P r0, 1s, which represent lower and upper bounds on the strength of the control.Online non-stochastic control. Let L " pA, B, x 1 , pγ t q tPN , pw t q tPN , pc t q tPN , Iq be a simplex LDS and let T P N `. We assume that the transition matrices A, B are known to the controller at the beginning of time, but the perturbations pw t q T t"1 are unknown. At each step 1 ď t ď T , the controller observes x t and γ t , plays a control u t P I, and then observes the cost function c t and incurs cost c t px t , u t q. The system then evolves according to Eq. ( 4). Note that our assumption that the controller observes γ t contrasts with some of the existing work on nonstochastic control [1, 21] , in which no information about the adversarial disturbances is known. In Appendix B, we justify the learner's ability to observe γ t by observing that in many situations, the learner observes the counts of individuals in a populations (in addition to their proportions, represented by the state x t ), and that this additional information allows computation of γ t .The goal of the controller is to minimize regret with respect to some class K " KpLq of comparator policies. Formally, for any fixed dynamical system and any time-invariant and Markovian policy K : ∆ d Ñ I, let px t pKqq t and pu t pKqq t denote the counterfactual sequences of states and controls that would have been obtained by following policy K. Then the regret of the controller on observed sequences px t q t and pu t q t with respect to K isregret K :" T ÿ t"1 c t px t , u t q ´inf KPK T ÿ t"1 c t px t pKq, u t pKqq.The following assumption on the cost functions of L is standard in online control [1, 3, 38, 37] : Assumption 1. The cost functions c t : ∆ d ˆI Ñ R are convex and L-Lipschitz, in the following sense: for all x, x 1 P ∆ d and u, u 1 P I, we have |c t px, uq ´ct px 1 , u 1 q| ď L ¨p}x ´x1 } 1 `}u ´u1 } 1 q.In prior works on non-stochastic control for linear dynamical systems [1] , the comparator class K " K κ,ρ pLq is defined to be the set of linear, time-invariant policies x Þ Ñ Kx where K P R dˆd pκ, ρq-strongly stabilizes L: Definition 4. A matrix M P R dˆd is pκ, ρq-strongly stable if there is a matrix H P R dˆd so that }H ´1M H} ď 1 ´ρ and }M }, }H}, }H ´1} ď κ. A matrix K P R dˆd is said to pκ, ρq-strongly stabilize an LDS with transition matrices A, B P R dˆd if A `BK is pκ, ρq-strongly stable.The regret bounds against K κ,ρ pLq scale with ρ ´1, and so are vacuous for ρ " 0 [1] . Unfortunately, in the simplex LDS setting, no policies satisfy the analogous notion of strong stability (see discussion in Section 3) unless ρ " 0. Intuitively, the reason is that a pκ, ρq-strongly stable policy with ρ ą 0 makes the state converge to 0 in the absence of noise.What is a richer but still-tractable comparator class for a simplex LDS? We propose the class of linear, time-invariant policies under which (a) the state of the LDS mixes, when viewed as a distribution, and (b) the level of control }u t } 1 is independent of the state x t . Formally, we make the following definitions: Definition 5. Given t P N and a matrix X P S d with unique stationary distribution π P ∆ d , we define D X ptq :" sup pP∆ d }X t p ´π} 1 and DX ptq :" sup p,qP∆ d }X t ¨pp ´qq} 1 . Moreover we define t mix pX, εq :" min tPN tt : D X ptq ď εu for each ą 0, and we write t mix pXq :" t mix pX, 1{4q. 9Definition 6 (Mixing a simplex LDS). Let L be a simplex LDS with transition matrices A, B P S d and control set I " Ť αPrα,αs ∆ d α . A matrix K P S d rα,αs is said to τ -mix L if t mix pA K q ď τ, whereEQUATIONWe define the comparator class K τ " K τ pLq as the set of linear, time-invariant policies x Þ Ñ Kx where K P S d rα,αs τ -mixes L.Notice that for any K P S d rα,αs , the linear policy u t :" Kx t always plays controls in the control set I, and the dynamics Eq. ( 4) under this policy can be written as x t`1 " p1 ´γt q ¨AK x t `γt ¨wt .Notice that by considering the comparator class K τ , we require the control norm to be independent of the state. This assumption is needed for technical reasons: without it, since Ax is multiplied by 1 ´}u} 1 in the transition dynamics (see Equation ( 4)), even a "linear" policy u :" Kx does not induce a linear transition. Hence, it would no longer be clear how one might define mixing time of a linear policy. It is a very interesting question whether there is a more natural (yet still tractable) definition of a simplex LDS that avoids this issue. 
online algorithm and theoretical guarantee: 
 In this section, we describe our main upper bound and accompanying algorithm for the setting of online control in a simplex LDS L. As discussed above, we assume that the set of valid controls is given by I " Ť αPrα,αs ∆ d α , for some constants 0 ď α ď α ď 1, representing lower and upper bounds on the strength of the control. 10For convenience, we write α t :" }u t } 1 and u 1 t " u t {α t P ∆ d (if α t " 0, we set u 1 t :" 0). The dynamical system Eq. (4) can then be expressed as follows:x t`1 " p1 ´γt q ¨pp1 ´αt q ¨Ax t `αt ¨Bu 1 t q `γt ¨wt .We aim to obtain a regret guarantee as in Eq. ( 3) with respect to some rich class of comparator policies K . As is typical in existing work on linear nonstochastic control, we take K to be a class of time-invariant linear policies, i.e. policies that choose control u t :" Kx t at time t for some matrix K P R dˆd . In the standard setting of nonstochastic control, it is typically further assumed that all policies in the comparator class strongly stabilize the LDS (Definition 4). 11 The naive generalization of such a requirement in our setting would be that A K is strongly stable; however, this is impossible, since no stochastic matrix can be strongly stable. Instead, we aim to compete against the class K " K τ pLq of time-invariant linear policies that (a) have fixed level of control in rα, αs, and (b) τ -mix L (Definition 6). We view the second condition as a natural distributional analogue of strong stabilizability; the first condition is needed for τ -mixing to even be well-defined.Algorithm description. Our main algorithm, GPC-Simplex (Algorithm 1), is a modification of the GPC algorithm [1, 21] . As a refresher, GPC chooses the controls u t by learning a disturbance-action policy: a policy u t :" Kx t `řH i"1 M ris w t´i , where K is a known, fixed matrix that strongly stabilizes the LDS; w t´1 , . . . , w t´H are the recent noise terms; and M r1s , . . . , M rHs are learnable, matrix-valued parameters which we abbreviate as M r1:Hs . The key advantage of this parametrization of policies (as opposed to a simpler parametrization such as u t " Kx t for a parameter K) is that the entire trajectory is linear in the parameters, and not a high-degree polynomial. Thus, optimizing the cost of a trajectory over the class of disturbance-action policies is a convex problem in M r1:Hs . But why is the class of disturbance-action policies expressive enough to compete against the comparator class? This is where GPC crucially uses strong stabilizability. Notice that in the absence of noise, every disturbance-action policy is identical to the fixed policy u t :" Kx t . This is fine when K and the comparator class are strongly stabilizing, since in the absence of noise, all strongly stabilizing policies rapidly force the state to 0, and thus incur very similar costs in the long run. But in the simplex LDS setting, strong stabilizability is impossible. While all policies in K mix the LDS, they may mix to different states, which may incur different costs. There is no reason to expect that an arbitrary K P K , chosen before observing the cost functions, will have low regret against all policies in K .We fix this issue by enriching the class of disturbance-action policies with an additional parameter p P ∆ d which, roughly speaking, represents the desired stationary distribution to which x t would converge, in the absence of noise, as t Ñ 8. It is unreasonable to expect prior knowledge of the optimal choice of p, which depends on the not-yet-observed cost functions. Thus, GPC-Simplex instead learns p together with M r1:Hs . We retain the property that the requisite online learning problem is convex in the parameters, and therefore can be efficiently solved via an online convex optimization algorithm (as discussed in Appendix C.1, we use lazy mirror descent, LazyMD). One advantage of GPC-Simplex over GPC is that the former requires no knowledge of the fixed "reference" policy K (which, in the context of GPC, had to be strongly stabilizing). While such K is needed in the context of GPC to bound a certain approximation error involving the cost functions, in the context of GPC-Simplex this approximation error may be bounded by some simple casework involving properties of stochastic matrices (see Appendix C.3).Formally, for parameters a 0 P rα, αs and H P N, GPC-Simplex considers a class of policies parametrized by the set X d,H,a0,α :" Ť aPra0,αs ∆ d a ˆpS d a q H . We abbreviate elements pp, pM r1s , . . . , M rHs qq P X d,H,a0,α by pp, M r1:Hs q. The high level idea of GPC-Simplex, like that of GPC, is to perform online convex optimization on the domain X d,H,a0,α (Line 10). At each time t, the current iterate pp t , M r1:Hs t q, which defines a policy π pt,M r1:Hs t , is used to choose the control u t . The optimization subroutine then receives a new loss function t : X d,H,a0,α Ñ R based on the newly observed cost function c t . As with GPC, showing that this algorithm works requires showing that the policy class is sufficiently expressive. Unlike for GPC, our comparator policies are not strongly stabilizing, so new ideas are required for the proof.We next formally define the policy π p,M r1:Hs associated with parameters pp, M r1:Hs q, and the loss function t used to update the optimization algorithm at time t. Parametrization of policies. First, for t P rT s and i P N `, we define the weights λ t,i :" γ t´i ¨i´1 ź j"1 p1 ´γt´j q, λt,i :"EQUATIONWe write w 0 :" x 1 , γ 0 " 1, and w t " 0 for t ă 0 as a matter of convention. 12 λ t,i can be interpreted as the "influence of perturbation w t´i on the state x t ", and λt,i can be interpreted as the "influence of perturbations prior to time step t ´i on the state x t ". An element pp, M r1:Hs q P X d,H,a0,α induces a policy 13 at time t, denoted π p,M r1:Hs t , via the following variant of the disturbance-action control [1] :EQUATIONIn Line 6 of GPC-Simplex, the control u t is chosen to be π pt,M r1:Hs t t pw t´1:t´H q, which belongs to ∆ d }pt}1 (using ř H i"0 λ t,i " 1) and hence to the constraint set I (since }p t } 1 P ra 0 , αs Ă rα, αs).12 As a result of this convention, we have ř t i"1 λt,i " 1 for all t P rT s, and λt,i " 0 for all i ą t. 13 Technically, we are slightly abusing terminology here, since π p,M r1:Hs t takes as input a set of the previous H disturbances, δt´1:t´H , as opposed to the current state xt.Algorithm 1 GPC-Simplex: GPC for Simplex LDS Require: Linear system A, B, mixing time τ ą 0 for comparator class, horizon parameter H P N, set of valid controls I " Ť αPrα,αs α ¨∆d , total number of time steps T .1: Write τ A :" t mix pAq, and define a 0 :" maxtα, mintα, 1tτ A ą 4τ u{p96τ quu.2: Initialize an instance LazyMD of mirror descent (Algorithm 2) for the domain X d,H,a0,α with the regularizer R d,H (defined in Appendix C.1) and step size η " c a dH lnpdq{pLτ 2 log 2 pT q ? T q, for a sufficiently small constant c. Receive cost c t px t , u t q.8:Observe x t`1 , γ t and compute w t " γ ´1 t px t`1 ´p1 ´γt qrp1 ´}u t } 1 qAx t `Bu t sq. (If γ t " 0, then set w t " 0.)9:Define loss function t pp, M r1:Hs q :" c t px t pp, M r1:Hs q, u t pp, M r1:Hs qq. Loss functions. For pp, M r1:Hs q P X d,H,a0,α , we let x t pp, M r1:Hs q and u t pp, M r1:Hs q denote the state and control at step t obtained by following the policy π p,M r1:Hs s at all time steps s prior to t (see Eqs. (20) and (21) in the appendix for precise definitions). We then define t pp, M r1:Hs q to be the evaluation of the adversary's cost function c t on the state-action pair px t pp, M r1:Hs q, u t pp, M r1:Hs qq (Line 9).Main guarantee and proof overview. Theorem 7 gives our regret upper bound for GPC-Simplex: Theorem 7. Let d, T P N and τ ą 0. Let L " pA, B, I, x 1 , pγ t q tPN , pw t q tPN , pc t q tPN q be a simplex LDS with cost functions pc t q t satisfying Assumption 1 for some L ą 0. Set H :" τ rlogp2LT 3 qs. Then the iterates px t , u t q T t"1 of GPC-Simplex (Algorithm 1) with input pA, B, τ, H, I, T q satisfy:regret K τ pLq :" T ÿ t"1 c t px t , u t q ´inf KPK τ pLq T ÿ t"1 c t px t pKq, u t pKqq ď ÕpLτ 7{2 d 1{2 ? T q,where Õp¨q hides only universal constants and poly-logarithmic dependence in T . Moreover, the time complexity of GPC-Simplex is polypd, T q.While for simplicity we have stated our results for obliviously chosen pγ t q t , pw t q t , pc t q t , since GPC-Simplex is deterministic the result also holds when these parameters are chosen adaptively by an adversary. See Appendix C for the formal proof of Theorem 7.Lower bound. We also show that the mixing assumption on the comparator class K τ pLq (Definition 6) cannot be removed. In particular, without that assumption, if the valid control set I is restricted to controls u t of norm at mostly roughly Op1{T q, then linear regret is unavoidable. 14 Theorem 8 (Informal statement of Theorem 30). Let β ą 0 be a sufficiently large constant. For any T P N, there is a distribution D over simplex LDSs with state space ∆ 2 and control space Ť αPr0,β{T s ∆ 2 α , such that any online control algorithm on a system L " D incurs expected regret ΩpT q against the class of all time-invariant linear policies x Þ Ñ Kx where K P Ť αPr0,β{T s S d α . 
experimental evaluation: 
 The previous sections focused on linear systems, but in fact GPC-Simplex can be easily modified to control non-linear systems, for similar reasons as in prior work [2] . It suffices for the dynamics to 14 We remark that, with the mixing assumption, Theorem 7 does achieve Õp ? T q regret when I :" Ť αPr0,Op1{T qs ∆ 2 α . In particular, there is no hidden dependence on I in the regret bound.have the formx t`1 :" p1 ´γt qf px t , u t q `γt w t (9) for known f , observed γ t , and unknown w t . See Appendix E for discussion of the needed modifications and other implementation details. Relevant code is open-sourced in [16] .As a case study, in this section we apply GPC-Simplex (Algorithm 1) to a disease transmission model -specifically, a controlled generalization of the SIR model introduced earlier. In Appendix H we apply GPC-Simplex to a controlled version of the replicator dynamics from evolutionary game theory.A controlled disease transmission model. The Susceptible-Infectious-Recovered (SIR) model is a basic model for the spread of an epidemic [26] . The SIR model has been extensively studied since last century [36, 41, 4, 24, 6] and attracted renewed interest during the COVID-19 pandemic [10, 29, 9] .As discussed previously, this model posits that a population consists of susceptible (S), infected (I), and recovered (R) individuals. When a susceptible individual comes into contact with an infected individual, the susceptible individual becomes infected at some "transmission rate" β. Infected patients become uninfected and gain immunity at some "recovery rate" θ. We consider a natural generalization of the standard dynamics Eq. ( 1) where recovered individuals may also lose immunity at a rate of ξ. Formally, in the absence of control, the population evolves over time according to the following system of differential equations:EQUATIONTypically, β ą θ ą ξ. We normalize the total population to be 1, and thus x " rS, I, Rs P ∆ 3 . Next, we introduce a variable called the preventative control u t P ∆ 2 , which has the effect of decreasing the transmission rate β, and adversarial perturbations w t , which allow for model misspecification.Incorporating these changes to the forward discretization of Eq. ( 10) gives the following dynamics:EQUATIONThe control u t P ∆ 2 represents a distribution over transmission prevention protocols: u t " r1, 0s represents full-scale prevention, whereas u t " r0, 1s represents that no prevention measure is imposed.Concretely, the effective transmission rate under control u t is β ¨ut p2q.Parameters and cost function. To model a highly infectious pandemic, we consider Eq. ( 11) with parameters β " 0.5, θ " 0.03, and ξ " 0.005. Suppose we want to control the number of infected individuals by modulating a (potentially expensive) prevention protocol u t . To model this setting, the cost function includes (1) a quadratic cost for infected individuals I t , and (2) a cost that is bilinear in the magnitude of prevention and the susceptible individuals:EQUATIONwhere x t " rS t , I t , R t s. Typically c 3 ě c 2 ą 0 to model the high cost of infection.In Fig. 1 , we compare GPC-Simplex against two baselines -(a) always executing u t " r1, 0s (i.e. full prevention), and (b) always executing u t " r0, 1s (i.e. no prevention) -for T " 200 steps in the above model with no perturbations. We observe that GPC-Simplex suppresses the transmission rate via high prevention at the initial stage of the disease outbreak, then relaxes as the outbreak is effectively controlled. Moreover, GPC-Simplex outperforms both baselines in terms of cumulative cost. See Appendix F for additional experiments exhibiting the robustness of GPC-Simplex to perturbations (i.e. non-zero γ t 's) and different model parameters.4.1 Controlling hospital flows: reproducing a study by [27] We now turn to the recent work [27] , which also studies a controlled SIR model. Similar to above, they considered a control that temporarily reduces the rate of contact within a population. In one scenario (inspired by the COVID-19 pandemic), they considered a cost function that penalizes medical surges, i.e. when the number of infected exceeds a threshold y max determined by hospital capacities. Formally, they define the cost of a trajectory px t , u t q T t"1 asEQUATION)where W 0 is the principal branch of Lambert's W -function, and c 2 , c 3 are hyperparameters. The system parameters used by [27] are β " 0.3, θ " 0.1, ξ " 0. In the absence of noise and with a known cost function, [27] is able to compute the approximate solutions of the associated Hamilton-Jacobi-Bellman equations for various choices of c 2 , c 3 .In Fig. 2 , we show that GPC-Simplex (with a slightly modified instantaneous version of Eq. ( 13)) in fact matches the optimal solution analytically computed by [28] . See Appendix G for further experimental details, including the exact model parameters and cost function. show the number of infected and susceptible under GPC-Simplex, which closely match the optimal solutions computed by [28] (dashed yellow and blue). Right: GPC-Simplex control (solid) vs. optimal control (dashed). For completeness, we recall the definition of a standard LDS [21] .Definition 9 (LDS). Let d x , d u P N. A linear dynamical system (LDS) is described by a tuple L " pA, B, x 1 , pw t q tPN , pc t q tPN q where A P R dxˆdx , B P R dxˆdu are the transition matrices;x 1 P R dx is the initial state; w t P R dx is the noise value at time t; and c t : R dx ˆRdu Ñ R is the cost function at time t. For each t ě 1, given state x t P R dx and control u t P R du at time t, the state at time t `1 is given byx t`1 :" Ax t `Bu t `wt ,and the instantaneous cost incurred at time t is given by c t px t , u t q.B Discussion on the observation modelOur main algorithm GPC-Simplex for online control of simplex LDSs assumes that for each t, the perturbation strength γ t is observed by the controller at the same time as it observes x t`1 (the algorithm does not require the entire sequence pγ t q t to be known in advance). In this appendix we discuss (a) why this is a crucial technical assumption for the algorithm, and (b) why it is a reasonable assumption in many natural population models.First we explain why is it technically important for GPC-Simplex that the controller observes γ t .Recall that like the algorithm GPC from [1] , GPC-Simplex is a disturbance-action controller, meaning that the control at time t is computed based on previous disturbances w t´i . In the standard LDS model (Definition 9) studied by [1] , it's clear that w t´1 can be computed from x t´1 , u t´1 , x t , using the fact that A, B are known. However, in the simplex LDS model, if γ t´1 is not directly observed, then in fact w t´1 may not be uniquely identifiable given x t´1 , u t´1 , x t . This is why GPC-Simplex requires observing the parameters γ t . It is an interesting open problem whether this assumption can be removed.Second, we argue that in many practical applications, it is reasonable for γ t´1 to be observed along with the population state x t . The reason is that often the controller can observe not just the proportions of individuals of different categories in a population but also the total population size.Formally, consider a population which has N t individuals at time t. Thus, if the distribution of the population across d categories is described by x t P ∆ d , then for each i P rds there are N t px t q i individuals in category i. Suppose that under control u t P I, this population evolves to a new distribution p1 ´}u t } 1 qAx t `Bu t , but then the adversary adds n t new individuals to the population, whose distribution over categories is given by w t P ∆ d . Then if we write xt P R d ě0 to denote the vector of counts of individuals in each category at time t, it holds that xt`1 " N t pp1 ´}u t } 1 qAx t `Bu t q `nt w t " N t`1 pp1 ´γt qpp1 ´}u t } 1 qAx t `Bu t q `γt w t q where N t`1 " N t `nt is the total number of individuals at time t`1, and we write γ t :" n t {pN t `nt q. Thus, the distribution of the population across the d categories at time t `1 isx t`1 " xt`1 N t`1 " p1 ´γt qpp1 ´}u t } 1 qAx t `Bu t q `γt w twhich is exactly the update rule from Definition 3. Moreover, if the controller observes the total population counts N t , N t`1 in addition to x t , u t , x t`1 , then it may compute γ t " pN t`1 ´Nt q{N t`1 as well as w t (using knowledge of A, B), which is what we wanted to show.In this section, we prove Theorem 7. We begin with an overview of this section that outlines the structure and the main idea behind the proof of Theorem 7.Overview. GPC-Simplex (Algorithm 1) essentially runs mirror descent on the loss functions t pp, M r1:Hs q constructed in Line 9. In particular, the loss at time t measures the counterfactual cost of following the policy π p,M r1:Hs for the first t timesteps. Thus, the regret of GPC-Simplex against the comparator class K τ pLq (Definition 6) can be bounded by the following decomposition: Approximation error of comparator class `Mismatch error of costs `LazyMD regret In more detail:• Approximation error of comparator class. Since GPC-Simplex is only optimizing over policies of the form π p,M r1:Hs for pp, M r1:Hs q P X d,H,a0,α , we must show that every policy in the comparator class can be approximated by some policy π p,M r1:Hs . This is accomplished by Lemma 17.• Mismatch error of costs. The cost incurred by the mirror descent algorithm LazyMD at time t is t pp t , M r1:Hs t q, which is the counterfactual cost at time t had the current policy π pt,M r1:Hs t been carried out from the beginning of the time. However, the cost actually incurred by the controller at time t is c t px t , u t q, which is the cost incurred by following policy π ps,M r1:Hs s at time t, for each s ď t. Thus, there is a mismatch between the loss that GPC-Simplex is optimizing and the loss that GPC-Simplex needs to optimize. This mismatch can be bounded using the stability of mirror descent along with a mixing argument; see Lemma 21.• LazyMD regret. GPC-Simplex uses LazyMD as its subroutine for mirror descent. The regret of LazyMD can be bounded by standard guarantees; see Corollary 15.We begin with some preliminaries regarding mirror descent. Let X Ă R d be a convex compact set, and let R : X Ñ R be a convex function. We consider the Lazy Mirror Descent algorithm LazyMD (also known as Following the Regularized Leader) for online convex optimization on X . Given an offline optimization oracle over X , the function R, and a parameter η ą 0, LazyMD chooses each iterate z t based on the historical loss functions s : X Ñ R (for s P rt ´1s) as described in Algorithm 2.Algorithm 2 LazyMD: Lazy Mirror Descent [35] Require: Offline convex optimization oracle over set X Ă R d ; convex regularization function R : X Ñ R; step size η ą 0; loss functions 1 , . . . , T where t is revealed after iteration t. 1: for t ě 1 doCompute and output the solution to the following convex optimization problem:EQUATIONReceive loss function t : X Ñ R.The following lemma bounds the regret of LazyMD against the single best z P X (in hindsight), for an appropriately chosen step size η. Lemma 10 (Mirror descent). Suppose that X Ă R d is convex and compact, and let }¨} be a norm on R d . Let R : X Ñ R be a 1-strongly convex function with respect to }¨}. Let L ą 0, and let ρ :" max zPX Rpzq ´min zPX Rpzq.Fix an arbitrary sequence of loss functions t : X Ñ R which are each convex and L-Lipschitz with respect to } ¨}. Then the iterates z t of LazyMD (Eq. ( 14)) with an optimization oracle over X , regularizer R, step size η " ? ρ{pL ? 2T q, and loss functions 1 , . . . , T satisfy:EQUATIONMoreover, for each t P rT ´1s, it holds thatEQUATION)Lemma 10 is essentially standard but we provide a proof for completeness.Proof ? ρ L ?2T yields Eq. ( 15). To establish the movement bound Eq. ( 16), we argue as follows. Consider any y 1 , y 2 P R d and define, for i P t1, 2u,w i :" arg min zPX xy i , zy `Rpzq.The definition of w 2 implies thatRpw 1 q ´xy 2 , w 2 y `xy 2 , w 1 y ě Rpw 2 q ě Rpw 1 q `x∇Rpw 1 q, w 2 ´w1 y `1 2 }w 2 ´w1 } 2where the second inequality is by 1-strong convexity of R. Simplifying, we get1 2 }w 1 ´w2 } 2 ď xy 2 , w 1 ´w2 y `x∇Rpw 1 q, w 2 ´w1 y.Symmetrically, the definition of w 1 together with strong convexity implies that1 2 }w 1 ´w2 } 2 ď xy 1 , w 2 ´w1 y `x∇Rpw 2 q, w 1 ´w2 y.Adding the two above displays gives}w 1 ´w2 } 2 ď xy 2 ´y1 , w 1 ´w2 y `x∇Rpw 1 q ´∇Rpw 2 q, w 2 ´w1 y ď }y 2 ´y1 } ‹ ¨}w 1 ´w2 },where the second inequality uses convexity of R (which gives x∇Rpw 1 q ´∇Rpw 2 q, w 1 ´w2 y ě 0). It follows that }w 1 ´w2 } ď }y 1 ´y2 } ‹ . Setting y 1 :" η ř t´1 s"1 ∇ s pz s q and y 2 :" η ř t s"1 ∇ s pz s q, and recalling the definitions of z t , z t`1 from Eq. ( 14), we get}z t ´zt`1 } ď }η∇ t pz t q} ‹ ď ηL ď a 2ρ{T ,as desired.We next apply Lemma 10 to the domain used in GPC-Simplex. Recall that, given d, H P N and real numbers 0 ď a ď b ď 1, we have defined X d,H,a,b :" Ť a 1 Pra,bs ∆ d a 1 ˆpS d a 1 q H . Definition 11 (Entropy of a sub-distribution). Let d P N. We define the function Ent :∆ d ď1 Ñ R ě0 by Entpvq :" v c ln 1 v c `d ÿ j"1 v j ln 1 v jwhere for any vector v P R d we write v c :" 1 ´řd j"1 v j P R. That is, v Þ Ñ ´Entpvq is 1-strongly convex on ∆ d ď1 with respect to }¨} 1 .Proof. Let p be the probability mass function on rd `1s with p i " u i for all i P rds, and let q be the probability mass function on rd `1s with p i " v i for all i P rds. Then it can be checked thatx∇ u Entpuq ´∇v Entpvq, v ´uy " KLpp||qq `KLpq||pq ě TVpp, qq 2 ě }u ´v} 2 1where the first inequality is by Pinsker's inequality. R d,H pp, M r1:Hs q :" ´Entppq ´H ÿEQUATIONDefinition 14 (Norm for analysis of mirror descent in GPC-Simplex). Let d, H P N, and identify , for all t P rT ´1s, we haveR d`Hd 2 with R d ˆpR dˆd q H . We define a norm }¨} d,H on R d`Hd 2 as follows: for p P R d , M r1:Hs P pR dˆd q H , › › ›pp, M r1:Hs q › › › 2 d,H :" }p} 2 1 `H ÿ h"1 d ÿ j"1 › › ›M rhs ¨,j › › ›EQUATION)Proof. Note that the set of pp, M r1:Hs q where p P R d and M r1:Hs P pR dˆd q H can be identified with R d`Hd 2 . We apply Lemma 10 with X :" 18) and (19) , where to prove Eq. (19) we are using the fact that }C} 1Ñ1 " max jPrds }C ¨,j } 1 ď b ř jPrds }C ¨,j } 2 1 for all C P R dˆd .X d,H,a,b , R " R d,Henceforth fix a simplex LDS L " pA, B, I, x 1 , pγ t q t , pw t q t , pc t q t q on ∆ d , where I " Ť αPrα,αs ∆ d α for some constants 0 ď α ď α ď 1.Recall that any choice of parameters pp, M r1:Hs q P X d,H,a,b (for some hyperparameters H P N and α ď a ď b ď α) induces, via Eq. ( 8), a set of policies pπ p,M r1:Hs s q sPrT s . The policy π p,M r1:Hs s takes as input the disturbances w s´1 , . . . , w s´H observed at the H time steps before step s, and outputs a control for step s. Recall that, in Algorithm 1, we used x t pp, M r1:Hs q, u t pp, M r1:Hs q to denote the state and control at time step t one would observe by playing the control π p,M r1:Hs s pw s´1:s´H q at step s, for each 1 ď s ď t.Formally, we have the following expressions for x t pp, M r1:Hs q, u t pp, M r1:Hs q: Fact 16. For any pp, M r1:Hs q P X d,H,a,b and t P rT s, it holds that x t pp, M r1:Hs q "EQUATIONu t pp, M r1:Hs q " π p,M r1:Hs t pw t´1:t´H q " λ t,0 ¨p `H ÿ j"1EQUATIONwhere we have written, for t P rT s, i P N, α p,M r1:Hs t,i:"ś i´1 j"1 ´1 ´› › ›π p,M r1:Hs t´j › › › 1 ¯" p1 ´}p} 1 q i´1 .Proof. This follows unrolling Eq. ( 6) with the controls u s :" π p,M r1:Hs s pw s´1:s´H q, and recalling the definitions in Eq. ( 7) and the conventions w 0 :" x 1 , γ 0 " 1, and w t " 0 for t ă 0.In a sense, Algorithm 1 performs online convex optimization over the set of such policies. Even if we can manage to show that doing so yields a good regret guarantee with respect to the class of policies tπ p,M r1:Hs t : pp, M r1:Hs q P X d,H,a,b u for some choices of H, a, b, why should this imply a good regret guarantee with respect to the class K τ pLq of linear policies (see Definition 6)? Lemma 17 bridges this gap, showing that any policy in K τ pLq can be approximated by a policy of the form pπ p,M r1:Hs s q sPrT s . Lemma 17 (Approximation). Suppose that the cost functions c 1 , . . . , c T of L satisfy Assumption 1 with Lipschitz parameter L. Fix τ ą 0, ε P p0, 1q, and any K ‹ P S d ď1 such that t mix pA K ‹ q ď τ . Write α ‹ :" }K ‹ } 1Ñ1 . If H ě τ rlog 2 p2LT 2 {εqs, then there is some pp, M r1:EQUATIONwhere x t pK ‹ q, u t pK ‹ q denote the state and control that one would observe at time step t if one were to play according to the policy x Þ Ñ K ‹ x at all time steps 1 ď s ď t.Proof. For each t, if the controls u t are chosen to satisfy u t :" K ‹ ¨xt , then we have α t :" }K ‹ } 1Ñ1 . Moreover, for 1 ď t ď T , we can writex t pK ‹ q " t ÿ i"1 pA K ‹ q i´1 ¨˜i´1 ź j"1p1 ´γt´j q ¸¨γ t´i w t´i "EQUATIONEQUATIONwhere A K ‹ was defined in Eq. (5) . By the assumption that t mix pA K ‹ q ď τ , there is some unique p 1 P ∆ d such that that A K ‹ ¨p1 " p 1 (see Definition 5) . Moreover, by our bound on H and Lemma 18, for any i ą H and q P ∆ d we have › › A i´1 K ‹ q ´p1 › › 1 ď p1{2q H{τ ď ε{p2LT 2 q. Using that λ t,0 " ř t i"H`1 λ t,i by the definition in Eq. ( 7),EQUATION)For 1 ď i ď H, let us define M ris :" K ‹ A i´1 K ‹ P S d α ‹ and p :" K ‹ ¨p1 P ∆ d α ‹ . Using Eqs. ( 21) and ( 24), we have thatEQUATION)where the final inequality uses Eq. ( 25).Next, we may bound the difference in state vectors using Eq. ( 26), as follows: for any sequence of pu i q t i"1 with }u i } 1 " α ‹ for all i, we can expand Eq. ( 6) to getx t " t ÿ i"1p1 ´α‹ q i´1 A i´1 p λt,i Bu t´i `λt,i w t´i q.Thus, for any t P rT s, we haveEQUATION)By Eqs. ( 26) and (27) and Assumption 1, it follows that, for each t P rT s, ˇˇctpxtpp, M r1:Hs q, u t pp, M r1:Hs qq ´ct px t pK ‹ q, u t pK ‹ qq ˇˇď ε{T, which yields the claimed bound Eq. ( 22).The following facts about distance to stationarity are well-known (see e.g. [31, Section 4.4]): Lemma 18. Let X P S d have a unique stationary distribution π. Then the following inequalities hold for any c, t P N:1. D X ptq ď DX ptq ď 2D X ptq.2. DX pctq ď DX ptq c .In this section, we prove Lemma 21, which allows us to show that an algorithm with bounded aggregate loss with respect to the loss functions t defined on Line 9 of Algorithm 1 in fact has bounded aggregate cost with respect to the cost functions c t chosen by the adversary.First, we introduce two useful lemmas on the mixing time of matrices (Definition 5 › › 1 ď 2tδ `sup p,qP∆ d › › X t pp ´qq › › 1 ď 2tδ `D X ptq ď 2tδ `2D X ptq,where the first and last inequalities apply the first item of Lemma 18.Lemma 20. Suppose that A, B P S d , K ‹ P S d ď1 satisfy t mix pAq ą 4 ¨tmix pA K ‹ q. Then }K ‹ } 1Ñ1 ą 1{p96 ¨tmix pA K ‹ qq.Proof. Let us write τ :" t mix pA K ‹ q and α ‹ :" }K ‹ } 1Ñ1 , so that A K ‹ " p1 ´α‹ q ¨A `BK ‹ . Suppose for the purpose of contradiction that α ‹ ď 1{p96τ q. We have that }A ´AK ‹ } 1Ñ1 ď 2α ‹ . By Lemma 18 and Definition 5, we have DA K ‹ pτ q ď 2D A K ‹ pτ q ď 1{2, so D A K ‹ p4τ q ď DA K ‹ p4τ q ď 1{16. Using Lemma 19 and the assumption on α ‹ ,D A p4τ q ď 12τ α ‹ `2D A K ‹ p4τ q ď 12τ α ‹ `1{8 ď 1{4, meaning that t mix pAq ď 4τ .The last step is to bound the memory mismatch error. Lemma 21 (Memory mismatch error). Suppose that pc t q t satisfy Assumption 1 with Lipschitz parameter L. Let τ, β ą 0, and suppose that K τ pLq is nonempty. Consider the execution of GPC-Simplex (Algorithm 1) on L with input τ . If the iterates pp t , M r1:Hs t q tPrT s satisfyEQUATIONthen for each t P rT s, the loss function t computed at time step t satisfies| t pp t , M r1:Hs t q ´ct px t , u t q| ď O `Lτ 3 β log 3 p1{βq ˘.Proof. Recall that u t P ∆ d denotes the control chosen in step t of Algorithm 1. We write α t :" }u t } 1 and, for i P rts, α t,i :" ś i´1 j"1 p1 ´αt´j q. Note that α t " }p t } 1 "› › ›M rhs t › › › 1Ñ1for each h P rHs, by definition of X d,H,a0,α .Let us fix t P rT s, and write p :" p t , M r1:Hs :" M r1:Hs t . By Eq. ( 6), the state x t at step t of Algorithm 1 can be written as follows:EQUATIONBy assumption that K τ pLq is nonempty, there is some K ‹ P S d rα,αs satisfying t mix pA K ‹ q ď τ . Let us write α ‹ :" }K ‹ } 1Ñ1 , so that A K ‹ " p1 ´α‹ qA `BK ‹ . Moreover, recall we have written in Algorithm 1 that τ A :" t mix pAq.For 1 ď i ď t, definev i :" λ t´i,0 λt,i Bp t´i `B H ÿ j"1 M rjs t´i λ t,i`j w t´i´j `λt,i w t´i , v 1 i :" λ t´i,0 λt,i Bp `B H ÿ j"1M rjs λ t,i`j w t´i´j `λt,i w t´i .Note thatEQUATIONNext, using Eq. ( 29) and Eq. ( 20), we havex t ´xt pp, M r1:Hs q "EQUATIONThe condition Eq. ( 28 | ď i 2 β for all i ě 1 and that for any ě 1,EQUATION)Using Eq. ( 32) and the fact thatEQUATION)We consider the following two cases:Case 1: τ A ď 4τ . Write t 0 " tτ A log 2 p1{βqu. Let the stationary distribution of A be denoted p ‹ P ∆ d . By Lemma 18, we have that for all i ě 1, › › A i ¨p ´p‹ › › 1 ď D A piq ď 1{2 ti{τ A u . Now, using Eq. ( 31), we may compute › › ›xt ´xt pp, M r1:Hs q› › › 1 ď › › › › › t0 ÿ i"1 ´αt,i ¨Ai´1 ¨vi ´αp,M r1:Hs t,i ¨Ai´1 ¨v1 i ¯› › › › › 1 `› › › › › t ÿ i"t0`1 α t,i ¨`A i´1 ¨vi ´}v i } 1 ¨p‹ ˘´α p,M r1:Hs t,i ¨`A i´1 ¨v1 i ´› › v 1 i › › 1 ¨p‹ ˘› › › › › 1 `› › › › › t ÿ i"t0`1 α t,i ¨}v i } 1 ¨p‹ ´αp,M r1:Hs t,i ¨› › v 1 i › › 1 ¨p‹ › › › › › 1 ď t0 ÿ i"1 ´αt,i ¨› › A i´1 ¨pv i ´v1 i q › › 1 `|α t,i ´αp,M r1:Hs t,i | ¨› › v 1 i › › 1 t ÿ i"t0`1 ´αt,i ¨› › A i´1 ¨vi ´}v i } 1 ¨p‹ › › 1 `αp,M r1:Hs t,i ¨› › A i´1 ¨v1 i ´› › v 1 i › › 1 ¨p‹ › › 1 ¯`t 3 0 β ď t 3 0 β `t0 ÿ i"1 i 2 β `t0 ÿ i"1 α t,i ¨iβ `t ÿ i"1`t0 2 ¨1{2 ti{τ A u ď Ct 3 0 β (34) ď C 1 τ 3 log 3 p1{βq ¨β,for some universal constants C, C 1 . Above, the first inequality uses the triangle inequality, the second inequality uses Eq. ( 33), and the third inequality uses that }v i ´v1 i } 1 ď iβ, |α t,i ´αp,M r1:Hst,i | ď i 2 β, }v 1 i } 1 ď 1.The fourth inequality uses the boundř t i"1`t0 2 ´ti{τ A u ď Opτ A βq ď Opt 0 βq.Case 2: τ A ą 4τ . In this case, we claim that a 0 ě 1{p96τ q. By choice of a 0 in Line 1 of Algorithm 1 and the fact that τ A ą 4τ , it suffices to show that α ě 1{p96τ q: to see this, note that τ A " t mix pAq ą 4τ ě 4 ¨tmix pA K ‹ q, so Lemma 20 gives that }K ‹ } 1Ñ1 ą 1{p96 ¨tmix pA K ‹ qq ě 1{p96τ q. But }K ‹ } 1Ñ1 ď α, and thus α ą 1{p96τ q. This proves that a 0 ě 1{p96τ q. Hence α i ě a 0 ě 1{p96τ q, by definition of X d,H,a0,α , for all i P rT s.Write t 0 :" t200τ ¨logp1{βqu. Then for any i ą t 0 , maxtα t,i , α p,M r1:Hs t,i u ď p1 ´a0 q i´1 ď p1 ´1{p96τ qq t200τ ¨logp1{βqu ď Opβq.Again using Eq. ( 31),› › ›xt ´xt pp, M r1:Hs q › › › 1 ď t0 ÿ i"1 ´|α t,i ´αp,M r1:Hs t,i | `αt,i ¨› › v i ´v1 i › › 1 ¯`t ÿ i"t0`1 pα t,i `αp,M r1:Hs t,i q ď t0 ÿ i"1 `i2 β `iβ ˘`t ÿ i"t0`1Opβq ¨p1 ´a0 q i´t0´1 (35)ď Ct 3 0 β `Cβ{a 0 ď C 1 τ 3 log 3 p1{βq ¨β,for some constants C, C 1 . Above, the first inequality uses Eq. ( 30); the second inequality uses the previously derived bounds |α t,i ´αp,M r1:Hst,i| ď i 2 β and }v i ´v1 i } 1 ď iβ; and the final inequality uses that a 0 ě 1{p96τ q.In both cases, we have › › x t ´xt pp, M r1:Hs q › › 1 ď C 1 τ 3 β log 3 p1{βq for some universal constant C 1 . By definition, the control u t chosen by Algorithm 1 at time step t is exactly u t " u t pp, M r1:Hs q. Thus, using L-Lipschitzness of c t , we have ˇˇ t pp, M r1:Hs q ´ct px t , u t q ˇˇ" ˇˇctpxtpp, M r1:Hs q, u t pp, M r1:Hs qq ´ct px t , u t q ˇďL ¨› › ›xt ´xt pp, M r1:Hs q › › › 1 ď C 1 Lτ 3 β log 3 p1{βq.as desired.Before proving Theorem 7, we establish that the loss functions t used in GPC-Simplex are Lipschitz. Lemma 22. Let X P S d with τ :" t mix pXq ă 8. Then for any i P N and v P R d with x1, vy " 0, it holds that› › X i v › › 1 ď 2 ´ti{τ u }v} 1 .Proof. Fix v P R d with x1, vy " 0. We can write v " v `´v ´, where v `, v ´P R d ě0 are the non-negative and negative components of v respectively. We have }v `}1 " }v ´}1 " 1 2 }v} 1 since x1, vy " 0. Let u 1 :" 2v `{}v} 1 and u 2 :" 2v ´{}v} 1 , so that u 1 , u 2 P ∆ d . By Lemma 18 and the definition of t mix pXq, we have}X i pu 1 ´u2 q} 1 ď DX piq ď DX pτ q ti{τ u ď p2D X pτ qq ti{τ u ď 2 ´ti{τ u . Thus, }X τ v} 1 ď 2 ´ti{τ u }v} 1 .Lemma 23 (Lipschitzness of t ). Let τ ą 0, and suppose that K τ pLq is nonempty. For each t P rT s, the loss function t pp, M r1:Hs q " c t px t pp, M r1:Hs q, u t pp, M r1:Hs qq (as defined on Line 9 of Algorithm 1) is OpLτ 2 q-Lipschitz with respect to the norm }¨} d,H in X d,H,a0,α .Proof. By L-Lipschitzness of c t with respect to }¨} 1 , it suffices to show that for any pp 1 , M r1:Hs 1 q, pp 2 , M r1:Hs 2 q P X d,H,a0,α , we haveEQUATIONEQUATION)Fix pp 1 , M r1:Hs 1 q, pp 2 , M r1:Hs 2 q P X d,H,a0,α , and write ε :" max" }p 1 ´p2 } 1 , max jPrHs › › ›M rjs 1 ´M rjs 2 › › › 1Ñ1 * . Since ε ď › › ›pp1, M r1:Hs 1 q ´pp 2 , M r1:Hs 2 q › › › d,H, it suffices to show that Eqs. ( 36) and ( 37) hold with ε on the right-hand sides.To verify Eq. ( 36) in this manner, we define, for b P t1, 2u,v i,b :"λ t´i,0 λt,i ¨B ¨pb `B H ÿ j"1 λ t,i`j ¨M rjs b ¨wt´i´j `λt,i ¨wt´i .Since λ t´i,0 λt,i `λt,i `řH j"1 λ t,i`j ď 1, we have }v i,b } 1 ď 1 for each i P rts, b P t1, 2u. Moreover, }v i,1 ´vi,2 } 1 ď pλ t´i,0 λt,i `řH j"1 λ t,i`j q ¨ε ď ε. Write σ 1 :" }p 1 } 1 , σ 2 :" }p 2 } 1 , so that |σ 1 ´σ2 | ď ε and |p1 ´σ1 q i ´p1 ´σ2 q i | ď iε for all i ě 1. Also note that for each b P t1, 2u,t ÿ i"1 p1 ´σb q i´1 ¨}v i,b } 1 " t ÿ i"1p1 ´σb q i´1 ¨λ t,i´1 ¨pp1 ´γt´i q ¨σb `γt´i q " t ÿ i"1 p1 ´σb q i´1 ¨λ t,i´1 ¨p1 ´p1 ´γt´i qp1 ´σb qq " 1,where the final equality follows since γ 0 " 1.By Eq. ( 20), we havex t pp 1 , M r1:Hs 1 q ´xt pp 2 , M r1:Hs 2 q " t ÿ i"1 `p1 ´σ1 q i´1 A i´1 ¨vi,1 ´p1 ´σ2 q i´1 A i´1 ¨vi,2 ˘.We consider two cases, depending on the mixing time τ A :" t mix pAq of A:Case 1: τ A ď 4τ . Let the stationary distribution of A be denoted p ‹ P ∆ d . Then› › ›xtpp1, M r1:Hs 1 q ´xt pp 2 , M r1:Hs 2 q › › › 1 " › › › › › t ÿ i"1 `p1 ´σ1 q i´1 A i´1 v i,1 ´p1 ´σ2 q i´1 A i´1 v i,2 ˘› › › › › 1 ď › › › › › t ÿ i"1 `p1 ´σ1 q i´1 pA i´1 v i,1 ´}v i,1 } 1 p ‹ q ´p1 ´σ2 q i´1 pA i´1 v i,2 ´}v i,2 } 1 p ‹ q ˘› › › › › 1 `› › › › › t ÿ i"1 `p1 ´σ1 q i´1 }v i,1 } 1 ´p1 ´σ2 q i´1 }v i,2 } 1 ˘p‹ › › › › › 1 " › › › › › t ÿ i"1 A i´1 `p1 ´σ1 q i´1 v i,1 ´p1 ´σ2 q i´1 v i,2 ˘´`p 1 ´σ1 q i´1 }v i,1 } 1 ´p1 ´σ2 q i´1 }v i,2 } 1 ˘p‹ › › › › › 1 ď t ÿ i"1 2 1´tpi´1q{τ A u › › p1 ´σ1 q i´1 v i,1 ´p1 ´σ2 q i´1 v i,2 ´`p1 ´σ1 q i´1 }v i,1 } 1 ´p1 ´σ2 q i´1 }v i,2 } 1 ˘p‹ › › 1 ď t ÿ i"1 2 2´tpi´1q{τ A u piε `εq ď Cτ A ε 8 ÿ i"0 τ A i2 ´i ď C 1 τ 2 εfor some constants C, C 1 . Above, the second equality uses Eq. ( 38), and the second inequality uses Lemma 22 together with the fact that A i´1 p ‹ " p ‹ and @ 1, `p1 ´σ1 q i´1 v i,1 ´p1 ´σ2 q i´1 v i,2˘´`p 1 ´σ1 q i´1 }v i,1 } 1 ´p1 ´σ2 q i´1 }v i,2 } 1 ˘D " 0.The final inequality uses the assumption that τ A ď 4τ .Case 2: τ A ą 4τ . In this case, the assumption that K τ pLq is nonempty together with the choice of a 0 in Line 1 of Algorithm 1 and Lemma 20 gives that a 0 ą 1{p96τ q. See Case 2 of the proof of Lemma 21 for more details of this argument, which uses the fact that τ A ą 96τ .Since pp b , M r1:Hs b q P X d,H,a0,α for b P t1, 2u, we have σ 1 , σ 2 ě a 0 ą 1{p96τ q. We may compute › › ›xtpp1, M r1:Hs1 q ´xt pp 2 , M r1:Hs 2 q › › › 1 " › › › › › t ÿ i"1 `p1 ´σ1 q i´1 A i´1 v i,1 ´p1 ´σ2 q i´1 A i´1 v i,2 ˘› › › › › 1 ď t ÿ i"1 |p1 ´σ1 q i´1 ´p1 ´σ2 q i´1 | `t ÿ i"1 p1 ´σ1 q i´1 }v i,1 ´vi,2 } 1 ď t ÿ i"2 i´1 ÿ j"1 |σ 1 ´σ2 |p1 ´σ1 q j´1 p1 ´σ2 q i´1´j `ε t ÿ i"1 p1 ´σ1 q i´1 ď t ÿ i"2 pi ´1qεp1 ´1{p96τ qq i´2 `ε t ÿ i"1 p1 ´1{p96τ qq i´1 ď Cτ 2 ε for some constant C.Thus, in both cases above, we have› › ›xtpp1, M r1:Hs 1 q ´xt pp 2 , M r1:Hs 2 q › › › 1 ďOpτ εq, which verifies Eq. (36) .The proof of Eq. ( 37) is much simpler: we have› › ›utpp1, M r1:Hs 1 q ´ut pp 2 , M r1:Hs 2 q › › › 1 ď λ t,0 ¨}p 1 ´p2 } 1 `H ÿ j"1 λ t,j ¨› › ›M rjs 1 ´M rjs 2 › › › 1Ñ1 ď ε, since λ t,0 `¨¨¨`λ t,H " 1.Proof of Theorem 7. Set β " ? 2dH ln d ? T, ε " 1{T , and K τ :" K τ pLq. We will apply Corollary 15to the sequence of iterates pp t , M r1:Hs t q produced in Algorithm 1, for the domain X d,H,a0,α (i.e., a " a 0 , b " α). Note that Lemma 23 gives that t is OpLτ 2 q-Lipschitz, for each t P rT s. Thus Corollary 15 guarantees a regret bound (with respect to X d,H,a0,α ) of OpLτ 2 a dH lnpdqT q. Moreover, Eq. ( 19) of Corollary 15 ensures that the precondition Eq. ( 28) of Lemma 21 is satisfied. Thus, we may bound where the first inequality uses Lemma 21 together with Eq. ( 19) of Corollary 15, and the second inequality uses Lemma 17 with " 1{T (by the theorem assumption, the inequality H ě τ rlog 2 p2LT 2 { qs is indeed satisfied). Note that for the second inequality to hold, we also need that }K} 1Ñ1 ě a 0 for all K P K τ , which in particular requires (by Line 1) that }K} 1Ñ1 ě 1{p96τ q if t mix pAq ą 4τ . But if t mix pAq ą 4τ , then for any K P K τ we have t mix pAq ą 4 ¨tmix pA K q and hence }K} 1Ñ1 ě 1{p96τ q by Lemma 20. Finally, the equality above uses the definition of t in Algorithm 1, and the final inequality uses the regret bound of Corollary 15. By our choice of β, ε, we see that the overall policy regret is ÕpLτ 7{2 d 1{2 ?T ÿ t"1 c t px t , u t q ´inf KPK τ T ÿ t"1 c t px t pKq, u t pKqq ď T ÿ t"1 t pp t , M r1:Hs t q ´inf KPK τ T ÿ t"T q, as desired.In this section, we formally state and prove the regret lower bounds Theorem 1 and Theorem 8. The former states that the comparator class for online control of standard LDSs cannot be broadened to all marginally stable (time-invariant, linear) policies; the latter states that the mixing time assumption cannot be removed from the comparator class for online control of simplex LDSs. Both results hold even in constant dimension.The basic idea is the same for both proofs: we construct two systems L 0 , L 1 which are identical until time T {2, but then at time T {2 experience differing perturbations of constant magnitude. The costs are zero until time T {2, after which they penalize distance to a prescribed state (and can in fact be taken to be the same for both systems). The optimal strategy in the first T {2 time steps therefore depends on which system the controller is in, but the controller does not observe this until time T {2, and hence will necessarily incur regret with respect to the optimal policy.Formalizing this intuition requires two additional pieces: first, for both systems there must be a near-optimal time-invariant linear policy. This can be achieved by careful design of the dynamics, perturbations, and costs. Second, if the controller finds itself in a high-cost state at time T {2 `1, it must be unable to reach a low-cost state without incurring ΩpT q total cost along the way. In the standard LDS setting, we achieve this by setting the transition matrices A, B so that }B} " Op1{T q (i.e. so constant-size controls have small effect on the state) and adding a penalty of |u t | to the cost for t ą T {2. In the simplex LDS setting, we achieve this by our choice of the valid constraint set I (which enforces that }u t } 1 " Op1{T q for all t).See Fig. 3 for a pictorial explanation of the proof in the simplex LDS setting.In this section we give a formal statement and proof of Theorem 1. Recall the definition of an LDS (Definition 9). We define the class K κ pLq of policies that κ-marginally stabilize L below; it is equivalent to the class K κ,ρ pLq of policies that pκ, ρq-strongly stabilize L (Definition 4) with ρ " 0.Definition 24 (Marginal stabilization). A matrix M P R dˆd is κ-marginally stable if there is a matrixH P R dˆd so that › › H ´1M H › › ď 1 and }M } , }H} , › › H ´1› › ď κ.A matrix K P R dˆd is said to κ-marginally stabilize an LDS with transition matrices A, B P R dˆd if A `BK is κ-marginally stable. For κ ą 0 and an LDS L on R d , we define K κ pLq to be the set of linear, time-invariant policies x Þ Ñ Kx where K P R dˆd κ-marginally stabilizes L.We also introduce a standard regularity assumption on cost functions: 15Assumption 2. Let L ą 0. We say that cost functions pc t q t , where c t : R dx ˆRdu Ñ R, are L-regular if c t is convex and L-Lipschitz with respect to the Euclidean norm for all t. Theorem 25 (Formal statement of Theorem 1). Let Alg be any randomized algorithm for online control with the following guarantee:1/2 T/2 1 0 T 𝑆 1 𝑆 2 𝑆 3Figure 3 : An intuitive illustration of xtp2q in the lower bound for simplex LDS (Theorem 30). The blue curve is the trajectory of π 0 , the "decreasing" comparator policy, in the system L 0 , which has the smaller perturbation. The green curve is π 1 , the "lazy" comparator policy, in the system L 1 , which has the larger perturbation.The orange curves correspond to the trajectories of an arbitrary policy π under the two different perturbation sequences. The sum of regret under the two perturbation sequences is equal to the area S1 `S2 `S3, which is shown to be ΩpT q for any h.Let d, T P N and κ ą 0, and let L " pA, B, x 1 , pw t q t , pc t q t q be an LDS with state space and control space R d ; L-regular cost functions pc t q t (Assumption 2); and perturbations pw t q t satisfying }w t } 2 ď L for all t. Then the iterates px t , u t q T t"1 produced by Alg with input pA, B, κ, T q on interaction with L satisfyregret KκpLq :" E « T ÿ t"1 c t px t , u t q ff ´inf KPKκpLq T ÿ t"1 c t px L,K t , u L,K t q ď f pd, κ, L, T q (41)where px L,K t , u L,K t q T t"1 are the iterates produced by following policy x Þ Ñ Kx in system L for all t P rT s.Then f p1, 1, 1, T q " ΩpT q. Remark 26. In the above theorem statement, if K κ pLq were replaced with K κ,ρ pLq, the class of linear time-invariant policies that pκ, ρq-strongly stabilize L, then the main result of [1] would imply that in fact there is a (deterministic) algorithm GPC with regret at most polypd, κ, L, ρ ´1q ¨?T logpT q on any LDS L satisfying the above conditions. Thus, Theorem 25 indeed provides a converse to [1] .We prove Theorem 25 by constructing a simple distribution over LDSs on which any algorithm must incur ΩpT q regret in expectation. Let β ě 2 be a constant that we will determine later, and fix T ě β. Recall that we denote an LDS on R d using the notation L " pA, B, x 1 , pw t q t , pc t q t q, where A, B P R dˆd . We define two LDSs on R as follows:L 0 :" p1, ´β{T, x 1 , pw 0 t q t , pc t q t q, L 1 :" p1, ´β{T, x 1 , pw 1 t q t , pc t q t q, where the (common) initial state is x 1 " 1, the (common) cost functions pc t q t are defined as c t px, uq :"" |x| `|u| if t ą T {2 0 otherwise ,the perturbations of L 0 are w 0 t :" 0 for all t, and the perturbations of L 1 arew 1 t :" " ´1 if t " T {2 0 otherwise .For simplicity, we assume that T {2 is an integer. Thus, at all times t ‰ T {2, the two systems have identical dynamicsx t`1 :" x t ´β T u t ,but at time t " T {2, system L 1 experiences a negative perturbation of magnitude 1, whereas L 0 does not. The following lemma characterizes the performance of two time-invariant linear policies π 0 , π 1 for L 0 , L 1 respectively: Lemma 27. Define π 0 , π 1 : R Ñ R by π 0 pxq " x and π 1 pxq " 0. Then:• Policy π 0 is an element of K 1 pL 0 q, and the iterates px L 0 ,π 0 t , u L 0 ,π 0 t q T t"1 produced by following π 0 in system L 0 satisfyT ÿ t"1 c t px L 0 ,π 0 t , u L 0 ,π 0 t q ď 2T β e ´β{2 .• Policy π 1 is an element of K 1 pL 1 q, and the iterates pxL 1 ,π 1 t , u L 1 ,π 1 t q T t"1 produced by follow- ing π 1 in system L 1 satisfy T ÿ t"1 c t px L 1 ,π 1 t , u L 1 ,π 1 t q " 0.Proof. Note that π 0 , π 1 are both time-invariant linear policies. The inclusion π 0 P K 1 pL 0 q is immediate from the fact that L 0 has transitions A " 1, B " ´β{T , and |A `B| ď 1. Similarly, π 1 P K 1 pL 1 q because |A| ď 1. To bound the total cost of π 0 on L 0 , note that u L 0 ,π 0 t " x L 0 ,π 0 t " p1 ´β{T q t´1 for all t P rT s. Hence,T ÿ t"1 c t px L 0 ,π 0 t , u L 0 ,π 0 t q " 2 T ÿ t"T {2`1 ˆ1 ´β T ˙t´1 ď 2T β ˆ1 ´β T ˙T {2 ď 2T β e ´β{2 .Moreover, we have x L 1 ,π 1 t " 1rt ď T {2s and u L 1 ,π 1 t " 0 for all t P rT s, from which it is clear thatř T t"1 c t px L 1 ,π 1 t , u L 1 ,π 1 t q " 0.Next, we show that the total cost of any trajectory px t , u t q T t"1 can be lower bounded in terms of |x T {2`1 | in both L 0 and L 1 : Lemma 28. Let Alg be any randomized algorithm for online control, and let b P t0, 1u. The (random) trajectory px t , u t q T t"1 produced by Alg in system L b satisfies the inequalityT ÿ t"1 c t px t , u t q " T ÿ t"T {2`1 |x t | `|u t | ě T 2β |x T {2`1 |with probability 1.Proof. By definition of L 0 , L 1 , any valid trajectory in L b satisfies |u t | " T β |x t`1 ´xt | for all T {2 ă t ă T . We consider two cases:1. If min T {2ătďT |x t | ě 1 2 |x T {2`1 |, then T ÿ t"T {2`1 |x t | `|u t | ě T 4 |x T {2`1 | ě T 2β |x T {2`1 | since β ě 2. 2. If min T {2ătďT |x t | ă 1 2 |x T {2`1 |, then T ÿ t"T {2`1 |x t |`|u t | ě T β T ´1 ÿ t"T {2`1 |x t`1 ´xt | ě T β ˇˇˇ| x T {2`1 | ´min T {2ătďT |x t | ˇˇˇě T 2β |x T {2`1 |by the triangle inequality.In both cases the claimed inequality holds.We can now prove Theorem 25.Proof of Theorem 25. Let b " Unifpt0, 1uq be an unbiased random bit, and let px t , u t q T t"1 be the (random) trajectory produced by executing Alg on L b . On the one hand, by Eq. ( 41) applied to L 0 and L 1 , we haveEQUATIONwhere the first inequality uses the fact that the cost functions pc t q t are convex and 1-Lipschitz and that |w 0 t |, |w 1 t | ď 1 for all t P rT s; and the second inequality is by Lemma 27. On the other hand, by Lemma 28, we haveEQUATIONwhere the key equality p‹q uses the fact that L 0 , L 1 are identical up until and including time T {2, and hence px T {2 , u T {2 q is independent of b. Comparing Eq. (43) with Eq. (42) yields that f p1, 1, 1, T q ě T 4β ´T β e ´β{2 " ΩpT q for any sufficiently large constant β.Definition 29. Let 0 ď α ď α ď 1 and let I :" Ť αPrα,αs ∆ d α . We define KpIq to be the set of linear, time-invariant policies x Þ Ñ Kx where K P Ť αPrα,αs S d α . Theorem 30 (Formal statement of Theorem 8). Let Alg be any randomized algorithm for online control with the following guarantee:Let d, T P N and I :" Ť αPr0,αs ∆ d α for some α P p0, 1q.Let L " pA, B, I, x 1 , pγ t q t , pw t q t , pc t q t q be a simplex LDS with state space ∆ d and cost functions pc t q t satisfying Assumption 1 with Lipschitz parameter L ą 0. Then the iterates px t , u t q T t"1 produced by Alg with input pA, B, I, T q on interaction with L satisfyregret KpIq :" E « T ÿ t"1 c t px t , u t q ff ´inf KPKpIq T ÿ t"1 c t px L,K t , u L,K t q ď f pd, L, α, T q (44)where px L,K t , u L,K t q T t"1 are the iterates produced by following policy x Þ Ñ Kx in system L for all t P rT s.For any sufficiently large constant β, if we define αpT q :" β{T , then f p1, 1, αpT q, T q " ΩpT q.We define two simplex LDSs on ∆ 2 as follows:L 0 :" pI 2 , I 2 , I, x 1 , pγ t q t , pw 0 t q t , pc t q t q L 1 :" pI 2 , I 2 , I, x 1 , pγ t q t , pw 1 t q t , pc t q t q where I 2 P R 2ˆ2 is the identity matrix, the (common) valid control set is I :" Ť αPr0,β{T s ∆ d α , the (common) initial state is x 1 " p0, 1q, the (common) cost functions pc t q t are defined as c t px, uq :"" |xp2q ´1{2| if t ą T {2 0 otherwise ,the (common) perturbation strengths are γ t :" 1 2 1rt " T {2s, and the perturbations of L 0 are w 0 t :" p1{2, 1{2q for all t whereas the perturbations of L 1 are w 1 t :" p1, 0q for all t. Thus, for both systems, the dynamics are described by x t`1 :" p1 ´}u t } 1 qx t `ut for all t ‰ T {2.Lemma 31. Define π 0 , π 1 : ∆ 2 Ñ Ť αPr0,1s ∆ d by π 0 pxq :" β T p1{2, 1{2q and π 1 pxq :" p0, 0q. Then π 0 , π 1 P KpIq, and:• The iterates px L 0 ,π 0 t , u L 0 ,π 0 t q T t"1 produced by following π 0 in system L 0 satisfyT ÿ t"1 c t px L 0 ,π 0 t , u L 0 ,π 0 t q ď T β e ´β{2 .• The iterates px L 1 ,π 1 t , u L 1 ,π 1 t q T t"1 produced by following π 1 in system L 1 satisfyT ÿ t"1 c t px L 1 ,π 1 t , u L 1 ,π 1 t q " 0.Proof. The fact that π 0 , π 1 P KpIq is immediate from Definition 29 and the choice of I. To bound the total cost of π 0 on L 0 , note that x L 0 ,π 0 t`1 p2q ´1{2 " p1 ´β{T qpx t p2q ´1{2q for all t ‰ T {2, and x L 0 ,π 0 t`1 p2q ´1{2 " p1{2qp1 ´β{T qpx t p2q ´1{2q for t " T {2. Thus,T ÿ t"1 c t px L 0 ,π 0 t , u L 0 ,π 0 t q " T ÿ t"T {2`1 |x L 0 ,π 0 t p2q ´1{2| ď T ÿ t"T {2`1 p1 ´β{T q t´1 ď T β e ´β{2 .Moreover, we have x L 1 ,π 1 t " p0, 1q for all t ď T {2 and x L 1 ,π 1 t " p1{2, 1{2q for all t ą T {2, so indeedř T t"1 c t px L 1 ,π 1 t , u L 1 ,π 1 tq " 0 as claimed.Lemma 32. Let Alg be any randomized algorithm for online control, and let b P t0, 1u. The (random) trajectory px t , u t q T t"1 produced by Alg in system L b satisfies the inequalityT ÿ t"1 c t px t , u t q " T ÿ t"T {2`1 |x t p2q ´1{2| ě T 8β |x T {2`1 p2q ´1{2| 2 ´1.Proof. By definition of L 0 , L 1 and the valid control set I, any valid trajectory in L b satisfies }x t ´xt`1 } 1 ď 2 }u t } 1 ď 2β{T for all T {2 ă t ă T . It follows that |x t`1 p2q ´1{2| ě |x t p2q 1{2| ´2β{T for all such t, and henceT ÿ t"T {2`1 |x t p2q ´1{2| ě T {2 ÿ n"1 max ˆ0, |x T {2`1 p2q ´1{2| ´2βn T ě |x T {2`1 p2q ´1{2| 2 ¨Z T 4β |x T {2`1 p2q ´1{2| ě T 8β |x T {2`1 p2q ´1{2| 2 ´1as claimed.Proof of Theorem 30. Let b " Unifpt0, 1uq be an unbiased random bit, and let px t , u t q T t"1 be the (random) trajectory produced by executing Alg on L b . On the one hand, by Eq. ( 44) applied to L 0 and L 1 , we haveEQUATIONwhere the first inequality uses the definition of I and the fact that the cost functions pc t q t are convex and 1-Lipschitz per Assumption 1; and the second inequality is by Lemma 31. On the other hand, by Lemma 32, we haveEQUATION)where the key equality p‹q uses the fact that L 0 , L 1 are identical up until and including time T {2, and hence px T {2 , u T {2 q is independent of b. Comparing Eq. ( 46) with Eq. (45) yields thatf p1, 1, β{T, T q ě T 1024β ´1´T 2β e ´β{2 " ΩpT q for any sufficiently large constant β.In this section we describe the version of GPC-Simplex (Algorithm 1) implemented for our experiments. First, the dynamical systems in our experiments are non-linear. The GPC-Simplex algorithm is still practical and applicable in such settings -concretely, any setting with update rule Eq. ( 9) -but of course several modifications/generalizations must be made:1. The algorithm takes as input the function f describing the dynamics in Eq. ( 9), rather than transition matrices A, B. Accordingly, in Line 8, the expression p1 ´}u t } 1 qAx t `Bu t Top: Perturbation sequence: wt " r0, 1, 0s, @1 ď t ď 200. γt " 0.01 ¨Berp0.2q, @1 ď t ď 200. Bottom: Perturbation sequence: @t, wt is a normalized uniform random vector. γt " 0.01, @1 ď t ď 200.In this section, we provide more details regarding the setup and experiments in Section 4.1.The continuous time dynamical system considered by [27] is the following: let Sptq, Iptq denote the susceptible and infected fraction of the population at time t, and let σptq denote the control at time t.The system has some initial state pSp0q, Ip0qq in the set D :" tpx 0 , y 0 q : x 0 ą 0, y 0 ą 0, x 0 `y0 ď 1u, reflecting the constraint that Sp0q, Ip0q represent disjoint proportions of a population, and the system evolves according to the differential equationEQUATIONEQUATION)where γ ą 0 is some fixed model parameter, and the control σptq models a non-pharmaceutical intervention (NPI) inducing a time-dependent reproduction number σptq P r0, σ 0 s, where σ 0 is the base reproduction number in the absence of interventions. In most examples in [27] , including the example of controlling hospital flows, the parameter settings σ 0 " 3 and γ " 0.1 are used. This means that the natural discretization of Eq. ( 48) is in fact equivalent to Eq. ( 11) with transmission rate β :" γσ 0 " 0.3, recovery rate θ :" γ " 0.1, loss-of-immunity rate ξ :" 0, no perturbations (i.e. γ t " 0 for all t), and controlu t :" ˆ1 ´σptq σ 0 , σptq σ 0 ˙,at each time t. The goal in [27] is the following: given an initial state pSp0q, Ip0qq along with a horizon length T ą 0 and the parameters listed above, choose an admissible control function σ : r0, T s Ñ r0, σ 0 s to minimize the loss J :" ´S8 pSpT q, IpT q, σ 0 q `ż T 0 LpSptq, Iptq, σptqqdt,where LpSptq, Iptq, σptqq is the instantaneous cost at time t, and the extra term S 8 pSpT q, IpT q, σ 0 q incentivizes the state of the system at time T to lead to a favorable long-term trajectory (in the absence of any interventions after time T ). In [27] , the following formula for S 8 is given; see that paper for further discussion: S 8 pS, I, σ 0 q " W 0 p´σ 0 Ie ´σ0pS`Iq q σ 0 . The instantaneous cost is modeled by [27] as follows:LpSptq, Iptq, σptqq " c 2 ¨ˆ1 ´σptq σ 0 ˙2 `c3 ¨pIptq ´ymax q 1 `e´100pIptq´ymaxq ,where c 2 , c 3 are some parameters determining the cost of preventing disease transmission and the cost of a medical surge (i.e. when the proportion of infected individuals exceeds y max ). Notice that the second term above will indeed be very small in magnitude unless Iptq exceeds y max .Note that GPC-Simplex cannot directly handle end-of-trajectory losses such as the term S 8 pSpT q, IpT q, σ 0 q. Thus, in our evaluation of GPC-Simplex on this system, we instead incorporate S 8 into the instantaneous cost functions. Concretely, we use the following cost function at time t: c t px t , u t q " ´S8 px t p1q, x t p2q, σ 0 q `c2 ¨ut p1q 2 `c3 px t p2q ´ymax q 1 `e´100pxtp2q´ymaxq . Recall that we write x t " pS t , I t , R t q and u t p1q " 1 ´σptq{σ 0 , so modulo the addition of S 8 to all times t ă T and the conversion from continuous time to discrete time, our loss is analogous to that of [27] .The replicator equation is a basic model in evolutionary game theory that describes how individuals in a population will update their strategies over time based on their payoffs from repeatedly playing a game with random opponents from the population [11] . The basic principle is that strategies (or traits) that perform better than average in a given environment will, over time, increase in frequency within the population, whereas strategies that perform worse than average will become less common.Formally, consider a normal-form two-player game with d possible strategies and payoff matrix M P R dˆd . A population at time t is modelled by the proportion of individuals that currently favor each strategy, and thus can be summarized by a distribution xptq P R d . The fitness of an individual playing strategy i P rds in a population with strategy distribution x P ∆ d is defined to be fitness M,x piq :" e J i M x, where e i P R d is the indicator vector for strategy i. That is, fitness M,x piq is simply the expected payoff of playing strategy i against a random individual from the population. The replicator dynamics posit that the population's distribution over strategies xptq will evolve according to the following differential equation:dx i ptq dt :" x i ptq ¨`fitness M,xptq piq ´Ej"x fitness M,xptq pjq ˘" x i ptq ¨pe J i M xptq ´xptq J M xptqq.(49) It is straightforward to check that this differential equation preserves the invariant that xptq is a distribution. This equation can induce various types of dynamics depending on the initialization and payoff matrix M : the distribution may converge to an equilibrium, or it may cycle, or it may even exhibit chaotic behavior [11] . In this study we focus on a simple (time-discretized) replicator equation -namely, the equation induced by a generalized Rock-Paper-Scissors game -when the payoffs may be controlled.Controlled Rock-Paper-Scissors. The standard Rock-Paper-Scissors game has d " 3 and payoff matrixM :" « 0 1 ´1 ´1 0 1 1 ´1 0 ff .Consider a setting where the game is run by an external agent that is allowed to set the payoffs. For simplicity, we assume that the game remains zero-sum and the rewards sum to 1, so the payoff matrix is nowEQUATIONff for a control vector u P ∆ 3 . The discrete-time analogue of the replicator equation with this controlled payoff matrix M puq isEQUATIONwhere x t , u t P ∆ 3 are the population distribution and control at time t respectively, and η P p0, 1q is the rate of evolution. Note that the term x t M pu t qx t does not need to appear in Eq. (50) because M pu t q is always zero-sum. Also, since η ď 1 and all entries of M pu t q are at most 1 in magnitude, if x t is a distribution then x t`1 will remain a distribution. We omit noise in this study, so Eq. ( 50) is a special case of Eq. ( 9) with γ t " 0 for all t. (b) Proportions of the population playing strategies "rock", "paper", and "scissors" over time under control by GPC-Simplex.Figure 7 : Experimental results for dynamical system with horizon T " 100, uniform initial state, update rule Eq. ( 50) with η " 1{4, no perturbations, and time-invariant cost function ctpxt, utq " x 2 t1 for all times t. GPC-Simplex was implemented as described in Appendix E. The Best Response controller at each time t picks the control u that minimizes ct´1pf pxt, uq, uq. The default controller picks the uniform control u " p1{3, 1{3, 1{3q.Parameters and cost function. We define a (nonlinear) dynamical system with uniform initial state x 1 " p1{3, 1{3, 1{3q, update rule Eq. ( 50) with η " 1{4, and T " 100 timesteps. We consider the fixed cost function cpx t , u t q :" x 2 t1 , which can be thought of as penalizing the strategy "rock".Results. We compare GPC-Simplex (implemented as described in Appendix E) with a baseline control that simply uses the standard Rock-Paper-Scissors payoff matrix (up to scaling) induced by u " p1{3, 1{3, 1{3q P ∆ 3 . As shown in Fig. 7a , GPC-Simplex (shown in blue) significantly outperforms this baseline (shown in green), learning to alter the payoff in such a way that the population tends to avoid the "rock" strategy. The evolution of the dsitribution over time under GPC-Simplex is shown in Fig. 7b .For completeness, we also compare GPC-Simplex against the "Best Response" strategy (shown in dashed orange) that essentially performs 1-step optimal control, using the fact that the cost function for this example is time-invariant. While both controllers eventually learn a good policy, Fig. 7a clearly shows that Best Response learns faster. However, it is strongly exploiting the time-invariance of the cost function, since in general, this algorithm computes the best response with respect to the previous cost function rather than the current cost function, which it does not observe until after playing a control. In Fig. 8 , we consider a slightly modified system where the cost function includes a cost on the control with probability 1{2. In this setting, we see that GPC-Simplex still eventually learns a good policy, whereas Best Response and the default control incur large costs through the trajectory. Best Response in particular suffers greatly due to the time-varying nature of the costs.Our work provides a robust algorithm with theoretical justifications for practical control problems that might be applicable to problems such as disease control. The experiments performed are preliminary. More careful empirical verification is necessary before our algorithm can be responsibly implemented in high-impact scenarios. Excluding the scenario of ill intention, we do not anticipate any negative social impact. t3 with equal probability. GPC-Simplex was implemented as described in Appendix E. The Best Response controller at each time t picks the control u that minimizes ct´1pf pxt, uq, uq. The default controller picks the uniform control u " p1{3, 1{3, 1{3q. The plot shows the cost achieved by GPC-Simplex over time, compared to default Rock-Paper-Scissors control and Best Response control (dashed orange). Due to the non-continuity induced by the random cost functions, the loss plotted at time t is the average loss of the controller across the last minpt, 15q time steps.The experiments in this work are simulations and relatively small-scaled. They were run on Google Colab with default compute resources. For each experiment, the time required to roll-out one trajectory using GPC-Simplex was less than 10 minutes. including code, unless this is central to the contribution (e.g., for a 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: //nips.cc/public/guides/CodeSubmissionPolicy) 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 a 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 in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: The paper specifies all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [No] Justification: The experiments are primarily deterministic; the experiments with randomness are provided largely as proof-of-concept. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • 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 error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.[22,20] showed that the prediction task in a marginally stable LDS can be solved with sublinear regret via spectral filtering if the state transition matrix is symmetric. The construction for Theorem 1 has symmetric transition matrices, so the result in a sense separates analogous prediction and control tasks.Markov decision processes can also be thought of as controlled Markov chains. However, in that setting the controls/actions are at the individual level, whereas we are concerned with controls at the population level, as motivated by applications to epidemiology, evolutionary game theory, and other fields.See Appendix B for discussion about this modelling assumption.If X does not have a unique stationary distribution, we say that all of these quantities are infinite.While our techniques allow some more general choices for I, we leave a full investigation of general I for future work.Such an assumption cannot be dropped in light of Theorem 1.Technically, in this setting of general LDSs where the state domain is unbounded, Assumption 1 is stronger than the assumption on cost functions made in prior work on non-stochastic control[1], because it enforces a uniform Lipschitzness bound on the entire domain. But we are proving a lower bound in this section, so this strengthening only makes our result stronger. 
 
 Appendix:  


Decision: This paper examines the problem of controlling dynamical systems such as those employed to model population dynamics, e.g., SIR model or replicator dynamics. Expanding on earlier research in non-stochastic/adversarial control of linear dynamical systems, the authors introduce a novel class of dynamics, simplex LDS. They prove how a broader application of disturbance action control policies can attain sublinear regret when compared against linear controllers with bounded mixing time. The paper also includes interesting numerical simulations. At the end of the discussion process the reviewers were in unanimous support for the paper. The authors should make sure to  carefully address the issues that they themselves how pointed out in their appendix in the manner they have suggested in their response.

Reviews: review: paper_summary: paper_summary: The paper explores the problem of population control in more practical settings such as the presence of adversarial noise and time-varying cost functions by proposing a robust methodology derived from online non-stochastic control theory.
strength_weakness: strength_weakness: - Unclear motivations for the considered simplex LDS setting. A discussion on more general LDS settings would be helpful.

- While an in-depth discussion on the assumption of gamma_t being observable was provided, there should be concrete examples where the controller could realistically observe the total counts of individuals of different types in a population. This is particularly important because the proposed algorithm and its guarantee are grounded on the simplex LDS model, which requires this assumption.

- Missing formal analyses on time complexity. This could be important for larger-scaled experiments (d >> 3), which the paper did not explore.
questions: questions: See the above and below comments.
limitations: limitations: See the above comments.

Have the authors adequately addressed the limitations and potential negative societal impact of their work? If not, please include constructive suggestions for improvement. Authors should be rewarded rather than punished for being upfront about the limitations of their work and any potential negative societal impact.

- Given the various assumptions made while proving the regret guarantee, a dedicated Limitations or Implications section delineating use cases and generalizability should be included.

- Figure 1 and its texts are too small; the texts in Figure 2 as well.

- The experiment on vanilla SIR model in the main text seems trivial and should be replaced with the replicator dynamics experiment in the appendix.
paper_summary: paper_summary: This paper studies online control problems for the simplex Linear Dynamical System model. They propose a gradient-based control algorithm GPC-Simplex and show its regret bound. Experiments are conducted to validate the performance of GPC-Simplex.
strength_weakness: strength_weakness: My main concern is the novelty of the proposed algorithm compared with the original GPC algorithm. Could the authors provide more justifications for this?
questions: questions: It seems that the authors assume the cost functions are uniformly Lipschitz. What happens if each $c_t$ is $L_t$-Lipschitz, but there isn't an upper bound for $L_t$'s?
limitations: limitations: I don't see any limitations or potential negative societal impact of this work.
paper_summary: paper_summary: The paper studies the problem of actively controlling a class of dynamical systems that are used to model population dynamics, like the SIR model or replicator dynamics. Building on prior work on non-stochastic / adversarial control of linear dynamical systems, the authors propose a new class of dynamics, simplex LDS, and show how a generalization of disturbance action control policies can achieve sublinear regret with respect to the comparator class of linear controllers with bounded mixing time. In addition to their theoretical results, the authors carry out numerical simulations on nonlinear dynamical systems to investigate the benefits of their algorithm.
strength_weakness: strength_weakness: It would be nice to include simple examples of simplex LDSs in the introduction when defining the model to provide the reader with more intuition. Some of the technical conditions are somewhat strange and hard to interpret, particularly the condition that the norm of the control vector is independent of the state in the comparator class. I think that the paper would be well served if the authors could provide further insights regarding why these assumptions are technically necessary, or under what conditions they might be justified. 

In terms of experiments, it would also be nice if the authors experimented with higher dimensional systems. They would make the paper stronger, but I don’t feel they are strictly necessary.
questions: questions: See questions about regarding the comparator class of policies.

Also please make the figures and label text larger, they are a bit hard to read.
limitations: limitations: Yes, these have been discussed to the extent necessary.
paper_summary: paper_summary: This paper addresses the challenge of controlling partially observable linear dynamical systems (LDS) with adversarial disturbances. Traditional methods for controlling LDS assume full observability, but this assumption does not hold in many real-world applications. The authors propose the GPC-PO-Simplex algorithm, which leverages mirror descent and approximate solutions to sub-problems to achieve control in partially observable settings. Theoretical guarantees are provided for the algorithm's performance, and empirical evaluations demonstrate its effectiveness in controlling population dynamics and other systems under adversarial conditions.
strength_weakness: strength_weakness: Idealized Assumptions: 
The algorithm assumes certain ideal conditions, such as known transition matrices and Gaussian noise, which may not hold in all real-world scenarios. Relaxing these assumptions could make the method more broadly applicable.

Limited Generalization: 
While the algorithm performs well on the tested systems, its generalization to highly non-linear or more complex systems is not fully established. Further work is needed to test the algorithm's performance in a broader range of scenarios.

Sensitivity to Parameters: 
The performance of the algorithm is sensitive to the choice of parameters. Providing more guidance on parameter selection or developing a method to adaptively choose parameters could improve practical usability.

Experimental Scope: 
The experimental validation is limited to simulated environments. More real-world experiments would strengthen the evidence for the algorithm's practical effectiveness.
questions: questions: 1.How does the algorithm perform in real-world applications with non-Gaussian noise and unknown transition matrices?
2.Can the authors provide more detailed guidance or a method for adaptively selecting the algorithm's parameters?
3.What are the computational requirements of the algorithm in large-scale systems? 
4. How robust is the algorithm to inaccuracies in the model assumptions, such as errors in the transition matrices or noise characteristics?
5. How does the algorithm handle delays in control actions or observations, which are common in real-world systems?
limitations: limitations: The authors have discussed some limitations of their work.

Comments: comment: I think the author has addressed the issues I raised, so I'm raising the score to boardline accept.
Thank you for the clarification and your honesty in reporting the bug. I think that a paper that only focuses on the fully observed setting is still worthy of acceptance.