\section{Proof of Control Bounds}
In this section, we demonstrate how our main guarantees for online learning - \Cref{thm:semions_memory} for the known sytem and \Cref{thm:semions_unknown} for the unknown system - imply bounds for non-stochastic control. Throughout, for simplicity, we assume $\radcomp,\radnat,\Rpinot \ge 1$. 

\subsection{Known System}
When the system is known (e.g. $\Ghat = \Gst$), \Cref{eq:recover_stuff} exactly recovers $\ypinothat = \ypinot,\upinothat = \upinot$. Therefore, our analysis considers the following regret benchmark:
\begin{align*}
\dfcreg_T(\Alg;\calM) := F_t(\matM_{t:t-h}\midypinot{t}) -  \inf_{M \in \calM} \sum_{t=1}^T f_t(\matM_t \midypinot{t})
\end{align*} 
To begin, we distill the arguments of \cite{simchowitz2020improper} into a black-box reduction from controller regret to the convex metric $\dfcreg_T(\Alg;\calM)$: 
\begin{proposition}\label{prop:DFC_reduction_known_system} Suppose that $\Alg$ is an adaptive DFC controller which uses $\ypinothat_t = \ypinot_t$ for all $t$, and let $\calM = \Mdfc(h,\radcomp)$. Then,
\begin{align*}
\Regret_T(\Alg;\Pi) \le \dfcreg_T(\Alg;\calM)  + 4 LT \radnat^2 \Rpinot^2 \radcomp^2 \left(\frac{\psicomp(h)}{\radcomp} + \frac{\psinot(h)}{\Rpinot}\right).
\end{align*}
\end{proposition}
The above is proved in \Cref{ssec:lem_dfc_reduction_known}. Next, we convert the assumptions from the control setting into bounds on the quantities which arise in \Cref{thm:semions_memory}. The following is proved in \Cref{sssec:lem:parameter_bounds_known}.
\begin{lemma}\label{lem:parameter_bounds_known} Let $\calM = \Mdfc(m,\radcomp)$, and let $\calC = \embedM(\calM)$, $\matY_t = \embedy(\ypinot_{t:t-h})$, $\matX_t = \sum_{i=0}^h \Gpinot^{[t-i]}\matY_t$. Then, 
\begin{enumerate}
\item $D = \diam(\calC) \le 2\radcomp \sqrt{h}$
\item $\radyc = \max_t\max_{z \in \calC}\|\matY_t z\| \le \radM\Rpinot$
\item $\radY = \max_t \|\matY_t\| \le \sqrt{h}\radnat$
\item $\radX \le \radG \radY$, $\radv = \radnat$, and $\Leff \le 2L \radnat \radcomp \Rpinot$. 
\end{enumerate}
\end{lemma}
We are now in a position to prove our main guarantee for controlling a known system:
\begin{proof}[Proof of \Cref{thm:known_control}]
\end{proof}
\subsection{Unknown System}
Next, let us turn to regret bounds for an unknown system. First, we will begin with an analysis assuming that we spend $N$ initial rounds in an estimation phase, which produces an estimate $\Ghat$ with suitable properties,  
\begin{condition}[Estimation Condition]\label{cond:estimation_setting} Consider the setting where $\Alg$ provides inputs 
\begin{align*}
\ualg_t = \uenalg_t + \uexalg_t, \quad \text{where } \uexalg_t = \begin{cases}  \uinit_t & t \in [N]\\
0 & t \in \{N+1,\dots,N+2h-1\}\\
\uen_t(\matM_t \midyhat{t}) & t \ge N+2h
\end{cases}.
\end{align*}
and where $\ypinothat_t$ is estimated in \Cref{eq:recover_stuff}, using an estimate $\Ghat$. We assume that $\Ghat^{[i]} = 0$ for all $i > 0$, that $\|\Gst - \Ghat\|_{\loneop} \le \epsG$, and that $\psinot(h) \Ru + 2\epsG \radM \radnat \le \radnat$. Lastly, we further assume that $\|\uinit_t\| \le \Ru$ for $t \le N$, 
\end{condition}
Since $\ypinothat_t$ are not exact, there is a feedback relationship between past inputs and future ones. Important, the above condition states that this feedback is not overwhelming, and that our parametrization is ``stable'' in the following sense:
\begin{lemma}[Stability]\label{lem:stability} Under \Cref{asm:estimation_setting}, we have
\begin{align*}
\|\ypinothat_t\| \le 2\radnat,  \quad \forall t \ge N+h.
\end{align*}
Moreover, for $t > N$, $\|\uexalg_t\| \le 2\radnat \radM$.
\end{lemma}
Next, we define a convex benchmark for regret which differs from the benchmark for the known system in two respects: (a) we consider time steps after $N + 2h$ (after the initial estimation phase) and (b), the benchmark considers controls based on the estimate $\ypinothat_t$ sequence:
\begin{align*}
\dfcreg_{T;T_0}(\Alg;\calM,\ypinothat) := \sum_{t=T_0}^T \Fcost_t(\matM_{t:t-h} \midyhat{t}) -  \inf_{M \in \calM} \sum_{t=T_0}^T \fcost_t(M \midypinot{t}), \quad T_0 = N+2h.
\end{align*}
The next step is to define an analogue of the reduction \Cref{prop:DFC_reduction_known_system} for unknown systems:
\begin{proposition}[DFC-Reduction Unknown]\label{prop:DFC_reduction_unknown} Set $T_0 = N+3h$, and let $N \ge 3h$, and suppose \Cref{asm:estimation_setting} holds. Moreover, let $\calM = \calM(h,\radM)$, where $\radM \ge \radcomp$. Then, 
\begin{align*}
\Regret_T(\Alg;\Pi) &\le \dfcreg_{T;N+2h}(\Alg;\calM,\ypinothat) + 8LN(\radnat + \Rpinot \radu)^2.\\
&\quad+ 11L\Rpinot^2 (\radM \radnat + \Ru)^2 \left(  \frac{\constpinot \psinot(h)}{\Rpinot} + \frac{\constpinot \psinot(h)}{\Rpinot}\right).
\end{align*}
\end{proposition}
So far, the above arguments are straightforward applications of those from \cite{simchowitz2020improper}. 
\paragraph{Accounting for Estimation Error in $\ypinothat_t$}


\subsubsection{Omitted Proofs}
\begin{lemma}\label{lem:input_error} Let $\Mapprox,\Mst \in \calM(M,\radM)$. Then,
\begin{align*}
\sum_{t=T_0}^T |f_t(\Mapprox \midyhat{t}) - f_t(\Mst \midypinot{t})| \le 4L\radGst^2\radM \radnat\sum_{t=T_0}^T \max_{i=0}^{h-1}\|\uex_t(\Mapprox \midyhat{t}) - \uex_t(\Mst \midypinot{t})\|_2
\end{align*}
\end{lemma}

\begin{lemma}\label{lem:y_est_sensitivity} For any parameter $\nu > 0$, we have the following inequality:
\begin{align*}
\sum_{t=T_0}^T |f_t(\Mapprox \midyhat{t}) - f_t(\Mst \midypinot{t})| &\le L \nu \sum_{t=T_0}^T \|\uexalg_{t} - \uex_{t}(\Mapprox \midyhat{t})\|_2^2\\
&\quad+ \constquad\cdot \frac{T\epsG^2}{\min\{\nu,1\}} + \consttrunc \cdot (T\psinot(h)+h),
\end{align*}
where $\constquad :=  20L\radGst^4\radnat^2\radM^4 $ and $\consttrunc := 4L \radGst^2 \radM  (2\radnat \radM + \Ru)^2$.
\end{lemma}
{"config": "arxiv", "file": "2006.05910/body/control_proofs.tex"}