Online Control in Population Dynamics
Authors: Noah Golowich
Elad Hazan
Zhou Lu
Dhruv Rohatgi
Y. Jennifer Sun
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Control
Theory
Population Dynamics
Linear Dynamical Systems
Primary area: online_learning
TL;DR: We give an efficient online controller with provable regret guarantees for population dynamical systems.

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.

Online Control in Population Dynamics
Noah Golowich"
Elad Hazan
Zhou Lu
Dhruv Rohatgi²
Y. Jennifer Sun
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 set of linear dynamical systems that can naturally model evolving populations. We then give an efficient gradient-bant based controller for these systems, with near-optimal regret bounds with respect to broad class linear policies. Our empirical evaluations demonstrate the effectiveness of the proposed algorithm for population control even in non-linear models such SIR and replicator dynamics.
Introduction
Dynamical systems involving populations are ubiquitous in describing processes that arise natural environments, As one example, the SIR model [26] is fundamental concept in epidemiology, used to describe the spread 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 infected if interacting with an infected individual. A removed individual either has recovered from the discase and gained immunity or is deceased. The population evolves over time according to three ordinary differential equations:
dS 315 dl
di 31S
dR
01,
01,
(I)
di
di
for constants 3,6 > 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 natural to how might best be controlled. For instance, controlling the spread of an infectious disease while minimizing externalities is problem of significant societal importance.
In many natural models, these dynamics tend be nonlinear, the control problem is often computationally intractable. Existing algorithms are designed on case-by-case basis by positing specific system of differential equations, and then numerically analytically solving for the optimal controller. Unfortunately, this approach is not robust to adversarial shocks to the system and cannot adapt time-varying cost functions.
MIT. nzg@mit. edu.
"Google DeepMind & Princeton University. ehazan@prinnetton.de
Prinnceton University. zhouleprinceton..de
MIT. drohatgi teaetgiiimit..ee edu.
Princeton University, 7e7784pprinneton.com
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

A new approach for population control. In this paper we propose a generic and robust methodol- ogy for population control, drawing on the framework and tools from online non -to-ssochastic control theory to obtain computationally efficient tradient-based method of control. In online non-stochastic control, at every time t = ,,..., The learner then incurs cost according to some time-varying cost function e (2t, Uy) evaluated at the current state/control pair, and the state evolves as:
T, ,.,,,
the learner is faced with a state 2y and must choose a control ut-
J(+1 := f(2,, u4) + Wi,
where f describes the (known) discrete-time dynamics, 2++1 is the next state, and is an adversarially-chone perturbation. A policy a mapping from states controls. The goal of the learner is to minimize regret with respect to some rich policy class II, formally defined by
regretn Σ cl ue)
min Tell
alx v.),
(3)
where (xT, u/) is the state/control pair at time had policy x been carried out since time
As with prior work in online control [1], our method is theoretically grounded by regret guarantees for a broad class of Linear Dynamical Systems (L.DSs). 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 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.
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, is impossible to achieve sub-linear regret against that class- result that may be of independent interest in online control:
Theorem 1 (Informal statement of Theorem 25). There a distribution over LDSs with state space and control space given by R. such that any online control algorithm on a system C ~ D incurs expected regret ((T) against the class of time invariant linear policies that marginally stabilize C.
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).
1.1 Our Results
Throughout this work, we model population as a distribution over d different categories, evolving over T discrete timesteps. For simplicity, we assume that u, a d-dimensional real vector.
Theoretical guarantees for online population control. We introduce the simplex LDS model (Definition 3), which is modification of the standard LDS model (Definition 9) that ensures the states (Ir)) always represent valid distributions, i.e. never leave the simplex A Informally, given state 2e E A and control Ue E Rg with [|ull, & 1, the next state is
It+1 = (1 (1-11)) 7) [(1 - ( + Bu]] + Wt.
where A, are known stochastic matrices, 7 E [0. 1] is the observed perturbation strength, & and w, E A is an unknown perturbation. The perturbation w, can be interpreted as representing an
$122, 20] showed that the prediction task in marginally stable LDS can be solved with sublinear regret via spectral filtering if the state transition matrix is symmetric. The construction for Theorem I has symmetric transition matrices, so the result in a sense separates analogous prediction and control tasks.
7 "Markov decision processes can also be thought of controlled Markov chains. However, in that setting the controls/actions are at the individual level, whereas we are concerned with controls the population level. as motivated by applications to epidemiology, evolutionary game theory, and other fields.
See Appendix B for discussion about this modelling assumption.

---

adversary that can add individuals from a population with distribution to the population under study. Intuitively, d, represents distribution over d possible interventions as well as 'null intervention".
For any simplex LDS L and mixing time parameter T > O, we define a class K.A (C. (Definition 6), which roughly consists of the linear iime-invariant policies under which the state of the system would mix to stationarity in time T, in the absence of noise. Our main theoretical contribution is an algorithm GPC-Simplex ex that achieves low regret against this policy class:
Theorem 2 (Informal version of Theorem 7). Let L be simplex LDS on Ad, and let T >> O. For any adversarially-
perturbations (wy) perturbation strengths (rt)s, and convex and Lipschitz cost fimctions (c));, the algorithm GPC-Simplex performs I steps of online control on L with regret Ö(7 V d'') against Kct (C).
Finally, analogously Theorem 1, we show that the mixing time assumption cannot be removed: is impossible to achieve sub-linear regret (for online control of 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) CPC-Simples 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, 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 noisy cost functions than a one-step best response controller.
algorithm is robust even in the presence
1.2 Related work
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 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 dynamies 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 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.
2 Definitions and setup
Notation. Denote Sd :- { M E [0, 1]dxd dd Σ.= M., = 1 1Vj [d]] as the set of d x d column-
stochastic matrices. For a > O. define sd = fa M : M E 8d) and gdt
denote the simplex in Idd. Similarly, we define A == a A and Ad ca == User' sg. Let A Ubsa'so sa Ag. Given square matrix M Rdxd, let M.j denote the jth column of M. We consider the following matrix norms: [M] denotes the spectral norm of M, |M := Σ |M is the sum of the squares of the l norms of the columns of M, and [M 1-11 sup sup -1 M
3

---

2.1 Dynamical systems
The standard model 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 N. A simplex LDS on A is tuple
L = B,I, 11, (To) (wy)teN. (Ce)teN),
where A, B E Sd are the transition matrices; I S Ag is the valid control set; 21 A d is the initial state; "/t [0, 1], Wy A are the noise strength and noise value at time and C A x I - IR is the cost, function at time t. These parameters define a dynamical system where the state at time t = 1 3T. For each & 1, given state 2, and control u, I at time the state at time i + i
T++1 (1 11-m) 7)) [(1 - | 1) + Bug] 7/t" Wt:
(4)
and the cost incurred at time is c2 uz).
Note that since the set of possible controls I is contained in A the states (Ir)), are guaranteed to remain within the simplex for all t. In this paper, we will assume that I = Uee[a A for some parameters a. a [o, 1], which represent lower and upper bounds the strength of the control.
Online non-stochastic control. Let L = (A, B, æ1, (1.(111())))) (T))ENN (Wi)tNN (C,) I) be a simplex LDS and let 7 N+. We assume that the transition matrices A, B are known to the controller at the beginning of time, but the perturbations (w,){= are unknown. At each step < f & T, the controller observes 22 and nt plays control #y I, and then observes the cost function C and incurs cost ea (22, uz). The system then evolves according to Eq. (4). Note that our assumption that the controller observes "/ contrasts with some of the existing work nonstochastic control [1, 211, in which no information about the adversarial disturbances is known. In Appendix B, we justify the learner's ability observe "/ 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 x4),, and that this additional information allows computation of %/-
The goal of the controller is to minimize regret with respect to some class K = KC(C) of comparator policies. Formally, for any fixed dynamical system and any time-invariant and Markovian policy K A - I, let (xx(K)); and (ux(K)), denote the counterfactual sequences of states and controls that would have been obtained by following policy K. Then the regret of the controller observed sequences (x))) and (ue), with respect to IC
regretx == Σ cola,, uz) - inf
Σ ((((((),((())))
KeK
The following assumption on the cost functions of C is standard in online control [1. 38, 37]: Assumption 1. The cost functions Ca A x I IR convex and L-Lipschitz, in the following sense: for all x, x' E A and u, u' E I. we have (z, u) - ae (x', ,²)) & L. L-I1 2'1, + u
2.2 Comparator class and spectral conditions
In prior works non-stochastic control for linear dynamical systems [1]. the comparator class K. (L) defined to be the set of linear, time-invariant policies x +> Ka where K Rddx (1s, p)-ttonnly stabilizes L:
Definition& 4. A matrix M Rdddd is (R. p)-strongly stable if there is matrix H Rdxd so that [H < 1 and [IM], [H | < K. A matrix K E [dxd is said to (x, p)-strongly stabilize an LDS with transition matrices A, B e dxd if A + BK is (k, p)-trongly stable.
The regret bounds against (C) scale with اا and so are vacuous for p = 0 [1]. Unfortunately, in the simplex LDS setting, no policies satisfy the analogous notion of strong stability (see discussion in Section 3) unless p = 0. Intuitively, the reason is that a (R,, p) strongly stable policy with p > makes the state converge 0 in the absence of noise.

---

What is richer but stil--tacctbbe comparator class for a simplex LDS? We propose the class of linear, time-invariane policies under which (a) the state of the LDS mixes, when viewed as distribution, and (b) the level of control | is independent of the state xy. Formally, we make the following definitions:
Definition 5. Given & N and matrix X e gd with unique stationary distribution ι A we define (x(t) == su I| T|, and (t) := supp.ge | (p- (p- 9)]l1 Moreover we define pmix (mix(X, (X, ;= minees (4 (1) & E) for each
0, and we write (mi := g (X, 1/4)."
Definition 6 (Mixing simplex LDS), Let L be simplex LDS with transition matrices A, B Sd and control set Z Une[a,a] Ag A matrix K E 84 [a.3]
is said to r-mix L if (mix(Ax & T, where
Ak := (1 ||X|)-
A+ BK S
(5)
We define the comparator class K (C) as the set of linear, where K e sd [a,o] T-mixes L.
policies - Kx
Notice that for any K E Si laay the linear policy u, == Kx, always plays controls in the control set I, and the dynamics Eq. (4) under this policy can be written as 2z+1 (1 7r) AKT "/ Wt.
Notice that by considering the comparator class ICF,, we require the control norm to be independent of the state. This assumption is needed for technical reasons: without it, since Axr is multiplied by 1 - |ulla in the transition dynamics (see Equation (4)), even a "linear" policy u := K does not induce 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.
3 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 Unefara] Ad. for some constants 0 & a a & representing lower and upper bounds on the strength of the control."
For convenience, we write a; := |uell and wnj = u E A (if a; = 0, we set u/ == 0). The dynamical system Eq. (4) can then be expressed follows:
1t+1 (1 ne) ((1 az) Ar, aa But) + 7 Wt.
(6)
We aim to obtain a regret guarantee as in Eq. (3) with respect to some rich class of comparator policies ICA, As is typical in existing work linear nonstochastic control, take KC to be class of time-invariant linear policies, i.e. policies that choose control un := KIx at time / for some matrix K E IRdxd 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)." The naive generalization of such requirement in our setting would be that Ax is strongly stable; however, this is impossible, since no stochastic matrix can be strongly stable. Instead, we aim to compete against the class K XCA of time-invariant linear policies that (a) have fixed level of control in [a, a]. and (b) 7-mix L (Definition 6). We view the second condition as a natural distributional analogue of strong stabilizabilitty the first condition is needed for r-mixing to even be well-defined.
Algorithm description. Our main algorithm, GPC-S GPC-Simples ex (Algorithm 1), is a modification of the GPC algorithm [1, 21]. As a refresher, GPC chooses the controls u, by learning disturbance-actio policy: a policy Ue := Kx, + > M M where K is a known, fixed matrix that strongly stabilizes the LDS; wi-1,.... -0:-1 are the recent noise terms; and M MH are learnable, matrix-valued parameters which we abbreviate as M The key advantage of this parametrization
'If X does not have a unique stationary distribution, say that all of these quantities are infinite. While our techniques allow some more general choices for Z. we leave a full investigation general for future work.
Such assumption cannot be dropped in light of Theorem 1.
5

---

of policies (as opposed to simpler parametrization such as = Kr, for parameter K) is that the entire trajectory linear in the parameters, and not a high-degree polynomial. Thus, optimizing the cost of trajectory over the class of disturbance-action policies a convex problem in M M11:H
But why is the class of disturbance-action policies expressive enough to compete against the compara- tor class? This is where GPC erucially uses strong stabilizabilitt. Notice that in the absence of noise, every disturbance-action policy is identical to the fixed policy ب := Kx. This is fine when and the comparator class are strongly stabilizing, since in the absence of noise, all strongly stabilizing policies rapidly force the state to O, and thus incur very similar costs in the long run. But in the simplex LDS setting, strong stabilizability is impossible. While all policies in KC mix the LDS, they may mix to different states, which may incur different costs. There is no reason to expect that an arbitrary K K,A, chosen before observing the cost functions, will have low regret against all policies in KA
We fix this issue by enriching the class of disturbance-action policies with an additional parameter p E A' which, roughly speaking, represents the desired stationary distribution to which zy would converge, in the absence of noise, t cc. 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 (1-1- We retain the property that the requisite online learning problem is convex in the parameters, and therefore can be efficiently solved via online convex optimization algorithm (as discussed in Appendix C.I, we use lazy mirror descent, LazyMD). One advantage of GPC-Simplex over GPC is that the former requires 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 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 ao E [ and HE E N, GPC-Simplex considers a class of poli- cies parametrized by the set Xa,H,oo.T = Uaelen.al A (S We abbreviate elements Hd, ā by (p, (2::1)). The high level idea of GPC-Simplex, like that of GPC, is to perform online convex optimization on the domain Ha. (Line 10). At each time 1, the current iterate (pt, M(I:HI,, which defines a policy TP.,, [ is used to choose the control u, The optimization subroutine then receives new loss function 4, Na. - I based on the newly observed cost function Cr. 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.
(p, (M ..... )
We next formally define the policy pPMM(" associated with parameters (p, M(..H)), and the loss function & used to update the optimization algorithm at time t.
Parametrization of policies. First, for L E [T] and E N+, we define the weights
Ae. = 7--s- I n-)), d,=== = I( - n-1), A = 1 Σ A
j-1
We write wip := 21, To 1, and w. = 0 for < 0 as a matter of convention." 12 Xe, can be interpreted as the "influence perturbation Wt-; on the state xzz,, and Aτ,; can be interpreted as the "influence of
perturbations prior to time step L- on the state xz". An element (p, M(1:Hl) E Xa, induces a
policy!3 at time I, denoted n. p.M via the following variant of the disturbunce-action control [1]:
p.M((L) xt
(61-1--) == de, P
Σ Aus Mi18
(8)
In Line 6 of GPC-Simplex, the control u, chosen be a Ad Ipclla (using Σ/1 Ao,; = 1) and hence to the constraint set (since [ptll E [ap, øt| c [a, a)).
(w,- 1.) H).
which belongs to
12 As a result of this convention, we have Σ A = for all & E [T]. and Ae, = for Technically we are slightly abusing terminology here, since n. () takes input set of the previous H disturbances, dt-1:t-H, Ait-H, opposed to the current state It.

---

Algorithm 1 GPC-Simplex: GPC for Simplex LDS
Require: Linear system A, B, mixing time 7 > 0 for comparator class, horizon parameter H E N, set of valid controls I Uae[a.a a A total number of time steps T.
1: Write TΛ == = (A), and define Go = max(o, aa, min(a. 1 (T > 4
2: Initialize an instance LazyMD of mirror descent (Algorithm 2) for the domain H. with the regularizer Ra, (defined in Appendix C.I) and step size 7j = o In(d) 2 log (T),)), for sufficiently small constant
3: Initialize (f1, Mf ] - arg min minl ye B.gg. Ra (V, M(.:H1).
4: Observe initial state 2ι Ad.
5: for &
& & 7 do 6: Choose control u4 := Ae, Pt + Σ M. Xe,5 Wh-i
7: Receive cost (1 We).
8: Observe It+1: "It and compute W/ 7 (0141 (1- (1-21) (1uua][t-luuulbAAr Buel).
(If = O, then set Wi = 0.)
9: Define loss function (p(p, Ml.H)) =- ce(ee(( Ml. uil,, Ml).H))..
Update (pr+1, M M - LazyMD, (45 (pt, Ml 1)
10:
Loss functions. For (p, M(.:H) Na,H.ao.a. we let rp Mll:H) and ue(p, ML.:H) denote the state and control at step / obtained by following the policy M.M.a at all time steps prior to / (see Eqs. (20) and (21) in the appendix for precise definitions). We then define (p, MlL-H) to be the evaluation of the adversary's cost function C on the state-action pair (Ir(p, M u.(p, Ml::H) (Line 9).
Main guarantee and proof overview. Theorem 7 gives regret upper bound for CPC-Simplex:
Theorem 7. Let d, E N and T O. Let L (A, B, x1, (Ti)eeN, (WE)eeNs (cz)ten) be simplex LDS with cost functions (ct) satisfying Assumption I for some > O. Set == T [[og(2LTT) Then the iterates (Iz, uz)r-1 of GPC-Simplex (Algorithm 1) with input (A, B, T, H.I,T satisfy:
T
regretx?1c0 (c) = Ea(m, inf
Σ (k)) "x 2
KeK. (C) t=1
where Õ(-) hides only universal constants and poly-logarithmic depeeeee in T. Moreover, the time complexity of GPC-Simplex is poly(d,T).
While for simplicity we have stated our results for obliviously chosen (Te)s, (we)r. (c),. since GPC-Simplex is deterministic the result also holds when these parameters are chosen adaptively by an adversary. See Appendix for the formal proof of Theorem 7.
K-((C) Lower bound. We also show that the mixing assumption on the comparator class K (C) (Def- inition 6) cannot be removed. In particular, without that assumption, if the valid control set I is restricted to controls ue of norm mostly roughly O(1/T), then linear regret is unavoidable."
Theorem 8 (Informal statement of Theorem 30). Let 3 > O be a sufficiently large constant. For any T E N, there is a distribution over simplex LDSSs with state space A and control space Uve A3, such that any online control algorithum a system L ~ D incurs expected regret Q(T) against the class of all time-inaaiaat linear policies x + Kx where K =Ueefo.orTy sd.
4 Experimental Evaluation
The previous sections focused on linear systems, but in fact GPO-Simplex can be easily modified to control non-linear systems, for similar reasons in prior work [2]. suffices for the dynamics to
We remark that, with the mixing assumption, Theorem 7 does achieve Õ(vT) regret when Z : Usetu J A. In particular, there hidden dependence on I in the regret bound.
7

---

have the form
2441 == (1-11)) (1),, ue) + 7/w
for known f. observed "r, and unknown Wt- See Appendix E for discussion of the needed modifica- tions and other implementation details. Relevant code open-sourced in [16].
As a case study, in this section we apply GPC-Simplex (Algorithm 1) to a disease transmission model specifically, 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- busceptiile--nfectious---- Innfectious-Recoveree (SIR) model is basic model for the spread 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 susceptible individual comes into contact with an infected individual, the susceptible individual becomes infected at some "transmission rate", B. Infected patients become uninfected and gain immunity at some "recovery rate" 9. We consider natural generalization of the standard dynamics Eq. (I) where recovered individuals may also lose immunity rate of Ç. Formally, in the absence of control, the population evolves over time according the following system of differential equations:
dS dt
dI 3IS 01, dt
dR
BIS + &R, dt
01 ER,
(10)
Typically, 3 >> 0> E. We normalize the total population to be 1, and thus x [S, RJ A3, Next, we introduce a variable called the preventative control u, A which has the effect of decreasing the transmission rate 3, and adversarial perturbations W4, which allow for model misspecification. Incorporating these changes to the forward discretization of Eq. (10) gives the following dynamics:
Si+1 4+1 = (1 - 7+) Re+1
(1
(1
1
81
0
S₁
S1,
0
1 1
4
+
B1S
U4.
+ Wh
(11)
0
0
-
R
0
The control u, E A represents a distribution over transmission prevention protocols: u, = [1, o]
represents full-scale prevention, whereas u, [0, 1] represents that prevention measure is imposed. Concretely, the effective transmission rate under control U, is /3 u, (2).
Parameters and cost function. To model a highly infectious pandemic, we consider Eq. (11) with parameters 0.5, 0.03, and & 0.005. Suppose want control the number of infected individuals by modulating a (potentially expensive) prevention protocol ut. To model this setting, the cost function includes (1) quadratic cost for infected individuals 4, and (2) cost that bilinear in the magnitude of prevention and the susceptible individuals:
CI u,) c3 (2)2 c2 =I( (1),
(12)
where H, = [S, Rt). Typically c > 0o to model the high cost of infection.
In Fig. 1, we compare GPC-Simplex against two baselines (a) always executing u, = [1, (i.e. full prevention), and (b) always executing u4 [0. 1] (i.e. prevention) for T 200 steps in the above model with no perturbations. We observe that GPC-Simplex suppresses the transmission rate via high prevention 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 7t's s) and different model parameters.
4.1 Controlling hospital flows: reproducing 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. one scenario (inspired by the COVID-19 pandemic), they considered cost function that penalizes
8

---

Cool Over Timw, P1055 0:023, (-0233 (ww.:_000.....o.oo... o
Carrubdiv Cast Over TiMe, 2ud Bud Eu1.000, cu12.
4221 Ovar Time, P:6.52 0:3.00 6:0.855, oy13, oy
275
0.5
044
2
15
1000.000
Tex: Srr
Figure 1: Control with cost function (12) for 200 steps: initial distribution æ11 [0.9, 0.1,0.0.000 parameters Cg = 10, Cg 1; no noise. Left/Middle: Cost and cumulative cost over time of GPC-Simplex versus baselines.
Right: control (2) (proportional to effective transmission rate) played by GPC-Simplex over time.
medical surges, i.c. when the number of infected exceeds threshold 3/max determined by hospital capacities. Formally, they define the cost of a trajectory (Iz, uz uz) as
((r(()))2(22))
02 ue v1) c2(2((2) Imaxx) [
dt,
(13)
1 e (00( Vmnaa)
where Wi is the principal branch of Lambert's W-function, and c2, C3 hyperparameters. The system parameters used by [27] are 3 = 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- Aacobi-Bellman equations for various choices of 62 C3.
In Fig. 2, we show that GPC-Simplex (with slightly modified instantaneous version of Eq. (13)) fact matches the optimal solution analytically computed by [28]. See Appendix for further experimental details, including the exact model parameters and cost function.
c2m0.01 c3-100
1.0
#2)1PPC singlol
42)
102110 intrvettio
0.8
You
0.-
0.1
0.4
0.
20
80 100
20
60 300
Figure 2: Controlling hospital flows for T 100 steps: initial distribution [0.9, 0,01,........ 0.09]; parameters Youz = 0.1, control; note that ymax (shown in dashed purple line) significantly exceeded. The solid yellow and blue lines show the number infected and susceptible under CPC-Simplex. which closely match optimal solutions computed by [28] (dashed yellow and blue). Right: GPC-Simp Simplie ex control (solid) vs. optimal control (dashed).
0.01, = 100. Left: The dashed red line shows the number of infected over time under no

---

Acknowledgements
NG is supported by a Fannie & John Hertz Foundation Fellowship and NSF Graduate Fellowship. EH, ZL and JS gratefully acknowledge funding from the National Science Foundation, the Office of Naval Research, and Open Philanthropy. DR is supported by a U.S. DoD NDSEG Fellowship.
References
[1] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119. PMLR, 2019.
[2] Naman Agarwal, Elad Hazan, Anirudha Majumdar, and Karan Singh. A regret minimization approach to iterative learning control. International Conference on Machine Learning, pages 100-109. PMLR, 2021.
[3] Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32, 2019.
[4] Linda IS Allen. Some discrete-time si, sir, and sis epidemic models. Mathematical biosciences, 124(1):83-105, 1994.
[5] Rocío Balderrama, Javier Peressutti, Juan Pablo Pinasco, Federico Vazquez, and Constanza Sánchez de la Vega. Optimal control for sir epidemic model with limited quarantine. Scientific Reports, 12(1):12583, 2022.
[6] Ottar N Bjørsstad, Bärbel F Finkenstädt, and Bryan T Grenfell. Dynamics of measles epidemics: estimating scaling of transmission rates using time series sir model. Ecological monographs, 72(2):169-184, 2002.
[7] Fred Brauer, Carlos Castillo-Chavez, and Carlos Castillo-Chavez. Mathematical models in population biology and epidemiology, volume 2. Springer, 2012.
[8] Tom Britton. Stochastic epidemic models: survey, Mathematical biosciences, 225(1):24-35, 2010.
[9] Yi-Cheng Chen, Ping-En Lu, Cheng-Shang Chang, and Tzu-Hsuan Liu, time-dependent sir model for covid-19 with undetectable infected persons. Ieee transactions on network science and engineering. 7(4):3279 -3244, 2020.
[10] Ian Cooper, Argha Mondal, and Chris G Antonopoulos. A sir model assumption for the spread of 19 in different communities. Chaos, Solitons & Fractals, 139: 10057, 2020.
[11] Ross Cressman and Yi Tao. The replicator equation and other game dynamics. Proceedings of the National Academy of Sciences, 1 1ssupppeement__ 3):10810-- 111101111181111 2014.
[12] Adil El-Alami Laaroussi, Mostafa Rachik, and Mohamed Elhia. An optimal control problem for a spatiotemporal sir model. International Journal of Dynamics and Control, 6:384-397, 2018.
[13] Mohamed Elhia, Mostafa Rachik, and Elhabib Benlahmar. Optimal control of an sir model with delay in state and control variables. International scholarly research notices, 2013, 2013.
[14] Herbert I Freedman. Deterministic mathematical models in population ecology. (No Title). 1980.
[15] Nicole M Gatto and Henry Schellhorn. Optimal control of the sir model in the presence of transmission and treatment uncertainty. Mathematical biosciences, 333:108539, 2021.
[16] Noah Golowich, Elad Hazan, Zhou Lu, Dhruv Rohatgi, and Y. Jennifer Sun. Population control, 2024. /ttpss//got //gbttubb/tttt//// com/ httpu////pppplaatioooooottrt
[17] EV Grigorieva, EN Khailov, and A Korobeinikov. Optimal control for sir epidemic model with nonlinear incidence rate, Mathematical Modelling of Natural Phenomena, 11(4):89-104 2016.
10

---

[18] Elad Hazan. Introduction to online convex optimization, 2019.
[19] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorithmic Learning Theory, pages 408-421. PMLR, 2020.
[20] Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems. Advances in Neural Information Processing Systems, 31, 2018.
[21] Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv preprint WiXiv:221100619 2022.
[22] Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering. Advances in Neural Information Processing Systems, 30, 2017.
[23] Josef Hofbauer and Karl Sigmund. Evolutionary games and population dynamics. Cambridge university press, 1998.
[24] Chunyan Ji, Daqing Jiang, and Ningzhong Shi. The behavior of an sir epidemic model with stochastic perturbation. Stochastic analysis and applications, 30(5):555-773: 2012.
[25] Sourabh Katoch, Sumit Singh Chauhan, and Vijay Kumar. A review on genetic algorithm: past, present, and future. Multimedia tools and applications, 80:8091-81266 2021.
[26] William Ogilvy Kermack and Anderson G McKendrick, A contribution to the mathematical theory of epidemics. Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 115(772):700-221, 1927.
[27] David Ketcheson. Optimal control of sir epidemic through finite-time non-pharmaceutical intervention. Journal of mathematical biology, 83(1):7, 2021.
[28] David I Ketcheson. Sir-control-code. optimal control of an sir epidemic through finite-time non-pharmaceutical intervention, 2021.
[29] Nikolay A Kudryashov, Mikhail A Chmykhov, and Michael Vigdorowitsch. Analytical features of the sir model and their applications to covid-19 19. Applied Mathematical Modelling, 90:466- 473, 2021.
[30] Urszula I Ledzewicz and Heinz Schättler, On optimal singular controls for a general sir-model with vaccination and treatment. In Conference Publications, volume 2011, pages 981-990. Conference Publications, 2011.
[31] David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. Markov chains and mixing times. American Mathematical Society, 2006.
[32] Alfred J Lotka. Contribution to the theory of periodic reactions. The Journal of Physical Chemistry, 14(3):271-274, 2002.
[33] Thomas Robert Malthus. An Essay on the Principle of Population Or a View of Its Past and Present Effects on Human Happiness, an Inquiry Into Our Prospects Respecting the Future Removal Or Mitigation of the Evils which it Occasions by Rev. TR Malthus. Reeves and Turner, 1872.
[34] Emilio Molina and Alain Rapaport. An optimal feedback control that minimizes the epidemic peak the sir model under a budget constraint. Automatica, 146: 10596, 2022.
[35] Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
[36] Boris Shulgin, Lewi Stone, and Zvia Agur. Pulse vaccination strategy in the sir epidemic model. Bulletin of mathematical biology, 60(6): 123- 1148, 1998.
[37] Max Simchowitz. Making non-stochastic control (almost) as easy as stochastic, Advances in Neural Information Processing Systems, 38:18318-1888 2020.

---

[38] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[39] Mandavilli Srinivas and Lalit Patnaik. Genetic algorithms: A survey, computer, 27(6): 1994.
[40] Vito Volterra. Fluctuations in the abundance of species considered mathematically. Nature, 118(297)):588-66) -60, 1926.
[41] Gul Zaman, Yong Han Kang, and II Hyo Jung. Stability analysis and optimal vaccination of an sir epidemic model. BioSystems, 93(3):440-249, 2008.
12

---

Contents
Introduction
1.1
Our Results
1.2
Related work
2
Definitions and setup
2.1
Dynamical systems
2.2
Comparator class and spectral conditions
3
Online Algorithm and Theoretical Guarantee
4
Experimental Evaluation
4.1
Controlling hospital flows: reproducing a study by [27]
A Additional preliminaries
14
Discussion on the observation model
14
C Proof of Theorem 7
14
C.I Preliminaries on mirror descent
15
C,2 Approximation linear policies
18
C33 Bounding the memory mismatch enror
19
C,4 Proof of Theorem 7
22
Proof of Lower Bounds
25
D.1 Proof of Theorem
25
D.2 Proof of Theorem
28
Implementation details
30
F Experiments: Controlled SIR model
31
F.I Control presence of perturbations
F22 Alternative parameter settings
31
Experiments:
Controlling hospital flows
32
H Experiments: Controlled replicator dynamics
35
Discussions
36
L1 Broader impacts
36
I.2 Computational Resources for Experiments
37
13

---

A Additional preliminaries
For completeness, we recall the definition of a standard LDS [21].
Definition 9 (LDS), Let day N. A linear dynamical system (LDS) is described by a tuple L (A, B, Fi, (we)ass, (c))eN) where A E Rddx B E Rdd are the transition matrices; I1 E Rd is the initial state; Wt E R&, is the noise value at time t; and o : Rd, x Rd - R is the cost function at time f. For each & 1, given state Iy Rdd and control de Rd at time t, the state at time t + 1 is given by
1 == Ax + Bu Wtr
and the instantaneous cost incurred at time t is given by ca(ae, uz).
B Discussion on the observation model
Our main algorithm GPC-Simplex for online control of simplex LDSs assumes that for each the perturbation strength "t. is observed by the controller at the same time as it observes Te+1 (the algorithm does not require the entire sequence (Te)r to be known in advance). In this appendix 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 Recall that like the algorithm GPC from [1], GPC-Simplex is disturbanne-action controller, meaning that the control at time is computed based on previous disturbances W0-i- In the standard LDS model (Definition 9) studied by [1], it's clear that w4-1 can be computed from Tt-1; 14-11 2t, using the fact that A, B are known. However, in the simplex LDS model, if 7t- is not directly observed, then in fact w may not be uniquely identifiable given æ;-1: 1, 2t-1, Tt. This is why GPC-Simplex requires observing the parameters It is an interesting open problem whether this assumption can be removed.
technically important for GPC-Simplex that the controller observes "Y--
Second, we argue that in many practical upplications, it is reasonable for %-1 to observed along with the population state 24. 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 population which has N₂ individuals at time f. Thus, if the distribution of the population across d categories is described by H, E Ad, then for each E [d] there are N1(2)); individuals in category i. Suppose that under control
I, this population evolves to new
distribution (1 - || uel Ar, + Bu,, but then the adversary adds n, new individuals to the population, whose distribution over categories is given by wy E A Then if we write 5g E Rg to denote the vector of counts of individuals in each category time t, it holds that
T++1 = N11(1 - ||well)) ) Ax, + Bu) + 72902
No 1 ((1 7x) -|v Ax, + Bu.) + Tow))
where Ne+1 Ne+nn n,, is the total number of individuals at time t+ 1, and we write == ni/nnnnNNnt Thus, the distribution of the population across the dl categories at time + 1
Dt+1 = - (1)-m(((11)))) - |uel )Az + Bu)) + Ye
E++1
No+1
which is exactly the update rule from Definition 3. Moreover, if the controller observes the total population counts N,, No+1 1 in addition to Tt, Ut, 11+1 then may compute ?/2 = (N - N,)/Nee well wa (using knowledge of A, B), which is what we wanted to show.
C Proof of Theorem 7
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.
14

---

Overview. GPC-Simplex (Algorithm 1) essentially runs mirror descent on the loss functions (p,, ) constructed in Line 9. In particular, the loss at time measures the counterfactual cost of following the policy (..A for the first / timesteps. Thus, the regret of GPC-Simplex: against the comparator class (C) (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 TP.M/(M for (p, M[1:H)) Ha, we must show that every policy in the comparator class can be approximated by some policy PP.M( This accomplished by Lemma 17.
Mismatch error of costs. The cost incurred by the mirror descent algorithm LazyMD at time is le (pt, M M(I:H)), which is the counterfactual cost at time / had the current policy xPc.Mf[-a)) been carried out from the beginning of the time. However, the cost actually incurred by the controller at time is ce (zz, Uz), which is the cost incurred by following policy pM at time t, for each & t. Thus, there is a mismatch between the loss that GPC-Simples ex is optimizing and the loss that GPC-Simplex needs optimize. This mismatch can be bounded using the stability of mirror descent along with a mixing argument; see Lemma 21.
LazyMD regret. GPC-Simples ex uses LazyMD as its subroutine for mirror descent. The regret of LazyMD can be bounded by standard guarantees; see Corollary 15.
C.1 Preliminaries mirror descent
We begin with some preliminaries regarding mirror descent. Let X' c [Rd be a convex compact set, and let R : X - R be convex function. We consider the Lazy Mirror Descent algorithm LazyMD (also known as Following the Regularized Leader) for online convex optimization on X. Given offline optimization oracle over X, the function R, and parameter 17 > LazyMD chooses each iterate 24 based on the historical loss functions Eg : X - R (for $ E [t - 1] as described in Algorithm 2.
Algorithm 2 LazyMD: Lazy Mirror Descent [35]
Require: Offline convex optimization oracle over set X < Rdd convex regularization function R: X - I;; step size O; loss functions f,....,4y lr where f is revealed after iteration t.
1: for t 1 do
2: Compute and output the solution to the following convex optimization problem:
arg min 2E
vls(z,)) + R(())
(14)
17
3: Receive loss function 4 : X - RR.
The following lemma bounds the regret of LazyMD against the single best 2 E X' (in hindsight), for an appropriately chosen step size n7.
Lemma 10 (Mirror descent). Suppose that X' c Rd is convex and compact, and let |-ll be a norm on Rdd Let R X - R be a 1-strongly convex function with respect to I|-I|- Let L > 0, and let P 2 R(2) min R(2).
Fix an arbitrary sequence of loss functions l, X - R which are each convex and L-Lipschitz with respect to 11. Then the iterates of LazyMD (Eq. (14)) with an optimization oracle over X, regularizer R, step size 7 (LV (Lv2T), and loss functions ei...., lr satisfy:
T Σ
(((2)) - min Σ
(((2) & LV8pT
(15)
15

---

Moreover. for each t [T 11. it holds that
|| Ze+
(16)
27
Lemma 10 is essentially standard but we provide a proof for completeness.
Proof of Lemma 10. By [18, Theorem 5.2], it holds that
I Σ
T
(((z)
min (2) 2e
& 2n Σ [V((())) P
where || ||. TR IR is the dual norm of ||-||, defined by ly] = max a =1 (v, Recall that
convex L-Lipschitz loss function & satisfies [6z(2)]. < L for all = E X. Thus, the above regret bound simplifies to
Σ
((z))
min ((2) & 21 L ZE
"
Substituting in 17 LV2T yields Eq. (15). To establish the movement bound Eq. (16), we argue as follows. Consider any 1/1 1/2 Rd and define, for {1.2),
wi
arg min yr 2) R(2).
26,2'
The definition of wa implies that R(wi) (1/2, w2) + (y2, wi) > R(w2) > R(wi) + (VR((W()))))) w2 -w)>+ 11 wi 1
1
where the second inequality is by I-strong convexity of R. Simplifying, we get
|w w2ll2 (Uz, w1 w2) (VR(w)) u/2
w1). w2>
Symmetrically, the definition of wi together with strong convexity implies that Adding the two above displays gives
|0 w2ll & (U1, uy - wi) + (VR(w2), w1 -W2)
wi ww2l" & (y/2 - Vı wT - w2) + (R(ww) (R(w2), 22 - w,>
1/2 v1ll- | w2l.
where the second inequality uses convexity of R (which gives
(R(w)) - vR(w2), W2) 2 0).
It follows that [w] wal || Vall-- Setting V1 - Vl, (z.) and y/2 7 Vl,(2,), and recalling the definitions of žt, # from Eq. (14), we get
2 z+1l < [1))) nL 2p/T,
as desired.
We next apply Lemma 10 to the domain used in GPC-Simplex. Recall that, given d, H e N and real numbers 0 & a & b 1, we have defined KaH,,a,b := Uetefa.b) Ag x (S "1
Definition 11 (Entropy of sub-distribution). Let d E N. We define the function Ent Ad E20 by
Ent(v) == vf
00 +
Uy
1=1
where for any vector E dd we write 2 :=
Ad 1-1 E R.
16

---

Lemma 12. Let d N and U A Then
(v Ent(u)- V. Eut(v), u- v) & - - uli
That is, Ent(v) is 1-strongly convex A with respect 11-111-
Proof. Let p be the probability mass function on [d + 1] with p; = us for E [d]. and let g be the probability mass function on [d + 1] with p; o for all i [d]. Then it can be checked that
(v Ent(u) V. Ent(t), a) (L(pll (L(g)))
TV (p: q)²
v
where the first inequality is by Pinsker's inequality.
Definition 13 (Regularizer for mirror descent in GPC-Simplex). Let d, H N and 0 & 1. We define Ra, HaB - Rgo as follows (omitting the domain's 's dependence on a, for notational simplicity):
H ΣΣ Ent M
(p Ml.Hl) = EEt((p)
(17)
Definition 14 (Norm for analysis of mirror descent in CPC-Simplex). Let d, H N, and identify Rd+ with Rd x (I We define norm I'lla, on Rd as follows: for R& MD:H] (Rdxd)H,
(p. Jo.MLLHH) = lIpl + Σ Σ
1
h=15-1
Corollary 15. Let H N and <a b Consider an arbitrary sequence of cost functions 4 : Na.H - IR which are convex and L-Lipschitz with respect to ll- Then the iterates zt of LazyMD with 1 = 22HH (n(d)/ regularizer R, and loss functions f,,....ue br satisfy the following regret guarantee:
Σ Cellpe, M(H:H)))
min Ell
Σ E((p, M(2:Hll) /222H In(d) -T
(18)
Moreover, for == 22H In(d)
for all t [T
11. we have
vT
Pt - Pttlll & B,
max kE[H]
M!h
M [+1
B.
(19)
Proof. Note that the set of (p, MIIH)) where p E Rd and M[IM) E (Raxd)" if can be identified with Hdd We apply Lemma 10 with X = NaH R Ra, and the norm l.laa It is
straightforward to check that X' is convex and compact in gd+Hdd By Lemma 12, we have that RIH h is 1-strongly convex with respect to the norm I-la,, Moreover, note that
Ra,H((v (L,((,) M((-)))
Ra, (o, Ml
max k..iiil))xx......
min (D.Miill)exxeee
$ (1+ dH) In(d +1) 1)
< 4dH Indd)
since 0 & Ent(v) & In(d + 1) for all E Ag, Thus, Lemma 10 implies the claimed bounds Eqs. (18) and (19), where to prove Eq. (19) we using the fact that [|C|]-->1 max ||Cri $ / Exetta ||..,l for all C Rdxd
17

---

C.2 Approximation of linear policies
Henceforth fix a simplex LDS C (A, (7ele, (we)e, (ca)e) on A where I Uaelæ 4 for some constants 0 & a x a & 1.
Recall that any choice of parameters (p, M[I:H]) E Kd,Haa.s (for some hyperparameters H E N and @ & a E E @)) induces, via Eq. (8), set of policies (xg. (mg. >etr] The policy rg. takes as input the disturbances We-1...., Wa-H observed at the H time steps before step s, and outputs control for step Recall that, in Algorithm I, we used rx(p, M ur(p, Ml=:Hl) to denote the
state and control time step & one would observe by playing the control m. ay. (W,-1:s- 1:s--1s-111 H)) step 8, for each & & t.
Formally, we have the following expressions for xe Ml..). ue M(I.H)):
Fact 16. For any (p, M(1:Hl) E NaHHHa and L E [T], it holds that
(e Te Ml
Σ P.MMin
Ai-1. (Aesiodes B. B
Σ
A MD]. Wi-in + de,i Wi-i
(20)
11
Ve(p,Muung = mt
(wi-lr-H) X0,0 p Σ
Xr MLil Wz-jj
(21)
P.M
11 i-1 (1- (1-111210 (esg 1.) -11 IIpl1)=-1
where have written, for forte iT] N. oz
Proof. This follows unrolling Eq. (6) with the controls u, == nh m..ASDiMM (wy-1:s- 1:8- H), and recalling the definitions in Eq. (7) and the conventions Wo == I1, = 1, and 0 for t < 0.
In a sense, Algorithm performs online convex optimization over the set of such policies. Even if we manage show that doing so yields good regret guarantee with respect to the class of policies (m. [
(p, M(1:Hl) Xa, for some choices of H, b, why should this imply good regret guarantee with respect to the class K.A (C) of linear policies (see Definition 6)? Lemma 17 bridges this gap, showing that any policy in K (C) can be approximated by a policy of the form (wR. (I:HH
>EfTy--
Lemma 17 (Approximation). Suppose that the cost functions Ci...,, CT of L satisfy Assumption I with Lipschitz parameter L. Fix f > 0, E E (0, 1), and any K* E S such that t (Ax)) & T.
Write a" == ||K" If > 7 (2LT2 then there is some (p, MDI-1) E A.. (S-.)
such that
T Σ
cola, M(IlH,,, velp, M( Σ (olx,(K") <
(22)
where Zel ee(K)), ue(K)) denote the state and control that one would observe at time step t if one were to play according to the policy +> K x at all time steps & & t.
Proof. For each if the controls un are chosen to satisfy ui K -r, then have o || (1 111-11
Moreover, for 1 & & T, we can write
((K) = Σ (AK.)=
- [a----)) w------ Σ Ax Ae.s Wh-in
(23)
u(K*)= K" xx(KK)KK)) Σ K" A Ae.5 Wi-t
(24)
where Ag- was defined in Eq. (5). By the assumption that emix (Ax-) & T, there is some unique p' Ad such that that Ax- p' p' (see Definition 5). Moreover, by our bound on H and
18

---

Lemma 18, for any i > H and q E A we have | 9-k---p' 1/1, & (1/2) < Using that
2i-H41 H+1 A by the definition Eq. (7),
K K' AK 00=- Ae,0 K'p'
K*
Σ
B. m3)
i= H+1
i=#++1
Σ
A
A i-1 Wtii pll, e/(27T)) (25)
(=#+1
For 1 1 i H. let us define MD = K* A
S.. and p == K pl D... Using Eqs. (21)
and (24), we have that
[uc(K*) - (c,, M
K A i-ن k de, A0 Σ
M
K K' K. A, 2 KtY
11
< (2LT
(26)
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 (u)) with |ulll = a" for all i, we can expand Eq. (6) to get
St. Σ (1-aa)
11-a")--1
A A- Bui+ + de,
Thus, for any t E [7], we have
(x((K() - 21 M
(1 a"))-"(xe, A (uL)(())) - un u- (.-(p,.M(imm))
|
2LT
(27)
2LT
By Eqs. (26) and (27) and Assumption 1, it follows that, for each e [T]. (x. M(I:1),, (e(p, MD:l))) -c(ax ue (K(K)) & E/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 gd have unique stationary distribution Then the following inequalities hold for any c, t N:
1. (t) & (x & 2Dx(t).
2. (x(ct) & (x)
C.3 Bounding the memory mismatch error
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 defined on Line 9 of Algorithm I in fact has bounded aggregate cost with respect to the cost functions e chosen by the adversary.
First, we introduce two useful lemmas on the mixing time of matrices (Definition 5).
Lemma 19. Let Sd have a unique stationary distribution. Let Y E Sd satisfy || Ylh Then for any 1. E N,
Dy & 2t8 + 2Dx
19

---

Proof. For any v E A", we have | Yull < 6. A hybrid argument then yields that for any >> 1,
||''v vl1 < tô. Then
Dy(1) & sup
IY' - 0)1 & 210 + sup
(p +)1 < 218 + Dx(1)= & 21 + 2Dx(1),
P.geAd
P.gE
where the first and last inequalities apply the first item of Lemma 18.
Lemma 20. Suppose that A, Be 84, K S satisfy ymix > 4 mmmim (muxx)))))) Then |K I| || 1/(96- tmix (Axx)))))
Proof. Let us write == ( and a' |K* 1-1 that Ax. (1 a²) A BK* Suppose for the purpose of contradiction that a" & 1/(96)). We have that ||A Ax 1 E 20". By Lemma 18 and Definition 5, we have Dax-(1 (T) & 2Dxx= (r) & 1/2, so Dākr (47) &
D Dan- (4r) & 1/16. Using Lemma 19 and the assumption on a²,
Da(4F) 12Ta" + +2Da (4r) 127a" + 1/8 1/4.
meaning that (Ai < 4r.
The last step bound the memory mismatch error.
Lemma 21 (Memory mismatch error). Suppose that (ci), satisfy Assumption I with Lipschitz parameter L. Let T, O, and suppose that KG( is nonempty. Consider the execution of GPC-Simplex (Algorithm 1) on L with imput t. If the iterates (pt, M M(L:H) ) satisfy
lp.. P4rlh &
max ic[M]
M
M
< B.
(28)
then for each e [T, the loss function & computed at time step satisfies
[e(( M(l.Hl) cx u.) 0 (lg (1/3))
Proof. Recall that u, E A denotes the control chosen in step t of Algorithm 1. We write a; := |14l
for each h [H]. by and, for e [t]. ag, : IT;=1 (1 ae-z)) Note that a₁ = [pee] 1 = M 1-1
definition of Hd.H.a..T.
Let us fix t E [2] and write == Pr, M == M! M By Eq. (6), the state I, at step t of Algorithm can be written as follows:
H (b B
Σ M Ae w-5-- + Se,2ere )
F1 ars 1--1
(29)
By assumption that KC (C) is nonempty, there is some K* Sd ((am) satisfying tmix (Ak.) & Let us write a" := | 1- so that Ag (1 a²) BK Moreover, recall we have written in Algorithm that тд == mix (A)).
For & i & L, define
H
04 == Ao- B
Σ
M Ar Wi-1s + W
Ar Bp + B Σ MDl A N
Note that
"
max([lus/12 1|44/1, |1 - of & de-adde + Σ
Aesty + Ae, &
(30)
20

---

Next, using Eq. (29) and Eq. (20), we have
Tt selp, M
(an: A 0s 12
P.M
A1-1.1() vl).
(31)
The condition Eq. (28) together with the triangle incquality gives that [Bp-s - Bpll < i and
BB - BM 1 < i3 for all i,j 2 1, as well as lar- - aul < i for all > 1.
It follows that llus - vill, < iB and lak,s - a E,
m 1 for all i t and that for any é E> 1,
4
Σ a |eall1 - Σ
dii
p.Mruum 11%
<
Σ
att
D.M d43
- -llssli
+ Σ
|/1 rfil
<
B.
(32)
Using Eq. (32) and the fact that Σ ozei |11/111
Ei
D.rrlu
|1//1 1, we see
|usl
Σ
$ BB.
(33)
1+++1
1-t+1
We consider the following two cases:
Case 1: TA & 4T. Write to = ITA (1//(1 Let the stationary distribution of A be denoted
p" Ad. By Lemma 18, we have that for all i > 1, | p p--''l, & Da(i) & 1/21:/Tal. Now, using Eq. (31), we may compute
2t- zz 11 M
Onti A'-1 us 02
M
A Aa-1. od))
agsi' (A--1 oz- - -lu:l1 p²)
p.M
(A--1. 2/6 -1o0l DD)
k=t++1
+
Σ
Ori . |eelll p² of | p-
i
to
| -22--1))) + +laes Lis 1- -11o(11))
Σ
(or |1it, 1s 1.- --lalll p'1,, + ag. p.M.
a|a of 1 -11//1, -1'1.)) + +23
+
i-to+1
to
< 8 +
233 +
ard iB +
Σ i-1+to
2 2/1/////Tl
$ C
(34)
& C' log (1/8) 8,
for some universal constants C, C.. Above, the first inequality uses the triangle inequality, the second inequality uses Eq. (33), and the third inequality uses that ||0; o/ 1 & i,3 Jar,s - of p.
$ 12
|u// & 1. The fourth inequality uses the bound Ei= 2 14/7l < 0((A3)) < O(to8)).
Case 2: > 4T. In this case, we claim that Qn > 1/(96r). By choice of ag in Line of Algorithm and the fact that TA > 4r, suffices to show that a > 1/(96r): to see this, note that TA (m)) > 4T 2 4. (Axx.) ). so Lemma 20 gives that | > 1/(96 mmxx (Axx)) )) > 1/(967). But || 1K111-, 111-11 & a, and thus a > 1/(967). This proves that ag > 1/(96T). Hence 04 00 > 1/(967), ), by definition of XH a. for all [T].
21

---

Write to == |200T log(1/8)]. Then for any i i> to.
max
2
p.M a0)-=1
= 1/(967)) (1006)))1000100011)333 x 0(3).
Again using Eq. (31),
It - (....M
10
|at
P.M(L:M Og3
+ * ||0, 11u1 |lus-v(l))) + Σ
(at og
)
1=to+1
Σ 0(3) (1- (1-a)) a0)=-to-
(35)
i-to+1
< Ct + C3/00
c 7 (1/3)
for constants C. Above, the first inequality uses Eq. (30); the second inequality uses the p.M(L.
previously derived bounds |att - 0, uses that (g 1/(96r).
< B and ||e - 2/ < i8; and the final inequality
In both cases, we have ||ara - (p, M(I:H)), & &o'r3Blog (1/8) for some universal constant C². By definition, the control u, chosen by Algorithm at time step / is exactly u, ut(p, M(.:H)). Thus, using T-LLipschizzness of ct, we have
Ml. ce(x,, un) = (x( Mlll(),, (P. ue(p, MDHH)) - ca(xs, uo)
< L - xt se M(
C L log (1/3).
as desired.
C.4 Proof of Theorem
Before proving Theorem establish that the loss functions & used in GPC-Simplex are Lipschitz.
Lemma 22. Let X 3d with == = (x) co. Then for any i E N and Rd with (1, b) 0,
holds that X $ 2 2-/r |0|1-
Proof. Fix Rd with (1, O. We can write v x v. where ut v- Rgg the non-negative and negative components of respectively. We have | || ||0_1 | since
(1, v) = 0. Let un := 20 / and u2 = 2u a0=//v/l, so that un, u2 E Ad, By Lemma and the definition of mmix we have
[X - u2)11 & Dx(i)= & (x & (2Dx
< 11/1l
Thus, |XTu|l 2 2-
Lemma 23 (Lipschitzness of l.). Let 7 0, and suppose that KA is nonempty. For each te [T], the loss function (p M[:H1) ca (2 MD-H),,
(I(LI), ue(p Mi:Hfl (as defined on Line 9 of
Algorithm 1) is
with respect to the norm Il a in Na
Proof. By L-Lipschitzness of & with respect to 1.1 it suffices to show that for any
(pi, M(llH), (p2,, Mfll e ar we have
xy (e(p Mitii 1e(p2 M,! |//m
< 0((}) |1p (((1i - (p2, Mr! (.
(36)
1.H
((rr,MMittt (itllll u (pz, M! [(:
< {({?) |0I, (p2, M1. M
(37)
d,H
22

---

Fix (pi, M,I:t!) (p2, M E a. and write
e:= max {
[PI
p2ll
max
MD
Mb/1
je(m]
1
Since & (pn, Ml - (p2, Mb.
it suffices show that Eqs. (36) and (37) hold with d.H
on the right-hand sides.
To verify Eq. (36) this manner, we define, for E {1,2),
H
0/bb :=>o-oo B.ps pb + B
Σ j-1
A MD11 Wi-i-s + Xo, Wi-i
Since A,, + Ar, + -3-1 At.ts & we have |1p,ll1 & for each [4].b e {1, Moreover, || 01,211 & (Ai- + Σド= )1.-))) E E E. Write 01
== |p 1 so
that |0 - 02| < E and [1 - ) - (1 - 02)"l & ie for all i > 1. Also note that for each b E {1,2),
(1 σb) 1- |1r,011 = Σ (1 - 01)²² 1'1 A . ((1 - 7--)) ob + )--)
Σ (1 (1-ov)) 01)² 1-11 - (1 (1 7-1)(11 -0)1)--)))))--)))))0)))))())))))
(38)
where the final equality follows since 7ao 1.
By Eq. (20), we have
(r(p,, (((Ht, M(HHHt 1x(p2, MP, |1 Σ (1--0))-' U1,1 (1 -00))=11111 1 ...2)
We consider two cases, depending on the mixing time TA := mmx((A of A:
Case 1: TA & 4T. Let the stationary distribution of be denoted p" A Then
[elp,, ( x x1 M
(1:
Σ ((1 01)²²1111 A'-
02)" - 0122)
Σ ((1 "''''''''-- 'AA'-'e.1 0,1 - 11 p²) - -1A'-((A'-11))) U122 l02el1
+ Σ ((1 .o 1 ||r 02)² 1-1 ||0,2211) p²
1
Σ 1- ((1 σ1) 1- 21 - (1 02)--1122 v2,2 - ((1 - 01)²=1 1- ||
- (1 -
(1-62)²= o2)²=1 |1, p"
2
11 211111-
1)/Tal [| - 01)² -
U1,1 - (1 o2) i- 11 - ((1 - 0z)² 6 |,, - (1 - o2)²² '11 |1 p"1,
Σ 22 1(1-1)/7al 6)
& CTA Σ T4
1-0
< C'
23

---

for some constants C, C", Above, the second equality uses Eq. (38), and the second inequality uses Lemma 22 together with the fact that A'- p' p" and
{1, ((1 - -1) o 0111 (1 - -2)"-1u.p)) - ((1 (1)- "1 |,, (1 o2) ---=-=--101 11122111)) - O.
The final inequality uses the assumption that тл $ 4T.
Case 2: TA > 4r. In this case, the assumption that KC, (C) is nonempty together with the choice of do in Line I of Algorithm and Lemma 20 gives that ag 1/(967). See Case 2 of the proof of Lemma 21 for more details of this argument, which uses the fact that > 96T.
Since (pb. Mf
Na for b E (1, we have 01, 02 2 > 1/(96r). We may compute ar (pt, Ml (22, M₁ M
Σ (11 - U1 (1 - 61 1
12) 1;,)
(11 (1) )1) - (1 - (1-02)* - +
(1 01)
1-1
|0:.1 - 0122
01 02 -1-1 1 (1 02)
1- 1 + 3 o1) 1-1
(i- - 1)=(1 1/(96))) + Σ (1 1/(96T))
1-2
& C
for some constant C.
Thus, in both cases above, we have selpi, M(litt)) x. (1 M M(
< O(Te), which verifies
Eq. (36).
The proof of Eq. (37) is much simpler: we have
/ M(liHt) ue(p2, MM
||
Aeo [Pi p2ll1 + Σ
Xe.
MM
M 1_ E
j=1
since Xτ,0 + AI, 1.
Proof of Theorem 7. Set B Ind = 1/T, and K.. (C). We will apply Corollary 15 /T
to the sequence of iterates (pt, M(=:HI produced in Algorithm 1, for the domain Na.H..o..a (i.e., ag, σ). Note that Lemma 23 gives that & is Lipssi-i for each e [Z']. Thus Corollary 15 guarantees a regret bound (with respect to Xd. of 2 In(d)T). More- over, Eq. (19) of Corollary 15 ensures that the precondition Eq. (28) of Lemma 21 is satisfied. Thus, we may bound
Ca (1 me)
inf KeKA
Σ ()))(())
T Σ (x(x((() + O(T - (1/3)))
(pe, MM (1:01]]]
inf Keka
T Σ (((rlp.MMMn)) ui(p, u(p.MMl..M ((ll(ii
lp M M! [2:
inf
(39)
(p.M a.
+ O(T L Log logg (1/3))3 +
T
T Σ (p, (D, MI1:Hl
li M.! [.uHH1]
inf X
(40)
24

---

+ + LITT-LT'MA log' (1/3)8) +E
L VdH + O(T L (1/3)8))
where the first inequality uses Lemma 21 together with Eq. (19) of Corollary 15, and the sec- ond inequality uses Lemma 17 with
1/T (by the theorem assumption, the inequality H > > (2TT%))) is indeed satisfied). Note that for the second inequality to hold, we also need that ||]]| 2 for all K E Kř, which in particular requires (by Line 1) that [| > 1/ if (AA) > 4T. But if t (mix(A) > 4T, then for any K e K2 we have (A) > 4. + and hence | 1-11 2 1967) by Lemma 20. Finally, the equality above uses the definition of & in Algorithm 1, and the final inequality uses the regret bound of Corollary 15. By our choice of [, c, we
see that the overall policy regret is O(L77/2d /2222///TT as desired.
D Proof of Lower Bounds
In this section, we formally state and prove the regret lower bounds Theorem 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" C 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 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 high-cost state at time T/2 + 1, must be unable to reach a low-cost state without incurring (T() total cost along the way. In the standard LDS setting, we achieve this by setting the transition matrices A, B so that B = O(1/T) (i.e. so constant-size controls have small effect on the state) and adding a penalty of |uy] to the cost fort brt>> > T/2. In the simplex LDS setting, we achieve this by our choice of the valid constraint set I (which enforces that |well O(1/T) for all t).
See Fig. 3 for pictorial explanation of the proof in the simplex LDS setting.
D.1 Proof of Theorem
In this section we give formal statement and proof of Theorem 1. Recall the definition of an LDS (Definition 9). We define the class (C) of policies that k-marginally stabilize L below; is equivalent to the class (C) of policies that (1s, p) -ttronyyyy stabilize L (Definition 4) with p 0.
Definition 24 (Marginal stabilization). A matrix M Rdxd is s-marginally stable if there is matrix H E Rdxd so that - M H|| k-marginally stabilize an LDS with transition matrices A, B E Rdddd if A BK is k-marginally stable. For k 0 and an LDS L on Rd, we define (C) to be the set linear, time-invariant policies x Kz where K E dddd k-marginally stabilizes L.
< 1 and || [ H < K. A matrix K E Rdxd is said to
We also introduce a standard regularity assumption on cost functions: 15
Assumption 2. Let L > O. We say that cost functions (ct),. where c : Rdz x Rdd R, are L-regular if ct is convex and L-Lipschitz with respect to the Euclidean norm for all
Theorem 25 (Formal statement of Theorem 1). Let Alg be any randomized algorithm for online control with the following guarantee:
Teeehnical,y this setting of general LDSs where the state domain is unbounded, Assumption I stronger than the assumption on cost functions made in prior work on non non-stoce 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.
25

---

S
5g
1/2
T/2
Figure An intuitive illustration of (2) in lower bound simplex LDS (Theorem 30). The blue curve the trajectory of n,, the "decreasing" comparator policy, in the system C which has the smaller perturbation. The green curve is r², the "lazy" comparator policy, in the system C², which has the larger perturbation. The orange curves correspond to the trajectories of arbitrary policy under the two different perturbation sequenees. The sum regret under the perturbation sequences is equal to the S S2 Ss, which shown be (TT for any
Let d N and > O, and let C. (A, B1, (wi),, (c()) be an LDS with slute space and control space Redd T--regllar cost functions (ct), (Assumption 2); and perturbations (wi): satisfying [[elll & L. for all Then the iterates (It, (A, B, K. T) on interaction with L satisfy
(Rt, uz) produced by Alg with input
regretx.(0) E
Σ ca( un)
inf (EK.,(C)
Σ
C.K .u Cala
C.K.) & ((d,k,
(41)
where (I. C.K L.K J. )T_ are the iterates produced by following policy x - K in system & for
ut.
all t [T].
Then 111,1,1,7) = S(T).
Remark 26. In the above theorem statement, if KC((C) were replaced with (C), the class of
linear Lime-invarian policies that (x., p) -tstooggyy stabilize L, then the main result of [1] would imply that in fact there is a (deterministic) algorithm GPC with regret at most poly(d, L, --1) log(T") on any LDS L satisfying the above conditions. Thus, Theorem 25 indeed provides converse to [1].
We prove Theorem 25 by constructing simple distribution over LDSs on which any algorithm must incur Q(T') regret expectation. Let > constant that we will determine later, and fix > 3. Recall that denote an LDS on Rd using the notation L (A, B, x1, (we),, (c:)t). where
A, B e Raxd We define two LDSs IR: follows:
_ = (1, (1.-3/T,ax (w (ce))),
C (1, BB/,, I1, (w) ). (c)).,
where the (common) initial state is = 1, the (common) cost functions (ca), are defined as
[2] |u|
if T/2 otherwise
Ce (x u)
0
26

---

the perturbations of _ are wi == for all and the perturbations of L' are
[-1
if T/2 otherwise
0
For simplicity, we assume that T/2 is an integer. Thus, at all times T/2. the two systems have identical dynamics
I++1 Zt Uc.
but at time = T/2, system L experiences a negative perturbation of magnitude 1, whereas L does not. The following lemma characterizes the performance of two time-invariant linear policies n² for _ C respectively:
Lemma 27. Define n. x² : by x (x)) = x and n (x) Fx 2 x Yi- produced by follow-
Then:
Policy T² is element of KC (E"), and the iterates (x,
th
ing x system L satisfy
Σ
(x
C 1000
1x0
2T
8/2
"i
Policy n² is element Kr (f'), and the iterates ing x² in system L satisfy
x² U4
L. xx TT produced by follow-
T x
Σ
ca (
Proof. Note that x0, T² are both time-invariant linear policies. The inclusion x0 Kg((C)) is
immediate from the fact that L has transitions A = B, = -//T, and |A + B & 1. Similarly,
x² (C*) because |A| & 1. To bound the total cost of T on 2 note that up (1 - 3/T)* for all to E [T]. Hence,
c .
c
It
Σ cz
10 -0 (======
)= 22 Σ
1
2T
8
T/2
2T
8/2
T
3
(-7/2+1
Moreover, we have C 1 = 1[1 < T/2] and ut c
= 0 for all / [T]. from which it clear that
ΣT (1 Ct. Ct.
=0
Next, we show that the total cost of any trajectory (It, ue) can be lower bounded in terms of [#T/2+1l in both 6 and L!:
Lemma 28. Let Alg be any randomized algorithm for online control, and let b 10, The (random) trajectory (Zz, u,)l_ produced by Alg in system Lh satisfies the inequality
()) =
Σ
T
|2al + |uel
2
T
23
1-7/2+1
with probability 1.
Proof. By definition of _ ,²,,,, any valid trajectory in L satisfies |vel
T
g - Fyl for all
B
T/2 < L < T. We consider two cases:
1. If minry [x]| > 1 then
Σ
T
|oo| + luel 2
T
|4T/2+1| >
233 1T//241
T
4
t- T/2+1
since 8>2 2.
27

---

2. If min7/221e7
|2 < 2 1
then
Σ +
T
Σ
T
T
11++1-20
2
2T/2+1|
min T/2c1E
2r/2+1
B 1-1/2+1
2
1-722+1
by the triangle inequality.
In both cases the claimed inequality holds.
We can now prove Theorem 25.
Proof of Theorem 25. Let b Uni 1J) be unbiased random bit, and let (æx, ue){=1 be the (random) trajectory produced by executing Alg on L.. On the one hand, by Eq. (41) applied to L and C), we have
T Σ
cl(o, un)
T
T
f11,1,1TT) +
inf (C))
Σ
calar
C.K
uu
inf (C))(
Σ
cl(
L
T
f(L, -9/2
(42)
where the first inequality uses the fact that cost functions (c)) are convex and 1-Lipschitz and that kell, w & 1 for all [T]: and the second inequality is by Lemma 27. On the other hand, by Lemma 28, we have
T
E
Σ
c (1r un)
>
El
TT/2+11
233
T
T2
WT/2 -
2,3
T
(+)
T
3
B
-
1
=11
E
IT/2
u2
E
TT/2
ur/2
28
T
2
T
T
B
-
11)
E
TT/22
T wry2
+
E
2T/2
T
ury2
(43)
43
4,3
where the key equality (+) uses the fact that L L are identical up until and including time T/2, and hence (IT/2, ury2) is independent of b. Comparing Eq. (43) with Eq, (42) yields that
T
T
f(1,1,1,7)
8/2 = (TT)
43
3
for any sufficiently large constant B.
D.2 Proof of Theorem
Definition 29. Let 0 & a a a < and let I = Uaela Ad. We define KC(T) to be the set of linear, time-invariant policies x ~ Kr where Une(ar)) st.
Theorem 30 (Formal statement Theorem 8). Let Alg be any randomized algorithm for online control with the following guarantee:
N and I (A, B,I,II, (1t),, (we),, (c:):) be simplex LDS with state space Ad and cost functions (Ct)t satisfying Assumption 1 with Lipschitz parameter L > 0. Then the iterates (ær, u))z produced by Alg with input (A, B, I,, T) interaction with L satisfy
Let d.T
Unejo A for some
(0,1). Let L
T
ca (0 un) - inf Σ
T
regret := E E
Σ
ca(x
C.K
.4
C.K & f(d, (44)
Kek(())
28

---

where (xt C.K 1 24
DT= are the iterates produced by following policy x: - Kx in system L for
all [T].
For any sufficiently large constant B, if we define ((T) : B/T, then f(1,1,a(T),7) - (((T).
We define two simplex LDSs A as follows:
_ == (I2, 12, I, Iı, (7t)e: (.))).()))))
C = (12, I, 31, (7t)e: (w,) (c+)))
where IR222 is the identity matrix, the (common) valid control set is I (ne A the (common) initial state is 21 = (0, 1), the (common) cost functions (ct) are defined as
c( u) = (0 (x(2) 1/2| 0
if ff2 otherwise
the (common) perturbation strengths are % == 1 T/2], and the perturbations of L are w :- (1/2, for all i whereas the perturbations of L are wi == (1,0) for all t. Thus, for both systems, the dynamics are described by
T++1 = (1 (1-114 (uell))))) + +
for all * T/2.
Lemma 31. Define n² x² Then x., ,x K((I), and:
A Uae|o.1) A by (x) = 11/2.11/2 and x ('()) = (0,0).
The iterates (xt x0
n0 )T=1 produced by following TO in system _ satisfy
Ut
Σ cal ,"
T
Ue e -/2_
c 5² &
T
g0-1/2
B
The iterates (at (af'."
x
Yt-1 produced by following nt in system L satisfy
Σ ca Up
Cl
Proof. The fact that n", x² E KI(I is immediate from Definition 29 and the choice of I. To bound _
the total cost of T C note that F++1 (2) 1/2 (1- (z.) 1/2) for all t * T/2, and
c =
(2) 1/2 (1/2)(1 (z.) 1/2) for t T/2. Thus,
T Σ ca
1 x00 o
Σ
1 x= (2) (2) 1/2/ <
Σ (1-
T
T & --/2
B
t-T/2+1
t-T/241
Moreover, we have L' x
10 for all L & T/2 and ui .²
(1/2,1/2) for all l. 7/2, so
indeed Σ colæe
m² 0 as claimed.
Lemma 32. Let Alg be any randomized algorithm for online control, and let {0,1). The (random) trajectory (æz, ut)T produced by Alg in system C satisfies the inequality
Σ c((
Σ t=T/241
(x.(2) 1/2|
T 83
(
1/2/2 1.
Proof. By definition of L C and the valid control set I. any valid trajectory in Lb satisfies ||, - -1-1/11 & 2 |ul1 & 23/T for all T/2 < T. follows that [2141(2) 1/2) (xx(2)
1/2| - 2//TT for all such f, and hence
7/2
Σ T-72441
(x(2)) - 1/21 >
Σ
max 0, (0/12)2+112) 11/2
2,8
T
29

---

1T/2+1(2) - 1/2]
T (r)2++1222) - 1/2)
433
T
TT/2+1 (2) -2)-1 11
as claimed.
Proof of Theorem 30. Let b Unif([0, 13) be an unbiased random bit, and let (æt, uz){_1 be the (random) trajectory produced by executing Alg L On the one hand, by Eq. (44) applied to c and L² we have
T Σ
Ce (Te, un)
E
T
T .u(
< (1,,1,8/T111 +
inf KeK(I)
Σ
calar
K
u2 + inf (E
Σ
Calof
K , ue
T
11,,1,87,,7
8/2
(45)
233
where the first inequality uses the definition of I and the fact that the cost functions (c)); are convex and 1-Lipschitz per Assumption 1; and the second inequality by Lemma 31. On the other hand, by Lemma 32, we have
1 + E Σ
ce (x u.)
T EI (20)2++1 (2) - 112)²]
83
27
T
WT/22 (1 )x112((2) + (2)
1 b
E
83
T
| (2T)/2(2) + 22)
1
(1 UTT22 )xT(2(2)) uT/2
E
E
88
2
4
T
(1
uT/22l (2) + (2)
1
(1
uT/2 )0TT2((2 + 22/2(2)
1
E
+
E
16,3
2
4
2
2
T
(46)
10243'
where the key equality (+) uses the fact that _ _² are identical up until and including time T/2, and hence (IT/2, uT/2) is independent of b. Comparing Eq. (46) with Eq. (45) yields that
T
T
1/L,,, 10243
8/2 ((T)
23
for any sufficiently large constant B.
E Implementation details
In this section we describe the version of GPC-Simplex (Algorithm 1) implemented for our experi- ments. First, the dynamical systems in experiments non-linear. The GPC-Simplex: algorithm still practical and applicable in such settings concretely, any setting with update rule Eq. (9) but of course several madiffatiion//eeenniiiziinos must be made:
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 (1 ||uel] Axx, Buc
30

---

(which exactly corresponds to the noiseless update rule in simplex LDS) is replaced by f (Iz, ut). Moreover, in Line 9, the hypothetical iterates 2 (p, M(I:))),, up M M under policy TP.M are computed using the update rule f.
2. The algorithm directly takes as input a learning rate for the mirror descent subroutine, rather than the mixing time bound т. In our experiments, we always set 1) v HH (22H))(2T)
3. We always parametrize our systems so that the valid control set the space of distributions
A Hence, the domain used for mirror descent is Xa, H.I.I. Mirror descent is implemented by exponential weights updates with learning rate 7) and uniform initialization.
We remark that the above (natural) modifications to GPO-Simplex are analogous to the modifications to GPC made by [2] to perform online control for nonlinear systems.
F Experiments: Controlled SIR model
In this section, we provide additional experiments in the controlled SIR model. Specifically, in Appendix F.1 we provide experimental evaluations when there are perturbations to the system (i.e. Y not always 0 in Eq. (9)). In Appendix F.2 we vary the parameters of the SIR model.
F.1 Control in presence of perturbations
We experiment with the SIR system Eq. (11) with the following parameters:
0.5, 0.03, & 0.005,
and cost function given by:
Ce (Tt, u+) = c3 x2) 02 24 (1)
We test the performance of our algorithm on (e2, c3) ) = (1. 5). In addition, we add perturbation sequence w [0, 1, OJ. V1 & & 200. Tt ~ 0.01 Ber(O.2), V1 < & 200.
Fig. 4 shows comparison of the costs over T = 200 time steps incurred by GPC-simplex to that of always executing " [1, 0] (full prevention) and that of always executing " [0. (no prevention). In addition to cost, we plot the value of uz(2) over time, representing how relaxed prevention measure evolves over time according GPC-simplex
F22 Alternative parameter settings
We experiment with two SIR systems with different set parameters. The first uses the following parameters:
= 0.5, 0.03, & = 0.005,
whereas the second uses the following parameters:
β 0.3, 0 0.05, & = 0.001.
In both cases, the cost function is:
cx u.) c3 (2)
2 02 x (1)u
For both experiments, we test the performance of our algorithm on different choices of parameters for the cost function. In particular, test the parameter tuples:
(c2,c3) E {(1, 20), (1, 10), (1,5), (1,1)}:
Figs. and 6 show comparison of the costs over T = 200 time steps incurred by GPC-Simplex to that of always executing de [1. 0] (full prevention) and that of always executing u, [0, (no prevention). Specifically, Fig. 5 uses the first set of parameters above, and Fig. uses the second set. In addition to cost, we plot the value of (2) over time, representing how the effective transmission rate evolves over time according to GPC-Simplex.
We notice that our algorithm consistently outperforms the two baselines. No matter how we set the parameters, our algorithm will outperform the full-intervention baseline since its cumulative cost grows linearly with time. As c3 gets larger, the gap between our algorithm and the no-intervention baseline becomes smaller, since the optimal policy with high cost on control is basically playing no control.
31

---

Time. f=0.50, 9w0.03, 5-0.005, cyml,
uf2) Over Time, f000.50, 8=0.03, $=0.005, f=0.005.
1.0
provertend
2.5
2.0
0.4
0.5
0.2
W/W
0.0
25
100
130
175
200
25
100
125
150
175
200
Step
Time Step
Time, $w0.50, 8w0.03, fw0.005, c,m1, Cym5
u121 Over Time, f800.50, 50,00 8m0.03, E=0. Cym5
1.0
3.0
2.5
0.8
3.5
0.0
325
350
200
Step
Step
Figure 4: SIR with perturbations. = 200. Initial state x (0.9, GPC-Simplex parameter H 5.
Top: Perturbation sequence: w, L. 0J. A1 & & 200. 7. 0.01 Ber & 200. Bottom: Perturbation sequence: VI, we is a normalized uniform random vector. 7 0.01, v1 & / 200.
G Experiments: Controlling hospital flows
In this section, we provide more details regarding the setup and experiments Section 4.1.
The continuous time dynamical system considered by [27] is the following: let S(t), 7(t) denote the susceptible and infected fraction of the population time t, and let att) denote the control time t. The system has some initial state (S(0), (()) in the set
D { yo) zo yo 0, + 90 & 1),
reflecting the constraint that S(0), 7(0) represent disjoint proportions of population, and the system evolves according to the differential equation
S'(t) (t))
(47)
r'(1) -00)(((())) 7I(()-
(48)
where 7 0 is some fixed model parameter, and the control o(t) models non-pharmaceutical intervention (NPI) inducing a time-dependent reproduction number (t) [0, oo). where op is the base reproduction number the absence of interventions. In most examples in [27], including the
example of controlling hospital flows, the parameter settings ou = 3 and = 0.1 are used. This means that the natural discretization of Eq. (48) is in fact equivalent Eq. (11) with transmission
rate B : y00p 0.3, recovery rate = 0.1, foss-of-immuuity rate = 0. no perturbations (i.c. Yt. for all t), and control
U4 = (1 o(t) (tt)
at each time t.
32

---

Core Time, FudSq AuD S4f bal Au00
Curciation Cat Over TIMA, 3-653 0-0.0, (0..85.col..
4221 Over Time, Pro d:o (-8.00.cchl...kk
312
condicio proprtee
0--
044
10W
100
15
Dost Over Time. 50r500 did 05. (nd 003, cyrl c
Caroulatve Card Over Time, Pii Ovd Evo 995 c
0221 Over Time, fled dwdid. (-d 003 (pm), cy10
10
115
7096
Time. Ju0 Bwd E40 G-1 C.05
Caraibike Card Over Time 50.0, 0ud 200 m203.
UC21 Over Time, Ba0 Bedd3, (ed $05.00 c.
2.5
125
540 6ud Exil
Gumalatioe Cott Ouer St, Sud Eu0.605 (wll.cu)
Time, dub00. Eud
130
Teme 2re
10000
Figure 5: Control with control over 200 steps. "t 0, VL. SIR parameters: 0.03, < 0.005. Initial state x1 [0.9, 0.1,0). sic-Simplex parameters: H 5. Left: instantaneous cost over time, compared with that of no control (green) and full control (orange). Middle: cumulative cost over time. Right: u. (2) output by CPC-Simplex over time. (Ca, Ca) values (from top to bottom rows): (1, (0, 10), 51, (1,
0.5,
The goal in [27] is the following: given an initial state (S(O), along with a horizon length >> 0 and the parameters listed above, choose admissible control function [0, 7] [0, to minimize the loss
J: -==-) + T(S()),()),
where I(S(t), I(t), (t)) is the instantaneous cost at time t, and the extra term (S(T), ((T), do) incentivizes the state the system time T to lead a favorable long-term trajectory the absence of any interventions after time T). In [27], the following formula for S., is given; see that paper for further discussion:
(S, I, 0g) = Wo op Te (o(()1)))
du
33

---

Cast Time. deoi twidd, Sat G
Damulldee Carl. Over Time, JHN Pn (-0.000..)))..000
4521 Over Time, Fudt 5-0.000 Gell
15
Trme
Dee Time. faid 3t, Bed Sa6.033 Cy-10
Gurralativn Cart Over Timee Su Be0.55 Eud 600, owll.dvel8
Over Time. pi6.33
Cradd
3.
100
Timee Fud 000, (all,
Conulative Cost Ove Time, Bob. 30, Bad 05, E-d 1e5.001, Owd. Cv05
422 Ovar fime. flgg 10.30 $w0.0 (-0.001 60.0..c-....e
14
Cosl Time, 3h0.30 tnd.05 E-0.001, 0or1.o0
Carsdative Dest [-0 6r1.
100
1.0
0.6
1:54
8
0.1
0.0
130
Figure 6: Control with control over 200 steps. "t 0, VL. SIR parameters: B 0.3, 0.05, c 0.001. Initial state 21 [0.9, 0.1,0]. XPC-Simplex parameters: H 5. Left: instantancous cost over time, compared with that of no control (green) and full control (orange). Middle: cumulative cost over time. Right: u. (2) output by CPC-Simplex over time. (Ca, Ca) values (from top to bottom rows): (1, (1, (1,
The instantaneous cost is modeled by [27] as follows:
σp (1-
o(t)
C3 (((t) Fmax) 1 e 100( Mymsx)))))))))
1()()))()) c2
where C2, Cy are some parameters determining the cost of preventing disease transmission and the cost of medical surge (i.e. when the proportion of infected individuals exceeds Vmux)). Notice that the second term above will indeed be very small magnitude unless I(t) exceeds ymax-
Note that GPC-Simplex cannot directly handle end-of-trajectrry losses such as the term (S((S) I(T)) go). Thus, our evaluation of GPC-Simplex on this system, we instead incor- porate See into the instantancous cost functions. Concretely, we use the following cost function at
34

---

time t:
ca(x)12) 1/max)
c,( = - 0n) + + ur(1)² -2--u((1)
+ e- 100((=(2))-(p))) -mmx))
Recall that we write 2; = (St, 4, R₂) and ue (1) = = o(1)/oo so modulo the addition of S.x to all times < T and the conversion from continuous time to discrete time, our loss is analogous to that of [27].
H Experiments: Controlled replicator dynamics
The replicator equation is basic model in evolutionary game theory that describes how individuals in population will update their strategies over time based on their payoffs from repeatedly playing game with random opponents from the population [11]. The basic principle is that strategies (or traits) that perform better than average in given environment will, over time, increase 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 Raxd A population at time is modelled by the proportion of individuals that currently favor each strategy, and thus can be summarized by distribution axt)) I The fitness of an individual playing strategy [d] in population with strategy distribution A is defined to be
fitness M_. (1) = c. Mx.
where e, E Rd is the indicator vector for strategy i. That is, fitness is simply the expected payoff of playing strategy against random individual from the population. The replicator dynamics posit that the population's 's distribution over strategies x(t) will evolve according to the following differential equation:
dr,(()) = xt) (i finesss xx(() (c. Mx(t) x(t) Mx(()).
dt
(49)
straightforward to check that this differential equation preserves the invariant that xxt) is distribution. This equation induce various types of dynamics depending the initialization and payoff matrix M: the distribution may converge to an equilibrium, or may cycle, or it may even exhibit chaotic behavior [1]]. In this study focus simple (time-dicrretized) replicator equation namely, the equation induced by a generalized Kock-PPaper-ccissors game when the payoffs may be controlled.
Controlled Pack--aape--eeisoors. matrix
The standard Rock-Paper-Seissonn game has d = 3 and payoff
0
1
-1 11
M =
-
0
-1
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, the payoff matrix now
U1
U3
(u))
=
U1
0
U3
U2
for control vector u 33, The discrete-time analogue of the replicator equation with this controlled payoff matrix ((u) is
Je1 e_ M( )z
Z1+1 = f(z,, uz) = De + 17
J12 e, Muu )
(50)
Fes C3 M M(u)
where Ft, U, E 3 are the population distribution and control at time t respectively, and r7 (0. 1) the rate evolution. Note that the term æ;, M (M,((),) (u,)æ, does not need to appear Eq. (50) because M ((u) is always zero-sum. Also, since 7) & 1 and all entries of M (u,) are at most in magnitude, if J, is a distribution then #++1 will remain distribution. We omit noise in this study, so Eq. (50) is special case of Eq. (9) with N 0 for all t.
35

---

Comperison over
Population evolution with GPC-Siimplex
1.0
Know 3F1
0.10
0.8
0.0
0.4
0.04
0.2
0.02
0.0
0
20
40
60
80
100
20
40
60
90
100
Time Step
Time Step
(a) Instantancous achieved hy GPC-Simplex over (b) Proportions of the population playing strategies time, compared default Rock-Paper-Ser Paee--aar--SSisoorss Scissors control "rack", "paper", and "scissors" over time under control and Best Response control (dashed orange).
by GPC-Simplex.
Figure 7: Experimental results for dynamical system with horizon T' 100, uniform initial state, update rule Eq. (50) with v 1/4, no perturbations, and time-invariant cost function (a ue) xii all times t. GPC-Simplex was implemented as described in Appendix E. The Best Response controller at each time f picks the control u that minimizes c--1 (f-1(f(2e; u), u.. The default controller picks the uniform control (1/3, 1/3, 1/3).
Parameters and cost function. We define (nonlinear) dynamical system with uniform initial state æ1 = (1/3, 1/3, 1/3), update rule Eq. (50) with 1/4, and 100 timesteps. We consider the fixed cost function
c(a,, uz) 2
which can be thought of as penalizing the strategy "rock".
Results. We compare GPC-Simplex (implemented described in Appendix E) with a baseline control that simply uses the standard Rock-Paper-Scisson payoff matrix (up to scaling) induced by (1/3, 1/3, 1/3) E A3. 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 CPC-Simplex is shown 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 good policy, Fig. 7a clearly shows that Best Response learns faster. However, 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 does not observe until after playing control. In Fig. 8, consider slightly modified system where the cost function includes a cost on the control with probability 1/2. In this setting, we see that GPC-Simpler ex still eventually learns 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.
I Discussions
I.1 Broader impacts
Our work provides robust algorithm with theoretical justifications for practical control problems that might be applicable 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.
36

---

Comparison of slic ing window losses over time
0.5
0.3
0.1
0 25 50 75 100
125
1.50
175
230
Time
Figure 8: Experimental results for dynamical system with horizon T' 200, uniform initial state, update rule Eq. (50) with 1/4, no perturbations, and random cost function which is either e4 (Tt,, ue) = æ² or (x M²) æ + Mis with equal prohability. GPC- Prc-Simplex was implemented as described in Appendix E. The Best Response controller each time & picks the control that minimizes ct-1 (f u), u). The default controller picks uniform control (1/3, 1/3, 1/3). The plot shows cost achieved by CPC-Simplex over time, compared to default to the non-continuity induced by the random cost functions, the loss plotted at time is the average loss of the controller across the last min (t, 15) time steps.
Sare---ppr---ssssee control and Best Response control (dashed orange). Due
1.2 Computational Resources for Experiments
The experiments in this work simulations and relatively small-scaled. They were 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.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the
contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The paper discussed the limitations of the work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
Justification: For each theoretical result, the paper provides the full set of assumptions and complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
38

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper fully discloses all the information needed to reproduce the main experimental results of the paper.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken
to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide a link to the anonymous repository containing our code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/ SatteSSumisssioPoo....
public/ pellic//gudees.c
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not
39

---

reproducible, they including code, unless this is central to the contribution (e.g., for new open-souree benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/nips. cc/public/ htt///uies/////ee sedddddde//eemmmiii /CodeSubmiss cerbbmssssonnl sssssssssiccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Ye]]
Justification: The paper specifies all the training and test details (e.g.. data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core of the paper to 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, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be elearly 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out 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.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
40

---

Answer: [Yes]
Justification: See Appendix J.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't Itdn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the ct/ppuullitt.c........eeeeeeeeee cwwuideeieeessssseeecee NeurlPS Code of Ethics https: : //nnunurissp cc waabblic/Ethiceeee
Answer: [Yes]
Justification: The research conforms to the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid-
eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: See Appendix J.1.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and funetioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Question:
Justification: the paper poses no such risks. Guidelines:
The answer NA means that the paper poses no such risks.
41

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: cite the original paper that produced the code package dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode thcode. www.co///aoooooo datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets. Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
42

---

According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "8DWmZ4MTZa", "reviewer": "Reviewer_XKZK", "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.", "questions": "See the above and below comments.", "limitations": "See the above comments.\n\nHave 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.\n\n- Given the various assumptions made while proving the regret guarantee, a dedicated Limitations or Implications section delineating use cases and generalizability should be included.\n\n- Figure 1 and its texts are too small; the texts in Figure 2 as well.\n\n- The experiment on vanilla SIR model in the main text seems trivial and should be replaced with the replicator dynamics experiment in the appendix.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides regret guarantees against policies that do not strongly stabilize the simplex LDS by developing an algorithm that aims to achieve low regret against this policy class while being robust to adversarial shocks to the system and adaptable to time-varying cost functions. All assumptions were reasonably justified, and all theoretical results were adequately proved. The paper also provides promising empirical results by applying the proposed algorithm to controlled settings of the SIR model and the replicator dynamics from evolutionary game theory.", "weaknesses": "- Unclear motivations for the considered simplex LDS setting. A discussion on more general LDS settings would be helpful.\n\n- 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.\n\n- Missing formal analyses on time complexity. This could be important for larger-scaled experiments (d >> 3), which the paper did not explore.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments! Please see below for our responses to your concerns:\n\n**Motivation for simplex LDS?** The basic motivation for the simplex LDS model, as discussed in the paper, is as a specialization/adaptation of the general LDS model to population dynamics, i.e. settings where the state is always a distribution. While there could be alternative models, we would argue that the constraints in the simplex LDS definition are for the most part fairly minimal. We are happy to add some discussion of potential generalizations and the technical obstacles to relaxing our assumptions. \n\nAdditionally, insofar as all models are wrong and should be justified by the algorithms they suggest, our experiments (in a variety of well-studied scenarios, not all of which satisfy the assumptions of the simplex LDS model or even the general LDS model) suggest that GPC-Simplex is a useful algorithm, and thereby vindicate the utility of the simplex LDS model as a theoretical tool for algorithm design. \n\n**Examples where $\\gamma_t$ is observable?** Note that even if we did not require knowledge of $\\gamma_t$, the algorithm still requires knowing the proportions of individuals of different types in the population, which seems unavoidable for controlling the system. The assumption that we know $\\gamma_t$ simply requires that we can additionally observe the total size of the population. Examples where this is feasible include many ecological settings, where e.g. the Mark-Recapture technique is often used to estimate the number of individuals. \n\n**Time complexity?** As stated in Theorem 7, the time complexity of our algorithm is polynomial in the dimension and number of iterations; the computational bottleneck is the mirror descent subroutine, which requires solving a simple convex program. From a practical perspective, we remark that the time complexity is comparable to that of the standard GPC algorithm (Agarwal et al. 2019) for controlling general linear dynamical systems. \n\n**Additional comments.** Thank you for the helpful comments about the figure sizes and order of experiments; modulo space constraints we will attempt those changes. Also as you suggested, we will add a section discussing the practical implications of our technical assumptions. We will remark that this work is only the first step towards more robust methodologies for control in population dynamics. There are numerous important directions for future research, including generalizations of the simplex LDS model, assumptions complementary to our mixing time assumption, and development of theoretical guarantees for non-linear systems.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3g0gfRgUem", "reviewer": "Reviewer_7y5h", "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.", "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": "I don't see any limitations or potential negative societal impact of this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is in general well-written and smooth to follow. The proofs seem to be theoretically sound. The studied problem is of great interest and hard to tackle as it involves adversarial shocks and time-varying cost functions.", "weaknesses": "My main concern is the novelty of the proposed algorithm compared with the original GPC algorithm. Could the authors provide more justifications for this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments! We are glad that you found the problem of great interest, and found our paper easy to follow. We address your questions and concerns below:\n\n**Novelty of the proposed algorithm.** First, we reemphasize that the original GPC algorithm does not work in the simplex LDS setting. When there are no perturbations to the system, the original GPC algorithm simply plays its initialization policy for all time, which is highly unlikely to perform well. As discussed in Section 3, the fundamental issue is that GPC only competes against strongly stabilizing policies, but in a simplex LDS, no policy is strongly stabilizing. Indeed, prior to our work, this reliance on strong stability was a limitation of the entire literature on non-stochastic control. \n\nThis is why solving the control problem in the simplex LDS setting requires a new algorithm. From a bird's eye view, our proposed algorithm GPC-Simplex indeed looks similar to GPC \\--- hence the name \\--- but the differences are conceptually important. As discussed in Section 3, the key difference is that we augment the class of disturbance-action policies (over which we are optimizing via mirror descent) with an additional parameter $p_t$ that roughly represents the optimal stationary distribution that we would like to converge to in the absence of noise. This depends on the future sequence of adversarial cost functions, and hence must be learned in an online fashion along with the other parameters. The upshot is that this modification enables competing against not just policies that strongly stabilize the system (which do not exist in population dynamics), but also policies that *mix* the system (which are highly natural in population dynamics).\n\nFrom a broader perspective, one contribution of our work is to show that even though non-stochastic control requires some assumptions to be tractable, *strong stabilizability is not the end of the story.* In particular, the tools from non-stochastic control can be modified to work even in some (theoretical and practical) settings where strong stabilizability is completely unreasonable and standard GPC fails. We believe that this perspective may be valuable even beyond the specific setting of population dynamics.\n\n**Non-uniform Lipschitz constant?**\n\nCertainly Theorem 7 would still hold with $L$ replaced by the maximum of $L_t$ over $1 \\leq t \\leq T$. If this maximum scales asymptotically slower (in $T$) than $\\sqrt{T}$, then we still get sub-linear regret. If it scales as fast as $\\sqrt{T}$ or faster, then (with no other control on the sequence of $L_t$'s) we would expect that achieving sub-linear regret is provably impossible by standard lower bounds from online convex optimization. It's plausible that tighter bounds are possible if e.g. the $L_t$'s are small on average, but we have not investigated this direction, as a uniform Lipschitz bound is the standard assumption in the control literature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6NOFnnamYK", "reviewer": "Reviewer_ofBj", "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.", "questions": "See questions about regarding the comparator class of policies.\n\nAlso please make the figures and label text larger, they are a bit hard to read.", "limitations": "Yes, these have been discussed to the extent necessary.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "I really liked this paper. It does a nice job of taking recently developed tools from online linear control and extends them to a new, interesting, and well motivated, class of dynamical systems. I like how the paper shows both positive and negative results. I found the idea that there is a gap between prediction and control for marginally stable systems to be quite insightful, and the regret bounds for the simplex LDS systems to be quite neat. \n\nI also thought that the experiments were a very good complement to the theoretical results. It is always nice when experiments test algorithms in regimes where the theory may not exactly hold.", "weaknesses": "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. \n\nIn 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments! We are glad that you appreciated our paper. We address your comments and questions below:\n\n**Intuition about simplex LDS conditions.** The assumption that the control norm is independent of the state is indeed needed for technical reasons: without it, since $Ax$ is multiplied by $1-\\|u\\|_1$ in the transition dynamics (see Eq. (4)), even a \"linear'' policy $u := Kx$ does not induce a linear transition. Hence, it's not clear how one might define mixing time of a fully general linear policy (since it may not correspond to a Markov chain over $[d]$). It is a very interesting question whether there is a more natural (yet still tractable) definition of a simplex LDS that avoids this issue. We will add some discussion about this issue to the text.\n\n**Figure/label sizes.** Thanks for pointing this out, we will try to make them larger.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fxEP13IEIL", "reviewer": "Reviewer_2PrE", "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.", "questions": "1.How does the algorithm perform in real-world applications with non-Gaussian noise and unknown transition matrices?\n2.Can the authors provide more detailed guidance or a method for adaptively selecting the algorithm's parameters?\n3.What are the computational requirements of the algorithm in large-scale systems? \n4. How robust is the algorithm to inaccuracies in the model assumptions, such as errors in the transition matrices or noise characteristics?\n5. How does the algorithm handle delays in control actions or observations, which are common in real-world systems?", "limitations": "The authors have discussed some limitations of their work.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Originality: \nThe paper introduces a novel approach to control partially observable LDS by combining mirror descent with a new parameterization method. This is a significant departure from traditional methods that assume full observability.\n\nQuality: \nThe theoretical foundations of the algorithm are robust, with detailed proofs and clear assumptions. The analysis includes regret bounds that highlight the algorithm's near-optimal performance under specific conditions.\n\nClarity: \nThe paper is well-structured and clearly written. The problem is well-motivated, and the methodology is presented in a step-by-step manner that is easy to follow.\n\nSignificance: \nThe ability to control systems with only partial observability has broad implications for various fields, including epidemiology, biology, and economics. The proposed method has the potential to be applied to a wide range of real-world problems.", "weaknesses": "Idealized Assumptions: \nThe 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.\n\nLimited Generalization: \nWhile 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.\n\nSensitivity to Parameters: \nThe 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.\n\nExperimental Scope: \nThe experimental validation is limited to simulated environments. More real-world experiments would strengthen the evidence for the algorithm's practical effectiveness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and comments! Unfortunately we believe that the reviewer has missed the point of the paper, which is to extend non-stochastic control methods to *population dynamics*. See below for responses to specific criticisms:\n\n**Idealized Assumptions?** The review claims that we assume Gaussian noise. This is incorrect. Our algorithm can deal with unknown adversarial perturbations (which is one of the main benefits of the non-stochastic control methodology).\n\nKnown transition matrices is a standard assumption in online non-stochastic control. Results established for known systems can often be extended to unknown systems with a similar regret guarantee (see the list of papers below). However, this is out of scope of our current work, which is focused on establishing a new framework for controlling population dynamics.\n\n[1] Simchowitz, Max, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. Conference on Learning Theory. PMLR, 2020.\n\n[2] Chen, Xinyi, and Elad Hazan. Black-box control for linear dynamical systems. Conference on Learning Theory. PMLR, 2021.\n\n[3] Gradu, Paula, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. Advances in Neural Information Processing Systems 33 (2020): 10764-10774.\n\n[4] Simchowitz, Max. Making non-stochastic control (almost) as easy as stochastic. Advances in Neural Information Processing Systems 33 (2020): 18318-18329.\n\n\n**Generalization to highly non-linear/complex systems?** In fact, many of the systems studied in our experiments (e.g. SIR in section 4.1 and replicator dynamics in Section J) are highly non-linear. As discussed in Appendix G, our algorithm GPC-Simplex can nonetheless be naturally extended to such systems, and the experimental results are promising.\n\nIt is true that our theoretical results are limited to linear systems. However, this is the case for almost all existing theoretical guarantees in the control theory literature. Obtaining provable guarantees for non-linear systems is generally considered a very challenging research direction, and the linearity assumption has proven to be a good testbed for algorithm design in the past. For a concrete example, note that the original GPC algorithm (Agarwal et. al. 2019) also has theoretical guarantees restricted to linear systems. \n\nReturning to empirical performance: we agree that experimenting with more complex scenarios is a valuable direction for future research, but it is outside the scope of this (primarily theoretical/conceptual) work. The goal of this work was to propose a robust framework for the long-standing problem of controlling population dynamics. To the best of our knowledge, all prior methods for this problem relied on much more restrictive assumptions (e.g., known costs, no noise, closed-form solution based on differential equations); see the references below. \n\n[1] Mohamed Elhia, Mostafa Rachik and Elhabib Benlahmar. Optimal Control of an SIR Model with Delay in State and Control Variables. International Scholar Research Notices, 2013.\n\n[2] Gul Zaman, Yong Han Kang and Il Hyo Jung. Optimal treatment of an SIR epidemic model with time delay. BioSystems, 2009.\n\n[3] E.V. Grigorieva, E.N. Khailov and A. Korobeinikov. Optimal Control for a SIR Epidemic Model with Nonlinear Incidence Rate. Math. Model. Nat. Phenom, 2016.\n\n[4] Luca Bolzoni, Elena Bonacini, Cinzia Soresina, Maria Groppi. Time-optimal control strategies in SIR epidemic models. Mathematical Biosciences, 2017.\n\n[5] Urszula Ledzewicz and Heinz Schättler. On optimal singular controls for a general SIR-model with vaccination and treatment. DYNAMICAL SYSTEMS, 2011.\n\n**Sensitivity to Parameters?** We are not sure of the basis for the reviewer's criticism that the performance of the algorithm is particularly sensitive to the choice of parameters. Our theoretical results provide guidance for setting the parameters (e.g. policy horizon $H$ and learning rate $\\eta$) based on a choice of $\\tau$ (mixing time of comparator class) and an upper bound on $L$ (Lipschitz constant for cost functions), which are both problem-specific. For our empirical results we did not need to tune the parameters across experiments; for all experiments we took $H = 5$ and $\\eta$ as defined in Appendix G. This suggests that parameter tuning is not critical to the algorithm's performance in practice. Of course, designing adaptive algorithm is in general an interesting research area, but it is beyond the scope of this work.\n\n**Experimental Scope?** As we mentioned previously, this is a theory-focused paper, and the primary role of our experiments is to serve as a validation of the theoretical framework. Therefore, although conducting experiments on real-world data would be interesting, we argue that it is not necessary for this work.\n\n**Question 1.** First, we want to reiterate that we *do not* assume Gaussian noise. In the SIR experiments in Appendix I.1, the perturbations are not Gaussian either. We do assume known dynamics. For unknown systems, one could run one of the existing system identification algorithms to obtain an estimate for the system, and run our controller algorithm using those system estimates.\n\n**Question 2-5.** As mentioned previously, this is not an experiment-focused paper. These are certainly valuable research directions and would lead to interesting follow-up works. However, they are out of scope of this work. The main focus of the work, again, was to provide a new framework for controlling population dynamics using tools from non-stochastic control theory \\--- a connection between two fields that has not previously been considered.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their time and comments. For full disclosure, we would like to inform the reviewers that we discovered a technical error in one of the secondary results in the appendices (Theorem 29, an analysis of a proposed extension to GPC-Simplex for the partially observable setting, which is briefly discussed in Section 3.1). The specific error is that the controller performs online convex optimization, but our loss function in the partially observable setting (Line 6 of Algorithm 2) involves a projection operator, and hence is actually not convex.

This error does not affect our primary theoretical contributions (Theorems 1/2/7/8) nor the experiments, which are all in the fully observable setting. Moreover, we expect that Theorem 29 is likely fixable by modifying the algorithm. However, if our paper is accepted, we would simply remove Theorem 29 from the camera-ready submission, since it is not relevant to the primary contribution of the paper, which is to use tools from non-stochastic control to design a robust methodology for control of (fully-observed) population dynamics. In any case, we apologize for the error.

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