Back

Non-stationary Online Learning with Memory and Non-stochastic Control

Peng ZhaoYu-Hu YanYu-Xiang WangZhi-Hua Zhou

article2023JMLR58 citations

Develops a switching-cost-aware online ensemble method that achieves optimal dynamic policy regret for online convex optimization with memory and yields the first provably competitive gradient-based controller for non-stationary, non-stochastic control.

Listen

Real-world sequential decision-making systems—such as real-time recommendation engines, automated traffic control, and cyber-physical systems—frequently operate in non-stationary, open environments where conditions continuously change. In these settings, current costs and performance outcomes depend not only on immediate actions but also on past decisions, creating temporal memory effects. Standard online decision-making frameworks primarily evaluate performance against a single, static best strategy in hindsight, making them ill-suited for dynamically shifting environments.

The article establishes robust online optimization and control frameworks for changing environments by designing algorithms that explicitly minimize dynamic policy regret. This metric benchmarks the algorithm's performance against an arbitrary sequence of time-varying policies rather than a single fixed policy.

The authors develop a theoretical framework centered on a two-layer meta-base online ensemble architecture. In this design, multiple base learners operate in parallel with different learning rates, while a meta-learner dynamically combines their outputs. To overcome the core technical bottleneck—the accumulation of decision movement known as switching cost—the article introduces a switching-cost-regularized surrogate loss and an epoch-based lazy update mechanism. The approach is subsequently applied to online non-stochastic control in linear dynamical systems subject to adversarial disturbances, both for known system dynamics and unknown systems estimated via random-input system identification.

The article yields four primary findings. First, the proposed framework attains an optimal dynamic policy regret bound across total time horizon, environmental fluctuation (comparator path length), and memory length, matching theoretical minimax lower bounds. Second, by introducing a lazy update schedule, the algorithm eliminates memory-dependent performance degradation, achieving optimal linear dependence on memory length. Third, when applied to online non-stochastic control, the resulting controller becomes the first to provably compete with time-varying dynamic policies. Fourth, empirical simulations on non-stationary online learning benchmarks, synthetic time-varying dynamical systems, and a physical inverted pendulum demonstrate that the proposed method consistently achieves lower cumulative losses than traditional online gradient descent and standard dynamic regret methods that ignore switching costs.

These findings provide actionable algorithmic principles for managing non-stationary environments and temporal delays without requiring prior knowledge of how rapidly the system will shift. Incorporating switching-cost awareness into multi-expert ensemble systems guarantees bounded decision volatility, mitigating operational instability and high control costs in real-world deployments. Organizations managing automated infrastructure, robotics, and online resource allocation should adopt switching-cost-regularized ensemble architectures to make systems resilient against adversarial disturbances and environmental drift.

Decision-makers should note that the theoretical guarantees rely on standard assumptions of convexity in the unary loss functions, bounded action domains, and linear system dynamics with strong stability or controllability. While high-confidence theoretical and empirical validation is demonstrated for convex costs, further evaluation is warranted before deploying in highly nonlinear environments or regimes where only bandit feedback (loss values without gradient information) is accessible.

Nanjing UniversityUniversity of California, Santa Barbaraonline learningstochasticstochastic controlnon-stationary online learningnon-stochastic controlonline convex optimization
arXiv: 2102.03758

No sufficiently relevant recommendations were found.

Cover for Non-stationary Online Learning with Memory and Non-stochastic Control

Abstract

We study the problem of Online Convex Optimization (OCO) with memory, which allows loss functions to depend on past decisions and thus captures temporal effects of learning problems. In this paper, we introduce dynamic policy regret as the performance measure to design algorithms robust to non-stationary environments, which competes algorithms’ decisions with a sequence of changing comparators. We propose a novel algorithm for OCO with memory that provably enjoys an optimal dynamic policy regret in terms of time horizon, non-stationarity measure, and memory length. The key technical challenge is how to control the switching cost, the cumulative movements of player’s decisions, which is neatly addressed by a novel switching-cost-aware online ensemble approach equipped with a new meta-base decomposition of dynamic policy regret and a careful design of meta-learner and base-learner that explicitly regularizes the switching cost. The results are further applied to tackle non-stationarity in online non-stochastic control (Agarwal et al., 2019), i.e., controlling a linear dynamical system with adversarial disturbance and convex cost functions. We derive a novel gradient-based controller with dynamic policy regret guarantees, which is the first controller provably competitive to a sequence of changing policies for online non-stochastic control.

Topics

online learningstochasticstochastic controlrandom access memory

Keywords

non-stationary online learningnon-stochastic controlonline convex optimizationdynamic regretonline gradient descentnon-stationary DAC policyadaptive regret minimizationdynamic policy regret minimizationtime-varying controllersadaptive control

Table of Contents

  • 1. Introduction
  • 2. Related Work
  • 3. Preliminaries
  • 4. OCO with Memory
  • 4.1 A Gentle Start: known path length
  • 4.2 Challenge: unknown path length and switching cost of OCO with memory
  • 4.3 Algorithmically Enforcing Low Switching Cost: a new meta-base decomposition
  • 4.4 Improved Algorithm with an Optimal Memory Dependence
  • 5. Online Non-stochastic Control
  • 5.1 Problem Statement
  • 5.2 Reduction to OCO with Memory
  • 5.3 Dynamic Policy Regret of Online Non-stochastic Control
  • 6. Experiment
  • 6.1 OCO with Memory
  • 6.2 Online Non-stochastic Control
  • 7. Conclusion
  • Acknowledgments
  • Appendix A. Preliminaries
  • A.1 Dynamic Regret of Memoryless OCO
  • A.2 Additional Notions
  • A.3 Technical Lemmas
  • Appendix B. Omitted Details for Section 4 (OCO with Memory)
  • B.1 Proof of Theorem 1
  • B.2 Proof of Switching Cost Decomposition
  • B.3 Additional Results for Online Mirror Descent
  • B.4 Proof of Theorem 2
  • B.5 Proof of Theorem 3
  • B.6 Proof of Theorem 4
  • B.7 Proof of Theorem 5
  • B.8 Discussion on Memory Dependence
  • Appendix C. Omitted Details for Section 5 (Non-stochastic Control)
  • C.1 Proof of Proposition 6
  • C.2 Proof of Theorem 7
  • C.2.1 Approximation Error
  • C.2.2 Dynamic Regret Analysis over M -space
  • C.2.3 Proof of Theorem 7
  • C.3 Proof of Theorem 8
  • C.3.1 Proof of Theorem 8
  • C.3.2 Key Lemmas in Unknown Systems
  • C.4 Proof of Corollary 9
  • C.5 Supporting Lemmas
  • References

Knowls

  1. Knowl 1 — Dynamic policy regret for online learning with memory

    definition

    Let wt∈Ww_t\in\mathcal W be the learner’s decision at round tt, where W\mathcal W is a feasible set, and let ft:Wm+1→Rf_t:\mathcal W^{m+1}\to\mathbb R be a loss depending on the current decision and the previous mm decisions. For a comparator sequence v1:T=(v1,…,vT)v_{1:T}=(v_1,\ldots,v_T) in W\mathcal W, dynamic policy regret is

    D ⁣-Regret⁡T(v1:T)=∑t=1Tft(wt−m:t)−∑t=1Tft(vt−m:t),\operatorname{D\!\text{-}Regret}_T(v_{1:T})=\sum_{t=1}^T f_t(w_{t-m:t})-\sum_{t=1}^T f_t(v_{t-m:t}),

    where wt−m:t=(wt−m,…,wt)w_{t-m:t}=(w_{t-m},\ldots,w_t) and vt−m:t=(vt−m,…,vt)v_{t-m:t}=(v_{t-m},\ldots,v_t) denote the decision histories used by the loss. The comparator path length is PT=∑t=2T∥vt−vt−1∥2P_T=\sum_{t=2}^T\|v_t-v_{t-1}\|_2; it measures comparator variation and hence the non-stationarity against which the learner is evaluated. A fixed comparator is the special case PT=0P_T=0.

  2. Knowl 2 — Assumptions and reduction of memory losses to unary losses

    model/method

    In online convex optimization with memory, each ft:Wm+1→Rf_t:\mathcal W^{m+1}\to\mathbb R is assumed convex on the diagonal: its unary loss f~t(w)=ft(w,…,w)\widetilde f_t(w)=f_t(w,\ldots,w) is convex in ww. The losses are LL-coordinate-wise Lipschitz, meaning ∣ft(x0,…,xm)−ft(y0,…,ym)∣≤L∑i=0m∥xi−yi∥2|f_t(x_0,\ldots,x_m)-f_t(y_0,\ldots,y_m)|\le L\sum_{i=0}^m\|x_i-y_i\|_2. The feasible set W⊆Rd\mathcal W\subseteq\mathbb R^d is convex and has diameter at most DD, and the unary-loss gradients satisfy ∥∇f~t(w)∥2≤G\|\nabla\widetilde f_t(w)\|_2\le G for all w∈Ww\in\mathcal W. Define λ=m2L\lambda=m^2L.

    Under these conditions, the memory-dependent regret is bounded by a unary-loss dynamic regret plus movement penalties for the learner and comparator:

    D ⁣-Regret⁡T(v1:T)≤∑t=1Tf~t(wt)−∑t=1Tf~t(vt)+λ∑t=2T∥wt−wt−1∥22+λPT.\operatorname{D\!\text{-}Regret}_T(v_{1:T})\le \sum_{t=1}^T\widetilde f_t(w_t)-\sum_{t=1}^T\widetilde f_t(v_t)+\lambda\sum_{t=2}^T\|w_t-w_{t-1}\|_2^2+\lambda P_T.

    Thus, controlling the learner’s cumulative squared movement is essential in addition to competing with changing comparators on the unary losses.

  3. Knowl 3 — Switching-cost-aware meta-base regret decomposition

    equation

    Suppose a learner combines NN base learners with weights pt=(pt,1,…,pt,N)p_t=(p_{t,1},\ldots,p_{t,N}) in the probability simplex ΔN\Delta_N, producing wt=∑i=1Npt,iwt,iw_t=\sum_{i=1}^N p_{t,i}w_{t,i} from base decisions wt,i∈Ww_{t,i}\in\mathcal W. For unary loss f~t\widetilde f_t, define the linearized loss gt(x)=⟨∇f~t(wt),x⟩g_t(x)=\langle\nabla\widetilde f_t(w_t),x\rangle and the switching-cost-regularized surrogate loss ℓt,i=gt(wt,i)+λ∥wt,i−wt−1,i∥22\ell_{t,i}=g_t(w_{t,i})+\lambda\|w_{t,i}-w_{t-1,i}\|_2^2. For every fixed base index ii, convexity and the bounded diameter DD imply

    ∑t=1Tf~t(wt)−∑t=1Tf~t(vt)+λ∑t=2T∥wt−wt−1∥22≤∑t=1T(⟨pt,ℓt⟩−ℓt,i)+λD∑t=2T∥pt−pt−1∥1⏟meta-learner regret and weight movement+∑t=1T(gt(wt,i)−gt(vt))+λ∑t=2T∥wt,i−wt−1,i∥22⏟base-learner regret and movement.\begin{aligned} &\sum_{t=1}^T\widetilde f_t(w_t)-\sum_{t=1}^T\widetilde f_t(v_t)+\lambda\sum_{t=2}^T\|w_t-w_{t-1}\|_2^2\\ &\le \underbrace{\sum_{t=1}^T\bigl(\langle p_t,\ell_t\rangle-\ell_{t,i}\bigr)+\lambda D\sum_{t=2}^T\|p_t-p_{t-1}\|_1}_{\text{meta-learner regret and weight movement}}\\ &\quad+\underbrace{\sum_{t=1}^T\bigl(g_t(w_{t,i})-g_t(v_t)\bigr)+\lambda\sum_{t=2}^T\|w_{t,i}-w_{t-1,i}\|_2^2}_{\text{base-learner regret and movement}}. \end{aligned}

    Here vt∈Wv_t\in\mathcal W is the comparator, and ℓt=(ℓt,1,…,ℓt,N)\ell_t=(\ell_{t,1},\ldots,\ell_{t,N}). Penalizing each base learner’s movement inside ℓt,i\ell_{t,i} lets the meta-learner favor slower-moving bases; the bound then requires controlling the movement of a selected base rather than the weighted movement of every base.

  4. Knowl 4 — Scream switching-cost-regularized ensemble

    algorithm

    Scream operates on online convex optimization with memory under the assumptions stated here: W\mathcal W is convex with diameter at most DD, unary losses f~t\widetilde f_t are convex with gradients bounded by GG, and memory losses are LL-coordinate-wise Lipschitz. Set λ=m2L\lambda=m^2L. Its inputs are the horizon TT and these problem parameters; its output is a decision sequence w1:Tw_{1:T}.

    Use N=⌈12log⁡2(1+T)⌉+1N=\lceil\tfrac12\log_2(1+T)\rceil+1 base learners with step sizes

    ηi=2i−1D2(λG+G2)T,i=1,…,N.\eta_i=2^{i-1}\sqrt{\frac{D^2}{(\lambda G+G^2)T}},\qquad i=1,\ldots,N.

    Initialize each base decision in W\mathcal W and initialize the meta-weights by p1,i∝1/(i(i+1))p_{1,i}\propto 1/(i(i+1)), normalized so that p1∈ΔNp_1\in\Delta_N. At each round, combine the current base decisions as wt=∑ipt,iwt,iw_t=\sum_i p_{t,i}w_{t,i} and incur the memory loss on the resulting decision history. Compute the shared gradient ∇f~t(wt)\nabla\widetilde f_t(w_t), then form gt(x)=⟨∇f~t(wt),x⟩g_t(x)=\langle\nabla\widetilde f_t(w_t),x\rangle and ℓt,i=gt(wt,i)+λ∥wt,i−wt−1,i∥22\ell_{t,i}=g_t(w_{t,i})+\lambda\|w_{t,i}-w_{t-1,i}\|_2^2. Update the meta-weights by Hedge, pt+1,i∝pt,iexp⁡(−εℓt,i)p_{t+1,i}\propto p_{t,i}\exp(-\varepsilon\ell_{t,i}), with ε=2/((2λ+G)(λ+G)D2T)\varepsilon=\sqrt{2/((2\lambda+G)(\lambda+G)D^2T)}. Update every base learner by projected gradient descent, wt+1,i=ΠW[wt,i−ηi∇f~t(wt)]w_{t+1,i}=\Pi_{\mathcal W}[w_{t,i}-\eta_i\nabla\widetilde f_t(w_t)]. Because all bases use the same gradient, only one unary-loss gradient needs to be computed per round.

  5. Knowl 5 — Lazy Scream and its dynamic policy regret guarantee

    theoretical result

    Lazy Scream applies Scream with episodic rather than per-round updates. Let λ=m2L\lambda=m^2L and choose an epoch length Δ=λ\Delta=\sqrt{\lambda}. During each epoch the learner submits the same decision at every round, accumulates the unary-loss gradients, and sends the cumulative gradient to Scream for an update at the epoch’s end. Under the convexity, coordinate-wise Lipschitzness, bounded-gradient, and bounded-domain assumptions for online convex optimization with memory, Lazy Scream satisfies, for every comparator sequence v1:Tv_{1:T},

    D ⁣-Regret⁡T(v1:T)=O ⁣(λT(1+PT)+λPT),\operatorname{D\!\text{-}Regret}_T(v_{1:T})=O\!\left(\sqrt{\lambda T(1+P_T)}+\lambda P_T\right),

    where PT=∑t=2T∥vt−vt−1∥2P_T=\sum_{t=2}^T\|v_t-v_{t-1}\|_2. The episodic updates improve the dependence on the memory-induced switching-cost coefficient compared with the per-round Scream updates. The paper also establishes that the corresponding dynamic-regret rate for online convex optimization with switching cost is minimax optimal in the switching-cost coefficient, horizon, and comparator path length.

  6. Knowl 6 — Minimax lower bound for online convex optimization with switching cost

    theoretical result

    Let W\mathcal W be a feasible set of diameter at most DD, let online convex losses ht:W→Rh_t:\mathcal W\to\mathbb R have gradients bounded in norm by GG, and let λ>0\lambda>0 be the coefficient on squared decision movement. For any τ∈[0,DT]\tau\in[0,DT], there exist such losses and a comparator sequence v1:T∈Wv_{1:T}\in\mathcal W with path length ∑t=2T∥vt−vt−1∥2≤τ\sum_{t=2}^T\|v_t-v_{t-1}\|_2\le\tau for which every online algorithm’s decisions w1:Tw_{1:T} satisfy

    ∑t=1Tht(wt)−∑t=1Tht(vt)+λ∑t=2T∥wt−wt−1∥22=Ω ⁣(λτT).\sum_{t=1}^T h_t(w_t)-\sum_{t=1}^T h_t(v_t)+\lambda\sum_{t=2}^T\|w_t-w_{t-1}\|_2^2=\Omega\!\left(\sqrt{\lambda\tau T}\right).

    This lower bound shows that the dependence on λ\lambda, TT, and comparator path length in the switching-cost dynamic-regret guarantee cannot generally be improved.

  7. Knowl 7 — Disturbance-action control as online convex optimization with memory

    model/method

    Consider a linear dynamical system xt+1=Axt+But+wtx_{t+1}=Ax_t+Bu_t+w_t, where xt,wt∈Rdxx_t,w_t\in\mathbb R^{d_x}, ut∈Rduu_t\in\mathbb R^{d_u}, and the system matrices AA and BB are known. A disturbance-action controller with memory length HH uses a fixed linear controller KK and matrices Mt=(Mt[1],…,Mt[H])M_t=(M_t^{[1]},\ldots,M_t^{[H]}) to choose ut=−Kxt+∑i=1HMt[i]wt−iu_t=-Kx_t+\sum_{i=1}^H M_t^{[i]}w_{t-i}. The past disturbances are recoverable from the dynamics as wt=xt+1−Axt−Butw_t=x_{t+1}-Ax_t-Bu_t.

    To obtain a fixed-memory online loss, the controller replaces the exact state and action by truncated versions computed from only the most recent HH disturbance inputs. In particular, with A~K=A−BK\widetilde A_K=A-BK, define

    Ψt,iK,h(Mt−h:t)=A~Ki1i≤h+∑j=0hA~KjBMt−j[i−j]11≤i−j≤H,yt+1K=∑i=02HΨt,iK,H(Mt−H:t)wt−i,vt+1K=−Kyt+1K+∑i=1HMt+1[i]wt+1−i,\Psi_{t,i}^{K,h}(M_{t-h:t})=\widetilde A_K^i\mathbf 1_{i\le h}+\sum_{j=0}^{h}\widetilde A_K^jB M_{t-j}^{[i-j]}\mathbf 1_{1\le i-j\le H},\qquad y_{t+1}^K=\sum_{i=0}^{2H}\Psi_{t,i}^{K,H}(M_{t-H:t})w_{t-i},\qquad v_{t+1}^K=-Ky_{t+1}^K+\sum_{i=1}^H M_{t+1}^{[i]}w_{t+1-i},

    where 1⋅\mathbf 1_{\cdot} is an indicator and M[r]=0M^{[r]}=0 for indices outside 1,…,H1,\ldots,H. The truncated loss is ft(Mt−H−1:t)=ct(ytK,vtK)f_t(M_{t-H-1:t})=c_t(y_t^K,v_t^K), so control becomes online convex optimization with memory length H+2H+2. If disturbances have norm at most WW, KK is (κ,γ)(\kappa,\gamma)-strongly stable, the costs have bounded gradients on the relevant state-action domain, and ∥Mt[i]∥op≤τ(1−γ)i\|M_t^{[i]}\|_{\mathrm{op}}\le\tau(1-\gamma)^i, the total truncation error is at most 2TGcD02κ3(1−γ)H+12TG_cD_0^2\kappa^3(1-\gamma)^{H+1}, with D0=Wκ3(1+HκBτ)γ[1−κ2(1−γ)H+1]+WτγD_0=\frac{W\kappa^3(1+H\kappa_B\tau)}{\gamma[1-\kappa^2(1-\gamma)^{H+1}]}+\frac{W\tau}{\gamma}; here GcG_c bounds the cost gradients and κB\kappa_B bounds ∥B∥op\|B\|_{\mathrm{op}}.

  8. Knowl 8 — Dynamic policy regret of Scream.Control for known systems

    theoretical result

    For online control of xt+1=Axt+But+wtx_{t+1}=Ax_t+Bu_t+w_t with known, bounded system matrices, adversarial disturbances of bounded norm, and convex online costs with bounded values and gradients on the relevant state-action domain, Scream.Control uses the disturbance-action parameterization and runs Scream on the truncated losses. The fixed linear controller KK is assumed (κ,γ)(\kappa,\gamma)-strongly stable: there exist matrices Q,LQ,L with A−BK=QLQ−1A-BK=QLQ^{-1}, ∥L∥op≤1−γ\|L\|_{\mathrm{op}}\le1-\gamma, and ∥K∥op,∥Q∥op,∥Q−1∥op≤κ\|K\|_{\mathrm{op}},\|Q\|_{\mathrm{op}},\|Q^{-1}\|_{\mathrm{op}}\le\kappa. The policy parameters lie in M={M:∥M[i]∥op≤κBκ3(1−γ)i, i=1,…,H}\mathcal M=\{M: \|M^{[i]}\|_{\mathrm{op}}\le\kappa_B\kappa^3(1-\gamma)^i,\ i=1,\ldots,H\}.

    Choose truncation memory H=Θ(log⁡T)H=\Theta(\log T). For any comparator sequence of disturbance-action policies πt=π(K,Mt∗)\pi_t=\pi(K,M_t^*) with Mt∗∈MM_t^*\in\mathcal M, define PT=∑t=2T∥Mt∗−Mt−1∗∥FP_T=\sum_{t=2}^T\|M_t^*-M_{t-1}^*\|_F. The resulting controller guarantees

    ∑t=1Tct(xt,ut)−∑t=1Tct(xtπt,utπt)=O~ ⁣(T(1+PT)),\sum_{t=1}^T c_t(x_t,u_t)-\sum_{t=1}^T c_t(x_t^{\pi_t},u_t^{\pi_t})=\widetilde O\!\left(\sqrt{T(1+P_T)}\right),

    where O~\widetilde O suppresses logarithmic factors in TT. A fixed comparator gives the O~(T)\widetilde O(\sqrt T) static policy-regret guarantee for known systems.

  9. Knowl 9 — Dynamic policy regret with unknown control dynamics

    theoretical result

    When AA and BB are unknown, the paper extends Scream.Control by first performing random-input system identification and then deploying the controller using the estimated dynamics. During T0T_0 exploration rounds, it applies ut=−Kxt+u~tu_t=-Kx_t+\widetilde u_t, where the entries of u~t\widetilde u_t are independent Rademacher random variables. For a controllability index kk, form Nj=1T0−k∑t=0T0−k−1xt+j+1u~t⊤N_j=\frac{1}{T_0-k}\sum_{t=0}^{T_0-k-1}x_{t+j+1}\widetilde u_t^\top for j=0,…,kj=0,\ldots,k, set C^0=[N0,…,Nk−1]\widehat C_0=[N_0,\ldots,N_{k-1}] and C^1=[N1,…,Nk]\widehat C_1=[N_1,\ldots,N_k], and estimate B^=N0\widehat B=N_0, A^K=C^1C^0⊤(C^0C^0⊤)−1\widehat A_K=\widehat C_1\widehat C_0^\top(\widehat C_0\widehat C_0^\top)^{-1}, and A^=A^K+B^K\widehat A=\widehat A_K+\widehat B K. The system is assumed strongly controllable: Ck=[B,(A−BK)B,…,(A−BK)k−1B]C_k=[B,(A-BK)B,\ldots,(A-BK)^{k-1}B] has full row rank and ∥(CkCk⊤)−1∥op≤κc\|(C_kC_k^\top)^{-1}\|_{\mathrm{op}}\le\kappa_c.

    Under the boundedness, stability, cost, and strong-controllability assumptions, and for a sufficiently large horizon, choosing T0=Θ(T2/3)T_0=\Theta(T^{2/3}) yields, with high probability, for any disturbance-action comparator sequence with path length PT=∑t=2T∥Mt∗−Mt−1∗∥FP_T=\sum_{t=2}^T\|M_t^*-M_{t-1}^*\|_F,

    ∑t=1Tct(xt,ut)−∑t=1Tct(xtπt,utπt)=O~ ⁣(T(1+PT)+T2/3).\sum_{t=1}^T c_t(x_t,u_t)-\sum_{t=1}^T c_t(x_t^{\pi_t},u_t^{\pi_t})=\widetilde O\!\left(\sqrt{T(1+P_T)}+T^{2/3}\right).

    The additional T2/3T^{2/3} term accounts for exploration and system-estimation error; for a fixed comparator, the resulting high-probability static policy regret is O~(T2/3)\widetilde O(T^{2/3}).

  10. Knowl 10 — Empirical comparisons in memory-based learning and online control

    empirical result

    In the online convex optimization experiment, the authors simulated T=50,000T=50{,}000 rounds in dimension d=10d=10, with a squared prediction loss and a target model that changed every 1,000 rounds (50 changes). They compared OGD, Ader, and Scream under switching-cost coefficients λ=αG\lambda=\alpha G for α∈{0.1,1,2}\alpha\in\{0.1,1,2\}, measuring cumulative loss, switching cost, and their sum; each experiment was repeated five times and reported as a mean and standard deviation. At α=0.1\alpha=0.1, Ader had the best overall cost and Scream was comparable; at α=1\alpha=1, Scream performed best overall; at α=2\alpha=2, OGD performed best and Scream was comparable. Ader incurred relatively high switching cost, while OGD moved slowly but had weaker performance on changing losses. The results are consistent with Scream balancing adaptation and movement penalties rather than optimizing either alone.

    For online control, the comparison used OGD.Control, Ader.Control, and Scream.Control on synthetic linear dynamical systems with gradual or abrupt changes and on an inverted-pendulum environment. Cumulative cost was the performance measure, and each experiment was repeated five times. Scream.Control achieved lower cumulative cost than both alternatives across the three environments, supporting the empirical value of combining a meta-base structure with switching-cost regularization.

Coverage note — Proofs and supporting technical lemmas are omitted because they serve primarily to establish the stated guarantees; the separate lower bound for bounded-loss expert algorithms with switching cost is also omitted as an intermediate result supporting the motivation for Lazy Scream.

References

  1. 1.Yasin Abbasi-Yadkori and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory (COLT), pages 1–26, 2011.
  2. 2.Naman Agarwal, Brian Bullins, Elad Hazan, Sham M. Kakade, and Karan Singh. Online control with adversarial disturbances. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 111–119, 2019.
  3. 3.Jason Altschuler and Kunal Talwar. Online learning over a finite action set with limited switching. In Proceedings of the 31st Conference on Learning Theory (COLT), pages 1569–1573, 2018.
  4. 4.Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: Price of past mistakes. In Advances in Neural Information Processing Systems 28 (NIPS), pages 784–792, 2015.
  5. 5.Raman Arora, Teodor Vanislavov Marinov, and Mehryar Mohri. Bandits with feedback graphs and switching costs. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 10397–10407, 2019.
  6. 6.Dheeraj Baby and Yu-Xiang Wang. Online forecasting of total-variation-bounded sequences. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 11071–11081, 2019.
  7. 7.Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-concave online learning. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 359–409, 2021.
  8. 8.Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in proper online learning with strongly convex losses and beyond. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1805–1845, 2022.
  9. 9.Dheeraj Baby, Saurabh Garg, Tzu-Ching Yen, Sivaraman Balakrishnan, Zachary Chase Lipton, and Yu-Xiang Wang. Online label shift: Optimal dynamic regret meets practical algorithms. ArXiv preprint, arXiv:2305.19570, 2023.
  10. 10.Yong Bai, Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama, and Zhi-Hua Zhou. Adapting to online label shift with provable guarantees. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 29960–29974, 2022.
  11. 11.Omar Besbes, Yonatan Gur, and Assaf J. Zeevi. Non-stationary stochastic optimization. Operations Research, 63(5):1227–1244, 2015.
  12. 12.Avrim Blum and Adam Kalai. Universal portfolios with and without transaction costs. Machine Learning, 35(3):193–205, 1999.
  13. 13.Olivier Bousquet and Manfred K. Warmuth. Tracking a small set of experts by mixing past posteriors. Journal of Machine Learning Research, 3:363–396, 2002.
  14. 14.Asaf Cassel and Tomer Koren. Bandit linear control. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 8872–8882, 2020.
  15. 15.Asaf B. Cassel, Alon Cohen, and Tomer Koren. Efficient online linear control with stochastic convex costs and unknown dynamics. In Proceedings of 35th Conference on Learning Theory (COLT), volume 178, pages 3589–3604, 2022a.
  16. 16.Asaf B. Cassel, Alon Peled-Cohen, and Tomer Koren. Rate-optimal online convex optimization in adaptive linear control. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 7410–7422, 2022b.
  17. 17.Nicolò Cesa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
  18. 18.Nicolò Cesa-Bianchi, Yoav Freund, David Haussler, David P. Helmbold, Robert E. Schapire, and Manfred K. Warmuth. How to use expert advice. Journal of the ACM, 44(3):427–485, 1997.
  19. 19.Nicolò Cesa-Bianchi, Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems 25 (NIPS), pages 989–997, 2012.
  20. 20.Nicolò Cesa-Bianchi, Ofer Dekel, and Ohad Shamir. Online learning with switching costs and other adaptive adversaries. In Advances in Neural Information Processing Systems 26 (NIPS), pages 1160–1168, 2013.
  21. 21.Gong Chen and Marc Teboulle. Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM Journal on Optimization, 3(3):538–543, 1993.
  22. 22.Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of switching-constrained online convex optimization: No phase transition. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 3477–3486, 2020.
  23. 23.Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In Proceedings of the 31st Conference on Learning Theory (COLT), pages 1574–1594, 2018.
  24. 24.Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 1029–1038, 2018.
  25. 25.Ashok Cutkosky. Parameter-free, dynamic, and strongly-adaptive online learning. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 2250–2259, 2020.
  26. 26.Amit Daniely and Yishay Mansour. Competitive ratio vs regret minimization: Achieving the best of both worlds. In Proceedings of the 30th International Conference on Algorithmic Learning Theory (ALT), pages 333–368, 2019.
  27. 27.Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz. Strongly adaptive online learning. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1405–1411, 2015.
  28. 28.Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):633–679, 2020.
  29. 29.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), pages 1747–1754, 2012.
  30. 30.Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: T²/₃ regret. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 459–467, 2014.
  31. 31.Claude-Nicolas Fiechter. PAC adaptive control of linear systems. In Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT), pages 72–80, 1997.
  32. 32.Dylan J. Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 3211–3221, 2020.
  33. 33.Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997.
  34. 34.Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In Proceedings of the 23rd Conference on Learning Theory (COLT), pages 132–143, 2010.
  35. 35.Gautam Goel and Babak Hassibi. Regret-optimal control in dynamic environments. ArXiv preprint, arXiv:2010.10473, 2020.
  36. 36.Gautam Goel and Babak Hassibi. Online estimation and control with optimal pathlength regret. In Proceedings of the 4th Learning for Dynamics and Control Conference (L4DC), pages 404–414, 2022a.
  37. 37.Gautam Goel and Babak Hassibi. Competitive control. IEEE Transactions on Automatic Control, in press, 2022b.
  38. 38.Gautam Goel and Adam Wierman. An online algorithm for smoothed regression and LQR control. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2504–2513, 2019.
  39. 39.Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 1873–1883, 2019.
  40. 40.Eyal Gofer. Higher-order regret bounds with switching costs. In Proceedings of The 27th Conference on Learning Theory (COLT), pages 210–243, 2014.
  41. 41.Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 10764–10774, 2020a.
  42. 42.Paula Gradu, Elad Hazan, and Edgar Minasyan. Adaptive regret for control of time-varying dynamics. ArXiv preprint, arXiv:2007.04393, 2020b.
  43. 43.Lei Guo and Lennart Ljung. Performance analysis of general tracking algorithms. IEEE Transactions on Automatic Control, 40(8):1388–1402, 1995.
  44. 44.András György and Gergely Neu. Near-optimal rates for limited-delay universal lossy source coding. IEEE Transactions on Information Theory, 60(5):2823–2834, 2014.
  45. 45.András György and Csaba Szepesvári. Shifting regret, mirror descent, and matrices. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 2943–2951, 2016.
  46. 46.Thomas P. Hayes. A large-deviation inequality for vector-valued martingales. Combinatorics, Probability and Computing, 2005.
  47. 47.Elad Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization, 2(3-4):157–325, 2016.
  48. 48.Elad Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Proceedings of the 26th International Conference on Machine Learning (ICML), pages 393–400, 2009.
  49. 49.Elad Hazan, Sham M. Kakade, and Karan Singh. The nonstochastic control problem. In Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT), pages 408–421, 2020.
  50. 50.Mark Herbster and Manfred K. Warmuth. Tracking the best expert. Machine Learning, 32 (2):151–178, 1998.
  51. 51.Mark Herbster and Manfred K. Warmuth. Tracking the best linear predictor. Journal of Machine Learning Research, 1:281–309, 2001.
  52. 52.Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 398–406, 2015.
  53. 53.Rudolf Emil Kalman. Contributions to the theory of optimal control. Boletín de la Sociedad Matemática Mexicana, 5(2):102–119, 1960.
  54. 54.Haipeng Luo and Robert E. Schapire. Achieving all with no parameters: AdaNormalHedge. In Proceedings of the 28th Annual Conference Computational Learning Theory (COLT), pages 1286–1304, 2015.
  55. 55.Haipeng Luo, Mengxiao Zhang, Peng Zhao, and Zhi-Hua Zhou. Corralling a larger band of bandits: A case study on switching regret for linear bandits. In Proceedings of the 35th Conference on Learning Theory (COLT), pages 3635–3684, 2022.
  56. 56.Neri Merhav, Erik Ordentlich, Gadiel Seroussi, and Marcelo J. Weinberger. On sequential strategies for loss functions with memory. IEEE Transactions on Information Theory, 48 (7):1947–1958, 2002.
  57. 57.Aryan Mokhtari, Shahin Shahrampour, Ali Jadbabaie, and Alejandro Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In Proceedings of the 55th IEEE Conference on Decision and Control (CDC), pages 7195–7201, 2016.
  58. 58.Arkadij S. Nemirovsky and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
  59. 59.Shai Shalev-Shwartz. Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning, 4(2):107–194, 2012.
  60. 60.Uri Sherman and Tomer Koren. Lazy OCO: Online convex optimization on a switching budget. In Proceedings of the 34th Conference on Learning Theory (COLT), pages 3972–3988, 2021.
  61. 61.Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 20636–20647, 2020.
  62. 62.Max Simchowit. Making non-stochastic control (almost) as easy as stochastic. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 18318–18329, 2020.
  63. 63.Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Proceedings of the 33rd Conference on Learning Theory (COLT), pages 3320–3436, 2020.
  64. 64.Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent. In Advances in Neural Information Processing Systems 24 (NIPS), pages 2645–2653, 2011.
  65. 65.Masashi Sugiyama and Motoaki Kawanabe. Machine Learning in Non-stationary Environments: Introduction to Covariate Shift Adaptation. The MIT Press, 2012.
  66. 66.Guanghui Wang, Yuanyu Wan, Tianbao Yang, and Lijun Zhang. Online convex optimization with continuous switching constraint. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 28636–28647, 2021.
  67. 67.Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu. Tracking the best expert in non-stationary stochastic environments. In Advances in Neural Information Processing Systems 29 (NIPS), pages 3972–3980, 2016.
  68. 68.Yu-Hu Yan, Peng Zhao, and Zhi-Hua Zhou. Fast rates in time-varying strongly monotone games. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 39138–39164, 2023.
  69. 69.Lijun Zhang. Online learning in changing environments. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pages 5178–5182, 2020. Early Career.
  70. 70.Lijun Zhang, Tianbao Yang, Jinfeng Yi, Rong Jin, and Zhi-Hua Zhou. Improved dynamic regret for non-degenerate functions. In Advances in Neural Information Processing Systems 30 (NIPS), pages 732–741, 2017.
  71. 71.Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems 31 (NeurIPS), pages 1330–1340, 2018a.
  72. 72.Lijun Zhang, Tianbao Yang, Rong Jin, and Zhi-Hua Zhou. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 5877–5886, 2018b.
  73. 73.Mengxiao Zhang, Peng Zhao, Haipeng Luo, and Zhi-Hua Zhou. No-regret learning in time-varying zero-sum games. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26772–26808, 2022a.
  74. 74.Yu-Jie Zhang, Peng Zhao, and Zhi-Hua Zhou. A simple online algorithm for competing with dynamic comparators. In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), pages 390–399, 2020.
  75. 75.Zhiyu Zhang, Ashok Cutkosky, and Ioannis Ch. Paschalidis. Adversarial tracking control via strongly adaptive online learning with memory. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 8458–8492, 2022b.
  76. 76.Zhiyu Zhang, Ashok Cutkosky, and Yannis Paschalidis. Optimal comparator adaptive online learning with switching cost. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022c.
  77. 77.Peng Zhao. Online Ensemble Theories and Methods for Robust Online Learning. PhD thesis, Nanjing University, Nanjing, China, 2021. Advisor: Zhi-Hua Zhou.
  78. 78.Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Proceedings of the 3rd Conference on Learning for Dynamics and Control (L4DC), pages 48–59, 2021.
  79. 79.Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 12510–12520, 2020.
  80. 80.Peng Zhao, Guanghui Wang, Lijun Zhang, and Zhi-Hua Zhou. Bandit convex optimization in non-stationary environments. Journal of Machine Learning Research, 22(125):1–45, 2021a.
  81. 81.Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Adaptivity and non-stationarity: Problem-dependent dynamic regret for online convex optimization. ArXiv preprint, arXiv:2112.14368, 2021b.
  82. 82.Peng Zhao, Long-Fei Li, and Zhi-Hua Zhou. Dynamic regret of online markov decision processes. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 26865–26894, 2022a.
  83. 83.Peng Zhao, Yu-Xiang Wang, and Zhi-Hua Zhou. Non-stationary online learning with memory and non-stochastic control. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2101–2133, 2022b.
  84. 84.Kai Zheng, Haipeng Luo, Ilias Diakonikolas, and Liwei Wang. Equipping experts/bandits with long-term memory. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 5927–5937, 2019.
  85. 85.Zhi-Hua Zhou. Ensemble Methods: Foundations and Algorithms. Chapman & Hall/CRC Press, 2012.
  86. 86.Zhi-Hua Zhou. Open-environment machine learning. National Science Review, 9(8):nwac123, 07 2022.
  87. 87.Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 928–936, 2003.

Citation

MLA
Zhao, P., et al. “Non-stationary Online Learning with Memory and Non-stochastic Control”. Journal of Machine Learning Research, 2023, 2021, http://arxiv.org/abs/2102.03758v4.
APA
Zhao, P., Yan, Y.-H., Wang, Y.-X., & Zhou, Z.-H. (2021). Non-stationary Online Learning with Memory and Non-stochastic Control. Journal of Machine Learning Research, 2023. http://arxiv.org/abs/2102.03758v4
Chicago
Zhao, P., Y.-H. Yan, Y.-X. Wang, and Z.-H. Zhou. 2021. “Non-stationary Online Learning with Memory and Non-stochastic Control”. Journal of Machine Learning Research, 2023. http://arxiv.org/abs/2102.03758v4.
Harvard
Zhao, P. et al. (2021) “Non-stationary Online Learning with Memory and Non-stochastic Control”, Journal of Machine Learning Research, 2023 [Preprint]. Available at: http://arxiv.org/abs/2102.03758v4.
Vancouver
1. Zhao P, Yan Y-H, Wang Y-X, Zhou Z-H (2021) Non-stationary Online Learning with Memory and Non-stochastic Control. Journal of Machine Learning Research, 2023

BibTeX

@article{zhao2021non,
  title = {Non-stationary Online Learning with Memory and Non-stochastic Control},
  author = {Zhao, Peng and Yan, Yu-Hu and Wang, Yu-Xiang and Zhou, Zhi-Hua},
  year = {2021},
  journal = {Journal of Machine Learning Research, 2023},
  url = {http://arxiv.org/abs/2102.03758v4},
  eprint = {2102.03758}
}
Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/