text:
\begin{document}
\maketitle

\begin{abstract}
  We study the impact of predictions in online Linear Quadratic Regulator control with both stochastic and adversarial disturbances in the dynamics. In both settings, we characterize the optimal policy and derive tight bounds on the minimum cost and dynamic regret. Perhaps surprisingly, our analysis shows that the conventional greedy MPC approach is a near-optimal policy in both stochastic and adversarial settings. Specifically, for length-$T$ problems, MPC requires only $O(\log T)$ predictions to reach $O(1)$ dynamic regret, which matches (up to lower-order terms) our lower bound on the required prediction horizon for constant regret.
\end{abstract}

\section{Introduction}

This paper studies the effect of using predictions for online control in a linear dynamical system governed by $x_{t+1} = Ax_t + Bu_t + w_t$, where $x_t$, $u_t$, and $w_t$ are the state, control, and disturbance (or exogenous input) respectively. At each time step $t$, the controller incurs a quadratic cost $c(x_t,u_t)$. Recently, considerable effort has been made to leverage and integrate ideas from learning, optimization and control theory to study the design of optimal controllers under various performance criteria, such as static regret \cite{dean2018regret,agarwal2019online,agarwal2019logarithmic,cohen2019learning,hazan2019nonstochastic,foster2020logarithmic,simchowitz2020naive}, dynamic regret \cite{li2019online,goel2020power} and competitive ratio \cite{shi2020beyond,goel2019online}. However, the study of online convergence when incorporating predictions has been largely absent.

Indeed, a key aspect of online control is considering the amount of available information when making decisions.  Most recent studies focus on the basic setting where only past information, $x_0,w_0,\cdots,w_{t-1}$, is available for $u_t$ at every time step \cite{dean2018regret,agarwal2019online,foster2020logarithmic,shi2020beyond}. However, this basic setting does not effectively characterize situations where we have accurate predictions, e.g., when  $x_0,w_0,\cdots,w_{t-1+k}$ are available at step $t$. These types of accurate predictions are often available in many applications, including robotics \cite{baca2018model,shi2019neural}, energy systems \cite{vazquez2016model}, and data center management \cite{lazic2018data}. Moreover, there are many practical algorithms that leverage predictions, such as the popular Model Predictive Control (MPC)~\cite{baca2018model,camacho2013model,angeli2016theoretical,angeli2011average,grune2018economic,grune2014asymptotic}.

While there has been increased interest in studying online guarantees for control with predictions, to our knowledge, there has been no such study for the case of a finite-time horizon with disturbances.

Several previous works studied the economic MPC problem by analyzing the asymptotic performance without disturbances~\cite{angeli2016theoretical,angeli2011average,grune2018economic,grune2014asymptotic}.
\citet{rosolia2019sample,rosolia2017learning} studied learning for MPC but focused on the episodic setting with asymptotic convergence guarantees.
\citet{li2019online} considered a linear system where finite predictions of costs are available, and analyzed the dynamic regret of their new algorithm; however, they neither consider disturbances nor study the more practically relevant MPC approach. \citet{goel2020power} characterized the offline optimal policy (i.e., with infinite predictions) and cost in LQR control with i.i.d.\ zero-mean stochastic disturbances,
but those results do not apply to limited predictions or non-i.i.d.\ disturbances. Other prior works analyze the power of predictions in online optimization~\cite{lin2019online,chen2015online}, but the connection to online control in dynamical systems is unclear.

From this literature, fundamental questions about online control with predictions have emerged:
\begin{enumerate}
  \item \textit{What are the cost-optimal and regret-minimizing policies when given $k$ predictions? What are the corresponding cost and regret of these policies?}
  \item \textit{What is the marginal benefit from each additional prediction used by the policy, and how many predictions are needed to achieve (near-)optimal performance?}

  \item \textit{How well does MPC with $k$ predictions perform compared to cost-optimal and regret-minimizing policies?

  }
\end{enumerate}

\paragraph{Main contributions.} We systematically address each of the questions above in the context of LQR systems with general stochastic and adversarial disturbances in the dynamics. In the stochastic case, we explicitly derive the cost-optimal and dynamic regret minimizing policies with $k$ predictions. In both the stochastic and adversarial cases, we derive (mostly tight) upper bounds for the optimal cost and minimum dynamic regret given access to $k$ predictions. We also show that the marginal benefit of an extra prediction exponentially decays as $k$ increases. Additionally, for MPC specifically, we show that it has a bounded performance ratio against the cost-optimal policy in both stochastic and adversarial settings. We further show that MPC is near-optimal in terms of dynamic regret, and needs only $O(\log T)$ predictions to achieve $O(1)$ dynamic regret (the same order as is needed by the dynamic regret minimizing policy) in both settings.

We would like to emphasize the generality of the results. The model we consider is the general LQR setting with disturbance in the dynamics, where only the stabilizability of $[A,B]$ and $[A^\top,Q]$ is assumed \cite{anderson2007optimal}. Further, in the stochastic setting we consider general distributions, which are not necessarily i.i.d.\ or zero-mean. Additionally, our results compare to the \emph{globally} optimal policies for cost and regret rather than compare to the optimal linear or static policy. Finally, our upper bounds are (almost) \textit{tight}, i.e., there exist some systems such that the bounds are (nearly) reached, up to lower-order terms.

It is perhaps surprising that classic MPC, which is a simple greedy policy (up to the prediction horizon), is near-optimal even with adversarial disturbances in the dynamics. Our results thus highlight the power of predictions to reduce the need for algorithmic sophistication.
In that sense, our results somewhat mirror recent developments in the study of exploration strategies in online LQR control with unknown dynamics $\{A,B\}$: after a decade's research beginning with the work of \citet{abbasi2011regret}, \citet{simchowitz2020naive} recently show that naive exploration is optimal.
Taken together with the result from \cite{simchowitz2020naive}, our paper provides additional evidence for the idea that the structure of LQR allows simple algorithmic ideas to be effective, which sheds light on key algorithmic principles and fundamental limits in continuous control.

\section{Background and model} \label{sec:model}
We consider the \emph{Linear Quadratic Regulator (LQR)} optimal control problem with disturbances in the dynamics. In particular, we consider a linear system initialized with $x_0 \in \bR^n$ and controlled by $u_t\in \bR^d$, with dynamics
\[x_{t+1} = A x_t + B u_t + w_t \quad \text{ and cost } \quad J = \sum_{t=0}^{T-1} (x_t^\top Q x_t + u_t^\top R u_t) + x_T^\top \Qf x_T,\]
where $T \ge 1$ is the total length of the control period. The goal of the controller is to minimize the cost given $A, B, Q, R, \Qf, x_0$, and the characterization of the disturbance $w_t$. Throughout this paper, we use $\rho(\cdot)$ to denote the spectral radius of a matrix and $\norm{\cdot}$ to denote the 2-norm of a vector or the spectral norm of a matrix.

We assume $Q,\Qf\succeq0,R\succ0$ and the pair $(A,B)$ is \emph{stabilizable}, i.e., there exists a matrix $K_0 \in \bR^{d \times n}$ such that $\rho(A - B K_0) < 1$. Further, we assume the pair $(A,Q)$ is \emph{detectable}, i.e., $(A^\top,Q)$ is stabilizable, to guarantee stability of the closed-loop. Note that detectability of $(A,Q)$ is more general than $Q\succ0$, i.e., $Q\succ0$ implies $(A,Q)$ is detectable. For $w_t$, in the stochastic case, we assume $\{w_t\}_{t=0,1,\cdots}$ are sampled from a joint distribution with bounded cross-correlation, i.e., $\bE{w_t^\top w_{t'}} \le m$ for any $t,t'$; in the adversarial case, we assume $w_t$ is picked from a bounded set $\Omega$.

These are standard assumptions in the literature, e.g., \cite{dean2018regret,foster2020logarithmic,simchowitz2020naive} and it is worth noting that our notion of stochasticity is much more general than typically considered \cite{dean2018regret,cohen2019learning,cassel2020logarithmic}. We also note that many important problems can be straightforwardly converted to our model --- for example, input-disturbed systems and the Linear Quadratic (LQ) tracking problem \cite{anderson2007optimal}.

\textbf{Example: linear quadratic tracking.}

The standard quadratic tracking problem is defined with dynamics $x_{t+1}=Ax_t+Bu_t+\tilde{w}_t$ and cost function
$J=\sum_{t=0}^{T-1} (x_{t+1}-d_{t+1})^\top Q (x_{t+1}-d_{t+1}) + u_t^\top R u_t$,
where $\{d_t\}_{t=1}^T$ is the desired trajectory to track. To map this to our model, let $\Tilde{x}_t=x_t-d_t$. Then, we get
$J=\sum_{t=0}^{T-1} \Tilde{x}_{t+1}^\top Q \Tilde{x}_{t+1} + u_t^\top R u_t$
and $\Tilde{x}_{t+1} = A \Tilde{x}_t + B u_t + w_t$,
which is an LQR control problem with disturbance $w_t = \tilde{w}_t + Ad_t - d_{t+1}$ in the dynamics.

\subsection{Predictions}

In the classic model, at each step $t$, the controller decides $u_t$ after observing $w_{t-1}$ and $x_t$. In other words, $u_t$ is a function of all the previous information: $x_0, x_1, \dots, x_{t-1}$ and $w_0, w_1, \dots, w_{t-1}$, or equivalently, of $x_0, w_0, w_1, \cdots, w_{t-1}$. We describe this scenario via the following \emph{event sequence}:
\begin{equation*} \label{eq:event_seq_0}
  \begin{matrix}
  x_0 & u_0 & w_0 & u_1 & w_1 & \cdots & u_{T-1} & w_{T-1}
  \end{matrix},
\end{equation*}
where each $u_t$ denotes the decision of a control policy, each $w_t$ denote the observation of a disturbance, and each decision may depend on previous events.

However, in many real-world applications the controller may have some knowledge about future. In particular, at time step $t$, the controller may have \emph{predictions} of immediate $k$ future disturbances and make decision $u_t$ based on $x_0, w_0, \dots, w_{t+k-1}$. In this case, the event sequence is given by:
\[\begin{matrix}
x_0 & w_0 & w_1 & \cdots & w_{k-1} & u_0 & w_k & u_1 & w_{k+1} & \cdots & u_{T-k-1} & w_{T-1} & u_{T-k} & \cdots & u_{T-1}.
\end{matrix}\]
The existence of predictions is common in many applications such as disturbance estimation in robotics \cite{shi2019neural} and model predictive control (MPC) \cite{camacho2013model}, which is a common approach for the LQ tracking problem.  When given $k$ predictions of $d_t$, the LQ tracking problem can be formulated as a LQR problem with $k-1$ predictions of future disturbances. In this paper we assume all the predictions are \textit{exact}, and leave inexact predictions \cite{shi2020beyond,chen2015online} as future work.  This is common in the literature on online algorithms with predictions, e.g., \cite{li2019online,lin2019online}.

\subsection{Disturbances}

The characteristics of the disturbances have a fundamental impact on the optimal control policy and cost. We consider two types of disturbance: stochastic disturbances, which are drawn from a joint distribution (not necessarily i.i.d.), and adversarial disturbances, which are chosen by an adversary to maximize the overall control cost of the policy.

In the stochastic setting, we model the disturbance sequence $\{w_t\}_{t = 0}^{T-1}$ as a discrete-time stochastic process with joint distribution $\cW$ which is known to the controller. Let $W_t = W_t(w_0, \dots, w_{t-1})$ be the conditional distribution of $w_t$ given $w_0, \dots, w_{t-1}$.

Then the cost of the optimal online policy with $k$ predictions is given by:
\[\sto^T_k = \bEE[w_0 \sim W_0, \dots, w_{k-1} \sim W_{k-1}] \Big( \min_{u_0} \Big( \bEE[w_k \sim W_k] \Big( \cdots \min_{u_{T-k-1}} \Big( \bEE[w_{T-1} \sim W_{T-1}] \Big( \min_{u_{T-k}, \dots, u_{T-1}} J \Big) \Big) \Big) \Big) \Big).\]

Note that the cost $J=J(x_0,u_0,\cdots,u_{T-1},w_0,\cdots,w_{T-1})$. Two extreme cases are noteworthy: $k=0$ reduces to the classic case without prediction and $k=T$ reduces to the offline optimal.

In the adversarial setting, each disturbance $w_t$ is selected by an adversary from a bounded set $\Omega \subseteq \bR^n$ in order to maximize the cost. The controller has no information about the disturbance except that it is in $\Omega$. Similar to the stochastic setting, we define:
\begin{gather*}
  \adv^T_k = \sup_{w_0, \dots, w_{k-1} \in \Omega} \Big( \min_{u_0} \Big( \sup_{w_k \in \Omega} \Big( \cdots \min_{u_{T-k-1}} \Big( \sup_{w_{T-1} \in \Omega} \Big( \min_{u_{T-k}, \dots, u_{T-1}} J \Big) \Big) \Big) \Big) \Big).
\end{gather*}
This can be viewed as online $\mathcal{H}_\infty$ control \cite{zhou1998essentials} with predictions.

The average cost in an infinite horizon is particularly important in both control and learning communities to understand asymptotic behaviors. We use separate notation for it:
\[\STO_k = \lim_{T \to \infty} \frac{1}{T} \sto^T_k, \quad \ADV_k = \lim_{T \to \infty} \frac{1}{T} \adv^T_k.\]

We emphasize that we do not have any constraints (like linearity) on the policy space, and both $\sto_k^T$ and $\adv_k^T$ are globally optimal with the corresponding type of disturbance. This point is important in light of recent results that show that linear policies cannot make use of predictions at all \cite{goel2020power,shi2020beyond}, i.e., the cost of the best linear policy with infinite predictions ($k=\infty$) is asymptotically equal to that with no predictions ($k=0$) in the setting with i.i.d.\ zero-mean stochastic disturbances. In this paper, we explicitly derive the optimal policy for every $k > 0$, which is \emph{nonlinear} in general.

\subsection{Model predictive control}

Model predictive control (MPC) is perhaps the most common control policy for situations where predictions are available. MPC is a greedy algorithm with a receding horizon based on all available current predictions. \Cref{alg:mpc} provides a formal definition, and we additionally refer the reader to the book \cite{camacho2013model} for a literature review on MPC.  We adopt a conventional definition of MPC as an online optimal control problem with a finite-time horizon with dynamics constraints. Note that other prior work on MPC sometimes considers other input and state constraints \cite{camacho2013model}.

MPC is a practical algorithm in many scenarios like robotics \cite{baca2018model}, energy system \cite{vazquez2016model} and data center cooling \cite{lazic2018data}. The existing theoretical studies of MPC focus on asymptotic stability and performance \cite{angeli2016theoretical,angeli2011average,grune2018economic,grune2014asymptotic,rosolia2017learning}. To our knowledge, we provide the first general, dynamic regret guarantee for MPC in this paper.

\begin{algorithm}[t]
  \caption{Model predictive control with $k$ predictions}
  \label{alg:mpc}
  \DontPrintSemicolon
  \SetKwInput{KwPara}{Parameter}

  \KwPara{$\{A,B,Q,R\}$ and $\tilde \Qf \in \bR^{n \times n}$ }
  \KwIn{$x_0, w_0, \dots, w_{k-1}$}
  \For{$t = 0$ \KwTo $T - 1$}{
    \KwIn{$x_t, w_{t+k-1}$ \tcp*{The controller now knows $x_0, \dots, x_t, w_0, \dots, w_{t+k-1}$}}
    $(u_t, \dots, u_{t+k-1}) = \arg\min_u \sum_{i=t}^{t+k-1} (x_i^\top Q x_i + u_i^\top R u_i) + x_{t+k}^\top \tilde \Qf x_{t+k}$ subject to $x_{i+1} = A x_i + B u_i + w_i$ for $i = t, \dots, t + k - 1$ \label{line:mpc}\;
    \KwOut{$u_t$}
  }
\end{algorithm}

In this paper, we study the performance of MPC in three different cases, where disturbances are i.i.d. zero-mean stochastic, generally stochastic, and adversarial, corresponding to \Cref{sec:iid,sec:general_sto,sec:adv} respectively.  We define the performance of MPC in the stochastic and adversarial settings as follows:
\begin{align*}
  \mpcs_k^T & = \bEE[w_0, \dots, w_{T-1}] J^{\MPC_k}, \qquad \MPCS_k = \lim_{T \to \infty} \frac{1}{T} \mpcs_k^T, \\
  \mpca_k^T & = \sup_{w_0, \dots, w_{T-1}} J^{\MPC_k}, \qquad \MPCA_k = \lim_{T \to \infty} \frac{1}{T} \mpca_k^T,
\end{align*}
where
$J^{\MPC_k}$ is the cost of MPC given a specific disturbance sequence, i.e., $J^{\MPC_k}(w) = J(u, w)$ where for each $t$, $u_t = \phi(x_t, w_t, \dots, w_{t+k-1})$ and $\phi(\cdot)$ is the function that maps $x_t, w_t, \dots, w_{t+k-1}$ to the policy $u_t$, as defined in \Cref{alg:mpc}.
By definition, $\MPCS_k \ge \STO_k$ and $\MPCA_k \ge \ADV_k$ for every $k \ge 1$ since they use the same information but the latter ones are defined to be optimal.

\subsection{Dynamic regret and the performance ratio} \label{sec:regret_PR}

In this paper, we focus on two performance metrics,
the \emph{dynamic regret} and the \emph{performance ratio}.

\textbf{Dynamic regret.} Regret is a standard metric in online learning and provides a bound on the cost difference between an online algorithm and the optimal static policy given complete information. We focus on the \emph{dynamic} regret, which compares to the optimal dynamic offline policy, rather than the optimal static offline policy.  Note that the optimal offline policy may be nonlinear. It is important to consider nonlinear policies because recent results highlight that the optimal offline policy can have cost that is arbitrarily lower than the optimal linear policy in hindsight \cite{goel2020power,shi2020beyond}.

More specifically, we compare the cost of an online algorithm with $k$ predictions to that of the offline optimal (nonlinear) algorithm, i.e., one that has predictions of all disturbances. For MPC with $k$ predictions,
we define its dynamic regret in the stochastic and adversarial settings, respectively, as:
\begin{align*}
  Reg^S(\MPC_k) & = \bEE[(w_0, \cdots, w_{T-1}) \sim \cW] \Big(J^{\MPC_k}(w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big), \\
  Reg^A(\MPC_k) & = \sup_{w_0, \cdots, w_{T-1} \in \Omega} \Big(J^{\MPC_k}(w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big).
\end{align*}

As compared to (static) regret, dynamic regret does not have any restriction on the policies $u'_0, \dots, u'_{T-1}$ used for comparison and thus differs from other notions of regret where $u'_0, \dots, u'_{T-1}$ are limited in special cases. For example, in the classic form of regret, $u'_0 = \dots = u'_{T-1}$; and in the regret compared to the best offline linear controller \cite{agarwal2019online,cohen2019learning}, $u'_t = -K^* x_t$.

In this work, we obtain both upper bounds and lower bounds on dynamic regret. For lower bounds, we define the minimum possible regret that an algorithm with $k$ predictions can achieve (i.e., the regret of the algorithm that minimizes the regret):
\begin{align*}
  {Reg^S_k}^* & = \bEE[w_0, \cdots, w_{k-1}] \min_{u_0} \bEE[w_k] \cdots \min_{u_{T-k-1}} \bEE[w_{T-1}] \min_{u_{T-k}, \cdots, u_{T-1}} \Big(J(u, w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big), \\
  {Reg^A_k}^* & = \sup_{w_0, \cdots, w_{k-1}} \min_{u_0} \sup_{w_k} \cdots \min_{u_{T-k-1}} \sup_{w_{T-1}} \min_{u_{T-k}, \cdots, u_{T-1}} \Big(J(u, w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big).
\end{align*}

Finally, we end our discussion of dynamic regret with a note highlighting an important contrast between stochastic and adversarial settings.  In the stochastic setting,
\begin{align*}
  {Reg^S_k}^*

  & = \bEE[w_0, \cdots, w_{k-1}] \min_{u_0} \bEE[w_k] \cdots \min_{u_{T-k-1}} \bEE[w_{T-1}] \Big(\min_{u_{T-k}, \cdots, u_{T-1}} J(u, w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big) \\

  & = \bEE[w_0, \cdots, w_{k-1}] \min_{u_0} \bEE[w_k] \cdots \min_{u_{T-k-1}} \bEE[w_{T-1}] \min_{u_{T-k}, \cdots, u_{T-1}} J(u, w) - \bEE[w_0, \dots, w_{T-1}] \min_{u'_0, \dots, u'_{T-1}} J(u', w) \\
  & = \sto_k^T - \sto_T^T.
\end{align*}
This equality still holds if we take $\arg\min$ instead of $\min$ and thus the regret-optimal policy is the same as the cost-optimal policy. However, in the adversarial case, a similar reasoning gives an inequality: ${Reg^A_k}^* \ge \adv_k^T - \adv_T^T$, and correspondingly, the regret-optimal and cost-optimal policies can be different. Similarly, for MPC, we have $Reg^S(\MPC_k) = \mpcs_k^T - \sto_T^T$ while $Reg^A(\MPC_k) \ge \mpca_k^T - \adv_T^T$.

\textbf{Performance ratio.}
The second metric we study is a new metric that we term the \emph{performance ratio}.  It characterizes the ratio of the cost of an online algorithm with $k$ predictions to the cost of the optimal online algorithm using $k$ predictions.  Thus, it gives a way of comparing to a weaker benchmark than regret -- one that has the same amount of information as the algorithm. Note that it is related to, but different than, the competitive ratio in this context.
Formally, the performance ratio of the MPC algorithm in stochastic and adversarial settings, respectively, is defined as:
\[\PR^S(\MPC_k) = \frac{\MPCS_k}{\STO_k}, \quad
  \PR^A(\MPC_k) = \frac{\MPCA_k}{\ADV_k}.\]

While the dynamic regret indicates whether the algorithm can match the optimal offline policy (which has complete information), the performance ratio measures whether the algorithm is using the information available to it in as efficient a manner as possible.  Thus, the contrast between the two separates the efficiency of the algorithm from the inefficiency created by the lack of information about future disturbances.

Finally, one may wonder if there are connections between dynamic regret and performance ratio. As might be expected, in both the stochastic and adversarial settings, the performance ratio of an online policy with $k$ predictions provides a lower bound of its dynamic regret:
\begin{gather*}
  \PR^S(\MPC_k) - 1
  \le \frac{\MPCS_k}{\STO_\infty} - 1
  = \frac{\MPCS_k - \STO_\infty}{\STO_\infty}
  = \frac{1}{\STO_\infty} \lim_{T \to \infty} \frac{1}{T} Reg^S(\MPC_k), \\
  \PR^A(\MPC_k) - 1
  \le \frac{\MPCA_k}{\ADV_\infty} - 1
  = \frac{\MPCA_k - \ADV_\infty}{\ADV_\infty}
  \le \frac{1}{\ADV_\infty} \lim_{T \to \infty} \frac{1}{T} Reg^A(\MPC_k).
\end{gather*}

\iffalse
\paragraph{Relation to the competitive ratio.} Another commonly used metric for online algorithm is the competitive ratio. In the adversarial setting, the performance ratio is smaller than the competitive ratio because
\[\mathit{PR}
  = \frac{\sup_w J^{\MPC_k}}{\sup_w \min_u J}
  \le \sup_w \frac{J^{\MPC_k}}{\min_u J}
  = \mathit{CR}.\]
In the stochastic setting, there is no single-sided relationship between the two concepts in general. The analysis of competitive ratio is more challenging and will not be the focus of this work.
\fi

\section{Zero-mean i.i.d.\ disturbances}
\label{sec:iid}

We begin our analysis with the simplest of the three settings we consider: the disturbances $w_t$ are independent and identically distributed with zero mean. Though i.i.d.\ zero-mean is a limited setting, it is still complex enough to study predictions and the first results characterizing the optimal policy with predictions appeared only recently \cite{goel2020power,foster2020logarithmic}, focusing only on the optimal policy when $k\to\infty$.

Before delving into our results, we first recap the classic \emph{Infinite Horizon Linear Quadratic Stochastic Regulator} \cite{anderson2007optimal,anderson2012optimal}, i.e., the case when $k=0$:

\begin{prop}[\citet{anderson2012optimal}] \label{thm:iid_classical}
  Let $w_t$ be i.i.d.\ with zero mean and covariance matrix $W$. Then, the optimal control policy corresponding to $\STO_0$ is given by:
  \[u_t = -(R + B^\top P B)^{-1} B^\top P A x_t \eqqcolon -K x_t,\]
  where $P$ is the solution of discrete-time algebraic Riccati equation (DARE)
  \begin{equation} \label{eq:DARE}
    P = Q + A^\top P A - A^\top P B(R + B^\top P B)^{-1} B^\top PA.
  \end{equation}
  The corresponding closed-loop dynamics $A-BK$ is exponentially stable, i.e., $\rho(A-BK)<1$. Further, the optimal cost is given by $\STO_0=\Tr{PW}$.
\end{prop}
This result has been extensively studied in optimal control theory \cite{kirk2004optimal,anderson2007optimal} as well as in reinforcement learning \cite{fazel2018global,dean2018regret,simchowitz2020naive}. We want to emphasize two important properties of the optimal policy $u_t=-Kx_t$. First, the policy is \emph{linear} in the state $x_t$. In contrast, we show later that the optimal policy when $k\neq0$ is, in general, \emph{nonlinear}. Second, under the assumptions of our model, this policy is \emph{exponentially stable}, i.e., $\rho(A-BK)<1$.
We leverage this to show the power of predictions later in the paper.

\paragraph{Optimal policy.} Let $F=A-BK$ and $\lambda = \frac{1+\rho(F)}{2} < 1$. From Gelfand's formula, there exists a constant $c(n)$ such that $\|F^k\|\leq c(n)\lambda^k$ for all $k\geq1$.
\begin{theorem} \label{thm:iid_pred}
  Let $w_t$ be i.i.d.\ with zero mean and covariance matrix $W$. Suppose the controller has $k \ge 1$ predictions. Then, the optimal control policy at each step $t$ is given by:
  \begin{equation} \label{eq:iid_policy}
    u_t = -(R + B^\top P B)^{-1} B^\top \left(P A x_t + \sum_{i=0}^{k-1} (A^\top - A^\top P H)^i P w_{t+i}\right),
  \end{equation}
  where $P$ is the solution of DARE in \Cref{eq:DARE}. The cost under this policy is:
  \begin{equation} \label{eq:iid_pred_cost}
    \STO_k = \Tr{\left(P - \sum_{i=0}^{k-1} P (A - HPA)^i H (A^\top - A^\top PH)^i P\right) W},
  \end{equation}
   where $H = B (R + B^\top P B)^{-1} B^\top$.
\end{theorem}
Following the approach developed in \cite{goel2020power,foster2020logarithmic}, the proof is based on an analysis of quadratic cost-to-go functions in the form $V_t(x_t) = x_t^\top P_t x_t + v_t^\top x_t + q_t$. Note that $A - HPA = A - B (R + B^\top P B)^{-1} B^\top P A = A - B K = F$. Thus, the online optimal cost $\STO_k$ with $k$ predictions approaches the offline optimal cost $\STO_\infty$ by an exponential rate. In other words, $\STO_k / \STO_\infty = 1 + O(\|F^k\|^2) = 1 + O(\lambda^{2k})$.
Two extreme cases of our result are noteworthy. When $k = 0$, it reduces to the classic \Cref{thm:iid_classical}. When $k \to \infty$, it reduces to the offline optimal case derived by \citet{goel2020power}.

\paragraph{Model predictive control.}
As might be expected, since the disturbances are i.i.d., future disturbances have no dependence on the current. As a result, MPC gives the \emph{optimal} policy.
\begin{theorem} \label{thm:mpc_policy}
  In \Cref{alg:mpc}, let $\tilde\Qf = P$. Then, the MPC policy with $k$ predictions is also given by \Cref{eq:iid_policy}. Assuming i.i.d.\ disturbance with zero mean, the MPC policy is optimal.
\end{theorem}

Due to the greedy nature, MPC does not utilize any properties of the disturbance, so the first part in \Cref{thm:mpc_policy} holds not only for i.i.d.\ disturbance, but also other types of disturbance considered in the later sections, i.e., MPC policy with $k$ predictions is always given by \Cref{eq:iid_policy}.

\section{General stochastic disturbances} \label{sec:general_sto}

In this section, we consider a general form of stochastic disturbance, more general than typically considered in this context \cite{dean2018regret,cohen2019learning,cassel2020logarithmic}. Suppose the disturbance sequence $\{w_t\}_{t = 0, 1, 2, \dots}$ is sampled from a joint distribution $\cW$ such that the trace of the cross-correlation of each pair is uniformly bounded,

i.e., there exist $m > 0$ such that for all $t, t' \ge 1$, $\bE{w_t^\top w_{t'}} \le m$.

\paragraph{Optimal policy.}
In the case of general stochastic disturbances, we cannot obtain as clean a form for $\STO_k$ as in the i.i.d.\ case in \Cref{sec:iid}. However, the marginal benefit of having an extra prediction decays with the same (exponential) rate and
the optimal policy is similar to that in \Cref{sec:iid}, but with some additional terms that characterize the expected future disturbances given the current information.

\begin{theorem} \label{thm:sto_pred_diff}
  The optimal control policy with general stochastic disturbance is given by:
  \begin{equation} \label{eq:sto_policy}
    u_t = -(R + B^\top P B)^{-1} B^\top \Bigg(P A x_t + \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i} + \sum_{i=k}^\infty {F^\top}^i P \mu_{t+i|t+k-1}\Bigg),
  \end{equation}
  where $\mu_{t'|t} = \bE{w_{t'} \given w_0, \dots, w_t}$.
  Under this policy, the marginal benefit of obtaining an extra prediction decays exponentially fast in the existing number $k$ of predictions. Formally, for $k \ge 1$,
  \[\STO_k - \STO_{k+1} = O(\|F^k\|^2) = O(\lambda^{2k}).\footnote{We say that $f(k) = O(g(k))$ if $\exists C > 0$, $\forall k \ge 1$, $|f(k)| \le C \, g(k)$; $\Omega()$ is similar except that the last ``$\le$'' is replaced by ``$\ge$''; $\Theta()$ means both $O()$ and $\Omega()$. This is stronger than the \href{https://en.wikipedia.org/wiki/Big_O_notation}{\underline{standard definition}} where $f(k) = O(g(k))$ if $\exists C > 0, k^* > 0$, $\forall k \ge k^*$, $|f(k)| \le C \, g(k)$.}\]
\end{theorem}

This proof leverages a novel difference analysis of cost-to-go functions. Note that for some distributions, $\STO_k$ may approach $\STO_\infty$ much faster than exponential rate. It is even possible that $\STO_k = \STO_\infty$ for finite $k$, as we show in \Cref{ex:sto_finite_pred} below.
On the other hand, there are scenarios where $\STO_k$ approaches $\STO_\infty$ in an exactly exponential manner, as we show in \Cref{ex:exp_speed} below.
\begin{example} \label{ex:sto_finite_pred}

  Define the joint distribution $\cW$ such that with probability $\nicefrac{1}{2}$, all $w_t = w$, and otherwise all $w_t = -w$. In this case, one prediction is equivalent to infinite predictions since it is enough to distinguish these two scenarios with only $w_0$. As a result, $\STO_1 = \STO_\infty$.
\end{example}
\begin{example} \label{ex:exp_speed}
  Suppose the system is 1-d ($n = d = 1$) and the disturbance is i.i.d.\ with zero mean, i.e., the setting of \Cref{sec:iid}. Then, according to \Cref{eq:iid_pred_cost}, as long as $F, P, H, W$ are non-zero,
  \[\STO_k - \STO_\infty = \sum_{i=k}^\infty F^{2i} P^2 H W = \Theta(F^{2k}).\]
\end{example}

\paragraph{Model predictive control.}
The comparison between the MPC policy in \Cref{eq:iid_policy} and the optimal policy in \Cref{eq:sto_policy} reveals that MPC is a \emph{truncation} of the optimal policy and is no longer optimal because MPC is a greedy policy without considering future dependence on current information. Nevertheless, it is still a near-optimal policy, as characterized by the following results.

\begin{theorem} \label{thm:mpcs_diff}
  $\MPCS_k - \MPCS_{k+1} = O(\|F^k\|^2) = O(\lambda^{2k})$. Moreover, in Example \ref{ex:exp_speed}, $\MPCS_k - \MPCS_{k+1} = \Theta(\|F^k\|^2)$.
\end{theorem}
In other words, the marginal benefit for the MPC algorithm of an extra prediction decays exponentially fast, paralleling the result for optimal policy in \Cref{eq:sto_policy}.
\Cref{thm:mpcs_diff} implies that MPC has a bounded performance ratio, which converges to 1 with an exponential rate in the number of available predictions. Formally:
\begin{corollary}
\label{thm:mpcs_pr}
  $\PR^S(\MPC_k) = \frac{\MPCS_k}{\STO_k} \le \frac{\MPCS_k}{\STO_\infty} = \frac{\MPCS_k}{\MPCS_\infty} = 1 + O(\|F^k\|^2) = 1 + O(\lambda^{2k})$. Moreover, in Example \ref{ex:sto_finite_pred}, we have $\PR^S(\MPC_k) = 1 + \Theta(\|F^k\|^2)$.
\end{corollary}

Besides, the dynamic regret of MPC (nearly) matches the order of the optimal dynamic regret.
\begin{theorem}[Main result] \label{thm:regret_mpcs}
  $Reg^S(\MPC_k) = \mpcs_k^T - \sto_T^T = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$, where the second term results from the difference between finite/infinite horizons.
\end{theorem}

\begin{theorem} \label{thm:regret_sto}
  The optimal dynamic regret ${Reg_k^S}^* = \sto_k^T - \sto_T^T = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$ and there exist $A$, $B$, $Q$, $R$, $\Qf$, $x_0$, and $\cW$ such that
  ${Reg_k^S}^* = \Theta(\|F^k\|^2 (T - k))$.
\end{theorem}

Note that, in the stochastic case, the regret-optimal policy is the same as the cost-optimal policy, i.e., the policy for $\sto_k^T$ is the same as ${Reg_k^S}^*$.

\section{Adversarial disturbances} \label{sec:adv}
We now move from stochastic to adversarial disturbances.  In this section, the disturbances are chosen from a bounded set $\Omega \subseteq \bR^n$ by an adversary in order to maximize the controller's cost.
Maintaining small regret is more challenging in adversarial models than in stochastic ones, so one may expect weaker bounds. Perhaps surprisingly, we obtain bounds with the same order.

\paragraph{Optimal policy.} \label{sec:adv_optimal}
In the adversarial setting, the cost of the optimal policy, defined with a sequence of $\min$'s and $\sup$'s, is the equilibrium value of a two-player zero-sum game.
In general, it is impossible to give an analytical expression of either $\ADV_k$ or the corresponding optimal policy.
However, we prove a result that is structurally similar to the results from the stochastic setting, highlighting the exponential improvement from predictions.

\begin{theorem} \label{thm:adv_pred_diff}
  For $k \ge 1$, $\ADV_k - \ADV_{k+1} = O(\|F^k\|^2) =  O(\lambda^{2k})$.
\end{theorem}

Similarly to \Cref{ex:sto_finite_pred} for the stochastic case, in the adversarial setting, the optimal cost with $k$ predictions may approach the offline optimal cost (under infinite predictions) much faster than exponential rate, and it is possible that $\ADV_k = \ADV_\infty$ for finite $k$, as shown in \Cref{ex:adv_finite_pred}.

\begin{example} \label{ex:adv_finite_pred}
  Let $A = B = Q = R = 1$ and $\Omega = [-1, 1]$. In this case, one prediction is enough to leverage the full power of prediction. Formally, we have $\ADV_1 = \ADV_\infty = 1$. In other words, for all $k \ge 1$, $\ADV_k = 1$. The optimal control policy (as $T \to \infty$) is a piecewise function:
  \[u^*(x, w) = \begin{cases}
    -(x+w) &, -1 \le x+w \le 1 \\
    -(x+w) + \frac{3 - \sqrt{5}}{2} (x+w-1) &, x+w > 1 \\
    -(x+w) + \frac{3 - \sqrt{5}}{2} (x+w+1) &, x+w < -1
  \end{cases}.\]

  The proof leverages two different cost-to-go functions for the $\min$ player and the $\sup$ player.
\end{example}
Note that the optimal policy could be much more complex.
Unlike \Cref{ex:adv_finite_pred}, where the optimal policy is piecewise linear with only 3 pieces, for other values of $A, B, Q, R$, this function may have many more pieces.

\iffalse
\ck{Is there an analytical expression of $\ADV_k$ in 1-dim using the minimax theorem? Two predictions are enough if $A = 2$, but not if $A = 3$.}

\ck{If $n = 1$ and $\Omega = [-1, 1]$, then $\ADV_\infty = (1 - F^2 - H P) P / (1 - \abs{F})^2$.}\guanya{I like this result very much but we need to find some ``story'' for it}
\fi

\paragraph{Model predictive control.}

Under adversarial disturbances, MPC is suboptimal, e.g., in Example \ref{ex:adv_finite_pred}. However, its performance ratio and dynamic regret bounds turn out to be the same as those in the stochastic setting.

\begin{theorem} \label{thm:mpca_diff}
  $\MPCA_k - \MPCA_{k+1} = O(\|F^k\|^2) = O(\lambda^{2k})$.
\end{theorem}

\begin{corollary}\label{cor:mpca/adv_inf}
  For $k \ge 1$, $\PR^A(\MPC_k) = \frac{\MPCA_k}{\ADV_k} \le \frac{\MPCA_k}{\ADV_\infty} = \frac{\MPCA_k}{\MPCA_\infty} = 1 + O(\|F^k\|^2) = 1 + O(\lambda^{2k})$.
\end{corollary}

This highlights that MPC has a bounded performance ratio, which converges to 1 with exponential rate. Additionally, MPC has the same order of dynamic regret as the stochastic case:

\begin{theorem}[Main result] \label{thm:regret_mpca}
  $Reg^A(\MPC_k) = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$.
\end{theorem}

This dynamic regret is linear in the horizon $T$ if we fix the number of predictions. However, if $k$ is a super-constant function of $T$ --- an increasing function of $T$ that is not upper-bounded by a constant --- then the regret is sub-linear.
Furthermore, if we let $k = \frac{\log T}{2 \log(1/\lambda)}$, then $Reg^A(\MPC_k) = O(1)$. In other words, we can get constant regret with $O(\log T)$ predictions, even with adversarial disturbances.
Finally, as implied by the following result, the $O(\log T)$ horizon cannot be improved since even the regret minimizing algorithm needs the same order of predictions to reach constant regret.

\begin{theorem} \label{thm:regret_adv}
  ${Reg^A_k}^* = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$.
  Moreover, there exist $A$, $B$, $Q$, $R$, $\Qf$, $x_0$, and $\Omega$ such that ${Reg^A_k}^* = \Omega(\|F^k\|^2 (T - k))$.\footnote{$\Omega(\cdot)$ is the growth order notation and has nothing to do with the bounded set $\Omega$.}
\end{theorem}

\section{Numerical experiments}

To illustrate our theoretical results, we test MPC with different numbers of predictions in a Linear Quadratic (LQ) tracking problem, where the desired trajectory is given by:
\[d_t = \begin{bmatrix}
  8 \sin(t/3) \cos(t/3) \\
  8 \sin(t/3)
\end{bmatrix}.\]
We consider following double integrator dynamics:
\[p_{t+1} = p_t + v_t + h_t, \qquad v_{t+1} = v_t + u_t + \eta_t,\]
where $p_t \in \mathbb{R}^2$ is the position, $v_t$ is the velocity, $u_t$ is the control, and $h_t, \eta_t \sim \mathrm{U}[-1, 1]^2$ are i.i.d.\ noises.

The objective is to minimize
\[\sum_{t=0}^{T-1} \norm{p_t - d_t}^2 + \norm{u_t}^2,\]
where we let $T = 200$.

This problem can be converted to the standard LQR with disturbance $w_t$ by letting $x_t = \begin{bsmallmatrix} p_t \\ v_t \end{bsmallmatrix}$ and $\tilde w_t = \begin{bsmallmatrix} h_t \\ \eta_t \end{bsmallmatrix}$ and then using the reduction in the LQ tracking example in \Cref{sec:model}. Note that after the reduction, the disturbances are the combination of a deterministic trajectory and i.i.d. noises, which corresponds to the case discussed in \Cref{sec:general_sto}.

\Cref{fig:numerics} shows the tracking results with MPC using different numbers of predictions. We see that the regret exponentially decreases as the number of predictions increases, which is consistent with our theoretical results.

\begin{figure}[t]
  \centering
  \includegraphics[height = 0.25 \hsize]{figures/eight-tracking_0.pdf}
  \includegraphics[height = 0.25 \hsize]{figures/eight-tracking_1.pdf}
  \includegraphics[height = 0.25 \hsize]{figures/eight-tracking_2.pdf}
  \includegraphics[height = 0.25 \hsize]{figures/eight-tracking_4.pdf}
  \includegraphics[height = 0.25 \hsize]{figures/eight-tracking_8.pdf}
  \includegraphics[height = 0.25 \hsize]{figures/cost_diff.pdf}
  \caption{The power of predictions in online tracking. The left four figures show the desired trajectory (blue) and the actual trajectories (orange). The rightmost figure shows the cost difference (regret) between MPC using $k$ predictions and the offline optimal policy. Note that the y-axis of the rightmost figure is in log-scale.}
  \label{fig:numerics}
\end{figure}

\section{Concluding remarks}

\iffalse
\begin{table}[ht]
  \centering
  \caption{Summary of our results. Most of our bounds are tight --- i.e., there exist $A, B, Q, R$, and $\cW$ or $\Omega$ such that the bound is reached --- except the performance ratio of MPC in the adversarial setting. Intuitively, the adversarial setting is harder than the stochastic one, but we obtain the same bound for them.}
  \begin{threeparttable}
  \begin{tabular}{c c c c}
    \toprule
                          &              & Performance ratio                       & Dynamic regret \\
    \midrule[0.7pt]
    \multirow{2}{*}{Stochastic}  & Optimal\tnote{\dag} & $1$                                     & $O(\|F^k\|^2 T + 1)$, tight \\
                                 & MPC                 & $1 + O(\|F^k\|^2)$, tight & $O(\|F^k\|^2 T + 1)$, tight \\
    \midrule
    \multirow{2}{*}{Adversarial} & Optimal\tnote{\dag} & $1$                                     & $O(\|F^k\|^2 T + 1)$, tight \\
                                 & MPC                 & $1 + O(\|F^k\|^2)$        & $O(\|F^k\|^2 T + 1)$, tight \\
    \bottomrule
  \end{tabular}
  \begin{tablenotes}
    \item[\dag] For stochastic disturbance, the policy that minimizes the performance ratio and the policy that minimizes the regret are the same. However, this is not true for adversarial disturbance.
  \end{tablenotes}
  \end{threeparttable}
\end{table}

\begin{table}[ht]
  \centering
  \caption{Summary of our results. Most of our bounds are tight --- i.e., there exist $A, B, Q, R$, and $\cW$ or $\Omega$ such that the bound is reached --- except performance ratio of MPC in the adversarial setting.}
  \begin{threeparttable}
  \begin{tabular}{cccc}
    \toprule
                &              & Stochastic                                & Adversarial  \\
    \midrule[0.7pt]
    \multirow{2}{*}{Performance ratio} & Optimal\tnote{\dag} & $1$                                       & $1$                                       \\
                                       & MPC                 & $1 + O(\|F^k\|^2)$, tight   & $1 + O(\|F^k\|^2)$          \\
    \midrule
    \multirow{2}{*}{Dynamic regret}    & Optimal\tnote{\dag} & $O(\|F^k\|^2 T + 1)$, tight & $O(\|F^k\|^2 T + 1)$, tight \\
                                       & MPC                 & $O(\|F^k\|^2 T + 1)$, tight & $O(\|F^k\|^2 T + 1)$, tight \\
    \bottomrule
  \end{tabular}
  \begin{tablenotes}
    \item[\dag] For stochastic disturbance, the policy that minimizes the performance ratio and the policy that minimizes the regret are the same. However, this is not true for adversarial disturbance.
  \end{tablenotes}
  \end{threeparttable}
\end{table}

\begin{table}[ht]
  \centering
  \caption{Summary of our results. Most of our bounds are tight --- i.e., there exist $A, B, Q, R$, and $\cW$ or $\Omega$ such that the bound is reached --- except MPC's performance ratio in the adversarial setting.}
  \begin{threeparttable}
  \begin{tabular}{c c c}
    \toprule
                              & Stochastic                                & Adversarial  \\
    \midrule
    Minimum performance ratio & $1$                                       & $1$                                       \\
    MPC's performance ratio   & $1 + O(\|F^k\|^2)$, tight   & $1 + O(\|F^k\|^2)$          \\
    Minimum dynamic regret    & $O(\|F^k\|^2 T + 1)$, tight & $O(\|F^k\|^2 T + 1)$, tight \\
    MPC's dynamic regret      & $O(\|F^k\|^2 T + 1)$, tight & $O(\|F^k\|^2 T + 1)$, tight \\
    \bottomrule
  \end{tabular}
  \iffalse
  \begin{tablenotes}
    \item[\dag] The policy that minimizes the performance ratio may be different from the one that minimizes the regret.
    \ck{make sure they are different?} \guanya{a bit confusing here.}
  \end{tablenotes}
  \fi
  \end{threeparttable}
\end{table}

\begin{table}[ht]
  \centering
  \caption{Summary of our results. Most of our bounds are tight --- i.e., there exist $A, B, Q, R$, and $\cW$ or $\Omega$ such that the bound is reached --- except for those of the marginal benefit of prediction in the adversarial setting.}
  \begin{tabular}{c c c c}
    \toprule
    Setting                      & Policy         & Marginal benefit of prediction & Regret \\
    \midrule[0.7pt]
    \multirow{2}{*}{Stochastic}  & Optimal        & $O(\|F^k\|^2)$, tight but also can be 0 & $O(\|F^k\|^2 T + 1)$, tight \\
                                 & MPC            & $O(\|F^k\|^2)$, tight                   & $O(\|F^k\|^2 T + 1)$, tight \\
    \midrule
    \multirow{3}{*}{Adversarial} & Cost-optimal   & $O(\|F^k\|^2)$, can be 0 & / \\
                                 & Regret-optimal & /                                      & $O(\|F^k\|^2 T + 1)$, tight \\
                                 & MPC            & $O(\|F^k\|^2)$           & $O(\|F^k\|^2 T + 1)$, tight \\
    \bottomrule
  \end{tabular}
\end{table}
\fi

We conclude with several open problems and potential future research directions. Our results highlight the power of predictions and show that, given predictions, a simple greedy policy (MPC) is near-optimal for LQR control with disturbances in the dynamics, in terms of dynamic regret.  Building on our results, it will be interesting to understand if MPC has a constant competitive ratio in this setting. In a different but related setting, \citet{chen2015online} show for negative results on the competitive ratio so the answer is unclear at this point.  Additionally, in this paper predictions are assumed to be perfect.  Of course, in real applications predictions are noisy and are derived based on historical data.  An important extension will be to understand how the analysis and results in this paper can extend to models with imperfect predictions learned from history, such as done in related models \cite{shi2020beyond,chen2015online}.
Finally, real-world MPC problems often require non-linear dynamics and/or constraints, and the learning-theoretic study of such settings remains largely unexplored.

\section*{Broader Impact}
Linear quadratic control is a common and powerful model with a variety of commercial and industrial applications, e.g., in robotics, chemical process control, and energy systems. This paper provides new fundamental insights about the role of predictions in online linear quadratic control with disturbances and provides the first finite time performance guarantees for the most commonly used policy in the linear quadratic setting, model predictive control (MPC).

The guarantees provided by the theoretical analysis in this paper offer the potential for ensuring safety and robustness in industry applications where predictions are common and MPC is used. However, like many other theoretical contributions, this paper's results are limited to its assumptions, e.g., linear system and fixed system parameters $\{A,B,Q,R\}$. The performance of MPC and the fundamental limits in other scenarios, e.g., nonlinear dynamics or time-variant $\{A,B,Q,R\}$, are still open research problems.

We see no ethical concerns related to the results in this paper.

\begin{ack}
This project was supported in part by funding from Raytheon, DARPA PAI, AitF-1637598 and CNS-1518941, with additional support for Guanya Shi provided by the Simoudis Discovery Prize.
\end{ack}

{\small
\bibliographystyle{plainnat}
\bibliography{ref}}

\newpage
\appendix

\iffalse
\section{Minor revision}
The upper bounds in \Cref{thm:regret_mpcs,thm:regret_sto,thm:regret_mpca,thm:regret_adv} should be $O(\|F^k\|^2 T + 1)$ instead of $O(\|F^k\|^2 T + \|F^k\|)$. This change does not affect any conclusions or implications in this paper.
\fi

\section{Proofs of Section~\ref{sec:iid}}
In all proofs in this paper, for a sequence $x = (x_0, x_1, \dots, x_n)$, we use $x_{a:b}$ to denote its consecutive subsequence $(x_a, x_{a+1}, \dots, x_b)$.

\iffalse
\begin{figure}
  \centering
  \includegraphics[width=0.7\textwidth]{STO_k&ADV_k.png}
  \caption{How $\STO_k$ and $\ADV_k$ may shrink as $k$ increases. For this figure, we use $A = B = Q = R = 1$. For $\STO_k$, the disturbance $w_t = \pm 1$ with probability $\nicefrac{1}{2}$ respectively and is i.i.d. For $\ADV_k$, $w_t \in \Omega = [-1, 1]$. As in \Cref{ex:adv_finite_pred}, $\ADV_k$ does not further decrease when $k \ge 1$, though this may not be true for other values of $A, B, Q, R$.}
  \label{fig:STO_kADV_k}
\end{figure}
\fi

\subsection{Proof of Theorem~\ref{thm:iid_pred}}
\textit{Let $w_t$ be i.i.d.\ with zero mean and covariance matrix $W$. Suppose the controller has $k \ge 1$ predictions. Then, the optimal control policy at each step $t$ is given by:
  \begin{equation}
    u_t = -(R + B^\top P B)^{-1} B^\top \left(P A x_t + \sum_{i=0}^{k-1} (A^\top - A^\top P H)^i P w_{t+i}\right), \tag{\ref{eq:iid_policy}}
  \end{equation}
  where $P$ is the solution of DARE in \Cref{eq:DARE}. The cost under this policy is:
  \begin{equation}
    \STO_k = \Tr{\left(P - \sum_{i=0}^{k-1} P (A - HPA)^i H (A^\top - A^\top PH)^i P\right) W}, \tag{\ref{eq:iid_pred_cost}}
  \end{equation}
   where $H = B (R + B^\top P B)^{-1} B^\top$.}

\begin{proof}

  Our proof technique closely follows that in Section 4.1 of \cite{goel2020power}. To begin, note that the definition of $\sto^T_k$ has a structure of repeating $\min$'s and $\bEE$'s. We use dynamic programming to compute the value iteratively. In particular, we apply backward induction to solve the optimal cost-to-go functions, from time step $T$ to the initial state. Given state $x_t$ and predictions $w_t, \dots, w_{t+k-1}$, we define the cost-to-go function:
  \begin{align}
    V_t(x_t; w_{t:t+k-1})
    & \coloneqq \min_{u_t} \bEE[w_{t+k}] \min_{u_{t+1}} \cdots \bEE[w_{T-1}] \min_{u_{T-k}, \cdots, u_{T-1}} \sum_{i=t}^{T-1} (x_i^\top Q x_i + u_i^\top R u_i) + x_T^\top \Qf x_T \label{eq:V_t_pred} \\
    & = x_t^\top Q x_t + \min_{u_t} \left(u_t^\top R u_t + \bE[w_{t+k}]{V_{t+1}(A x_t + B u_t + w_t; w_{t+1:t+k})}\right) \notag
  \end{align}
  with $V_T(x_T; \dots) = x_T^\top \Qf x_T$.
  Note that $\bEE[w_{t+k}]$ has no effect for $t \ge T - k$.
  This function measures the expected overall control cost from a given state to the end, assuming the controller makes the optimal decision at each time.

  We will show by backward induction that for every $t = 0, \dots, T$, $V_t(x_t; w_{t:t+k-1}) = x_t^\top P_t x_t + v_t^\top x_t + q_t$, where $P_t, v_t, q_t$ are coefficients that may depend on $w_{t:t+k-1}$. This is clearly true for $t = T$. Suppose this is true at $t + 1$. Then,
  \begin{align*}
    & V_t(x; w_{t:t+k-1}) \\
    & = x^\top Q x + \min_u \Big( u^\top R u + (Ax + Bu + w_t)^\top P_{t+1} (Ax + Bu + w_t) \\
    & \quad + \bE[w_{t+k}]{v_{t+1}}^\top (Ax + Bu + w_t) + \bE[w_{t+k}]{q_{t+1}} \Big) \\
    & = x^\top Q x + (Ax + w_t)^\top P_{t+1} (Ax + w_t) + \bE[w_{t+k}]{v_{t+1}}^\top (Ax + w_t) + \bE[w_{t+k}]{q_{t+1}} \\
    & \quad + \min_u \left(u^\top (R + B^\top P_{t+1} B) u + u^\top B^\top \left(2 P_{t+1} Ax + 2 P_{t+1} w_t + \bE[w_{t+k}]{v_{t+1}}\right)\right).
  \end{align*}
  The optimal $u$ is obtained by setting the derivative to be zero:
  \begin{equation} \label{eq:u_pre}
    u^* = -(R + B^\top P_{t+1} B)^{-1} B^\top \left(P_{t+1} A x + P_{t+1} w_t + \frac{1}{2} \bE[w_{t+k}]{v_{t+1}}\right).
  \end{equation}
  Let $H_t = B (R + B^\top P_{t+1} B)^{-1} B^\top$.
  Plugging $u^*$ back into $V_t$, we have
  \begin{align*}
    & V_t(x; w_{t:t+k-1}) \\
    & = x^\top Q x + (Ax + w_t)^\top P_{t+1} (Ax + w_t) + \bE[w_{t+k}]{v_{t+1}}^\top (Ax + w_t) + \bE[w_{t+k}]{q_{t+1}} \\
    & \quad - \left(P_{t+1} A x + P_{t+1} w_t + \frac{1}{2} \bE[w_{t+k}]{v_{t+1}}\right)^\top H_t \left(P_{t+1} A x + P_{t+1} w_t + \frac{1}{2} \bE[w_{t+k}]{v_{t+1}}\right) \\
    & = x^\top \left(Q + A^\top P_{t+1} A - A^\top P_{t+1} H_t P_{t+1} A\right) x \\
    & \quad + x^\top \left((A^\top - A^\top P_{t+1} H_t) \bE[w_{t+k}]{v_{t+1}} + 2 (A^\top - A^\top P_{t+1} H_t) P_{t+1} w_t\right) \\
    & \quad + w_t^\top (P_{t+1} - P_{t+1} H_t P_{t+1}) w_t + w_t^\top (I - P_{t+1} H_t) \bE[w_{t+k}]{v_{t+1}} \\
    & \quad - \frac{1}{4} \bE[w_{t+k}]{v_{t+1}}^\top H_t \bE[w_{t+k}]{v_{t+1}} + \bE[w_{t+k}]{q_{t+1}}.
  \end{align*}
  Thus, the recursive formulae, which parallel \cite{goel2020power}, are given by:
  \begin{subequations} \label{eq:Pvq}
  \begin{align}
    P_t & = Q + A^\top P_{t+1} A - A^\top P_{t+1} H_t P_{t+1} A, \\
    v_t & = (A^\top - A^\top P_{t+1} H_t) \bE[w_{t+k}]{v_{t+1}} + 2 (A^\top - A^\top P_{t+1} H_t) P_{t+1} w_t, \\
    \begin{split}
      q_t & = w_t^\top (P_{t+1} - P_{t+1} H_t P_{t+1}) w_t + w_t^\top (I - P_{t+1} H_t) \bE[w_{t+k}]{v_{t+1}} \\
      & \quad - \frac{1}{4} \bE[w_{t+k}]{v_{t+1}}^\top H_t \bE[w_{t+k}]{v_{t+1}} + \bE[w_{t+k}]{q_{t+1}}.
    \end{split}
  \end{align}
  \end{subequations}
  As $T - t \to \infty$, $P_t$ and $H_t$ converge to $P$ and $H$ respectively, where $P$ is the solution of discrete-time algebraic Riccati equation (DARE) $P = Q + A^\top P A - A^\top PHPA$, and $H = B (R + B^\top P B)^{-1} B^\top$. Note that $v_T=0$ and $q_T=0$. Then,
  \begin{align}
    v_t & = 2 \sum_{i=0}^{k-1} (A^\top - A^\top P H)^{i+1} P w_{t+i}, \label{eq:v_t} \\
    q_t & = w_t^\top (P - PHP) w_t + w_t^\top (I - PH) \bE[w_{t+k}]{v_{t+1}} - \frac{1}{4} \bE[w_{t+k}]{v_{t+1}}^\top H \bE[w_{t+k}]{v_{t+1}} + \bE[w_{t+k}]{q_{t+1}}, \label{eq:q_t} \\
    & \!\!\!\!\!\! \bE[w_{t+k}]{v_{t+1}} = 2 \sum_{i=1}^{k-1} (A^\top - A^\top P H)^i P w_{t+i}. \label{eq:E_v_t+1}
  \end{align}
  Taking the expectation of $q_t$ over all randomness, namely $w_0, w_1, w_2, \dots$, we have
  \begin{align}
    \bE{q_t}
    & = \Tr{(P - PHP) W} - \sum_{i=1}^{k-1} \Tr{P (A - HPA)^i H (A^\top - A^\top P H)^i P W} + \bE{q_{t+1}} \notag \\
    & = \Tr{\left(P - \sum_{i=0}^{k-1} P (A - HPA)^i H (A^\top - A^\top PH)^i P\right) W} + \bE{q_{t+1}}, \label{eq:E[q_t]}
  \end{align}
  where in the first equality we use $\bE{w_t} = 0$ and the independence of the disturbances.
  Thus, as $T \rightarrow \infty$, in each time step, a constant cost is incurred and the average cost $\STO_k$ is exactly this value.
  \begin{align*}
    & \STO_k
    = \lim_{T \to \infty} \frac{1}{T} \sto^T_k
    = \lim_{T \to \infty} \frac{1}{T} \bE{V_0(x_0; w_{0:k-1})}
    = \lim_{T \to \infty} \frac{1}{T} \bE{q_0} \\
    & = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \bE{q_t} - \bE{q_{t+1}}
    = \Tr{\left(P - \sum_{i=0}^{k-1} P (A - HPA)^i H (A^\top - A^\top PH)^i P\right) W}.
  \end{align*}

  The explicit form of the optimal control policy is obtained by combining \Cref{eq:u_pre,eq:E_v_t+1}.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:mpc_policy}}
\textit{In \Cref{alg:mpc}, let $\tilde\Qf = P$. Then, the MPC policy with $k$ predictions is also given by \Cref{eq:iid_policy}. Assuming i.i.d.\ disturbance with zero mean, the MPC policy is optimal.}

\begin{proof}

  Due to the greedy nature, MPC policy is given by the solution of a length-$k$ optimal control problem, given deterministic $w_t,\cdots,w_{t+k-1}$. In other words, we want to derive the optimal policy $(u_t, \dots, u_{t+k-1})$ that minimizes
  \[\sum_{i=t}^{t+k-1} (x_i^\top Q x_i + u_i^\top R u_i) + x_{t+k}^\top P x_{t+k},\]
  where $x_{i+1} = A x_i + B u_i + w_i$, given $x_t, w_t, \dots, w_{t+k-1}$.
  Define the cost-to-go function at time $i$ given $x_i, w_i, \dots, w_{t+k-1}$:
  \begin{align*}
    V_i(x_i; w_{i:t+k-1})
    & = \min_{u_{i:t+k-1}} \sum_{j=i}^{t+k-1} (x_j^\top Q x_j + u_j^\top R u_j) + x_{t+k}^\top P x_{t+k} \\
    & = x_i^\top Q x_i + \min_{u_i}(u_i^\top R u_i + V_{i+1}(A x_i + B u_i + w_i; w_{i+1:t+k-1})).
  \end{align*}
  Note that $V_{t+k}(x_{t+k}) = x_{t+k}^\top P x_{t+k}$.
  Similar to the proof of \Cref{thm:iid_pred}, we can inductively show that $V_i(x_i; w_{i:t+k-1}) = x_i^\top P x_i + v_i^\top x_i + q_i$ for some $v_i$ and $q_i$. Note that the second-degree coefficient no longer depends on the index $i$ as in the previous proof because we start from $P$, the solution of DARE.
  We then have the followings equations that parallel with \Cref{eq:v_t,eq:u_pre}:
  \begin{align*}
    v_i & = 2 \sum_{j=0}^{t+k-i-1} {F^\top}^{j+1} P w_{i+j}, \\
    u_i^* & = -(R + B^\top P B)^{-1} B^\top \left(P A x_i + P w_i + \frac{1}{2} v_{i+1}\right) \\
    & = -(R + B^\top P B)^{-1} B^\top \left(P A x_i + \sum_{j=0}^{t+k-i-1} {F^\top}^j P w_{i+j}\right).
  \end{align*}
  The case $i = t$ gives:
  \[u_t^* = -(R + B^\top P B)^{-1} B^\top \left(P A x_t + \sum_{j=0}^{k-1} {F^\top}^j P w_{t+j}\right),\]
  which is the MPC policy at time step $t$, and is same as \Cref{eq:iid_policy}.

  \iffalse
  We first show that for any $x_0$,
  \[x_0^\top P x_0 = \lim_{T \to \infty} \min_{u_0, \dots, u_{T-1}} \sum_{i=0}^{T-1} (x_i^\top Q x_i + u_i^\top R u_i),\]
  where $x_{i+1} = A x_i + B u_i$.
  Note that there is no disturbance, so the overall cost is finite \cite{anderson2007optimal}.
  Let $V_t(x_t) = \min_{u_t, \dots, u_{T-1}} \sum_{i=t}^{T-1} x_i^\top Q x_i + u_i^\top R u_i$. We will inductively show that $V_t(x)$ is a quadratic form, i.e., $V_t(x) = x^\top P_t x$, where $P_t$ is a matrix to be determined. Clearly, $V_{T-1}(x) = x^\top Q x$ satisfies the claim with $P_{T-1} = Q$. Suppose the claim is true at $t + 1$. Then,
  \begin{align*}
    V_t(x) & = x^\top Q x + \min_u (u^\top R u + V_{t+1}(A x + B u)) \\
    & = x^\top Q x + \min_u (u^\top R u + (Ax+Bu)^\top P_{t+1} (Ax+Bu)) \\
    & = x^\top (Q + A^\top P_{t+1} A) x + \min_u (u^\top (R + B^\top P_{t+1} B) u + 2 u^\top B^\top P_{t+1} A x) \\
    & = x^\top (Q + A^\top P_{t+1} A - A^\top P_{t+1} H P_{t+1} A) x.
  \end{align*}
  Thus, as $T - t \to \infty$, $P_t \to P$.

  Replace $x_0$ by $x_{t+k}$ in the above result and we have the following:
  \begin{align*}
    & \min_u \sum_{i=t}^{t+k-1} x_i^\top Q x_i + u_i^\top R u_i + x_{t+k}^\top P x_{t+k} \text{ where } x_{i+1} = A x_i + B u_i + w_i \text{ for } i \in [t, t + k - 1] \\
    & = \min_u \sum_{i=t}^\infty x_i^\top Q x_i + u_i^\top R u_i \text{ where } x_{i+1} = A x_i + B u_i + w_i \text{ for } i \ge t \text{ and } w_i = 0 \text{ for } i \ge t + k.
  \end{align*}
  Therefore, we are actually looking for the optimal control policy with infinite predictions ($k \to \infty$) but only the first $k$ of which are non-zero. Let $k \to \infty$ and $w_i = 0$ for $i \ge t + k$ in \Cref{eq:iid_policy}. Then we obtain \Cref{eq:iid_policy} itself.
  \fi
\end{proof}

\section{Proofs of Section~\ref{sec:general_sto}}

\subsection{Proof of Theorem~\ref{thm:sto_pred_diff}}
\textit{The optimal control policy with general stochastic disturbance is given by:
  \begin{equation}
    u_t = -(R + B^\top P B)^{-1} B^\top \Bigg(P A x_t + \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i} + \sum_{i=k}^\infty {F^\top}^i P \mu_{t+i|t+k-1}\Bigg), \tag{\ref{eq:sto_policy}}
  \end{equation}
  where $\mu_{t'|t} = \bE{w_{t'} \given w_0, \dots, w_t}$.
  Under this policy, the marginal benefit of obtaining an extra prediction decays exponentially fast in the existing number $k$ of predictions. Formally, for $k \ge 1$,
  \[\STO_k - \STO_{k+1} = O(\|F^k\|^2) = O(\lambda^{2k}).\]}

\begin{proof}
  Similar to the proof of \Cref{thm:iid_pred}, we assume
  \[V_t(x_t; w_{0:t+k-1}) = x_t^\top P_t x_t + x_t^\top v_t + q_t,\]
  where $V_t$ has a similar definition as in \Cref{eq:V_t_pred} but may further depend on $w_0, \dots, w_{t-1}$ because the disturbance sequence is no longer Markovian.
  In this case, $P_t$, $v_t$ and $q_t$ still satisfy the recursive forms in \Cref{eq:Pvq}. However, the expected values of $w_t$ and $v_t$ are different since we have a more general distribution now.

  Let $T - t \to \infty$, $\mu_{t'|t} = \bE{w_{t'} \given w_0, \dots, w_t}$ and $F = A - HPA$. Then,
  \begin{align}
    v^k_t & = 2 \sum_{i=0}^{k-1} {F^\top}^{i+1} P w_{t+i} + 2 \sum_{i=k}^\infty {F^\top}^{i+1} P \mu_{t+i|t+k-1}, \label{eq:v_t-general} \\
    q^k_t & = w_t^\top (P - PHP) w_t + w_t^\top (I - PH) \bE[w_{t+k}]{v^k_{t+1}} - \frac{1}{4} \bE[w_{t+k}]{v^k_{t+1}}^\top H \bE[w_{t+k}]{v^k_{t+1}} + \bE[w_{t+k}]{q^k_{t+1}}, \notag
  \end{align}
  where the superscript $k$ denotes the number of predictions.

  The optimal policy in this case has the same form as \Cref{eq:u_pre}. Plugging \Cref{eq:v_t-general} into it, we obtain the optimal policy in the theorem.

  Further,
  \begin{subequations}
  \begin{align}
    \bE{q^k_t - q^{k+1}_t}
    & = \bE{w_t^\top (I - PH) \left(\bE[w_{t+k}]{v^k_{t+1}} - \bE[w_{t+k+1}]{v^{k+1}_{t+1}}\right)} \label{eq:dqt1} \\
    & \quad + \frac{1}{4} \bE{\bE[w_{t+k+1}]{v^{k+1}_{t+1}}^\top H \bE[w_{t+k+1}]{v^{k+1}_{t+1}} - \bE[w_{t+k}]{v^k_{t+1}}^\top H \bE[w_{t+k}]{v^k_{t+1}}} \label{eq:dqt2} \\
    & \quad + \bE{q^k_{t+1} - q^{k+1}_{t+1}},
  \end{align}
  \end{subequations}
  where the expectation $\bEE$ is taken over all randomness. Part \eqref{eq:dqt1} is zero because
  \[\bE[w_{t+k}]{v^k_{t+1}} = \bE[w_{t+k}, w_{t+k+1}]{v^{k+1}_{t+1}}.\]
  \begin{align*}
    \text{Part \eqref{eq:dqt2}}
    & = \frac{1}{4} \bE[w_{t+k}]{\left(\bE[w_{t+k+1}]{v^{k+1}_{t+1}} - \bE[w_{t+k}]{v^k_{t+1}}\right)^\top H \left(\bE[w_{t+k+1}]{v^{k+1}_{t+1}} - \bE[w_{t+k}]{v^k_{t+1}}\right)} \\
    & = \bE[w_{t+k}]{z_{k,t}^\top H z_{k,t}},
  \end{align*}
  where
  \[z_{k,t} = {F^\top}^k P (w_{t+k} - \mu_{t+k|t+k-1}) + \sum_{i=k+1}^\infty {F^\top}^i P (\mu_{t+i|t+k} - \mu_{t+i|t+k-1}).\]
  Note that $z_{k,t} = F^\top z_{k-1,t+1} = {F^\top}^k z_{0,t+k}$. Thus,
  \begin{align*}
    \STO_k - \STO_{k+1}
    & = \lim_{T \to \infty} \frac{1}{T} \bE{q^k_0 - q^{k+1}_0} \\
    & = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \bE{z_{k,t}^\top H z_{k,t}} \\
    & = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \bE{z_{0,t+k}^\top F^k H {F^\top}^k z_{0,t+k}} \\
    & = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \Tr{F^k H {F^\top}^k \bE{z_{0,t+k} z_{0,t+k}^\top}} \\
    & \le \norm{F^k}^2 \norm{H} \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \Tr\bE{z_{0,t+k} z_{0,t+k}^\top}
  \end{align*}
  where in the last line we use the fact that if $A$ is symmetric, then $\Tr{AB} \le \lambda_{\max}(A) \Tr{B}$. Finally we just need to show the last item $\Tr\bE{z_{0,t+k} z_{0,t+k}^\top}$ is uniformly bounded for all $t$. This is straightforward because the cross-correlation of each disturbance pair is uniformly bounded, i.e., there exists $m > 0$ such that for all $t, t' \ge 1$, $\bE{w_t^\top w_{t'}} \le m$.

  \begin{align*}
    \Tr\bE{z_{0,t} z_{0,t}^\top}
    & = \sum_{i,j=0}^\infty \Tr\bE{P F^i {F^\top}^j P (\mu_{t+j|t} - \mu_{t+j|t-1}) (\mu_{t+i|t} - \mu_{t+i|t-1})^\top} \\

    & = \sum_{i,j=0}^\infty \Tr{P F^i {F^\top}^j P \bE{\mu_{t+j|t} \mu_{t+i|t}^\top - \mu_{t+j|t-1} \mu_{t+i|t-1}^\top}} \\

    & \le \sum_{i,j=0}^\infty \norm{F^i} \norm{F^j} \norm{P}^2 \bE{w_{t+j}^\top w_{t+i} - w_{t+j}^\top w_{t+i}} \\

    & \le \sum_{i,j=0}^\infty c \lambda^i c \lambda^j \norm{P}^2 2 m = 2 \frac{c^2}{(1 - \lambda)^2} \norm{P}^2 m
  \end{align*}
  for some constant $c$ from Gelfand’s formula.
  Thus $\Tr\bE{z_{0,t} z_{0,t}^\top}$ is bounded by a constant independent of $t$. Thus,
  \[\STO_k - \STO_{k+1} = O(\|F^k\|^2).\]
\end{proof}

\subsection{Proof of Theorem~\ref{thm:mpcs_diff}}
\textit{$\MPCS_k - \MPCS_{k+1} = O(\|F^k\|^2) = O(\lambda^{2k})$. Moreover, in Example \ref{ex:exp_speed}, $\MPCS_k - \MPCS_{k+1} = \Theta(\|F^k\|^2)$.}
\begin{proof}

  To recursively calculate the value of $J^{\MPC_k}$, we define:
  \begin{align*}
    V_t^{\MPC_k}(x_t; w_{0:t+k-1})
    & = \sum_{i=t}^{T-1} (x_i^\top Q x_i + u_i^\top R u_i) + x_T^\top \Qf x_T \\
    & = x_t^\top Q x_t + u_t^\top R u_t + V_{t+1}(A x_t + B u_t + w_t; w_{0:t+k})
  \end{align*}
  as the cost-to-go function with MPC as the policy, i.e., $u_t$ is the control at time step $t$ from the MPC policy with $k$ predictions.
  Similar to the previous proofs, we assume $V_t^{\MPC_k}(x) = x^\top P_t x + x^\top v_t + q_t$ (which turns out to be correct by induction) and $T - t \to \infty$ so that $P_t = P$. Then,
  \begin{align}
    V_t^{\MPC_k}(x_t; w_{0:t+k-1})
    & = x_t^\top Q x_t + u_t^\top R u_t + (A x_t + B u_t + w_t)^\top P (A x_t + B u_t + w_t) \notag \\
    & \quad + (A x_t + B u_t + w_t)^\top v_{t+1} + q_{t+1} \notag \\
    & = u_t^\top (R + B^\top P B) u_t + 2 u_t^\top B^\top (P A x_t + P w_t + v_{t+1}/2) \notag \\
    & \quad + x_t^\top Q x_t + (A x_t + w_t)^\top P (A x_t + w_t) + (A x_t + w_t)^\top v_{t+1} + q_{t+1}. \label{eq:V_t_with_u}
  \end{align}
  Let $F = A - HPA$. Plugging in the formula of $u_t$ in \Cref{thm:mpc_policy}, we have
  \begin{align}
    V_t^{\MPC_k}(x_t; w_{0:t+k-1})
    & = \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right)^\top H \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right) \notag \\
    & \quad - \left(P A x_t + P w_t + \frac{1}{2} v_{t+1}\right)^\top H \left(P A x_t + P w_t + \frac{1}{2} v_{t+1}\right) \notag \\
    & \quad + x_t^\top Q x_t + (A x_t + w_t)^\top P (A x_t + w_t) + (A x_t + w_t)^\top v_{t+1} + q_{t+1} \notag \\
    & = x_t^\top (Q + A^\top P A - A^\top PHPA) x_t + x_t^\top ({F^\top}v_{t+1} + 2{F^\top} P w_t) \notag \\
    & \quad + \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right)^\top H \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right) \notag \\
    & \quad - \left(P w_t + \frac{1}{2} v_{t+1}\right)^\top H \left(P w_t + \frac{1}{2} v_{t+1}\right) + w_t^\top P w_t + w_t^\top v_{t+1} + q_{t+1} \notag \\
    & = x_t^\top P x_t + x_t^\top v_t + q_t. \notag
  \end{align}
  Thus,
  \[v_t = {F^\top} v_{t+1} + 2{F^\top} P w_t = 2 \sum_{i=0}^\infty {F^\top}^{i+1} P w_{t+i}.\]
  Then, we can plug $v_{t+1}$ into $q_t$:
  \begin{align}
    q_t & = q_{t+1} + \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right) \notag \\
    & \quad - \left(\sum_{i=0}^\infty {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=0}^\infty {F^\top}^i P w_{t+i}\right) + w_t^\top P w_t + 2 w_t^\top \left(\sum_{i=1}^\infty {F^\top}^i P w_{t+i}\right). \label{eq:mpc_cost_per_step}
  \end{align}
  Note that \Cref{eq:mpc_cost_per_step} is for MPC with $k$ predictions. With the disturbance sequence $\{w_t\}$ fixed, we can compare the per-step cost of MPC with $k$ predictions and that with $k + 1$ predictions:
  \begin{align}
    q_t^k - q_t^{k+1}
    & = q_{t+1}^k - q_{t+1}^{k+1} + \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right) \notag \\
    & \quad - \left(\sum_{i=k+1}^\infty {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=k+1}^\infty {F^\top}^i P w_{t+i}\right) \notag \\
    & = q_{t+1}^k - q_{t+1}^{k+1} + w_{t+k}^\top P F^k H {F^\top}^k \left(P w_{t+k} + 2\sum_{i=1}^\infty {F^\top}^i P w_{t+i+k}\right). \label{eq:mpc_2diff}
  \end{align}
  Thus,
  \begin{align}
    & \!\!\! \bE{q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1})}
    = \bE{w_{t+k}^\top P F^k H {F^\top}^k \left(P w_{t+k} + 2\sum_{i=1}^\infty {F^\top}^i P w_{t+i+k}\right)} \notag \\
    & = \Tr{P F^k H {F^\top}^k \left(P \bE{w_{t+k} w_{t+k}^\top} + 2\sum_{i=1}^\infty {F^\top}^i P \bE{w_{t+i+k} w_{t+k}^\top}\right)} \notag \\
    & = \Tr{P F^k H {F^\top}^k Z_{k, t}}, \notag
  \end{align}
  where $Z_{k, t} = P \bE{w_{t+k} w_{t+k}^\top} + 2\sum_{i=1}^\infty {F^\top}^i P \bE{w_{t+i+k} w_{t+k}^\top}$. Note that $Z_{k,t} = Z_{k-1,t+1}$.

  \begin{align*}
    \MPCS_k - \MPCS_{k+1}
    & = \lim_{T \to \infty} \frac{1}{T} \bE{q_0^k - q_0^{k+1}} \\
    & = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \Tr{P F^k H {F^\top}^k Z_{k, t}} \\
    & \le \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \norm{P} \norm{H} \norm{F^k}^2 \Tr{Z_{k, t}},
  \end{align*}
  where in the last line we use the fact that if $A$ is symmetric, then $\Tr{AB} \le \norm{A} \Tr{B}$. Similarly to the last part in the proof of \Cref{thm:sto_pred_diff}, now we just need to show the last term $\Tr{Z_{k,t}}$ is uniformly bounded for all $t$. Again, this is because the cross-correlation of each disturbance pair is uniformly bounded.
  \begin{align*}
    \Tr{Z_{k,t}}
    & \le \norm{P} \Tr\bE{w_{t+k} w_{t+k}^\top} + 2 \sum_{i=1}^\infty \norm{P} \norm{F^i} \bEE \!\Bigg[\sum_j \sigma_j(w_{t+i+k} w_{t+k}^\top)\Bigg] \\
    & \le \norm{P} m + 2 \sum_{i=1}^\infty c \lambda^i \norm{P} m = \norm{P} m + 2 c \frac{\lambda}{1 - \lambda} \norm{P} m
  \end{align*}
  where $c$ is some constant, and in the first line, we use the fact that $\Tr{AB} \le \norm{A} \sum_j \sigma_j(B)$ with $\sigma_j(\cdot)$ denoting the $j$-th singular value. Thus, $\Tr{Z_{k,t}}$ is uniformly bounded. Therefore, $\MPCS_k - \MPCS_{k+1} = O(\|F^k\|^2)$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:regret_mpcs}}
\textit{$Reg^S(\MPC_k) = \mpcs_k^T - \sto_T^T = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$, where the second term results from the difference between finite/infinite horizons.}

\begin{proof}

  To calculate the dynamic regret, we cannot simply let $T - t \to \infty$ as we did before \Cref{eq:V_t_with_u} in the proof of \Cref{thm:mpcs_diff} and instead need to handle the expressions in a more delicate manner. In particular, we need to rigorously analyze the impact of finite horizon.
  Let $\Delta_t = P_t - P$.
  \begin{align*}
    & V_t^{\MPC_k}(x_t; w_{0:t+k-1}) \\
    & = u_t^\top (R + B^\top P_{t+1} B) u_t + 2 u_t^\top B^\top (P_{t+1} A x_t + P_{t+1} w_t + v_{t+1}/2) \\
    & \quad + x_t^\top Q x_t + (A x_t + w_t)^\top P_{t+1} (A x_t + w_t) + (A x_t + w_t)^\top v_{t+1} + q_{t+1} \\
    & = u_t^\top (R + B^\top P B) u_t + 2 u_t^\top B^\top (P A x_t + P w_t + v_{t+1}/2) \\
    & \quad + x_t^\top Q x_t + (A x_t + w_t)^\top P (A x_t + w_t) + (A x_t + w_t)^\top v_{t+1} + q_{t+1} \\
    & \quad + u_t^\top B^\top \Delta_{t+1} B u_t + 2 u_t^\top B^\top \Delta_{t+1} (A x_t + w_t) + (A x_t + w_t)^\top \Delta_{t+1} (A x_t + w_t).
  \end{align*}
  Plugging in the MPC policy as in \Cref{thm:mpc_policy}, we have:
  \begin{align*}
    & V_t^{\MPC_k}(x_t; w_{0:t+k-1}) \\
    & = x_t^\top (Q + A^\top P A - A^\top PHPA) x_t + x_t^\top ({F^\top}v_{t+1} + 2{F^\top} P w_t) \\
    & \quad + \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right)^\top H \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right) \\
    & \quad - \left(P w_t + \frac{1}{2} v_{t+1}\right)^\top H \left(P w_t + \frac{1}{2} v_{t+1}\right) + w_t^\top P w_t + w_t^\top v_{t+1} + q_{t+1} \\
    & \quad + \left(F x_t + w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right)^\top \Delta_{t+1} \left(F x_t + w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right) \\
    & = x_t^\top (Q + A^\top P A - A^\top PHPA + F^\top \Delta_{t+1} F) x_t \\
    & \quad + x_t^\top \left({F^\top}v_{t+1} + 2{F^\top} P w_t + 2 F^\top \Delta_{t+1}\left(w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right)\right) \\
    & \quad + \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right)^\top H \left(\frac{1}{2} v_{t+1} - \sum_{i=1}^{k-1} {F^\top}^i P w_{t+i}\right) \\
    & \quad - \left(P w_t + \frac{1}{2} v_{t+1}\right)^\top H \left(P w_t + \frac{1}{2} v_{t+1}\right) + w_t^\top P w_t + w_t^\top v_{t+1} + q_{t+1} \\
    & \quad + \left(w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right)^\top \Delta_{t+1} \left(w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right)
  \end{align*}
  Comparing this with the induction hypothesis $V_t^{\MPC_k} = x_t^\top (P + \Delta_t) x_t + x_t^\top v_t + q_t$, we obtain the recursive formulae for $\Delta_t, v_t, q_t$.
  \[\Delta_t = F^\top \Delta_{t+1} F = {F^\top}^{T-t} \Delta_T F^{T-t} = {F^\top}^{T-t} (\Qf - P) F^{T-t}.\]
  This implies that $P_t$ converges to $P$ exponentially fast, i.e., $\norm{\Delta_t} = O(\|F^{T-t}\|^2) = O(\lambda^{2(T-t)})$.
  \begin{align*}
    v_t & = {F^\top}v_{t+1} + 2{F^\top} P w_t + 2 F^\top \Delta_{t+1} \left(w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right) \\
    & = 2 \sum_{j=0}^{T-t-1} \left({F^\top}^{j+1} P w_{t+j} + {F^\top}^{j+1} \Delta_{t+j+1} \left(w_{t+j} - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+j+i}\right)\right) \\
    & = 2 \sum_{i=0}^{T-t-1} {F^\top}^{i+1} P w_{t+i} + 2 \sum_{j=0}^{T-t-1} {F^\top}^{j+1} \Delta_{t+j+1} \left(w_{t+j} - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+j+i}\right).
  \end{align*}
  Denote the second term by $2 d_t$. We have
  \begin{align*}
    d_t & = \sum_{j=0}^{T-t-1} {F^\top}^{j+1} \Delta_{t+j+1} \left(w_{t+j} - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+j+i}\right) \\
    & = \sum_{j=0}^{T-t-1} O(\lambda^j \lambda^{2(T-t-j)})
    = O(\lambda^{T-t}).
  \end{align*}
  \begin{align}
    d_t^k - d_t^{k+1}
    & = \sum_{j=0}^{T-t-k-1} {F^\top}^{j+1} \Delta_{t+j+1} {F^\top}^k P w_{t+j+k} \label{eq:d^k-d^k+1} \\
    & = \sum_{j=0}^{T-t-k-1} O(\lambda^j \lambda^{2(T-t-j)} \|F^k\|)
    = O(\lambda^{T-t+k} \|F^k\|). \notag
  \end{align}
  \iffalse
  \begin{align*}
    v_t & = {F^\top}v_{t+1} + 2{F^\top} P w_t + 2 F^\top \Delta_{t+1}\left(w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right) \\
    & = {F^\top}v_{t+1} + 2{F^\top} P w_t + O(\lambda^{2(T-t)}) \\
    & = 2 \sum_{i=0}^{T-t-1} \left({F^\top}^{i+1} P w_{t+i} + O(\lambda^{2T-2t-i})\right) \\
    & = 2 \sum_{i=0}^{T-t-1} {F^\top}^{i+1} P w_{t+i} + 2 O(\lambda^{T-t}).
  \end{align*}
  We denote the residual term in the Big-Oh notation in the last line by:
  \[d_t = \sum_{i=0}^{T-t-1} F^\top \Delta_{t+1} \left(w_t - \sum_{i=0}^{k-1} {F^\top}^i P w_{t+i}\right).\]
  \fi

  Finally, we have a formula for $q_t$ that parallels \Cref{eq:mpc_cost_per_step}:
  \begin{align*}
    q_t & = q_{t+1} + \left(d_{t+1} + \sum_{i=k}^{T-t-1} {F^\top}^i P w_{t+i}\right)^\top H \left(d_{t+1} + \sum_{i=k}^{T-t-1} {F^\top}^i P w_{t+i}\right) \notag \\
    & \quad - \left(d_{t+1} + \sum_{i=0}^{T-t-1} {F^\top}^i P w_{t+i}\right)^\top H \left(d_{t+1} + \sum_{i=0}^{T-t-1} {F^\top}^i P w_{t+i}\right) \\
    & \quad + w_t^\top P w_t + 2 w_t^\top \left(d_{t+1} + \sum_{i=1}^{T-t-1} {F^\top}^i P w_{t+i}\right).
  \end{align*}
  \iffalse
  \begin{align*}
    q_t & = q_{t+1} + O(\lambda^{T-t}) + \left(\sum_{i=k}^{T-t-1} {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=k}^{T-t-1} {F^\top}^i P w_{t+i}\right) \notag \\
    & \quad - \left(\sum_{i=0}^{T-t-1} {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=0}^{T-t-1} {F^\top}^i P w_{t+i}\right) + w_t^\top P w_t + 2 w_t^\top \left(\sum_{i=1}^{T-t-1} {F^\top}^i P w_{t+i}\right),
  \end{align*}
  \fi
  Taking the difference between $k$ and $k+1$ predictions, we have
  \begin{align}
    & q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1}) \notag \\
    & = (w_{t+k}^\top P F^k + (d_{t+1}^k - d_{t+1}^{k+1})^\top) H \left(d_{t+1}^k + d_{t+1}^{k+1} + {F^\top}^k P w_{t+k} + 2\sum_{i=1}^{T-t-k-1} {F^\top}^{i+k} P w_{t+i+k}\right) \label{eq:mpc_2diff_with_res} \\
    & = (w_{t+k}^\top P F^k + O(\lambda^{T-t} \|F^k\|)) H \left(O(\lambda^{T-t}) + {F^\top}^k P w_{t+k} + 2\sum_{i=1}^{T-t-k-1} {F^\top}^{i+k} P w_{t+i+k}\right), \notag
  \end{align}
  \iffalse
  \begin{align}
    q_t^k - q_t^{k+1}
    & = q_{t+1}^k - q_{t+1}^{k+1} + w_{t+k}^\top P F^k H {F^\top}^k \left(P w_{t+k} + 2\sum_{i=1}^{T-t-k-1} {F^\top}^i P w_{t+i+k}\right) + O(\lambda^{T-t}). \label{eq:mpc_2diff_with_res}
  \end{align}
  \fi
  and thus
  \begin{align*}
    \bE{q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1})}
    & = O(\|F^k\| (\lambda^{T-t} + \|F^k\|)).
  \end{align*}
  \iffalse
  \begin{align*}
    \bE{q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1})}
    & = \Tr{P F^k H {F^\top}^k Z_{k, t}} + O(\lambda^{T-t}),
  \end{align*}
  where $Z_{k,t}$ is bounded by some constant.
  Therefore,
  \begin{align*}
    Reg^S(\MPC_k) = \bEE J^{\MPC_k} - \bEE J^{\MPC_T}
    & = \bE{q_0^k - q_0^T} \\
    & = \sum_{t=0}^{T-1} \bE{q_t^k - q_t^{k+1} - q_{t+1}^k + q_{t+1}^{k+1}} \\
    & = \sum_{t=0}^{T-1} \Tr{P F^k H {F^\top}^k Z_{k, t}} + \sum_{t=0}^{T-1} O(\lambda^{T-t}) \\
    & = O(\lambda^{2k} T + 1).
  \end{align*}
  \fi
  \begin{align*}
    \bE{q_0^k - q_0^T}
    & = \sum_{t=0}^{T-1} \bE{q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1})} \\
    & = \sum_{t=0}^{T-1} O(\|F^k\| (\lambda^{T-t} + \|F^k\|)) \\
    & = O(\|F^k\|^2 T + \|F^k\|).
  \end{align*}
  \[\bE{v_0^k - v_0^T} = 2 (d_0^k - d_0^T) = O(\lambda^{T+k} \|F^k\|).\]

  \begin{align}
    \bEE J^{\MPC_k} - \bEE J^{\MPC_T}
    & = \bE{V_0^k(x_0) - V_0^T(x_0)} \notag \\
    & = \bE{x_0^\top (v_0^k - v_0^T) + (q_0^k + q_0^T)} \notag \\
    & = O(\|F^k\|^2 T + \|F^k\|). \label{eq:MPC_k-MPC_T}
  \end{align}
  By definition, $J^{\MPC_T}$ is the cost of MPC policy given all future disturbances before making any decisions. It almost equals to $\min_u J$, the optimal policy given all future disturbances, except that during optimization, MPC assumes the final-step cost to be $x_T^\top P x_T$ instead of $x_T^\top \Qf x_T$. This will incur at most constant extra cost, i.e.,
  \begin{equation}
    J^{\MPC_T} - \min_u J = O(P - \Qf) = O(1). \label{eq:MPC_T-minJ}
  \end{equation}
  By \Cref{eq:MPC_k-MPC_T,eq:MPC_T-minJ},
  \[Reg^S(\MPC_k) = \bEE J^{\MPC_k} - \bEE \min_u J = O(\|F^k\|^2 T + \|F^k\| + 1) = O(\|F^k\|^2 T + 1).\]

  \iffalse
  Since $P_t$ converges to $P$ exponentially fast \ck{cannot find a rigorous proof}, we suppose $\norm{P_t - P} \le c \eta^{T-t}$ where $c$ and $\eta < 1$ are constants. Let $F = HPA$.
  \begin{align*}
    v_t & = (F^\top + O(\eta^{T-t})) \bE[w_{t+k}]{v_{t+1}} + 2 (F^\top P + O(\eta^{T-t})) w_t, \\
    \begin{split}
      q_t & = w_t^\top (P - P H P + O(\eta^{T-t})) w_t + w_t^\top (I - P H + O(\eta^{T-t})) \bE[w_{t+k}]{v_{t+1}} \\
      & \quad - \frac{1}{4} \bE[w_{t+k}]{v_{t+1}}^\top (H + O(\eta^{T-t})) \bE[w_{t+k}]{v_{t+1}} + \bE[w_{t+k}]{q_{t+1}}.
    \end{split}
  \end{align*}
  \[\sum_{j=0}^i O(\eta^{T-t-j}) = O(\eta^{T-t-i} / (1 - \eta)) = O(\eta^{T-t-i})\]
  \begin{align*}
    v^k_t & = 2 \sum_{i=0}^{k-1} \prod_{j=0}^i ({F^\top} + O(\eta^{T-t-j})) (P + O(\eta^{T-t-i})) w_{t+i} \\
    & \quad + 2 \sum_{i=k}^\infty {F^\top}^{i+1} P \mu_{t+i|t+k-1} ...... \\
    & = 2 \sum_{i=0}^{k-1} ({F^\top}^{i+1} P + O(\eta^{T-t-i})) w_{t+i} + 2 \sum_{i=k}^\infty ({F^\top}^{i+1} P + O(\eta^{T-t-i})) \mu_{t+i|t+k-1} \\
    q^k_t & = w_t^\top (P - PHP) w_t + w_t^\top (I - PH) \bE[w_{t+k}]{v^k_{t+1}} - \frac{1}{4} \bE[w_{t+k}]{v^k_{t+1}}^\top H \bE[w_{t+k}]{v^k_{t+1}} + \bE[w_{t+k}]{q^k_{t+1}}, \notag
  \end{align*}

  $\sum_{t=0}^T O(\eta^{T-t}) = O(1)$.

  \[P_t = Q + A^\top P_{t+1} A - A^\top P_{t+1} H_t P_{t+1} A,\]

  In \Cref{eq:mpc_cost_per_step}, we derive the per-step MPC cost with $k$ predictions. We now compare it to that with infinite predictions.
  \begin{align*}
    q_t^k - q_t^\infty
    & = q_{t+1}^k - q_{t+1}^\infty + \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right) \\
    & = q_{t+1}^k - q_{t+1}^\infty + \left(\sum_{i=0}^\infty {F^\top}^i P w_{t+k+i}\right)^\top F^k H {F^\top}^k \left(\sum_{i=0}^\infty {F^\top}^i P w_{t+k+i}\right).
  \end{align*}

  \[Reg^S(\MPC_k) = \mpcs^T_k - \mpcs^T_\infty = \bE{q_0^k - q_0^\infty} \]
  \fi
\end{proof}

\subsection{Proof of Theorem~\ref{thm:regret_sto}}
\textit{The optimal dynamic regret ${Reg_k^S}^* = \sto_k^T - \sto_T^T = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$ and there exist $A$, $B$, $Q$, $R$, $\Qf$, $x_0$, and $\cW$ such that
  ${Reg_k^S}^* = \Theta(\|F^k\|^2 (T - k))$.}

\begin{proof}
  The first part follows from \Cref{thm:regret_mpcs} and that fact that ${Reg_k^S}^* \le Reg^S(\MPC_k)$.

  The second part is shown by \Cref{ex:exp_speed}, i.e., suppose $n = d = 1$ and the disturbance are i.i.d.\ and zero-mean. Additionally, let $\Qf = P$ and $x_0 = 0$. In this case, MPC has not only the same policy but also the same cost as the optimal control policy. Also, $P_t = P$ for all $t$. To calculate the total cost, we follow the approach used in the proof of \Cref{thm:iid_pred}. Since $T$ is finite now, we have a similar (to \Cref{eq:v_t}) but different form of $v_t$:
  \[v_t = 2 \sum_{i=0}^{\min\{k-1, T-t-1\}} {F^\top}^{i+1} P w_{t+i}.\]
  Thus,
  \[\bE{q_t} = \Tr{\left(P - \sum_{i=0}^{\min\{k-1,T-t-1\}} P F^i H {F^\top}^i P\right) W} + \bE{q_{t+1}}.\]
  \[\bE{q_0} = \Tr{\sum_{t=0}^{T-1} \left(P - \sum_{i=0}^{\min\{k-1,T-t-1\}} P F^i H {F^\top}^i P\right) W}.\]
  Let $q_t^k$ denote $q_t$ in the scenario of $k$ predictions.
  \begin{align*}
    {Reg^S}^* = \bE{q_0^k - q_0^T}
    & = \Tr{\sum_{t=0}^{T-k-1} \sum_{i=k}^{T-t-1} P F^i H {F^\top}^i P W} \\
    & \ge (T - k) \Tr{P F^k H {F^\top}^k P W} = \Omega(\|F^k\|^2 (T - k)).
  \end{align*}
  On the other hand,
  \[{Reg^S}^* = \bE{q_0^k - q_0^T}
    \le (T - k) \Tr{\sum_{i=k}^\infty P F^i H {F^\top}^i P W}
    = O(\|F^k\|^2 (T - k)).\]
  Therefore, ${Reg^S}^* = \Theta(\|F^k\|^2 (T - k))$.

  \iffalse
  For the second part, let $A = B = R = 1$, $Q = \nicefrac{1}{2}$ and $\Qf = 0$. Then, $P = 1$ and $P_{T-i} = 1 - \frac{3}{4^i + 2}$.

  $H_t \ge B R B^\top$. $F_t = A - A P_{t+1} H_t \le $

  $F = \nicefrac{1}{2}$. $F_{T-i} = \frac{4^i + 2}{}$
  \[v_{T-i} = \]
  \[q_{T-i} = \]

  parallels \Cref{eq:E[q_t]}:
  \begin{align*}
    \bE{q_t}
    & = \Tr{\left(P_{t+1} - \sum_{i=0}^{k-1} P_{t+i+1} \prod_{j=i\downarrow}^1 F_{t+j} H_t \prod_{j=1}^i F_{t+j}^\top P_{t+i+1}\right) W} + \bE{q_{t+1}},
  \end{align*}
  where the product of matrices is from left to right and notation $\downarrow$ means decreasing index.
  Thus,
  \[\bE{q_0} = \Tr{\sum_{t=0}^{T-1} \left(P_{t+1} - \sum_{i=0}^{k-1} P_{t+i+1} \prod_{j=i\downarrow}^1 F_{t+j} H_t \prod_{j=1}^i F_{t+j}^\top P_{t+i+1}\right) W}\]
  \[{Reg^S}^* = \bE{q_0^k - q_0^T} = \Tr{\sum_{t=0}^{T-1} \sum_{i=k}^{T-t-1} P_{t+i+1} \prod_{j=i\downarrow}^1 F_{t+j} H_t \prod_{j=1}^i F_{t+j}^\top P_{t+i+1} W}\]

  It suffices to show that even when $\|F^k\|^2 T$ is arbitrarily small, ${Reg^S}^*$ is lower-bounded by a constant.
  Let $k = T - 1$ and $T \to \infty$.

  \[{Reg^S}^* = \Tr{P_T F_{T-1} \cdots F_1 H_0 F_1^\top \cdots F_{T-1}^\top P_T W}\]

  \fi
\end{proof}

\section{Proofs of Section~\ref{sec:adv}}

\subsection{Proof of Theorem~\ref{thm:adv_pred_diff}}
\textit{For $k \ge 1$, $\ADV_k - \ADV_{k+1} = O(\|F^k\|^2) =  O(\lambda^{2k})$.}

\begin{proof}
  This proof is based on \Cref{thm:mpca_diff}. It turns out that the behavior of the MPC policy and its cost is easier to analyze than the optimal one, especially in the adversarial setting.
  \[\ADV_k - \ADV_{k+1} \le \ADV_k - \ADV_\infty \le \MPCA_k - \ADV_\infty = \sum_{i = k}^\infty \MPCA_i - \MPCA_{i+1}.\]
  By \Cref{thm:mpca_diff},
  \[\MPCA_i - \MPCA_{i+1}
    \le O\left(\norm{F^i}^2\right)
    \le O\left(\norm{F^k}^2 \norm{F^{i-k}}^2\right)
    \le O\left(\norm{F^k}^2 \lambda^{2(i-k)}\right).\]
  Thus,
  \[\ADV_k - \ADV_{k+1} \le O\left(\norm{F^k}^2 \sum_{i=k}^\infty \lambda^{2(i-k)}\right) = O(\|F^k\|^2).\]
\end{proof}

\subsection{Proof of Example~\ref{ex:adv_finite_pred}}
\textit{Let $A = B = Q = R = 1$ and $\Omega = [-1, 1]$. In this case, one prediction is enough to leverage the full power of prediction. Formally, we have $\ADV_1 = \ADV_\infty = 1$. In other words, for all $k \ge 1$, $\ADV_k = 1$. The optimal control policy (as $T \to \infty$) is a piecewise function:
  \[u^*(x, w) = \begin{cases}
    -(x+w) &, -1 \le x+w \le 1 \\
    -(x+w) + \frac{3 - \sqrt{5}}{2} (x+w-1) &, x+w > 1 \\
    -(x+w) + \frac{3 - \sqrt{5}}{2} (x+w+1) &, x+w < -1
  \end{cases}.\]

  The proof leverages two different cost-to-go functions for the $\min$ player and the $\sup$ player.}

\begin{proof}
  We will show $\ADV_1 = 1$ and $\ADV_\infty = 1$ separately.
  The system dynamics is given by $x_{t+1} = x_t + u_t + w_t$ with $w_t \in [-1, 1]$ and
  \[\adv_1^T = \max_{w_0} \min_{u_0} \cdots \max_{w_{T-1}} \min_{u_{T-1}} \sum_{t=0}^{T-1} (x_t^2 + u_t^2) + x_T^2.\]
  We will calculate the results of each $\min$ and $\max$ by dynamical programming.
  In particular, we will define two cost-to-go functions for the $\min$ player and the $\max$ player respectively.
  Let $z_t = x_t + w_t$. Then, $z_t$ can be regarded as the disturbed state. This is natural since the controller has one prediction and decides $u_t$ after knowing $w_t$. Thus, the system dynamics can be split into two stages: $z_t = x_t + w_t$ and $x_{t+1} = z_t + u_t$. Let
  \begin{align*}
    f_t(z_t)
    & = \min_{u_t} \max_{w_{t+1}} \min_{u_{t+1}} \cdots \max_{w_{T-1}} \min_{u_{T-1}} \sum_{i=t}^{T-1} (u_i^2 + x_{i+1}^2) \\
    & = \min_{u_t} \left( u_t^2 + (z_t + u_t)^2 + g_{t+1}(z_t + u_t) \right), \\
    g_t(x_t)
    & = \max_{w_t} \min_{u_t} \cdots \max_{w_{T-1}} \min_{u_{T-1}} \sum_{i=t}^{T-1} (u_i^2 + x_{i+1}^2) \\
    & = \max_{w_t} f_t(x_t + w_t).
  \end{align*}
  For $t = T - 1$, we have
  \begin{align*}
    f_{T-1}(z) & = \min_u u^2 + (z + u)^2 = \frac{z^2}{2}, \\
    g_{T-1}(x) & = \max_w \frac{(x + w)^2}{2} = \frac{(|x| + 1)^2}{2}.
  \end{align*}
  We will prove by backward induction that $g_t(x) = a_t x^2 + 2 b_t \abs{x} + c_t$ where $a_t, b_t, c_t$ are some coefficients with $0 < b_t < 1$. Assuming this is true at $t$, we will show this is true at $t - 1$.
  \begin{align*}
    f_{t-1}(z) & = \min_u \left(u^2 + (z + u)^2 + g_t(z + u)\right) \\
    & = \min_y \left((y-z)^2 + y^2 + g_t(y)\right) \\
    & = \min_y \left((y-z)^2 + y^2 + a_t y^2 + 2 b_t |y| + c_t\right) \\
    & = \min_y \left((a_t + 2) y^2 - 2 (z - b_t \sign(y)) y + z^2 + c_t\right),
  \end{align*}
  where $y = z + u = x + w + u$ is the state after the control policy is applied.

  Let function $y(z)$ map from the disturbed old state to the new state. The optimal $y$ is given by:
  \begin{align}
    y^*(z)
    & = {\arg\min}_y \left((a_t + 2) y^2 - 2 (z - b_t \sign(y)) y + z^2 + c_t\right) \notag \\
    & = \begin{cases}
    0 &, -b_t \le z \le b_t \\
    \frac{z - b_t \sign(z)}{a_t + 2} &, \text{ otherwise}
    \end{cases}. \label{eq:state_mapping}
  \end{align}
  Thus, for $z < -b_t$ or $z > b_t$, we have
  \begin{align*}
    f_{t-1}(z) & = -\frac{(z - b_t \sign(z))^2}{a_t + 2} + z^2 + c_t \\
    & = -\frac{z^2 - 2 b_t \abs{z} + b_t^2}{a_t + 2} + z^2 + c_t \\
    & = \frac{a_t + 1}{a_t + 2} z^2 + \frac{2 b_t}{a_t + 2} |z| + c_t - \frac{b_t^2}{a_t + 2}.
  \end{align*}
  For $z \in [-b_t, b_t]$, the value of $f_t(z)$ is not needed in the calculation of $g_t(x)$ because $0 < b_t < 1$ (induction hypothesis) and the adversary --- who wants to maximize $f_t(z_t)$, a convex, even function --- will never choose $w_t$ such that $z_t = x_t + w_t \in (-1, 1)$ since $w_t$ can be chosen from $[-1,1]$.
  \begin{align*}
    g_{t-1}(x)
    & = \max_w f_t(x + w) = f_t(x + \sign(x)) \\
    & = \frac{a_t + 1}{a_t + 2} (x^2 + 2 |x| + 1) + \frac{2 b_t}{a_t + 2} (|x| + 1) + c_t - \frac{b_t^2}{a_t + 2} \\
    & = \frac{a_t + 1}{a_t + 2} x^2 + \frac{2 (a_t + b_t + 1)}{a_t + 2} |x| + c_t + \frac{a_t + 1 + 2 b_t - b_t^2}{a_t + 2} \\
    & = a_{t-1} x^2 + 2 b_{t-1} |x| + c_{t-1}.
  \end{align*}
  Now, we have obtained the recursive formulae for $a_t, b_t, c_t$. The initial values are $a_{T-1} = b_{T-1} = c_{T-1} = \nicefrac{1}{2}$.

  Let $\ff_i$ be the $i$-th Fibonacci number with $\ff_0 = 0, \ff_1 = 1$. Then, $a_{T-i} = \ff_{i+1} / \ff_{i+2}$. As $i \to \infty$, $a_{T - i} \to \frac{\sqrt{5} - 1}{2}$.

  For $b_t$, we have $1 - b_{T-(i+1)} = (1 - b_{T-i}) / (a_{T-i} + 2)$. When $i$ is large, $1 - b_{T-i}$ approaches $0$ but is always positive. Thus, $b_{T-i}$ approaches $1$ but is always less than $1$.

  For $c_t$, we have
  \[c_{T-(i+1)} = c_{T-i} + 1 - \frac{(1 - b_{T-i})^2}{a_{T-i} + 2}\]
  and thus $c_{T-(i+1)} - c_{T-i} \to 1$. Therefore, $\ADV_1 = 1$.

  The optimal control policy is obtained by plugging the above values back into \Cref{eq:state_mapping}:
  \[u^*(x, w) = - (x + w) + y^*(x + w) = - (x + w) + \begin{cases}
    0 &, -1 \le x + w \le 1 \\
    \frac{x + w - \sign(x + w)}{\frac{\sqrt{5} + 3}{2}} &, \text{ otherwise}
    \end{cases}.\]

  For $\ADV_\infty$, we will show that $\STO_\infty = 1$ at a specific disturbance sequence: $w_t = 1$ for all $t$. Because $\STO_\infty \le \ADV_\infty \le \ADV_1 = 1$, we know that $\ADV_\infty = 1$.

  According to \Cref{eq:q_t,eq:v_t} with $k \to \infty$,
  \[\STO_\infty = \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} (2 w_t \psi_t - P w_t^2 - H \psi_t^2) \text{ with } \psi_t = \sum_{i=0}^\infty F^i P w_{t+i}.\]
  Solving the Riccati equation, we have $P = \frac{1 + \sqrt{5}}{2},\ H = F = \frac{3 - \sqrt{5}}{2}$. When $w_t = 1$ for all $t$, $\STO_\infty = 1$.
\end{proof}

\subsection{Proof of Theorem~\ref{thm:mpca_diff}}
\textit{$\MPCA_k - \MPCA_{k+1} = O(\|F^k\|^2) = O(\lambda^{2k})$.}

\begin{proof}
  Note that \Cref{eq:mpc_2diff} in the proof of \Cref{thm:mpcs_diff} does not rely on the type of disturbance, i.e., \Cref{eq:mpc_2diff} holds for adversarial disturbance as well. Let $r = \sup_{w \in \Omega} \norm{w}_2$.

  \begin{align}
    q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1})
    & = w_{t+k}^\top P F^k H {F^\top}^k \left(P w_{t+k} + 2\sum_{i=1}^\infty {F^\top}^i P w_{t+i+k}\right) \notag \\
    & \le \norm{w_{t+k}} \norm{P} \norm{H} \norm{F^k}^2 \left(\norm{P} \norm{w_{t+k}} + 2 \sum_{i=1}^\infty \norm{F^i} \norm{P} \norm{w_{t+i+k}}\right) \notag \\
    & \le \norm{F^k}^2 \left(1 + 2 \sum_{i=1}^\infty \norm{F^i} \right) \norm{H} \norm{P}^2 r^2 \notag \\
    & \le \norm{F^k}^2 \left(1 + 2 \frac{c \lambda}{1 - \lambda} \right) \norm{H} \norm{P}^2 r^2 \notag
  \end{align}
  for some constant $c$.
  \begin{align*}
    \MPCA_k - \MPCA_{k+1}
    & = \lim_{T \to \infty} \frac{1}{T} (\max_w q_0^k - \max_w q_0^{k+1}) \\
    & \le \lim_{T \to \infty} \frac{1}{T} \max_w (q_0^k - q_0^{k+1}) \\
    & \le \lim_{T \to \infty} \frac{1}{T} \sum_{t=0}^{T-1} \max_w (q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1}) ) \\
    & \le \norm{F^k}^2 \left(1 + 2 \frac{c \lambda}{1 - \lambda} \right) \norm{H} \norm{P}^2 r^2 = O(\|F^k\|^2).
  \end{align*}
\end{proof}

\subsection{Proof of Theorem~\ref{thm:regret_mpca}}
\textit{$Reg^A(\MPC_k) = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$.}

\begin{proof}
  We follow the notations in the proof of \Cref{thm:regret_mpcs}. \Cref{eq:mpc_2diff_with_res} does not rely on the type of disturbance, so it holds for adversarial disturbance as well.
  By \Cref{eq:mpc_2diff_with_res} and the fact that $w_t$ is bounded, we have
  \[q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1}) = O(\|F^k\| (\lambda^{T-t} + \|F^k\|)),\]
  where the constant in the Big-Oh notation does not depend on the disturbance sequence $w$. Thus,
  \[\max_w (q_0^k - q_0^T) \le \sum_{t=0}^{T-1} \max_w (q_t^k - q_t^{k+1} - (q_{t+1}^k - q_{t+1}^{k+1}) ) = O(\|F^k\|^2 T + \|F^k\|).\]
  By \Cref{eq:d^k-d^k+1} and the boundedness of $w_t$,
  \[\max_w (v_0^k - v_0^T) = 2 \max_w (d_0^k - d_0^T) = O(\lambda^{T+k} \|F^k\|).\]
  \begin{align*}
    \max_w (J^{\MPC_k} - J^{\MPC_T}) = \max_w (V_0^k(x_0) - V_0^T(x_0))
    & \le \max_w (x_0^\top (v_0^k - v_0^T)) + \max_w (q_0^k - q_0^T) \\
    & = O(\|F^k\|^2 T + \|F^k\|).
  \end{align*}
  As \Cref{eq:MPC_T-minJ}, $J^{\MPC_T} - \min_u J = O(1)$. Thus,
  \begin{align*}
    Reg^A(\MPC_k) = \max_w (J^{\MPC_k} - \min_u J)
    & \le \max_w (J^{\MPC_k} - J^{MPC_T}) + \max_w (J^{\MPC_T} - \min_u J) \\
    & = O(\|F^k\|^2 T + \|F^k\| + 1) = O(\|F^k\|^2 T + 1).
  \end{align*}

  \iffalse
  Starting from \Cref{eq:mpc_2diff_with_res}, we perform similar steps as in \Cref{eq:mpca_2diff} and obtain:
  \[q_t^k - q_t^{k+1} - q_{t+1}^k + q_{t+1}^{k+1} = O(\|F^k\|^2 + \lambda^{T-t}),\]
  where the constant in the Big-Oh notation does not depend on the disturbance sequence $w$. Thus,
  \begin{align*}
    Reg^A(\MPC_k) = \max_w (J^{\MPC_k} - J^{\MPC_\infty})
    & = \max_w (q_0^k - q_0^\infty) \\
    & \le \sum_{t=0}^{T-1} \max_w (q_t^k - q_t^{k+1} - q_{t+1}^k + q_{t+1}^{k+1}) \\
    & = O(\|F^k\|^2 T + 1).
  \end{align*}
  \fi

  \iffalse
  Let $r = \sup_{w \in \Omega} \norm{w}_2$.
  In \Cref{eq:mpc_cost_per_step}, we derive the per-step MPC cost with $k$ predictions. We now compare this to the case with infinite predictions.
  \begin{align*}
    q_t^k - q_t^\infty
    & = q_{t+1}^k - q_{t+1}^\infty + \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right)^\top H \left(\sum_{i=k}^\infty {F^\top}^i P w_{t+i}\right) \\
    & = q_{t+1}^k - q_{t+1}^\infty + \left(\sum_{i=0}^\infty {F^\top}^i P w_{t+k+i}\right)^\top F^k H {F^\top}^k \left(\sum_{i=0}^\infty {F^\top}^i P w_{t+k+i}\right).
  \end{align*}
  \[\norm{\sum_{i=0}^\infty {F^\top}^i P w_{t+k+i}} \le \sum_{i=0}^\infty \norm{F^i} \norm{P} \norm{w_{t+k+i}} \le \frac{c}{1 - \lambda} \norm{P} r\]
  for some constant $c$. Thus,
  \[q_t^k - q_t^\infty - q_{t+1}^k + q_{t+1}^\infty \le \norm{F^k}^2 \norm{H} \frac{c^2}{(1 - \lambda)^2} \norm{P}^2 r^2.\]
  This result holds only when $T \to \infty$. For finite $T$, if $\Qf \ne P$, an extra $o(1)$ is needed. Thus,
  \begin{align}
    Reg_k^\MPC
    = \max_w (J^{\MPC_k} - \min_u J)
    & = \max_w (q_0^k - q_0^\infty) \notag \\
    & \le \sum_{t=0}^{T-1} \max_w (q_t^k - q_t^\infty - q_{t+1}^k + q_{t+1}^\infty) \notag \\
    & \le \norm{F^k}^2 \norm{H} \frac{c^2}{(1 - \lambda)^2} \norm{P}^2 r^2 T + o(T). \label{eq:o(T)}
  \end{align}

  To give a more precise analysis for that $o(T)$, we must go back to \Cref{eq:V_t_with_u}, where we were doing backward induction on $V_t$ assuming $T - t \to \infty$. For finite $T$, that equation is instead given by:
  \begin{align*}
    V_t(x_t; w_{t:T-1})
    & = u_t^\top (R + B^\top P_{t+1} B) u_t + 2 u_t^\top B^\top (P_{t+1} A x_t + P_{t+1} w_t + v_{t+1}/2) \notag \\
    & \quad + x_t^\top Q x_t + (A x_t + w_t)^\top P_{t+1} (A x_t + w_t) + (A x_t + w_t)^\top v_{t+1} + q_{t+1}.
  \end{align*}
  Plugging in $u_t$ in \Cref{thm:mpc_policy}, we can derive formulae for $P_t, v_t, q_t$ very similar to those in \Cref{eq:Pvq_mpc}. To avoid collision of notation, we denote the coefficients in \Cref{eq:Pvq_mpc} by $P_t', v_t', q_t'$. Of course, $P_t' = P$. Note that if $\Qf = P$, then \Cref{eq:Pvq_mpc} holds even for finite $T$.

  The results are: $P_t = P + \Delta P_t$ where $\Delta P_t = F^\top \Delta P_{t+1} F$, $v_t = v_t' + O(\norm{\Delta P_t})$, and $q_t - q_{t+1} = q_t' - q_{t+1}' + O(\norm{\Delta P_t})$. Note that $\norm{\Delta P_t} \le \norm{F^{T-t}}^2 \norm{\Delta P_T} = O(\lambda^{2(T-t)})$. Thus, $q_t - q_t' = O(\sum_{i=t}^{T-1} \norm{\Delta P_i}) = O(\sum_{i=t}^{T-1} \lambda^{2(T-i)}) = O(1)$. Therefore, the $o(T)$ that appears in \Cref{eq:o(T)} is actually $O(1)$. Thus, $Reg_k^\MPC = O(\norm{F^k}^2 T + 1)$.

  \guanya{$P_t$ exponentially converge to $P$ \cite{anderson2007optimal,anderson2012optimal}} \ck{MPC case turns out to be easier. It is not described by Riccati Difference Equation, but an easier equation.}
  \fi
\end{proof}

\subsection{Proof of Theorem~\ref{thm:regret_adv}}
\textit{${Reg^A_k}^* = O(\|F^k\|^2 T + 1) = O(\lambda^{2k} T + 1)$.
  Moreover, there exist $A$, $B$, $Q$, $R$, $\Qf$, $x_0$, and $\Omega$ such that ${Reg^A_k}^* = \Omega(\|F^k\|^2 (T - k))$.}

\begin{proof}
  The first part of the theorem follows from \Cref{thm:regret_mpca} and the fact that ${Reg_k^A}^* \le Reg^A(\MPC_k)$.

  We reduce the second part of this theorem to the second part of \Cref{thm:regret_sto}. Since the proof of \Cref{thm:regret_sto} works for any fixed distribution of $w_t$ (with finite second moment), we can restrict that distribution to have bounded support. Denote this bounded support by $\Omega$. Then, we have
  \begin{align*}
    {Reg^A_k}^*
    & = \sup_{w_0, \cdots, w_{k-1}} \min_{u_0} \sup_{w_k} \cdots \min_{u_{T-k-1}} \sup_{w_{T-1}} \min_{u_{T-k}, \cdots, u_{T-1}} \Big(J(u, w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big) \\
    & \ge \bEE[w_0, \cdots, w_{k-1}] \min_{u_0} \bEE[w_k] \cdots \min_{u_{T-k-1}} \bEE[w_{T-1}] \min_{u_{T-k}, \cdots, u_{T-1}} \Big(J(u, w) - \min_{u'_0, \dots, u'_{T-1}} J(u', w)\Big) \\
    & = {Reg^S_k}^* = \Theta(\|F^k\|^2 (T - k)).
  \end{align*}
\end{proof}

\end{document}


TITLE: Book after Kreyszig Functional Analysis
QUESTION [2 upvotes]: I have finished the book Introductory Functional Analysis by Erwin Kreyszig and enjoyed it a lot. Wonderful book, but I feel that

This book did not give knowledge about $L^p$ spaces and Euclidean spaces.
I want to read more and modern book on normed spaces
I want to study applicable functional analysis

REPLY [1 votes]: I would recommend

H. Brezis, Functional Analysis, Sobolev spaces and Partial Differential Equations.


TITLE: Finding an inner product given a norm
QUESTION [1 upvotes]: Let $V=\mathbb{R}^n$. Given a norm $|\cdot |$, find the inner product for which $\langle v,v\rangle=|v|$.
So basically I need to find an inner product such that $\forall v\in V. \langle v,v\rangle=1$, right? How do I do that?
I was also given a hint: "Find a way to write $\langle u,v\rangle$ as a function of norms." I think they mean $\langle u,v\rangle= \dfrac{|u+v|^2-|u|-|v|}{2}$?

REPLY [1 votes]: The parallelogram law says for a norm from an inner product, $2 || x||^2 + 2 ||y||^2 = ||x-y||^2 + ||x+y||^2$.
You can get from this the polarization identity $$\langle x,y\rangle = \frac{||x+y||^2-||x-y||^2}{4}$$


TITLE: A map that is injective but not a homemorphism onto its image
QUESTION [0 upvotes]: How I have to show that the map $\sigma: \mathbb{R} \to \mathbb{R}^2$ such that
$\sigma(t)=(\frac{t}{1+t^4},\frac{t}{1+t^2})$ is injective but not an homeomorphism onto its image?

REPLY [2 votes]: Method 1. In $\mathbb R$ the set $\mathbb Z$ \  $\{0\}$ is closed but in the image space $S=\{\sigma (t):t\in \mathbb R\}$ the set  $\{\sigma (n): n\in \mathbb Z$ \ $\{0\}\}$ is not closed. The point $(0,0)=\sigma (0)$ is in its closure.
Method 2. $S$ is not homeomorphic to $\mathbb R$. For if $U$ is a connected open subset of $\mathbb R$ then  $\partial U$ contains at most $2$ points. But $S$ \ $\{\sigma (t): 1\leq t\leq 2 \lor -2\leq t\leq -1\}$ is connected and open in $S$ and has $4$ boundary points.
Remark: Observe that $S$ is homeomorphic to the shape of the numeral $8.$


TITLE: If C-14 has a half-life of $5750$ years and an artifact has lost $22.3\%$ of its original C-14, how old is the artifact?
QUESTION [0 upvotes]: Carbon dating: The radioactive element carbon-14 has a half-life of 5750 years. The percentage of Carbon-14 present in the remains of organic matter can be used to date the age of organic matter. Archaeologists discovered that the linen wrapping from one end of the Dead Sea Scrolls had lost 22.3% of its Carbon-14 at the time it was found. How old was the linen wrapping?
I don't know how to do it.

REPLY [2 votes]: I will give you the setup of the problem and leave the algebra to you.
It's a standard $Pe^{rt}$ problem. We know at $t = 0$, we have $100\%$ of the Carbon, right? So $f(0) = 1 = Pe^{0r} = P$.
So then we know at $t = 5750$, there is $50\%$ of the carbon remaining. So $f(5750) = e^{5750 * r} = \frac{1}{2}$. That gives you enough information to solve for $r$.
Now you set up $f(t) = 0.223 = e^{rt}$. Plug in your result for $r$ from the previous equation and solve for $t$.