Online Convex Optimization with Unbounded Memory
Authors: Raunak Kumar
Sarah Dean
Robert Kleinberg
Venue: NeurIPS 2023 poster (2023)
Keywords: online learning
online convex optimization
online linear control
TL;DR: We introduce an online convex optimization framework that captures long-term dependence of current losses on past decisions. We prove matching upper and lower bounds on policy regret, and derive strong regret bounds for a variety of problems.

Abstract: Online convex optimization (OCO) is a widely used framework in online
  learning. In each round, the learner chooses a decision in a convex set and an
  adversary chooses a convex loss function, and then the learner suffers the
  loss associated with their current decision. However, in many applications the
  learner's loss depends not only on the current decision but on the entire
  history of decisions until that point. The OCO framework and its existing
  generalizations do not capture this, and they can only be applied to many
  settings of interest after a long series of approximation arguments. They also
  leave open the question of whether the dependence on memory is tight because
  there are no non-trivial lower bounds. In this work we introduce a
  generalization of the OCO framework, ``Online Convex Optimization with
  Unbounded Memory'', that captures long-term dependence on past decisions. We
  introduce the notion of $p$-effective memory capacity, $H_p$, that quantifies
  the maximum influence of past decisions on present losses. We prove an
  $O(\sqrt{H_p T})$ upper bound on the policy regret and a matching (worst-case)
  lower bound. As a special case, we prove the first non-trivial lower bound for
  OCO with finite memory~\citep{anavaHM2015online}, which could be of
  independent interest, and also improve existing upper bounds. We demonstrate
  the broad applicability of our framework by using it to derive regret bounds,
  and to improve and simplify existing regret bound derivations, for a variety
  of online learning problems including online linear control and an online
  variant of performative prediction.

Online Convex Optimization with Unbounded Memory
Raunak Kumar
Sarah Dean Department Computer Science Cornell University Ithaca, NY 14853 sdean@cornell.co edu
Department of Computer Science Cornell University Ithaca, NY 14853
raunakōcs. cornell edu
Robert Kleinberg
Department of Computer Science
Cornell University Ithaca, NY 14853
rdk#cs cornell edu
Abstract
Online convex optimization (OCO) is widely used framework in online learning. In each round, the learner chooses decision in convex and adversary chooses convex loss function, and then the learner suffers the loss associated with their current decision. However, in many applications the learner's loss depends not only on the current decision but on the entire history of decisions until that point. The OCO framework and its existing generalizations do not capture this, and they can only be applied many settings of interest after long series of approximation arguments. They also leave open the question of whether the dependence on memory is tight because there are no non-trivial lower bounds. In this work we introduce a generalization of the OCO framework, "Online Convex Optimization with Unbounded Memory", that captures long-term dependence on past decisions. We introduce the notion of p-effective memory capacity, Hn, that quantifies the maximum influence of past decisions on present losses. We prove an O ((HHTTT upper bound on the policy regret and matching (worst-case) lower bound. As a special case, we prove the first non-trivial lower bound for OCO with finite memory [Anava et al., 2015], which could be of independent interest, and also improve existing upper bounds. We demonstrate the broad applicability of our framework by using it derive regret bounds, and improve and simplify existing regret bound derivations, for variety of online learning problems including online linear control and an online variant of performative prediction.
Introduction
Numerous applications are characterized by multiple rounds of sequential interactions with an environment, e.g., prediction from expert advice [Littlestone and Warmuth, 1989, 1994], portoflio selection [Cover, 1991], routing [Awerbuch and Kleinberg, 2008], etc. One of the most popular frameworks for modelling such sequential decision-making problems is online convex optimization (OCO) [Zinkevich, 2003]. The OCO framework is as follows. In each round, the learner chooses decision in convex set and an adversary chooses a convex loss function, and then the learner suffers loss associated with their current decision. The performance regret: the difference between the algorithm's total loss and that of the best fixed decision. We refer the reader to Shalev-Shwand [2012], Hazan [2019], Orabona [2019] for surveys on this topic.
an algorithm measured by
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, in many upplications the loss of the learner depends not only on the current decisions but on the entire history of decisions until that point. For example, in online linear control [Agarwal et al., 2019b], in each round the learner chooses "control policy" (i.e., decision), suffers loss that a function of the action taken by this policy and the current state of the system, and the system's state evolves according to linear dynamics. The current state depends on the entire history of actions and, therefore, the current loss depends not only on the current decision but the entire history of decisions. The OCO framework cannot capture such long-term dependence of the current loss on the past decisions and neither can existing generalizations that allow the loss to depend on a constant number of past decisions [Anava et al., 2015]. Although series of approximation arguments can be used to apply finite memory generalizations of OCO to the online linear control problem, there is no OCO framework that captures the complete long-ter long-term dependence of current losses on past decisions. Furthermore, there are no non-trivial lower bounds for OCO in the memory setting," which leaves open the question whether the dependence memory is tight.
Contributions. In this paper we introduce generalization of the OCO framework, "Online Convex Optimization with Unbounded Memory" (Section 2), that allows the loss in the current round to depend on the entire history of decisions until that point. We introduce the notion of p-effective memory capacity, Hp. that quantifies the maximum influence of past decisions on present losses. We prove an O( /H,T) upper bound on the policy regret (Theorem 3.1) and a matching (worst-case) lower bound (Theorem 3.2). As special case, we prove the first non-trivial lower bound for OCO with finite memory (Theorem 3.4), which could be of independent interest, and also improve existing upper bounds (Theorem 3.3). Our lower bound technique extends existing techniques developed for memoryless settings. We design novel adversarial loss functions that exploit the fact that an algorithm cannot overwrite its history. We illustrate the power of our framework by bringing together the regret analysis of two seemingly disparate problems under the same umbrella. First, we show how our framework improves and simplifies existing regret bounds for the online linear control problem [Agarwal et al., 2019b] in Theorem 4.1. Second, we show how our framework can be used derive regret bounds for online variant of performative prediction [Perdomo et al., 2020] in Theorem 4.2. This demonstrates the broad applicability of our framework for deriving regret bounds for variety of online learning problems, particularly those that exhibit long-term dependence of current losses on past decisions.
Related work. The most closely related work to ours is the OCO with finite memory frame- work [Anava et al., 2015]. They consider generalization of the OCO framework that allows the current loss to depend on a constani number of past decisions. There have been a number of follow-up works that extend the framework in a variety of other ways, such non-stationarity [Zhao et al., 2022], incorporating switching costs [Shi et al., 2020], etc. However, none of these existing works go beyond constant memory length and do not prove non-trivial lower bound with dependence on the memory length. In a different line of work, Bhatia and Sridharan [2020] consider a much more general online learning framework that goes beyond constant memory length, but they only provide non-constructive upper bounds on regret. In contrast, our OCO with unbounded memory framework allows the current loss depend on an unbounded number of past decisions, provides constructive upper bounds on regret, and lower bounds for a broad class of problems that includes OCO with finite memory with a general memory length m.
A different framework for sequential decision-making is multi-armes bandits [Bubeck and Cesa- Bianchi, 2012, Slivkins, 2019]. Qin et al. [2023] study variant of contextual stochastic bandits where the current loss can depend on a sparse subset of all prior contexts. This setting differs from ours due to the feedback model, stochasticity, and decision space. Reinforcement learning [Sutton and Barto, 2018] is yet another popular framework for sequential decision Decision-making that considers very general state- action models of feedback and dynamics. In reinforcement learning one typically measures regret with respect to the best state-action policy from some policy class, rather than the best fixed decision in online learning and OCO. In the special case of linear control, policies can be reformulated as decisions while preserving convexity; we discuss this application in Section 4. Considering the general framework is an active area of research.
We defer discussion of related work for specific applications to Section 4.
'The trivial lower bound refers to the 2( lower bound for OCO in the memoryless setting.
2

---

2 Framework
We begin with some motivation for the formalism used in our framework (Section 2.1). Many real-world applications involve controlling a physical dynamical system, for example, variable-speed wind turbines in wind energy electric power production [Boukhezzar and Siguerdidjane, 2010]. The typical solution for these problems has been to model them as offline control problems with linear time- invariant dynamics and use classical methods such as LQR and LQG [Boukhezzar and Siguerdidjane, 2010]. Instead of optimizing over the space of control inputs, the typical feedback control approach optimizes over the space of controllers, i.e., policies that choose a control input as a function of the system state. The standard controllers considered in the literature are linear controllers. Even when the losses are convex in the state and input, they are nonconvex in the linear controller. In the special case of quadratic losses in terms the state and input, there is a closed-form solution for the optimal solution using the algebraic Riccati equations [Lancaster and Rodman, 1995]. But this does not hold for general convex losses resulting in convex reparameterizations such as Youla [Youla et al., 1976, Kučera, 1975] and SLS [Wang et al., 2019, Anderson et al., 2019]. The resulting parameterization represents an infinite dimensional system response and is characterized by sequence of matrices. Recent work has studied an online approach for some of these control theory problems, where a sequence of controllers is chosen adaptively rather than choosing one offline YAbbasi-Yadkori and Szepesvári, 2011, Dean et al., 2018, Simchowitz and Foster, 2020, Agarwal et al., 2019b].
The takeaway from the above is that there are online learning problems in which (i) the current loss depends on the entire history of decisions; and (ii) the decision space can be more complicated than just subset of Rd, e.g., it can be an unbounded sequence of matrices. This motivates us to model the decision space as Hilbert space and the history space as a Banach space in the formal problem setup below, and this subsumes the special cases of OCO and OCO with finite memory. This formalism not only lets us consider a wide range of spaces, such as Rd, unbounded sequences of matrices, etc., but also lets define appropriate norms on these spaces. This latter feature is crucial for deriving strong regret bounds for some applications such as online linear control. For this problem we derive improved regret bounds (Theorem 4.1) by defining weighted norms the decision and history spaces, where the weights are chosen to leverage the problem structure.
Notation. We use ||- le to denote the norm associated with space 4. The operator norm for a linear L operator from space 4 - V defined as [[ = m| [[Lu|ly For convenience, sometimes we simply use || || when the meaning is clear from the context. For finiteddimensional matrix we use || || and ||2 to denote its Frobenius norm and operator norm respectively.
2.1
Setup
Let the decision space X' be a closed and convex subset of a Hilbert space W with norm || ||x and the history space H be a Banach space with norm || ||.- Let A : ' - H and B : W + 7 be linear operators. The game between the learner and an oblivious adversary proceeds follows. Let T denote the time horizon and ft H + IR be loss functions chosen by the adversary. The initial history is ho 0. In each round E [T'. the learner chooses 2, E X, the history is updated to hy = A + Br, and the learner suffers loss fe An instance of an online convex optimization with unbounded memory problem is specified by the tuple (X, H, A, B).
We use the notion of policy regret [Dekel et al., 2012] as the performance measure in our framework. The policy regret of a learner is the difference between its total loss and the total loss of strategy that plays the best fixed decision in every round. The history after round t for a strategy that chooses & in every round is described by he = Σt- : A Bx. which motivates the following definition.
Definition 2.1. Given f+ : 7 > IR, the function f. X' -> TR is defined by fe(x) = f( A Br).
Definition 2.2 (Policy Regret), The policy regret of an algorithm A is defined as RT(A) =
EL fhh) mingex Ii, (z)
In many motivating examples such as online linear control (Section 4.1., the history at the end of round is a sequence linear transformations of past decisions. The following definition captures this formally and we leverage this structure to prove stronger regret bounds (Thcorem 3.1).
3

---

Definition 2.3 (Linear Sequence Dynamics), Consider an online convex optimization with unbounded memory problem specified by (X, H. A, B). Let (Ex) be sequence of nonnegative real numbers satisfying ço = 1. We say that (X, H. A, B) follows linear sequence dynamics with the g-weighted p-norm for p 2 1 if
1. H. is the f-weighted ( dirritect sum of finite countably infinite number of copics of W: every element E H is sequence y = (yi)ezz, where I N or I { nj for some n E N, and ||ll (Eiez(E
1/2 co.
2. We have Ayoo Ayo..1.......................... V1....) = (0, AoYo. A1 .1.1....), where A, W - W are linear operators.
3. The operator B satisfies (xx) = (x, 0,... O,...)
Note that since the norm on H depends on the weights &, the operator norm ||A*1] also depends on g. If the weights are all equal to 1, then we simply say p-norm instead of g-weighted p-norm.
2.2 Assumptions
We make the following assumptions about the feedback model and the loss functions.
A1
The learner knows the operators and B, and observes ft at the end of each round t. A2 The operator norm of B is at most 1, i.e., ||B]| S 1.
A3 The functions ft are convex.
A4 The functions ft are L-Lipschitz continuous: h, H and E [2], we have [fe(h)
[e(h)] < Ll/h- - Tilla
Regarding Assumption A1, our results casily extend to the case where instead of observing fc- the learner receives a gradient fe(x)) from a gradient oracle, which can be implemented using knowledge of fi and the dynamics A and B. Handling the cases when the operators A and B are unknown and/or the learner observes bandit feedback (i.e., only ft (h,)) are important problems and we leave them future work. Note that our assumption that A and B are known is more restrictive than in the existing literature on OCO with finite memory [Anava et al., 2015] where is assumed that the learner knows the constant memory length. In fact, our assumption is more general because our framework not only captures constant memory length as a special case but allows for richer dynamics as we illustrate in Section 4. Assumption A2 is made for convenience, and amounts to rescaling of the problem. Assumption A3 can be replaced by the weaker assumption that fa are convex (similar to the literature on OCO with finite memory [Anava et al., 2015]) and this is what we use in the rest of the paper.
Assumptions A1 and A4 imply that f. are i-Lippschtz continuous for the following L.
Theorem 2.1. Consider an online convex optimization with unbounded memory problem spec- ifsed by (X, H. A, B). If ft is L-Lipschitz continuous, then fe is L-Lipschitz continuous for L - L k ||AF (X, H. A, B) follows linear sequence dynamics with the E-weighted p-norm for p 1, then i. < T. (E ||
The proof follows from the definitions of f, and || ||x, and we defer it to Appendix A. The above bound is tighter than similar results in the literature on OCO with finite memory and online linear control. This theorem is a key ingredient, amongst others, in improving existing upper bounds on regret for OCO with finite memory (Theorem 3.3) and for online linear control (Theorem 4. 4.1). Before presenting our final assumption we introduce the notion of p-effective memory capacity that quantifies the maximum influence of past decisions on present losses.
Definition 2.4 (p-Effective Memory Capacity). Consider online convex optimization with un- bounded memory problem specified by (X', H, A, B). For p 2 1, the p-effective memory capacity is defined as
8
H2(X, H. A)
Σ
k 1
(1)

---

When the meaning is clear from the context we simply use Hp instead. The p-effective memory capacity an upper bound on the difference in histories for two sequences of decisions whose difference grows at most linearly with time. To see this, consider two sequences of decisions, (Ia) and (Rx), whose elements differ by no more than at time k: || - S& || Σ k. Then the histories generated
by the two sequences have difference between bounded as || - bll = || Ex A B( - Rx)ll _ >x A|| & > ||||A*|| = H1, where the last inequality follows from Assumption A2. A
similar bound holds with Hp instead when (X, H. A, B) follows linear sequence dynamics with the g-weighted p-norm.
A5 The 1-effective memory capacity is finite, i... H1
Since Hp is decreasing in p. H1 < oo implies Hp < oo for all p 2 1. For the case of linear sequence dynamics with the g-weighted p-norm it suffices make the weaker assumption that Hp 00. However, for simplicity of exposition, we assume that H1 < 00.
2.3 Special Cases
OCO with Finite Memory. Consider the OCO with finite memory problem with constant memory length m. It can be specified in our framework by (X', H. Annite Bunite where H. is the e². direct sum of m copies of X, Ammiee, (al/m),..,,,)). z!!)
(0, (0.=!!).... x22)). and Bimine, (2) = Note that (X, H. Aimme.m: Binite.n . follows linear sequence dynamies with the 2-norm. Our framework can even model an extension where the problem follows linear sequence dynamics
(xr, ..... 0).
with the p-norm for p 2 1 by simply defining H to be the (P-direct sum of m copies of X.
OCO with p-discounted Infinite Memory. Our framework can also model OCO with infi- nite memory problems that are not modelled by existing OCO frameworks. Let p (0. 1) be the discount factor and p 2 1. An OCO with p-discounted infinite memory problem is specified by (X' H. Ainfinite.p Bintinie.p); where H is the ( (d-direct sum of countably many copies of X, Ainfinite,p V1....)) (X, H. Amnimite. Binfimte.p) follows linear sequence dynamics with the p-norm. Due to space con- straints we defer proof's of regret bounds for this problem to the appendix.
(0. Plo- PU),.... .) and Bininite,
(x, .. Note that
3 Regret Analysis
We present two algorithms for choosing the decisions 2₁. Algorithm uses follow-the-regulaaizeed leader (FTRL) [Shalev-Shwarte and Singer, 2006, Abernethy al., 2008] the loss functions ft- Due to space constraints, we discuss how to implement it efficiently in Appendix G and present simple simulation experiments in Appendix I. Algorithm 2, which we only present in Appendix H, combines FTRL with a mini-batching approach [Dekel et al., 2012, Altschuler and Talwar, 2018, Chen al., 2020] additionally guarantee that the decisions switch most O(TL/I.H) times. We defer the proofs of the following upper and lower bounds to Appendices C and D respectively.
Algorithm 1: FTRL
Input Time horizon T', step size 1), a-strongly-convex regularizer R: X + R. Initialize history hnp = O.
2 for t = 1, 1,2...., T.....Ta do
Learner chooses E arg migminzea Ei=l fa(x)) R(x) Set f4 Ah,- Bui,
Learner suffers loss Seg) and observes fc-
6 end
Theorem 3.1. Consider online convex optimization with unbounded memory problem specified by
(X, H. A, B). Let the regularizer R X + IR be a-strongly-conver and satisfy [R(x) - -R()) < D
for all x. Z e X. Algorithm I with step-size n satisfies (F(FTR I
D 7 Tī' TLLH. If
5

---

oD " V +
then
RT (FTR)) < so (VPrrim
When (X, H. A, B) follows linear sequence dynamics with the E-weighted p-norm, then all of the above hold with Hy instead of H1.
fe(xx) The proof of this theorem involves writing the regret as (z.)) Si(z,) fe(a")
and bounding the first term using the p-effective memory capacity and the second term using FTRL. We defer the full proof to Appendix C. The following lower bound shows that this is tight in the worst-case.
Theorem 3.2. There exists an instance of the online convex optimization with unbounded memory problem, (X, H. A, B), that follows linear sequence dynamics with the E-weighted p-norm and there exist I--iipschitz continuous loss fanctions (Se satisfies
BR such that the regret of any algorithm A
(A 20 (VTLHH,)
The proof of this theorem follows from our lower bound for the special case of OCO with finite memory (Theorem 3.4), which diseuss in detail below. However, show in Appendix D, the lower bound holds for much broader class of problems.
Specialization to OCO with finite memory. Now we show how our bounds specialize to the special case of OCO with finite memory (Section 2.3). Due to space constraints, we defer the specialization of the upper and lower bounds for OCO with p-discounted infinite memory (Section 2.3) to Appendix and Appendix D respectively.
Theorem 3.3. Consider an online convex optimization with finite memory problem with constant memory length m specified by (X, nm Ajiniemm Bjinte, Let the regularizer R X -> TR be a- settrnnllycomeee and satisfy RR()) - R(ã) & D for all x, &t X. Algorithm I with step-size
n
oD
satisfies
TiiLm +L)
D (V so m TL2
(F So
This follows from using the definition of Asnite, to bound L and H2 in Theorem 3.1. This improves existing results [Anava et al., 2015] by a factor of m 1/1 Our bound depends on the Lipschitz continuity constants as VLŻ whereas existing bounds depend as L, and can be as large as vmL (Theorem 2.1). We defer the full proof to Appendix C and detailed comparison with existing results to Appendix C.I. The following lower bound shows that this is tight the worst-case.
Theorem 3.4. There exists an instance of the online convex optimization with finite memory problem with constant memory length m, (X, H. X Afmite m. Bunite mn). and there exist L-Lipschitz continuous loss functions (fe H + +R such that the regret of any algorithm A satisfies
Rr Ω (
To the best of our knowledge, this is the first non-trivial lower bound for OCO with finite memory with an explicit dependence on the memory length m. Our construction involves three main steps, the first two of which are loosely based Altschuler and Talwar [2018]. First, divide time into N T/m blocks of size m. (For simplicity, assume T' is a multiple of m.) Second, sample a random sign c, for each block [N]. Third, for t. choose
f(( E
Lm (6)
Ft- + Fmal & 1111:
(8)
(0)

---

where term (a) is the random sign sampled for the block n = [t/m] that belongs to, term (b) is scaling factor chosen while respecting the Lipschitz continuity constraint, and term (c) sum over subxet of past decisions. Two important features of this construction are: (i) a random sign is sampled for each block rather than each round; and (ii) the loss round depends on the history of decisions until and including the first round of the block that & belongs to. These exploit the fact that an algorithm cannot overwrite its history and penalize it for its past decisions even after it observes the random sign en for the current block. (See Fig. 1 for an illustration.) Existing lower bound proofs for OCO sample a random sign in each round and choose fz(x²) X Ex A first attempt at extending this for the OCO with finite memory setting would be to choose fe(he) x < Em-1 T However, in constrast to our approach, this does not exploit the fact that an algorithm cannot overwrite its history and does not suffice for obtaining a matching lower bound.
T 12, m 3, I. I.
Resample every mn rounds.
C2
64
121
25
26
210
211
212
Time
(22 Da x.)) fa(ha) = cg 3
3 à (ayg x4) (bsss
fa(ha) = <g 3 (m44)
Figure 1: An illustration of the loss functions fa for the OCO with finite memory lower bound.
Comparison of upper bound with prior work. The algorithmic ideas and analysis for our regret upper bound are influenced by Anava et al. [2015]. However, an important innovation in our work is the use of weighted norms in the case of linear sequence dynamics. This is simple but powerful way of encoding prior knowledge about problem, and allows to derive non-trivial regret bounds historics. The technical complications that arise are captured in bounding the relevant quantities of interest, e.g., the Lipschitz constant L, the operator norm ||A|], [], etc. Furthermore, using weighted norms even leads to improved regret bounds for some applications. Indeed, consider the application to online linear control with adversarial disturbances (Section 4.1). Our framework and upper bound applied to this problem (Theorem 4.1) improve upon the existing upper bound, which used a finite memory approximation. See Lemmas E.2 and E.6 for an illustration of the technical details involved when using weighted norms.
in the case of unbounded-lengee
4 Applications
In this section we apply our framework to online linear control (Section 4. and online performative prediction (Section 4.2). We defer expanded details and proofss to Appendices E and F respectively.
4.1 Online Linear Control
Background. Online linear control (OLC) is the problem of controlling a system with linear dynamics, adversarial disturbances, and adversarial and convex losses. It combines aspects from control theory and online learning. We refer the reader Agarwal et al. [2019b] for more details. Here, we introduce the basic mathematical setup of the problem.
Let S C I. and U C dd denote the state and control spaces. Let s, and un denote the state and control at time with 8p being the inital state. The system evolves according to the linear dynamics 8141 Fs, + Gu+ + Wt, where F E xd, G &dd are matrices satisfying || ||G||2 and w; E Rd. is an adversarially chosen disturbance with ||ll| < W. Without loss of generality, we assume that K. W 2 1, d, = d, = d, and also define w = Su- For L = O,.... .,, T 1, let c: S - [0, 1] be convex loss functions chosen by oblivous adversary. The functions c satisfy the following Lipschitz condition: if ||s||2. |u
|| L (s, u)ll S Dx The goal in online linear control is to choose sequence of policies that yield sequence of controls 4, minimize the regret (II) Σi= ce u,) ming en Σ ce(s7" ur ). where 8, evolves according to linear dynamics stated above, denotes controller class, and 87 ct denote the state and control at time & when the controls are chosen according to n²
S Dx then V[Vac( (s, u)
7

---

A very simple controller class is constant input, i.e., II {Ta T(s) = E U}. In this case, the history h, can be represented by the
state st, and the operators can be set to A = F and B = C/ICI] However, like previous work [Agarwal et al., 2019b] we focus on the class of (vs, -)strongyyyyyy stable linear controllers, IC, where K E satisfies F GK = HI.H with ||K]| || 2: H 2l2 I k and |[[||2 = p < 1. Given such a controller, the inputs are chosen as linear functions the current state, i.c., Ut = - st. Unfortunately, parameterizing i, directly with a linear controller ",, - Ks; leads to non-convex problem because s, is a non-linear function of K, e.g., if disturbances are 0, then 8t = (F - GK)'so 80. An alternative parameterization is the disturbance-action controller (DAC).
Definition 4.1. Let K K. be fixed. The class of disturbance-actinn controllers (DACs) Mr is {(K, (M) M = (M where M E Raxd satisfies || [+ I x* pp. The control in round k is chosen as uA = Ksg + ck+1 Milwr---
The class of such DACs has two important properties. First, it acts on the entire history of past disturbances. Consequently, given an arbitrary K E K, every K* KC can be expressed as a DAC (K, M) MM with M = (Mil ...... ,....,
M(T+1), .,...) [Agarwal al., 2019a, Section 16.5]. That is, K. C Mx and it suffices to compute regret against Mr instead of K. For the rest of this paper we fix K E KC and denote F- F - GK. Second, suppose Mr (M.") ) is the parameter chosen in round & and the control ue is chosen according to the DAC (K, M,). Then, 8, and u, are linear functions of the parameters, which implies that e, is convex in the parameters. (See the next paragraph on "Formulation as OCO with Unbounded Memory" for a formula.) A similar parameterization was first considered for online linear control by Agarwal al. [2019b] and is based on similar ideas in control theory, e.g., Youla (Youla et al., 1976, Kučera, 1975] and SLS [Wang et al., 2019, Anderson al., 2019].
Formulation as OCO with Unbounded Memory. The first step a change of variables with respect to the control inputs from linear controllers to DACs and the second is a corresponding change of variables for the state. Define the decision space X' = {M = (Ml+)) Mi4 E Raxd |M S x² ".p"). Define the history space H to be the set consisting of sequences h (Y&), where Yo X
and Y₁ G for X E X, 2 1. (Recall F = F GK.) Define weighted norms ||+ and | Ex= & 113. where the weights (Ex) are defined .p _ ....... Define the linear operators A H - H and B W + H as A((Y,. Y)....) GYo FY,....... and B(M) (M, 0, o.... ). Note that the problem follows linear sequence dynamics with the g-weighted 2-norm (Definition 2.3). The weights in the norms on X' and H increase exponentially. However, the norms || and || GI decrease exponentially well: by definition of X and the assumption on F = GK for K E K. Leveraging these exponential decays to define exponentially increasing weights is crucial for deriving our regret bounds that are stronger than existing results.
as & = p
|| =
P- p-
Construct the functions ft : H + E that correspond to ce ue) as follows. Given a sequence of decisions (Mo,.... (Mo....,M)) M.). the history at the end of round t is given by GM,
he (M,, BGM-1,FGM, that the state and control in round t can be written as functions of h4 as St = F'so + Ek= sk1 Ta--R-1GMM lal Wk-, + wi-1 and u = Ks, + Et+1 M/" We-e- Define the func- tions ft H. + R by fe(h) ca(s, u). where s and u are the state and control determined by the history as above. Note that ft is parameterized by the past disturbances. Since the state and control linear functions of the history and e, is convex, this implies that fe is convex. Now, given the above formulation and the fact that the class of disturbance-actio action controllers is superset of the linear controllers,
A simple inductive argument shows
=-=1
have that the policy regret for the online linear control problem at most the policy regret, Ei- fe(h.) - minMex ET-1 f.(M.. The following is our main result for online linear control and it improves existing results [Agarwal et al., 2019b] by a factor of (dd log x5 p)
class of (R., ---stronglyystaiee
(1 -1). ). See Appendix E.3 for a detailed comparison.
Theorem 4.1. Consider the online linear control problem as defined in Section 4.1. Suppose the decisions in round are chosen using Algorithm 1. Then, the upper bound on the policy regret is
o (LoW VTdà (7 p) -)5)))))
(2)
8

---

Comparison with prior and concurrent work. Existing works solve OLC (and its extensions) by making multiple finite memory approximations. First, they formulate the problem as OCO with finite memory. This requires bounding numerous error terms because the problem is inherently an OCO with unbounded memory problem. We bypass these error analysis steps entirely because the problem fits into our framework naturally. Second, existing works use the parameterization from Agarwal et al. [2019b] that only acts on a fixed, constant number of past disturbances. In particular, existing works use "truncated" DAC policy that is sequence of d x d matrices of length 2x*(1 -)- _ log T, Our DAC policy acts on the entire history of disturbances and a sequence of d x d matrices of unbounded length. Yet, we capture the dimension of this infiniteddimensional space in way that still improves the overall bound, including completely eliminating the dependence on log and improving the dependence on d, KG, and (1 p). This improvement comes from our novel use of weighted norms on the history and decision spaces. These norms allow us to give tighter bounds on the relevant quantities in the regret upper bound, e.g.. || (Lemma E.2) and (Lemma E.6).
In complementary concurrent work, Lin et al. [2022] focus on more general online control problem. They improve regret bounds for this general version by a factor of log T compared to existing reductions to OCO with finite memory. They do so by using that the impact of past policy decays geometrically with time. On the other hand, the primary focus of our work is studying the complete dependence of present losses on the entire history in OCO. Applying our resulting OCO with unbounded memory framework to OLC, we improve upon existing results for OLC by removing all log I" factors and improving the dependence on d, K, and (1 - p).
4.2 Online Performative Prediction
Background. In many applications of machine learning the algorithm's decisions influence the data distribution, e.g.. online labor markets [Anagnostopoulos et al., 2018, Horton, 2010], predictive policing [Lum and Isaac, 2016], on-strect parking [Dowling et al., 2020, Pierce and Shoup, 2018], vehicle sharing markets [Banerjee et al., 2015], etc. Motivated by such applications, several works have studied the problem of performative prediction, which models the data distribution as a function of the decision-maker" decision [Perdomo et al., 2020, Sendler-Dünnes et al., 2020, Miller et al., 2021, Brown et al., 2022, Ray et al., 2022, Jagadeesan et al., 2022]. Most of these works view the problem as stochastic optimization problem; Jagadeesan al. [2022] adopt regret minimization perspective. We refer the reader to these citations for more details. As a natural extension to existing works, we introduce an online learning variant of performative prediction with geometric decay [Ray et al., 2022] that differs from the original formulations in few key ways.
Let the decision set X C Rd be closed and convex with ||0||| S Dx. Let p1 denote the initial data distribution over the instance space Z, In each round E [T]. the learner chooses a decision 2, e X and oblivious adversary chooses loss function 4 : X' x 2 -> [0, 1]. and then the learner suffers the loss L2 (3re) = Ez-p, (,,, =)]. where p: Pt (......, 224 is the data distribution in round f. The goal in our online learning setting is to minimize the difference between the algorithm's total loss and the total loss of the best fixed decision. _T1 Es-p, [1 =)] m Σt= Ez=p((x) (x) (z, 2)], where (z(x) = Pr (r........ x) is the data distribution in round had x been chosen in all rounds far. This measure is similar to performative regret [Jagadeesan et al., 2022] and is natural generalization of performative optimality [Perdomo et al., 2020] for an online learning formulation.
.......,,
We make the following assumptions. First, the loss functions 4 are convex and LypLiischitz continuous. Second, the data distribution satisfies for all 2 Pt+1 pp: + (1 -2)D(z)) where E (0, 1) and D(x;) is a distribution over Z that depends on the decision I, [Ray et al., 2022].
Third, D(x) is a location-scale distribution: z ~ D(x) iff 2 ~ & + Fx, where F e dddd satisfies ||F]|2 < and & is random variable with mean μ and covariance E [Ray et al., 2022].
Our problem formulation differs from existing work in the following ways. First, we adopt an online learning perspective on performative prediction with geometric decay, whereas Ray et al. [2022] adopt a stochastic optimization one. So, we assume that the loss functions I, are adversarially chosen, whereas Ray et al. [2022] assume 4,- = / are fixed. Second, we assume that the dynamics (D and p) are known (Assumption A1), whereas Ray et al. [2022] assume they are unknown and use samples from the data distribution. We believe that an appropriate extension of our framework that can deal with unknown linear operators and can be applied to this more difficult setting, and we leave this as future work. Third, even though Jagadeesan et al. [2022] also study online learning variant

---

of performative prediction, they assume 1 = are fixed and the data distribution depends only on the current decisions. whereas we assume the data distribution depends on the entire history of decisions.
Formulation as OCO with Unbounded Memory. Let p E (0, 1). Let the decision space X C R be closed and convex with the 2-norm. Let the history space H be the e di-reetct sum of count- ably infinite number of copies of X. Define the linear operators A H - H and B : W - H as A((yo, Vi,...)) )) (0, pyao pU),.... ) and (ax) (ar, O,...... ). The problem is OCO with p-discounted infinite memory problem and follows linear sequence dynamics with the 1-norm (Defini- tion 2.3). Given a sequence of decisions (2 the history h (xt, p p. O...)
and the data distribution pr = Pr (h+) satisfies: 2 ~ Pr iff 2 ~ Σk=1 (1 -cl--ppp p-ppppppp Fx(x))+ This follows from the recursive definition of p. and parametrie assumption about D(x).. Define the functions fa: : H + [0, 1] by fo (he) = Ez-p, [4, (1), Now, the original goal of minimizing the difference between the algorithm's 's total loss and the total loss of the best fixed decision is equivalent to minimizing the policy regret. The following is our main result for online performative prediction.
Theorem 4.2. Consider the online performative prediction problem as defined in Section 4.2. Suppose the decisions in round t are chosen using Algorithm 1. Then, the upper bound on the policy regret is
o
- bp)
5 Conclusion
In this paper we introduced generalization of the OCO framework, "Online Convex Optimization with Unbounded Memory". that allows the loss in the current round to depend on the entire history of decisions until that point. We proved matching upper and lower bounds on the policy regret in terms of the time horizon, the p-effective memory capacity (a quantitative measure of the influence of past decisions on present losses), and other problem parameters (Theorems 3.1 and 3.2). As a special case, we proved the first non-trivial lower bound for OCO with finite memory (Theorem 3.4), which could be of independent interest, and also improved existing upper bounds (Theorem 3.3). We illustrated the power of our framework by bringing together the regret analysis of two seemingly disparate problems under the same umbrella: online linear control (Theorem 4.1), where we improve and simplify existing regret bounds, and online performative prediction (Theorem 4.2).
There are number of directions for future research. A natural follow-up is to consider unknown dynamics (i.e., when the learner does not know the operators A and B) and/or the case of bandit feedback (i.e., when the learner only observes fh.).). The extension to bandit feedback has been considered in the OCO and OCO with finite memory literature [Hazan and Li, 2016, Bubeck et al., 2021, Zhao et al., 2021, Gradu et al., 2020, Cassel and Koren, 2020]. It is tempting to think about a version where the history is a nonlinear, but decaying, function of the past decisions. The obvious challenge is that the nonlincarity would lead to non-convex losses. It is unclear how to deal with such issues, c.g., restricted classes of nonlinearities for which the OCO with unbounded memory perspective is still relevant [Zhang et al., 2015], different problem formulations such as online non-convex learning [Gao et al., 2018, Suggala and Netrapalli, 2020), etc.
There is a growing body of work on online linear control and its variants that rely on OCO with finite memory [Hazan et al., 2020, Agarwal et al., 2019c, Foster and Simchowitz, 2020, Cassel and Koren, 2020, Gradu et al., 2020, Li et al., 2021, Minasyan et al., 2021]. In this paper we showed how our framework can be used to improve and simplify regret bounds for the online linear control problem. Another direction for future work is to use our framework, perhaps with suitable extensions outlined above, to derive similar improvements for these other variants of online linear control.
Acknowledgments and Disclosure of Funding
We thank Sloan Nietert and Victor Sanches Portella for helpful discussions. We thank Wei- Yu Chan for pointing out an error in the proof of Lemma C. We also thank anonymous AISTATS and NeurIPS reviewers for their helpful comments on an older and the current version of the paper respectively. This research was partially supported by the NSERC Postgraduate Scholarships-Docee 545847-2020, NSF awards CCF-2312774 and OAC-2311521, and a gift from Wayfair.
Fellowship
10

---

References
Yasin Abbasi-Yadkond and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Sham M. Kakade and Ulrike von Luxburg, editors, COLT 20/1 -he 24th Annual Conference on Learning Theory, June 9-11, 2011, Budapest, Hungary, 2011.
Jacob D. Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In Rocco A. Servedio and Tong Zhang, editors, 2 Annual Conference on Learning Theory- COLT 2008, Helsinki, Finland, July 9-12. 2008, pages 263-274. Omnipress, 2008
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. 2019a.
Naman Agarwal, Brian Bullins, Elad Hazan, Sham M. Kakade, and Karan Singh. Online control with adversarial disturbances. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 111-119. PMLR, 2019b.
Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 10175-10184, 2019c.
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
Jason M. Altschuler and Kunal Talwar. Online learning over finite action set with limited switching. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, 2018.
Aris Anagnostopoulos, Carlos Castillo, Adriano Fazzone, Stefano Leonardi, and Evimaria Terzi. Algorithms for hiring and outsourcing in the online labor market. In Yike Guo and Faisal Farooq, editors, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018, pages 1109-1118. ACM, 2018.
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: Price of past mistakes. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 784-79,, 2015.
James Anderson, John C Doyle. Steven H Low, and Nikolai Matni. System level synthesis. Annual Reviews in Control, 07:364-393, 2019.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. J. Comput. Syst. Sci., 74(1):97-114, 2008
Siddhartha Banerjee, Carlos Riquelme, and Ramesh Johari. Pricing in ride-share platforms: A queueing-theorrtt approach. Available at SSRN 2568258, 2015.
Kush Bhatia and Karthik Sridharan. Online learning with dynamics: A minimax perspective. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Boubekeur Boukhezzar and Houria Siguerdidjane. Comparison between linear and nonlinear control strategies for variable speed wind turbines. Control Engineering Practice, 18:1351 1357-13368, 2010.
Gavin Brown, Shlomi Hod, and Iden Kalemaj. Performative prediction in stateful world. In Gustau Camps- Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 6045-6061. PMLR, 2022.
11

---

Sébastien Bubeck and Nicolo Desa-Bianchi.. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5:1-122, 2012.
Sébastien Bubeck, Ronen Eldan, and Yin Tat Lee. Kernel-based methods for bandit convex optimiza- tion. J. ACM, 68(4))25:1 -25:35, 2021.
Asaf B. Cassel and Tomer Koren. Bandit linear control. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell,
Balcan, and Hsuan-Tiee -iean Lin, editors, Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020,
NeurlPS 2020, December 6-12, 2020, viriual, 2020.
Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of online convex optimization: No phase transition. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Thomas M Cover. Universal portfolios. Mathematical finance, 1(1):1-29, 1991.
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 0111242200 2018.
Ofer Dekel, Ambuj Tewari, and Raman Arora. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Conference on Machine Learning, ICML 2012, Edinburgh, Scotland, UK, June 26 July 1, 2012. ieml.ec / Omnipress, 2012.
Steven Diamond and Stephen Boyd. CVXPY: A embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83)1155, 2016.
Chase P. Dowling, Lillian J. Ratliff, and Baosen Zhang. Modeling curbside parking as a network of finite capacity queues. IEEE Trans. Intell. Transp. Syst., 21(1):1011-1000 2020.
Dylan J. Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In Proceed- ings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, 2020.
Xiand Gao, Xiaobo Li, and Shuzhong Zhang. Online learning with non-convex losses and non- stationary regret. In Amos J. Storkey and Fernando Pérez-Cruz, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, volume 84 of Proceedings of Machine Learning Research, pages 235-243. PMLR, 2018.
Gene H. Golub and Charles F. Van Loan. Matrix Computations, Third Edition. John Hopkins University Press, 1996.
Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Elad Hazan. Introduction to online convex optimization. CoRR, abs/ 2019
2019.
Elad Hazan and Yuanzhi Li. An optimal algorithm for bandit convex optimization. CoRR, abs/1603.0445 2016. URL http://aarrx wtt.a/awwww....//////.r//e/. 160.//0000......
Elad Hazan, Sham M. Kakade, and Karan Singh. The nonstochastic control problem. In Aryeh Kontorovich and Gergely Neu, editors, Algorithmic Learning Theory, ALT 2020, 8-11 February 2020, San Diego CA, USA, volume 117 of Proceedings of Muchine Learning Research, pages 408-421 PMLR, 2020.
12

---

John J Horton. Online labor markets. In International workshop on internet and network economics, pages 515-522. Springer, 2010.
Meena Jagadcesan, Tijana Zmnc,, and Celestine Mendler-Dünner. Regret minimization with perfor- mative feedback. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, 2022.
Anna Karlin. Lecture notes for cse 522: Algorithms and uncertainty, 2017. URL washington add/courses... wwwrsse/cceeee/ hTtpp///eeeeereseeeeeeeeeee pdf.
Vladimír Kučera. Stability of discrete linear feedback systems. IFAC Proceedings Volumes, 8(1): 573-578, 1975.
Peter Lancaster and Leiba Rodman. Algebraic riccati equations. Clarendon press, 1995.
Yingying Li, Subhro Das, and Na Li. Online optimal control with affine constraints. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Ap- plications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 8527-8537. AAAI Press, 2021.
Yiheng Lin. James Preiss, Emile Anand, Yingying Li, Yisong Yue, and Adam Wierman. Online adaptive controller selection in marying systems: No-regret via contractive perturbations. arXiv preprint 2rXiv:2210.12233 2022.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October 1 November 1989, pages 256-261 IEEE Computer Society, 1989.
Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. Inf. Comput., 108(2): 212-261, 1994.
Kristian Lum and William Isaac. To predict and serve? Significance, 13(5):14-1, 2016.
Celestine Mendler-Dinner, Juan C. Perdomo, Tijana Zrnic, and Moritz Hardt. Stochastic optimization for performative prediction. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria- Florina Balcan, and Hsuan-Tier Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
John Miller, Juan C. Perdomo, and Tijana Zrnie. Outside the echo chamber: Optimizing the performative risk. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 7710-7720. PMLR, 2021.
Edgar Minasyan, Paula Gradu, Max Simchowitz, and Elad Hazan. Online control of unknown time-varying dynamical systems. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, 2021.
Francesco Orabona. modern introduction to online learning. CoRR, abs/1912.13213.. 2019.
Juan C. Perdomo, Tijana Zmic, Celestine Hendler-Dünnedd and Moritz Hardt. Performative prediction. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Leurning Research, pages 7599-7609. PMLR, 2020.
Gregory Pierce and Donald Shoup. Sfpark: Pricing parking by demand. In Parking and the City, pages 344-34 353. Routledge, 2018.
Yuzhen Qin, Yingcong Li, Fabio Pasqualetti, Maryam Fazel, and Samet Oymak. Stochastic contextual bandits with long horizon rewards. In SheeethSeventh AAAI Conference on Artificial Intelligence, AAAI 2023, Washington, DC, USA, February 7-14, 2023, AAAI Press, 2023.
13

---

Mitas Ray. Lillian J. Ratliff. Dmitriy Drusvyatskiy, and Maryam Fazel. Decision-dependee risk minimization in geometrically decaying dynamic environments. In Thirty- Sirrt--Sitthaao AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 March 1, 2022, pages 8081-800 0081-8088. AAAI Press, 2022.
Shai Shallv-Shwarrz. Online learning and online convex optimization. Found. Trends Mach. Learn., 422):177-19,, 2012.
Shai Shalev-Shwartz and Yoram Singer. Online learning meets optimization in the dual. In Gábor Lugosi and Hans Ulrich Simon, editors, Learning Theory, 19th Annual Conference on Learning Theory, COLT 2006, Pittsburg,, PA, USA, June 22-25, 2006, Proceedings, 2006.
Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020.
Max Simchowitz and Dylan J. Foster. Naive exploration is optimal for online LQR. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, 2020.
Aleksandrs Slivkins. Introduction to multi-armed bandits. Found. Trends Mach. Learn., 12:1-286. 2019.
Arun Sai Suggala and Praneeth Netrapalli. Online non-convex learning: Following the perturbed leader is optimal. In Aryeh Kontorovich and Gergely Neu, editors, Algorithmic Learning Theory, ALT 2020, 8-11 February 2020, San Diego CA, USA, volume 117 of Proceedings of Machine Learning Research, pages 845- 861. PMLR, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Yuh-Shyang Wang. Nikolai Matni, and John C. Doyle. A system-level approach to controller synthesis. IEEE Trans. Autom. Control., 64(10):4079-4993 2019.
Dante Youla, Hamid Jabr, and Jr Bongiomo. Modern wiener-hopf design of optimal controllers-part ii: The multivariable case. IEEE Transactions on Automatic Control, 21(3)3319-338, 1976.
Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Online bandit learning for a special class of non-convex losses. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAA/ Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 3158-3164 AAAI Press, 2015.
Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Mach. Learn. Res., 12:125::-1 2021.
Peng Zhao, Yu-Xiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non-stochastic control. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 2101-2133, PMLR, 2022.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Tom Fawcett and Nina Mishra, editors, Proceedings of the 20th International Conference on Machine Learning, ICML 2003, August 21 21-24 2003, Washington, DC, USA, 2003.
14

---

Organization of the Appendix
The appendix is organized follows:
Appendix A contains the proofs of the results from Section 2.
Appendix contains the proofs of existing results about FTRL for completeness.
Appendix contains the proofs of upper bounds on regret from Section
Appendix D contains the proofs of lower bounds on regret from Section 3.
Appendix contains the proofs of results about online linear control from Section 4.1. Appendix F contains the proofs of results about online performative prediction from Sec- tion 4.2.
Appendix G discusses how to implement Algorithm efficiently.
Appendix H presents an algorithm for OCO with unbounded memory that provides the same upper bound on policy regret Algorithm while guarantecting small number of switches (Algorithm 2).
Appendix presents simulation experiments.
A Framework
In this section prove Theorem 2.1. But first we prove a lemma that we use for proofs involving linear sequence dynamics with the E-weighted p-norm (Definition 2.3). Recall that 112 denotes the norm associated with a space and the operator norm ||]]| for linear operator L :u - defined as
||Z|| uaaxu: | [[uulpy
Lemma A.1. Consider an online convex optimization with unbounded memory problem specified by (X, A, ABB. B). If (X, H, A, B)..B..... follows linear sequence dynamics with the g-weighted p-norm for p 2 then for all
Ex A Aoll ||
Proof. Let x E X' with ||~||x = 1. We have
Ex ... Agzllxx = ||A (xx, O.... )l I [|] O,....)le 1l S ||
where the last incquality follows because O,..,.....ll Go||=||x and &o 1 by Definition 2.3. Therefore, ||Ag11 Aoll s ||A4
Theorem 2.1. Consider an online convex optimization with unbounded memory problem spec- ified by (X, H. A, B). If ft is L-Lipschitz continuous, then fc is L-Lipschitz continuous for L < L E || If (X, H. A, B) follows linear sequence dynamics with the E-weighted p-norm for 2 1, then < L (E ||A+|P)
Proof. Let x. 5 X. For the general case, we have
-(
fa
A Bx
Se
Σ A
Bi
by Definition 2.1
A
h-1
1
Σ
A B(x -z)
Si is L-Lipschitz continuous
71
SL
||A ||| 21
|| ||| ø||x
by Assumption A2
K=0
5 L Σ
|| ||] - Z|1xx-
0
15

---

If 2, A,B) B) follows linear sequence dynamics with the g-weighted p-norm for 1, then we have
(((z)) = Se
A Br
-
Σ
A BT
by Definition 2.1
0=0
k=0
A B(x - -t)
fa is L-Lipschitz continuous by Definition 2.3
K=U
L
(0, Ao(æ A2A((2 -.)....)
L
$ ||| Ao(o -3)11"
by Definition 2.3
1
||
|| - -
by Lemma A.1
L
|
|| -|=- =1lx
B Standard Analysis of Follov-the-Regulariiee----
In this section state and prove existing results about the follow-the-rggulaiizee--ee (FTRL) algorithm [Shalev-Shwartz and Singer, 2006, Abernethy et al., 2008]. These results are well known in the literature, but prove them here for completeness and use them in the remainder of the paper. We the below results for functions Se with Lipschitz constants L. However, in this section we use more general notation, denoting functions by Jt and their Lipschitz constant by Lg-
Consider the following setup for online convex optimization (OCO) problem. Let T denote the time horizon. Let the decision space X' be a closed, convex subset of Hilbert space and gr : R be loss functions chosen by oblivious adversary. The functions Jr are convex and Ly--ipschitz continuous. The game between the learner and the adversary proceeds as follows. each round t [T), the learner chooses 2, X' and the learner suffers loss ge (2,). The goal of the learner is to minimize (static) regret,
R Σ (x))
min x
9c(x).
(3)
Let : + R be an a-strongly convex regularizer satisfying [R(x) R()) S D for all x E X. The FTRL algorithm chooses iterates I,
R(x)
E arg min
Σ (x(z) +
(4)
FEX
77
where yj a tunable parameter referred to as the step-size. what follows, let go 77" in this section closely follows Karlin [2017]. Lemma B.1. For all x E X, FTRL (Eq. (4)) satisfies
The analysis
Σ (x( Σ g((x441)
Proof. We use proof by induction on T. The base case is T = 0. By definition, .1 arg min R(x). Therefore, R(x)) 2 R(xi) for all x E X. Recalling the notation go proves the base case. Now, assume that the lemma is true for 1. That is,
T-1
T-1
Σ
N
ge (x(+1)))
1=0
16

---

Let x E X be arbitrary. Since 27+1 argminzez ZE Σt=o (1(x), we have
Σ (r(
gi(TT-11
(x(TT+1) + gr((T+1)
(((x+11) + (T(rr1))
by inductive hypothesis
ge (x
This completes the proof.
Lemma B.2, For all x E X, FTRL (Eq. (4)) satisfies
T
Σ
(((z))
Σ
(x( v +
Σ g(())) (0(+))))
1=1
1=1
Proof. Note that
T Σ (((x) (x))
T
Σ (x)))
-0)()
go(x) -9((11)
because I1 E arg g (z)). The proof of this lemma now follows by using the above inequal-
ity, Lemma B. the definition 9o = and the definition of D.
Theorem B.1. FTRL (Eq. (4)) satisfies
Lg
D TL3
1 2z 1111x S 11
and
sstattc < 11
a
Choosing 1 V
al TT3
yields
(
D P L0Prr
1egotic <0
Proof. Let arg argmin,ea Etm1((z) lz(z). Using Lemma B.2 we have
T Σ (xx) Σ (x())) < (()))) - (e(x++1).
D
(5)
We can bound the summands in the sum above follows. Define G((x) Dt=bb. Then, It E arg min Gz(z). and #++1 arg min G++1(x). Since {g are convex, R is a-strongly-coovex, and go nj we have that G, -strongly-convex. So.
Ge(z+11) 2 Gz(zz) +
| Zz 22
27
G 2 Ge+1(#241) +
-
| 2z 112
2n
Adding the above two inequalities yields
ge( zo (x++1) 2 - | - =el12
(6)
17

---

Since are convex and Lg Lipschitz continuous, we also have
gr (xxx)) - ge(2++1) S Lig sgl| Fe xel1x.
Combining Eqs. (6) and (7) have
|14+1 - xellx Lg
a
This proves the first part of the theorem. Now, using this in Eq. (7) we have
1
gr(x)) (e(4441) 1)
(8)
Finally, substituting this in Eq. (5) proves the second part of the theorem.
C Regret Analysis: Upper Bounds
First we prove a lemma that bounds the difference in the value of fa evaluated at the actual history he and an idealized history that would have been obtained by playing 2; in all prior rounds.
Lemma C.1. Consider online convex optimization with unbounded memory problem specified by (X, H. B). If the decisions (It) are generated by Algorithm 1, then
LLHI
(((())) S
for all rounds L. When (X, H. A, B) follows linear sequence dynamics with the E-weighted p-norm for p 2 1, then
f((h))) - Fe(x)) Sn I.H.Hp
for all rounds L.
Proof. We have
[((hh) - -((s
f((he))
Σ
A Bri
by Definition 2.1
h=
1-1
<
h4
Σ
A Bat
by Assumption A4 by definition of he
k=0
1-1
A Bat-
Σ
A Bar
k=0
L
A B(Ir - xz)
(a)
First consider the general case where (X, H, A, B) does not necessarily follow linear sequence dynamics. We can bound the term (a)
Σ B zx) k=
|| A Bl| |21
xz-
km i
|| B||
by Theorem B.1
||
km
by Assumption A2
k=0
i
H1.
18

---

Plugging this into Eq. (9) completes the proof for the general case. Now consider the case when (X, H. A, B) follows linear sequence dynamcis with the f-weighted p-norm. We can bound the term (a) as
Σ A ( m2) h=0
-1( - 11-1), =1-2)....]
by Definition 2.3
A Ao(o: - 5t x1-1))1
by Definition 2.3
|||
Ao A0 1|=, - xe- 11
||
||, - x
by Lemma A.1
L
Σ
||
10))
by Theorem B.1
a
k=
L
1)
Hp
a
Plugging this into Eq. (9) completes the proof.
Now we restate and prove Theorem 3.1
Theorem 3.1. Consider an online convex optimization with unbounded memory problem specified by
(X, H. A, B). Let the regularizer R: X - R be a-strongly-convex and satisfy |R(z) R[@)] D
for all x; &6 E X. Algorithm with step-size satisfies Ry I
+ n + +
Ti² TLLH. If
aD then TE(LH,+E)
(FTRL))) So so (
When (X, H. A, B) follows linear sequence dynamics with the E-weighted p-norm, then all of the above hold with H. instead of H1.
Proof. First consider the general case where (X, H. A, B) does not necessarily follow linear sequence dynamics. Let x² E arg min xxx ETH f(().. Note that we can write the regret as
T
T
(FTLL) =
Σ
f((he)
min ZEX
Σ f((x)
fe(he)) fa( + Σ Je(a)) - f((x))
(a)
(6)
We bound term (a) using Lemma C.1 and term (b) using Theorem B.1. Therefore, we have
T
Ry R (FTRL)
Σ
S((h))
Fe(x))
E fe(x)) -((aa)
(a)
(b)
T..L.
D
TÎ?
n
19

---

Choosing V
aD +I(LH1+E)
yields
RT (FTRL) so C
where we used the definition of p-effective memory capacity (Definition 2.4) and the bound on (Theorem 2.1) to simplify the above expression. This completes the proof for the general case. The proof for when (X, H. A, B) follows linear sequence dynamcis with the g-weighted p-norm the same as above, except we bound the term (a) above using Lemma C.1 for linear sequence dynamics.
Now we restate and prove Theorem 3.3.
Theorem 3.3. Consider an online convex optimization with finite memory problem with constant memory length m specified by (X', H. = X Asinte.m Binite.n) Let the regularizer R : X - R be a-strrogly-conve and satisfy [R(x) R(ū) D for all x, X. Algorithm I with step-size
aD Ti(Lm& 2 +L)
satisfies
(F So ( so
D PTL m
The OCO with finite memory problem, defined in the literature, follows linear sequence dynamics with the 2-norm. In this subsection we consider a more general version of the OCO with finite memory problem that follows linear sequence dynamics with the p-norm. We provide an upper bound on the policy regret for this more general formulation and the proof of Theorem 3.3 follows as special case when p 2
Theorem C.1. Consider online convex optimization with finite memory problem with constant memory length m, (X, H. Xm Afmite,ms mm) Assume that the problem follows linear se- quence dynamics with the p-norm for p 2 1. Let the regularizer R X + l. be o-strongly-comvex and satisfy [B(x)- - R(ā) S for all x, T E X. Algorithm with step-size n satisfies
( wid
(rrimm
(
50 PPTPmm xi2
RT (F 50
Proof. Using Theorem 3.1 suffices to bound L and Hp for this problem. Note that || k S m and 0 otherwise. Using this we have
1
1
20 Σ A
m
1)²
m
This proves the first inequality in the statement of the theorem. The second inequality follows from the above and Theorem 2. which states that
i. L
Σ
1 1P)
Lmmd
Finally, we provide an upper bound on the policy regret for the OCO with p-discounted infinite memory problem. For simplicity, we consider the case when the problem follows linear sequence dynamics with the 2-norm instead of general p-norm.
Theorem C.2, Consider an online convex optimization with p-discounted infinite memory problem (X, H. Aingintte Biginite- Suppose that the problem follows linear sequence dynamics with the 2- norm. Let the regularizer R. X > R be a ---sstonglyccowee and satisfy [R(x) R(ā) < D for all
x, X. Algorithm with step-size n satisfies
(FTRL) so (V - -2)-3
(
p2)-2 0o ( TLP - pp)-
20

---

Proof. Using Theorem 3.1, it suffices to bound L and Hp for this problem. Recall that || mfinite.pl pll p Using this have
3
3 (kpp))
H2 Σ (kll 11)²
Σ A=0
S (1 (1-
This proves the first inequality in the statement of the theorem. The second inequality follows from the above and Theorem 2.1, which states that
S. L
Σ A ,11 = L(1-p') -²)-
The last inequality follows because 1 p² =1 p)., which implies that 1 S 2(1 - p) because p E (0, 1).
p²
C.1 Existing Regret Bound for OCO with Finite Memory
In this subsection we provide a detailed comparison of our upper bound on the policy regret for OCO with finite memory with that of Anava al. [2015]. The material in this subsection comes from Appendix A.2 of their arXiv version or Appendix C.2 of their conference version.
The existing upper bound regret is
DT
where D = max,,2eX [R(x) - R(i)]. Although the parameter À is defined in terms of dual norms of the gradient of fe it is essentially the Lipschitz-continuity constant for fú: for all x, 5 E X,
[(()) - [+) s Vxalla =||,
where a is the troogg-coventt parameter of the regularizer R (or the notation of Anava et al. [2015]). Therefore, the existing regret bound can be rewritten as
o
o
Tm3
Our upper bound on the policy regret for OCO with finite memory Theorem 3.3 is
o V
Since < VmL by Theorem 2.1, this leads an improvement by a factor of m
D Regret Analysis: Lower Bounds
first restate Theorems 3.2 and 3.4.
Theorem 3.2. There exists an instance of the online convex optimization with unbounded memory problem, (X, H, A, B), that follows linear sequence dynamics with the E-weighted p-norm and there exist L-pipschitz continuous loss functions {Se 71 IR 12 such that the regret of any algorithm A satisfies
RT(A) 2 (VTLİ.H,)
Theorem 3.4. There exists an instance of the online convex optimization with finite memory problem with constant memory length m, (X, H = x Aguite my Bruite m.) and there exist L-Lipschitz continuous loss functions (Se H + RJTT such that the regret of any algorithm A satisfies
(r(A) 2 Ω (MVT12)
21

---

T 12,
Resample every en rounds.
81
22 48
24
25
36
2.8
210 811 212
fa(ha)
62 123-1
(22 + 244
(ks)s)
c2
(ag 244
Sa(ha) 22 (244)
Figure 2: An illustration of the loss functions ft for the OCO with finite memory lower bound. Suppose T = 12, 3, 1, and p 2. Time is divided into blocks of size m = 3. Consider round = 5. The history hs = (I', J.. ). The loss function fa()s) is product of three terms: random sign C2 sampled for the block that round belongs to, namely, block 2; a scaling factor of m==;; 2; sum over the decisions in the history excluding those that were chosen after observing <2,
i.c,, sum over and 24,, excluding T5.
Theorem 3.2 follows from Theorem 3.4. However, the lower bound is true for much broader class of problems show in this section. We first provide lower bound for more general formulation of the OCO with finite memory problem (Theorem D.I). The proof of Theorem 3.4 follows as a special case when p 2. Then, provide lower bound for the OCO with p-discounted infinite memory problem (Theorem D.2).
The OCO with finite memory problem, as defined in the literature, follows linear sequence dynamics with the 2-norm. In this section we consider a more general version the OCO with finite memory problem that follows linear sequence dynamics with the p-norm. We provide lower bound on the policy regret for this more general formulation and the proof of Theorem 3.4 follows as a special case when p = 2.
Theorem D.1. For all 2 1, there exists an instance of the online convex optimization with finite memory problem with constant memory length m. (X, X Agmnte, Bmintt,m. that follows linear sequence dynamics with the p-norm, and there exist L-Lipschitz continuous loss functions (Je: R) such that the regret of any algorithm satisfies
VVLLm" p+2
RT(A) 20
Proof. Let = 1-1, and consider an OCO with finite memory problem with constant memory length m. (X, H = x A Annite,ms my Bunite.) that follows linear sequence dynamics with the p-norm. For simplicity. assume that T is a multiple m (otherwise, the same proof works but with slightly more tedious bookkeeping) and that L = 1 (otherwise, multiply the functions fr defined below by L).
Divide the T rounds into N m
blocks of m rounds each. Sample N independent Rademacher
random variables (c1,...,,N) where each e; equal to +1 with probability 1. Recall that h = (ra, (I....., "tt....,,t--... "..,,I---tt It-m+1). Define the loss functions (fe)T= as follows. (See Fig. for an illustration.) t I m, let Otherwise, let
m- mn-1((te (t- (t-- 1
fe(h)) C 1-p
Σ
Fe L |+1-k
k=
Le
= (Iz-m+1
2m mm141+11
In words, the loss in the first m rounds is equal 0. Thereafter, in round / the loss is equal random sign (r which is fixed for that block, times a scaling factor, which chosen according to the p-norm to ensure that the Lipschitz constant L is at most 1, times sum of a subset of past decisions in the history ht (#t,... ........ xt-m+1) This subset consists of all past decisions until and including the first decision of the current block, which is the decision in round m [ +1
The functions are linear, so they convex. In order to show that they satisfy Assumptions A3
and A4, it remains to show that they are 1-Lipschitz continuous. Let h (1) ...., (m)) and
22

---

(8(1, 3(m)) be arbitrary elements of 74 = x We have
f((h)) - f(h))
(cx(1) - -1(1) + .... (xx x((m)) 1_ p (xx =(1)) + ... (x((m) - -
<
because e E (-1,+11
1-
x((h) $008/
by Hölder's inequality
= =I 7ll
where the last equality follows because of our assumption that the problem that follows linear sequence dynamics with the p-norm.
First we will show that the total expected loss of any algorithm is O, where the expectation is with respect to the randomness the choice of {e }. The total loss the first block is because f2, ..., .N. the total loss in block n depends
ft 0 for f [m]] For each subsequent block the algorithm's 's choices made before observing Gn. namely, {I(n- (2(m=2)m+2-- 22. (n- 1)m+11 1 }- Since en
is equal to =1 with probability 5. the expected loss of any algorithm in a block is equal to and the total expected loss is also equal to O.
Now we will show that the expected loss of the benchmark is at most
-o
(
T'
where the expectation with respect to the randomness in the choice of (eI,...,EN) We have
E
min
(x)
= E
min
Σ
f((z)
1)m+1
E
min
Σ
En
x (m (t- (n- 1)m 1))
1=
(=(n-1)m++
The first equality follows from first summing over blocks and then summing over the rounds that block. The second equality follows from the definitions of f. above and of f. (Definition 2.1). By the defintion of ftx the history h consists of m copies of x for f. 2 m. By the definition of ft, which sums over all past decisions until the first round of the current block, sum first extends over m copies of z (in the first round of the block), then m - -1 copies of æ (in the second round of the block), and on until the last round of the block. So, we have
have that within block the
T
E
min
fx(
=
E
min TEX
Σ
Ga 1-P
x x (m (t (n 1)m 1))
1=1
2=
t=
1mm+1
N
E
min
En
X (m (m- k:)
n=2 k=0
1-g m m
m.
min
2
PEN
N
I-p m2 + m
= m
min
2
1E(-1,1)
n=2
N
m
1-p m72 + m
E
Cn
(-11+11)
1
Σ
cn
(-1-111)
2
2
2
n=
n=2
23

---

where the second-last equality follows because the minima of a linear function over an interval is at one of the endpoints and the last equality follows because min [x, y) 2 + y) - a y/- Since en are Rademacher random variables equal to #1 with probability 2. we can simplify the above as
m m7
1
E
min ZER
fx(
E
2p
2
m 1- m
m
2
n=
N
LE 171 + m
= -
2
n=
1-p m + m
< m P
VN,
2
where the last inequality follows from Khintchine's inequality. Using the definition
N T m.
we have
min Σ f((x))
T
Le
m
+
T
$ m
ZEX
m
VT m +
+ m 1
2
s -0
(Tm+++ +
0
VTm 27
T'm p+2
Therefore, we have
(V
tt
E Eey [R = IE Σ fe(he)
E min Σ
f((x)
This completes the proof.
Now we provide lower bound for the OCO with p-discounted infinite memory problem. For simplicity, we consider the case when the problem follows linear sequence dynamics with the 2-norm instead of general p-norm.
Theorem D.2. Let 1). 1). There exists an instance of the online convex optimization with discounted infinite memory problem, (X, H. Ainfmie, Bingnite, ) that follows linear sequence dynamics with the 2-norm and there exist L-Lipschitz continuous loss functions {fe H. B]T, such that the regret of any algorithm A satisfies
RT(A) 2 Ω (1)=2(1-))-
The proof is very similar to that of Theorem D.I with slight adjustments to account for p-discounted infinite memory instead of a finite memory of constant size m.
Proof. Let X' [-1, 1] and consider an OCO with infinite memory problem with discount factor p, (X, H. Ainfinite,p- ), that follows linear sequence dynamics with the 2-norm. For simplicity, assume that T is a multiple of (1 p) (otherwise, the same proof works but with slightly more tedious bookkeeping) and that L (otherwise, multiply the functions Se defined below by L).
Define m = (1 -p) Divide the T rounds into N blocks of m rounds each. Sample N independent Rademacher random variables {eI,..., E. where each is equal to #1 with

---

probability 3. Recall that ht (2t, p
1.........'.1....... 1,,''10,,,..........,,1,,,,,,,,, 02.0..... Define the loss functions {fe)z=1 as
follows. If m, let fo O. Otherwise,
m--1
f((h)) = Er 1
p m
2m ++1-k
The functions ft are linear, so they are convex. In order to show that they satisty Assumptions A3 and A4, it remains show that they are 1-Lipschitz continuous. Let (x(1), px) ....) and h (z(1), pi(t) ....) )) be arbitrary elements of have
Se(h) sb(h)
$
p k-1 (z(t)) - x((5))
k=1
k-1 (2()) x((c))
$ m
because cr11 E {-1, +1}
k=1
Σ 2(1--1) (x(()) s((k)) 2 1
m m
by Hölder's inequality
$ ||4 - hllx
where the last equality follows because the follows linear sequence dynamics with the 2-norm.
First we will show that the total expected loss of any algorithm is O, where the expectation is with respect the randomness the choice of fei..... eN.. The total loss the first block is because fi = 0 for t [m]. For each subsequent block algorithm's is choices made before observing en. namely, (= ((n-1)m+1) ). Since en 2 the expected loss any algorithm a block is equal to and the total expected loss is also equal to O.
f2.... NN, the total loss in block n depends on
equal to 11 with probability 1
Now we will show that the expected loss of the benchmark is at most
-0(v((1p))-)
where the expectation is with respect to the randomness in the choice of (cI,...,EN} We have
E
min
fx)
E
min zed
Σ
Σ
fe(x))
t=1
n=
t= 1)m-1
N
m-1
E
min
p k+t
(n- 1000-11m111
x
2=
t=
1im-1
k=
N
nm
m
E
min BEY
Σ
(- 1)m
n
1)m++
k=0
N
p
m
E
min
E
(n 1m
X
1=
t=
(n
1)
pm
2
N
m
E
min
n==
25

---

The term (a) above can be bounded above by -V as in the proof Theorem D.1 using Khintchine's inequality. Therefore, using that N and (1 p) we have
1- VN
min E
f((x))
S -m
1 (
xEA
S -1 0) (--p") pm) (1-p) VT(1 p)
VT (1 pm
p-p P
-TV(11 (1-2(11 S - (VT(1-1) - p)-
where the last inequality follows from the assumption that p E [ 1) and the following argument:
p = (1 (1 - p)) = (1- - (1 p)) م -
(1- pmm)
- pm-p=/? 1 1 2
e
2
+ - pm- < -
(1-2
1
This completes the proof.
E
Online Linear Control
E.1
Formulation as OCO with Unbounded Memory
Now we formulate the online linear control problem in our framework by defining the decision space X, the history space H. and the linear operators A H - H and B : W - H. Then, we define the functions H IR in terms of and finally, prove upper bound the policy regret. For notational convenience, let (Ml and (Y&) denote the sequences (M 11, M [2] ....) and (Yo, ......) respectively.
Recall that we fix K E K. to be an arbitrary (k, p)-strongly stable linear controller and consider the disturbance-actiin controller policy class MM (Definition 4.1). For the rest of this paper let F = F - GK. The first step is a change of variables with respect to the control inputs from linear controllers to DACs and the second is a corresponding change of variables for the state. Define the decision space X' as
X (M= (M-l1))) Ml E RRdxd || 12 S p²p
(10)
with
2 Σ
|M
(11)
Define the history space H. to be the set consisting of sequences h (Yx), where Yo X and Yk G for Xx E X k 2 1 with
|AAl|
Σ
12
(12)
26

---

where the weights (5x) are nonnegative real numbers defined as
{ (1,1,11,, & 3,p ......
(13)
Define the linear operators A H + H and B W + H as
A((Y,, .1....) (0, GY,, FY, FY2..... and B(M) OM,
Note that the problem follows linear sequence dynamics with the E-weighted 2-norm (Definition 2.3), where & is defined above in Eq. (13). The weights in the weighted norms X and H increase exponentially. However, the norms
|| and FFR-IG|: decrease exponentially as well: by definition of M in Eq. (11) and the assumption on F = F GK for K E K. Leveraging this exponential decrease in |M [s] |p and || G to define exponentially increasing weights turns out to be crucial for deriving our regret bounds that are stronger than existing results. Furthermore, the choice to have cp = 1 for p E {1,2} in addition to 0 (as required by Definition 2.3) might seem like a small detail, but this also turns out to be crucial for avoiding unnecessary factors of p in the regret bounds.
p
Recall that the loss functions the online linear control problem are (s(St. Uz), where s, and ue are the state and control at round t. Now we will show how to construct the functions fr H + R that correspond to (#,, w.). By definition, given sequence of decisions (Mo...., Mt), the history at the end of round / given by
h (M, GM,-1, FGM-2,...... F F O,...).
A simple inductive argument shows that the state and control in round t can be written
1+
8, F* 80 +
p L Wk-. + w1-1
k-
(14)
k= am1
8+1
U1 Kst e Σ
M [5)
Wt-s.
(15)
Define the functions f H R by Je( (s, u),, where and are the state and control determined by the history as above. Note that fe is parameterized by the past disturbances. Since the state and control linear functions of the history and e is convex, this implies that fa convex.
With the above formulation and the fact that the class of disturbance-action controllers a superset of the class of (x, p)--stonglly-sallee linear controllers, we have that the policy regret for the online linear control problem is at most
T-1 Σ f(MM). t=
Σ f((h)) t=0
min MEX
This completes the specification of the online convex optimization with unbounded memory problem, (X, H. A) B), corresponding to the online linear control problem. Using Algorithm and Theorem 3.1 can upper bound the above by
o (vPLLns))
where L the Lipschitz constant of fr. L is the Lipschitz constant of Fc. Hy the 2-effective memory capacity, and D = max,,Bex' [Rxx) R(2) for an a-strongly-conve regularizer R : X' - R. In the next subsection we bound these quantities in terms of the problem parameters of the online linear control problem. We use (-)) to hide absolute constants.
E.2
Regret Analysis
We the following standard facts about matrix norms.
Lemma E.1. Let M,N N pdddd Then.
27

---

1. |M & | S V2
2. || & |
Proof. Part can be found in, for example, Golub and Loan [1996, Section 2.3.2]. Letting N, denote the j-th column of N, part 2 follows from
d
d
M
Σ |MN, S M Σ 1N - I
This completes the proof.
Lemma E.2. For s 2 2, the operator norm ||AA'] is bounded above as
|||'|| S O (x²p2)
Proof. Recall the definition of H and || || (Eq. (12)). Let (Yo, 11.... (Yo, GX1, ,X,, FG,,, FxX.....) be an element of H with unit norm, i.e.,
1 1,
where the weights (Ex) are defined in Eq. (13). Note that E, 1 for p 0, and Eg p pPt2 for
= 2, .... From the definition of the operator A and for s 2 2, we have
A A"Yo,, Yi,...)) )) (,. F G
Now we bound || as follows. By definition of A and || || (Eq. (12)), and part 2 of Lemma E. we have
2
||A ((Yo, YI... 1)11
p p GYol 1+++ + Σ 1
+ Σ
pp-s-kt21
S p ||| 111001111
112,
p -
Σ
10
Using our assumptions that | < and || S x² p. we have
[|A, ((Y. Y.... M < =11 112, P2221Yol1 +
S - & pm3 11 11/00-1112
|Yoll + Σ p A+2 12
km
S 0 2/2 pm k2 x22=011
||ooll3
k+2 1Y
= x²p
||8o133 +
k+ || 11.-.
28

---

Using p --++2-- p 1 for k 1 in the above sum, the definition of (Ex), and our assumption that (Yo, ....) has unit norm, we have
(I..... YI... ))l
E 1
>
1 =x
This completes the proof.
Lemma E.3. The 2-effective memory capacity bounded above as
H2 s 1000'5'/ - p)
(1)) f)-
Proof. Using Lemma E.2 to bound
||A*|| for &o 2 2, we have
H2
k2 n ph
S 00 (1)
k=
Lemma E.4. Suppose R: X is defined by R(M) 1lllM 11x. Then, is L-strongly-conve and D = max M.MEx [R(M) R(M) dx p)-
Proof. Note that R is 1-strongly-convex by definition. Using part of Lemma E. and the definition of X (Eq. (10)), have for all M, M E X,
[R(M) - R(M)
max M.MEX
1
2 |IM 123
M
max
M.MeX
||M 1
max MEX
by Eq. (11)
< max MEX
ddl M|
by Lemma E.1
1=1
"dk. P22
by Eq. (10)
< d 8 (1 p)-
This completes the proof.
Lemma E.5. We can bound the norm of the state and control at time t
max([]sell2, [| < Dx 0
29

---

Proof. We can bound the norm of and using Eqs. (14) and (15) as
8/ 12 S
F'sD
F p
GML wk- + 16-1
0=0==1
SxNpt + W
ΣΣ
p2 "xxppp"T D'W
k=0s=1
S + W WK p)
0 CWw'' (1 - p) 7)-
1+
1 10122- v
Ks; + Σ
/ Wi-s
8=1
<W -
Σ
WK p
So 7)
Above, we used the assumptions that K, W 2 1. This completes the proof.
Lemma E.6. The Lipschitz constant of ft can be bounded above
L (<oDDDxWW(l--p7
where Dx is defined in Lemma E.5.
Proof. Let (Mo.... M₁) and (Mo..., M,) be two sequences decisions, where Mj and M3 X. Let h4 and hy be the corresponding histories, and (st. u.) and (s,, ūz) be the corresponding state- control pairs at the end of round We have
(((h))-s(iie = (cr, wr) - (5t, we)l
I LoDx max{[ls; - 3elly 1lue ucllzh.
where the last inequality follows from our assumptions about the functions e, and Lemma E.5. It suffices to bound the two norms on the right-hand side in terms of like hellx. For k O,..., 1.
30

---

define Fit G - D. Using Eq. (14), we have
A+1
|10c - -
2 wk
k=0
1-1
| wk-s -
k= s=1
p 2//
p wkk
2
||0
wk 2
1 ||0 1
ST 51+1-1- || 1p20x=ss) 112
k++
k+1
G |0- +
E
2 k
2 12
(16)
s=
a=1
1-1
1+1
Σ
2 k+1
0 w
St-
2
1=1
(a)
(b)
where Eq. (16) follows from the Cauchy-Schward inequality. The specific choice of weighted norms on X' and H. allow us bound the terms (a) and (b) in terms of l| hellx. We can bound the term (a) using the definition of %
|| I1x, and || 2/ as
k+1
k+1
To(")) ||
G
Σ
p
k=0
k+1
p-*
F [
(17)
< 1
hell H
(18)
where Eq. (17) follows from part 1 of Lemma E.1 and Eq. (18) follows from the definitions of || ||x and || I/x.. Using [|wel|2 S W for all rounds t, we can bound the term (b) as
R+1
R+1
på wk
11
2
SW
W
k=0
1=1
8=1
p(1 - ph+1)
< W
2
St-k
1
< W(1 p)
(19)
where Eq. (19) follows from the definition of (Ex) (Eq. (13)). Substituting Eqs. (18) and (19)
in Eq. (16), we have
||s -5el2 S W(1 p) -11l, hellx.
31

---

Similarly,
++1
_ (M/²) /. pure
| ūz/
=
K(xt - xc) +
==1
0
1 (W(K(11-))
- p)-1
heg (x(lza)
where the last inequality follows from our assumption that || S &. and the above inequality for ||st &z l22 This completes the proof.
Lemma E.7. The Lipschitz constant of ft. can be bounded above as
I i 1L (LoDxW (11-))- p)-
where Dx is defined in Lemma E.S.
Proof. Using Lemma E.2 that bounds ||A*|], we have
|A411 S O (~^11 (n)
Using Theorem 2.1 that bounds L in terms L and the above, we have
5.5 O T -)- 0o ( Dx -p)- o)-8),
where the last inequality follows from Lemma E.6.
Now we restate and prove Theorem 4.1.
Theorem 4.1. Consider the online linear control problem defined in Section 4.1. Suppose the decisions round are chosen using Algorithm Then, the upper bound on the policy regret is
O (LoW2>VTdie
p.5
Proof. Using Theorem 3.1 and the above lemmas, we can upper bound the policy regret of Algo- rithm 1 for the online linear control problem by
o (V PTLLL
0 (Vane (1-1) (1oW2R9(1-
0)- (1 -)) x2 0) x1 p)
0 VT -4.)
This completes the proof.
E.3 Existing Regret Bound
The upper bound on policy regret for the online linear control problem in existing work is given in Agarwal et al. [2019b, Theorem 5.1]. The theorem statement only shows the dependence L, W. and T. The dependence on k, and p can be found in the details of the proof. Below we give detailed accounting of all of these terms in their regret bound.
To simplify notation let p. Agarwal al. [2019b] define
log(T)) and C= W(x2 + HKBKda)
7(1 x2 #+1 + KBK"
7
The value of a is not specified in Theorem 5.1. However, from Theorem 5.3 and the definition in Algorithm their paper, infer that KgK3.
32

---

The final regret bound is obtained by summing Equations 5.1, 5.3, and 5.4, Given the definition of H above, we have that
(1 (1-7) H+1 I exp(-x² log 7' T""""
So, the dominant term in the regret bound is Equation 5.4, which is
O (L
Substituting the values of H and C from above and collecting terms, we have that the upper bound on policy regret in existing work [Agarwal al., 2019h, Theorem 5.1] is
(oW a VT
0 Lo LoWdd (Tog y 335
( + HK
KBxOW
7(1 - 711-12(1 - 11+
?
LoWd V log (T)
-3.5
3.5
Wx²
+
Wrig x22 log(T)
+
BB
7(1 - x²(11 - 11+]
72(1 - x² - u+)
o
(Lo log 2.5
1 4.5 - x²(1 - - -11-1
+0 LoW +0
log KBK 18
5.5 (1 - 2² - 7) )
+0
LoW2d log
11 -1.5
= -0 [o V log KBh
18 18
Above we used that limt- (1 upper bound on policy regret for the online linear control problem in existing work is
x² = to simplify the expressions. Therefore,
o (Lo (Tlog(T) 1
(20)
F Online Performative Prediction
Before formulating online performative prediction problem in our OCO with unbounded memory framework, state the definition of 1- 1-Wasserstein distance that we in regret analysis. Informally, the 1-Wasserstein distance a measure of the distance between two probability measures.
Definition F.1 (1-Wasserstein Distance). Let (Z, d) be a metric space. Let (2) denote set of Radon probability measures on Z with finite first moment. That is, there exists z' E 2 such that Eggu (d(2,, =²)] < co. The I-Wasserstein distance between two probability measures v, // P(2) defined as
Wi(n, v') = sup (E.p - Es- [f,w
where the supremum is taken over all 1-Lipschitz continuous functions f: R.
F1 Formulation as OCO with Unbounded Memory
Now we formulate the online performative prediction problem our framework by defining the decision space X, the history space H. and the linear operators A H -> H and B W - H. Then, we define the functions fe regret. For notational convenience, let (ya) denote the sequence (No. V1....).
R terms of and finally, prove an upper bound on the policy
Let E (o, 1). Let the decision space X' C Rd be closed and convex with || 1|x = 11 ||-11 1|2. Let the history space H be the el -direct sum of countably infinte number of copies of X. Define the linear operators H + and : X' as
A((10, vI....)) = (0, pBo. p!l....) and B(x) = (x, O,...).
Note that the problem an OCO with p-discounted infinite memory problem and follows linear sequence dynamics with the 1-norm (Definition 2.3).
33

---

Given a sequence of decisions k= the history is he = (Tz, p. .p"....p''' data distribution Pt (h,) satisfies:
pp'''1, rı, O,... and the
iff
Fx(-R) ()= (f + +''PI
(21)
k=1
This follows from the recursive definition of p: and parametric assumption about D(z). Define the functions ft H
+ [0, 1] by
fe(he) Ee-w, (Ire, =)].
With the above formulation and definition of ft, the original goal of minimizing the difference between the algorithm's 's total loss and the total loss of the best fixed decision equivalent to minimizing the policy regret.
Σ f((hd)
Σ f() ZER
min
F.2 Regret Analysis
Lemma F.1. The operator norm ||A*]] is bounded above as
Proof. Recall the definition of H and || 1| Let
(yo, vI,...) (zo, ptt1, p² ...))....)
be element of H with unit norm, i.e.,
M1uell = 1.
From the definition of the operator A, we have
A ((Jo: .). = (o....,., O, xo t xr ......).
Now we bound ||A*|| as follows. By definition of A and || llxes we have
||A ((yo. WI.
1)11
+
Σ
||ax||
1ykk
= p²
1==
k=0
k=
Lemma F2. The L-effective memory capacity is bounded above as H2 S O ((1-))
Proof. Using Lemma F.1 to bound ||,A*|, have
Hi k |
Σ kp <0((1 k=
0=0
Lemma E.3. Suppose R + R is defined by R(x) = 1/11 Then, it is 1-strongly-comvex and
D = maxx,aex R(xx) - R(ā) < Dy-
Proof. Note that R is I-strongly-convex by definition. By the assumption that ||>|| S Dx for all X. have that D D
Lemma E4. The Lipschitz constant of ft can be bounded above as
1
450 Lo
||F
34

---

Proof. Let (21....,2z)) 2x) and (ă1...... kx) be two sequences of decisions, where Ty. E d. Let hy and he be the corresponding histories, and Pr and pt be the corresponding distributions the end of round t. We have
(1a) fi(
|BenD (e =)] - Bzni [Te =)]1
B.g (1 2)] Bggup (e 2)] + Eawn (Tt, Ba-i, (T 2)]l S Lo - #e|12 + Wo (pt,Pt);
where the last inequality follows from the assumptions about the functions 4 and the definition the Wasserstein distance W1. By definition of pt (Eq. (21)), we have
p p | xe-k -
P
|12 hellze. P
where the last inequality follows from the definition || l1x.. Therefore, S Lo 1-2 F112.
Lemma F.. The Lipschitz constant of ft can be bounded above as
i is ( (1F1))))))))
Lo
Proof. Using Lemma F.1 that bounds ||A*|, have
- (1 (1-))
k=0
Using Theorem 2.1 that bounds f. in terms of L, and the above, we have
Lo Lo- 1111))
i O (((((111)-11
where the last equality follows from Lemma F.4.
Now we restate and prove Theorem 4.2.
Theorem 4.2. Consider the online performative prediction problem defined in Section 4.2. Suppose the decisions in round t are chosen using Algorithm 1. Then, the upper bound on the policy regret is
o (D=+ooTii4/)a111>>))
Proof. Using Theorem 3.1 and the above lemmas, we can upper bound the policy regret of Algo- rithm 1 for the online performative prediction problem by
o ( P ( =0 (DxLoollFlalLL pp) -p-
This completes the proof.
We note that the upper bound can be improved by defining a weighted norm on H. similar to the approach in Appendix E. However, here present the looser anaysis for simplicity of exposition.
G Implementation Details for Algorithm 1
In this section we discuss how implement Algorithm I efficiently.
35

---

Dimensionality of X. First, note that the decisions E X' could be high-dimensional, e.g., an unbounded sequence of matrices as the online linear control problem, but this is external to our framework and is application dependent. Our framework can be applied to X' or to lower- dimensional decision space X". However, the choice of X' and analyzing the difference
E --in a' EEX"
min
Σ f((z)
TEX
is application dependent. For example, for the online linear control problem one could consider restricted class of disturbance-action controllers that operate on a constant number of past disturbances as opposed to all the past disturbances, and then analyze the difference between these two policy classes. See, for example, Agarwal al. [2019b, Lemma 5.2].
Computational cost of each iteration of Algorithm 1. Now we discuss how to implement each iteration of Algorithm efficiently. We are interested in the computational cost of computing the decision 1 as a function of t. (Given the above discussion about the dimensionality of X' we ignore the fact that the dimensionality of the decisions themselves could depend on t.) Therefore, for the purposes of this section we (i) use O-)) notation to hide absolute constants and problem parameters excluding t and T; (ii) invoke the operators A and B by calling oracles Oa(-) and Og (+); and (iii) evaluate the functions Se by calling oracles (t,,,)). -). Recall from Assumption A1 that we assume the learner knows the operators A and B, and observes ft at the end of each round So, the oracles O,, OB, and Oy are readily available.
Algorithm chooses the decision Fz+11
R(x)
R(x) "
Tt+1 E arg min
Σ f(xx) REX
arg min xEX
Σ Sa
Σ K=D
A
Bæ
+
"
-P)(a)
Since (x) is sum of fi,.... fi. evaluating F; (x) requires ((t) oracle calls to O,. However, this issue is present FTRL for OCO and OCO with finite memory as well and is not specific to our framework. To deal with this issue, Altschuler and Talwar, 2018, Chen et al., 2020] such as Algorithm 2.
could consider mini-batching algorithms [Dekel et al., 2012,
A naïve implementation to evaluate (z) could require O(t*) oracle calls to O,A: for each E [t]. constructing the argument Σi= A Bz for fo could require le oracle calls to O to compute A Bz, for total of (s²²) oracle calls. However, F.(x)) can be evaluated with just (l) oracle calls to Ox by constructing the arguments incrementally. For 2 0, define r, X - H as
To(2) Ba
Te(x)) = A (x) for t 2 1.
Note that [.(B)) A'Ba. Also, for 2 1, define $, : X - H as
Φ (z) (z) (x) for 2
ro(
Note that (,(x)) = Σi=1 A Bx is the argument for Sa. These can be constructed incrementally as follows.
1. Construct (z) using one oracle call Og.
2. For s =
(a) Construct (x) = (=(
(b) Construct (1r) from [2( using one oracle call to O
3. For 8 2 2,
(a) Construct & (x) by adding (x)) and (x)) This can be done in O(1) time. Recall from our earlier discussion that O(-) hides absolute constants and problem parameters excluding and T.
(b) Construct (xx)) from (=)1(x) using one oracle call to OA-
By incrementally constructing (xr) as above, we can evaluate (x( in O()) time with 0(1) oracle calls to Og. Ott) oracle calls to O and O(t) oracle calls to Oy.
36

---

Memory usage of Algorithm 1. end with brief discussion of the memory usage of Algorithm 1. We are interested in the memory usage of computing the decision I++1 1 as function of t. (Given the discussion about the dimensionality of X' at the start of this section, we ignore the fact that the dimensionality of the decisions themselves could depend on f.) For each E (T), the memory usage could be low as O(1) (if, for example, X' C _ and A, B Igd which implies that (z) is d-dimensional vector) or as high as (t) (if, for example, (x(z) is t-length sequence of d-dimensional vectors). However, the memory usage is already (2(t) to store the functions f Therefore, Algorithm only incurs a constant factor overhead.
H An Algorithm with A Low Number of Switches: Mini-Batch FTRL
this section we present an algorithm (Algorithm 2) for OCO with unbounded memory that provides the same upper bound on policy regret as Algorithm 1 while guaranteeting small number of switches. Algorithm 2 combines FTRL on the functions fo with mini-batching approach. First, divides rounds into batches of size S, where S a parameter. Second, at the start of batch b (1....,77ss}} it performs FTRL the functions {91,.... (91,....9b) where 9i is the average of the functions S. in batch Then, it this decision for the entirety of the current batch. By design, Algorithm switches decisions at most O(T/s) times. This algorithm insipired by similar algorithms for online learning and OCO [Dekel al., 2012, Altschuler and Talwar, 2018, Chen et al., 2020].
[7/s]],
Algorithm 2: Mini -atch FTRL
Input Time horizon T, step size a-strronglycoonex regularizer R X + IR, batch size S. Initialize history hg 0.
2 for i 1,2.... ..2..... T do
it' mod S 1 then
Let N, {1...., [] denote the number of batches so far. For b E No, let To {bb - 1)8 + ........$) denote the rounds in batch b.
For E No, let gb E.er, Sa. denote the average of the functions in batch b.
Learner chooses E arg minzex ODEN,96(1)) 7
R(x)
end else end
10
Learner chooses xe = Tt-1.
12
Set h, Ah;-1 + Bag,
Learner suffers loss fha) and observes fe.
14
end
Theorem H.1. Consider online convex optimization with unbounded memory problem specified by
(X, H. A, B). Let the regularizer R: X + IR be a-strongly and satisfy [R(z) R(ã) S D
for all x, X. Algorithm with batch size S and step-size 1) satisfies
SD
TÎ?
TLLH.
Ry (MiniiBBata FTRL) S
+
+
Sa
Ifn
aSD Ti( ( E
then
RM(Mini-Bateh FTRL) so (vPr
P (LiHI +Si²)
Setting the batch size to be S = L. / we obtain the same upper bound policy regret as Algorithm while guaranteeing that the decisions 24 switch at most Tİ/L.H, times.
Corollary H.1. Consider an online convex optimization with unbounded memory problem specified by (X, H. A. B). Let the regularizer R. X + RR be a-strongly-conver and satisfy [R(z) R(Ø) D
37

---

for all I E X. Algorithm 2 with batch size S LHL and step-size 1
aSD TL 12
satisfies
Ry FTRL) so
Furthermore, the decisions 24 switch at most
TÈ LH1 times.
Intuitively, in the OCO with unbounded memory framework each decision x; is penalized not just in round t but in future rounds as well. Therefore, instead of immediately changing the decision, it is prudent to stick to it for while, collect more data, and then switch decisions. For the OCO with finite memory problem, the constant memory length m provides a natural measure of how long decisions penalized for and when one should switch decisions. In the general case, this is measured by the quantity /. Note that this simplifies to m for OCO with finite memory for p-norms.
Proof of Theorem H.I. For simplicity, assume that T is multiple of S. Otherwise, the same proof works after replacing T with [- Let x= arg zix Et fe(x)) Note that write the regret as
T
T
BMiiiiBBatch FTRL) = Σ Se(he)
min NEN
f((x)
t=1
t=1
T
Se(ha) - f. +
Σ
- f((x*)
-
(a)
(6)
We can bound the term (b) using Theorem B.1 for mini-batches [Dekel et al., 2012, Altschuler and
Talwar, 2018, Chen al., 2020] by
SD
+ Tī²
It remains to bound term (a). Let = T/s denote the number of batches and T, = {(n 1)5- +
1. n denote the rounds in batch [N]. We can write
T
Σ f((b)) f(())))((x)))))
Σ
f
A BBB
ft
Σ A Bxi
by Definition 2.1
T
1-1
< T.
Σ A Bat-
Σ
A Bri
by Assumption A4
k=0
1 Σ LET
A Bri
A B
K=
k=
where the last inequality follows because of the following. Consider rounds t b,S + r and t2 b2S r for bj < by and r E [S). Then, || Ei= A ArBx,, S ||,, - ^ Bx, because the latter sums over more terms in its history and decisions in consecutive batches have distance bounded above by n4/a (Theorem 1. Therefore, suffices to show that term (c) is upper bounded by n/. We have
1-1
Σ KETN
A Bri
Σ A
S
A Bri A Br,
BETN
Σ
TN K=D
Σ
Σ
| xIll
by Assumption A2.
BETN K=D
38

---

Since the same decision 2n, is chosen in all rounds of batch n. we can reindex and rewrite
Σ
A B
Σ
A
| - xzll
TETN
k=0
0=
tETN k= 0
S- N-1 8
I 11 - Inll
0=0
N-11
(N - m-]mm]l
i S-IN-1
= " ΣEΣ
where the last inequality follows from bounding the distance between decision in consecutive batches Theorem B.1 and the triangle inequality. Expanding the triple sum yields
8-1N-1 s
Σ Σ (1
o=
< |||| + +...4 + || + 21145+11|| +... + + 311 |28+1
+ +... + 335 +... ||42||| +... || + 2 + + 2||42 3 2 + +... + 3 311 13s11 +
+ ||A + +...
+1.....112255---11 1| 2 + .... +2 2/|428-1 +3114455| +.... 45-1 +...,
, - 11. Adding up these terms yields where each line above corresponds to a value of o E (0....,, H1. This completes the proof.
Note that Theorem H.1 only provides upper bound on the policy regret for the general case. Unlike Algorithm 1, it is unclear how to obtain a stronger bound depending on H, for the case of linear sequence dynamics with the g-weighted p-norm for p > 1. The above proof can be specialized for this special case, similar to the proofs of Theorem 2.1 and Lemma C.I, to obtain
N- mllAAn (ml1Atnn)))4tttoo)) $
[-1
i.
S-1
A BrI-k
Σ R=0
A
S
17 a
Σ
TENN
0=
and
N-1 S Σ
71| (1[44(0)))+++000
R=1 s=1
(I|AIPP- + ||AS||P + 2 1 |p +... 211421p +3 1 pP...))+....*
+ (1A2310- + || + A +... 2" 14 ||2 + 3" A +...)
(IASIP++... +... 1|1 + 2 +... P...SIPP......55...... 2211 + +3 3211435 P
+...)
The above expression cannot be easily simplified to O(Hp). However, for the special case of OCO with finite memory, which follows linear sequence dynamics with the 2-norm, we can do so by leveraging the special structure of the linear operator Añnite,m.
Theorem H.2. Consider an online convex optimizution with finite memory problem with constant memory length m specified by (X, H X Afmite.m Bjunee... ). Let the regularizer R. X - be a-strongly-comver and satisfy [R(z) R(ž) < D for all x, I E X. Algorithm 2 with batch size m
39

---

and step-size q
omD Ti (i(2+++)
satisftes
RI (Néni-Bater FTRL) so ( 0
D
T13
my
Furthermore, the decisions switch at most I. times.
Proof. Given the proof of Theorem H.1 and the above discussion, it suffices show that 2 1 H2 m
2(nl)(((nn)) (mllA(l-1)Sttttoo))
Recall that ||itee = & m and otherwise. Using this and m, we have that the above sum most ym + mm I+ + VI - (ma) This completes the proof.
I Experiments
In this section we present simple simulation experiments.
Problem Setup. We consider the problem of online linear control with constant input controller class 11 {TT (s)) E U}. Let I denote the time horizon. Let S I2 and t {u E g ||u]|2 S 1] denote the state and control spaces. Let 8, and ut denote the state and control at time with s0 being the initial state. The system evolves according to linear dynamics 8 Fs; + Gu, Wt. where F.G E [dddd are system matrices and wy E I&d is disturbance. The loss function in round t is simply (st,, u4) = (s(s; = Σラ= St,j where St.j denotes the j-th coordinate of st. The goal is to choose a sequence of control inputs ug. uT E l to minimize the regret
T-1 min MEll
(5 u.)
cs u),
t=
where se denotes the state round upon choosing control input u in each round. Note that the state in round f can be written as
F F
Σ F wk
Therefore, we can formulate this problem as an OCO with unbounded memory problem by setting
X' = U.H (y E Rd === Ei GkGu for some u lf and t E N), A(h) = Fh, B(x) Ga. and (h.).) at dimensional.
F. (kGur- + Et= I (k Note that H, A, and B all finite-
Data. We set the time horizon T 750 and dimension d = 2. We sample the disturbances {w,} from a standard normal distribution. We set the system matrix G to be the identity and the system matrix F be diagonal plus upper triangular matrix with the diagonal entries equal p and the upper triangular entries equal to a. We run simulations with various values of p and a.
Implementation. We the cvxpy library [Diamond and Boyd, 2016, Agrawal al., 2018] for implementing Algorithm 1. We use step-sizes according to Theorems 3.1 and 3.3. We run the experiments standard laptop.
40

---

Results. We compare the regret with respect to the optimal control input of OCO with unbounded memory and OCO with finite memory for various memory lengths m in Fig. for p 0.90 and Fig. for p = 0.95. There are few important takeaways.
OCO with unbounded memory either performs as well as or better than OCO with finite memory, and it does at comparable computational cost (Appendix G). In fact, the regret curve for OCO with unbounded memory reaches an asymptote whereas this is not the case for OCO with finite memory for a variety of memory lengths.
2. Knowledge of the spectral radius of F, p. is not sufficient to tune the memory length m for OCO with finite memory. This is illustrated by comparing Figs. 3a to 3d. Even though small memory lengths perform well when the upper triangular value is small, they perform poorly when the upper triangular value large. In contrast, OCO with unbounded memory performs well in all cases.
3. For a fixed memory length, OCO with unbounded memory eventually performs better than OCO with finite memory. This illustrated by comparing Figs. 3a to 3d.
4. As increase the memory length, the performance of OCO with finite memory eventually approaches that of OCO with unbounded memory. However, an advantage OCO with unbounded memory is that does require tuning the memory length. For example, when P p= 0.90 and the upper triangular entry of F = 0. 0.10, OCO with finite memory with m = performs comparably m and m 16 (Fig. 3c). However, when the upper triangular entry of F 0.12, then it performs much worse (Fig. 3d). However, OCO with unbounded memory performs well in all cases without the need for tuning an additional hyperparameter in the form of memory length.
rho 0.9, val
rho val
700
700
000
Regret
500
Regret
400
300
400
200
-M-1
0CD-FM-4
000-MM-1
100
000-NN-8
100
000-1M-1
CCC-TM-16
100
200
300
400
500
000
700
100
200
300
400
500
000
700
Time
Time
(a)
(b)
d 2, rho 0.9, ut val 0.1
d 2, rho 0.9, ut val 0.12
1000
800
1000
Regret
Regret
800
OCO-UM
OCO-UM
200
0C0-F4-4
OCO-F168
200
0C0-F4-4
0CD-F4-1
OC0-F4-1
OC0-F416
(c)
(d)
Figure 3: Regret plot for p 0.90. The label OCO-UM refers to formulating the problem an OCO with unbounded memory problem. The OCD-FM-m refers formulating the problem as an OCO with finite memory problem with constant memory length The titles of the plots indicate the values of the dimension, the diagonal entries F, and the upper triangular entries of F.
41

---

rho 0.95, ut val 0.02
2, rho 0.95, ut val 0.04
2200
1250
Regret
800
Regrat
1000
600
750
OCO-UM
500
200
250
0CD-4%
OCO-NW-15
000-F4415
(a)
(b)
tho 0.95, val 0.05
rho 0.95,
0.06
2000
2500
2000
Regret
Regret
JU00
OCO UM
OCO UM
0C0 FM-1
0C0 F411
OC0-F44
OC0-FW16
OCO.F4416
100
200
300
400
500
000
700
100
200
300
400
500
000
700
Time
Time
(c)
(d)
d 2. rho 0.95, ut val 0.07
1000
2500
1000
DCC-FM-1
DCC-FM-4
500
DOC-FN-5
430
Time
(c)
Figure 4: Regret plot for p 0.95. The label OCD-UM refers to formulating the problem OCO with unbounded memory problem. The OCD-FM-m refers to formulating the problem as an OCO with finite memory problem with constant memory length The titles of the plots indicate the values of the dimension, the diagonal entries of F, and the upper triangular entries of F.
42


Reviews:
[{"review_id": "YqOGXmcbd6", "reviewer": "Reviewer_cA1Y", "summary": "This paper studies a generalization of online convex optimization (OCO) with memory. The setting allows the current stage cost to depend on all past decisions via a discrete-time linear dynamical system. The authors proposed a follow-the-regularized-leader algorithm that can achieve a sublinear static regret against any fixed action. They also showed a lower bound that matches the regret upper bound in the order of horizon $T$ and Lipschitz constants. The authors discussed two applications of their results to online control and online performative prediction.", "questions": "Please see my comments in the previous section. I gave the score based on my current understanding about the similarity with online control, and I would be happy to raise the score if the authors address my concern.", "limitations": "The authors discussed about some future directions in Section 5.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Theory for online (convex) optimization with unbounded memory is important in the field of learning for control. While this problem is intractable in general, it is good to see results that formally define the “effective memory” and study the corresponding upper/lower bounds.", "weaknesses": "My major concern about this work is about the problem setting: I believe the setting proposed here is a special case of online control with adversarial disturbances (e.g., [Agarwal et al., 2019b]). Specifically, the history $h_t$ corresponds to the state and the decision $x_t$ corresponds to the control input. The only difference might be the benchmark: While online control compares against the best DAC policy, this work compares with a fixed action. But the DAC policy class can easily contain any fixed action if we add a dummy dimension with entry 1 in the (adversarial) disturbances. I hope the authors can correct me if my understanding is wrong, and a discussion in the revision may be helpful.\n\nSince the proposed problem setting can be reduced to (or maybe equivalent to) online control with adversarial disturbances, one should evaluate the results in this work by comparing with not only [Agarwal et al., 2019b], but also more recent works on online control like [Minasyan et al., 2022], [Chen et al., 2022], and [Lin et al., 2022]. To the best of my knowledge, existing results can handle much more complicated settings that involves time-varying dynamics, unknown dynamics, or even nonlinear dynamics. They considered stronger benchmarks like adaptive regret or dynamic regret. I encourage the authors to do a more detailed literature review about online control and clarify the significance of the main results.\n\nBesides, I also have a concern about the time complexity of the proposed algorithm. It seems that the time/memory complexity of constructing $\\tilde{f}_t$ from past $f_1, \\cdots, f_t$ grows linearly with respect to time $t$. However, existing online control algorithms like the one in [Agarwal et al., 2019b] only requires $log(T)$ time/memory for each decision. Thus, I am not sure how practical the proposed FTRL algorithm is.\n\n[Minasyan et al., 2022]: https://arxiv.org/pdf/2202.07890.pdf\n[Chen et al., 2022]: https://arxiv.org/pdf/2110.07807.pdf\n[Lin et al., 2022]: https://arxiv.org/pdf/2210.12320v1.pdf\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad that you liked the definition of effective memory capacity, and tight upper and lower bounds on regret.\n\n## Application to Online Linear Control with Adversarial Disturbances.\n  * You are correct that our formulation of OCO with unbounded memory bears a strong resemblance to online linear control with adversarial disturbances (OLC) with a fixed control input. In fact, you would be correct in asserting that our setting is a special case of OLC **if the latter problem allowed for an infinite-dimensional state space**. However, the treatment of OLC in [Agarwal et al., 2019b] and follow-up work is limited to finite-dimensional state spaces because their regret bounds include a polynomial dependence on a dimension-dependent constant that makes them inapplicable to problems with infinite-dimensional states unless one makes additional assumptions. One of the key contributions of our work is to find the right generalization of finite-dimensionality (namely, finite effective memory capacity) that enables generalizing these results to problems with infinite-dimensional states. \n  * Our framework is *not* a special case of OLC. In fact, in lines 305-330 we show the reverse.\n    * Decisions in our framework correspond to policies in the linear control framework, not a fixed control input. The decision is a DAC policy (Definition 4.1) defined by a sequence of matrices and a fixed matrix (line 294).\n    * Our DAC policy acts on the entire history of past disturbances, whereas the \"truncated\" DAC policy used in [Agarwal et al., 2019b] only acts on a fixed, constant number of past disturbances. The class of strongly-stable linear controllers is a subset of our DAC policy class, but not a subset of the \"truncated\" DAC policy class. (See [Agarwal et al., 2019a, Section 16.5].) Unbounded-length DAC policies are why modelling an infinite-dimensional space is relevant.\n    * Our regret bound (Theorem 4.1, lines 328 - 332) improves upon the existing one by $O(d (\\log T)^{3.5} \\kappa^5 (1-\\rho)^{-1})$ (Appendix E.3). This is possible due to a novel use of defining weighted norms on the history and decision spaces, and using that to bound the relevant quantities in the upper bound (Lemmas E.2 and E.6).\n    * A \"truncated\" DAC policy is a sequence of $d \\times d$ matrices of length $2 \\kappa^4 (1-\\rho)^{-1} \\log T$ [Agarwal et al., 2019b]. Our DAC policy is a sequence of $d \\times d$ matrices of unbounded length. Yet, we capture the dimension of this infinite-dimensional space in a way that still improves the overall bound, including completely eliminating the dependence on $\\log T$, and improving the dependence on $d, \\kappa$ and $(1-\\rho)$ (Theorem 4.1 and Appendix E.3).\n  * Thank you for citing the additional works. We will add them to the revision. However, all of them analyze the problem under a finite memory approximation even though it is inherently an unbounded memory problem. We focused on addressing gaps in the OCO with memory literature by first developing the general framework of OCO with unbounded memory. Then, we proved an upper bound and a **tight lower bound** on the regret, including a previously unknown, tight lower bound for OCO with finite memory. The basic online control setting is just one application - we also consider an application to a performative prediction problem, showing how our general framework can unify two seemingly disparate areas of work. The value of our work lies in (i) an improvement in the upper bound for control (Theorem 4.1); (ii) a simplification of the regret analysis; (iii) a new lens to study extensions that you cited. Our improvements will carry over to these extensions after developing appropriate extensions of our framework, and it is an important direction for future work.\n\n## Time complexity of the proposed algorithm.\n  * We provide details for efficient implementation of Algorithm 1 in Appendix G. Here, we summarize how it only has a constant overhead compared to standard FTRL and FTRL for OCO with finite memory (Algorithm 1 in Anava et al.)\n    * Our Algorithm 1 chooses iterate $x_{t+1}$ as the minimizer of $\\sum_{s=1}^t f_s(\\sum_{k=0}^{s-1} A^k B x) + \\frac{R(x)}{\\eta}$. Each such minimization problem requires evaluating $\\sum_{s=1}^t f_s(\\sum_{k=0}^{s-1} A^k B x)$. In Appendix G, we show how to do this in $O(t)$ time by iteratively updating the function arguments. Here, $O(\\cdot)$ notation hides constant factors excluding $t$ and $T$ but includes constant factors related to the dimensionality of the decision space. See Appendix G for details.\n    * Standard FTRL and Algorithm 1 of Anava et al. also choose iterate $x_{t+1}$ by minimizing over a sum of $t$ functions. For example, Algorithm 1 of Anava et al. chooses iterate $x_{t+1}$ as the minimizer of $\\sum_{s=1}^t f_s(x, \\dots, x) + \\frac{R(x)}{\\eta}$. Each such minimization problem requires evaluating $\\sum_{s=1}^t f_s(x, \\dots, x)$. This takes $O(t)$ time, where the $O(\\cdot)$ notation hides constant factors excluding $t$ and $T$ but includes constant factors related to the dimensionality of the decision space.\n  * For OLC specifically, the squared-norm regularizer $R$ (Lemma E.4) results in an update rule similar in spirit to online gradient descent and the existing algorithm in [Agarwal et al., 2019b]. The dimensionality of our decision space depends on $O(T)$, whereas it depends on $O(\\log T)$ in [Agarwal et al., 2019b]. This is the only factor in $T$ that leads to a difference between the runtimes of the two algorithms. One can change our decision space to be the \"truncated\" DAC policy class and the runtime will depend on $O(\\log T)$. This will introduce an error term that is the difference between the costs of the best strongly-stable linear controller and of the best \"truncated\" DAC policy. We can bound this using Lemma 5.2 of [Agarwal et al., 2019b]. This is not the dominant term in the regret bound (Appendix E.3 of our paper), so the final bound is unchanged."}, {"review_id": "bZfw6TKYo4", "reviewer": "Reviewer_i8qJ", "summary": "The paper considers an online learning problem between a learner and adversary. The learner chooses action $x_t$ each round, and the state $h_t$ evolves according to the dynamics $h_t = Ah_{t-1} + Bx_t$. The oblivious adversary commits to a loss function $f_t$ each round. The learner suffers cumulative loss $\\sum f_t(h_t)$. This paper uses FTRL to solve this problem. ", "questions": "na", "limitations": "The authors addressed limitations and directions for future work. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper studies online learning with a linear control component. The framework captures a setting where past decisions affect future loss. The paper presented theoretical results with upper and lower bounds. \n\nThe paper showed that the difficulty of this problem is captured by the so-called $p$-effective memory, which essentially quantifies the memory(less) property of the operator $A$. ", "weaknesses": "While the problem proposed in this paper is seemingly new, it does seem to shed much new algorithmic ideas and insights. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad that you liked the definition of effective memory capacity, and tight upper and lower bounds on regret.\n\n## \"While the problem proposed in this paper is seemingly new, it does seem to shed much new algorithmic ideas and insights.\"\n\n  * From context (i.e., the fact that this sentence was listed under \"Weaknesses\") we suspect the reviewer meant to write \"_doesn't seem to shed much new algorithmic ideas and insights_\" rather than \"_does_ seem to shed...\". It's true that the algorithmic ideas and insights in our paper are strongly influenced by Anava et al.'s (2015) use of FTRL to solve online convex optimization with finite memory. An important innovation in our work is the use of weighted norms to prove regret bounds in the case of linear sequence dynamics, which allows us to derive non-trivial regret bounds in the case of unbounded-length histories and even leads to improved regret bounds in the case of online linear control (lines 328 - 330 and Appendix E.3). A brief summary of the novelty and technical contributions is as follows:\n    \n    * Our OCO with unbounded memory framework and upper bound (Algorithm 1 and its analysis) might seem like simple extensions of their OCO with finite memory counterparts. However, we believe it is a feature that our framework and upper bound provide a clean abstraction for the user that they can use for a variety of applications. For instance, our framework allows the user to define non-standard norms on the decision and history spaces. This can be a simple but powerful way of encoding prior knowledge about a problem. The technical complications that arise from this are captured in bounding the relevant quantities of interest, e.g., the Lipschitz constant $\\tilde{L}$, the operator norm $\\| A \\|$, etc. Indeed, consider the application to online linear control with adversarial disturbances (section 4.1). Our seemingly simple framework and upper bound applied to this problem (Theorem 4.1 and Appendix E.3) improve upon the existing upper bound, which used a finite memory approximation. See Lemmas E.2 and E.6 for an illustration of the technical details involved when using non-standard norms, e.g., lines 885 - 891 in the proof of Lemma E.6.\n  \n    * One of our main technical contributions is the **first lower bound** for OCO with finite memory, and therefore, for OCO with unbounded memory. Furthermore, this **lower bound is tight**. Our tight lower bound, which was previously unknown and uses new technical ideas, shows that the upper bound is unimprovable in the worst-case. Therefore, without additional assumptions, no other algorithm or proof technique can improve the upper bound in the worst-case. (We also provide an explicit proof of the lower bound for OCO with $\\rho$-discounted infinite memory problem in Theorem D.2 in the appendix.)\n  \n    * As alluded to above, another technical contribution is the upper bound for online linear control with adversarial disturbances (Theorem 4.1, lines 328 - 332), which improves upon existing results (lines 328 - 330 and Appendix E.3). Our regret bound (Theorem 4.1, lines 328 - 332) quantitatively improves upon the existing one (lines 328 - 330 and Appendix E.3). This is possible due to a novel use of defining weighted norms on the history and decision spaces, and using that to bound the relevant quantities in the upper bound (Lemmas E.2 and E.6)."}, {"review_id": "jgP8gNhG14", "reviewer": "Reviewer_xqDp", "summary": "This paper introduces a problem called online convex optimization (OCO) with unbound memory, which generalizes an existing problem called OCO with memory. To address this problem, the authors propose an algorithm called FTRL and analyze its regret. Moreover, the authors demonstrate that this new problem and their algorithm have several applications.", "questions": "1) Please explain the reasons for only considering the history determined by fixed linear operators.\n2) It would be better if the authors could conduct experiments by setting the parameters of algorithms according to their theoretical guarantees.", "limitations": "There does not exist a potential negative societal impact.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1) The problem of online convex optimization (OCO) with unbound memory is more general than the existing problem called OCO with memory.\n2) The proposed algorithm enjoys a regret bound and has some applications.\n3) It seems that the results in this paper can simplify the regret anlysis for the problem of online linear control.", "weaknesses": "1) The extension from OCO with memory to OCO with unbound memory seems to be straightforward. Moreover, the algorithm for OCO with unbound memory and the corresponding analysis are very similar to existing algorithms for OCO with memory and their analysis. So, to some extent, the novelty of this paper is limited.\n2) Although OCO with unbound memory seems to be more challenging, the authors only consider the history determined by fixed linear operators, i.e., $A$ and $B$ in the paper. Moreover, the authors do not explain why they only consider this case.\n3) In the experiments, the authors simply set the step size of the proposed algorithm and the existing algorithms as $1/\\\\sqrt{T}$, instead of tuning it according to their theoretical guarantees. In this way, it is not clear whether the improvement in experiments is consistent with their theoretical guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad that you liked the generality of our framework and the simplification of the results for online linear control.\n\n## Novelty of the extension from OCO with finite memory to OCO with unbounded memory.\n\n  * Our OCO with unbounded memory framework and upper bound (Algorithm 1 and its analysis) might seem like simple extensions of their OCO with finite memory counterparts. However, we believe it is a feature that our framework and upper bound provide a clean abstraction for the user that they can use for a variety of applications. For instance, our framework allows the user to define non-standard norms on the decision and history spaces. This can be a simple but powerful way of encoding prior knowledge about a problem. The technical complications that arise from this are captured in bounding the relevant quantities of interest, e.g., the Lipschitz constant $\\tilde{L}$, the operator norm $\\| A \\|$, etc. Indeed, consider the application to online linear control with adversarial disturbances (section 4.1). Our seemingly simple framework and upper bound applied to this problem (Theorem 4.1 and Appendix E.3) improve upon the existing upper bound, which used a finite memory approximation. See Lemmas E.2 and E.6 for an illustration of the technical details involved when using non-standard norms, e.g., lines 885 - 891 in the proof of Lemma E.6.\n\n  * One of our main technical contributions is the **first lower bound** for OCO with finite memory, and therefore, for OCO with unbounded memory. Furthermore, this **lower bound is tight**. Our tight lower bound, which was previously unknown and uses new technical ideas, shows that the upper bound is unimprovable in the worst-case. Therefore, without additional assumptions, no other algorithm or proof technique can improve the upper bound in the worst-case. (We also provide an explicit proof of the lower bound for OCO with $\\rho$-discounted infinite memory problem in Theorem D.2 in the appendix.)\n\n  * As alluded to above, another technical contribution is the upper bound for online linear control with adversarial disturbances (Theorem 4.1, lines 328 - 332), which improves upon existing results (lines 328 - 330 and Appendix E.3). Our regret bound (Theorem 4.1, lines 328 - 332) quantitatively improves upon the existing one (lines 328 - 330 and Appendix E.3). This is possible due to a novel use of defining weighted norms on the history and decision spaces, and using that to bound the relevant quantities in the upper bound (Lemmas E.2 and E.6).\n\n## History is determined by fixed linear operators.\n\n  * We consider linear operators because the composition of such operators with convex functions remains convex. Nonlinear dynamics would lead to non-convexity. That is, if $f_t$ is convex, then $\\tilde{f}\\_t(x) = f_t ( \\sum_{s=0}^{t-1} A^s B x )$ is convex if $A$ and $B$ are linear operators. Instead, if the history evolved according to nonlinear dynamics, then $\\tilde{f}_t(x)$ would be $f_t$ applied to a $t$-fold composition of nonlinear operators acting on $x$, and this may not be convex.\n\n## Choice of the step-size in the experiments.\n\n  * We have attached a PDF to the global response with after running the experiments with the theoretically optimal step-size. We will update the revision with these experiments."}, {"review_id": "RTfZyGEyEd", "reviewer": "Reviewer_58kP", "summary": "This paper focuses on online convex optimization with memory, a topic with increasing attention recently. Traditional framework assumes that the current environment is only affected by the decisions of a limited past, while this work considers that the current environment is affected by \\emph{all} previous decisions. Specifically, the authors generalize the existing framework by studying the sequences of decisions in a typical sequence space. The authors then define the notion of memory capacity with the help of a bounded weighted norm in such sequence space and achieve new policy regret bounds. The authors verify its applicability by reducing several problems into the proposed framework, including variants of online linear control and performative prediction. ", "questions": "Please see the comments above.", "limitations": "Please see the comments above.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1)\tThe motivation is meaningful. It is definitely important in online learning literature to capture the historical impact in the sequence. \n\n(2)\tThe solution is simple, and the proof is clear and correct. ", "weaknesses": "(1)\tMy first concern comes from the novelty of the proposed framework. Although it enables an infinite memory length, the impact of history is modelled as typical linear operators, and positive results are obtained only when the operator behaves like a geometric combination of past decisions, which has been studied in some areas like linear control and reinforcement learning. Could the authors provide more special cases (in sec. 2.3), or elaborate more (in the paragraph just above def 2.3), to show that the proposed framework does give some new intuition to this problem? \n\n(2)\tThe technical contribution seems insufficient. The results mostly follows that of the traditional proofs in (Anava et al., 2015), with the operations on a finite sequence replaced by linear operators in functional space of sequences. Could the authors highlight the technical contributions in the proofs of their theory? For example, the explanation of (theorem 3.4) is quite clear and intuitive, is there something worth highlighted in the main results of the upper bounds?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review. We are glad you found the motivation meaningful, and the liked the simplicity and clarity of our proofs.\n\n## Novelty of the extension from OCO with finite memory to OCO with unbounded memory and technical contributions.\n\n  * Our formulation of OCO with unbounded memory bears a strong resemblance to online linear control with adversarial disturbances. In fact, you would be correct in asserting that our setting is a special case of online linear control with adversarial disturbances **if the latter problem allowed for an infinite-dimensional state space**. However, the treatment of online linear control in [Agarwal et al., 2019b] and follow-up work is limited to finite-dimensional state spaces because their regret bounds include a polynomial dependence on a dimension-dependent constant that makes them inapplicable to problems with infinite-dimensional state unless one makes additional assumptions. One of the key contributions of our work is to find the right generalization of finite-dimensionality (namely, finite effective memory capacity) that enables generalizing these results to problems with infinite-dimensional state. \n  \n  * Our OCO with unbounded memory framework and upper bound (Algorithm 1 and its analysis) might seem like simple extensions of their OCO with finite memory counterparts. However, we believe it is a feature that our framework and upper bound provide a clean abstraction for the user, while at the same time giving them a lot of power and hiding the technical details. For instance, our framework allows the user to define non-standard norms on the decision and history spaces. This can be a simple but powerful way of encoding prior knowledge about a problem. The technical complications that arise from this are captured in bounding the relevant quantities of interest, e.g., the Lipschitz constant $\\tilde{L}$, the operator norm $\\| A \\|$, etc. Indeed, consider the application to online linear control with adversarial disturbances (section 4.1). Our seemingly simple framework and upper bound applied to this problem (Theorem 4.1 and Appendix E.3) improve upon the existing upper bound, which used a finite memory approximation. See Lemmas E.2 and E.6 for an illustration of the technical details involved when using non-standard norms, e.g., lines 885 - 891 in the proof of Lemma E.6.\n  \n  * One of our main technical contributions is the **first lower bound** for OCO with finite memory, and therefore, for OCO with unbounded memory. Furthermore, this **lower bound is tight**. While the proof of the upper bound is an extension of existing proofs, our tight lower bound, which was previously unknown and uses new technical ideas, shows that the upper bound is unimprovable in the worst-case. Therefore, without additional assumptions, no other algorithm or proof technique can improve the upper bound in the worst-case. (We also provide an explicit proof of the lower bound for OCO with $\\rho$-discounted infinite memory problem in Theorem D.2 in the appendix.)\n\n  * Another technical contribution is the upper bound for online linear control with adversarial disturbances (Theorem 4.1, lines 328 - 332), which improves upon existing results (lines 328 - 330 and Appendix E.3). Our regret bound (Theorem 4.1, lines 328 - 332) quantitatively improves upon the existing one (lines 328 - 330 and Appendix E.3). This is possible due to a novel use of defining weighted norms on the history and decision spaces, and using that to bound the relevant quantities in the upper bound (Lemmas E.2 and E.6)."}]

Author rebuttal:
We have responded to each reviewer individually. This global rebuttal only includes plots for the experiments requested by Reviewer xqDp.

Meta-review: This paper attacks OCO with memory by casting the history into a banach space and applying online learning in that space. A key application is in adversarial control, where considering the appropriate Banach space allows the authors to reduce a dimension factor in previous bounds. Theory-oriented papers can have significant value along several axes, including (but not limited to): (1) generating novel technical approaches, (2) improving results on known and well-studied problems,  and (3) developing a novel and interesting setting of study. Some reviewers raise concerns about (1) and (3): the techniques used in the paper are relatively standard, and the setting of adversarial control is also well-studied. However, this  paper satisfies (2) by improving the general OCO with memory bounds and applying them to improve the adversarial control bounds by a polynomial factor in the dimension. Such dimension factor improvements are relatively rare and so this represents a significant enough contribution to be accepted.
Decision: Accept (poster)