Online Control of Unknown Time-Varying Dynamical Systems
Year: 2021

Abstract:
We study online control of time-varying linear systems with unknown dynamics in the nonstochastic control model. At a high level, we demonstrate that this setting is qualitatively harder than that of either unknown time-invariant or known timevarying dynamics, and complement our negative results with algorithmic upper bounds in regimes where sublinear regret is possible. More specifically, we study regret bounds with respect to common classes of policies: Disturbance Action (SLS), Disturbance Response (Youla), and linear feedback policies. While these three classes are essentially equivalent for LTI systems, we demonstrate that these equivalences break down for time-varying systems. We prove a lower bound that no algorithm can obtain sublinear regret with respect to the first two classes unless a certain measure of system variability also scales sublinearly in the horizon. Furthermore, we show that offline planning over the state linear feedback policies is NP-hard, suggesting hardness of the online learning problem. On the positive side, we give an efficient algorithm that attains a sublinear regret bound against the class of Disturbance Response policies up to the aforementioned system variability term. In fact, our algorithm enjoys sublinear adaptive regret bounds, which is a strictly stronger metric than standard regret and is more appropriate for time-varying systems. We sketch extensions to Disturbance Action policies and partial observation, and propose an inefficient algorithm for regret against linear state feedback policies.

heading: 1 Introduction
text: The control of linear time-invariant (LTI) dynamical systems is well-studied and understood. This includes classical methods from optimal control such as LQR and LQG, as well as robust H∞ control. Recent advances study regret minimization and statistical complexity for online linear control, in both stochastic and adversarial perturbation models. Despite this progress, rigorous mathematical guarantees for nonlinear control remain elusive: nonlinear control is both statistically and computationally intractable in general.
In the face of these limitations, recent research has begun to study the rich continuum of settings which lie between LTI systems and generic nonlinear ones. The hope is to provide efficient and robust algorithms to solve the most general control problems that are tractable, and at the same time, to characterize precisely at which degree of nonlinearity no further progress can be made.
35th Conference on Neural Information Processing Systems (NeurIPS 2021), virtual.
This paper studies the control of linear, time-varying (LTV) dynamical systems as one such point along this continuum. This is because the first-order Taylor approximation to the dynamics of any smooth nonlinear system about a given trajectory is an LTV system. These approximations are widely popular because they allow for efficient planning, as demonstrated by the success of iLQR and iLQG methods for nonlinear receding horizon control. We study online control of discrete-time LTV systems, with dynamics and time-varying costs
xt+1 = Atxt +Btut + wt, ct(xt, ut) : (x, u)→ R. (1.1)
Above, xt is the state of the system, ut the control input, wt the disturbances, and At, Bt the system matrices. Our results extend naturally to partial-state observation, where the controller observes linear projections of the state yt = Ctxt. We focus on the challenges introduced when the system matrices At, Bt and perturbations wt are not known to the learner in advance, and can only be determined by live interaction with the changing systems.
In this setting, we find that the overall change in system dynamics across time characterizes the difficulty of controlling the unknown LTV system. We define a measure, called system variability, which quantifies this. We show both statistical and computational lower bounds as well as algorithmic upper bounds in terms of the system variabilility. Surprisingly, system variability does not impede the complexity of control when the dynamics are known [16].

heading: 1.1 Contributions
text: We consider the recently popularized nonstochastic model of online control, and study regret bounds with respect to common classes of policies: Disturbance Action (DAC/SLS [44]), Disturbance Response (DRC/Youla [46]), and linear feedback policies. Planning over the third class of feedback policies in LTI systems admits efficient convex relaxations via the the first two parametrizations, DAC and DRC. This insight has been the cornerstone of both robust [49, 44] and online [3, 39] control.
Separation of parametrizations. For linear time-varying systems, however, we find that equivalences between linear feedback, DAC and DRC fail to hold: we show that there are cases where any one of the three parametrizations exhibits strictly better control performance than the other two.
Regret against convex parametrizations. Our first set of results pertain to DAC and DRC parametrizations, which are convex and admit efficient optimization. We demonstrate that no algorithm can obtain sublinear regret with respect to these classes when faced with unknown, LTV dynamics unless a certain measure of system variability also scales sublinearly in the horizon. This is true even under full observation, controllable dynamics, and fixed control cost. This finding is in direct contrast to recent work which shows sublinear regret is attainable over LTV system dynamics if they are known [16].
We give an efficient algorithm that attains sublinear regret against these policy classes up to an additive penalty for the aforementioned system variability term found in our lower bound. When the system variability is sufficiently small, our algorithm recovers state-of-the-art results for unknown LTI system dynamics up to logarithmic factors.
In fact, our algorithm enjoys sublinear adaptive regret [21], a strictly stronger metric than standard regret which is more appropriate for time-varying systems. We also show that the stronger notion of adaptivity called strongly adaptive regret [11] is out of reach in the partial information setting.
Regret against state feedback. Finally, we consider the class of state feedback policies, which are linear feedback with memory length one. We show that full-information optimization over state feedback policies is computationally hard. This suggests that obtaining sublinear regret relative to these policies may be computationally prohibitive, though does not entirely rule out the possibility of improper learning. However, improper learning cannot be done via the DRC or DAC relaxations in light of our policy class separation results. Finally, we include an inefficient algorithm which attains sublinear (albeit nonparametric-rate) regret against state feedback control policies.
Paper Structure
Discussion of relevant literature and relation to our work can be found in Section 1.2. In Section 2, we formally introduce the setting of LTV nonstochastic control, the policy classes we study and our key result regarding their non-equivalence in the LTV setting (Theorem 2.1). Motivated by this
non-equivalence, the remainder of the paper is split into the study of convex policies (Section 3) and of state feedback policies (Section 4). In Section 3, we show that regret against the DAC and DRC classes cannot be sublinear unless the metric system variability (Definition 3.1) itself is sublinear (Theorem 3.1), and also propose Algorithm 2 whose adaptive regret scales at the rate of our lower bound plus a T 2/3 term (Theorem 3.4). On the other hand, in Section 4 we show sublinear regret against state feedback policies is technically possible (Theorem 4.1) with a computationally inefficient algorithm, but also provide a computational lower bound (Theorem 4.2) for planning which reveals significant difficulties imposed by the LTV dynamics in this scenario as well. Finally, in Section 5 we pose several future directions, concerning both questions in LTV control, as well as the extension to nonlinear control.

heading: 1.2 Related Work
text: Our study of LTV systems is motivated by the widespread practical popularity of iterative linearization for nonlinear receding horizon control; e.g., the iLQR [40], iLC [29], and iLQG [41] algorithms. Recent research has further demonstrated that near-optimal solutions to LTV approximations of dynamics confer stability guarantees onto the original nonlinear system of interest [45].
Low-Regret Control: We study algorithms which enjoy sublinear regret for online control of LTV systems; that is, whose performance tracks a given benchmark of policies up to a term which is vanishing relative to the problem horizon. [1] initiated the study of online control under the regret benchmark by introducing the online LQR problem: where a learner is faced with an unknown LTI system, fixed costs and i.i.d. Gaussian disturbances, and must attain performance relative to the LQR-optimal policy. Bounds for this setting were later improved and refined in [12, 26, 10, 38], and extended to partial-state observation in [25, 24]. Our work instead adopts the nonstochastic control setting [3], where the adversarially chosen (i.e. non-Gaussian) noise is considered to model the drift terms that arise in linearizations of nonlinear terms, and where costs may vary with time. [3] consider known system dynamics, later extended to unknown systems under both full-state [20] and partial-state observation [39, 37]. The study of nonstochastic control of known LTV dynamics was taken up in [16], with parallel work by [32] considering known LTV dynamics under stochastic noise.
Unknown LTV dynamics: Our work is the first to consider online (low-regret) control of unknown LTV systems in any model. There is, however, a rich body of classical work on adaptive control of LTV systems [28, 42]. These guarantees focus more heavily on error sensitivity and stability; they only permit dynamical recovery up to error that scales linearly in system noise, and thus guarantee only (vacuous) linear-in-horizon regret. More recent work has studied identification (but not online control) of an important LTV class called switching systems [31, 35].
Online Convex Optimization: We make extensive use of techniques from the field of online convex optimization [9, 18]. Most relevant to our work is the literature on adapting to changing environments in online learning, which starts from the works of [22, 6]. The notion of adaptive regret was introduced in [21] and significantly studied since as a metric for adaptive learning in OCO [2, 47]. [11] proposed to strengthen adaptive regret and the stronger metric has been shown to imply results over dynamic regret [48].
Recent nonlinear control literature: Recent research has also studied provably guarantees in various complementary (but incomparable) models: planning regret in nonlinear control [4], adaptive nonlinear control under linearly-parameterized uncertainty [5], online model-based control with access to non-convex planning oracles [23], and control with nonlinear observation models [27, 13].

heading: 2 Problem Setting
text: We study control of a linear time-varying (LTV) system Eq. (1.1) with state xt ∈ Rdx , control input ut ∈ Rdu chosen by the learner, and the external disturbance wt ∈ Rdx chosen by Nature. The system is characterized by time-varying matrices At ∈ Rdx×dx , Bt ∈ Rdx×du . For simplicity, the initial state is x1 = 0. At each time t, oblivious1 adversary picks the system matrices (At, Bt), disturbances wt and cost functions ct : Rdx × Rdu → R. The dynamics (At, Bt) are unknown to the learner: one observes only the next state xt+1 and current cost ct(·, ·) after playing control ut.
1An oblivious adversary chooses the matrices, costs and perturbations prior to the control trajectory.
Adaptive Regret. The goal of the learner is to minimize regret w.r.t. a policy class Π, i.e. the difference between the cumulative cost of the learner and the best policy π? ∈ Π in hindsight. Formally, the regret of an algorithm A with control inputs u1:T and corresponding states x1:T , over an interval I = [r, s] ⊆ [T ], is defined as
RegretI(A; Π) = ∑ t∈I ct(xt, ut)− inf π∈Π ∑ t∈I ct(x π t , u π t ) . (2.1)
Here uπt , x π t indicate the control input and the corresponding state when following policy π. For a randomized algorithmA, we consider the expected regret. In this work, we focus on designing control algorithms that minimize adaptive regret, i.e. guarantee a low regret relative to the best-in-hindsight policy π?I ∈ Π on any interval I ⊆ [T ]. This performance metric of adaptive regret is more suitable for control over LTV dynamics given its agility to compete against different local optimal policies π?I ∈ Π at different times [16]. Key objects. A central object in our study is the sequence of Nature’s x’s xnat1:T that arises from playing zero control input ut = 0 at each t ∈ [T ], i.e. xnatt+1 = Atxnatt +wt [39]. define the following operators for all t,
Φ [0] t = I, ∀h ∈ [1, t), Φ [h] t = t−h+1∏ k=t Ak, ∀i ∈ [0, t), G[i]t = Φ [i] t Bt−i,
where the matrix product ∏r s with s ≥ r is taken in the indicated order k = s, . . . , r. the following identities give an alternative representation for the Nature’s x’s xnatt and state xt with control input ut in terms of the Markov operator at time t, Gt = [G [i] t ]i≥0:
xnatt+1 = t−1∑ i=0 Φ [i] t wt−i, xt+1 = x nat t+1 + t−1∑ i=0 G [i] t ut−i .
These operators and the alternative representation capture the dynamics by decoupling the disturbance and the control action effects.
Assumptions. We make the three basic assumptions: we require from (i) the disturbances to not blow up the system with no control input, (ii) the system to have decaying effect over time, and (iii) the costs to be well-behaved and admit efficient optimization. Formally, these assumptions are: Assumption 1. For all t ∈ [T ], assume ‖xnatt ‖ ≤ Rnat. Assumption 2. Assume there exist RG ≥ 1 and ρ ∈ (0, 1) s.t. for any h ≥ 0 and for all t ∈ [T ]∑
i≥h
‖G[i]t ‖op ≤ RG · ρh := ψ(h) .
Assumption 3. Assume the costs ct : Rdx × Rdu → R are general convex functions that satisfy the conditions 0 ≤ ct(x, u) ≤ Lmax{1, ‖x‖2 + ‖u‖2}, and ‖∇ct(x, u)‖ ≤ Lmax{1, ‖x‖+ ‖u‖} for some constant L > 0, where ∇ denotes any subgradient [7].
The conditions in Assumption 3 allow for functions whose values and gradient grow as quickly as quadratics (e.g. the costs in LQR) , and the max{1, ·} term ensures the inclusion of standard bounded and Lipschitz functions as well. Assumptions 1 and 2 arise from the assumption our LTV system is open-loop stable; Appendix A.2 extends to the case where a nominal stabilizing controller is known, as in prior work [3, 39]. While these two assumptions may seem unnatural at first, they can be derived from the basic conditions of disturbance norm bound and sequential stability.
Lemma 2.1. Suppose that there exist C1 ≥ 1, ρ1 ∈ (0, 1) such that ‖Φ[h]t ‖op ≤ C1ρh1 for any h ≥ 0 and all t ∈ [T ], and suppose that maxt ‖wt‖ ≤ Rw. Then, Assumption 1 holds withRnat = C11−ρ1Rw, and Assumption 2 holds with ρ = ρ1 and RG = max{1,maxt ‖Bt‖op · C11−ρ1 }.
Note that Assumption 2 implies that ‖Gt‖`1,op = ∑ i≥0 ‖G [i] t ‖op ≤ RG. It also suggests that for a sufficiently large h the effect of iterations before t − h are negligible at round t. This prompts introducing a truncated Markov operator: denote Ḡht = [G [i] t ]i<h to be the h-truncation of the true
Markov operator Gt. It follows that their difference is ‖Ḡht − Gt‖`1,op = ∑ i≥h ‖G [i] t ‖op ≤ ψ(h) negligible in operator norm for a sufficiently large h. Define the bounded set of h-truncated Markov operators to be G(h,RG) = {G = [G[i]]0≤i<h : ‖G‖`1,op ≤ RG} with Ḡht ∈ G(h,RG) for all t.

heading: 2.1 Benchmarks and Policy Classes
text: The performance of an algorithm, measured by Eq. (2.1), directly depends on the policy class Π that is chosen as a benchmark to compete against. In this work, we consider the following three policy classes: DRC, DAC, and linear feedback. DRC parameterizes control inputs in terms of Nature’s x’s xnatt , DAC does so in terms of the disturbances wt and linear feedback in terms of the states xt. We express all three in terms of a length-m parameter M = [M [i]]i<m in a bounded ballM(m,RM ):
M(m,RM ) = {(M [0], . . . ,M [m−1]) : ∑m−1 i=0 ‖M [i]‖op ≤ RM} .
Definition 2.1 (DRC policy class). A DRC control policy πMdrc of length m is given by uMt =∑m−1 i=0 M [i]xnatt−i where M = [M [i]]i<m is the parameter of the policy. Define the bounded DRC policy class as Πdrc(m,RM ) = {πMdrc : M ∈M(m,RM )}. Definition 2.2 (DAC policy class). A DAC control policy πMdac of length m is given by uMt =∑m−1 i=0 M
[i]wt−i where M = [M [i]]i<m is the parameter of the policy. Define the bounded DAC policy class as Πdac(m,RM ) = {πMdac : M ∈M(m,RM )}. Definition 2.3 (Feedback policy class). A feedback control policy πMfeed of length m is given by uMt = ∑m−1 i=0 M
[i]xt−i where M = [M [i]]i<m is the parameter of the policy. Define the bounded feedback policy class as Πfeed(m,RM ) = {πMfeed : M ∈ M(m,RM )}. In the special case of memory m = 1, denote the state feedback policy class as Πstate = Πfeed(m = 1).
Convexity. Both the DRC and DAC policy classes are convex parametrizations: a policy π ∈ Πdrc ∪Πdac outputs controls ut that are linear in the policy-independent sequences xnat1:T and w1:T , and thus the mapping from parameter M to resulting states and inputs (resp. costs) is affine (resp. convex). Hence, we refer to these as the convex classes. In contrast, feedback policies select inputs based on policy-dependent states, and are therefore non-convex [15].
We drop the arguments m,RM when they are clear from the context. The state feedback policies Πstate encompass the H2 and H∞ optimal control laws under full observation. For LTI systems, DRC and DAC are equivalent [46, 44] and approximate all linear feedback policies to arbitrarily high precision [3, 39]. However, we show that these relationships between the classes break down for LTV systems: there exist scenarios where any one of the three classes strictly outperforms the other two. Theorem 2.1 (Informal). For each class Π in {Πdrc,Πdac,Πfeed} there exists a sequence of wellbehaved (At, Bt, wt, ct) such that a policy π? ∈ Π suffers 0 cumulative cost, but each of the other two classes Π′ ∈ {Πdrc,Πdac,Πfeed} \Π suffers Ω(T ) cost on all their constituent policies π ∈ Π′.
The formal theorem that includes the definition of a well-behaved instance sequence and the final statement dependence on m,RM along with its proof can be found in Appendix F.1.
Notation. The norm ‖ · ‖ refers to Euclidean norm unless otherwise stated, [n] is used as a shorthand for [1, n], T is used as a subscript shorthand for [T ]. The asymptotic notation O(·),Ω(·) suppress all terms independent of T , Õ(·) additionally suppresses terms logarithmic in T . We define Õ?(·) to suppress absolute constants, polynomials in Rnat, RG, RM and logarithms in T .

heading: 3 Online Control over Convex Policies
text: This section considers online control of unknown LTV systems so as to compete with the convex DRC and DAC policy classes. The fundamental quantity which appears throughout our results is the system variability, which measures the variation of the time-varying Markov operators Gt over intervals I . Definition 3.1. Define the system variability of an LTV dynamical system with Markov operators G = G1:T over a contiguous interval I ⊆ [T ] to be
VarI(G) = min G
1 |I| ∑ t∈I ‖G−Gt‖2`2,F = 1 |I| ∑ t∈I ‖GI −Gt‖2`2,F ,
where ‖ · ‖`2,F indicates the `2 norm of the fully vectorized operator and GI = |I|−1 ∑ t∈I Gt is the empirical average of the operators that correspond to I . Recall that VarT (G) corresponds to I = [T ].
Our results in this section for both upper and lower bounds focus on expected regret: high probability results are possible as well with more technical effort using standard techniques.

heading: 3.1 A Linear Regret Lower Bound
text: Our first contribution is a negative one: that the regret against the class of either DAC or DRC policies cannot scale sublinearly in the time horizon. Informally, our result shows that the regret against these classes scales as Tσ, where σ2 is the system variability.
More precisely, for any σ2 ∈ (0, 1/8], we construct a distributionDσ over sequences (At, Bt, ct, wt), formally specified in Appendix F.2. Here, we list the essential properties of Dσ: (i) At ≡ 0, (ii) ct ≡ c is a fixed cost satisfying Assumption 3 with L ≤ 4, (iii) the matrices (Bt) are i.i.d., with ‖Bt‖op ≤ 2 almost surely, and E[‖Bt−E[Bt]‖2F] = σ2, and (iv) ‖wt‖ ≤ 4 for all t. These conditions imply that Assumptions 1 and 2 hold for RG = 2, ρ = 0, Rnat = 4. The condition At ≡ 0 implies that xnatt = wt for all t, so the classes DRC and DAC are equivalent and the lower bound holds over both. Moreover, by Jensen’s inequality, this construction ensures that
E[VarI(G)] = |I|−1E[min G ∑ t∈I ‖G−Gt‖2`2,F ]
= |I|−1E[min B
∑ t∈I ‖B −Bt‖2F] ≤ E[‖Bt − E[Bt]‖2F] = σ2.
In particular, E[VarT (G)] ≤ σ2. For the described construction, we show the following lower bound:
Theorem 3.1. Let C be a universal, positive constant. For any σ ∈ (0, 1/8] and any online control algorithm A, there exists a DRC policy π? ∈ Πdrc(1, 1) s.t. expected regret incurred by A under the distribution Dσ and cost c(x, u) is at least
EDσ,A[RegretT (A; {π?})] ≥ C · Tσ ≥ C · T · √ E[VarT (G)],
A full construction and proof of Theorem 3.1 is given in Appendix F.2. In particular, for σ = 1/8, we find that no algorithm can attain less than Ω(T ) expected regret; a stark distinction from either unknown LTI [39, 20] or known LTV [16] systems.

heading: 3.2 Estimation of Time-Varying Vector Sequences
text: To devise an algorithmic upper bound that complements the result in Theorem 3.1, we first consider the setting of online prediction under a partial information model. This setting captures the system identification phase of LTV system control and is used to derive the final control guarantees. Formally, consider the following repeated game between a learner and an oblivious adversary: at each round t ∈ [T ], the adversary picks a target vector z?t ∈ K from a convex decision set K contained in a 0-centered ball of radius Rz; simultaneously, the learner selects an estimate ẑt ∈ K and suffers quadratic loss `t(ẑt) = ‖ẑt − z?t ‖2. The only feedback the learner has access to is via the following noisy and costly oracle. Oracle 1 (Noisy Costly Oracle). At each time t ∈ [T ], the learner selects a decision bt ∈ {0, 1} indicating whether a query is sent to the oracle. If bt = 1, the learner receives an unbiased estimate z̃t as response such that ‖z̃t‖ ≤ R̃z and E[z̃t | Ft, bt = 1] = z?t . The filtration Ft is the sigma algebra generated by z̃1:t−1, b1:t−1 and the choices of the oblivious adversary z?1:T . A completed query results in a unit cost λ > 0 for the learner.
The performance metric of an online prediction algorithm Apred is expected quadratic loss regret along with the extra cumulative oracle query cost. It is defined over each interval I = [r, s] ⊆ [T ] as
RegretI(Apred;λ) = EF1:T [∑ t∈I `t(ẑt)−min z∈K ∑ t∈I `t(z) + λ ∑ t∈I bt ] . (3.1)
To attain adaptive regret, i.e. bound Eq. (3.1) for each interval I , we propose Algorithm 1 constructed as follows. First, suppose we wanted non-adaptive (i.e. just I = [T ]) guarantees. In this special case, we propose to sample bt ∼ Bernoulli(p) for an appropriate parameter p ∈ (0, 1), and perform a gradient descent update on the importance-weighted square loss ˜̀t(z) = 12p I{bt = 1}‖z− z̃t‖ 2. To
Algorithm 1 Adaptive Estimation Algorithm (ADA-PRED) 1: Input: parameter p, decision set K 2: Initialize: ẑ(1)1 ∈ K, working dictionary S1 = {(1 : ẑ (1) 1 )}, q (1) 1 = 1, parameter α =
p
(Rz+R̃z)2
3: for t = 1, . . . , T do 4: Play iterate ẑt = ∑ (i,ẑ
(i) t )∈St
q (i) t ẑ (i) t
5: Draw/Receive bt ∼ Bernoulli(p) 6: if bt = 1 then 7: Request estimate z̃t from Oracle 1 8: Let ˜̀t(z) = 12p ||z− z̃t||
2 and ∇̃t = 1p (zt − z̃) 9: else
10: Let z̃t ← ∅ and ˜̀t(z) = 0 and ∇̃t = 0 11: Update predictions ẑ(i)t+1 ← ProjK(ẑ (i) t − η (i) t ∇̃t) for all (i, ẑ (i) t ) ∈ St 12: Form new dictionary S̃t+1 = (i, ẑ(i)t+1)i∈keys(St)
13: Construct proxy new weights q̄(i)t+1 = t t+1 ·
q (i) t e −α˜̀t(ẑ (i) t )∑
j∈keys(St) q (j) t e −α˜̀t(ẑ
(j) t )
for all i ∈ keys(St)
14: Add new instance S̃t+1 ← S̃t+1∪ (t+ 1, ẑ(t+1)t+1 ) for arbitrary ẑ (t+1) t+1 ∈ K with q̄ (t+1) t+1 = 1 t+1 15: Prune S̃t+1 to form St+1 (see Appendix C.1) 16: Normalize q(i)t+1 = q̄ (i) t+1∑
j∈keys(St+1) q̄ (j) t+1
extend this method to enjoy adaptive regret guarantees, we adopt the approach of [21]: the core idea in this approach is to initiate an instance of the base method at each round t and use a weighted average of the instance predictions as the final prediction (Line 4). The instance weights are multiplicatively updated according to their performance (Line 13). To ensure computational efficiency, the algorithm only updates instances from a working dictionary St (Line 11). These dictionaries are pruned each round (Line 15) such that |St| = O(log T ) (see Appendix C.1 for details).
Theorem 3.2. Given access to queries from Oracle 1 and with stepsizes η(i)t = 1t−i+1 , Algorithm 1 enjoys the following adaptive regret guarantee: for all I = [r, s] ⊆ [T ],
RegretI(ADA-PRED;λ) ≤ 2(Rz + R̃z) 2(1 + log s · log |I|) p + λp|I| . (3.2)
When I = [T ], the optimal choice of parameter p = log T/ √ λT yields regret scaling roughly as √ λT log2 T . Unfortunatelly, this gives regret scaling as
√ T for all interval sizes: to attain√ |I| regret on interval I , the optimal choice of p would yield ∼ T/ √ |I| regret on [T ], which is considerably worse for small |I|. One may ask if there exists a strongly adaptive algorithm which adapts p as well, so as to enjoy regret polynomial in |I| for all intervals I simultaneously [11]. The following result shows this is not possible:
Theorem 3.3 (Informal). For all γ > 0 and λ > 0, there exists no online algorithm A with feedback access to Oracle 1 that enjoys strongly adaptive regret of RegretI(A;λ) = Õ(|I|1−γ).
Hence, in a sense, Algorithm 1 is as adaptive as one could hope for: it ensures a regret bound for all intervals I , but not a strongly adaptive one. The lower bound construction, formal statement, and proof of Theorem 3.3 are given in Appendix C.2.

heading: 3.3 Adaptive Regret for Control of Unknown Time-Varying Dynamics
text: We now apply our adaptive estimation algorithm (Algorithm 1) to the online control problem. Our proposed algorithm, Algorithm 2, takes in two sub-routines: a prediction algorithm Apred which enjoys low prediction regret in the sense of the previous section, and a control algorithm Actrl which has low regret for control of known systems. Our master algorithm trades off between the two in epochs τ = 1, 2, . . . of length h: each epoch corresponds to one step of Apred indexed by [τ ].
At each epoch, the algorithm receives Markov operator estimates from Apred (Line 3) and makes a binary decision b[τ ] ∼ Bernoulli(p). If b[τ ] = 1, then it explores using i.i.d. Rademacher inputs (Line 7), and sends the resulting estimator to Apred (Line 14). This corresponds to one query from Oracle 1. Otherwise, it selects inputs in line with Actrl (Line 9), and does not give a query to Apred (Line 16). Regardless of exploration decision, the algorithm feeds costs, current estimates of the Markov operator and Nature’s x’s based on the Markov operator estimates to Actrl (Lines 10-12), which it uses to select inputs and update its parameter.
The prediction algorithm Apred is taken to be ADA-PRED with the decision set K = G(h,RG): the projection operation onto it and the ball BRnat is done by clipping when the norm of the argument exceeds the indicated bound. The control algorithm Actrl is taken to be DRC-OGD [39] for known systems.
Theorem 3.4. For h = log T
log ρ−1 , p = T−1/3 and m ≤
√ T , on any contiguous interval I ⊆ [T ],
Algorithm 2 enjoys the following adaptive regret guarantee: E [RegretI(ADA-CTRL); Πdrc(m,RM )] ≤ Õ? ( Lm ( |I| √ E[VarI(G)] + duT 2/3 ))
(3.3)
Proof Sketch. The analysis proceeds by reducing the regret incurred to that over a known system, accounting for: 1) the additional exploration penalty (O(p|I|)), 2) the system misspecification induced error (∼ ∑ t∈I ‖Ĝt − Ḡht ‖`1,op), and 3) truncation errors (∼ ψ(h)|I|). Via straightforward computations, the system misspecification error can be expressed in terms of the result in Theorem 3.2, ultimately leading to an error contribution∼ |I| √ E[VarI(G)]+p−1/2|I|1/2. The analysis is finalized by noting that the chosen p ideally balances p|I| and p−1/2|I|1/2, and that the chosen h ensures that the truncation error is negligible. The full proof can be found in Appendix D. The adaptive regret bound in Eq. (3.3) has two notable terms. Note that the first term |I| √
E[VarI(G)] for I = [T ] matches the regret lower bound in Theorem 3.1. Furthermore, our algorithm is adaptive in this term for all intervals I . On the other hand, for unknown LTI systems with VarI(G) = 0, the algorithm recovers the state-of-the-art bound of T 2/3 [20]. However, the T 2/3 term is not adaptive to the intervals I consistent with the lower bound against strongly adaptive algorithms in Theorem 3.3.
Algorithm 2 DRC-OGD with Adaptive Exploration (ADA-CTRL) 1: Input: p, h,Apred ← ADA-PRED(p, Ĝ0,G(h,RG)), Actrl ← DRC-OGD(m,RM) 2: for τ = 1, . . . , T/h do . let tτ = (τ − 1)h+ 1 3: Set Ĝtτ , Ĝtτ+1, . . . , Ĝtτ+h−1 equal to τ -th iterate Ĝ[τ ] from Apred 4: Draw b[τ ] ∼ Bernoulli(p) 5: for t = tτ , . . . , tτ + h− 1 do 6: if b[τ ] = 1 then 7: Play control ut ∼ {±1}du 8: else 9: Play control ut according to the t-th input chosen by Actrl
10: Suffer cost ct(xt, ut) , observe new state xt+1 11: Extract x̂natt+1 = ProjBRnat ( xt+1 − ∑h−1 i=0 Ĝ [i] t ut−i ) 12: Feed cost, Markov operator and Nature’s x estimates (ct, Ĝt, x̂natt+1) to Actrl. 13: if b[τ ] = 1 then 14: Feed (b[τ ], G̃[τ ]) to Apred, where G̃ [i] [τ ] = xtτ+hu > tτ+h−i, i = 0, 1, . . . , h− 1. 15: else 16: Feed (b[τ ], G̃[τ ]) to Apred, where G̃[τ ] ← ∅.

heading: 4 Online Control over State Feedback
text: Given the impossibility of sublinear regret against DRC/DAC without further restrictions on system variability, this section studies whether sublinear regret is possible against the class of linear feedback
policies. For simplicity, we focus on the state feedback policies ut = Kxt, that is, linear feedback policies with memory m = 1 (Definition 2.3). We note that state feedback policies were the class which motivated the relaxation to DAC policies in the first study of nonstochastic control [3].
We present two results, rather qualitative in nature. First, we show that obtaining sublinear regret is, in the most literal sense, possible. The following result considers regret relative to a class K of static feedback controllers which satisfy the restrictive assumption that each K ∈ K stabilizes the time varying dynamics (At, Bt); see Appendix E for the formal algorithm, assumptions, and guarantees. We measure the regret against this class K:
RegretT (K) := T∑ t=1 ct(xt, ut)− inf K∈K T∑ t=1 ct(x K t , u K t ),
where (xKt , u K t ) are the iterates arising under the control law ut = Kxt.
Theorem 4.1 (Sublinear regret against state-feedback). Under a suitable stabilization assumption, there exists a computationally inefficient control algorithm which attains sublinear expected regret:
E[RegretT (K)] ≤ eΩ(dxdu/2) · T 1− 1 2(dxdu+3) .
Above, Ω(·) suppresses a universal constant and exponent base, both of which are made explicit in a formal theorem statement in Appendix E. The bound follows by running the EXP3 bandit algorithm on a discretization of the set K (high probability regret can be obtained by instead using EXP3.P [8]). The guarantee in Theorem 4.1 is neither practical nor sharp; its sole purpose is to confirm the possibility of sublinear regret. Due to the bandit reduction and exponential size of the cover of K ⊂ Rdu×dx , the algorithm is computationally inefficient and suffers a nonparametric rate of regret [33]: -regret requires T = −Ω(dimension).
One may wonder if one can do much better than this naive bandit reduction. For example, is there structure that can be leveraged? For LTV systems, we show that there is strong evidence to suggest that, at least from a computational standpoint, attaining polynomial regret (e.g. T 1−α for α > 0 independent of dimension) is computationally prohibitive. Theorem 4.2. There exists a reduction from MAX-3SAT on m-clauses and n-literals to the problem of finding a state-feedback controler K which is within a small constant factor of optimal for the cost∑T t=1 ct(x K t , x K t ) on a sequence of sequentially stable LTV systems and convex costs (At, Bt, ct) with no disturbance (wt ≡ 0), with state dimension n+1, input dimension 2, and horizon T = Θ(mn). Therefore, unless P = NP, the latter cannot be solved in time polynomial in n [17].
A more precise statement, construction, and proof are given in Appendix F.4. Theorem 4.2 demonstrates that solving the offline optimization problem over state feedback controllers K to within constant precision is NP-Hard. In particular, this means that any sublinear regret algorithm which is proper and convergent, in the sense that ut = Ktxt for some sequence Kt converges to a limit as T →∞, must be computationally inefficient. This is true even if the costs and dynamics are known in advance. Our result suggests it is computationally hard to obtain sublinear regret, but it does not rigorously imply it. For example, there may be more clever convex relaxations (other than DRC and DAC, which provably cannot work) that yield efficient and sublinear regret. Secondly, this lower bound does not rule out the possibility of an computationally inefficient algorithm which nevertheless attains polynomial regret.

heading: 5 Discussion and Future Work
text: This paper provided guarantees for and studied the limitations of sublinear additive regret in online control of an unknown, linear time-varying (LTV) dynamical system.
Our setting was motivated by the fact that the first-order Taylor approximation (Jacobian linearization) of smooth, nonlinear systems about any smooth trajectory is LTV. One would therefore hope that low-regret guarantees against LTV systems may imply convergence to first-order stationary points of general nonlinear control objectives [34], which in turn may enjoy stability properties [45]. Making this connection rigorous poses several challenges. Among them, one would need to extend our low-regret guarantees against oblivious adversaries to hold against adaptive adversaries, the latter
modeling how nonlinear system dynamics evolve in response to the learner’s control inputs. This may require parting from our current analysis, which leverages the independence between exploratory inputs and changes in system dynamics.
Because we show that linear-in-T regret is unavoidable for changing systems with large system variability, at least for the main convex policy parametrizations, it would be interesting to study our online setting under other measures of performance. In particular, the competive ratio, or the ratio of total algorithm cost to optimal cost in hindsight (as opposed to the difference between the two measured by regret) may yield a complementary set of tradeoffs, or lead to new and exciting principles for adaptive controller design. Does system variability play the same deciding roles in competive analysis as it does in regret? And, in either competitive or regret analyses, what is the correct measure of system variability (e.g. variability in which norm/geometry, or of which system parameters) which best captures sensitivity of online cost to system changes?

heading: Acknowledgments
text: Elad Hazan and Edgar Minasyan have been supported in part by NSF grant #1704860. This work was done in part when Paula Gradu was at Google AI Princeton and Princeton University. Max Simchowitz is generously supported by an Open Philanthropy AI fellowship.

Review summaries:
This paper studies LTV systems control, which is a very challenging problem in my opinion. A set of interesting results have been obtained, including the non-equivalence between different control classes, and algorithms with adaptive regret bounds against different controller classes. Computational complexity in achieving sublinear regret against state-feedback controller has also been discussed.   In general, I think this paper makes interesting contributions. However, I have some reservations on the notion of "adaptive regret". Further, I find some places in the presentation that need more discussions and clarifications.   I will be happy to revise the score after rebuttal if these points are clarified. 

This paper studies online control in linear time-varying (LTV) systems where the dynamics are unknown. The performance metric is the adaptive regret against three common classes of policies. When the benchmark policy class is DRC/DAC, the authors show a lower bound of the adaptive regret of any online controllers that grows linearly with respect to the length of horizon. This negative result demonstrate that the unknown LTV setting is qualitatively harder than either unknown linear time invariant (LTI) or known LTV, where sublinear regrets are achievable. On the other hand, they also propose an online control algorithm whose adaptive regret matches the lower bound in the same setting.  When the benchmark policy class is static feedback controllers, they show that although sublinear regret is achievable under some restrictive assumptions, planning over this policy class is computational inefficient in general.

This paper studies the online control of unknown Linear Time-Varying (LTV) systems in the nonstochastic control setting. They present in-depth theoretical results given the aforementioned problem setting that shows the following (in the order presented in the paper): 1. Statement that the regret for the DAC/DRC policies cannot scale sub linearly in the time horizon (lower bound) 2. An algorithmic upper-bound for online prediction 3. Applying (2) to the online control problem 4.Theoretical analysis showing that sublinear regret is possible but in non-polynomial time (computationally inefficient) unless P=NP)