
\subsection{Supporting material}
We begin by recalling the definition and properties of quasiconvex functions on $\R$.
We then recall some basic facts about scalar LQR.

\begin{definition}
	A function $f : \cD \mapsto \R\ $ on the convex domain $\ \cD \subseteq \R^n$
	is \emph{quasiconvex} if its sublevel sets
	\(
		\cD_\alpha = \{ x \in \cD : f(x) \leq \alpha \}
	\)
	are convex for all $\alpha \in \R$.
\end{definition}

\begin{lemma}[\citet{boyd-convex}, \S 3.4]
\label{lem:quasiconvex}
	The following facts hold for quasiconvex functions on a convex $\cD \subseteq \R$:
	\begin{enumerate}[label=(\alph*)]
		\item \label{alternatives}
			If $f: \R \mapsto \R$ is continuous,
			then $f$ is quasiconvex
			if and only if at least one of the following conditions holds on $\cD$:
			\begin{enumerate}[label=\arabic*.]
				\item $f$ is nondecreasing.
				\item $f$ is nonincreasing.
				\item \label{alternative-incdec}
					There exists $c \in \cD$ such that
					for all $t \in \cD$,
					if $t < c$ then $f$ is nonincreasing,
					and if $t \geq c$ then $f$ is nondecreasing.
			\end{enumerate}
		\item \label{secondorder}
			If $f : \R \mapsto \R$ is twice differentiable
			and
			$\partial^2 f / \partial x^2 > 0$
			for all $x \in \cD$ where
			$\partial f / \partial x = 0$,
			then $f$ is quasiconvex on $\cD$.
		\item \label{quotient}
			If $f(x) = p(x) / q(x)$,
			where $p: \R \mapsto \R$ is convex with $p(x) \geq 0$ on $\cD$
			and $q: \R \mapsto \R$ is concave with $q(x) > 0$ on $\cD$,
			then $f$ is quasiconvex on $\cD$.
	\end{enumerate}
\end{lemma}

\noindent The following facts about scalar LQR problems can be derived from
the LQR Riccati equation and some calculus (not shown).
\begin{lemma}
\label{lem:scalar-lqr-facts}
For the scalar LQR problem with $a > 0, b > 0$ and $q = r = 1$,
the optimal linear controller $\kopt{a,b}$ is given by the closed-form expression
	\[
		k^\star_{a,b}
		=
		\min_{k \in \R} J_{a,b}(k)
		=
		\min_{k \in \R} \frac{1 + k^2}{-2(a + bk)}
		=
		-\frac{a + \sqrt{a^2 + b^2}}{b}.
	\]
For fixed $a$, the map from $b$ to $k^\star_{a,b}$
is continuous and strictly increasing on the domain $b \in (0, \infty)$
and has the range $(-\infty, -1)$.
For any $k \in (-\infty, -1)$,
there exists a unique $b_k \in (-\infty, -1)$
for which $k = k^\star_{a,b_k}$, given by
\[
	b_k = \frac{2ak}{1 - k^2}.
\]
\end{lemma}

\newcommand{\cD}{\cD}
\newcommand{\cD^b}{\cD^b}
\newcommand{\cD^k}{\cD^k}

\subsection{Proof of \lemmaref{lem:subopt-convex}}

We first recall the statement of the lemma.
\quasi*

\noindent Instead of a monolithic proof,
we present supporting material in \lemmaref{lem:ratio-quasi,lem:cost-quasi}.
We then show the main result in \lemmaref{lem:increasing-main},
which considers $\alpha$-suboptimal neighborhoods on all of $\R$
instead of restricted to $\mathbf{B}$.
\lemmaref{lem:subopt-convex} will follow as a corollary.

We proceed with more setup.
Recall that the scalar DDF problem\ is defined by
$\mathbf{A} = \{a\}$ and $\mathbf{B} = [\recip \theta, 1]$, where $a > 0$.
For this section,
let
\[
	\cD
	= \{ (b, k) \in (0, \infty) \times \R : a + bk < 0 \}
\]
(note that $J_b(k) < \infty \iff a + bk < 0$).
Denote its projections by
$\cD^b(k) = \{ b: (b, k) \in \cD \}$
and
$\cD^k(b) = \{ k: (b, k) \in \cD \}$.
We compute the suboptimality ratio $r : \cD \mapsto \R$ by
\[
	r(b, k) =
	\frac{J_b(k)}{J^\star_b}
	=
	\nofrac{
		\frac{
			1 + k^2
		}{
			-2(a + bk)
		}
	}{
		\frac{
			a + \sqrt{a^2 + b^2}
		}{
			b^2
		}
	}
	=
	\frac{
		(1 + k^2) b^2
	}{
		-2(a + bk)(a + \sqrt{a^2 + b^2})
	}.
\]
We denote its sublevel sets with respect to $b$ for fixed $k$ by
\[
	\cD^b_\alpha(k) = \{ b \in \cD^b(k) : r(b, k) \leq \alpha \}.
\]
\begin{lemma}
\label{lem:ratio-quasi}
	For fixed $k < 0$, the ratio $r(b, k)$ is quasiconvex on $\cD^b_k$,
	and there is at most one $b \in \cD^b_k$ at which $\partial r / \partial b = 0$.
\end{lemma}
\begin{proof}
	By inspection, $r(b, k)$ is smooth on $\cD^b$.
	We now show that the second-order condition of \lemmaref{lem:quasiconvex}\ref{secondorder} holds.
	\input{ratio_intervals_proof.tex}
	The conclusion follows from \lemmaref{lem:quasiconvex}\ref{secondorder}.
\end{proof}

\begin{lemma}
\label{lem:cost-quasi}
	For fixed $b$, the cost $J_b(k)$ is quasiconvex on $\cD^k(b)$.
	Also, $J_b(k)$ is not monotonic,
	so case \ref{alternative-incdec} of \lemmaref{lem:quasiconvex}\ref{alternatives} applies.
\end{lemma}
\begin{proof}
	We have
	\[
		J_b(k)
		=
		\frac{
			1 + k^2
		}{
			-2(a + bk)
		}.
	\]
	The numerator is nonnegative and convex on $k \in \R$.
	The denominator is linear (hence concave) and positive on $\cD^k(b)$.
	Quasiconvexity follows from \lemmaref{lem:quasiconvex}\ref{quotient}.
	Nonmonotonicity follows from the fact that $J_b(k)$ is smooth on $\cD^k(b)$
	and has a unique optimum at $\kopt{b}$, which is not on the boundary of $\cD^k(b)$.
\end{proof}

\noindent We now combine these into the main result.

\begin{lemma}
\label{lem:increasing-main}
	For a scalar DDF problem,
	if $\alpha > 1$ and $k < -1$,
	then $\cD^b_\alpha(k)$ is either:
	a bounded closed interval $[b_1, b_2]$,
		with $b_1$ and $b_2$ increasing in $k$, or
	a half-bounded closed interval $[b_1, \infty)$,
		with $b_1$ increasing in $k$.
\end{lemma}

\begin{proof}
	By \lemmaref{lem:ratio-quasi}, due to quasiconvexity $\cD^b_\alpha$ is convex.
	The only convex sets on $\R$ are the empty set and all types of intervals:
	open, closed, and half-open.
	We know $\cD^b_\alpha$ is not empty because it contains $b_k$.
	We can further assert that
	$\cD^b_\alpha$ has a closed lower bound
	because $\lim_{b \to (-a/k)} r(b, k) = \infty$
	(see \citet[\S A.3.3]{boyd-convex} for details).
	However, the upper bound may be closed or infinite.
	We handle the two cases separately.

	\paragraph{Bounded case.}
	Fix $k_0 < -1$.
	Suppose $\cD^b_\alpha(k_0) = [b_1, b_2]$ for $0 < b_1 < b_2 < \infty$.
	By the implicit function theorem (IFT), at any $(b_0, k_0)$ satisfying $r(b_0, k_0) = \alpha$,
	if $\partial r / \partial b|_{b_0, k_0} \neq 0$
	then there exists an open neighborhood around $(b_0, k_0)$
	for which the solution to $r(b, k) = \alpha$ can be expressed as
	$(g(k), k)$, where $g$ is a continuous function of $k$ and
	\[
		\left. \frac{\partial g(k)}{\partial k} \right|_{k_0} =
		\left. - \left( \frac{\partial r}{\partial b} \right)^{-1}
		\frac{\partial r}{\partial k} \right|_{b_0, k_0}.
	\]
	By the continuity and quasiconvexity of $r$,
	and the fact that $\partial r / \partial b = 0$ only at $b_k$
	(\lemmaref{lem:ratio-quasi})
	we know that $r(b_1, k_0) = r(b_2, k_0) = \alpha$
	and
	\[
		\left. \frac{\partial r}{\partial b} \right|_{b_1, k_0} < 0
		\quad \text{and} \quad
		\left. \frac{\partial r}{\partial b} \right|_{b_2, k_0} > 0.
	\]
	By \lemmaref{lem:scalar-lqr-facts},
	since $k < -1$
	there exists $b_k > 0$ satisfying
	$k = k^\star_{b_k}$.
	Since $r(b_k, k) = 1$ and $\alpha > 1$, we know $b_{k_0} \in (b_1, b_2)$.
	Again by \lemmaref{lem:scalar-lqr-facts},
	the map from $b$ to $k^\star_b$ is increasing in $b$.
	Therefore,
	\(
		{k^\star_{b_1} < k_0 < k^\star_{b_2}}.
	\)
	By the quasiconvexity and nonmonotonicity of $J_b(k)$ from \lemmaref{lem:cost-quasi},
	via \lemmaref{lem:quasiconvex}\ref{alternatives}
	we have
	\[
		\left. \frac{\partial r}{\partial k} \right|_{b_1, k_0} \geq 0
		\quad \text{and} \quad
		\left. \frac{\partial r}{\partial k} \right|_{b_2, k_0} \leq 0.
	\]
	Therefore, the functions $g_1, g_2$ satisfying the conclusion of the IFT
	in the neighborhoods around $(b_1, k_0)$ and $(b_2, k_0)$ respectively
	also satisfy
	\[
		\left. \frac{ \partial g_1(k)}{ \partial k } \right|_{b_1, k_0} \geq 0
		\quad \text{and} \quad
		\left. \frac{ \partial g_2(k)}{ \partial k } \right|_{b_2, k_0} \geq 0.
	\]
	Therefore, $b_1$ and $b_2$ are locally nondecreasing in $k$.
	

	\paragraph{Unbounded case.}
	Suppose $\cD^b_\alpha(k) = [b_1, \infty)$ for $b_1 < \infty$.
	By the same IFT argument as in the bounded case, $b_1$ is increasing in $k$.
	By the quasiconvexity of $r$ in $b$,
	the value of $r$ is increasing for $b  > b_k$,
	but the definition of $\cD^b_\alpha(k)$ implies that
	$r(b, k) \leq \alpha$ for all $b > b_k$.
	Therefore, $\lim_{b \to \infty} r(b, k)$ exists
	and is bounded by $\alpha$.
	In particular,
	\begin{equation*}
		\begin{split}
			\lim_{b \to \infty} r(b, k)
			&=
			\lim_{b \to \infty}
			\frac{
				(1 + k^2) b^2
			}{
				-2(a + bk)(a + \sqrt{a^2 + b^2})
			}
			\\ &=
			\lim_{b \to \infty}
			\frac{
				(1 + k^2) b^2 / b^2
			}{
				-2(a + bk)(a + \sqrt{a^2 + b^2}) / b^2
			}
			\\ &=
			-
			\frac{
				1 + k^2
			}{
				2k
			}.
		\end{split}
	\end{equation*}
	Taking the derivative shows that this value is decreasing in $k$ for $k < 0$.
	Therefore, if $k < k' < 0$ then
	\[
		\lim_{b \to \infty} r(b, k') \leq \lim_{b \to \infty} r(b, k) \leq \alpha.
	\]
	The property that $r(b, k')$ is increasing in $b$ for $b > b_k$
	further ensures that
	$r(b, k') \leq \alpha$ for all $b > b_k$.
	Therefore, $\cD^b_\alpha(k')$ is also unbounded.
\end{proof}

\noindent For completeness, we prove \lemmaref{lem:subopt-convex}.

\quad

\begin{proof} (of \lemmaref{lem:subopt-convex}).
	By \lemmaref{lem:increasing-main},
	$\cD^b_\alpha(k)$ is either
	a bounded closed interval $[b_1, b_2]$,
		with $b_1$ and $b_2$ increasing in $k$, or
	a half-bounded closed interval $[b_1, \infty)$,
		with $b_1$ increasing in $k$.
	Recall that $\suboptneighb{\alpha}{k} = \cD^b_\alpha(k) \cap \mathbf{B}$
	with $\mathbf{B} = [\recip \theta, 1]$.
	Therefore, the half-bounded case can be reduced to the bounded case with $b_2 = 1$.
	The intersection can be expressed as
	\[
		\suboptneighb{\alpha}{k} = [\max\{b_1, \textstyle \recip \theta\}, \min\{b_2, 1\}],
	\]
	where the interval $[a, b]$ is defined as the empty set if $a > b$.
	Taking the maximum or minimum of a nonstrict monotonic function and a constant
	preserves the monotonicity, so we are done.
\end{proof}







\section{Introduction}
\input{introduction.tex}

\section{Problem setting}
\input{setting.tex}

\paragraph{Standard LQR problem}
\input{lqr.tex}

\section{Theoretical results}
\input{results_scalar.tex}

\section{Empirical results}
\input{empirical_upperbound.tex}

\subsection{Suboptimal neighborhood visualizations}
\input{empirical_lowerbound.tex}

\section{Related work}
\input{related.tex}

\section{Conclusion and future work}
\input{conclusion.tex}

\newpage




\subsection{Scalar upper bound}

We are now ready to bound the covering number for scalar systems.
The first lemma bounding $J^\star_{a,b}$ will be useful for the lower bound also.
We then construct a cover inductively.

\begin{lemma}
\label{lem:scalar-cost-ub}
	In a scalar LQR problem,
	if $a > 0$ and $0 < b \leq 1$,
	then the optimal scalar LQR cost satisfies the bounds
	\(
		\nofrac{2a}{b^2}
		<
		J^\star_{a,b}
		<
		\nofrac{(2a + 1)}{b^2}.
	\)
\end{lemma}
\begin{proof}
	The lower bound is visible from
	the closed-form solution for the scalar Riccati equation, which is
	\(
		J^\star_{a,b} = \frac{a + \sqrt{a^2 + b^2}}{b^2}.
	\)
	The upper bound is obtained by substituting $a^2 + b^2 \leq (a + 1)^2$.
\end{proof}

\begin{lemma}
\label{lem:scalar-cover-recursion}
	If $p, \tau, k = {\normalfont \texttt{GCC}}(a, b_1, b_2, q)$,
	then for any $\beta \in (0, 1)$,
	there exists $k' \in \R$
	such that
	$\displaystyle p', \tau, k' = {\normalfont \texttt{GCC}} \left( a, \beta b_1, \beta b_2, \beta^{-2} q \right)$,
	where $\ p' = \beta^{-2} p$.%
\end{lemma}
\begin{proof}
	In the scalar system,
	the GCC matrix Riccati equation \eqref{eq:petersen-riccati}
	reduces to the quadratic equation
	\begin{equation}
	\label{eq:scalar-ric}
		\left(
			\textstyle \recip \tau b_1^2
			- \recip{1 + \tau} b_2^2
		\right)
		p^2
		+ 2a p
		+ q
		= 0.
	\end{equation}
	Substituting $p' = \beta^{-2} p$ into \eqref{eq:scalar-ric}
	and multiplying by $\beta^{-2}$ yields
	a new instance of~\eqref{eq:scalar-ric}
	with the parameters
		$b_1' = \beta b_1$, \ 
		$b_2' = \beta b_2$, \ 
		$q' = \beta^{-2} q$,
	for which $p'$ is a solution
	with $\tau$ unchanged.
\end{proof}


\begin{theorem}
\label{thm:covering-scalar}
	For the scalar DDF problem\ defined by
		$\mathbf{A} = \{ a \}$,
		where $a > 0$,
		and 
		$\mathbf{B} = \left[\textstyle \recip \theta, 1 \right]$,
	if $\alpha \geq \frac{2a+1}{2a}$,
	then $\coveringnum{\alpha}{\mathbf{B}} = O(\log \theta)$.
\end{theorem}
\begin{proof}
	We construct a cover from the upper end of $\mathbf{B}$.
	By \lemmaref{lem:scalar-cost-ub},
	the condition ${\alpha \geq \frac{2a+1}{2a}}$ implies that
	\(
		J^\star_{b=1} < \alpha 2 a < \alpha J^\star_{b=1}.
	\)
	Therefore, by
	\lemmaref{lem:petersen-gcc,lem:petersen-existence},
	there exists $\beta \in (0, 1)$
	and
	$p, \tau, k$
	such that
	$p, \tau, k = {\normalfont \texttt{GCC}}(a, (1-\beta)/2, (1+\beta)/2, 1)$
	and
	$p \leq \alpha 2a$.

	Proceeding inductively,
	suppose that for $N \geq 1$,
	we have covered $[\beta^N, 1]$
	by the intervals $\mathbf{B}_n = [\beta^{n+1}, \beta^{n}]$
	for $n \in \{0, \dots, N-1\}$,
	and each $\mathbf{B}_n$ has a controller $k_n$ such that 
	\[
		\beta^{-2n}p, \tau, k_n = {\normalfont \texttt{GCC}} \left(
			a,
			\nofrac{(\beta^{n} - \beta^{n+1})}{2},
			\nofrac{(\beta^{n} + \beta^{n+1})}{2},
			\beta^{-2n}
		\right).
	\]
	Then the existence of the desired $\mathbf{B}_N, k_N$
	follows immediately from
	\lemmaref{lem:scalar-cover-recursion}.

	By \lemmaref{lem:lancaster-ARE-domination},
	for each $\mathbf{B}_n$
	the GCC state cost $q_n = \beta^{-2n} \geq 1$
	is an upper bound on the cost if we replace $q_n$ with $1$
	to match the DDF problem.
	Therefore,
	for each interval $\mathbf{B}_n$,
	for all $b \in \mathbf{B}_n$,
	\[
		\alpha J^\star_{b}
		\geq
		\alpha J^\star_{\beta^n}
		>
		\beta^{-2n} \alpha 2 a 
		\geq
		\beta^{-2n} p
		\geq
		J_b(k_n),
	\]
	where first inequality is due to \lemmaref{lem:lancaster-ARE-domination},
	the second is due to \lemmaref{lem:scalar-cost-ub},
	the third is by construction of $p$,
	and last is due to the GCC guarantee of $k_n$.
	Hence, $\mathbf{B}_n \subseteq \suboptneighb{\alpha}{k_n}$.
	We cover the full $\mathbf{B}$ when
	$\beta^{N} \leq \recip \theta$,
	which is satisfied by $N \geq - \log \theta / \log \beta$.
\end{proof} 

\subsection{Scalar lower bound}

For the matching lower bound,
we begin by
deriving a simplified overestimate of $\suboptneighb{\alpha}{k}$.
We then show that the true $\suboptneighb{\alpha}{k}$
is still a closed interval moving monotonically with $k$.
Finally, we argue that
the gaps between consecutive elements of a cover grow at most geometrically,
while the range of $k$ values in a cover must grow linearly with $\theta$.

\begin{lemma}
\label{lem:scalar-neighborhood-optimistic}
	For a scalar DDF problem\ with $a \geq 1,\ \mathbf{B} = [\recip \theta, 1]$,
	for any $k < 0$,
	if $\alpha \geq 3/2$, then
	$\suboptneighb{\alpha}{k} \subseteq \recip{|k|} [c_1 \!- \!c_2,\ c_1\! + \!c_2]$,
	where $c_1$ and $c_2$ are constants depending on $\alpha$ and $a$.
\end{lemma}
\begin{proof}
	Beginning with the closed-form solution for $J_b(k)$,
	which can be derived from \eqref{eq:cost-suboptimal},
	we define
	\begin{equation}
	\label{eq:Jbk}
		J_b(k) = \frac{1 + k^2}{-2(a + bk)}
		\geq \frac{k^2}{-2(a + bk)}
		\defeq \underline{J_b}(k)
		.
	\end{equation}
	By \lemmaref{lem:scalar-cost-ub}, we have
	\(
		J^\star_b < \nofrac{3a}{b^2} \defeq \overline{J^\star_b}
	\),
	so $\tilde r = \nofrac{\underline{J_b}(k)}{\,\overline{J^\star_b}}$
	is a lower bound on the suboptimality of $k$.
	Computing $\partial^2 \tilde r / \partial b^2$
	shows that $\tilde r$ is strictly convex in $b$ on the domain $a + bk < 0$,
	so the $\alpha$-sublevel set of $\tilde r$ is the closed interval
	with boundaries where $\tilde r = \alpha$.
	This equation is quadratic in $b$ with the solutions
	\(
		b = -a(3 \alpha \pm \sqrt{9 \alpha^2 - 6 \alpha})/k
	\).
	The resulting interval contains $\suboptneighb{\alpha}{k}$.
\end{proof}


\begin{restatable}{lemma2}{quasi}
\label{lem:subopt-convex}
	For a scalar DDF problem, if $\alpha > 1$
	and $k < -1$,
	then $\suboptneighb{\alpha}{k}$ is either empty or a closed interval
	$[b_1, b_2]$,
	with $b_1$ and $b_2$ positive and nondecreasing in $k$.
\end{restatable}
\begin{proof}
The result follows from quasiconvexity of
both the suboptimality ratio $J_b(k) / J^\star_b$
and the cost $J_b(k)$.
Showing these requires some tedious calculations.
\ifextended{
	For details, see \Cref{sec:appendix-theory}.
}{
	For details, see the extended version of this paper.
}
\end{proof}

\begin{theorem}
\label{thm:scalar-lb}
	For a scalar DDF problem\ with
	$a = 1,\ \mathbf{B} = [\recip \theta, 1]$,
	if $\alpha \geq \frac 3 2$, %
	then
	$\coveringnum{\alpha}{\mathbf{B}} = \Omega(\log \theta)$.
\end{theorem}
\begin{proof}
	From the closed-form solution
	\(
		k^\star_{a,b} = -(a + \sqrt{a^2 + b^2})/b
	\),
	we observe that $k^\star_b < -1$ for all $b \in \mathbf{B}$.
	This, along with the quasiconvexity of $J_b(k)$ in $k$,
	implies that there exists a minimal $\alpha$-suboptimal cover $\cC$ for which all $k_i < -1$.
	Suppose $\cC = k_1, \dots, k_N$ is such a cover, ordered such that $k_i < k_{i+1}$.
	Then
	by \lemmaref{lem:subopt-convex},
	$\suboptneighb{\alpha}{k_i}$
	and
	$\suboptneighb{\alpha}{k_{i+1}}$
	must intersect,
	so their overestimates according to
	\lemmaref{lem:scalar-neighborhood-optimistic}
	certainly intersect,
	therefore satisfying
	\[
		\frac{c_1 + c_2}{-k_{i+1}}
		\geq
		\frac{c_1 - c_2}{-k_i}
		\implies
		\frac{k_{i+1}}{k_i} \leq \frac{c_1 + c_2}{c_1 - c_2}
		\implies
		\frac{k_N}{k_1} \leq \left(\frac{c_1 + c_2}{c_1 - c_2}\right)^{N-1}.
	\]
	By \lemmaref{lem:scalar-neighborhood-optimistic},
	to cover $b = 1$
	controller $k_1$ must satisfy
	$k_1 \geq -(c_1 + c_2)$,
	and to cover $b = \recip \theta$,
	controller $k_N$ must satisfy
	$k_N \leq -\theta(c_1 - c_2)$.
	Along with the previous result, this implies
	\[
		\left(\frac{c_1 + c_2}{c_1 - c_2}\right)^{N-1}
		\geq
		\theta
		\frac{c_1 - c_2}{c_1 + c_2}
		\implies
		N \geq \frac{\log \theta}{\log \frac{c_1 + c_2}{c_1 - c_2}}.
	\]
	Recalling that $c_1$ and $c_2$ only depend on $a$ and $\alpha$,
	the $\Omega(\log \theta)$ dependence on $\theta$ is established.
\end{proof}

\paragraph{Remarks}
\begin{itemize}
	\item For the upper bound, it may be possible to compute or bound $\beta$ in the scalar case
		as a function of $a$ and $\alpha$,
		but the analogous result will likely be much more complicated in the matrix case.
	\item \theoremref{thm:covering-scalar} imposes a lower bound on $\alpha$ greater than $1$.
		We believe this is a mild condition in practice:
		if the application demands a suboptimality ratio very close to 1,
		then the size of the suboptimal cover is likely to become impractical for storage.
		However, further theoretical results building upon suboptimal coverings may require eliminating the bound.
\end{itemize}




