Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations
Authors: Yiheng Lin
James A Preiss
Emile Timothy Anand
Yingying Li
Yisong Yue
Adam Wierman
Venue: NeurIPS 2023 poster (2023)
Keywords: Online policy selection
online control
online learning

Abstract: We study online adaptive policy selection in systems with time-varying costs and dynamics. We develop the Gradient-based Adaptive Policy Selection (GAPS) algorithm together with a general analytical framework for online policy selection via online optimization. Under our proposed notion of contractive policy classes, we show that GAPS approximates the behavior of an ideal online gradient descent algorithm on the policy parameters while requiring less information and computation. When convexity holds, our algorithm is the first to achieve optimal policy regret. When convexity does not hold, we provide the first local regret bound for online policy selection. Our numerical experiments show that GAPS can adapt to changing environments more quickly than existing benchmarks.

Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations
Yiheng Lin
James A. Preiss California Institute of Technology
California Institute of Technology Pasadena, CA, USA yihengl@canl tehtngl@caltech.. edu
Pasadena, CA, USA
tepreiss@caltech..oo edu
Emile Anand
Yingying Li University of Illinois Urbana- -hhampahn Urbana, IL, USA y1101011linois.c edu
California Institute of Technology
Pasadena, CA, USA Lanandccaltech edu
Yisong Yue California Institute of Technology Pasadena, CA, USA yyue@caltech.ee
Adam Wierman
California Institute of Technology
Pasadena, CA, USA adamw@caltech. edu
Abstract
We study online adaptive policy selection in systems with time-varying costs and dynamics. We develop the Gradient-based Adaptive Policy Selection (GAPS) algorithm together with general analytical framework for online policy selection via online optimization. Under our proposed notion of contractive policy classes, we show that GAPS approximates the behavior of an ideal online gradient descent algorithm on the policy parameters while requiring less information and compu- tation. When convexity holds, our algorithm is the first to achieve optimal policy regret. When convexity does not hold, we provide the first local regret bound for online policy selection. Our numerical experiments show that GAPS can adapt changing environments more quickly than existing benchmarks.
Introduction
We study the problem of online adaptive policy selection for nonlinear time-varying discrete-time dynamical systems. The dynamics are given by Tz+1 (I ut), where I; is the state and u, is the control input time t. The policy class is time-varying mapping π. from the state 2, and policy parameter 0 to control input At every time step f, the online policy incurs a stage cost c = fe( 4e) that depends on the current state and control input. The goal of policy selection is to pick the parameter 6, online to minimize the total stage costs over finite horizon T..
Online adaptive policy selection and general online control have received significant attention recently [1- because many control tasks require running the policy on a single trajectory, as opposed to restarting the episode to evaluate different policy from the same initial state. Adaptivity is also important when the dynamics and cost functions are time-varying. For example, in robotics, time- varying dynamics arise when we control an aircraft under changing wind conditions (9]
This work supported by NSF Grants CNS-2146814, CPS-2136197, CNS-2106403, NGSDI-2105648, CCF. 1918865, and Gift from Latitude AI, with additional support for Yiheng Lin provided by Amazon A14Science Fellowship and PIMCO Graduate Fellowship in Data Science.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we are interested in developing unified framework that can leverage a broad suite of theoretical results from online optimization and efficiently translate them to online policy selec- tion, where efficiency includes both preserving the tightness of the guarantees and computational considerations. A central issue is that, in online policy selection, the stage cost. ea depends on all previously selected parameters (fo..... 12-1) via the state T2. Many prior works along this direction have addressed this issue by on online policy selection, but the bounds are not tight, the computational cost can be large, and the dynamics and policy classes studied are restrictive
reductions. This approach led to the first regret bound
Contributions. We propose and analyze the algorithm Gradient- based Adaptive Policy Selection (GAPS, Algorithm[]] [ to address three limitations of existing results on online policy selection. First, under the assumption that is a convex function of (fo.... 0z), prior work left a log I regret gap between OCO and online policy selection. We close this gap by showing that GAPS achieves the optimal regret of O(VT) (Theorem 3.3 | Second, many previous approaches require oracle access to the dynamics/costs and expensive resimulation from imaginary previous states. In contrast, GAPS only requires partial derivatives of the dynamics and costs along the visited trajectory, and computes (log T) matrix multiplications at each step. Third, the application of existing regret analysis frameworks is limited to specific policy classes and systems because they require et to be convex in (fo..... ..., .t). We address this limitation by showing the first local regret bound for online policy selection when the convexity does not hold. Specifically, GAPS achieves the local regret of O(v(1 + V)T), where V is a measure of how much (gt. Ft, Re) changes over the entire horizon.
To derive these performance guarantees, we develop a novel proof framework based on a general exponentially decaying, or "contractive", perturbation property (Definition 2.6 on the policy-induced closed-loop dynamics. This generalizes a key property of disturbance-action controllers [e.g. 11 g and includes other important policy classes such as model predictive control (MPC) [e.g. 11 and linear feedback controllers [e.g. [2]. Under this property, we prove an approximation error bound (Theorem 3.2), which shows that GAPS can mimic the update of an ideal online gradient descent (OGD) algorithm [3 that has oracle knowledge of how the current policy parameter O, would have performed if used exclusively over the whole trajectory. This error bound bridges online policy selection and online optimization, which means regret guarantees on OGD for online optimization can be transferred to GAPS for online policy selection.
In numerical experiments, we demonstrate that GAPS can adapt faster than an existing follow-th the- leader-type baseline MPC with imperfect disturbance predictions, and outperforms a strong optimal control baseline in a nonlinear system with non-i.i.d. disturbances. The source code for all experi- httpprriiss/aapptieee......... selecciion
ments is published at https: //www gi gith........
Related Work. Our work is related to online control and adaptive-leaminn-bon beanneg---nane control 2
14
especially online control with adversarial disturbances and regret guarantees 7 20 For
example, there is rich literature on policy regret bounds for time-invariant dynamics
2C
2
There also a growing interest in algorithms for varring systems with small adaptive regret
7 21. dynamic regret (23 25), and competitive ratio 22 29 Many prior works study a specific
When applied to linear dynamics De with convex cost functions Jt, DAC renders the stage cost Ct a convex function in past policy parameters (fo...., O.).
policy class called disturbance-action controller (DAC) ПE
Our work contributes to the literature by proposing a general contractive perturbation property that includes DAC as a special case, and showing local regret bounds that do not require e to be convex in (oo...., ,0.). A recent work also handles nonconvex ct, but it studies an episodic setting and requires o, to be "nearly convex", which holds under its policy class 30
In addition to online control, this work is also related online learning/optimization especially online optimization with memory and/or switching costs, where the cost at each time step depends on past decisions. Specifically, our online adaptive policy selection problem is related to online optimization with memory 20 33 39 Our analysis for GAPS provides insight on how to handle indefinite memory when the impact of a past decision decays exponentially with time.
Our contractive perturbation property and the analytical framework based on this property are closely related to prior works on discrete-time incremental stability and contraction theory in nonlinear systems [40 as well as works that leverage such properties to derive guarantees for (online) controllers 47 In complicated systems, it may be hard to design policies that provably satisfy
A concurrent work 10 also closes this gap in less general setting. See Section 3.2 for discussion.

---

C1
Rt
Figure 1: Diagram of the causal relationships between states, policy parameters, con- trol inputs, and costs.
200
47
2/2
Ft
Tt-1
gt
U1
... ft
80
81
8
these properties. This motivates some recent works study neural-based approaches that can learn controller together with its certificate for contraction properties simultaneously (50 [T Our work contributes to this field by showing that, when the system satisfies the contractive perturbation property, one can leverage this property to bridge online policy selection with online optimization.
Notation. We use [t1 :f2 to denote the sequence (41, (f.....;f) f2), dti:to denote (At, ..t))
for 1 < 12, and axr for (o) with repeated 2 0 times. We define g(a, Q) = Qr. Symbols 1 and 0 denote the all-one and all-zero vectors/matrices respectively, with dimension implied by context. The Euclidean ball with center and radius R in R" is denoted by B,, R).
We let |l-|| denote the (induced) Euclidean norm for vectors (matrices). The diameter of a set θ is diam ) sup,,yeo || yll. The projection onto the set θ is IIe(2)) arg min lly ==|.
2 Preliminaries
consider online policy selection on a single trajectory. The setting is discrete-time dynamical system with state 2; R" for time index E T = [0 T a control action 4 E RT, and the next state and the incurred cost are given by:
1]. 1J. At time step E T, the policy picks
Dynamics: T(+1 = (r 42);
Cost: C₃ == fe( ut).
respectively, where (e(;))) is time-varying dynamics function and fe(;,) is time-varying stage cost. The goal is to minimize the total cost Ei-- Ct.
consider parameterized time-varying policies of the form of u, me (T 0z), where x; the current state at time step i. and 0g & is the current policy parameter. O is closed convex subset of IRd. We assume the dynamics, cost, and policy functions {9t, ft, heeT are oblivious, meaning they are fixed before the game begins. The online policy selection algorithm optimizes the total cost by selecting Oe sequentially. We illustrate how the policy parameter sequence 0p.7-1 affects the trajectory { t4 hee and per-step costs co:r-1 in Figure D The online algorithm has access the partial derivatives of the dynamics fi and cost 9r along the visited trajectory, but does not have oracle access to the fe.g for arbitrary states and actions.
We provide two motivating examples for our setting. Appendix H contains more details and a third example. The first example is MPC with confidence coefficients, generalization of 38
Example 2.1 (MPC with Confidence Coefficients). Consider a linear time-varying (LTV) system
ge (21, ux) Aeæ; B wi, with time-varying costs fe(x1, u.) g( Qi) + g(u, R2). At time t, the policy observes {Att+k-1, BL.++-1, Qu:++-1, Ruttk-1-1 (0ea+k-11 1je. where w, is a (noisy) prediction of the future disturbance w,. Then, ny ( 0t) commits the first entry of
++--1
arg argmin Mall
Σ
fT urle) + q( Q)
T=E
Ir+1je = Ay + By + X Wo/e:
8. b. Eelt
11ah and Q a fixed positive-definite matrix. Intuitively. X{ represents level of confidence in the disturbance prediction i steps into the future time step t, with entry being fully confident and 0 being not confident at all.
where 0, = (2 .!...,,!--!)) -
The second example studies a nonlinear control model motivated by 12 47
Example 2.2 (Linear Feedback Control Nonlinear Systems). Consider a time-varying nonlinear control problem with dynamics gi (z,, uz) Ax; + Bu, &g (Zt, Us) costo costs fe(Ei, u.) g(z Q)=

---

que, R). Here, the nonlinear residual 5, comes from linearization and is assumed to be sufficiently small and Lipschitz. Inspired by f12V. we construct an online policy based on the optimal controller
Me - -Kxt for the linear-quaen qitear-uuaruticc regulator T.QR(A, B, Q. R). Specifically, we let Te(21,
- -K (00) where K is a mapping from & to R=x= such that (0t) K|] is uniformly bounded.
2.1 Policy Class and Performance Metrics
In our setting, the state at time / is uniquely determined by the combination of 1) state x, at previous time T < t, and 2) the parameter sequence 8y.-11 Similarly, the cost at time t is uniquely determined by 2, and a Since we these properties often, introduce the following notation. Definition 2.3 (Multi-Step Dynamics and Cost). The multi-step step dynamics gelr between two time steps specifies the state Iı as function of the previous stale Te and previous policy parameters 0 It is defined recursively, with the base case 9r/7 (IT) ) = Rr and the recursive case
9141/7 (I,, 0r.1)= ge(22, Te(21, 0z)), V12T,
in which zt = Or It is defined as Stjr (I,,, 0ra) == Se(ze, ((,,,,T((2,,
i The multi-step cost Sulr specifies the cost as function of x,, and
In this paper, we frequently compare the trajectory of our algorithm against the trajectory that would arise from applying a fixed parameter 0 since time step O, which we denote as (0) == Sejo(ro, 0xt) and (f) == ( (0), 0). A related concept that is heavily used is the surrogate cost F,, which maps single policy parameter real number.
Definition 2.4 (Surrogate Cost). The surrogate cost function is defined as Fe(0) = f+()x(0), (0))
Figure I shows the overall causal structure, from which these concepts follow.
To measure the performance of an online algorithm, we adopt the objective of adaptive policy regret. which has been used by 7 522. It is a stronger benchmark than the static policy regret [ [ and more suited to time-varying environments. We use fx+, 4, 02 JET to denote the trajectory of the online algorithm throughout the paper. The adaptive policy regret R (T) is defined as the maximum difference between the cost of the online policy and the cost of the optimal fixed fixed-paramen parameter policy over any sub-interval of the whole horizon T, i.e.
(T) (fx)=( (Ener (((x),)) inface Eier Fi()))-
(2)
In contrast, the (static) policy regret defined in 11 restricts the time interval / to be the whole horizon T. Thus, a bound on adaptive regret is strictly stronger than the same bound on static regret. Adaptive regret particularly useful in vineing environments like Examples 2.1 and 2.2 because an online algorithm must adapt quickly to compete against a comparator policy parameter that can change indefinitely with every time interval 32 Section 10.2].
In the general case when surrogate costs Fo:r-1 are nonconvex, is difficult (if not impossible) for online algorithms to achieve meaningful guarantees classic regret metrics like (T or static policy regret because they do not have oracle optimization solvers or even the exact knowledge of the surrogate costs. Therefore, we introduce the metric of local regret, which bounds the sum of squared gradient norms over the whole horizon:
RT - IV
Similar metrics have been adopted by previous works on online nonconvex optimization [53 In- tuitively, (T) measures how well the online agent chases the (changing) stationary point of the surrogate cost sequence Fo Since the surrogate cost functions are changing over time, the bound on R² RT( will depend on how much the system {gt, fer m.)ee changes over the whole horizon T. We defer the details to Section 3
2.2 Contractive Perturbation and Stability
In this section, we introduce two key properties needed for our sub-linear regret guarantees in adaptive online policy selection. We define both with respect to trajectories generated by "slowly" time-varying parameters, which are easier to analyze than arbitrary parameter sequences.
2z is an auxiliary variable to denote the state at t under initial state ær and parameters 0r:e-

---

Definition 2.5. We denote the set of policy parameter sequences with E-constrained step size by
(t : 12) = {9tsst E @ || - 0 S e, VT [8 :t 1]}.
The first property we require is an exponentially decaying, or "contractive", perturbation property of the closed-loop dynamics of the system with the policy class. We now formalize this property.
Definition 2.6 (s- (s-Time-varying Contractive Perturbation). The e-time-varying contractive perturba- tion property holds for Rc > 0, C > 0, p E (0, 1), and & 2 0 for any 07 E S5(T :t 1), 1)
|191) (2., 0r:-11= 9t) - - Cp " 1|,, 2111
holds for arbitrary x,,,', E (0, Rc) and time steps 7 S t.
Intuitively, e-time-varying contractive perturbation requires two trajectories starting from different states (in bounded ball) to converge towards each other if they adopt the same slowly time-varying policy parameter sequence. We call the special case of e = 0 time-inarriant contractive perturbation, meaning the policy parameter is fixed. Although it may be difficult to verify the mare-nayingg property directly since it allows the policy parameters change, we show in Lemma 2.8 that time-invarian contractive perturbation implies that the time-varying version also holds for some small >> 0.
The fime-invariant contractive perturbation property is closely related to discrete-time incremental stability [e.g. 45 and contraction theory [e.g. 46. which have been studied in control theory. While some specific policies including DAC and MPC satisfy s-time-varying contractive perturbation globally in linear systems, in other cases it is hard to verify. Our property is local and thus is easier to establish for broader applications in nonlinear systems (e.g., Example 2.2
Besides contractive perturbation, another important property we need is the stability of the policy class, which requires Wo:7-1 can stabilize the system starting from the zero state as long as the policy parameter varies slowly. This property is stated formally below:
Definition 2.7 (e- (e-Time-varying Stability). The e-time-varying stability property holds for Rs > and E 2 0 if. for any fra-1 E S2(T it - 1), [1 (0, 6-:-11) S Rs holds for any time steps 2
Intuitively, --aim--vryying stability guarantees that the policy class To:T-1 can achieve stability if the policy parameters 6o:r-1 vary slowly | Similarly to contractive perturbation, one only needs to verify invarinvar stability (i.e., & and the policy parameter fixed) to claim time-varying stability holds for some strictly positive (see Lemma 2.8 The reason we still use the time-varying contractive perturbation and stability in our assumptions is that they hold for g = + in some cases, including DAC and MPC with confidence coefficients. Applying Lemma 2.8 for those systems will lead to a small, overly pessimistic 8.
2.3 Key Assumptions
We make two assumptions about the online policy selection problem to achieve regret guarantees. Assumption 2.1. The dynamics 90.T-1, policies T0.T-1- and costs forT-1 are differentiable at every time step and satisfy that, for any convex compact sets X C RT, C ER", one can find Lipxchitznesssmooonnees constants (can depend on X and U) such that:
1. The dynamics ge (2, u. is (Lg.z, The policy function ie 0) is (Lm,z) L=z,0)-ipsschitz and (Ln,2) (n,0)-smoone in (z. 0) on X x A.
and (gg.z, (g.)) Eg.u) -mmoohh in (x, u) on X' x U.
3. The stage cost cost function felæ, u) is Liipsschittz and (f (..a) smoooh in (z, u) on X x U.
Assumption 2.1 is general because we only require the Lipschiznnesssmootness of gr and fo to hold for bounded states/actions within A' and U. where the coefficients may depend on 2' and U. Similar assumptions are common in the literature of online control/optimizztion
25 29
Our second assumption is on the contractive perturbation and the stability of the closed-loop dynamics induced by slowly time- varying policy parameter sequence.
Assumption 2.2. Let G denote the set of all possible dynamics/policy sequences {gt, Tehe the environment/policy class may provide. For a fixed e E R220, the e-time-varying contractive pertur- bation (Definition 2.6 holds with (Rc, C, p) for any sequence in G. The e-time-varying stability
This property is standard in online control and is satisfied by DAC 13
g
well Examples 2.1 & 2.2
5

---

(Definition 2.7 holds with Rs < for any sequence in G. We assume that the initial state satisfies |zol| (Rc- Rs)/C. Further, we assume that if [g. ) is the dynamics/policcy at an intermediate time step of a sequence in 9, then the time-invariant sequence {g. π xxx is also in G
Note that Assumption 2.2 is on the joint properties of both the dynamical system and the policy class when composed together in a closed loop. The motivation is to generalize two key properties of linear systems under typical reasonable controllers: 1) the effect of past decisions on the current state decays exponentially fast, and 2) if the system is initialized near the origin, it remains near the origin. We generalize these properties via e-time-varying contractive perturbation (Definition 2.6 and g-time E-time-varying stability (Definition 2.7) respectively. Although Assumption 2.2 may seem complicated to understand, it is less restrictive than the assumptions in the most closely related work (e.g.. M that focus on linear dynamics.
Compared to other settings where contractive perturbation holds globally 0 g 54], Assumption 2.2 only requires it to hold locally in bounded ball B(,, Rc), which becomes important in nonlinear settings. This brings a new challenge because we need to guarantee that the starting state stays within (0, Re) whenever we apply this property in the proof. Therefore, in Assumption 2.2 we assume Ric > Rs + zo Similarly, to leverage the Lipschizzness/smottnesss property, we require
X 2 B0, R2) where Rg 2 C'R + C' + Rs and U = {m(z, 0) E X,0 E O π E 9}. Since the coefficients in Assumption 2.1 depend on X' and U4 we will set X B(0, and R2 = C(ss + 1ool) + Rs by default when presenting these constants. The goal is ensure that the controller never leaves the region where contractive perturbation applies, which is critical for our analysis and again generalizes properties found the literature (e.g., Examples 2.
and H.T..
For some systems, verifying Assumption 2.2 is straightforward (e.g., Example 2.1 In other cases, we can rely on the following lemma, which can convert time-invariant version of the property to general time-varying one. We defer its proof to Appendix C
Lemma 2.8. Suppose Assumption 2. 2 holds for E = 0 and (Rc, C, p, Rs), which satisfies Re > (C + 1)Rg. Suppose Assumption
2. also holds and let X == ((0, R2), where R2 = (C (C++1 +1)2 Then, Assumption 2.2 also holds for ê > 0, (Rc, C,P. Rt)), and vo that satisfies (Rc- Rs) Here, Rs, Rc, P are arbitrary constants that satisfies Rg < Rg < Rc < Rc/(C + 1) and p < ý <1 1. The positive constants É and C are given detailed expressions in Appendix C
Remark 2.9. Lemma 2.8 can also be useful when applied to some parameterized controllers for time-invariant nonlinear systems. For example, the well-known "computtd torque control" feedback linearization controllers for robotic manipulators (see, e.g., (55y) renders the closed-loop dynamics exponentially stable about an equilibrium, and the feedback gains can be parameterized. Thus, it satisfies Assumption 2.2 in neighborhood about the equilibrium, via Lemma 2.8 Even with time-imo iimeiinvaiaant dynamics, the time-varying costs (such as tracking a trajectory determined online) provide setting where selecting the policy parameters online can be beneficial.
Method and Theoretical Results
Our algorithm, Gradient-Bass Adaptive Policy Selection (GAPS), is inspired by the classic online gradient descent (OGD) algorithm 32 (56. with novel approach for approximating the gradient of the surrogate stage cost Fr. In the context of online optimization, OGD works as follows. At each time f, the current stage cost describes how good the learner's 's current decision O, is. The learner updates its decision by taking a gradient step with respect to this cost. Mapping this intuition to online policy selection, the ideal OGD update rule would be the following.
Definition 3.1 (Ideal OGD Update). At time step update 0s+1 = II 17 (..))).
This is because the surrogate cost F, (Definition 2.4 characterizes how good 0, is for time if we had applied 0, from the start, i.e., without the impact of other historical policy parameters 0g.t-1- However, since the complexity of computing V F, exactly grows proportionally to i, the ideal OGD becomes intractable when the horizon T is large.
*For [g, Ther to be in G. it must satisfy other assumptions about contractive perturbation and stability that we impose on G but does not need to occur in real problem instances. We only use this assumption in the proof of Theorem 3.6 and it can be made without the loss of generality for line-invariant dynamics and policy classes.

---

As outlined in Algorithm 1 compare the decompositions, with key differences highlighted colored text:
GAPS uses G2 to approximate (f,) efficiently. To see this, we
min B-AA) Σ
O5
(O.)
Σ b=0
and G. = 00:-b (0)
00c-b 20.00.
GAPS uses two techniques to efficiently approximate (.(( First, we replace the ideal sequence (0t) ((++1) by the actual sequence 80:1. This enables computing gradients along the actual trajectory experienced by the online policy without re- rimiiunaa the trajectory under Oz. Second, we truncate the whole historical dependence at most B steps. This bounds the memory used by GAPS. time-varying contractive perturbation is the key to bound the bias of Gy: Intuitively, in the first step, although 0, becomes more different with 0₂ (exponentially); In the second step, the terms that we discard are exponentially small with respect to B. We provide rigorous bound of the bias in Theorem 3.2 and proof outline in Appendix D
decreases, its impact
fyjo decays more quickly
Algorithm 1 Gradient- based Adaptive Policy Selection (GAPS)
Require: Learning rate 17. buffer length B, initial 8.
I: for = -...., T 1 do
2: Observe the current state It.
3: Pick the control action u, T (I,, 0z).
4: Incur the stage cost C = fc (x ut).
ming B-1,
Ofejo
5: Compute the approximated gradient: G₁
00._b 2u.
b=
6: Perform the update O.+1 IIo GGG))
7: end for
Algorithm α presents GAPS in its simplest form. Although the expression of the partial derivatives contains fort, the time- and space-efficient implementation of GAPS only requires to store B partial derivatives for B previous time steps. Details are given in Algorithm 2 in Appendix B
Compared to many previous online control algorithms that take a reduction approach based on OCO with Memory, our algorithm can be much more computationally efficient (see Appendix I.4 for an take a different f finite-memory reduction
empirical comparison). Specifically, these works I approach toward reducing the online control problem to OCO with Memory removing the dependence on policy parameters before time step In the finite-ment mettey reduction, one must "imaginarily" reset the state time t B be 0 and then use the B-step truncated multi-step cost function f (0, 0.-B:t) in the OGD with Memory algorithm D. When applied to our setting, this equivalent to replacing G, in line D of Algorithm 8f
3 6
B3 by completely
B for fixed memory length B.
20. x0.(0)))(+44) However, the estimator G¹, has limitations compared with G in GAPS. First, computing G² requires oracle access the partial derivatives of the dynamics and cost functions for arbitrary state and actions. Second, even if those are available, Gý is less computationally efficient than G2 in GAPS, especially when the policy is expensive to execute. Taking MPC (Example 2. as an example, computing G², at every time step requires solving B MPC optimization problems when re-simulating the system, where 2ilog T).. In contrast, computing G, in GAPS only requires solving one MPC optimization problem and O(B) matrix multiplications to update the partial derivatives. One may wonder how significant this improvement is, and if affects the regret. To address this concern, we compare GAPS with Ideal OGD and OGD with Memory in the setting of MPC with confidence coefficients for a 2D double integrator. The simulation results show that GAPS achieve very similar regret with the two benchmarks, while the improvement on computation efficiency is significant (see Appendix
by G² = EBD
3.1 Bounds Truncation Error
We now present the first part of our main result, which states that the actual stage cost fe( u.) incurred by GAPS is close to the ideal surrogate cost (0.),, and the approximated gradient G; is close to the ideal gradient V (B..).. In other words, GAPS mimics the ideal OGD update (Definition 3.1
7

---

Theorem 3.2. Suppose Assumptions 2.1 and 2.2 hold. Let {(z,, ue b:) denote the trajectory of GAPS (Algorithm 1 with buffer size B and learning rate r S (1 - -))). Then, we have
(fe( u.) F.((.)) = ((1 - p)>>>) and ||G, - (F)( = ( (1 p) + (1- p)-
where ((-) and O(-) hide the dependence on the Lipschitz/smoothnees constants defined in Assump- tion 2.1 and C. in contractive perturbation - see details in Appendix D.
We defer the proof of Theorem to Appendix D.I Note that this result does not require any
convexity assumptions on the surrogate cost Fi.
3.2
Regret Bounds for GAPS: Convex Surrogate Cost
The second part of our main result studies the case when the surrogate cost F, is a convex function. This assumption is explicitly required or satisfied by the policy classes and dynamical systems in many prior works on online control and online policy selection 3 54
The error bounds in Theorem 3.2 can reduce the problem of GAPS' regret bound in control to the problem of OGD's 's regret bound in online optimization, where the following result is well known: When the surrogate cost functions F; are convex, the ideal OGD update (Definition 3.1 achieves the regret bound Ei- (O.) minsge Σ/=o (0) = O(VT), when the step size v) is of the order 1/vT 12 By taking the biases on the stage costs and the gradients into consideration, we derive the adaptive regret bound Theorem 3.3 Besides the adaptive regret, one can use similar reduction approach to "transfer" other regret guarantees for OGD in online optimization to GAPS in control. We include the derivation of dynamic regret bound as an example in Appendix E
Theorem 3.3. Under the same assumptions as Theorem 3.2 if we additionally assume Fe is convex for every time t and diam(E) is bounded by constant D, then GAPS achieves adaptive regret
RA(T) = 0 + (1 (1- + (1 -) + (1 p) 10 + (1 (1--p) 2) nT),
where (c) hides the same constants as Theorem 3.2 and - see details in Appendix D.
We discuss how to choose the learning rate and the regret it achieves in the following corollary. Corollary 3.4. Under the same assumptions as Theorem 3.3 suppose the horizon length T > T-p and the buffer length B 2 1/2 log(/))/og(///p) If we set 1 = (1 - 3, then GAPS achieves adaptive regret RA
( -))--pp)))
We defer the proof of Theorem 3.3 to Appendix D.I Compared to the (static) policy regret bounds of [13. our bound is tighter by a factor of log T. The key observation is that the impact of a past policy parameter 0,-b the current stage cost Ct decays exponentially with respect to b (see Appendix D for details). In comparison, the reduction-based approach first approximates c, with & that depends on O.- 1:t. and then applies general OCO with memory results on é M B General OCO with memory cannot distinguish the different magnitudes of the contributions that 0.- B- make to é. which leads to the regret gap of B Ollgg T).
In the more restrictive setting of linear time-invariant dynamics with the DAC policy class, the results of concurrent work [00 can also be used to close the log I gap on static regret of online policy selection. In comparison, Theorem 3.3 considers more general time-varying dynamics and adopts the stronger metric of adaptive regret. As practical matter, the follow-the-regularizee algorithm used by [0 is often (much) less computationally efficient than a gradient- brade algorithm like GAPS. Nevertheless, [C made distinct contributions by allowing the state space to be general Banach space and providing a lower bound for OCO with unbounded memory.
type of
3.3 Regret Bounds for GAPS: Nonconvex Surrogate Cost
The third part of our main result studies the case when the surrogate cost FÚ is nonconvex. Before presenting the result, we formally define the variation intensity that measures how much the system changes over the whole horizon.
Definition 3.5 (Variation Intensity). Let (gt, Te, StheT be a sequence of dynamics/plics/cost functions that the environment provides. The variation intensity V of this sequence is defined as
Σ sup [1oc(,, u) 01-1(2,, (xx,,))1++ +) NEE
sup [ 0) =x-1(2, 0)11+
sup [f((z, u) fc (z, u)]-
x0x
8

---

Variation intensity is used as measure of hardness for changing environments in the literature of online optimization that often appear regret upper bounds (see [57] for an overview). Definition 3.5 generalizes one of the standard definitions to online policy selection. Using this definition, we present our main result for GAPS applied to nonconvex surrogate costs using the metric of local regret
Theorem 3.6. Under the same assumptions as Theorem for some integer d, then GAPS satisfies local regret
3.2
if we additionally assume that +
R
(T) ( 0 ( (1-1)1 (1 p)
1+V 1)
nIT
P PT
T
B
+
(1 p)²
(1
p)
(1 1--p) pp5
where O(-) hides the same constants as in Theorem 3.2 see details Appendix
We discuss how to choose the learning rate and the regret it achieves in the following corollary.
Corollary 3.7. Under the same assumptions Theorem 3.6 suppose the horizon length T >> I-P and the buffer length B 2 2 lTg(T)/ log(1/p). Ie set v ()+ GAPS achieves local regret R (T) O((1 - p) $ V)+T)..
We defer the proof of Theorem 3.6 to Appendix F Note that the local regret will be sublinear in T the variation intensity V o("). To derive the local regret guarantee in Theorem 3.6, we address additional challenges compared the convex case. First, we derive local regret guarantee for OGD in online nonconvex optimization. We cannot directly apply results from the literature because they do not use ordinary OGD, and it is difficult to apply algorithms like wewowthe-Perturbelee Leader [e.g. [58 to online policy selection due to constraints information and step size. Then, transfer the regret bound from online optimization to online policy selection, we show how to convert the measure of variation defined - to our variation intensity V defined on {gt, Te, ftJIET
limitation of Theorem 3.6 that we need assume θ is whole Euclidean space so that GAPS will not converge to point at the boundary of θ that is not stationary point. Example 2.2 and Appendix H3 show that one can re-parameterize the policy class to satisfy this assumption some cases. Relaxing this assumption is our future work.
4 Numerical Experiments
In this section compare GAPS to strong baseline algorithms in settings based on Examples 2. and 2.2 Details are deferred to Appendix [uue to space limitations. Appendix also includes a third experiment comparing GAPS to bandit-based algorithm for selecting the planning horizon in MPC, and computation time comparison between GAPS and the alternative gradient approximation
1.0
cenfe A
0.5
GAPS (ours)
A-confident
accurate
0.0
100
200
400
100
2001
300
400
time
Figure 2: Comparing GAPS and baseline 11 for online adaptation of a confidence parameter for MPC with disturbance predictions. Left: Confidence parameter. Right: Per-step cost. Shaded bands show 10%-90% quantile range over randomized disturbance properties. See body for details.
MPC confidence parameter. We compare GAPS the beloo-the-leader-tyee method of |1| for tuning a scalar confidence parameter in model-
control with noisy disturbance predictions. The setting is close Example 2.1 but restricted satisfy the conditions of the theoretical guarantees in [II] We consider the scalar system Ø++1 = 2x, + dt + W/ under non-stochastic disturbances with the cost fe(a,, uz) x + u². For / to 100, the predictions of w, are corrupted by large amount of noise. After / > 100, the prediction noise is instantly reduced by a factor of 100. In this setup, an ideal algorithm should learn to decrease confidence level at first account for the noise, but then increase to À se 1 when the predictions become accurate.

---

Figure 2 shows the values of the confidence parameter À and the per- per-timestep cost generated by each algorithm. Both methods are initialized to À 1. The method of [M] rapidly adjusts to an appropriate confidence level at first, while GAPS adjusts more slowly but eventually reaches the same value. However, when the accuracy changes, GAPS adapts more quickly and obtains lower costs towards the end of the simulation. In other words, we see that GAPS behaves essentially like an instance Ideal OGD with constant step size, which is consistent with our theoretical results (Theorem 3.2
disturbance gaussian
disturbance walk
5k
"regret" GAPS LQR
-0
param
hp
20
Ad
-5k
disturbance
contraller
gaussian
10
OUTS
-00k
200
400
600
1000
200
400
600
1000
time
time
time
(a) Linear gains kp, ka tuned by GAPS compared to LQR optimal.
(b) Cumulative cost difference.
Figure Comparing GAPS and LQQ baseline nonlinear inverted pendulum system. Shaded bands show 1 standard deviation over the randomness of the disturbances. See body for details.
Linear controller of nonlinear time-varying system. We apply GAPS to tune the gain parameters of a linear feedback controller in nonlinear inverted pendulum system. Every 100 seconds, the pendulum mass changes. The system reflects the smooth nonlinear dynamics and nonconvex surrogate
costs in Example 2.2] although it differs in other details (see Appendices H.3 and L.2) We compare GAPS to strong and dynamic baseline that deploys the infinite-horizon Emear-quadratin regulator (LQR) optimal controller for the linearized dynamics at each mass. We simulate two disturbances: random walk.
1) i. Gaussian, and 2)
Figure Sal shows the controller parameters tuned by GAPS, along with the baseline LQR-optimal gains, for each disturbance type. The derivative gain ka closely follows LQR for i.i.d. disturbances but diverges for random-walk disturbances, where LQR no longer optimal. This reflected in the cumulative cost difference between GAPS and LQR, shown in Figure 3b GAPS nearly matches LQR under i.i.d. disturbances, but significantly outperforms it when the disturbance is random walk. The results show that GAPS can both 1) adapt to step changes in dynamics as quickly the comparator that benefits from knowledge of the near-optimal analytic solution, and 2) outperform the comparator in more general settings where the analytic solution no longer applies.
single trajectory almost
5 Conclusion and Future Directions
In this paper, we study the problem of online adaptive policy selection under a general contractive perturbation property. We propose GAPS, which can be implemented more efficiently and with less information than existing algorithms. Under convexity assumptions, we show that GAPS achieves adaptive policy regret of O( O(VT), which closes the log T gap between online control and OCO left open by previous results. When convexity does not hold, we show that GAPS achieves local regret of O(v(1 V)Σ),, where V is the variation intensity of the time-varying system. This is the first local regret bound on online policy selection attained without any convexity assumptions on the surrogate cost functions. Our numerical simulations demonstrate the effectiveness of GAPS, especially for fast adaptation in vime-varying settings.
Our work motivates interesting future research directions. For example, a limitation is that GAPS assumes all policy parameters can stabilize the system and satisfy contractive perturbation. recent work on online policy selection relaxed this assumption by bandit-based algorithm but requires θ to be a finite set [59]. An interesting future direction to study is what regret guarantees can be achieved when e is continuous parameter set and not all of the candidate policies satisfy these assumptions.
10

---

References
[1] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances, In International Conference Machine Learning, pages 111-119. PMLR, 2019.
[2] Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. In Advances Neural Information Processing Systems, volume 32, 2019.
[3] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorithmic Learning Theory, pages 408-48 1.842.1. PMLR, 2020.
[4] Dimitar Ho, Hoang Le, John Doyle, and Yisong Yue. Online robust control of nonlinear systems with large uncertainty. In International Conference on Artificial Intelligence and Statistics, pages 3475-3483. PMLR, 2021.
[5] Dheeraj Baby and Yu- Yu-Xiang Wang. Optimal dynamic regret in LQR control. In Advances in Neural Information Processing Systems, 2022.
[6] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference Learning Theory, pages 1114-1 114. PMLR, 2021.
[7] Paula Gradu, Elad Hazan, and Edgar Minasyan. Adaptive regret for control of time-varying dynamics. CoRR, abs/2007.04399, 2020.
[8] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[9] Michael O' O'Connell, Guanya Shi, Xichen Shi, Kamyar Azizzadenesheli, Anima Anandkumar, Yisong Yue, and Soon-Jo Chung. Neural-fly enables rapid learning for agile flight in strong winds. Science Robotics, 7(66)=abm6659, 2022.
[10] Raunak Kumar, Sarah Dean, and Robert Kleinberg. Online convex optimization with unbounded memory. arXiv preprint arXiv:2210.09903, 2022.
[11] Tongxin Li, Ruixiao Yang, Guannan Qu, Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. Robustness and consistency in linear quadratic control with predictions. Proceedings of the ACM Measurement and Analysis of Computing Systems, 6:1-35. 2021.
[12] Guannan Qu, Chenkai Yu, Steven Low, and Adam Wierman. Exploiting linear models for model-free nonlinear control: A provably convergent policy gradient approach. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 6539-6544 IEEE, 2021.
[13] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference Machine Learning, pages 928-936, 2003.
[14] Yingying Li, Subhro Das, and Na Li. Online optimal control with affine constraints. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8527-8537, 2021.
[15] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. In Advances in Neural Information Processing Systems, volume 33, pages 15312-15325, 2020.
[16] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. In Advances in Neural Information Processing Systems, volume 31, 2018.
[17] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only vt regret. In International Conference on Machine Learning, pages 1300-1309. PMLR, 2019.
[18] Yingying Li, Subhro Das, Jeff S. Shamma, and Na Li. Safe adaptive learning-based control for constrained linear quadratic regulators with regret guarantees. CoRR, abs/21 1.00411, 2021.
11

---

[19] Jing Yu, Dimitar Ho, and Adam Wierman. Online stabilization of unknown networked systems with communication constraints. arXiv preprint arXiv:2203.026:0, 2022.
[20] Dylan Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In International Conference on Machine Learning, volume 19, pages 3211-3221. PMLR, 2020.
[21] Edgar Minasyan, Paula Gradu, Max Simchowitz, and Elad Hazan. Online control of unknown time-varying dynamical systems. In Advances Neural Information Processing Systems, volume 34, pages 15934-15945 2021.
[22] Kim Peter Wabersich and Melanie N. Zeilinger. Performance and safety of bayesian model predictive control: Scalable model-based RI. with guarantees. CoRR, abs/2006.03488. 034483, 2020.
[23] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Advances in Neural Information Processing Systems, volume 33, pages 1994-2004, 2020.
[24] Yingying Li, Xin Chen, and Na Li. Online optimal control with linear dynamics and predic- tions: Algorithms and regret analysis. In Advances in Neural Information Processing Systems, volume 32, 2019.
[25] Yiheng Lin, Yang Hu, Guanya Shi, Haoyuan Sun, Guannan Qu, and Adam Wierman. Perturbation-base regret analysis of predictive control in linear time varying systems. In Advances Neural Information Processing Systems, volume 34, 2021.
[26] Oron Sabag, Sahin Lale, and Babak Hassibi. Optimal competitive-ratio control. CoRR, abs/2206.01782. 2022.
[27] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Competitive control with delayed imperfect information. In 2022 American Control Conference (ACC), pages 2604-2610, IEEE, 2022.
[28] Gautam Goel and Babak Hassibi. Competitive control. CoRR, abs/2107.13657, 2021.
[29] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In Advances in Neural Information Processing Systems, volume 33, pages 20647,20647, 2020.
[30] Xinyi Chen, Edgar Minasyan, Jason D Lee, and Elad Hazan. Regret guarantees for online deep control. Proceedings of Machine Learning Research vol XX, 1:34, 2023.
[31] Peter Auer, Nicolo Cesa-Bian -isanhianchi, Yoav Freund, and Robert Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
[32] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization, 2(3-4):157332 2016.
[33] Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. In Advances in Neural Information Processing Systems, volume 28, 2015.
[34] Chloé Rouyer, Yevgeny Seldin, and Nicolò adversarial bandits with switching costs. In International Conference on Machine Learning. pages 9127-9135. PMLR, 2021.
An algorithm for stochastic and
[35] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. In Advances in Neural Information Processing Systems, volume 32, 2019.
[36] Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non-convex losses. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-32, 2020.
[37] Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Conference On Learning Theory, pages 1574-1594, PMLR, 2018
12

---

[38] Yingying Li, Guannan Qu, and Na Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 66(10))4761-4766 2020.
[39] Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against adaptive adversary: from regret to policy regret. In International Conference on Machine Learning, pages 1747-1754, 2012.
[40] Nicholas M Boffi, Stephen Tu, and Jean-Jacques E Slotine. Regret bounds for adaptive nonlinear control. In Learning for Dynamics and Control, pages 471-483. PMLR, 2021.
[41] Guanya Shi, Kamyar Azizzadenesheli, Michael O' O'Connell, Soon-Jo Chung, and Yisong Yue. Meta-adaptive nonlinear control: Theory and algorithms. In Advances in Neural Information Processing Systems, volume 34, pages 10013-10025, 2021.
[42] Winfried Lohmiller and lean-Jacques E Slotine. On contraction analysis for non-linear systems. Automatica, 34(6))683-696, 1998.
[43] David Angeli. A Lyapunov approach to incremental stability properties. IEEE Transactions on Automatic Control, 47(3):4 2002.
[44] Bjöm S Rüffer, Nathan Van De Wouw, and Markus Mueller. Convergent systems vs. incremental stability. Systems & Control Letters, 62(3):277-288 2013.
[45] Florian Bayer, Mathias Bürger, and Frank Allgöwer. Discrete-time incremental iss: A framework for robust nmpe. In 2013 European Control Conference (ECC), pages 2068-2073. IEEE, 2013.
[46] Hiroyasu Tsukamoto, Soon-Jo Chung, and Jean-Jaques E Slotine. Contraction theory for nonlinear stability analysis and learning-based control: tutorial overview, Annual Reviews in Control, 52:135-169, 2021.
[47] Tongxin Li, Ruixiao Yang, Guannan Qu, Yiheng Lin, Adam Wierman, and Steven H. Low. Certifying black-box policies with stability for nonlinear control. IEEE Open Journal of Control Systems, 2:49-62, 2023.
[48] Hiroyasu Tsukamoto, Soon-Jo Chung, and Jean-Jacques Slotine. Learning-basee based adaptive control using contraction theory. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2533 2538. IEEE, 2021.
[49] Stephen Tu, Alexander Robey, Tingnan Zhang, and Nikolai Matni. On the sample complexity of stability constrained imitation learning. In Learning for Dynamics and Control Conference, pages 180-191. PMLR, 2022.
[50] Charles Dawson, Sicun Gao, and Chuchu Fan. Safe control with learned certificates: A survey of neural Iyapunov, barrier, and contraction methods for robotics and control. IEEE Transactions on Robotics, pages 1-19, 2023.
[51] Dawei Sun, Susmit Jha, and Chuchu Fan. Learning certified control using contraction metric. In Conference on Robot Learning, pages 1519-1539. PMLR, 2021.
[52] Elad Hazan and Comandur Seshadhri. Adaptive algorithms for online decision problems. In Electronic Colloquium on Computational Complexity (ECCC), volume 14, 2007.
[53] Elad Hazan, Karan Singh, and Cyril Zhang. Efficient regret minimization non-convex games. In International Conference on Machine Learning, pages 1433-1441. PMLR, 2017.
[54] Runyu Zhang, Yingying Li, and Na Li. On the regret analysis of online LQR control with predictions. In 2027 American Control Conference (ACC), pages 697-703. IEEE, 2021.
[55] Jcan-Jacques E Slotine, Weiping Li, et al. Applied nonlinear control, volume 199, Prentice hall Englewood Cliffs, NJ, 1991.
[56] Nikhil Bansal and Anupam Gupta. Potential-function proofs for gradient methods. Theory of Computing, 15(1):1-32, 2019.
13

---

[57] Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie. and Alejandro Ribeiro. Online optimiza- tion dynamic environments: Improved regret rates for strongly convex problems. 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195-7201. IEEE, 2016.
[58]
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Algoritimic Learning Theory, pages 845-861. PMLR, 2020.
[59] Yingying Li, James A Preiss, Na Li, Yiheng Lin, Adam Wierman, and Jeff S Shamma. Online switching control with stability and regret guarantees, In Learning for Dynamics and Control Conference, pages 11 1138-1151, PMLR, 2023.
[60] Rolf Schneider. Convex Bodies: the Brunn- Theory. Cambridge University Press, 2014.
[61] Hongyu Zhou, Zirui Xu, and Vasileios Tzoumas. Efficient online learning with memory via Frank-Wolfe optimization: Algorithms with bounded dynamic regret and applications to control. CoRR, abs/2301. 100497, 2023.
[62] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4): 2013.
[63] Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T2/3 regret. In ACM Symposium the Theory of Computing, pages 459 459-467, 2014.
[64] Yiheng Lin, Yang Hu, Guannan Qu, Tongxin Li, and Adam Wierman. Bounded-regret MPC via perturbation analysis: Prediction error, constraints, and nonlinearity. In Advances in Neural Information Processing Systems, 2022.
14


Reviews:
[{"review_id": "V47UumTBki", "reviewer": "Reviewer_1Vdt", "summary": "This paper presents a novel algorithm, Gradient-based Adaptive Policy Selection (GAPS), for online policy selection in time-varying systems. The authors introduce a general analytical framework for online policy selection via online optimization. The paper also provides theoretical guarantees for the performance of the GAPS algorithm under some assumptions on the stability of the dynamical system and on the convexity of the surrogate cost function. Complementary local bounds are also give in the case of nonconvex cost.", "questions": "one main question listed in the weaknesses.", "limitations": "Some of the limitations havebeen listed in the conclusions, but perhaps a more extended discussion about the applicability of the assumptions would be informative.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well-organized and easy to follow, with clear explanations of the theoretical concepts and practical implementation details. The authors provide detailed proofs of their theoretical results in the appendices, as well as numerical experiments to document the performance of the GAPS algorithm in two concrete example settings. \n\nOn the math side, while I did not check the details of the proof, I find the underlying perturbative idea new and interesting, and on a high level the steps of the proof check out.", "weaknesses": "The main weakness of the paper is, given its novelty, that it is hard for the reader to understand how restrictive the set of assumptions that are put on the dynamical systrem. This holds for both assumptions of Theorem 3.3: Convexity of $F$ and $\\epsilon$-time varying contractive perturbation/stability. It is good that the authors give examples of systems where these assumptions hold, and describe in Lemma 2.8 how the time-invariant stability can be translated to these conditions, but I still find it a bit hard to understand how restrictive these conditions are. For instance, I imagine that in the case of a multistable dynamical system the contractive perturbation property would not hold?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments.\n\nOur major assumption (Assumption 2.2) is about the joint properties of both the dynamical system and the policy class when composed together in a closed loop. Thus, it is not particularly restrictive on the dynamical system when one has the freedom to choose/design the corresponding policy class. An example is the design of the disturbance-action controller (DAC) class for linear time-varying (LTV) systems (see Appendix H.1), which is a special case of our setting and has been studied by many previous works in online control [1, 3, 6-8]. Assumption 2.2 is also satisfied by other online control settings including learning-augmented model predictive control (MPC) for LTV systems [10] and linear feedback control in nonlinear systems [11, 46] (see Examples 2.1 and 2.2). We will add a discussion about this in the revision.\n\nThe literature on nonlinear control contains many examples of a parameterized family of controllers for a time-invariant system, each of which renders the closed-loop dynamics exponentially stable about an equilibrium. For example, the well-known “computed torque control” feedback linearization controllers for robotic manipulators, where the feedback gains can be parameterized. These settings satisfy our assumptions in a neighborhood about the equilibrium, via our Lemma 2.8. Even with time-invariant dynamics, the time-varying costs (such as tracking a trajectory determined online) provide an online, possibly adversarial, setting where our algorithm is useful.\n\nWe also want to emphasize that our result about the local regret of GAPS (Theorem 3.6) does not require the surrogate cost $F_t$ to be convex. The convexity assumption is required or satisfied by many previous works on online control [1, 3, 6, 53], and relaxing it is one of our major contributions.\n\nLastly, a dynamical system with multiple stable equilibrium points can still satisfy the contractive perturbation property (Definition 2.6) because the property is only assumed locally in the ball $B_n(0, R_C)$. By controlling the step size of GAPS (Algorithm 1), we can guarantee that the state of GAPS always stays within $B_n(0, R_C)$ (see (25) in Appendix D.5). Therefore, it does not matter if there are other stable equilibrium points out of $B_n(0, R_C)$."}, {"review_id": "LMjHkgQOqB", "reviewer": "Reviewer_hsz4", "summary": "The paper studies online adaptive policy selection in systems with time-varying costs and dynamics. \n\nThis paper proposes an algorithm that obtains optimal regret bound in the convex case and a local regret bound in the non-convex setting with four assumptions: (1) the dynamics are contractive starting from a ball near 0 if the policy has small variations across time. (2) the dynamics starting from 0 never goes out of an even smaller ball if the policy has small variations across time. (3) the dynamics will start from a point that would never go out of the ball in assumption (1). (4) smoothness and Lipschitzness for the dynamics, policy function, and cost functions.\n\nThe algorithm does not require Oracle access to the dynamics.", "questions": "Could you give some examples of dynamics where the assumptions hold? I am giving a low score mainly because I am not very sure that I understand the dynamics of interest. If there are good examples which show that the assumptions are not as severe as vacuous, then I will change my score.", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problems under investigation are interesting.", "weaknesses": "It seems that the restriction on the dynamics is quite severe.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and please find the response to your concerns below.\n\nOur assumptions generalize the assumptions in the most closely related previous work on online control – please see the global rebuttal for details.\n\nThe intricate nature of the contractiveness and stability ball assumptions come from our desire to have local, instead of global, assumptions. Note that in our DAC and MPC examples (Appendix H.1 and H.2) the contractiveness ball has radius $\\infty$.\n\nThe example settings discussed in our paper have each appeared in related work previously with motivating applications:\n\n- Example 1: Learning-augmented model predictive control in linear time-varying systems (Example 2.1), which generalizes the setting studied in the previous work [10] on learning-augmented control. This setting has applications in EV charging and trajectory tracking [10], and we show that it satisfies all of our assumptions in Appendix H.2.\n\n- Example 2: Linear feedback control applied to time-varying nonlinear control (Example 2.2), which was studied in [11, 46] on nonlinear control. This example is practical because it is a standard technique in control engineering to stabilize a nonlinear system about an operating point by linearizing the system and using linear control synthesis. We show it satisfies all of our assumptions in Appendix H.3.\n\n- Example 3: Disturbance-action controllers in linear time-varying systems (Appendix H.1), which has received much attention from previous works on no-regret online control [1, 3, 6]. We show it satisfies all of our assumptions in Appendix H.1.\n\nMore discussion: The literature on nonlinear control contains many examples of a parameterized family of controllers for a time-invariant system, each of which renders the closed-loop dynamics exponentially stable about an equilibrium. For example, the well-known “computed torque control” feedback linearization controllers for robotic manipulators, where the feedback gains can be parameterized. These settings satisfy our assumptions in a neighborhood about the equilibrium, via our Lemma 2.8.  Even with time-invariant dynamics, the time-varying costs (such as tracking a trajectory determined online) provide an online, possibly adversarial, setting where our algorithm is useful."}, {"review_id": "v9QxMEpZL3", "reviewer": "Reviewer_AQ7q", "summary": "This paper proposes a new algorithm, Gradient-based Adaptive Policy Selection (GAPS), for online adaptive policy selection with time-varying dynamics and costs. For analysis, it proposes a general analytical framework for online policy selection. Under this framework, by restricting the problem and policy class to have the contractive perturbation property it identified, GAPS is shown to approximate an ideal online gradient descent algorithm. This results in better regret bounds compared to existing results. When convexity holds, GAPS is the first to achieve optimal regret in this setting; when convexity doesn’t hold, it gives the first local regret bound for online policy selection. Empirical results on two examples in the main text also illustrate GAPS’s better adaptivity to changing environments compared to baselines.", "questions": "1. Though the proposed contractive perturbation property includes some existing works as special cases, I wonder how likely or hard it is to find a more general property.\n\nTypos\n1. In Line 216, it seems that some part is missing after “satisfies”.", "limitations": "As the paper discussed in the Conclusion and Future Directions section, the major limitation of this work may be that the assumptions on the contractive perturbation property and stability are quite strong. It requires the properties should hold for all policy parameters. But still, this work is quite complete, and relaxing the assumptions can be interesting future directions.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The results seem to be significant. First, when assuming convexity, the regret bound of the proposed algorithm improves over existing work and fills a gap in the literature. It is the first to achieve the optimal regret of $O(\\sqrt{(T)})$ under the discussed setting while requiring less information about the problem. Second, when the cost function is nonconvex, it gives the first local regret bound for online policy selection.\n2. The proposed contractive perturbation property and its corresponding analytical framework are general and subsume an existing class (DAC) as well as some known downstream applications. They may be helpful for future research.\n3. The paper is well-written, and the presentation of empirical results is clear, which is convincing.", "weaknesses": "Overall, the paper seems strong to me, and I have a minor suggestion: If possible, it would be nice to have the result of online gradient descent (OGD) oracle in the numerical experiments. This may help the reader gain more understanding about GAPS’s performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and please find the response to your concerns below.\n\n> It would be nice to have the result of online gradient descent (OGD) oracle in the numerical experiments.\n\nThank you for the suggestion. For the rebuttal, we performed an experiment comparing GAPS to the OGD oracle as well as the gradient approximation from the manuscript’s reference [1], which we discussed in lines 239 of the manuscript. Plots are shown in the rebuttal supplement. The setting is MPC with confidence coefficients for a 2D double integrator, as discussed in Appendix I.3 of the manuscript. In the computation time plot, we see that the oracle’s computation time grows quadratically and we must terminate it early. GAPS and the method of [1] both use constant time per step, but GAPS’s constant is smaller. On the regret plots, the three methods are indistinguishable. The final regret of GAPS and [1] differ by less than 0.02%, while the computation time of GAPS is over 15x faster. We can include this result in the final paper.\n\n> I wonder how likely or hard it is to find a more general property than contractive perturbation.\n\nThe goal of contractive perturbation is to guarantee the impact of a previous decision decays quickly over time as long as the policy parameter is changing sufficiently slowly. We believe a similar decay property is needed to address the challenge of indefinite impact of a past error in policy selection. An interesting direction towards relaxing it is to consider the case where only a subset of policy parameters satisfies this property. We will add a discussion about this intuition in revision.\n\n> The assumptions on the contractive perturbation property and stability are quite strong. It requires the properties should hold for all policy parameters.\n\nThanks for pointing this out! As we discussed in Section 5, an interesting future direction is to study what guarantees can be achieved when not all of the candidate policy parameters satisfy these assumptions. It is challenging to detect and rule out the policy parameters that violate these properties when $\\Theta$ is a continuous parameter set, so we leave this direction as future work."}, {"review_id": "EZGiXsYX5D", "reviewer": "Reviewer_FkR7", "summary": "The paper studies online adaptive policy selection for nonlinear systems. The algorithm proposed by the authors, GAPS, is a gradient-based algorithm that achieves the first optimal regret bound in the convex case, and the first local regret bound in the case when convexity does not hold. The authors provided numerical experiments.  ", "questions": "1. Can the authors provide more justifications of Definition 2.7 ($\\epsilon$-time-varying stability)? How does this assumption compare with the standard assumptions made in existing literature? \n\n2. One of the main contributions of the paper is that it closes the $\\log T$ gap between OCO-M based control algorithms and the OGD regret guarantee. However, there are also OCO-M based algorithm that achieves $O(\\sqrt{T})$ bound such as in https://arxiv.org/pdf/2210.09903.pdf. Can the authors compare GAPS to this work?", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The novel approach to the online control problem is interesting and closes the $\\log T$ gap between the currently established bounds for online nonstochastic control and OGD. The paper is well-organized.", "weaknesses": "1. The experiments do not compare the algorithm proposed by the paper to the existing algorithms in online nonstochastic control. It would be interesting to see the comparison against benchmarks in the online control literature including GPC in Algorithm 1, https://arxiv.org/pdf/2211.09619.pdf. \n\n2. Although the analysis is novel, the algorithm proposed is essentially OGD with approximated gradient. The idea of truncation is also very similar to the gradient-based existing algorithms in online control like GPC. \n\n3. To compute the gradient estimator in GAPS, do we need access to all $\\theta_t$'s, requiring storing all $\\theta_t$?  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and please find the response to your comments below.\n\n> It would be interesting to see the comparison against benchmarks in the online control literature including GPC.\n\nThe Gradient Perturbation Control (GPC) in Hazan and Singh, [2022] can be viewed as a special case of our Ideal OGD Update (Definition 3.1) when applied to the disturbance-action controller class in linear time-varying systems. We discussed the major algorithmic differences between GAPS, Ideal OGD, and the finite-memory reduction approach [1] in Section 3.\n\nFor the rebuttal, we compared GAPS to the Ideal OGD as well as the gradient approximation of [1]. Plots are shown in the rebuttal supplement. The setting is MPC with confidence coefficients for a 2D double integrator, as discussed in Appendix I.3 of the manuscript. In the computation time plot, we see that the oracle’s computation time grows quadratically and we must terminate it early. GAPS and the method of [1] both use constant time per step, but GAPS’ constant is smaller. On the regret plots, the three methods are indistinguishable. The final regret of GAPS and [1] differ by less than 0.02%, while the computation time of GAPS is over 15x faster. We can include this result in the final paper.\n\n> The idea of truncation is very similar to the gradient-based existing algorithms in online control like GPC.\n\nAs we discussed before, GPC can be viewed as a special case of our Ideal OGD Update (Definition 3.1) when applying to the disturbance-action controller class in linear time-varying systems. While Ideal OGD does not use truncation, GAPS and the finite-memory reduction approach [1, 3, 6] use the truncation but they approximate the gradients of the surrogate costs in different ways. As we discussed in line 239, Section 3, the design of GAPS enables it to be implemented much more efficiently with less derivative information than existing approaches.\n\n> Does GAPS require storing all previous parameters $\\{\\theta_\\tau\\}_{\\tau \\leq t}$?\n\nNo. The time- and space-efficient implementation of GAPS only requires to store $B$ partial derivatives for $B$ previous time steps (see Algorithm 2 in Appendix B). In revision, we will add a clarification under the simplest form of GAPS (Algorithm 1) that it does not store the previous parameters $\\theta_{0:t}$ in the practical implementation.\n\n> Can the authors provide more justifications of Definition 2.7 ($\\varepsilon$-time-varying stability)?\n\nIntuitively, $\\varepsilon$-time-varying stability holds if any slowly time-varying policy parameter sequence $\\theta_{0:T}$ can achieve stability from state $0$. By Lemma 2.8, one only needs to verify this property for $\\varepsilon = 0$ (any fixed policy parameter) to claim that this property holds for some strictly positive $\\varepsilon$ in our setting. By assuming this property holds, we study the problem of optimizing the policy parameter $\\theta_t$ while the stability issue has been handled by the policy class $\\pi_t$. Handling the case where not all policy parameters can stabilize the system is challenging, and we leave it as a future direction (see Section 5 for a discussion).\n\nWe believe our $\\varepsilon$-time-varying stability property is more general than the combination of disturbance-action controller (DAC) class applied to linear systems (e.g., see Section 6.2.4 of Hazan and Singh, [2022]), which is commonly used in many previous works [1, 3, 6]. Specifically, DAC satisfies $\\varepsilon$-time-varying stability with $\\varepsilon = +\\infty$ when applied to linear time-varying systems, which means arbitrary policy parameter sequences can achieve stability (see Appendix H.1). In contrast, our algorithm and theoretical results also apply to settings where $\\varepsilon$-time-varying stability only holds for small $\\varepsilon$. An example of such settings is linear feedback control in nonlinear systems (see Example 2.2 and Appendix H.3).\n\n> Can the authors compare GAPS to Kumar et al., [2022]?\n\nThank you for pointing out this related work!  This work does indeed close the $\\log T$ regret gap as well, but in a more restricted setting (as discussed below).  Since this paper and the preprint version of our work appeared on arXiv within a week of each other, we will revise our submission to include this paper as concurrent related work.\n\nThere are several major differences between Kumar et al., [2022] and our work. For comparison, one shall view the history vector $h_t$ in Kumar et al., [2022] as our state $x_t$, the decision vector $x_t$ as our policy parameter $\\theta_t$, where the policy $\\pi_t$ is always an identity function (i.e., the control action $u_t = \\pi_t(\\theta_t) = \\theta_t$). Under this mapping of the notations, Kumar et al., [2022] studies a special case of our setting where the dynamics is linear time-invariant and the policy is identity. And one can verify that our Assumptions 1 and 2 hold under their Assumptions A1-A5 when our parameter set $\\Theta$ (corresponds to their $\\mathcal{X}$) is a convex compact set. The main regret upper bound in Theorem 3.1 of Kumar et al., [2022] should be compared with our Theorem 3.3 and Corollary 3.4 because our surrogate cost $F_t$ is convex in their setting. Both regret bounds are in the order of $O(\\sqrt{T})$, while our metric of adaptive regret is stronger than their metric of static regret.  As a practical matter, Kumar et al., [2022] uses a follow-the-regularized-leader type of algorithm, which is often (much) less computationally efficient than our gradient-based algorithm. One distinct contribution of Kumar et al., [2022] is a lower bound for online convex optimization with unbounded memory.\n\n[Hazan and Singh, 2022]: Hazan, Elad, and Karan Singh. \"Introduction to online nonstochastic control.\" arXiv preprint arXiv:2211.09619 (2022).\n\n[Kumar et al., 2022]: Kumar, Raunak, Sarah Dean, and Robert D. Kleinberg. \"Online Convex Optimization with Unbounded Memory.\" arXiv preprint arXiv:2210.09903 (2022)."}, {"review_id": "vhUravl7A8", "reviewer": "Reviewer_r9o3", "summary": "This paper studies online adaptive policy selection for nonlinear time-varying discrete-time dynamical systems. At time step $t \\in\\mathcal{T}$, the policy picks a control action $u_t$, and the next state and the incurred cost are given by $x_{t+1}=g_t\\left(x_t, u_t\\right), c_t:=f_t\\left(x_t, u_t\\right)$, where $g_t(\\cdot, \\cdot)$ is a time-varying dynamics function and $f_t(\\cdot, \\cdot)$ is a time-varying stage cost. The goal is to minimize the total cost $\\sum_{t=0}^{T-1} c_t$. The regret definition in (2) is similar to [52]( https://arxiv.org/pdf/1708.00075.pdf). They require two key properties to achieve sub-linear regret in this time varying systems. Definition 2.6 requires that Intuitively, two trajectories starting from different states (in a bounded ball) to converge towards each other if they adopt the same slowly time-varying policy parameter sequence, and definition 2.7 requires that the policy class $\\pi_{0:T-1}$ can achieve stability if the policy parameters $\\theta_{0:T-1}$ vary slowly. Assumption 2.1 is standard (see [52]( https://arxiv.org/pdf/1708.00075.pdf)) while assumption 2.2 ensures starting state stays within an euclidean ball whenever the dynamics changes. Since the complexity of computing $\\nabla F_t$ exactly grows proportionally to $t$, the key difference in their approach is that their algorithm GAPS uses $G_t$ to approximate $\\nabla F_t\\left(\\theta_t\\right)$ over a batch size of $B$. This results in solving only one MPC optimization problem. Finally in their main theorem 3.6 they show that a regret of $R^L(T)=O\\left((1-\\rho)^{-\\frac{9}{2}}(1+V)^{\\frac{1}{2}} T^{\\frac{1}{2}}\\right)$ is possible without any convexity assumption on $F_t$, where $V$ is the variation intensity of the time-varying system. Finally they empirically validate their algorithm.", "questions": "See weakness section.", "limitations": "1) The writing can be improved. I think you some of the definitions and assumptions can be moved to the section 3. Also the authors need to discuss the results more. It is not clear to me exactly what technical novelty over [52]( https://arxiv.org/pdf/1708.00075.pdf) led to the regret bound of $O(\\sqrt{T})$ which does not include the $\\log T$ factor.\n\n2) The two examples in the main paper seems to be slightly contrived (and i did not see the appendix). Can the authors give moire real life examples where their approach can be used?\n\n3) See weakness section.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) The paper analyzes Online Gradient Descent (OGD) algorithm for time varying systems. They propose the GAPS algorithm which uses the approximate gradient $G_t$ to estimate surrogate function $F_t$. This is also computationally faster than previous methids.\n\n2) They theoretically analyze their algorithm and provide a regret bound of $R^L(T)=O\\left((1-\\rho)^{-\\frac{9}{2}}(1+V)^{\\frac{1}{2}} T^{\\frac{1}{2}}\\right)$ is possible without any convexity assumption on $F_t$, where $V$ is the variation intensity of the time-varying system. This improves over the previous bounds in this setting by a $log(T)$ factor.\n\n3) They show empirically that their algorithm is competitive.", "weaknesses": "\n1) While assumption 2.1 is standard, I think assumption 2.2 is very strong. The implication of the $R_C>R_S+C\\left\\|x_0\\right\\|$ in assumption 2.2 is not clear to me. Moreover $\\mathcal{G}$ is the set of all possible dynamics/policy sequences ${g_t, \\pi_t\\}_{t \\in \\mathcal{T}}$ the environment/policy class may provide and you assume that if $\\{g, \\pi\\}$ is the dynamics/policy at an intermediate time step of a sequence in $\\mathcal{G}$, then the time-invariant sequence $\\{g, \\pi\\} \\times T$ is also in $\\mathcal{G}$. This seems to be very strong assumption. Where do you use it? Are there other works also that require this assumption or is this specific for the time varying system to provide stability?\n\n2) The key novelty in their method lies in using $G_t$ instead of $F_t$ and substituting the ideal sequence by the actual sequence $\\theta_{0: t}$. However, doesn't this approach might introduce additional variance in your estimation of the gradient? How do you control for that? Similarly when you truncate your observation to $B$ timesteps rather than the ideal sequence there must be approximation error creeping into your estimation of $F_t$ through $G_t$. How do you account for that? Also it will be great if you can point out where in the theory you deal with these issues.\n\n3) It is not clear to me how the regret improvement occurs in Theorem 3.3 and Theorem 3.6 that results in a regret of $O(\\sqrt{T})$ (and improves by a factor of $\\log(T)$. The paper has limited discussions on how this happens, and I would like the authors to discuss/clarify this in more details. It will be also great if the authors specifically point out where in their proof the use the assumption 2.1 and 2.2 ti get the improvement. Also why [52]( https://arxiv.org/pdf/1708.00075.pdf) fails to achieve this bound.\n\n4) It makes sense to me that the quantity $V$ occurs in the time-varying system which is similar to the quantity in [Besbes et al.](https://arxiv.org/pdf/1307.5449.pdf). However, it is defined on $f,g$, and policy $\\pi$. Shouldn't this $V$ only depend on the environment dynamics and cost $f,g$? Can you please elaborate on this? Also please point out how it comes up in the proof of Theroem 3.6.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. Please see our global response about the generality and complexity of our assumptions. Detailed responses are below.\n\n> The implication of the $R_C > R_S + C\\|x_0\\|$ in Assumption 2.2 is not clear.\n\nThe goal of Assumption 2.2 is to guarantee that the critical contractive perturbation and stability properties (Definitions 2.6 and 2.7) hold on the trajectory of GAPS when its learning rate is small enough. By assuming $R_C > R_S + C\\|x_0\\|$, we show that any state $x_t$ on the trajectory of GAPS satisfies $\\|x_t\\| \\leq R_S + C\\|x_0\\|$ (eq. (25) in Appendix D.5), so one can apply contractive perturbation from any intermediate state visited by GAPS to bound the partial derivatives of multi-step dynamics/costs (Lemma D.3, Corollary D.4).\n\n> The assumption that “If $g, \\pi$ is the dynamics/policy at an intermediate time-step of a sequence in G, then the time-invariant sequence $g, \\pi$ repeating $T$ times is also in G” seems very strong.\n\nTo clarify, we only need this repeating sequence of $g, \\pi$ to satisfy contractive perturbation and stability, not to occur in real problem instances. We only use this assumption in the proof of Theorem 3.6 (in a rather technical way, see Appendix F). There is no fair comparison with previous works because Theorem 3.6 is the first regret bound for online policy selection with nonconvex surrogate costs. Also, this assumption is without the loss of generality for time-invariant dynamics and policy classes. We will discuss in the revision.\n\n> About variance in our gradient estimation introduced by using the actual parameter sequence $\\theta_{0:t}$ and bounded buffer length $B$.\n\n$\\varepsilon$-time-varying contractive perturbation (Definition 2.6) is the key property that enables us to bound the bias of our gradient estimation. (Our setting is nonstochastic, so it has no variance.) Intuitively, when the learning rate is small, this property guarantees that the actual state/action pair is close to the state/action pair achieved by applying $\\theta_t$ repeatedly since time $0$. This intuition extends to the gradient estimation, formalized in Theorems D.5 and D.6 in the appendix. Discarding the partial derivatives before $b$ steps ago in the expression of $\\nabla F_t(\\theta_t)$ introduces small bias because the magnitude of this partial derivative decays exponentially with respect to $b$ (see Corollary D.4). We will discuss more about this intuition.\n\n> What enables the regret to improve by a factor of $\\log T$ in Theorems 3.3 and 3.6?\n\nAs discussed after Corollary 3.4, the regret bounds in [1, 3] are loose by a factor of $B = O(\\log T)$ because they apply general OCO with memory results. This treats the impact of all inputs $\\theta_{t-B+1:t}$ to the OCO stage cost equally, introducing the factor of $B$. Our problem is more “structured” because the impact of a past parameter $\\theta_{t-b}$ on the current $c_t$ decays exponentially with respect to $b$. We formally state this insight in Corollary D.4, which uses Assumptions 2.1 and 2.2.\n\n> Comparison with [52].\n\n[52] studies online nonconvex optimization, so its regret bounds are not directly comparable with our main results for online policy selection. It is also challenging to use our gradient estimator $G_t$ (4) in the algorithms proposed by [52]. This is because $G_t$, constructed using the actual trajectory experienced by GAPS, is only a good approximation of $\\nabla F_t(\\theta)$ for $\\theta$ that is at or very close to $\\theta_t$. However, line 7 in Algorithm 1 of [52] queries for the gradients that may be far from $\\theta_t$.\n\n> Why should $V$ depend on $f, g,$ and policy $\\pi$?\n\n$V$ depends on $\\pi_t$ because the online agent can only pick the policy parameters $\\theta_t$. The policy classes $\\pi_t$ are given. Even under time-invariant costs and dynamics, time-varying policy classes can change how policy parameters affect the states and actions, which lead to the changes in surrogate cost functions $F_t$.\n\nIn the proof, the terms that measure the variation on policy classes are introduced in equations (48-50) in the proof of Lemma F.4 in Appendix F.3, where we bound the variation of surrogate cost functions $F_t$ by the variation of $f_t, g_t, \\pi_t$.\n\n> The two examples in the main paper seems to be slightly contrived… Can the authors give more real life examples where their approach can be used?\n\nWe are not sure if the Reviewer refers to Examples 2.1 and 2.2 or our two numerical experiments.\n\nWe contend that Example 2.1 can be broadly useful in settings with a complex, but partially predictable disturbance process. The manuscript’s reference [10] gives examples of EV charging and trajectory tracking. Regarding Example 2.2, it models stabilizing a nonlinear system about an operating point by linearization, a standard textbook technique in control engineering.\n\nOur experiments are meant to clearly demonstrate the properties of GAPS that our theory predicts. Experiment 1 shows the fast adaptation predicted by our adaptive (vs. static) regret bound. Experiment 2 shows that we can handle nonlinear systems. Also, the inverted pendulum is a “wrong but useful” approximation of bipedal walking [Grizzle et al., 2014] and a standard benchmark problem.\n\nFor real-life applications, GAPS can be instantiated in almost any system even if one cannot verify all assumptions. The only hard requirement is the smoothness for locally bounded derivatives. By analogy, gradient descent for optimization has strong theoretical guarantees mostly for convex problems, but good empirical performance in much broader settings.\n\nWe are excited to extend GAPS to more complex systems in both theory and practice. The examples/experiments in this paper are a starting point, since we focus on theory for now.\n\n[Grizzle et al., 2014] J.W. Grizzle, C. Chevallereau, R.W. Sinnet, A.D. Ames. \"Models, feedback control, and open problems of 3D bipedal robotic walking.\" Automatica (2014)."}, {"review_id": "Lm1Ev6wVuC", "reviewer": "Reviewer_GGAL", "summary": "This paper proposes an algorithm, GAPS, for online adaptive policy selection in time-varying systems. The algorithm is shown to achieve optimal $O(\\sqrt{T})$ regret based on the contractive perturbation property of the online policy-induced dynamics. Numerical results are provided to verify the performance of GAPS.", "questions": "1. Is it possible to relax the projection step in the algorithm?\n2. It would be interesting to explore the introduction of switching costs in this problem.", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and organized. The insights behind the main results are effectively presented.\n2. The optimal $O(\\sqrt{T})$ regret can be achieved using partial derivatives of the dynamics and costs.", "weaknesses": "1. The results require a slow change of the policy parameter sequences and an $\\epsilon$-time varying contractive perturbation, which cannot handle sudden changes.\n2. There is an additional assumption on the initial state.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and please find the response to your concerns below.\n\n> The results require a slow change of the policy parameter sequences and an $\\varepsilon$-time-varying contractive perturbation.\n\nWe require the policy parameter sequences to change slowly for two reasons: 1. Bound the approximation error introduced by using the efficient gradient estimator $G_t$ (see equation (4)). Note that when there is an `abrupt’ change on the policy parameter, our construction of $G_t$ based on the actual trajectory may not approximate $\\nabla F_t(\\theta_t)$, which comes from using $\\theta_t$ repeatedly since time $0$. 2. Satisfy $\\varepsilon$-time-varying contractive perturbation (see line 257 in Theorem 3.2). Note that when $\\varepsilon = +\\infty$ as in the case of Examples 2.1 and H.1, this constraint is always satisfied. And even when $\\varepsilon$ is a small constant, the constraint can be easily satisfied because we require $\\eta$ to be $O(1/\\sqrt{T})$ to achieve the optimal regret (see Corollaries 3.4 and 3.7).\n\nWe don’t view our requirement for the policy parameters to change slowly as a limitation because this sequence is fully under the control of our algorithm. GAPS ensures that the parameter $\\theta_t$ does not change too fast by using a carefully chosen learning rate $\\eta$ (see Theorem D.5 for the formal statement).\n\n> There is an additional assumption on the initial state.\n\nWe make this assumption to ensure the critical contractive perturbation property (Definition 2.6) is always satisfied at any state visited by our algorithm. Such assumption is necessary because our $\\varepsilon$-time-varying contractive perturbation is locally, and large initial state $x_0$ can make an intermediate state $x_t$ go out of the region $B_n(0, R_C)$ where contractive perturbation holds. This assumption can be relaxed when contractive perturbation holds globally (e.g., Example 2.1).\n\n> Is it possible to relax the projection step in the algorithm?\n\nThank you for mentioning this point! The projection step is a standard way to handle the constraint in many first-order online optimization algorithms (see [31] for a survey). When the parameter set $\\Theta$ is complicated, the projection step might be expensive to compute. An interesting future direction is to design a projection-free algorithm (see Chapter 7 in [31] for a survey) in the setting of online policy selection.\n\n> About introducing the switching costs.\n\nWe didn’t see a direct motivation to introduce switching costs on the decisions (which are the policy parameters $\\{\\theta_t\\}$ in our setting), because GAPS already guarantees that the policy parameter sequence changes slowly. However, it would be interesting to consider more general stage costs. For example, we can allow $c_t$ to also depend on some previous states and actions.\n"}, {"review_id": "7F1lrFd9UN", "reviewer": "Reviewer_5Tn1", "summary": "The paper studies online adaptive policy selection for nonlinear time-varying discrete-time dynamical systems. The algorithm named GAPS is proposed and is shown to achieve optimal regret, which closes the regret gap between online convex optimization (OCO) and online policy selection. En route, a general proof framework based on exponentially decaying perturbation property is developed that connects online policy selection with OCO. Numerical experiments are provided to demonstrate GAPS's superior performance over baselines.", "questions": "I hope the authors can provide clarification for two questions:\n\n1.  Can the authors comment on the necessity of assuming Definition 2.6 and Definition 2.7 for achieving optimal regret?\n\n2. Does the variational intensity or a similar quantity also appear in the analysis of Theorem 3.3 (the convex setting)? What is $V$ in that setting?", "limitations": "Limitations are discussed in Section 3 and the conclusion. In addition to the ones mentioned in the paper, the algorithm also needs the knowledge of problem parameters $\\rho$ and $\\epsilon$ (or $\\rho$ and $V$) to set the learning rate and run optimally.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written. The problem and the results seem significant.", "weaknesses": "A slight weakness is that the algorithm needs $\\Omega(\\log T)$ memory instead of a constant complexity to $T$. I did not spot any major weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments and please find the response to your comments below.\n\n> The algorithm needs $\\Omega(\\log T)$ memory instead of a constant complexity to $T$.\n\nTo the best of our knowledge, there is no algorithm that can achieve sublinear regret with $O(1)$ memory length in our setting. It is possible that this is a fundamental limit of the online policy selection problem.\n\n> The necessity of assuming Definitions 2.6 and 2.7.\n\nWe discuss below about the necessity of Definitions 2.6 and 2.7 respectively.\n\n$\\varepsilon$-time-varying contractive perturbation (Definition 2.6): This assumption guarantees that the impact of a past decision decays quickly over time. Intuitively, general online policy selection is intractable without an assumption that limits the impact of a bad decision in the past. To see this, consider a setting where the dynamics is $x_{t+1} = x_t, \\forall t \\geq 2$. It can satisfy all of our assumptions except contractive perturbation. Any online algorithm may suffer a linear regret in this setting because it cannot foresee the future to choose $\\theta_1$ optimally before the state `freezes’ at time step $2$.\n\nSo we argue that some kind of assumption in the spirit of “forgetting the past” is necessary for sublinear regret in online policy selection. Searching for more general assumptions in this spirit is a future research direction of great interest.\n\n$\\varepsilon$-time-varying stability (Definition 2.7): This assumption guarantees that any slowly-time-varying policy parameter sequence can stabilize the system. Without this assumption, it is possible for the trajectory of GAPS to grow to an unbounded magnitude. This will break our approximation error bounds (Theorem 3.2) and regret bounds (Theorems 3.3 and 3.6) because the gradients and parameter updates are no longer uniformly bounded.\n\n> Does the variational intensity or a similar quantity also appear in the analysis of Theorem 3.3?\n\nNo. Intuitively, a quantity like variational intensity appears in the regret bound when we allow the comparator policy parameters to change over time. For the metric of adaptive regret in Theorem 3.3, the comparator policy parameter is fixed (see equation (2)). In contrast, for the metric of local regret in Theorem 3.6, one can view any local minimizer of $F_t$ as the comparator policy parameter, which is changing over time. Thus, we need to introduce the variational intensity in the regret bound in Theorem 3.6.\n\n> The algorithm also needs the knowledge of problem parameters $\\rho$ and $\\varepsilon$ (or $\\rho$ and $V$) to set the learning rate and run optimally.\n\nIn the literature of online learning/optimization, it is common for the optimal learning rate to depend on the system parameters (see [31] for a survey). In the case when these system parameters are unknown, our Theorems 3.3 and 3.6 also provide regret guarantees for arbitrary learning rates. For example, even when $\\rho$ is unknown, one can still achieve $O(\\sqrt{T})$ regret in Theorem 3.3 with the learning rate $1/\\sqrt{T}$ given that $T >> 1/\\varepsilon$."}]

Author rebuttal:
Several reviewers were concerned that our assumptions are restrictive. We argue that they are perhaps more complicated, but *less* restrictive than the assumptions in the most closely related work (e.g., [1, 3, 7]). In particular, we relax the common linear-time-varying dynamics assumption, and our assumptions are local, which becomes important in nonlinear settings.

The motivation of our assumptions is to generalize two key properties of linear systems under typical controllers: 1) the effect of past decisions on the current state decays exponentially fast, and 2) if initialized near the origin, they remain near the origin. These are generalized by contractive perturbation (Definition 2.6) and time-varying stability (Definition 2.7) respectively.

The remaining assumptions are more technical in nature, but their main purpose is to ensure that the online controller 1) never leaves the region where contractive perturbation applies, and 2) the magnitude of the state does not grow to be unbounded. These two properties are critical for our analysis of GAPS, and are again generalizations of properties found in the literature (e.g., Examples 2.1, 2.2, and H.1).

Please see our responses to the individual reviews for more details about the generality/strength of our assumptions.

Meta-review: This paper had generally favorable reviews along with one strong support in the form a score of 7. The reviewers appreciated the presentation and the non-convex local regret bound. On the other hand, I hope the authors can, in accordance with the reviewers' wishes, expand on the discussion regarding the applicability of the contractivity assumption to nonlinear systems.

I am happy to tentatively recommend this paper for acceptance.
Decision: Accept (poster)