# A Bounded Regret Strategy for Linear Dynamics with Unknown Control

Jacob Carruth

(November 2023)

###### Abstract

We consider a simple linear control problem in which a single parameter $b$,
describing the effect of the control variable, is unknown and must be learned.
We work in the setting of agnostic control: we allow $b$ to be any real number
and we do not assume that we have a prior belief about $b$. For any fixed time
horizon, we produce a strategy whose expected cost is within a constant factor
of the best possible.

##  1 Introduction

In this paper, we consider a simple linear control problem with a single
unknown parameter $b$. We do not assume that we are given a prior belief about
$b$, and we seek to bound a quantity called the regret, which compares our
expected cost to that of an opponent with perfect knowledge of $b$.

This falls within the purview of adaptive control. In the adaptive control
literature, one typically seeks a control strategy that minimizes the regret
as the time horizon tends to infinity. Here, we explore a variant of adaptive
control called agnostic control, in which one seeks to minimize the regret
over a fixed, potentially short, time horizon; see also [2, 3, 4, 5, 6].

Let $q(t)$ denote the position of a particle at time $t$. Given some starting
position $q_{0}\in\mathbb{R}$, the particle evolves according to the
stochastic ODE

$dq(t)=(aq(t)+bu(t))dt+dW(t),\qquad q(0)=q_{0}.$ (1.1)

Here $a$ and $b$ are real numbers, $W(t)$ is a standard Brownian motion (here
“standard” means that $W(0)=0$ and the variance of $W(t)$ is $t$), and $u$ is
the control variable. We treat the parameter $a$ as a fixed, known quantity,
but we treat $b$ as an unknown parameter about which we have no prior belief.
We choose $u(t)$ depending on the history up to time $t$, i.e.,
$(q(\tau))_{0\leq\tau\leq t}$. The control $u(t)$ is allowed to depend on $a$,
but not on the unknown parameter $b$.

More precisely, a _strategy_ is a choice of $u(t)$ for every $t$ and every
history $(q(\tau))_{0\leq\tau\leq t}$, subject to certain technical conditions
that allow us to make sense of solutions to (1.1) for arbitrary
$b\in\mathbb{R}$ (a precise definition is given in Section 3). For a given
strategy $\sigma$, we let $q^{\sigma}(t,b)$ and $u^{\sigma}(t,b)$ denote the
corresponding solutions to (1.1) (note that these are random variables). Fix a
time horizon $T>0$. We define the cost of $\sigma$ to be the random variable

$\textsc{Cost}(\sigma,b)=\int_{0}^{T}\big{(}(q^{\sigma}(t,b))^{2}+(u^{\sigma}(t,b))^{2}\big{)}dt,$

and we write $\textsc{ECost}(\sigma,b)$ for the expected value of
$\textsc{Cost}(\sigma,b)$.

For a given value of $b$, there exists a strategy $\sigma_{\text{opt}}(b)$
that minimizes the quantity $\textsc{ECost}(\sigma,b)$ over all strategies
$\sigma$ (this is well-known, see, e.g., [1]). We write

$\textsc{ECost}_{\text{opt}}(b)=\textsc{ECost}(\sigma_{\text{opt}}(b),b).$

It is helpful to think of $\sigma_{\text{opt}}(b)$ as the strategy of an
opponent who knows the value of $b$ and plays optimally—this leads to the
notion of _regret_.

We define the (multiplicative) _regret_ 111We will use the multiplicative
regret, often referred to as the competitive ratio. There are other notions of
regret; see [2, 4] for a discussion of two others. of a strategy $\sigma$ by

$\text{MReg}(\sigma,b)=\frac{\textsc{ECost}(\sigma,b)}{\textsc{ECost}_{\text{opt}}(b)},$

and the _worst-case regret_ of $\sigma$ by

$\text{MReg}^{*}(\sigma)=\sup_{b\in\mathbb{R}}\text{MReg}(\sigma,b).$

We seek a strategy that minimizes the _worst-case regret_ , and we refer to
such a strategy as an _optimal agnostic strategy_.

In [2, 4], we produced almost optimal agnostic strategies for the dynamics
(1.1) in the case in which the parameter $a$ is unknown and $b$ is known (for
simplicity, in those papers we took $b=1$). The problem considered here, in
which $b$ is unknown, appears to be more difficult. This is because it has the
following feature: If we set $u(t)=(\Delta t)^{-1/2}$ for a very short time
increment $\Delta t$, then we learn a lot about the parameter $b$ and only
incur a finite cost. Therefore, we may want to take $u=\pm\infty$; this had
better be done carefully.

In this paper, we tackle the more modest problem of exhibiting a strategy with
_bounded_ multiplicative regret. Specifically, we prove the following theorem

######  Theorem 1.

Fix $|q_{0}|\geq 1$ and $T>0$ as above. Then there exists a constant $C>0$
such that for any $a\in\mathbb{R}$ the strategy BR defined in Sections 4–7
satisfies

$\textsc{ECost}(\emph{BR},b)\leq
C\cdot\textsc{ECost}_{\emph{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$

Clearly, Theorem 1 implies that

$\text{MReg}^{*}(\text{BR})\leq C.$

We emphasize that the constant $C$ in Theorem 1 depends on $q_{0}$ and $T$ but
is independent of the parameter $a$.

We note that our assumption that $|q_{0}|\geq 1$ in Theorem 1 can be replaced
by $|q_{0}|\geq q_{\text{small}}$ for any $q_{\text{small}}>0$. Unfortunately,
however, the resulting constant $C$ in Theorem 1 then tends to infinity as
$q_{\text{small}}$ tends to zero. We think that with a bit of care this can be
avoided, and we are currently working on producing a bounded regret strategy
for small $q_{0}$.

We now give an overview of some of the ideas behind the strategy BR. We will
assume that $q_{0}\geq 1$. By symmetry, this also defines the strategy for
$q_{0}\leq-1$.

We begin with a high-level overview of our strategy. Our strategy is different
in each of the cases $a>A$, $|a|\leq A$, and $a<-A$, where $A>1$ is large real
number.

First, we describe our strategy when $a<-A$. In this case, the position $q$ of
the particle will decay to zero rapidly if we just set $u=0$. This will
achieve bounded regret unless $|b|\gg|a|$, in which case the system will decay
to zero much faster if we set $u=\pm q$ (depending on the sign of $b$).
Therefore, our strategy begins by immediately testing whether $|b|$ is huge.
If we find that it is, then we set $u=\pm q$; if not, we set $u=0$.

Next, we describe our strategy when $|a|\leq A$. In this case, we incur a
bounded expected cost by simply setting $u=0$. As in the previous case, this
achieves bounded regret unless $|b|$ is huge, in which case we should again
set $u=\pm q$. Therefore, when $a$ is bounded, our strategy is essentially the
same as in the case in which $a$ is large and negative.

Last, suppose that $a>A$. As in the previous two cases, we’d like to set
$u=\pm q$ if $|b|\gg|a|$. On the other hand, if $|b|$ is extremely small, then
we stand to gain little by controlling the system and we are happy setting
$u=0$. For $|b|$ neither huge nor tiny, we can achieve bounded regret by
exercising a control whose order of magnitude is $|u|\approx\pm(a/b^{2})|q|$
(again, the sign here is determined by the sign of $b$).

We thus proceed as follows. We begin by testing whether $|b|\gg a$. If we
detect that it is, then we set $u=\pm q$ (depending on the sign of $b$). If do
not detect $|b|\gg a$, then we attempt to learn the order of magnitude of
$|b|$. We accomplish this via a series of _Testing Epochs_ , in which we
exercise increasingly large control over extremely short successive time
intervals. If during one of these Testing Epochs we register a significant
change in $q$, then we have a good guess for the order of magnitude of $b$ and
we control the system by setting $u\approx(a/|b|)|q|$. If, on the other hand,
we undergo many Testing Epochs without registering a significant change in
$q$, we conclude that $|b|$ is extremely small and we set $u=0$ for the
remainder of the game. We now discuss the Testing Epochs in a bit more detail.

We continue to assume that $a$ is large and positive. Suppose that we have
determined that $|b|\gg a$; our goal now is to determine the order of
magnitude of $|b|$. We enter a Testing Phase, consisting of a series of
Testing Epochs indexed by an integer $\nu\geq 1$. The goal of each Testing
Epoch is to determine whether $|b|\approx e^{-\nu}a$. Only the first of these
Testing Epochs is guaranteed to occur.

Let $\tau>0$ be a small real number depending on $a$. During Testing Epoch 1,
we set $u\approx e(a\tau)^{-1/2}|q|$. If we register a change in $q$ on the
order of magnitude of $(a\tau)^{1/2}$ within time $\tau$, then with high
probability $|b|\approx e^{-1}a$. Since we have a good guess for $|b|$, we
exit the Testing Phase and control the system by setting
$u\approx\pm(a/|b|)|q|\approx\pm e^{\nu}|q|$. If, on the other hand, we fail
to register a sufficiently large change in $q$ within time $\tau$, then we
assume that $|b|\ll e^{-1}a$ and we enter Testing Epoch 2.

If we enter Testing Epoch 2, then we set $u\approx e^{2}(a\tau)^{-1/2}|q|$. As
above, if we register a change in $q$ on the order of magnitude of
$(a\tau)^{1/2}$ within time $\tau$, then with high probability $|b|\approx
e^{-2}a$. We then exit the Testing Phase and control the system by setting
$u\approx\pm e^{2}|q|$. If, on the other hand, we fail to detect a significant
change in $q$ within time $\tau$, then we enter Testing Epoch 3.

In general, if we enter Testing Epoch $\nu$, then we set $u\approx
e^{\nu}(a\tau)^{-1/2}|q|$. If we register a change in $q$ on the order of
magnitude of $(a\tau)^{1/2}$ within time $\tau$, then with high probability
$|b|\approx e^{-\nu}a$. We then exit the Testing Phase and set $u\approx\pm
e^{\nu}|q|$. If, on the other hand, we fail to detect a significant change in
$q$ within time $\tau$, then we enter Testing Epoch $(\nu+1)$.

If we pass through $\nu^{*}$ Testing Epochs for some large, positive integer
$\nu^{*}$ (depending on $a$) without detecting a significant change in $q$,
then we conclude that $|b|\ll e^{-\nu^{*}}a$. We then achieve bounded regret
by setting $u=0$ for the remainder of the game.

This concludes our high-level overview of the strategy BR. In order to keep
the discussion simple, we’ve left out some details, e.g., we haven’t said how
our strategy handles rare events or how we determine the sign of $b$. For
details, see Sections 5–7.

We now outline the contents of the remainder of this paper. In Section 2, we
prove some preliminary lemmas about stochastic processes. In Section 3, we
establish some basic properties of strategies and of the function
$\textsc{ECost}_{\text{opt}}(b)$. In Sections 4–7, we prove Theorem 1.

We note here that adaptive control theory is an active field of research, and
we refer the interested reader to the literature surveys in our papers [2, 4].

The author would like to thank the Air Force Office of Scientific Research,
and specifically Frederick Leve, for support via AFOSR grant FA9550-19-1-0005.
He would also like to thank Maximilian Eggl and Clarence Rowley for helpful
discussions, and Charles Fefferman for helpful discussions and for carefully
reading an earlier draft of this paper.

##  2 Preliminaries

Throughout this paper we let $W(t)$ denote a copy of standard Brownian motion
and $(\Omega,\mathcal{F},\text{Prob})$ denote the corresponding probability
space. We write $\text{E}[X]$ and $\text{Var}[X]$ to denote the expectation
and variance (respectively) of a random variable $X$ with respect to Prob.
Here, “standard” Brownian motion means that $W(0)=0$ and $\text{Var}[W(t)]=t$.
For $t\geq 0$, we let $\mathcal{F}_{t}$ denote the sigma-algebra determined by
the history of $W(s)$ from time $s=0$ until time $s=t$.

Throughout this section we write $C$, $C^{\prime}$, $c$, $c^{\prime}$, etc. to
denote positive absolute constants. We write $C_{X}$, $C_{X}^{\prime}$,
$c_{X}$, etc. to denote positive constants depending on a quantity $X$. The
value of these constants will change from line to line.

The remainder of this section is devoted to proving two lemmas about the
hitting times of certain simple stochastic ODE’s. We will make use of the
following remark.

######  Remark 1.

Suppose $q(t)$ is governed by

$dq(t)=(\alpha q(t)+\beta)dt+dW(t),\qquad q(0)=Q_{0}$ (2.1)

for real numbers $\alpha$, $\beta$, and $Q_{0}\neq 0$. Define a stochastic
process

$X(t)=e^{-\alpha t}q(t)-Q_{0}=\beta\bigg{(}\frac{1-e^{-\alpha
t}}{\alpha}\bigg{)}+\int_{0}^{t}e^{-\alpha s}dW(s)$ (2.2)

and observe that, for any $t\geq 0$, $X(t)$ is a normal random variable with

$\emph{E}[X(t)]=\beta\bigg{(}\frac{1-e^{-\alpha
t}}{\alpha}\bigg{)},\qquad\emph{Var}[X(t)]=\bigg{(}\frac{1-e^{-2\alpha
t}}{2\alpha}\bigg{)}.$ (2.3)

For the remainder of this paper, we adopt the convention that $(1-e^{-\alpha
t})/\alpha=t$ when $\alpha=0$, so that (2.2) and (2.3) are well-defined for
any $\alpha\in\mathbb{R}$.

Observe that the process $t\mapsto(X(t)-\emph{E}[X(t)])$ satisfies the
reflection principle, i.e., for any $M>0$ we have

$\emph{Prob}\Big{[}\sup_{0\leq s\leq t}\\{X(s)-\emph{E}[X(s)]\\}\geq
M\Big{]}=2\cdot\emph{Prob}[(X(t)-\emph{E}[X(t)])\geq M].$ (2.4)

The proof of (2.4) is easily adapted from the proof of the reflection
principle for Brownian motion; see [2] for details.

We are now ready to state and prove the first of our preliminary lemmas.

######  Lemma 1.

For any sufficiently large positive integers $m_{0}$, $n_{0}$, the following
holds. Let $Q_{0}\neq 0$, $\alpha>0$, and $\beta$ be real numbers, and let
$\tau>0$ be a sufficiently small real number depending on $\alpha$. Suppose
$q(t)$ is governed by

$dq(t)=(\alpha q(t)+\beta Q_{0}(\alpha\tau)^{-1/2})dt+dW(t),\qquad
q(0)=Q_{0}.$ (2.5)

Define a stopping time $\tau_{*}$ to be equal to the first time $t\in(0,\tau)$
for which

$|q(t)-Q_{0}|\geq|Q_{0}|(\alpha\tau)^{1/2}$

if such a time exists and equal to $\tau$ if no such time exists. Then the
following hold.

  1. _(A)_

$\emph{Prob}[\tau_{*}=\tau]\leq C\exp(-cQ_{0}^{2}\beta^{2}/\alpha)$ for any
$|\beta|\geq\alpha e^{n_{0}}.$

  2. _(B)_

$\emph{Prob}[\tau_{*}<\tau]\leq C\exp(-cQ_{0}^{2}\alpha)$ for any
$|\beta|\leq\alpha e^{-m_{0}}$.

###### Proof.

Without loss of generality, we assume that $Q_{0}>0$. Motivated by Remark 1,
we define

$X(t)=e^{-\alpha t}q(t)-Q_{0};$

note that

$\text{E}[X(t)]=\bigg{(}\frac{\beta
Q_{0}}{(\alpha\tau)^{1/2}}\bigg{)}\bigg{(}\frac{1-e^{-\alpha
t}}{\alpha}\bigg{)}$ (2.6)

and

$\text{Var}[X(t)]=\bigg{(}\frac{1-e^{-2\alpha t}}{2\alpha}\bigg{)}.$ (2.7)

Provided $\tau$ is sufficiently small depending on $\alpha$, we then have for
any $t\in[0,\tau]$ that

$\displaystyle|\text{E}[X(t)]|\approx\bigg{(}\frac{|\beta|Q_{0}t}{(\alpha\tau)^{1/2}}\bigg{)},$
(2.8) $\displaystyle\text{Var}[X(t)]\approx t.$ (2.9)

Let $n_{0}\geq 1$ be a sufficiently large integer and assume until further
notice that

$\beta\geq\alpha e^{n_{0}}.$ (2.10)

Suppose that $q(\tau)<Q_{0}(1+(\alpha\tau)^{1/2})$. This implies that
$X(\tau)<Q_{0}(\alpha\tau)^{1/2}$; combining this with (2.8) and (2.10) (and
observing that $\text{E}[X(\tau)]>0$ when $\beta>0$), we get

$(X(\tau)-\text{E}[X(\tau)])<\frac{Q_{0}\tau^{1/2}\beta}{\alpha^{1/2}}(e^{-n_{0}}-c).$

Taking $n_{0}$ sufficiently large ensures that

$(X(\tau)-\text{E}[X(\tau)])<-c\bigg{(}\frac{Q_{0}\tau^{1/2}\beta}{\alpha^{1/2}}\bigg{)}.$

Note that the event $(\tau_{*}=\tau)$ implies that
$q(t)<Q_{0}(1+(\alpha\tau)^{1/2})$ for all $t\in(0,\tau)$. We have therefore
shown that

$\text{Prob}[\tau_{*}=\tau]\leq\text{Prob}\big{[}(X(\tau)-\text{E}[X(\tau)])<-cQ_{0}\tau^{1/2}\beta/\alpha^{1/2}\big{]}.$
(2.11)

Since $X(\tau)$ is a normal random variable, we use (2.9) and (2.11) to deduce
that

$\text{Prob}[\tau_{*}=\tau]\leq C\exp(-cQ_{0}^{2}\beta^{2}/\alpha)\;\text{for
any}\;\beta\geq\alpha e^{n_{0}}.$ (2.12)

We now assume that

$\beta\leq-\alpha e^{n_{0}}.$ (2.13)

If $q(\tau)>Q_{0}(1-(\alpha\tau)^{1/2})$, then

$\displaystyle X(\tau)>$
$\displaystyle(1-\alpha\tau)Q_{0}(1-(\alpha\tau)^{1/2})-Q_{0}$
$\displaystyle>$ $\displaystyle-c(\alpha\tau)^{1/2}Q_{0}$

provided $\tau$ is sufficiently small depending on $\alpha$. Combining this
with (2.13) and (2.8) (and observing that $\text{E}[X(t)]<0$ when $\beta<0$),
we get

$(X(\tau)-\text{E}[X(\tau)])>\frac{Q_{0}\tau^{1/2}|\beta|}{\alpha^{1/2}}(c-c^{\prime}e^{-n_{0}}).$

Taking $n_{0}$ sufficiently large then ensures that

$(X(\tau)-\text{E}[X(\tau)])>c\frac{Q_{0}\tau^{1/2}|\beta|}{\alpha^{1/2}}.$

Proceeding as in the proof of (2.12), i.e., observing that the event
$(\tau_{*}=\tau)$ implies $q(\tau)>Q_{0}(1-(\alpha\tau)^{1/2})$ and using
(2.9) along with the fact that $X(\tau)$ is a normal random variable, we
deduce that

$\text{Prob}[\tau_{*}=\tau]\leq C\exp(-cQ_{0}^{2}\beta^{2}/\alpha)\;\text{for
any}\;\beta\leq-\alpha e^{n_{0}}.$ (2.14)

Combining (2.12) and (2.14) proves Part (A) of the Lemma.

Until further notice, assume that $\beta\geq 0$. Observe that if $q(t)\leq
Q_{0}(1-(\alpha\tau)^{1/2})$ for some $t\in[0,\tau]$, then
$X(t)\leq-(\alpha\tau)^{1/2}Q_{0}$. Since $\text{E}[X(t)]\geq 0$ (see (2.6)),
we therefore have

$\text{Prob}[\exists t\in[0,\tau]:q(t)\leq Q_{0}(1-(\alpha\tau)^{1/2})]\\\
\leq\text{Prob}[\exists
t\in[0,\tau]:(X(t)-\text{E}[X(t)])\leq-(\alpha\tau)^{1/2}Q_{0}].$

By the reflection principle for $(X(t)-\text{E}[X(t)])$, (2.9), and the fact
that $X(\tau)$ is a normal random variable, we have

$\text{Prob}[\exists t\in[0,\tau]:q(t)\leq Q_{0}(1-(\alpha\tau)^{1/2})]\leq
C\exp(-cQ_{0}^{2}\alpha)\;\text{for any}\;\beta\geq 0.$ (2.15)

Now assume that $\beta<0$. If $q(t)\geq Q_{0}(1+(\alpha\tau)^{1/2})$, for some
$t\in[0,\tau]$, then

$\displaystyle X(t)\geq$ $\displaystyle(1-\alpha
t)Q_{0}(1+(\alpha\tau)^{1/2})-Q_{0}$ $\displaystyle\geq$ $\displaystyle
c(\alpha\tau)^{1/2}Q_{0}$

provided $\tau$ is sufficiently small depending on $\alpha$. By (2.6),
$\text{E}[X(t)]\leq 0$ when $\beta<0$. We have therefore shown that

$\text{Prob}[\exists t\in[0,\tau]:q(t)\geq Q_{0}(1+(\alpha\tau)^{1/2})]\\\
\leq\text{Prob}[\exists t\in[0,\tau]:(X(t)-\text{E}[X(t)])\geq
c(\alpha\tau)^{1/2}Q_{0}].$

As above, we use the reflection principle for $(X(t)-\text{E}[X(t)])$, along
with (2.9) and the fact that $X(\tau)$ is a normal random variable, to deduce
that

$\text{Prob}[\exists t\in[0,\tau]:q(t)\geq Q_{0}(1+(\alpha\tau)^{1/2})]\leq
C\exp(-cQ_{0}^{2}\alpha)\;\text{for any}\;\beta<0.$ (2.16)

Let $m_{0}\geq 1$ be a sufficiently large integer and assume until further
notice that

$\alpha e^{-m_{0}}\geq\beta\geq 0.$ (2.17)

Observe that if $q(t)>Q_{0}(1+(\alpha\tau)^{1/2})$ for any $t\in[0,\tau]$,
then $X(t)>c(\alpha\tau)^{1/2}Q_{0}$ provided $\tau$ is sufficiently small
depending on $\alpha$. Combining this with (2.8) and (2.17) gives

$(X(t)-\text{E}[X(t)])>(\alpha\tau)^{1/2}Q_{0}(c-Ce^{-m_{0}});$

taking $m_{0}$ sufficiently large gives

$(X(t)-\text{E}[X(t)])>c(\alpha\tau)^{1/2}Q_{0}.$

We have therefore shown that

$\text{Prob}[\exists t\in[0,\tau]:q(t)>Q_{0}(1+(\alpha\tau)^{1/2})]\\\
\leq\text{Prob}[\exists
t\in[0,\tau]:(X(t)-\text{E}[X(t)])>c(\alpha\tau)^{1/2}Q_{0}].$

Using (2.4) (the reflection principle for $X(t)$), along with (2.9) and the
fact that $X(\tau)$ is a normal random variable, we have

$\begin{split}\text{Prob}[\exists
t\in[0,\tau]:q(t)>Q_{0}(&1+(\alpha\tau)^{1/2})]\\\ &\leq
C\exp(-cQ_{0}^{2}\alpha)\;\text{for any}\;0\leq\beta\leq\alpha
e^{-m_{0}}.\end{split}$ (2.18)

Combining this with (2.15) gives

$\text{Prob}[\tau_{*}<\tau]\leq C\exp(-cQ_{0}^{2}\alpha)\;\text{for
any}\;0\leq\beta\leq\alpha e^{-m_{0}}.$ (2.19)

Now assume that

$-\alpha e^{-m_{0}}\leq\beta<0.$ (2.20)

Observe that if

$q(t)<Q_{0}(1-(\alpha\tau)^{1/2})\;\text{for any}\;t\in[0,\tau]$

, then $X(t)<-Q_{0}(\alpha\tau)^{1/2}$. Combining this with (2.8) and (2.20),
we get

$(X(t)-\text{E}[X(t)])<-Q_{0}(\alpha\tau)^{1/2}(c-Ce^{-m_{0}}).$

Taking $m_{0}$ sufficiently large gives

$(X(t)-\text{E}[X(t)])<-cQ_{0}(\alpha\tau)^{1/2}.$

Proceeding in the proof of (2.18), we deduce that

$\text{Prob}[\exists t\in(0,\tau):q(t)<Q_{0}(1-(\alpha\tau)^{1/2})]\\\ \leq
C\exp(-cQ_{0}^{2}\alpha)\;\text{for any}\;-\alpha e^{-m_{0}}\leq\beta<0.$

Combining this with (2.16) gives

$\text{Prob}[\tau_{*}<\tau]\leq C\exp(-cQ_{0}^{2}\alpha)\;\text{for
any}\;-\alpha e^{-m_{0}}\leq\beta<0.$ (2.21)

Together, (2.19) and (2.21) prove Part (B) of the lemma. ∎

######  Lemma 2.

Let $Q_{0}\neq 0$ and $\alpha$ be real numbers. Suppose that $q(t)$ is
governed by

$dq(t)=\alpha q(t)dt+dW_{t},\qquad q(0)=Q_{0}.$

For any $\eta\in(0,(\log(2))^{-1})$, the following hold.

  1. _(A)_

If $\alpha>0$, then:

    1. _(i)_

$\emph{Prob}[q(t)<2Q_{0}\;\emph{for all}\;t\in[0,(\eta\alpha)^{-1}]]\leq
C\exp(-c_{\eta}Q_{0}^{2}\alpha)$.

    2. _(ii)_

$\emph{Prob}[\exists t\geq 0:q(t)\leq Q_{0}/2]\leq C\exp(-cQ_{0}^{2}\alpha)$.

  2. _(B)_

If $\alpha<0$, then:

    1. _(i)_

$\emph{Prob}[q(t)>Q_{0}/2\;\emph{for all}\;t\in[0,(\eta|\alpha|)^{-1}]]\leq
C\exp(-c_{\eta}Q_{0}^{2}|\alpha|)$.

    2. _(ii)_

For any $\hat{T}>0$, we have

$\emph{Prob}[\exists t\in[0,\hat{T}]:|q(t)|\geq 2Q_{0}]\leq
C_{\hat{T}}(1+Q_{0}^{-2})\exp(-cQ_{0}^{2}|\alpha|).$

  3. _(C)_

If $\alpha\neq 0$, then

$\emph{Prob}[\exists t\in[0,\eta|\alpha|^{-1}]:q(t)\geq
2Q_{0}\;\emph{OR}\;q(t)\leq Q_{0}/2]\leq C\exp(-c_{\eta}Q_{0}^{2}|\alpha|).$

###### Proof.

We first remark that Part (B.ii) is an easy consequence of Lemma 4.3 in [2].

Motivated by Remark 1, we define

$X(t)=e^{-\alpha t}q(t)-Q_{0},$

and we recall that $X(t)$ is a normal random variable with mean 0 and

$\text{Var}[X(t)]=\frac{1-e^{-2\alpha t}}{2\alpha}.$ (2.22)

Assume until further notice that $\alpha>0$. If $q((\eta\alpha)^{-1})<2Q_{0}$,
then

$X((\eta\alpha)^{-1})<e^{-1/\eta}2Q_{0}-Q_{0}<-c_{\eta}Q_{0}.$

Therefore

$\text{Prob}[q(t)<2Q_{0}\;\text{for
all}\;t\in[0,(\eta\alpha)^{-1}]]\leq\text{Prob}[X((\eta\alpha)^{-1})<-c_{\eta}Q_{0}].$

By (2.22),

$\text{Var}[X((\eta\alpha)^{-1})]\approx\alpha^{-1}.$ (2.23)

Since $X((\eta\alpha)^{-1})$ is a normal random variable with mean 0, we
conclude that

$\text{Prob}[q(t)<2Q_{0}\;\text{for all}\;t\in[0,(\eta\alpha)^{-1}]]\leq
C\exp(-c_{\eta}Q_{0}^{2}\alpha).$ (2.24)

This proves (A.i)

To prove (A.ii), it suffices (e.g., by Fatou’s Lemma) to show that for any
sufficiently large $\hat{T}>0$ we have

$\text{Prob}[\exists t\in[0,\hat{T}]:q(t)\leq Q_{0}/2]\leq
C\exp(-cQ_{0}^{2}\alpha).$ (2.25)

If $q(t)\leq Q_{0}/2$ for some $t\in[0,\hat{T}]$, then $X(t)\leq-Q_{0}/2$.
Combining this with (2.4) (i.e., the reflection principle for $X(t)$), we see
that

$\text{Prob}[\exists t\in[0,\hat{T}]:q(t)\leq Q_{0}/2]\leq
2\cdot\text{Prob}[X(\hat{T})<-Q_{0}/2].$

To prove (2.25), we note that $\text{Var}[X(\hat{T})]\approx\alpha$ and that
$X(\hat{T})$ is a normal random variable with mean 0.

Now observe that if $q(t)\geq 2Q_{0}$ for some $t\in[0,\eta\alpha^{-1}]$, then

$X(t)\geq e^{-\alpha t}2Q_{0}-Q_{0}\geq c_{\eta}Q_{0}.$

By (2.4) (i.e., the reflection principle for $X(t)$), we have

$\text{Prob}[\exists t\in[0,\eta\alpha^{-1}]:q(t)\geq 2Q_{0}]\leq
2\cdot\text{Prob}[X(\eta\alpha^{-1})\geq c_{\eta}Q_{0}].$

Observe that $\text{Var}[X(\eta\alpha^{-1})]\approx_{\eta}\alpha^{-1}$;
combining this with the fact that $X(\eta\alpha^{-1})$ is a normal random
variable with mean 0 gives

$\text{Prob}[\exists t\in[0,\eta\alpha^{-1}]:q(t)\geq 2Q_{0}]\leq
C\exp(-c_{\eta}Q_{0}^{2}\alpha).$ (2.26)

We combine (2.25) and (2.26) to get

$\begin{split}\text{Prob}[\exists t\in[0,\eta\alpha^{-1}]:(q(t)\geq
2Q_{0})\;\text{OR}\;&(q(t)\leq Q_{0}/2)]\\\ &\leq
C\exp(-c_{\eta}Q_{0}^{2}\alpha)\;\text{for any}\;\alpha>0.\end{split}$ (2.27)

This proves (C) when $\alpha>0$.

We omit the proofs of (B.i), and (C) when $\alpha<0$; they are essentially the
same as the proofs of (2.24) and (2.27) (respectively). ∎

##  3 Agnostic Control Strategies

We begin this section by establishing some conventions and notation:

  * •

We introduce a _starting position_ $Q_{0}\neq 0$, a _time horizon_ $T>0$, and
a _growth parameter_ $a\in\mathbb{R}$.

  * •

Constants $c,C,C^{\prime},$ etc. denote absolute constants.

  * •

Recall that $W(t)$ denotes a copy of standard Brownian motion,
$(\Omega,\mathcal{F},\text{Prob})$ denotes the corresponding probability
space, and, for any $t\geq 0$, we write $\mathcal{F}_{t}$ to denote the sigma-
algebra determined by the history $(W(s))_{s\in[0,t]}$.

A _strategy_ (for starting position $Q_{0}$, time horizon $T$, and growth
parameter $a$) is a collection of random variables $q(t,b)$ and $u(t,b)$
defined for all $t\in[0,T]$ and $b\in\mathbb{R}$ satisfying the following
properties:

  1. (S.1)

For every $b\in\mathbb{R}$, $q(t,b)$ is a continuous function of $t$ with
probability 1 and $u(t,b)$ is an $L^{2}$ function of $t$ with probability 1.

  2. (S.2)

For every $b\in\mathbb{R}$ and $t\in[0,T]$ the maps $(s,\omega)\mapsto
q(s,b,\omega)$ and $(s,\omega)\mapsto u(s,b,\omega)$, defined on
$[0,t]\times\Omega$, are measurable as functions on
$[0,t]\times(\Omega,\mathcal{F}_{t},\text{Prob})$. Intuitively, this means
that $q,u$ are determined by the past.

  3. (S.3)

For every $b\in\mathbb{R}$,

$\text{E}\bigg{[}\int_{0}^{T}(q(t,b))^{2}+(u(t,b))^{2}\ dt\bigg{]}<\infty.$

  4. (S.4)

For almost all $\omega\in\Omega$, we have that for all
$b,b^{\prime}\in\mathbb{R}$, and for all $t\in[0,T]$, if
$q(s,b,\omega)=q(s,b^{\prime},\omega)$ for all $s\in[0,t]$, then
$u(s,b,\omega)=u(s,b^{\prime},\omega)$ for almost all $s\in[0,t]$. This tells
us that $u$ does not depend on the unknown $b$.

  5. (S.5)

For every $b\in\mathbb{R}$ and $t\in[0,T]$, we have

$q(t,b)=Q_{0}+W(t)+\int_{0}^{t}[aq(s,b)+bu(s,b)]\ ds$

with probability 1.

For a given $b\in\mathbb{R}$, we refer to $q(t,b)$ and $u(t,b)$ as,
respectively, the _particle trajectory_ and the _control variable_ at time
$t$.

Let $\sigma$ denote an arbitrary strategy. We then write $q^{\sigma}(t,b)$,
$u^{\sigma}(t,b)$ for the particle trajectories and control variables
associated with $\sigma$. Often, the parameter $b$ is implicit and we just
write $q^{\sigma}(t)$, $u^{\sigma}(t)$.

We define the _cost_ of a strategy $\sigma$ to be the random variable

$\textsc{Cost}(\sigma,b)=\int_{0}^{T}\big{(}(q^{\sigma}(t,b))^{2}+(u^{\sigma}(t,b))^{2}\big{)}\
dt.$

We then define the _expected cost_ of a strategy $\sigma$ by

$\textsc{ECost}(\sigma,b)=\text{E}[\textsc{Cost}(\sigma,b)].$

Given any smooth function $v:[0,T]\rightarrow\mathbb{R}$, we can define a
strategy $\tilde{\sigma}$ by setting

$u^{\tilde{\sigma}}(t,b)=-v(t)q^{\tilde{\sigma}}(t,b)$

(note that $q^{\tilde{\sigma}}$ is then determined by Property (S.5)). We
refer to such a strategy $\tilde{\sigma}$ as a _simple feedback strategy_ with
_gain function_ $v$.

We now establish some upper bounds on the expected cost of simple feedback
strategies.

Let $\tilde{\sigma}$ denote the simple feedback strategy with gain function
$v$. One can show (as in [2]) that for any $b\in\mathbb{R}$ we have

$\textsc{ECost}(\tilde{\sigma},b)=\varphi(0,b)\cdot
Q_{0}^{2}+\int_{0}^{T}\varphi(t,b)\ dt,$

where

$\varphi(t,b)=\int_{t}^{T}(1+v^{2}(\tau))\cdot\exp\bigg{(}2\int_{t}^{\tau}\big{(}\alpha-
bv(s)\big{)}\ ds\bigg{)}\ d\tau.$

This implies the following remark.

######  Remark 2.

Let $\emph{CG}(\alpha)$ denote the simple feedback strategy with constant gain
function $v\equiv\alpha\in\mathbb{R}$ (so that
$u^{\emph{CG}(\alpha)}(t)=-\alpha\cdot(q^{\emph{CG}(\alpha)}(t))$). Then the
following hold.

  1. _(A)_

If $a<b\alpha$, then

$\textsc{ECost}(\emph{CG}(\alpha),b)\leq\frac{(Q_{0}^{2}+T)(1+\alpha^{2})}{|a-b\alpha|}.$

  2. _(B)_

Let $A=\max\\{|\alpha|,|a-b\alpha|\\}$. Then

$\textsc{ECost}(\emph{CG}(\alpha),b)\leq C_{A}(Q_{0}^{2}+T).$

  3. _(C)_

If $a>0$ and $\alpha=0$, then

$\textsc{ECost}(\emph{CG}(0),b)\leq(Q_{0}^{2}+T)\frac{e^{2aT}}{2a}\;\text{for
any}\;b\in\mathbb{R}.$

For any $\beta\in\mathbb{R}$, we define a simple feedback strategy
$\sigma_{\text{opt}}(\beta)$ via the control variable

$u^{\sigma_{\text{opt}}(\beta)}(t)=-\beta\cdot\kappa(T-t,\beta)\cdot
q^{\sigma_{\text{opt}}(\beta)}(t),$

where $\kappa:[0,T]\times\mathbb{R}\rightarrow[0,\infty)$ is defined by

$\kappa(t,\beta)=\kappa(t,\beta;a)=\begin{cases}t&\text{if }a=\beta=0,\\\
\frac{\tanh(t\sqrt{a^{2}+\beta^{2}})}{\sqrt{a^{2}+\beta^{2}}-a\tanh(t\sqrt{a^{2}+\beta^{2}})}&\text{else}.\end{cases}$
(3.1)

It is well-known (see, e.g., [1]) that for any $b\in\mathbb{R}$ the strategy
$\sigma_{\text{opt}}(b)$ minimizes the quantity $\textsc{ECost}(\sigma,b)$
among simple feedback strategies. (In fact, by a straightforward modification
of an argument in [2], one can show that $\sigma_{\text{opt}}(b)$ minimizes
$\textsc{ECost}(\sigma,b)$ among _all_ strategies.) For $b\in\mathbb{R}$ we
define

$\textsc{ECost}_{\text{opt}}(b)=\textsc{ECost}(\sigma_{\text{opt}}(b),b).$

Of course, both the strategies $\sigma_{\text{opt}}(\beta)$ and the quantity
$\textsc{ECost}_{\text{opt}}(b)$ depend on the parameters $a$, $T$, $Q_{0}$.

It is well known (again, see [1]) that $\textsc{ECost}_{\text{opt}}(b)$ is of
the form

$\textsc{ECost}_{\text{opt}}(b)=\kappa(T,b)\cdot
Q_{0}^{2}+\int_{0}^{T}\kappa(t,b)\ dt,$ (3.2)

where $\kappa(t,b)$ is defined in (3.1). We use (3.2) to prove the following
lemma.

######  Lemma 3.

We have the following lower bounds on $\textsc{ECost}_{\emph{opt}}(b)$.

  1. _(A)_

If $a\geq 1$, then

$\textsc{ECost}_{\emph{opt}}(b)\geq c_{T}\cdot
Q_{0}^{2}\cdot\begin{cases}\frac{e^{2aT}}{a}&\text{for any}\;|b|\leq
ae^{-aT},\\\ \frac{a}{b^{2}}&\text{for any}\;ae^{-aT}\leq|b|\leq a,\\\
\frac{1}{|b|}&\text{for any}\;|b|\geq a.\end{cases}$

  2. _(B)_

If $a\leq 1$, then

$\textsc{ECost}_{\emph{opt}}(b)\geq\frac{c_{T}\cdot
Q_{0}^{2}}{1+|a|+|b|}\;\text{for any}\;b\in\mathbb{R}.$

###### Proof.

Observe that

$\kappa(t,b)\geq 0\;\text{for any}\;t\in[0,T],$

and therefore

$\textsc{ECost}_{\text{opt}}(b)\geq Q_{0}^{2}\cdot\kappa(T,b).$ (3.3)

It is straightforward to verify that

$\kappa(T,b)>\frac{c_{T}}{1+|a|+|b|}\;\text{for any}\;a,b\in\mathbb{R};$

combining this with (3.3) implies Part (B) of the Lemma as well as the case
$|b|\geq a$ in Part (A).

We now remark that

$\begin{split}&\tanh(x)\geq(1-Ce^{-2x})\;\text{for any}\;x\geq 0.\end{split}$
(3.4)

Assume that $a\geq 1$. Then clearly

$\kappa(T,b)\geq\frac{c_{T}}{\sqrt{a^{2}+b^{2}}-a\tanh(T\sqrt{a^{2}+b^{2}})}\;\text{for
any}\;b\in\mathbb{R}.$

Combining this with (3.4) gives

$\kappa(T,b)\geq\frac{c_{T}}{(b^{2}/a)+aCe^{-2T\sqrt{a^{2}+b^{2}}}}.$

From this inequality and (3.3), we easily deduce the remaining two cases of
Part (A). ∎

##  4 Conventions for the remainder of the paper

The remainder of this paper is devoted to proving Theorem 1.

Throughout Sections 5–7, the following hold:

  * •

We fix a starting position $|q_{0}|\geq 1$ and a time horizon $T>0$.

  * •

For any $a,b\in\mathbb{R}$, we write $\textsc{ECost}_{\text{opt}}(b;a)$ to
denote the optimal expected cost for known $b$ with time horizon $T$, starting
position $q_{0}$, and growth parameter $a$. Similarly, we write
$\textsc{ECost}(\sigma,b;a)$ to denote the expected cost of a strategy
$\sigma$ for time horizon $T$, starting position $q_{0}$, and growth parameter
$a$.

  * •

Often, the value of the growth parameter $a$ will be clear from context and we
will just write $\textsc{ECost}_{\text{opt}}(b)$, $\textsc{ECost}(\sigma,b)$.

  * •

We let $A\geq 1$ be a large real number depending only on $T$.

  * •

Constants $c,C,C^{\prime},$ etc. are allowed to depend on $q_{0}$ and $T$ (and
therefore on $A$).

For any $a\in\mathbb{R}$, we will define in Sections 5–7 a strategy denoted BR
for time horizon $T$, starting position $q_{0}$, and growth parameter $a$. We
will then show that there exists a constant $C>1$ so that

$\textsc{ECost}(\text{BR},b;a)\leq
C\cdot\textsc{ECost}_{\text{opt}}(b;a)\;\text{for any}\;a,b\in\mathbb{R}.$

Once we do this, we’ve proved Theorem 1.

##  5 The strategy for large, positive $a$

We let $a$ denote the growth parameter, and we assume throughout this section
that

$a\geq A.$

Our goal in this section is to prove Theorem 1 for such $a$.

We let $0<\tau\ll 1$ denote a small real number depending on $a$.

We let $K\geq 1$ denote a large absolute constant, to be chosen later. Of
course, constants $c,C,C^{\prime},$ etc. may depend on $K$.

In a moment we will define the strategy BR (referenced in Theorem 1) in the
case $a\geq A$. Throughout this section we write $q,u$ for the particle
trajectories and control variables $q^{\text{BR}},u^{\text{BR}}$.

We define a quantity

$\nu^{*}=\lfloor aT\rfloor.$ (5.1)

The strategy BR is divided into $(\nu^{*}+2)$ Epochs; we enumerate them
starting from 0. Only the first of the Epochs (Epoch 0) is guaranteed to
occur. Each of the Epochs $0,\dots,\nu^{*}$ (all but the final Epoch) is
divided into two or more Subepochs. When one of these Epochs occurs, only the
first Subepoch (the _Testing_ Subepoch) is guaranteed to occur.

We now define the strategy BR.

Epoch 0: Our strategy begins, at time 0, with Subepoch $0.\text{i}$.

Subepoch $0.\text{i}$ (Testing): During Subepoch $0.\text{i}$ we set $u=-q$.
Subepoch $0.\text{i}$ ends at time $\tau_{0}$, where $\tau_{0}$ is equal to
the first time $t\in(0,(10a)^{-1})$ for which $q(t)=2q_{0}$ or
$q(t)=\frac{1}{2}q_{0}$ if such a time exists and is equal to $(10a)^{-1}$ if
no such time exists.

In the event that $\tau_{0}<(10a)^{-1}$, then at time $\tau_{0}$ we enter
Subepoch $0.\text{ii}$. In the event that $\tau_{0}=(10a)^{-1}$, then at time
$\tau_{0}$ we enter Epoch 1.

We stipulate that $A$ is large enough to ensure that $(10a)^{-1}<T$, so that
$\tau_{0}<T$ with probability 1.

Subepoch $0.\text{ii}$ (Control): Note that $\tau_{0}$ is equal to the time at
which we enter Subepoch $0.\text{ii}$ if such a time exists and equal to $T$
if no such time exists.

Suppose that we enter Subepoch $0.\text{ii}$, i.e., suppose that
$\tau_{0}<(10a)^{-1}$; we then have either $q(\tau_{0})=\frac{1}{2}q_{0}$ or
$q(\tau_{0})=2q_{0}$ with probability 1.

If $q(\tau_{0})=\frac{1}{2}q_{0}$, then during Subepoch $0.\text{ii}$ we set
$u(t)=-K\cdot q(t)$.

If $q(\tau_{0})=2q_{0}$, then during Subepoch $0.\text{ii}$ we set
$u(t)=K\cdot q(t)$.

Subepoch $0.\text{ii}$ then lasts until time $\tilde{\tau}_{0}$, where
$\tilde{\tau}_{0}$ is equal to the first time $t\in(\tau_{0},T)$ for which
$|q(t)|\geq 2q(\tau_{0})$ if such a time exists and is equal to $T$ if no such
time exists. If $\tilde{\tau}_{0}=T$, then the game ends along with Subepoch
$0.\text{ii}$ at time $\tilde{\tau}_{0}$. If $\tilde{\tau}_{0}<T$, then at
time $\tilde{\tau}_{0}$ we enter Epoch 1.

Epoch $\nu$ (for $1\leq\nu\leq\nu^{*}$):

Define a stopping time $t_{\nu}$ to be equal to the time at which we enter
Epoch $\nu$ if such a time exists and equal to $T$ if no such time exists.

Epoch $\nu$ is divided into three Subepochs, only the first of which (Subepoch
$\nu.\text{i}$) is guaranteed to occur.

Subepoch $\nu.\text{i}$ (Testing): Assume that $t_{\nu}<T$; we then enter
Subepoch $\nu.\text{i}$ at time $t_{\nu}$. During Subepoch $\nu.\text{i}$ we
set

$u=\frac{e^{\nu}q(t_{\nu})}{(a\tau)^{1/2}},$

and Subepoch $\nu.\text{i}$ lasts until time $\tau_{\nu}$, where $\tau_{\nu}$
is equal to the first time $t$ in the interval
$(t_{\nu},\min\\{T,t_{\nu}+\tau\\})$ for which

$|q(t)-q(t_{\nu})|>|q(t_{\nu})|(a\tau)^{1/2}$

if such a time exists and equal to $\min\\{T,t_{\nu}+\tau\\}$ if no such time
exists.

If $\tau_{\nu}<\min\\{T,t_{\nu}+\tau\\}$, then at time $\tau_{\nu}$ we enter
Subepoch $\nu.\text{ii}$.

If $\tau_{\nu}=(t_{\nu}+\tau)$, then at time $\tau_{\nu}$ we enter Epoch
($\nu$ \+ 1).

If $\tau_{\nu}=T$, then at time $\tau_{\nu}$ the game ends.

Subepoch $\nu.\text{ii}$ (Control I): Define a stopping time $\tilde{t}_{\nu}$
to be equal to the time at which we enter Subepoch $\nu.\text{ii}$ if such a
time exists and equal to $T$ if no such time exists. Note that we enter
Subepoch $\nu.\text{ii}$ only if we enter Subepoch $\nu.\text{i}$.

Suppose that we enter Subepoch $\nu.\text{ii}$, i.e., suppose that
$\tilde{t}_{\nu}<T$. Then during Subepoch $\nu.\text{ii}$ we set
$u=1000e^{\nu}q$, and Subepoch $\nu.\text{ii}$ lasts until time
$\tilde{\tau}_{\nu}$, where $\tilde{\tau}_{\nu}$ is equal to the first time
$t\in(\tilde{t}_{\nu},T)$ for which $|q(t)|\geq 2|q(\tilde{t}_{\nu})|$ if such
a time exists and equal to $T$ if no such time exists.

If $\tilde{\tau}_{\nu}<T$, then at time $\tilde{\tau}_{\nu}$ we enter Subepoch
$\nu.\text{iii}$.

If $\tilde{\tau}_{\nu}=T$, then at time $\tilde{\tau}_{\nu}$ the game ends
(along with Subepoch $\nu.\text{ii}$).

Subepoch $\nu$.iii (Control II): Define a stopping time $\hat{t}_{\nu}$ to be
equal to the time at which we enter Subepoch $\nu.\text{iii}$ if such a time
exists and equal to $T$ if no such time exists. Note that we enter Subepoch
$\nu.\text{iii}$ only if we enter Subepoch $\nu.\text{ii}$.

Suppose that we enter Subepoch $\nu$.iii. Then during Subepoch $\nu$.iii, we
set $u=-1000e^{\nu}q$ and Subepoch $\nu$.iii lasts until time
$\hat{\tau}_{\nu}$, where $\hat{\tau}_{\nu}$ is equal to the first time
$t\in(\hat{t}_{\nu},T)$ for which $|q(t)|\geq 2|q(\hat{t}_{\nu})|$ if such a
time exists and equal to $T$ if no such time exists.

If $\hat{\tau}_{\nu}<T$, then at time $\hat{\tau}_{\nu}$ we enter Epoch
$(\nu+1)$.

If $\hat{\tau}_{\nu}=T$, then at time $\hat{\tau}_{\nu}$ the game ends (along
with Subepoch $\nu.\text{iii}$).

Epoch $(\nu^{*}+1)$ (Apathy): Define a stopping time $t_{\nu^{*}+1}$ to be
equal to the time at which we enter Epoch $(\nu^{*}+1)$ if such a time exists
and equal to $T$ if no such time exists. If we enter Epoch $(\nu^{*}+1)$, then
we set $u=0$ until the end of the game at time $T$.

This completes the definition of our strategy BR. It is straightforward to
verify that the strategy BR satisfies the definition of a strategy given in
Section 3; we will not give the details here. (For more detail see the
discussion of branching strategies in [2].)

We say that a given Epoch or Subepoch occurs if there exists some time at
which we enter the given Epoch or Subepoch.

For $0\leq\nu\leq(\nu^{*}+1)$ we define, for a given value of $b$, the random
variable $\textsc{Cost}_{\nu}(b)$ to be equal to the cost incurred during
Epoch $\nu$ if Epoch $\nu$ occurs and equal to 0 if Epoch $\nu$ does not
occur. Clearly

$\textsc{ECost}(\text{BR},b)=\sum_{\mu=0}^{\nu^{*}+1}\text{E}[\textsc{Cost}_{\mu}(b)].$

For $0\leq\nu\leq\nu^{*}$, we define the random variable
$\textsc{Cost}_{\nu.j}(b)$ to be equal to the cost incurred during Subepoch
$\nu.j$ (with $j\in\\{\text{i},\text{ii},\text{iii}\\}$ if $\nu\geq 1$ and
$j\in\\{\text{i},\text{ii}\\}$ if $\nu=0$) if Subepoch $\nu.j$ occurs and
equal to zero if Subepoch $\nu.j$ does not occur.

We define events

$\displaystyle\mathcal{E}_{\nu}$
$\displaystyle=\\{\text{Epoch}\;\nu\;\text{occurs}\\}$
$\displaystyle\text{for}\;0\leq\nu\leq(\nu^{*}+1),$
$\displaystyle\mathcal{E}_{\nu.\text{ii}}$
$\displaystyle=\\{\text{Subepoch}\;\nu.\text{ii occurs}\\}\qquad$
$\displaystyle\text{for}\;0\leq\nu\leq\nu^{*},$
$\displaystyle\mathcal{E}_{\nu.\text{iii}}$
$\displaystyle=\\{\text{Subepoch}\;\nu.\text{iii occurs}\\}\qquad$
$\displaystyle\text{for}\;1\leq\nu\leq\nu^{*}.$

Note that

$\displaystyle\mathcal{E}_{\nu.\text{iii}}\subset\mathcal{E}_{\nu.\text{ii}}\subset\mathcal{E}_{\nu}$
$\displaystyle\text{for}\;1\leq\nu\leq\nu^{*},$
$\displaystyle\mathcal{E}_{\nu}\subset\bigcap_{\mu=0}^{\nu-1}\mathcal{E}_{\mu}$
$\displaystyle\text{for}\;1\leq\nu\leq(\nu^{*}+1).$

For any $1\leq\nu\leq(\nu^{*}+1)$ and $0\leq m\leq\nu$ we define the event

$\mathcal{E}_{\nu,m}=\\{\mathcal{E}_{\nu}\text{ AND
}(\mathcal{E}_{\mu.\text{ii}}\;\text{for exactly }m\text{ integers }\mu\text{
with }0\leq\mu<\nu)\\}.$

Note that by taking $\tau$ sufficiently small depending on $a$, we can ensure
that

$\displaystyle(1+(a\tau)^{1/2})^{\nu^{*}}<\frac{11}{10},$
$\displaystyle(1-(a\tau)^{1/2})^{\nu^{*}}>\frac{9}{10}$

(recall that the quantity $\nu^{*}$ is determined by $a$). This implies the
following: Suppose that the event $\mathcal{E}_{\nu,m}$ occurs and that we
enter Epoch $\nu$ at time $t_{\nu}$. Then with probability 1 we have

$c\cdot 4^{m}\leq|q(t_{\nu})|\leq C\cdot 4^{m}.$ (5.2)

For any stopping time $\tau^{*}$ we define

$\mathcal{F}_{\tau^{*}}=\\{A\in\mathcal{F}:A\cap\\{\tau^{*}\leq
s\\}\in\mathcal{F}_{s}\;\text{for all}\;s\in[0,T]\\}.$

Note that $\mathcal{F}_{\tau^{*}}$ is a sub $\sigma$-algebra of $\mathcal{F}$
and that the random variables $\tau^{*}$ and $(q(s))_{0\leq s\leq\tau^{*}}$
are $\mathcal{F}_{\tau^{*}}$-measurable.

###  5.1 Performance of the strategy during Epoch 0

Recall that we set $u=-q$ during Subepoch $0.\text{i}$ and that Subepoch
$0.\text{i}$ ends at time $\tau_{0}$. Assume that $|b|\geq 100a$. Then

$\text{Prob}[\tau_{0}>10|b|^{-1}]\leq\text{Prob}[\tau_{0}>(10|a-b|/99)^{-1}].$

Using Parts AA.i and BB.i of Lemma 2 (and that our assumption implies
$10|b|^{-1}\leq(10a)^{-1}$), we deduce that

$\text{Prob}[\tau_{0}>10|b|^{-1}]\leq C\exp(-c|b|)\;\text{for any}\;|b|\geq
100a.$ (5.3)

Assume that $|b|\leq a/10$; then

$\text{Prob}[\mathcal{E}_{0.\text{ii}}]=\text{Prob}[\tau_{0}<(10a)^{-1}]\leq\text{Prob}[\tau_{0}<(11|a-b|^{-1}/100)].$

By Lemma 2.C, we have

$\text{Prob}[\mathcal{E}_{0.\text{ii}}]\leq C\exp(-ca)\;\text{for
any}\;|b|\leq a/10.$ (5.4)

We now claim that

$\text{Prob}[\mathcal{E}_{1}]\leq C\exp(-c|b|)\;\text{for any}\;|b|\geq 100a.$
(5.5)

Observe that

$\begin{split}\text{Prob}[\mathcal{E}_{1}]\leq&\text{Prob}[\tau_{0}=(10a)^{-1}]+\text{Prob}[(q(\tau_{0})=2q_{0}\;\text{AND}\;\mathcal{E}_{1}]\\\
&+\text{Prob}[(q(\tau_{0})=q_{0}/2)\;\text{AND}\;\mathcal{E}_{1}].\end{split}$
(5.6)

Inequality (5.3) implies that

$\text{Prob}[\tau_{0}=(10a)^{-1}]\leq C\exp(-c|b|)\;\text{for}\;|b|\geq 100a.$
(5.7)

By Lemma 2.BB.ii, we have

$\text{Prob}[q(\tau_{0})=2q_{0}]\leq C\exp(-c|b|)\;\text{for any}\;b\geq
100a.$ (5.8)

Recall that if we enter Subepoch $0.\text{ii}$ with $q(\tau_{0})=q_{0}/2$,
then we set $u=-Kq$. We then enter Epoch 1 if and only if we encounter
$|q|=q_{0}$. Therefore, by Lemma 2.BB.ii,

$\text{Prob}[(q(\tau_{0})=q_{0}/2)\;\text{AND}\;\mathcal{E}_{1}]\leq
C\exp(-c|b|)\;\text{for any}\;b\geq 100a.$ (5.9)

Similarly, if we enter Subepoch $0.\text{ii}$ with $q(\tau_{0})=2q_{0}$, then
we set $u=Kq$. We then enter Epoch 1 if and only if we encounter $|q|=4q_{0}$.
Therefore (again by Lemma 2.BB.ii),

$\text{Prob}[(q(\tau_{0})=2q_{0})\;\text{AND}\;\mathcal{E}_{1}]\leq
C\exp(-c|b|)\;\text{for any}\;b\leq-100a.$ (5.10)

By Lemma 2.AA.ii,

$\text{Prob}[q(\tau_{0})=q_{0}/2]\leq C\exp(-c|b|)\;\text{for
any}\;b\leq-100a.$ (5.11)

Combining (5.6)-(5.11) proves (5.5).

The remainder of this section is devoted to showing that

$\text{E}[\textsc{Cost}_{0}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$ (5.12)

During Subepoch $0.\text{i}$ we set $u=-q$ and we have $|q|\leq C$ with
probability 1. Since Subepoch $0.\text{i}$ lasts for at most time
$(10a)^{-1}$, we have

$\text{E}[\textsc{Cost}_{0.\text{i}}(b)]\leq Ca^{-1}\;\text{for
any}\;b\in\mathbb{R}.$ (5.13)

Additionally, (5.3) implies that

$\text{E}[\textsc{Cost}_{0.\text{i}}(b)]\leq C|b|^{-1}\;\text{for
any}\;|b|\geq 100a.$ (5.14)

Combining (5.13) and (5.14) with Lemma 3 gives

$\text{E}[\textsc{Cost}_{0.\text{i}}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$ (5.15)

During Subepoch 0.ii (if it occurs) we again have $|q|\leq C$ and thus
$|u|\leq C$ (since $|u|=K|q|$). Therefore (5.4) implies that

$\text{E}[\textsc{Cost}_{0.\text{ii}}(b)]\leq Ca^{-1}\;\text{for any}\;|b|\leq
a/10.$ (5.16)

Recall that if we enter Subepoch 0.ii with $q(\tau_{0})=q_{0}/2$, then during
Subepoch 0.ii we set $u=-Kq$. By Remark 2.A, we therefore have

$\text{E}[\textsc{Cost}_{0.\text{ii}}(b)\cdot\mathbbm{1}_{q(\tau_{0})=q_{0}/2}]\leq
C|b|^{-1}\;\text{for any}\;b\geq a/10$ (5.17)

provided $K$ is large enough.

Assume that $b\leq-a/10$. Then $|b|^{-1}>K|a-bK|^{-1}$, so by Lemma 2.AA.i we
have

$\text{E}\big{[}\mathbbm{1}_{q(\tau_{0})=q_{0}/2}\cdot\text{Prob}[(\tilde{\tau}_{0}>|b|^{-1})|\mathcal{F}_{\tau_{0}}]\big{]}\leq
C\exp(-c|b|)$

provided $K$ is sufficiently large. Since

$\text{E}[\textsc{Cost}_{0.\text{ii}}\cdot\mathbbm{1}_{q(\tau_{0})=q_{0}/2}]\\\
\leq
C|b|^{-1}+C\cdot\text{E}\big{[}\mathbbm{1}_{q(\tau_{0})=q_{0}/2}\cdot\text{Prob}[(\tilde{\tau}_{0}>|b|^{-1})|\mathcal{F}_{\tau_{0}}]\big{]},$

we deduce that

$\text{E}[\textsc{Cost}_{0.\text{ii}}(b)\cdot\mathbbm{1}_{q(\tau_{0})=q_{0}/2}]\leq
C|b|^{-1}\;\text{for any}\;b\leq-a/10.$ (5.18)

If we enter Subepoch 0.ii with $q(\tau_{0})=2q_{0}$, then we set $u=Kq$ during
Subepoch 0.ii. As in the proofs of (5.17) and (5.18), we use Remark 2.A and
Lemma 2.AA.i to deduce that

$\text{E}[\textsc{Cost}_{0.\text{ii}}(b)\cdot\mathbbm{1}_{q(\tau_{0})=2q_{0}}]\leq
C|b|^{-1}\;\text{for any}\;|b|\geq a/10.$ (5.19)

Combining (5.16)–(5.19) with Lemma 3 and (5.15) proves (5.12).

###  5.2 Probability estimates for Epoch $\mu$ (for $1\leq\mu\leq\nu^{*}$)

We let $m_{0},n_{0}$ be sufficiently large positive integers so that the
conclusion of Lemma 1 holds. Note that we can take $m_{0},n_{0}$ to be
absolute constants. We fix $m_{0},n_{0}$ for the remainder of Section 5.

Recall that we defined the event $\mathcal{E}_{\nu,m}$ as

$\mathcal{E}_{\nu,m}=\\{\mathcal{E}_{\nu}\text{ AND
}(\mathcal{E}_{\mu.\text{ii}}\;\text{for exactly }m\text{ integers }\mu\text{
with }0\leq\mu<\nu)\\}.$

The purpose of the present section is to prove the following estimates:

  1. (P.I)

For any integers $\mu,m$ satisfying $2\leq\mu\leq(\nu^{*}+1)$ and $0\leq
m\leq\mu$, we have

$\text{Prob}[\mathcal{E}_{\mu,m}]\leq C\exp(-c4^{2m}e^{\mu}|b|)\;\text{for
any}\;|b|\geq ae^{-\mu+n_{0}+1}.$

  2. (P.II)

For any integers $\mu,m$ satisfying $2\leq\mu\leq(\nu^{*}+1)$ and $2\leq
m\leq\mu$ we have

$\text{Prob}[\mathcal{E}_{\mu,m}]\leq C\exp(-c4^{2m}a)\;\text{for
any}\;|b|\leq ae^{-\mu-m_{0}+1}.$

  3. (P.III)

For any integers $\mu,m$ satisfying $1\leq\mu\leq\nu^{*}$ and $0\leq
m\leq\mu$, we have

$\text{Prob}[\mathcal{E}_{\mu.\text{ii}}\;\text{AND}\;\mathcal{E}_{\mu,m}]\leq
C\exp(-c4^{2m}a)\;\text{for any}\;|b|\leq ae^{-\mu-m_{0}}.$

We first prove (P.III). Let $1\leq\mu\leq\nu^{*}$ and $0\leq m\leq\mu$. Recall
that if $t_{\mu}<T$, i.e., if Subepoch $\mu.\text{i}$ occurs, then:

  * •

Subepoch $\mu.\text{i}$ lasts until time $\tau_{\mu}$, where $\tau_{\mu}$ is
equal to the first time $t\in(t_{\mu},\min\\{T,(t_{\mu}+\tau)\\})$ for which
$|q(t)-q(t_{\mu})|\geq|q(t_{\mu})|(a\tau)^{1/2}$ if such a time exists and
equal to $\min\\{T,(t_{\mu}+\tau)\\}$ if no such time exists.

  * •

We set $u=e^{\mu}q(t_{\mu})(a\tau)^{-1/2}$ during Subepoch $\mu.\text{i}$.

  * •

If $\tau_{\mu}<\min\\{T,(t_{\mu}+\tau)\\}$, then at time $\tau_{\mu}$ we enter
Subepoch $\mu.\text{ii}$.

  * •

If $\tau_{\mu}=(t_{\mu}+\tau)<T$, then at time $\tau_{\mu}$ we enter Epoch
$(\mu+1)$.

Therefore, Lemma 1 implies that

$\text{E}[\mathbbm{1}_{\mathcal{E}_{\mu.\text{ii}}}|\mathcal{F}_{t_{\mu}}]\leq
C\exp(-c|q(t_{\mu})|^{2}a)\;\text{for any}\;|b|\leq ae^{-\mu-m_{0}}.$

Recall (see (5.2)) that if the event $\mathcal{E}_{\mu,m}$ occurs, then we
have $|q(t_{\mu})|\geq c4^{m}$ with probability 1. Since the event
$\mathcal{E}_{\mu,m}$ is $\mathcal{F}_{t_{\mu}}$-measurable, we have

$\displaystyle\text{E}[\mathbbm{1}_{\mathcal{E}_{\mu,m}}\mathbbm{1}_{\mathcal{E}_{\mu.\text{ii}}}]$
$\displaystyle=\text{E}\big{[}\mathbbm{1}_{\mathcal{E}_{\mu,m}}\cdot\text{E}[\mathbbm{1}_{\mathcal{E}_{\mu.\text{ii}}}|\mathcal{F}_{t_{\mu}}]\big{]}$
$\displaystyle\leq
C\text{E}[\mathbbm{1}_{\mathcal{E}_{\mu,m}}\exp(-c|q(t_{\mu})|^{2}a)]$
$\displaystyle\leq C\exp(-c4^{2m}a)\;\text{for any}\;|b|\leq ae^{-\mu-m_{0}}.$

This proves inequality (P.III).

We now prove (P.I). Let $\mu,m$ be integers satisfying
$2\leq\mu\leq(\nu^{*}+1)$ and $0\leq m\leq\mu$. Observe that

$\begin{split}\text{Prob}[\mathcal{E}_{\mu,m}]\leq&\text{E}[\mathbbm{1}_{\mathcal{E}_{(\mu-1),(m-1)}}\mathbbm{1}_{\mathcal{E}_{\mu,m}}]\cdot\mathbbm{1}_{m>0}\\\
&+\text{E}[\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{ii}}^{c}}\mathbbm{1}_{\mathcal{E}_{(\mu-1),m}}\mathbbm{1}_{t_{\mu-1}<(T-\tau)}]\cdot\mathbbm{1}_{0\leq
m\leq(\mu-1)}.\end{split}$ (5.20)

Assume that $0\leq m\leq(\mu-1)$. By Lemma 1, we have

$\begin{split}\mathbbm{1}_{t_{\mu-1}<T-\tau}&\cdot\text{E}[\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{ii}}^{c}}|\mathcal{F}_{t_{\mu-1}}]\\\
&\qquad\leq C\exp(-c|q(t_{\mu-1})|^{2}b^{2}e^{2\mu}/a)\;\text{for
any}\;|b|\geq ae^{-\mu+n_{0}+1}.\end{split}$ (5.21)

Since the events $\mathcal{E}_{(\mu-1),m}$ and $t_{\mu-1}<(T-\tau)$ are
$\mathcal{F}_{t_{\mu-1}}$-measurable, and since $\mathcal{E}_{(\mu-1),m}$
implies that $|q(t_{\mu-1})|>c4^{m}$ with probability 1, we use (5.21) to get

$\begin{split}\text{E}[\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{ii}}^{c}}\mathbbm{1}_{\mathcal{E}_{(\mu-1),m}}&\mathbbm{1}_{t_{\mu-1}<(T-\tau)}]\\\
=&\text{E}\big{[}\mathbbm{1}_{\mathcal{E}_{(\mu-1),m}}\mathbbm{1}_{t_{\mu-1}<(T-\tau)}\cdot\text{E}[\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{ii}}^{c}}|\mathcal{F}_{t_{\mu-1}}]\big{]}\\\
\leq&C\exp(-c4^{2m}b^{2}e^{2\mu}/a)\;\text{for any}\;|b|\geq
ae^{-\mu+n_{0}+1}.\end{split}$ (5.22)

Now assume that $0<m\leq\mu$. Recall that if $\tilde{t}_{\mu-1}<T$, i.e., if
Subepoch $(\mu-1).\text{ii}$ occurs, then

  * •

we set $u=Ke^{\mu-1}q$ during Subepoch $(\mu-1).\text{ii}$, and

  * •

Subepoch $(\mu-1).\text{iii}$ occurs if and only if we encounter
$|q|=2|q(\tilde{t}_{\mu-1})|$ during Subepoch $(\mu-1).\text{ii}$.

Similarly, if $\hat{t}_{\mu-1}<T$, i.e., if Subepoch $(\mu-1).\text{iii}$
occurs, then

  * •

we set $u=-Ke^{\mu-1}q$ during Subepoch $(\mu-1).\text{iii}$, and

  * •

Epoch $\mu$ occurs if and only if we encounter $|q|=2|q(\hat{t}_{\mu-1})|$
during Subepoch $(\mu-1).\text{iii}$.

We can therefore use Lemma 2.BB.ii to get

$\text{E}[\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{iii}}}|\mathcal{F}_{\tilde{t}_{\mu-1}}]\leq
C\exp(-c|q(\tilde{t}_{\mu-1})|^{2}e^{\mu}|b|)\;\text{for any}\;b\leq-
ae^{-\mu+n_{0}+1}$ (5.23)

and

$\text{E}[\mathbbm{1}_{\mathcal{E}_{\mu}}|\mathcal{F}_{\hat{t}_{\mu-1}}]\leq
C\exp(-c|q(\hat{t}_{\mu-1})|^{2}e^{\mu}|b|)\;\text{for any}\;b\geq
ae^{-\mu+n_{0}+1}.$ (5.24)

Since

$\mathbbm{1}_{\mathcal{E}_{\mu,m}}\mathbbm{1}_{\mathcal{E}_{(\mu-1),(m-1)}}=\mathbbm{1}_{\mathcal{E}_{\mu}}\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{iii}}}\mathbbm{1}_{\mathcal{E}_{(\mu-1).\text{ii}}}\mathbbm{1}_{\mathcal{E}_{(\mu-1),(m-1)}},$

we use (5.23), (5.24), and (5.2) to deduce that

$\text{E}[\mathbbm{1}_{\mathcal{E}_{\mu,m}}\mathbbm{1}_{\mathcal{E}_{(\mu-1),(m-1)}}]\leq
C\exp(-c4^{2m}e^{\mu}|b|)\;\text{for any}\;|b|\geq ae^{-\mu+n_{0}+1}.$ (5.25)

Combining (5.20), (5.22), (5.25) proves (P.I).

We now prove (P.II). We claim that for any $2\leq\mu\leq(\nu^{*}+1)$ and
$2\leq m\leq\mu$ we have

$\text{Prob}[\mathcal{E}_{\mu,m}]\leq C(\mu-m+1)\exp(-c4^{2m}a)\;\text{for
any}\;|b|\leq ae^{-\mu-m_{0}+1}.$ (5.26)

Since $\nu^{*}\leq Ca$, (5.26) implies (P.II).

We fix $m$ with $2\leq m\leq(\nu^{*}+1)$. Observe that for any $\mu$ with
$m\leq\mu\leq(\nu^{*}+1)$ we have

$\begin{split}\text{Prob}[\mathcal{E}_{\mu,m}]\leq\text{Prob}[\mathcal{E}_{(\mu-1).\text{ii}}\;\text{AND}&\;\mathcal{E}_{(\mu-1),(m-1)}]\\\
&+\text{Prob}[\mathcal{E}_{(\mu-1),m}]\cdot\mathbbm{1}_{\mu\geq(m+1)}.\end{split}$
(5.27)

We now show by induction that (5.26) holds for any such $\mu$.

Base Case: Inequality (5.27) and (P.III) imply that

$\text{Prob}[\mathcal{E}_{m,m}]\leq C\exp(-c4^{2m}a)\;\text{for any}\;|b|\leq
ae^{-m-m_{0}+1}.$

Induction Step: Suppose that

$\text{Prob}[\mathcal{E}_{(\mu-1),m}]\leq C(\mu-m)\exp(-c4^{2m}a)\;\text{for
any}\;|b|\leq ae^{-\mu-m_{0}+2}$ (5.28)

for some $\mu$ with $m<\mu\leq(\nu^{*}+1)$. Combining (5.28) with (5.27) and
(P.III) gives

$\text{Prob}[\mathcal{E}_{\mu,m}]\leq C(\mu-m+1)\exp(-c4^{2m}a)\;\text{for
any}\;|b|\leq ae^{-\mu-m_{0}+1}.$

This proves (5.26).

###  5.3 Expected cost during Epoch $\mu$ (for $1\leq\mu\leq\nu^{*}$)

Recall that if $t_{\mu}<T$, i.e., if Subepoch $\mu.\text{i}$ occurs, then
(with probability 1):

  * •

Subepoch $\mu.\text{i}$ lasts for at most time $\tau$.

  * •

During Subepoch $\mu.\text{i}$ we have $|q|\leq C|q(t_{\mu})|$ and
$|u|=e^{\mu}(a\tau)^{-1/2}|q(t_{\mu})|$.

Taking $\tau<a^{-1}$ (recall that $\tau$ is chosen to be sufficiently small
depending on $a$), we get

$\text{E}[\textsc{Cost}_{\mu.\text{i}}(b)|\mathcal{F}_{t_{\mu}}]\leq
Ce^{2\mu}|q(t_{\mu})|^{2}a^{-1}\;\text{for any}\;b\in\mathbb{R}.$ (5.29)

If $\tilde{t}_{\mu}<T$, i.e., if Subepoch $\mu.\text{ii}$ occurs, then during
Subepoch $\mu.\text{ii}$ we set $u=Ke^{\mu}q$ and so (with probability 1) we
have $|q|\leq 2|q(\tilde{t}_{\mu})|$ and $|u|\leq
C|q(\tilde{t}_{\mu})|e^{\mu}$. Similarly, if $\hat{t}_{\mu}<T$, then during
Subepoch $\mu.\text{iii}$ we set $u=-Ke^{\mu}q$ and so (with probability 1) we
have $|q|\leq 2|q(\hat{t}_{\mu})|$ and $|u|\leq C|q(\hat{t}_{\mu})|e^{\mu}$.
Therefore

$\displaystyle\text{E}[\textsc{Cost}_{\mu.\text{ii}}(b)|\mathcal{F}_{\tilde{t}_{\mu}}]\leq
Ce^{2\mu}|q(\tilde{t}_{\mu})|^{2}\;\text{for any}\;b\in\mathbb{R},$ (5.30)
$\displaystyle\text{E}[\textsc{Cost}_{\mu.\text{iii}}(b)|\mathcal{F}_{\hat{t}_{\mu}}]\leq
Ce^{2\mu}|q(\hat{t}_{\mu})|^{2}\;\text{for any}\;b\in\mathbb{R}.$ (5.31)

It will be useful to have sharper versions of (5.30), (5.31). We claim that
for any $|b|\geq ae^{-\mu-m_{0}}$, we have

$\displaystyle\text{E}[\textsc{Cost}_{\mu.\text{ii}}(b)|\mathcal{F}_{\tilde{t}_{\mu}}]\leq
Ce^{2\mu}a^{-1}|q(\tilde{t}_{\mu})|^{2},$ (5.32)
$\displaystyle\text{E}[\textsc{Cost}_{\mu.\text{iii}}(b)|\mathcal{F}_{\hat{t}_{\mu}}]\leq
Ce^{2\mu}a^{-1}|q(\hat{t}_{\mu})|^{2}.$ (5.33)

We prove (5.32); the proof of (5.33) is essentially identical.

We condition on the history up to time $\tilde{t}_{\mu}<T$ (if
$\tilde{t}_{\mu}=T$, then $\textsc{Cost}_{\mu.\text{ii}}=0$ and thus (5.32) is
trivial ). Recall that Subepoch $\mu.\text{ii}$ ends before time $T$ if and
only if we encounter $|q|=2|q(\tilde{t}_{\mu})|$. Provided $K$ is large enough
depending on the constant $m_{0}$, we use Remark 2.A to establish (5.32) for
$b\leq-ae^{-\mu-m_{0}}$. Lemma 2.AA.i implies (5.32) for any $b\geq 0$ (and in
particular for any $b\geq ae^{-\mu-m_{0}}$). This completes the proof of
(5.32).

####  5.3.1 The Epochs in which our guess for $b$ is too small

Assume that:

  * •

$\nu$ is an integer with $1\leq(\nu-m_{0})\leq\nu^{*}$,

  * •

$|b|\leq ae^{-\nu}$.

By (P.II), for any $2\leq\mu\leq(\nu-m_{0})$ and $2\leq m\leq\mu$ we have

$\text{Prob}[\mathcal{E}_{\mu,m}]\leq C\exp(-c4^{2m}a).$ (5.34)

Combining this with (5.29) and (5.2) gives

$\text{E}[\textsc{Cost}_{\mu.\text{i}}(b)\cdot\mathbbm{1}_{\mathcal{E}_{\mu,m}}]\leq
Ce^{2\mu}a^{-1}4^{-2m};$

therefore

$\text{E}[\textsc{Cost}_{\mu.\text{i}}(b)]=\sum_{m=0}^{\mu}\text{E}[\textsc{Cost}_{\mu.\text{i}}(b)\cdot\mathbbm{1}_{\mathcal{E}_{\mu,m}}]\leq
Ce^{2\mu}a^{-1}$ (5.35)

for any $2\leq\mu\leq(\nu-m_{0})$. Observe that (5.29) also implies that

$\text{E}[\textsc{Cost}_{1.\text{i}}(b)]\leq Ca^{-1};$ (5.36)

combining (5.35) and (5.36) gives

$\sum_{\mu=1}^{\nu-m_{0}}\text{E}[\textsc{Cost}_{\mu.\text{i}}(b)]\leq
Ce^{2\nu}a^{-1}.$ (5.37)

Now observe that, by (P.III), for any $1\leq\mu\leq(\nu-m_{0})$ and $0\leq
m\leq\mu$ we have

$\text{Prob}[\mathcal{E}_{\mu.\text{ii}}\;\text{AND}\;\mathcal{E}_{\mu,m}]\leq
C\exp(-c4^{2m}a).$ (5.38)

Recall that $\mathcal{E}_{\mu.\text{iii}}$ occurs only if
$\mathcal{E}_{\mu.\text{ii}}$ occurs. Therefore, combining (5.30), (5.31),
(5.2), and (5.38) gives

$\text{E}[(\textsc{Cost}_{\mu.\text{ii}}(b)+\textsc{Cost}_{\mu.\text{iii}}(b))\cdot\mathbbm{1}_{\\{\mathcal{E}_{\mu,m}\;\text{AND}\;\mathcal{E}_{\mu.\text{ii}}\\}}]\leq
Ce^{2\mu}a^{-1}4^{-2m},$

and we deduce that

$\text{E}[\textsc{Cost}_{\mu.\text{ii}}(b)+\textsc{Cost}_{\mu.\text{iii}}(b)]\leq
Ce^{2\mu}a^{-1}$

for any $1\leq\mu\leq(\nu-m_{0})$. Summing over $\mu$, we get

$\sum_{\mu=1}^{\nu-
m_{0}}\text{E}[\textsc{Cost}_{\mu.\text{ii}}(b)+\textsc{Cost}_{\mu.\text{iii}}(b)]\leq
Ce^{2\nu}a^{-1}.$ (5.39)

Combining (5.37) and (5.39) gives

$\sum_{\mu=1}^{\nu-m_{0}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
Ce^{2\nu}a^{-1}\;\text{for any}\;|b|\leq ae^{-\nu}.$ (5.40)

####  5.3.2 The Epochs in which our guess for $b$ is too large

Assume that:

  * •

$\nu$ is an integer with $m_{0}\leq\nu\leq(\nu^{*}-n_{0}-2)$,

  * •

$|b|\geq ae^{-\nu-1}$.

By (P.I), for any $\mu$ satisfying

$(\nu+n_{0}+2)\leq\mu\leq\nu^{*}$

and for any $0\leq m\leq\mu$ we have

$\text{Prob}[\mathcal{E}_{\mu,m}]\leq C\exp(-c4^{2m}e^{\mu}|b|).$ (5.41)

Combining (5.41) with (5.29), (5.30), (5.31), and (5.2) gives (for any such
$\mu$)

$\text{E}[\textsc{Cost}_{\mu}(b)]=\sum_{m=0}^{\mu}\text{E}[\textsc{Cost}_{\mu}(b)\cdot\mathbbm{1}_{\mathcal{E}_{\mu,m}}]\leq\frac{C}{e^{\mu}|b|^{3}}.$

Summing over $\mu$, we get

$\sum_{\mu=(\nu+n_{0}+2)}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq\frac{C}{e^{\nu}|b|^{3}}\;\text{for
any}\;|b|\geq ae^{-\nu-1};$ (5.42)

this implies

$\sum_{\mu=(\nu+n_{0}+2)}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq\frac{Ce^{2\nu}}{a}\;\text{for
any}\;|b|\geq ae^{-\nu-1}.$ (5.43)

####  5.3.3 The Epochs in which our guess for $b$ is accurate

Assume that:

  * •

$\nu$ is an integer with $(m_{0}+1)\leq\nu<(\nu^{*}+m_{0})$,

  * •

$ae^{-\nu-1}\leq|b|\leq ae^{-\nu}$,

  * •

$(\nu-m_{0}+1)\leq\mu\leq\min\\{\nu^{*},(\nu+n_{0}+1)\\}$.

Inequalities (5.32) and (5.33) imply

$\displaystyle\text{E}[\textsc{Cost}_{\mu.\text{ii}}(b)|\mathcal{F}_{\tilde{t}_{\mu}}]\leq
Ce^{2\mu}a^{-1}|q(\tilde{t}_{\mu})|^{2},$ (5.44)
$\displaystyle\text{E}[\textsc{Cost}_{\mu.\text{iii}}(b)|\mathcal{F}_{\hat{t}_{\mu}}]\leq
Ce^{2\mu}{a}^{-1}|q(\hat{t}_{\mu})|^{2}.$ (5.45)

Now observe that, by (P.II), we have

$\text{Prob}[\mathcal{E}_{\mu}\;\text{AND}\;\mathcal{E}_{(\nu-
m_{0}+1),m}]\leq\text{Prob}[\mathcal{E}_{(\nu-m_{0}+1),m}]\leq
C\exp(-c4^{2m}a)$ (5.46)

for any $2\leq m\leq(\nu-m_{0}+1)$. Combining (5.46) and (5.2) with (5.29),
(5.44), (5.45) gives (respectively)

$\text{E}[\textsc{Cost}_{\mu.j}(b)]\leq
Ce^{2\mu}a^{-1}\;\text{for}\;j=\text{i},\text{ii},\text{iii}.$

Summing over $\mu$ gives

$\sum_{\mu=(\nu-
m_{0}+1)}^{\min\\{\nu^{*},(\nu+n_{0}+1)\\}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
Ce^{2\nu}{a}^{-1}\;\text{for any}\;ae^{-\nu-1}\leq|b|\leq ae^{-\nu}.$ (5.47)

####  5.3.4 Putting it all together

Taking $\nu=(\nu^{*}+m_{0})$ in (5.40) and using Lemma 3 (recall that
$\nu^{*}\leq aT$), we deduce

$\sum_{\mu=1}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\leq
ae^{-\nu^{*}-m_{0}}.$ (5.48)

Setting $\nu=m_{0}$ in (5.43) gives

$\sum_{\mu=m_{0}+n_{0}+2}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
Ca^{-1}\;\text{for any}\;|b|\geq ae^{-m_{0}-1}.$ (5.49)

By (5.2), we have the following for any $1\leq\mu\leq(m_{0}+n_{0}+1)$: If
$t_{\mu}<T$ (resp. $\tilde{t}_{\mu}<T$, $\hat{t}_{\mu}<T$), then
$|q(t_{\mu})|<C$ (resp. $|q(\tilde{t}_{\mu})|<C$, $|q(\hat{t}_{\mu})|<C$) with
probability 1. Therefore, (5.29), (5.32), and (5.33) imply that for any
$|b|\geq ae^{-m_{0}-1}$ we have

$\text{E}[\textsc{Cost}_{\mu}(b)|\mathcal{F}_{t_{\mu}}]\leq Ca^{-1}\;\text{for
any}\;1\leq\mu\leq(m_{0}+n_{0}+1).$ (5.50)

Therefore

$\sum_{\mu=1}^{m_{0}+n_{0}+1}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
Ca^{-1}\;\text{for any}\;|b|\geq ae^{-m_{0}-1}.$ (5.51)

In particular, (5.49), (5.51) and Lemma 3 give

$\sum_{\mu=1}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;100a\geq|b|\geq
ae^{-m_{0}-1}.$ (5.52)

Recall inequality (5.5):

$\text{Prob}[\mathcal{E}_{1}]\leq C\exp(-c|b|)\;\text{for any}\;|b|\geq 100a.$

Combining this with (5.42), (5.50), and Lemma 3 gives

$\sum_{\mu=1}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\geq 100a.$ (5.53)

For any $(\nu^{*}-n_{0}-1)\leq\nu<(\nu^{*}+m_{0})$, we use (5.40), (5.47), and
Lemma 3 to get

$\sum_{\mu=1}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;ae^{-\nu-1}\leq|b|\leq
ae^{-\nu}.$ (5.54)

Similarly, we use (5.40), (5.43), (5.47) and Lemma 3 to deduce that (5.54)
also holds for any $(m_{0}+1)\leq\nu\leq(\nu^{*}-n_{0}-2)$. We conclude that

$\sum_{\mu=1}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for
any}\;ae^{-\nu^{*}-m_{0}}\leq|b|\leq ae^{-m_{0}-1}.$ (5.55)

Combining (5.48), (5.52), (5.53), and (5.55) gives

$\sum_{\mu=1}^{\nu^{*}}\text{E}[\textsc{Cost}_{\mu}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$ (5.56)

###  5.4 Performance during the Final Epoch

Recall that during Epoch $(\nu^{*}+1)$ we set $u=0$. Therefore, by Remark 2.C,
we have

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)|\mathcal{F}_{t_{(\nu^{*}+1)}}]\leq\frac{e^{2aT}}{2a}[|q(t_{(\nu^{*}+1)})|^{2}+T].$
(5.57)

For any $2\leq m\leq(\nu^{*}-m_{0}-n_{0})$, (P.II) implies that

$\text{Prob}[\mathcal{E}_{\nu^{*}+1}\;\text{AND}\;\mathcal{E}_{(\nu^{*}-m_{0}-n_{0}),m}]\\\
\leq C\exp(-c4^{2m}a)\;\text{for any}\;|b|\leq ae^{-\nu^{*}+n_{0}+1}.$ (5.58)

Combining (5.57), (5.58), and (5.2) gives

$\displaystyle\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)\cdot\mathbbm{1}_{\mathcal{E}_{(\nu^{*}-m_{0}-n_{0}),m}}]=$
$\displaystyle\text{E}\big{[}\mathbbm{1}_{\mathcal{E}_{(\nu^{*}-m_{0}-n_{0}),m}}\cdot\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)|\mathcal{F}_{t_{(\nu^{*}+1)}}]\big{]}$
$\displaystyle\leq$ $\displaystyle
Ce^{2aT}a^{-1}4^{2m}\cdot\text{E}[\mathbbm{1}_{\mathcal{E}_{\nu^{*}+1}}\cdot\mathbbm{1}_{\mathcal{E}_{(\nu^{*}-m_{0}-n_{0}),m}}]$
$\displaystyle\leq$ $\displaystyle Ce^{2aT}a^{-1}4^{-2m}\;\text{for
any}\;|b|\leq ae^{-\nu^{*}-n_{0}+1}.$

Observe that

$\mathbbm{1}_{\mathcal{E}_{\nu^{*}+1}}=\sum_{m=0}^{\nu^{*}-m_{0}-n_{0}}\mathbbm{1}_{\mathcal{E}_{\nu^{*}+1}}\cdot\mathbbm{1}_{\mathcal{E}_{(\nu^{*}-m_{0}-n_{0}),m}};$

therefore (since
$\textsc{Cost}_{\nu^{*}+1}=\mathbbm{1}_{\mathcal{E}_{\nu^{*}+1}}\cdot\textsc{Cost}_{\nu^{*}+1}$)

$\displaystyle\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
Ce^{2aT}a^{-1}\;\text{for any}\;|b|\leq ae^{-\nu^{*}+n_{0}+1}.$

Combining this with Lemma 3 (recall that $\nu^{*}=\lfloor aT\rfloor$), we get

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\leq
ae^{-\nu^{*}+n_{0}+1}.$ (5.59)

Let $-1\leq\nu\leq(\nu^{*}-n_{0}-1)$ until further notice. Use (P.I) to get
that

$\text{Prob}[\mathcal{E}_{(\nu^{*}+1),m}]\leq
C\exp(-c4^{2m}e^{(\nu^{*}-\nu)}a)\;\text{for any}\;|b|\geq ae^{-\nu-1},$

where $0\leq m\leq(\nu^{*}+1)$. Combining this with (5.57) and (5.2) gives

$\displaystyle\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)\cdot\mathbbm{1}_{\mathcal{E}_{(\nu^{*}+1),m}}]\leq
Ce^{2(aT-\nu^{*})}e^{2\nu}a^{-1}4^{-2m}\;\text{for any}\;|b|\geq ae^{-\nu-1}.$

Recall that $\nu^{*}=\lfloor aT\rfloor$, so $e^{2(aT-\nu^{*})}\leq C$. We
deduce that

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq Ce^{2\nu}a^{-1}\;\text{for
any}\;|b|\geq ae^{-\nu-1};$ (5.60)

combining this with Lemma 3 gives

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;ae^{-\nu-1}\leq|b|\leq
ae^{-\nu},$ (5.61)

where $-1\leq\nu\leq(\nu^{*}-n_{0}-1)$, and (setting $\nu=-1$ in (5.60))

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;a\leq|b|\leq 100a.$
(5.62)

Since (5.61) holds for any $-1\leq\nu\leq(\nu^{*}-n_{0}-1)$, we combine it
with (5.59) to get

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\leq a.$ (5.63)

By (P.I), we have for any $0\leq m\leq(\nu^{*}+1)$ that

$\text{Prob}[\mathcal{E}_{(\nu^{*}+1),m}]\leq
C\exp(-c4^{2m}e^{\nu^{*}}|b|)\;\text{for any}\;|b|\geq 100a.$

Combining this with (5.57) and (5.2) gives

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)\cdot\mathbbm{1}_{\mathcal{E}_{(\nu^{*}+1),m}}]\leq
C4^{-2m}|b|\;\text{for any}\;|b|\geq 100a;$ (5.64)

we conclude that

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq C|b|^{-1}\;\text{for any}\;|b|\geq
100a.$

By Lemma 3, we have

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\geq 100a.$

Combining this with (5.62) and (5.63) gives

$\text{E}[\textsc{Cost}_{\nu^{*}+1}(b)]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$ (5.65)

Together, (5.12), (5.56), and (5.65) prove Theorem 1 for $a\geq A$.

##  6 The strategy for bounded $a$

Throughout Section 6 we assume that

$|a|\leq A.$

In a moment we will define the strategy BR in this case. Throughout this
section we write $q,u$ for the particle trajectories and control variables
$q^{\text{BR}},u^{\text{BR}}$.

We now define the strategy BR; it is divided into three Epochs, only the first
of which is guaranteed to occur. At time 0 we enter Epoch 0.

Epoch $0$: During Epoch $0$ we set $u(t)=-q(t).$ Epoch $0$ lasts from time $0$
until time $t_{1}$, where $t_{1}$ is equal to the first time $t\in(0,T)$ for
which $|q(t)|=2q_{0}$ if such a time exists and is equal to $T$ if no such
time exists. If $t_{1}=T$, then at time $t_{1}$ the game ends. If $t_{1}<T$,
then at time $t_{1}$ we enter Epoch $1$.

Epoch $1$: Suppose that we enter Epoch $1$, i.e., that $t_{1}<T$. During Epoch
$1$ we set $u(t)=q(t).$ Epoch $1$ lasts from time $t_{1}$ until time $t_{2}$,
where $t_{2}$ is equal to the first time $t\in(t_{1},T)$ for which
$|q(t)|=4q_{0}$ if such a time exists and is equal to $T$ if no such time
exists. If $t_{2}=T$, then at time $t_{2}$ the game ends. If $t_{2}<T$, then
at time $t_{2}$ we enter Epoch $2$.

Note that we have only defined the stopping time $t_{2}$ in the event that
$(t_{1}<T)$. For convenience, we define $t_{2}$ to be equal to $T$ in the
event that $(t_{1}=T)$.

Epoch 2: Note that $t_{2}$ is equal to the time at which we enter Epoch 2 if
such a time exists and is equal to $T$ if no such time exists. If we enter
Epoch 2, then we set $u=0$ until the game ends at time $T$.

This concludes the definition of the strategy BR when $|a|\leq A$.

As in Section 5, we say that Epoch $\nu$ occurs if there exists some time at
which we enter Epoch $\nu$ and we let $\mathcal{E}_{\nu}$ denote the event
that Epoch $\nu$ occurs. We define a random variable $\textsc{Cost}_{\nu}(b)$
(for $\nu=0,1,2$) to be equal to the cost incurred during Epoch $\nu$ if Epoch
$\nu$ occurs and equal to 0 if Epoch $\nu$ does not occur. Observe that

$\textsc{ECost}(\text{BR},b)=\sum_{\nu=0}^{2}\text{E}[\textsc{Cost}_{\nu}(b)].$

Our goal in this section is to show that

$\textsc{ECost}(\text{BR},b)\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R};$ (6.1)

this implies Theorem 1 in the case $|a|\leq A$.

Since we set $u=0$ during Epoch 2, and since we assume that $|a|\leq A$,
Remark 2.B gives

$\text{E}[\textsc{Cost}_{2}(b)|\mathcal{F}_{t_{2}}]\leq C\;\text{for
any}\;b\in\mathbb{R}.$ (6.2)

Remark 2.B also implies that

$\text{E}[\textsc{Cost}_{0}(b)],\text{E}[\textsc{Cost}_{1}(b)]\leq
C\;\text{for any}\;|b|\leq 100A.$ (6.3)

Combining (6.2), (6.3) with Lemma 3 gives

$\textsc{ECost}(\text{BR},b)\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\leq 100A.$ (6.4)

Now, assume that $b\geq 100A$ and recall that we set $u=-q$ during Epoch 0. We
have

$\displaystyle\text{E}[\textsc{Cost}_{0}(b)]\leq C|b|^{-1}\;\text{by Remark
\ref{rmk: cg}.\ref{rmk: cg a}, and}$ (6.5)
$\displaystyle\text{Prob}[\mathcal{E}_{2}]\leq\text{Prob}[\mathcal{E}_{1}]\leq
C\exp(-c|b|)\text{ by Lemma \ref{lem: nhl}.\ref{lem: nhl biii}}.$ (6.6)

Also, since we set $u=q$ during Epoch 1, and since $|q|\leq C$ during Epoch 1,
we have

$\text{E}[\textsc{Cost}_{1}(b)]\leq
C|b|^{-1}+C\cdot\text{E}[\mathbbm{1}_{t_{1}<T-10|b|^{-1}}\cdot\text{E}[\mathbbm{1}_{t_{2}>t_{1}+|b|^{-1}}|\mathcal{F}_{t_{1}}]].$

Our assumption $b\geq 100A$ implies that $|b|^{-1}\geq 99|a+b|^{-1}/100$,
therefore we can use Lemma 2.AA.i to deduce that

$\text{E}[\mathbbm{1}_{t_{1}<T-10|b|^{-1}}\cdot\text{E}[\mathbbm{1}_{t_{2}>t_{1}+|b|^{-1}}|\mathcal{F}_{t_{1}}]]\leq
C|b|^{-1};$

we conclude that

$\text{E}[\textsc{Cost}_{1}(b)]\leq C|b|^{-1}\;\text{for any}\;b\geq 100A.$
(6.7)

Similarly, if $b\leq-100A$, then

$\displaystyle\text{E}[\textsc{Cost}_{0}(b)]\leq C|b|^{-1}\text{ by Lemma
\ref{lem: nhl}.\ref{lem: nhl ai},}$ (6.8)
$\displaystyle\text{E}[\textsc{Cost}_{1}(b)]\leq C|b|^{-1}\;\text{by Remark
\ref{rmk: cg}.\ref{rmk: cg a} and},$ (6.9)
$\displaystyle\text{Prob}[\mathcal{E}_{2}]\leq C\exp(-c|b|)\;\text{by Lemma
\ref{lem: nhl}.\ref{lem: nhl biii}}.$ (6.10)

Combining (6.5)–(6.10) with (6.2) gives

$\textsc{ECost}(\text{BR},b)\leq C|b|^{-1}\;\text{for any}\;|b|\geq 100A;$

we use Lemma 3 to deduce that

$\textsc{ECost}(\text{BR},b)\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;|b|\geq 100A.$ (6.11)

Combining (6.4), (6.11) proves (6.1).

##  7 The strategy for large, negative $a$

Throughout this section we assume that

$a\leq-A.$

In a moment, we will define the strategy BR in this case. Throughout this
section we write $q,u$ for the particle trajectories and control variables
$q^{\text{BR}},u^{\text{BR}}$.

We now define the strategy BR. It consists of three epochs, only the first two
of which are guaranteed to occur.

Epoch 0: Epoch 0 begins at time 0. During Epoch 0 we set $u=-q$. Epoch 0 lasts
until time $t_{1}$, where $t_{1}$ is equal to the first time
$t\in(0,(10|a|)^{-1})$ for which $q(t)=2q_{0}$ or $q(t)=\frac{1}{2}q_{0}$ if
such a time exists and equal to $(10|a|)^{-1}$ if no such time exists. At time
$t_{1}$ we enter Epoch 1. (Recall that $A$ was chosen so that $(10|a|)^{-1}<T$
for any $a\leq-A$; see Section 5.)

Epoch 1: If we enter Epoch 1 at time $t_{1}=(10|a|)^{-1}$, then we set $u=0$
until the game ends at time $T$.

If we enter Epoch 1 at time $t_{1}<(10|a|)^{-1}$, then with probability 1 we
have either $q(t_{1})=2q_{0}$ or $q(t_{1})=\frac{1}{2}q_{0}$.

If $q(t_{1})=2q_{0}$, then during Epoch 1 we set $u=1000\cdot q$. If
$q(t_{1})=\frac{1}{2}q_{0}$, then during Epoch 1 we set $u=-1000\cdot q$. In
either case Epoch 1 lasts until time $t_{2}$, where $t_{2}$ is equal to the
first time $t\in(t_{1},T)$ for which $|q(t)|=4q_{0}$ if such a time exists and
equal to $T$ if no such time exists. If $t_{2}<T$, then at time $t_{2}$ we
enter Epoch 2.

We have only defined the stopping time $t_{2}$ in the event that $(t_{1}<T)$.
For convenience, we define $t_{2}$ to be equal to $T$ in the event that
$(t_{1}=T)$.

Epoch 2: Note that $t_{2}$ is equal to the time at which we enter Epoch 2 if
such a time exists and is equal to $T$ if we never enter Epoch 2. If we enter
Epoch 2, then we set $u=0$ until the game ends at time $T$. (Note that if
$t_{1}=(10|a|)^{-1}$, then $t_{2}=T$ with probability 1.)

This concludes the definition of the strategy BR in the case $a\leq-A$.

As usual, we let $\mathcal{E}_{\nu}$ denote the event that Epoch $\nu$ occurs
(i.e., the event that there exists some time at which we enter Epoch $\nu$)
and we define the random variable $\textsc{Cost}_{\nu}(b)$ to be equal to the
cost incurred during Epoch $\nu$ if Epoch $\nu$ occurs and equal to 0 if Epoch
$\nu$ does not occur. Clearly

$\textsc{ECost}(\text{BR},b)=\sum_{\nu=0}^{2}\text{E}[\textsc{Cost}_{\nu}(b)].$

We first note that for any $|b|\geq 100|a|$,

$\text{Prob}[t_{1}>10|b|^{-1}]\leq\text{Prob}[t_{1}>(10|b-a|/99)^{-1}].$

Since we set $u=-q$ during Epoch 0, we can use Parts AA.i and BB.i of Lemma 2
to get

$\text{Prob}[t_{1}>10|b|^{-1}]\leq C\exp(-c|b|)\;\text{for any}\;|b|\geq
100|a|.$ (7.1)

For any $|b|\leq|a|/10$, we have that

$\text{Prob}[t_{1}<(10|a|)^{-1}]\leq\text{Prob}[t_{1}<(11|b-a|^{-1}/100)].$

Taking $A$ to be sufficiently large to ensure that $(11|b-a|^{-1}/100)<T$ for
any $|b|\leq|a|/10$, Lemma 2.C gives

$\text{Prob}[t_{1}<(10|a|)^{-1}]\leq C\exp(-c|a|)\;\text{for any
}|b|\leq|a|/10.$ (7.2)

Note that during Epoch 0 we have $|q|,|u|\leq C$ with probability 1, and
therefore

$\text{E}[\textsc{Cost}_{0}]\leq C|a|^{-1}\;\text{for any}\;b\in\mathbb{R}$
(7.3)

simply because $t_{1}\leq(10|a|)^{-1}$ with probability 1. Moreover,

$\text{E}[\textsc{Cost}_{0}]\leq
C|b|^{-1}+C\cdot\text{Prob}[t_{1}>10|b|^{-1}]\;\text{for any}\;|b|\geq
100|a|,$

and therefore (7.1) implies that

$\text{E}[\textsc{Cost}_{0}]\leq C|b|^{-1}\;\text{for any}\;|b|\geq 100|a|.$
(7.4)

Combining (7.3) and (7.4) with Lemma 3 gives

$\text{E}[\textsc{Cost}_{0}]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$ (7.5)

Recall that if we enter Epoch 1 at position $q(t_{1})=2q_{0}$, then we set
$u=1000\cdot q$ during Epoch 1, and Epoch 1 ends before time $T$ if and only
if we encounter $|q|=4q_{0}$. By Remark 2.A, we have

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{q(t_{1})=2q_{0}}]\leq
C|b|^{-1}\;\text{for any}\;b\leq-\frac{|a|}{10}.$ (7.6)

Observe that for any $b\geq|a|/10$ we have $b^{-1}\geq 100|a+1000\cdot
b|^{-1}$. Therefore we can use Lemma 2.AA.i to get

$\text{E}[\mathbbm{1}_{q(t_{1})=2q_{0}}\cdot\mathbbm{1}_{t_{1}<T-10b^{-1}}\cdot\text{E}[\mathbbm{1}_{t_{2}>t_{1}+b^{-1}}|\mathcal{F}_{t_{1}}]]\leq
C|b|^{-1}.$

Since

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{q(t_{1})=2q_{0}}]\\\ \leq
Cb^{-1}+C\text{E}[\mathbbm{1}_{q(t_{1})=2q_{0}}\cdot\mathbbm{1}_{t_{1}<T-10b^{-1}}\cdot\text{E}[\mathbbm{1}_{t_{2}>t_{1}+b^{-1}}|\mathcal{F}_{t_{1}}]],$

we conclude that

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{q(t_{1})=2q_{0}}]\leq
Cb^{-1}\;\text{for any}\;b\geq\frac{|a|}{10}.$ (7.7)

If we enter Epoch 1 at position $q(t_{1})=q_{0}/2$, then we set $u=-1000q$
during Epoch 1, and Epoch 1 ends before time $T$ if and only if we encounter
$|q|=4q_{0}$. Proceeding essentially as in the proofs of (7.6) and (7.7), we
conclude from Remark 2.A and Lemma 2.AA.i that

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{q(t_{1})=q_{0}/2}]\leq
C|b|^{-1}\;\text{for any}\;|b|\geq\frac{|a|}{10}.$ (7.8)

In the event that we enter Epoch 1 at time $t_{1}<(10|a|)^{-1}$, the random
variable $\textsc{Cost}_{1}$ is bounded above by a constant with probability
1. We therefore use (7.2) to deduce that

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{t_{1}<(10|a|)^{-1}}]\leq
C|a|^{-1}\;\text{for any}\;|b|\leq\frac{|a|}{10}.$ (7.9)

Recall that if we enter Epoch 1 at time $t_{1}=(10|a|)^{-1}$, then we set
$u=0$ until the end of the game at time $T$. By Remark 2.A, we then have

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{t_{1}=(10|a|)^{-1}}|\mathcal{F}_{t_{1}}]\leq
C|a|^{-1}\;\text{for any}\;b\in\mathbb{R}.$ (7.10)

In particular,

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{t_{1}=(10|a|)^{-1}}]\leq
C|a|^{-1}\;\text{for any}\;|b|\leq 100|a|.$ (7.11)

Using (7.1), we see also that

$\text{E}[\textsc{Cost}_{1}(b)\cdot\mathbbm{1}_{t_{1}=(10|a|)^{-1}}]\leq
C|b|^{-1}\;\text{for any}\;|b|\geq 100|a|.$ (7.12)

Combining (7.6)–(7.9), (7.11), and (7.12) with Lemma 3 gives

$\text{E}[\textsc{Cost}_{1}]\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\;b\in\mathbb{R}.$ (7.13)

Assume that $b\geq 100|a|$. By Lemma 2.BB.ii, we then have

$\displaystyle\text{Prob}[q(t_{1})=2q_{0}]\leq C\exp(-cb),$
$\displaystyle\text{Prob}[(q(t_{1})=q_{0}/2)\;\text{AND}\;(t_{2}<T)]\leq
C\exp(-cb).$

Therefore

$\text{Prob}[\mathcal{E}_{2}]\leq C\exp(-cb)\;\text{for any}\;b\geq 100|a|.$
(7.14)

Similarly, if $b\leq-100|a|$, then by Lemma 2.AA.ii we have

$\text{Prob}[q(t_{1})=q_{0}/2]\leq C\exp(-c|b|),$

and by Lemma 2.BB.ii we have

$\text{Prob}[(q(t_{1})=2q_{0})\;\text{AND}\;(t_{2}<T)]\leq C\exp(-c|b|).$

Therefore

$\text{Prob}[\mathcal{E}_{2}]\leq C\exp(-c|b|)\;\text{for any}\;b\leq-100|a|.$
(7.15)

If we enter Epoch 2, then we set $u=0$ for the remainder of the game.
Therefore, by Remark 2.A, we have

$\text{E}[\textsc{Cost}_{2}(b)|\mathcal{F}_{t_{2}}]\leq C|a|^{-1}\;\text{for
any}\;b\in\mathbb{R}.$ (7.16)

In particular,

$\text{E}[\textsc{Cost}_{2}]\leq C|a|^{-1}\;\text{for any}\;|b|\leq 100|a|.$
(7.17)

Combining (7.16) with (7.14), (7.15) gives

$\text{E}[\textsc{Cost}_{2}]\leq C|b|^{-1}\;\text{for any}\;|b|\geq 100|a|.$
(7.18)

Combining (7.5), (7.13) with (7.17), (7.18), and Lemma 3 gives

$\textsc{ECost}(\text{BR},b)\leq
C\cdot\textsc{ECost}_{\text{opt}}(b)\;\text{for any}\in b\in\mathbb{R}.$

Thus, we have succeeded in proving Theorem 1 in the case $a\leq-A$.

## References

  * [1] Karl Aström.  Introduction to Stochastic Control Theory.  Academic Press, 1970.
  * [2] Jacob Carruth, Maximilian F. Eggl, Charles Fefferman, and Clarence W. Rowley.  Controlling unknown linear dynamics with almost optimal regret.  arXiv:2309.10142, 2023.
  * [3] Jacob Carruth, Maximilian F. Eggl, Charles Fefferman, Clarence W. Rowley, and Melanie Weber.  Controlling unknown linear dynamics with bounded multiplicative regret.  Rev. Mat. Iberoam., 38(7):2185–2216, 2022.
  * [4] Jacob Carruth, Maximilian F. Eggl, Charles L Fefferman, and Clarence W. Rowley.  Optimal agnostic control of unknown linear dynamics in a bounded parameter range.  arXiv:2309.10138, 2023.
  * [5] Charles Fefferman, Bernat Guillén Pegueroles, Clarence W Rowley, and Melanie Weber.  Optimal control with learning on the fly: a toy problem.  Rev. Mat. Iberoam., 38(1):175–187, 2021.
  * [6] Daniel Gurevich, Debdipta Goswami, Charles L Fefferman, and Clarence W Rowley.  Optimal control with learning on the fly: System with unknown drift.  In Learning for Dynamics and Control Conference, pages 870–880. PMLR, 2022.