PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis

Yingying Li, Xin Chen, Na Li

arXiv:1906.11378v3math.OC

TL;DR

Online control with time-varying costs has limited analysis of how finite predictions interact with general dynamical systems. The paper introduces RHGC, using finite gradient steps on predicted costs, and shows exponentially decreasing dynamic-regret bounds as the prediction window grows; for linear-quadratic tracking, RHTM’s upper bound nearly matches a fundamental lower bound.

  • Problem

    Prior work offers limited non-asymptotic guarantees for time-varying costs and limited study of how predictions affect online control with general dynamical systems.

    Source: §1 · pp. 1–2

  • Method

    RHGC uses finite gradient computations on predicted costs, with RHGD and RHTM as the analyzed variants.

    Source: §1 · p. 2, §3.2 · p. 6

  • Results

    RHGD and RHTM dynamic-regret bounds decay exponentially with prediction-window size, and RHTM’s upper bound nearly matches a fundamental lower bound in linear-quadratic tracking.

    Source: §1 · p. 2, §5 · pp. 8–9

  • Takeaways & Limitations

    Under the stated linear-quadratic tracking conditions, RHTM uses predictions in a nearly optimal way despite conducting only a few gradient updates per time step.

    Source: §5 · pp. 8–9

    The prediction model assumes accurate short-term forecasts and none beyond the window, a model the paper describes as potentially too optimistic short-term and too pessimistic long-term.

    Source: §2 · p. 3

Abstract

from arXiv · show

This paper studies the online optimal control problem with time-varying convex stage costs for a time-invariant linear dynamical system, where a finite lookahead window of accurate predictions of the stage costs are available at each time. We design online algorithms, Receding Horizon Gradient-based Control (RHGC), that utilize the predictions through finite steps of gradient computations. We study the algorithm performance measured by dynamic regret: the online performance minus the optimal performance in hindsight. It is shown that the dynamic regret of RHGC decays exponentially with the size of the lookahead window. In addition, we provide a fundamental limit of the dynamic regret for any online algorithms by considering linear quadratic tracking problems. The regret upper bound of one RHGC method almost reaches the fundamental limit, demonstrating the effectiveness of the algorithm. Finally, we numerically test our algorithms for both linear and nonlinear systems to show the effectiveness and generality of our RHGC.

1 Introduction

The paper studies online control of time-varying costs with finite predictions, where prior work leaves gaps in non-asymptotic guarantees and in understanding predictions for general dynamical systems. It proposes RHGC and analyzes its dynamic regret.

1 Introduction

  • The setting is a finite-horizon decision problem in which each action uses a W-step window of future costs to control a known linear time-invariant system.The paper notes applications including data centers, robotics, autonomous driving, energy systems, and manufacturing.Source: §1 · p. 1
  • Control studies emphasize EMPC, but non-asymptotic guarantees remain limited, especially for time-varying costs and computationally efficient suboptimal or inexact MPC.Online optimization studies regret but generally do not combine predictions with dynamical systems.Source: §1 · p. 1
  • Although research increasingly studies predictions in online problems, general dynamical systems and the effect of predictions on them remain understudied; switching costs cover only a special dynamical case [36].Source: §1 · p. 2
  • RHGC provides non-asymptotic dynamic-regret guarantees, with RHGD and RHTM bounds that decay exponentially as the prediction window grows.The paper also gives a fundamental lower bound and reports that RHTM’s upper bound nearly matches it.Source: §1 · p. 2
  • Compared with online optimization using switching costs [36], this work treats general linear dynamics and studies how controllability affects regret.Source: §1 · p. 2
  • Unlike learning-based control, which typically learns unknown dynamics in a time-invariant environment, this paper assumes known dynamics and studies changing objectives with limited predictions [44] [46] [48].Combining the two lines of work is proposed as a future direction.Source: §1 · p. 2

2 Problem formulation and preliminaries

The paper formulates online control for time-varying costs and known linear dynamics when only a finite window of future costs is available. It measures performance against the optimal cost in hindsight and specifies assumptions on predictions, controllability, and costs.

Problem setup

  • At each time step, the controller observes the state, receives predictions of the next W costs, chooses an input, incurs the current state and control cost, and advances under known linear dynamics.The finite-horizon objective includes a terminal cost.Source: §2 · pp. 2–3

Prediction model

  • The prediction model assumes accurate costs for the next W steps and makes no accuracy guarantee beyond that window, which may be too optimistic short-term and too pessimistic long-term.Source: §2 · p. 3

Performance measure

  • Dynamic regret compares online cost with the optimal control cost in hindsight; static regret uses a weaker static-policy benchmark.The paper focuses on dynamic regret to study how predictions improve online performance.Source: §2 · p. 3

System assumptions

  • The system is assumed controllable, allowing an efficient a priori transformation to canonical form; its controllability index describes the maximum chain length in that form.The index is p = max{p1, . . . , pm}.Source: §2 · pp. 3–4

Scope

  • The stated setup assumes known A and B, no process noise, and state feedback, while leaving relaxation of these assumptions for future work.Source: §2 · p. 3

Cost assumptions

  • For theoretical analysis, state costs are strongly convex and smooth, control costs are convex and smooth, and their minimizers are uniformly bounded.These conditions apply to the analysis; the paper notes that applying RHGC does not require them.Source: §2 · p. 4

3 Online control algorithms: receding horizon gradient-based control

The paper transforms the constrained control problem into an equivalent optimization with finite temporal coupling, then uses that structure to design receding-horizon gradient methods. RHGC uses finite gradient updates based on lookahead costs, including triple momentum, and differs from suboptimal MPC by updating the complete-horizon objective.

3.1 Problem transformation

  • A bijective reparameterization turns constrained control into unconstrained optimization over z while preserving cost and yielding finite temporal coupling.Each transformed stage cost depends only on nearby decision variables.Source: §3.1 · p. 5

3.2 Online algorithm design: RHGC

  • RHGC uses finite neighboring-cost dependence to compute gradients with lookahead information, then translates decisions in z back into control actions.The method applies online gradient algorithms such as gradient descent or triple momentum.Source: §3.2 · pp. 5–6
  • RHTM achieves near-optimal performance with respect to the prediction window despite using only a few gradient updates.RHTM applies triple-momentum updates and uses the same number of iterations as RHGD for a given lookahead window.Source: §3.2 · p. 6
  • Unlike suboptimal MPC, RHGC uses a few gradient iterations on the complete N-stage optimization rather than a truncated W-stage problem, at similar computation time.Suboptimal MPC instead updates a truncated optimization based on the W-step lookahead.Source: §3.2 · p. 6

4 Regret upper bounds

The regret analysis shows that RHGD and RHTM improve exponentially with longer prediction windows, with RHTM decaying faster than RHGD. The analysis also gives a regret bound for FOSS in terms of variation in optimal steady states and bias functions.

4 Regret upper bounds

  • RHGD and RHTM improve regret exponentially fast as prediction window W increases, for any initialization method.Their regret guarantees connect to the regret of the initialization oracle.Source: §4 · p. 7
  • RHTM's regret decays faster than RHGD's, consistent with triple momentum converging faster than gradient descent.The number of available iterations decreases as controllability index p increases, and the paper links larger p to increased regret.Source: §4 · p. 7
  • FOSS is motivated for slowly changing costs but is proposed mainly for analysis, and other online algorithms may outperform it.Its motivation uses the optimal steady-state cost for time-invariant LTI costs as the optimal infinite-horizon average cost.Source: §4 · p. 7
  • FOSS regret is bounded in terms of variation in the optimal steady states and bias functions; those bias functions exist for many problems, including LQ tracking.The cited bound relies on solutions to Bellman equations.Source: §4 · p. 8

5 Linear quadratic tracking: regret upper bounds and a fundamental limit

For LQ tracking with constant Q and R, RHTM with FOSS has a regret upper bound tied to trajectory variation, while a lower bound for any online algorithm nearly matches it under stated conditions. The analysis concerns tracking a time-varying reference trajectory with fixed tracking and control-cost weights.

LQ tracking setup

  • The LQ tracking case follows a time-varying trajectory θ_t while keeping the tracking and control-cost weights constant.Here Q_t = Q and R_t = R, with terminal weight P_e and θ_N = 0.Source: §5 · p. 8

Regret upper bound

  • For constant Q and R, RHTM with FOSS has a regret upper bound bounded by the total variation of θ_t.The bound uses K = floor((W−1)/p), where ζ is the condition number of C(z).Source: §5 · p. 8

Fundamental limit

  • The lower bound for any online algorithm nearly matches RHTM’s upper bound, especially for large ζ, when W ≤ N/3 and the variation budget is not too small.The theorem’s stated lower bound requires 4θ̄ ≤ L_N ≤ (2N + 1)θ̄; the authors note that smaller variation can make regret very small.Source: §5 · p. 9

6 Numerical experiments

The experiments compare RHGC methods with truncated-horizon MPC on LQ tracking and also test RHGC on a nonlinear two-wheel robot. The reported results show regret decreasing with lookahead and better robot tracking with a longer window.

LQ tracking

  • RHGD, RHTM, and RHAG achieve exponentially decaying, piecewise-constant regret as W grows, and outperform one-iteration subMPC at similar gradient-evaluation cost.RHTM and RHAG perform better than RHGD; increasing subMPC iterations improves performance, but the improvement saturates as W increases while RHGC improves steadily.Source: Figure 1 · p. 9, §6 · p. 9

Two-wheel robot

  • On the nonlinear robot, W = 40 and W = 80 correspond to 1 s and 2 s of lookahead, and the longer window improves path tracking.Tracking is good on smooth paths but deviates more at sharp turns.Source: Figure 2 · p. 9, §6 · pp. 9–10
  • The robot experiment discretizes its nonlinear dynamics with Δt = 0.025 s and applies RHGC after reformulating path tracking as unconstrained optimization over (x_t, y_t).The objective balances tracking performance and control cost.Source: §6 · p. 10

7 Conclusion

The paper develops RHGC regret guarantees for online control with linear dynamics and finds that the fundamental limit nearly matches RHTM’s upper bound. It identifies prediction noise, unknown systems, broader control settings, and alternative metrics as directions for future work.

Conclusion

  • The paper gives regret upper bounds for RHGD and RHTM and a fundamental limit that almost matches RHTM’s upper bound.The conclusion frames its study as examining how predictions affect dynamic regret in online control with linear dynamics.Source: §7 · p. 10

Future directions

  • Future work includes noisy predictions, unknown systems with process noise, nonlinear control and state or input constraints, other metrics, and closing the regret-bound gap.The authors also identify the effect of canonical-form transformation on condition number as an open direction.Source: §7 · p. 10

Appendices

The appendices collect proofs, regret extensions, and experiment details. Appendix A transforms general controllable LTI systems into canonical form so the analysis can be conducted in that representation.

Appendices

  • The appendices provide proofs for the main results and technical lemmas, extend regret analysis to more general LQ tracking problems, and detail the numerical experiments.The appendix roadmap assigns these topics to Appendices B–H.Source: Appendices · p. 14

A Canonical form

  • An invertible linear transformation of state and control converts a general LTI system into canonical form when the system is controllable.The transformation matrices can be computed offline because A and B are known in advance.Source: A Canonical form · p. 14
  • Applying the transformation to online stage costs preserves their strong convexity and smoothness, possibly with different parameters, so analysis can be restricted to canonical-form systems.For example, the transformed state cost has adjusted convexity and smoothness parameters.Source: A Canonical form · p. 14

B Triple momentum and a proof of Theorem 1

Triple momentum supplies an accelerated optimizer for RHTM, whose finite-neighborhood gradients permit online implementation with a finite lookahead window. The proof links RHTM iterates to triple momentum and uses that equivalence to bound regret.

B Triple momentum and a proof of Theorem 1

B.1 Proof of Theorem 1

  • RHTM’s iterate after K steps matches the triple-momentum iterate, allowing the regret bound to follow from the optimization result; RHGD is proved similarly.The proof uses the equivalence between the optimization problem and optimal control.Source: §B.1 · p. 15

C Proof of Lemma 1

The proof transforms the control costs into functions of the decision vector z, then establishes strong convexity and smoothness of the resulting objective. The following regret proof uses an intermediate steady-state cost to combine two bounds.

C Proof of Lemma 1

  • Because states and controls are linear in z, composing their convex stage costs with these maps preserves convexity.Source: C Proof of Lemma 1 · p. 15
  • The transformed objective C(z) is strongly convex with parameter at least μ_f.The argument combines strongly convex state costs with convex control costs.Source: C Proof of Lemma 1 · pp. 15–16
  • The proof establishes smoothness of C(z) by bounding the transformed state-cost and control-cost terms separately, then summing their inequalities.The resulting smoothness bound depends on the stage-cost smoothness constants and the system matrix.Source: C Proof of Lemma 1 · p. 16

D Proof of Theorem 2

  • The regret proof bounds online cost and offline-optimal cost relative to the sum of optimal steady-state costs, then combines those bounds.Source: D Proof of Theorem 2 · p. 16

D.1 Proof of Lemma 2.

This section presents appendix proofs of control lemmas using uniform state bounds and Bellman recursions, and their application to regret bounds for general and fixed-cost linear quadratic tracking. The excerpt concludes a proof by deriving a norm expression, combining bounds, and summing them across Parts I, II, and III.

D.1 Proof of Lemma 2.

  • The proof of Lemma 2’s first inequality establishes a bound with c1 independent of N and W; it relies on canonical-form expressions for the steady state and FOSS-initialized state.Source: §D.1 · pp. 17, 19

D.2 Proof of Lemma 3.

  • The proof of Lemma 3 uses Bellman equations and dynamic programming to derive recursive relations and inequalities for the cost-to-go functions.It introduces a Bellman operator and sums the recursive inequality along the optimal trajectory.Source: §D.2 · p. 19

D.3 Proof of Lemma 4

  • Lemma 4’s proof bounds optimal steady states by constructing a suboptimal steady state and using cost-function convexity and smoothness.The resulting uniform state bound is independent of N and W.Source: §D.3 · p. 20

E Linear quadratic tracking

  • The LQT section treats general time-varying cost matrices and then considers the fixed-matrix case as a special case.It introduces a regret bound for general LQT before proving the corollary for unchanged Q_t and R_t.Source: E Linear quadratic tracking · p. 20

E.1 Regret bound on the general online LQT problems

  • For general LQT, Corollary 2 states a regret bound for RHTM with FOSS initialization under bounded stage-cost matrices and a terminal-cost condition.The terminal-cost condition is noted as being imposed for technical simplicity and removable; the supplied passage does not show the bound’s formula.Source: §E.1 · p. 21

E.2 Proof of Corollary 1

  • For fixed Q and R, the Corollary 1 proof avoids extra constants from the general bounds by exploiting that β_t−1 is zero and using intermediate results.The proof also represents the optimal steady state as a matrix transformation of θ_t.Source: §E.2 · pp. 22–23

D.1 Proof of Lemma 2.

  • By (20), the expression equals ∥F2∥2 times the sum of the indicated differences among θ terms.Taking square roots on both sides yields the next bound.Source: §E.2 · p. 24
  • The bounds established above are combined to obtain the next inequality.Source: §E.2 · p. 24
  • The proof concludes by summing the bounds for Parts I, II, and III.Source: §E.2 · p. 24

F Proof of Theorem 3

The proof constructs a linear-quadratic tracking instance to lower-bound regret for online algorithms with finite predictions. It relates missed target changes beyond the prediction window to decision error, and develops supporting matrix and finite-horizon LQT results.

F Proof of Theorem 3

  • The inverse Hessian Y has row entries that decay from the diagonal, a property used in the lower-bound argument.The proof identifies C(z)’s condition number as ζ for the constructed problem.Source: F Proof of Theorem 3 · pp. 24, 26
  • When a tracking target changes beyond the W-step prediction window, the online algorithm cannot prepare for that change, producing positive regret.Source: F Proof of Theorem 3 · p. 27

F.2 Proof of Lemma 12

  • For times when a target changes at the edge of the prediction window, the online decision differs from the offline optimum by a lower-bounded amount.Source: F Proof of Theorem 3 · p. 27

F Proof of Theorem 3

  • The constructed instance yields a worst-case regret lower bound of Ω(ρ^2 K L_N) for online algorithms.The proof first lower-bounds expected regret under random tracking targets, then concludes that some realization attains the bound.Source: F Proof of Theorem 3 · pp. 24, 28

G.1 Preliminaries: dynamic programming for finite-horizon LQT

  • Finite-horizon LQT dynamic programming expresses the cost-to-go parameters through recursions for P_t, M_t, β_t, and H_t.Source: §G.1 · p. 30

G.2 Proof of Lemma 9

  • The finite-horizon Riccati parameters P_t remain in the bounded matrix set P across horizons and stages under the stated cost-matrix conditions.This boundedness supports the proof that the corresponding infinite-horizon solution lies in P.Source: §G.2 · pp. 31–32

G.3 Proof of Lemma 6

The appendix verifies the average-cost LQ tracking formulas by establishing limits of the finite-horizon recursions and checking the Bellman equations and controller. It also supplies stability and simulation details for the subsequent lemmas and experiments.

G.3 Proof of Lemma 6

  • Under controllability and positive-definite Q and R, Proposition 1 states that the optimal average cost is independent of the initial state.The proof establishes the formula by verifying its limiting finite-horizon cost, the Bellman bias function, and the proposed optimal controller.Source: §G.3 · pp. 32–33

G.4 Proof of Lemma 7.

  • The closed-loop state-transition system is exponentially stable for the stated finite-horizon matrix conditions.The proof uses a Lyapunov function; the result applies for any horizon and the specified Q_t, R_t, terminal Q_N, and initial state.Source: §G.4 · p. 35

G.5 Proof of Lemma 8

  • For fixed Q and R, convergence of β_k to β_e is used to obtain a bound on the limiting β_e.The passage gives the convergence condition but its displayed bound is incomplete.Source: §G.5 · p. 37

H.1 LQT

  • The LQT experiment uses N = 30, diagonal Q_t and R_t entries drawn i.i.d. from Unif[1, 2], and θ_t drawn i.i.d. from Unif[−10, 10].The RHGD and RHTM stepsizes follow Theorem 1 conditions.Source: §H.1 · p. 37

H.2 Robotics tracking

  • The robotics tracking simulation uses a discrete-time kinematic model, with 0.025-second online decisions and 0.001-second motion simulation steps.The passage also specifies that the reference trajectory is used in the simulation.Source: §H.2 · p. 37

Related papers

Loading 1906.11378v3…