# Controlling Unknown Linear Dynamics with Almost Optimal Regret

J. Carruth, M. F. Eggl, C. Fefferman, C. W. Rowley

###### Abstract

Continuing from the companion paper [7], we consider a simple control problem
in which the underlying dynamics depend on a parameter $a$ that is unknown and
must be learned. In this paper, we assume that $a$ can be any real number and
we do not assume that we have a prior belief about $a$. We seek a control
strategy that minimizes a quantity called the regret. Given any
$\varepsilon>0$, we produce a strategy that minimizes the regret to within a
multiplicative factor of $(1+\varepsilon)$.

##  1 Introduction

Continuing from [6, 16], we explore a new flavor of adaptive control theory,
which we call “agnostic control.” 00footnotetext: This work was supported by
AFOSR grant FA9550-19-1-0005 and by the Joachim Herz Foundation.

Many works in adaptive control theory attempt to control a system whose
underlying dynamics are initially unknown and must be learned from
observation. The goal is then to bound Regret, a quantity defined by comparing
our expected cost with that incurred by an opponent who knows the underlying
dynamics. Typically one tries to achieve a regret whose order of magnitude is
as small as possible after a long time. Adaptive control theory has extensive
practical applications; see, e.g., [4, 8, 21, 29].

In some applications, we don’t have the luxury of waiting for a long time.
This is the case, e.g., for a pilot attempting to land an airplane following
the sudden loss of a wing, as in [5]. Our goal, here and in [7], is to achieve
the absolute minimum possible regret over a fixed, finite time horizon. This
poses formidable mathematical challenges, even for simple model systems.

We will study a one-dimensional, linear model system whose dynamics depend on
a single unknown parameter $a$. When $a$ is large positive, the system is
highly unstable. (There is no “stabilizing gain” for all $a$.) We suppose that
the unknown $a$ may be any real number and we don’t assume that we are given a
Bayesian prior probability distribution for it.

Modulo an arbitrarily small increase in regret, we reduce the problem to a
Bayesian variant in which the unknown $a$ is confined to a finite set and
governed by a prior probability distribution.

For the Bayesian problem, our task is to find a strategy that minimizes the
expected cost. This leads naturally to a PDE (a Bellman equation).

In [7], we prove that the optimal strategy for Bayesian control is indeed
given in terms of the solution of the Bellman equation, and that any strategy
significantly different from that optimum incurs a significantly higher cost.
We proceed modulo assumptions about existence and regularity of the relevant
PDE solutions, for which we lack rigorous proofs. (However, we have obtained
numerical solutions, which seem to behave as expected.)

Let us now explain the above in more detail.

###  1.1 The Model System

Our system consists of a particle moving in one dimension, influenced by our
control and buffeted by noise. The position of our particle at time $t$ is
denoted by $q(t)\in\mathbb{R}$. At each time $t$, we may specify a “control”
$u(t)\in\mathbb{R}$, determined by history up to time $t$, i.e., by
$(q(s))_{s\in[0,t]}$. A “strategy” (aka “policy”) is a rule for specifying
$u(t)$ in terms of $(q(s))_{s\in[0,t]}$ for each $t$. We write
$\sigma,\sigma^{\prime},\sigma^{*},\text{etc.}$ to denote strategies. The
noise is provided by a standard Brownian motion $(W(t))_{t\geq 0}$.

The particle moves according to the stochastic ODE

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

where $a$ and $q_{0}$ are real parameters. Due to the noise in (1.1), $q(t)$
and $u(t)$ are random variables.

Over a time horizon $T>0$, we incur a Cost, given222By rescaling, we can
consider seemingly different cost functions of the form
$\int_{0}^{T}(q^{2}+\lambda u^{2})$ for $\lambda>0$. by

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

This quantity is a random variable determined by $a,q_{0},T$ and our strategy
$\sigma$. Here, the starting position $q_{0}$ and time horizon $T$ are fixed
and known.

We would like to keep our cost as low as possible. We examine several variants
of the above control problem, making successively weaker assumptions regarding
our knowledge of the parameter $a$. Those variants are as follows.

### Variant I: Classical Control

We suppose first that the parameter $a$ is known. We write
$\mathcal{J}(\sigma,a;T,q_{0})$ to denote the expected Cost incurred by
executing a given strategy $\sigma$. Our task is to pick $\sigma$ to minimize
$\mathcal{J}(\sigma,a;T,q_{0})$. As shown in textbooks (e.g., [3]), the
optimal strategy $\sigma$ is given by

$u(t)=-\kappa(T-t,a)q(t)$

for a known elementary function $\kappa$; see also Section 2 below. We denote
this strategy by $\sigma_{\text{opt}}(a)$. It will be important later to note
that $\sigma_{\text{opt}}(a)$ satisfies the inequality

$|u(t)|\leq C\max\\{a,1\\}\cdot|q(t)|\;\text{for an absolute constant }C.$
(1.3)

### Variant II: Bayesian Control

Next, suppose that the parameter $a$ is unknown, but is subject to a given
prior probability distribution $d\text{Prob}(a)$ supported in an interval
$[-A,A]$. Our goal is now to pick a strategy $\sigma$ to minimize our expected
cost, given by

$\int_{-A}^{A}\mathcal{J}(\sigma,a;T,q_{0})\ d\text{Prob}(a).$ (1.4)

To solve this problem, we first note a major simplification: In principle, a
strategy $\sigma$ is a one-parameter family of functions on an infinite-
dimensional space, because it specifies $u(t)$ in terms of the path
$(q(s))_{s\in[0,t]}$ for each $t$. However, one computes that the posterior
probability distribution for the unknown $a$, given past history
$(q(s))_{s\in[0,t]}$, is determined by the prior $d\text{Prob}(a)$, together
with the two observable quantities

$\zeta_{1}(t)=\int_{0}^{t}q(s)\ dq(s)-\int_{0}^{t}q(s)u(s)\
ds,\qquad\zeta_{2}(t)=\int_{0}^{t}(q(s))^{2}\ ds.$ (1.5)

Therefore, it is natural to suppose that our optimal strategy
$\sigma_{\text{Bayes}}(d\text{Prob})$ takes the form

$u(t)=\tilde{u}(q(t),\zeta_{1}(t),\zeta_{2}(t),t)$ (1.6)

for a function $\tilde{u}$ on $\mathbb{R}^{4}$.

So, instead of looking for a one-parameter family of functions on an infinite-
dimensional space, we merely have to specify a function $\tilde{u}$ of four
variables. It isn’t hard to derive a PDE (the Bellman equation) for the
function $\tilde{u}(q,\zeta_{1},\zeta_{2},t)$ that, according to heuristic
reasoning, minimizes our expected cost. We have produced approximate solutions
$\tilde{u}$ to the Bellman equation in numerical simulations, but we don’t
have rigorous proofs of existence or regularity. We proceed by imposing the

PDE Assumption: The Bellman equation has a smooth solution, and the resulting
control strategy satisfies the estimate

$|u(t)|\leq C_{0}A^{m_{0}}[|q(t)|+1],$ (1.7)

for constants $C_{0},m_{0}$ independent of $A$.

Since our prior distribution $d\text{Prob}(a)$ is supported in $[-A,A]$, a
glance at (1.3) suggests that the optimal Bayesian strategy should satisfy

$|u(t)|\leq C\max\\{A,1\\}\cdot|q(t)|.$

Our numerical simulations appear to confirm this belief. Accordingly, (1.7)
seems to be a very safe assumption.

Under the above PDE Assumption, we prove in [7] the natural result that the
strategy $\sigma_{\text{Bayes}}(d\text{Prob})$ arising from the Bellman
equation indeed minimizes the expected cost given by (1.4). Moreover, any
strategy that differs significantly from $\sigma_{\text{Bayes}}(d\text{Prob})$
incurs a significantly higher expected cost.

Our results on Bayesian control pave the way for our analysis of agnostic
control.

### Variant III: Agnostic Control for Bounded $a$

We suppose that our parameter $a$ is confined to a bounded interval $[-A,A]$
but is otherwise unknown. In particular, we don’t assume that we are given a
Bayesian prior probability distribution $d\text{Prob}(a)$. Consequently, we
cannot define a notion of expected cost by formula (1.4).

Instead, our goal will be to minimize _worst-case regret_ , defined by
comparing the performance of our strategy with that of the optimal known-$a$
strategy $\sigma_{\text{opt}}(a)$. We will introduce several variants of the
notion of regret.

Let us fix a starting position $q_{0}$, a time horizon $T$, and an interval
$[-A,A]$ guaranteed to contain the unknown $a$. To a given strategy $\sigma$,
we associate the following functions on $[-A,A]$:

  * •

_Additive Regret_ , defined as

$\text{AR}(\sigma,a)=\mathcal{J}(\sigma,a;T,q_{0})-\mathcal{J}(\sigma_{\text{opt}}(a),a;T,q_{0})\geq
0.$

  * •

_Multiplicative Regret_ (aka “competitive ratio”), defined as

$\text{MR}(\sigma,a)=\frac{\mathcal{J}(\sigma,a;T,q_{0})}{\mathcal{J}(\sigma_{\text{opt}}(a),a;T,q_{0})}\geq
1.$

  * •

_Hybrid Regret_ , defined in terms of a parameter $\gamma>0$ by setting

$\text{HR}_{\gamma}(\sigma,a)=\frac{\mathcal{J}(\sigma,a;T,q_{0})}{\mathcal{J}(\sigma_{\text{opt}}(a),a;T,q_{0})+\gamma}$

Writing $\textsc{Regret}(\sigma,a)$ to denote any one of the above three
functions on $[-A,A]$, we define the _worst-case regret_

$\textsc{Regret}^{*}(\sigma)=\sup\\{\textsc{Regret}(\sigma,a):a\in[-A,A]\\}.$
(1.8)

We seek a strategy $\sigma$ that minimizes worst-case regret.

The above notions are useful in different regimes. If we expect to pay a large
cost, then we care more about multiplicative regret than about additive
regret. (If we have to pay $10^{9}$ dollars, we are unimpressed by a saving of
$10^{5}$ dollars.) Similarly, if our expected cost is small, then we care more
about additive regret than about multiplicative regret. (If we pay only
$10^{-5}$ dollars, we don’t care that we might instead pay $10^{-9}$ dollars.)
If we fix $\gamma$ to be a cost we are willing to neglect, then hybrid regret
$\text{HR}_{\gamma}(\sigma,a)$ provides meaningful information regardless of
the order of magnitude of our expected cost.

So far, we have defined three flavors of worst-case regret, and posed the
problem of minimizing that regret. The solution to our agnostic control
problem is given by the following result, proved in [7].

######  Theorem 1.1.

Fix $[-A,A]$, $q_{0}$, $T$ (and $\gamma$ if we use hybrid regret). Assume the
_PDE Assumption_. Then

  * _(I)_

There exists a probability measure $d\emph{Prob}_{*}$ on $[-A,A]$ for which
the optimal Bayesian strategy $\sigma_{\emph{Bayes}}(d\emph{Prob}_{*})$
minimizes the worst-case regret among all possible strategies.
Moreover,

  * _(II)_

The measure $d\emph{Prob}_{*}$ is supported on a finite set $E\subset[-A,A]$,
where

  * _(III)_

$E$ is precisely the set of points $a\in[-A,A]$ at which the function
$[-A,A]\ni a\mapsto\textsc{Regret}(\sigma_{\emph{Bayes}}(d\emph{Prob}_{*}),a)$
achieves its maximum.

So, for optimal agnostic control, we should pretend to believe that the
unknown $a$ is confined to a finite set $E$ and governed by the probability
distribution $d\text{Prob}_{*}$, even though in fact we know nothing about $a$
except that it lies in $[-A,A]$.

It is easy to see that a probability distribution $d\text{Prob}_{*}$
satisfying (II) and (III) gives rise to a Bayesian strategy satisfying (I).
The hard part of Theorem 1.1 is the assertion that such a probability measure
exists.

Theorem 1.1 lets us search for optimal agnostic strategies: We first guess a
finite set $E$ and a probability measure $d\text{Prob}$ concentrated on $E$.
By solving the Bellman equation, we produce the strategy
$\sigma=\sigma_{\text{Bayes}}(d\text{Prob})$, which allows us to compute the
function $[-A,A]\ni a\mapsto\textsc{Regret}(\sigma,a)$. If the maxima of that
function occur precisely at the points of $E$, then $\sigma$ is the desired
optimal agnostic strategy. We have carried this out numerically for several
$[-A,A],q_{0},T$.

This concludes our discussion of agnostic control for bounded $a$. Finally, we
pass to the most general case.

### Variant IV: Fully Agnostic Control

We make no assumption whatever regarding the unknown $a$; our $a$ may be any
real number, and we are not given a Bayesian prior distribution for it.

Our goal is again to find a strategy that minimizes the _worst-case regret_ ,
defined as in (1.8), except that the $\sup$ is now taken over all
$a\in\mathbb{R}$.

The main result of this paper is that, with negligible increase in regret, we
can reduce matters to agnostic control for bounded $a$. More precisely, we
will prove the following result.

######  Theorem 1.2.

Fix a time horizon $T$ and a nonzero starting position $q_{0}$, as well as
constants $C_{0},m_{0}$ (for which, see (1.7)). Then given $\varepsilon>0$
there exists $A>0$ for which the following holds.

Let $\sigma$ be a strategy for the starting position $q_{0}$ and time horizon
$T+\varepsilon$. Suppose $\sigma$ satisfies estimate (1.7) for the given
$C_{0},m_{0},A$.

Then there exists a strategy $\sigma_{*}$ for the starting position $q_{0}$
and time horizon $T$, satisfying the following estimates.

  * _(A)_

For $a\in[-A,A]$ we have

$\mathcal{J}(\sigma_{*},a;T,q_{0})\leq\varepsilon+(1+\varepsilon)\sup\\{\mathcal{J}(\sigma,a^{\prime};T+\varepsilon,q_{0}):|a^{\prime}-a|\leq\varepsilon|a|\\}.$

  * _(B)_

For $a\notin[-A,A]$ we have

$\mathcal{J}(\sigma_{*},a;T,q_{0})\leq\varepsilon+(1+\varepsilon)\mathcal{J}(\sigma_{\emph{opt}}(a),a;T,q_{0}).$

So, if $a\in[-A,A]$, then $\sigma_{*}$ performs almost as well as $\sigma$;
and if $a\notin[-A,A]$, then $\sigma_{*}$ performs almost as well as the
optimal known-$a$ strategy $\sigma_{\text{opt}}(a)$.

To apply Theorem 1.2, we take $\sigma$ to be an optimal agnostic strategy for
the starting position $q_{0}$ and the time horizon $T+\varepsilon$, assuming
$a$ to be confined to the interval $[-(1+\varepsilon)A,+(1+\varepsilon)A]$.

If our _PDE Assumption_ holds, then $\sigma$ satisfies the hypothesis of
Theorem 1.2. It’s easy to deduce from Theorem 1.2 that the worst-case hybrid
regret of the strategy $\sigma_{*}$ (for fully agnostic control) is at most
$O(\varepsilon)$ percent worse than that of $\sigma$ (for agnostic control
with $a$ confined to $[-(1+\varepsilon)A,(1+\varepsilon)A]$).

For any $\gamma>0$ and any strategy $\sigma$ for time horizon $T$ and starting
position $q_{0}$ we let $\text{HR}_{\gamma}^{*}(\sigma;T)$ denote the worst-
case hybrid regret (over all $a\in\mathbb{R}$) of $\sigma$. The above
discussion then implies the following.

######  Corollary 1.1.

Fix constants $T>0$, $\eta>0$, $q_{0}\neq 0$. Assume the _PDE Assumption_.
Then for any $\varepsilon>0$ we can construct a strategy $\sigma_{\emph{Ag}}$
for time horizon $T$ and starting position $q_{0}$ satisfying

$\emph{HR}_{\gamma}^{*}(\sigma_{\emph{Ag}};T)\leq(1+C\varepsilon)\cdot\emph{HR}_{\gamma}^{*}(\sigma;T+\varepsilon)$

for any strategy $\sigma$ for time horizon $T+\varepsilon$ and starting
position $q_{0}$.

There are variants of Theorem 1.2 and Corollary 1.1 for the case of starting
position $q_{0}=0$; see Corollary 2.1.

### Recap

Let us summarize what has been achieved.

Our goal is to minimize worst-case regret in the setting where $a$ may be any
real number. Modulo an arbitrarily small increase in regret, we may reduce
matters to the case in which $a$ is confined to a bounded interval $[-A,A]$.
We then look for a probability measure $d\text{Prob}_{*}$ living on a finite
subset $E\subset[-A,A]$ such that the regret of the optimal Bayesian strategy
for $d\text{Prob}_{*}$ is maximized precisely on $E$. We can calculate the
optimal Bayesian strategy for a given prior probability measure by solving a
Bellman equation. However, our results are conditional; we have to make an
assumption on the existence, size, and smoothness of solutions to the Bellman
equation. In numerical simulations, we have produced evidence for our _PDE
Assumption_ , and we have produced optimal agnostic strategies for cases in
which the unknown $a$ is confined to a bounded interval.

###  1.2 Ideas from the Proof of Theorem 1.2

Recall that in Theorem 1.2 we are given a strategy $\sigma$, a small positive
$\varepsilon$, and a large positive $A$ depending on $\varepsilon$. The
strategy $\sigma$ applies to a starting position $q_{0}\neq 0$, and a time
horizon $T+\varepsilon$. Our task is to find a strategy $\sigma_{*}$
satisfying conditions (A) and (B).

In this introduction, we allow ourselves some inaccuracy in the interest of
simplicity. See Sections 5–7 for correct details.

A recurring theme in the proof of Theorem 1.2 is that because the unknown $a$
may be arbitrarily large and positive, the system may be arbitrarily unstable.
Consequently, disasters of exponentially small probability may lead to
exponentially large expected cost.

To prepare the way for the proof of Theorem 1.2, we first examine two regimes
in which we can do almost as well as if we knew the value of $a$.

### The Large $q$ Regime

Suppose $q_{0}$ is very large. A glance at (1.1) suggests that the noise
$dW(t)$ has only a small effect compared to that of the term $(aq+u)dt$.
Therefore, after initially setting $u\equiv 0$ and observing $q(t)$ for small
$t$, we quickly arrive at a guess $\bar{a}$ for the unknown $a$. That guess is
probably highly accurate. Moreover, the larger $a$ is, the sooner we can
arrive at the guess $\bar{a}$.

Once we have found $\bar{a}$, we can simply play the known-a strategy
$\sigma_{\text{opt}}(\bar{a})$ until the end of the game at time $T$. (If
$\bar{a}$ is large positive, then in place of $\sigma_{\text{opt}}(\bar{a})$,
we use the strategy in which $u(t)=-2\bar{a}q(t)$, which is equivalent to
$\sigma_{\text{opt}}(\bar{a})$ asymptotically for $\bar{a}\gg 1$.)

This “Large $q$ strategy” incurs an expected cost almost as small as that of
an opponent who knows $a$.

A crucial point is that for large positive $a$, the probability of a
significantly inaccurate guess $\bar{a}$ is $O(\exp(-cq_{0}^{2}a))$, while the
expected cost if such an error occurs is $O(q_{0}^{2}\exp(CTa))$. Hence, for
large $q_{0}$, the exponentially tiny probability of disaster overwhelms the
exponentially large resulting cost.

### The Large $a$ Regime

As in our discussion of the Large $q$ strategy, a glance at (1.1) suggests
that the nosie $dW(t)$ will have negligibly small effect compared to that of
the term $(aq+u)dt$, provided $a$ is large positive, say, $a\geq A$. This
leads to a “naïve large $a$ strategy” in which we initially set $u\equiv 0$,
observe $q(t)$ for small $t$, arrive at a guess $\bar{a}$ for the unknown $a$,
and then play the known-a strategy $\sigma_{\text{opt}}(\bar{a})$ until the
game ends at time $T$.

This time, however, the exponentially small probability of an error of the
form $\bar{a}\ll a$ is dominated by the exponentially large cost of the
ensuing disaster. Consequently, the naïve large $a$ strategy fails. The cure
is to pick some $q_{0}^{*}$, big but not too big, and execute the naïve large
$a$ strategy only until the first moment we encounter $|q(t)|=q_{0}^{*}$. At
that moment, we switch over to the Large $q$ strategy. If we never encounter
$|q(t)|=q_{0}^{*}$, then we continue with the naïve large $a$ strategy until
the end of the game.

The above modification limits the damage arising from the event $\bar{a}\ll
a$. We have thus produced a “Large $a$ strategy” whose expected cost is close
to that of the optimal known-a strategy $\sigma_{\text{opt}}(a)$ whenever
$a\geq A$. When $a<A$, the expected cost of our Large $a$ strategy is
$O(A^{2})$. That’s bigger than we’d like, but it isn’t exponentially large.

### Strengthening the Given Strategy

Next, we consider the strategy $\sigma$ given in the statement of Theorem 1.2.
Recall that $\sigma$ is assumed to satisfy the estimate (1.7). From that
estimate we see at once that $\sigma$ disastrously undercontrols in case $a\gg
A^{m_{0}}$, leading to exponentially large expected cost. We can remedy this
defect, by modifying $\sigma$ the same way we modified the naïve large $a$
strategy. We pick a $q_{0}^{*}$, large but not too large, and switch over from
$\sigma$ to the Large $q$ strategy as soon as we encounter $|q(t)|=q_{0}^{*}$.
Thus, we obtain a strategy $\tilde{\sigma}$ that performs almost as well as
$\sigma$ for $a\in[-A,A]$, and avoids exponentially large expected cost if
$a>A$.

Like $\sigma$, the strategy $\tilde{\sigma}$ starts at position $q_{0}$. By
rescaling $\tilde{\sigma}$ slightly, we arrive at a strategy $\bar{\sigma}$
with starting position $(1+\varepsilon)q_{0}$. Like $\tilde{\sigma}$, the
strategy $\bar{\sigma}$ performs almost as well as $\sigma$ when $a\in[-A,A]$,
and avoids exponentially large expected cost when $a>A$.

Armed with the Large $q$ and Large $a$ strategies, and the modified strategy
$\bar{\sigma}$, we can now describe the strategy $\sigma_{*}$ whose existence
is asserted by Theorem 1.2. Without loss of generality, we suppose that our
nonzero starting position $q_{0}$ is positive.

In the strategy $\sigma_{*}$ there are two epochs, a Prologue and a Main Act.
During the Prologue, we set $u\equiv 0$. The Prologue ends as soon as we
encounter one of the three events

  1. (a)

$q(t)=(1+\varepsilon)q_{0}$

  2. (b)

$q(t)=-q_{\text{rare}}$ for a suitable $q_{\text{rare}}>0$ (big but not too
big)

  3. (c)

the end of the game at time $T$ (in which case there is no Main Act).

Event (b) occurs with small probability, regardless of the unknown $a$. If it
does occur, then during the Main Act we play a slight variant of the Large $q$
strategy to bound our losses.

If instead we enter the Main Act via case (a), then by observing how long it
took to pass from the initial position $q_{0}$ to the position
$(1+\varepsilon)q_{0}$, we obtain a guess $\bar{a}$ for the unknown $a$. If
$a$ is large positive, then as in our discussion of the Large $a$ strategy,
our guess $\bar{a}$ is probably highly accurate. Otherwise, $\bar{a}$ is
likely not so close to $a$, but at least $\bar{a}$ probably won’t be large
positive. Therefore, for large $A$, our guess $\bar{a}$ will at least tell us
whether $a\gtrsim A$ or $a\ll A$. Accordingly, in case (a) we proceed as
follows during the Main Act.

  * •

If $\bar{a}>A$, then during the Main Act we execute the Large $a$ strategy.

  * •

If $\bar{a}\leq A$, then during the Main Act we execute $\bar{\sigma}$, the
improved version of the given strategy $\sigma$.

The Main Act lasts until the end of the game at time $T$.

This completes our description of the strategy $\sigma_{*}$. We hope the
reader finds it plausible that our $\sigma_{*}$ satisfies conditions (A) and
(B) in Theorem 1.2.

We again warn the reader that our discussion in this introduction is somewhat
oversimplified. For instance, our basic stochastic ODE (1.1) isn’t obviously
well-defined if our strategy allows $u(t)$ to be a discontinuous function of
$t$. We haven’t even given a rigorous definition of a strategy. Our rigorous
discussion starts from scratch in Section 2.

### Survey of Prior Literature

Literature that considers adaptive control of a simple linear system similar
to the one considered in this paper commonly consists of one or more of the
following features: (_i_) unknown governing dynamics, (_ii_) unknown cost
function and (_iii_) adversarial noise. Examples of such work include [24, 26,
33, 18, 11, 25, 14] as well as our own prior work [16], [6].

Initial work in obtaining regret bounds in the infinite time horizon for the
related LQR (linear-quadratic regulator) problem was undertaken in [1], which
proved that under certain assumptions, the expected additive regret of the
adaptive controller is bounded by $\tilde{O}(\sqrt{T})$. Further progress was
made on this problem in [9]. Assuming controllability of the system, the
authors gave the first efficient algorithm capable of attaining sublinear
additive regret in a single trajectory in the setting of online nonstochastic
control. See also the related [28], which obtained sublinear adaptive regret
bounds, a stronger metric than standard regret and more suitable for time-
varying systems. Additional adaptive control approaches include [12, 13] using
the system level synthesis. This expands on ideas in [31], which showed that
the ordinary least-squares estimator learns a linear system nearly optimally
in one shot. Other work uses Thompson Sampling [2, 23] or deep learning [10].
Perhaps most related to the work performed in this study is [22], which
designed an online learning algorithm with sublinear expected regret that
moves away from episodic estimates of the state dynamics (meaning that no
boundedness or initially stabilizing control needed to be assumed).

In [16], the third and fourth authors of the present paper, along with B.
Guillén Pegueroles and M. Weber, found regret minimizing strategies for a
problem with simple unknown dynamics (a particle moving in one-dimension at a
constant, unknown velocity subject to Brownian motion). In [20], along with D.
Goswami and D. Gurevich, they generalized these results to an analogous,
higher-dimensional system with the addition of sensor noise. In [16], they
also posed the problem of finding regret minimizing strategies for the more
complicated dynamics (1.1). In [6], the authors of the present paper, along
with M. Weber, took the first steps toward resolving this problem.
Specifically, we exhibited a strategy for the dynamics (1.1) with bounded
multiplicative regret.

Historically, significant work has been undertaken in the closely related
“multi-armed bandit” problem; see, for instance, the classic papers [30, 32].
Recent work considering this paradigm includes [34], which used reinforcement
learning to obtain dynamic regret whose order of magnitude is optimal, and
[15], which studied the more general Generalized Linear Bandits (GLBs) and
obtains similar regret bounds.

We finally want to point out the parallel field of adversarial control, where
the noise profile is chosen by an adversary instead of randomly. This includes
[27], which attained minimum dynamic regret and guaranteed compliance with
hard safety constraints in the face of uncertain disturbance realizations
using the system level synthesis framework, and [19], which studied the
problem of competitive control.

As this list of references is by no means exhaustive and does not do justice
to the wealth of studies in the literature, we point the reader to the book
[21] and the references therein for a more thorough overview of online
control.

We emphasize that our approach in [16], [6], and the present paper differs
from the other work cited above in that:

  * •

We seek strategies that minimize the worst-case regret for a fixed time
horizon $T$, whereas the literature is mainly concerned with
$T\rightarrow\infty$.

  * •

Typically in the literature one assumes either that the dynamics are bounded
or that one is given a stabilizing control. We make no such assumptions and so
we must control a system that is arbitrarily unstable.

  * •

However, we achieve the above ambitious goals only for a simple model system.

We thank Amir Ali Ahmadi, Brittany Hamfeldt, Elad Hazan, Robert Kohn, Sam
Otto, Allan Sly, and Melanie Weber for helpful conversations. We are grateful
to the Air Force Office of Scientific Research, and Frederick Leve, for their
generous support. The second named author thanks the Joachim Herz foundation
for support.

##  2 Setup

Except for where we explicitly state otherwise, we adopt the following
conventions regarding constants throughout this paper. We write
$C,C^{\prime},C^{\prime\prime},\dots$ to denote positive absolute constants.
When we wish to specify that a positive absolute constant is smaller than 1,
we write $c,c^{\prime},c^{\prime\prime},\dots$. If a constant depends on some
quantity $X$, then we write $C_{X},C^{\prime}_{X},c_{X},c^{\prime}_{X},\dots$.
The values of these constants may change from line to line.

Whenever we say that a parameter/constant depends on other
parameters/constants, we assume that the dependence is continuous unless we
explicitly state otherwise.

We let $W(t)$ denote Brownian motion starting at $W(0)=0$ and normalized so
that $\text{E}[(W(t))^{2}]=t$. We write $(\Omega,\mathcal{F},\text{Prob})$ for
the corresponding probability space and $\text{E}[X]$ for the expected value
of a random variable $X$. We write $\omega$ to denote an arbitrary element of
$\Omega$. For $t\in[0,T]$, we write $\mathcal{F}_{t}$ to denote the sigma
algebra determined by the history of the Brownian motion from time 0 until
time $t$.

We introduce a _time horizon_ $T>0$ and a _starting position_ $q_{0}\neq 0$.
We define a _strategy_ (for time horizon $T$ and starting position $q_{0}$) to
be a collection of random variables $q(t,a)$, $u(t,a)$ defined for all
$t\in[0,T]$ and $a\in\mathbb{R}$ and satisfying the following:

  1. (S.1)

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

  2. (S.2)

For every $a\in\mathbb{R}$ and $t\in[0,T]$ the maps $(s,\omega)\mapsto
q(s,a,\omega)$ and $(s,\omega)\mapsto u(s,a,\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 $a\in\mathbb{R}$,

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

  4. (S.4)

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

  5. (S.5)

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

$q(t,a)=q_{0}+W(t)+\int_{0}^{t}[aq(\tau,a)+u(\tau,a)]\ d\tau$

with probability 1.

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

We remark that any strategy for time horizon $T$ and starting position $q_{0}$
gives rise to a strategy for time horizon $T^{\prime}$ and starting position
$q_{0}$ for any $T^{\prime}\in(0,T)$ (simply by restricting the time domain).

We will use $\sigma$ to denote an arbitrary strategy. We then write
$q^{\sigma}$ and $u^{\sigma}$ to denote the families of particle trajectories
and control variables associated with $\sigma$.

For any strategy $\sigma$ we define a random variable

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

This random variable is well-defined because with probability 1 $q(t,a)$ is a
continuous function of $t$ and $u(t,a)$ is an $L^{2}$ function of $t$. We then
define the _expected cost_ of $\sigma$ by

$\mathcal{J}(\sigma,a;T,q_{0})=\text{E}[\textsc{Cost}(\sigma,a)].$

For any smooth function $v:[0,T]\rightarrow\mathbb{R}$ we define a strategy
$\sigma_{v}$ by setting

$\displaystyle
q^{\sigma_{v}}(t,a)=q_{0}+W(t)+\int_{0}^{t}(a-v(\tau))q^{\sigma_{v}}(\tau,a)\
d\tau,$ (2.1) $\displaystyle u^{\sigma_{v}}(t,a)=-v(t)q^{\sigma_{v}}(t,a).$
(2.2)

We refer to $\sigma_{v}$ as a _simple feedback strategy_ with _gain function_
$v$.

For $\alpha\in\mathbb{R}$, $s\geq 0$ we define

$\kappa(s,\alpha)=\frac{\tanh(s\sqrt{\alpha^{2}+1})}{\sqrt{\alpha^{2}+1}-\alpha\tanh(s\sqrt{\alpha^{2}+1})}.$

We let $\sigma_{\text{opt}}(\alpha)$ denote the simple feedback strategy with
gain function $t\mapsto\kappa(T-t,\alpha)$. In Section 3, we will show that
for any $a\in\mathbb{R}$, the strategy $\sigma_{\text{opt}}(a)$ minimizes the
quantity $\mathcal{J}(\sigma,a;T,q_{0})$ over all strategies $\sigma$. We
therefore refer to the family of strategies
$(\sigma_{\text{opt}}(\alpha))_{\alpha\in\mathbb{R}}$ as _optimal known- $a$_
(or just known-$a$) strategies. For ease of notation we define

$\mathcal{J}_{0}(a;T,q_{0})=\mathcal{J}(\sigma_{\text{opt}}(a),a;T,q_{0});$

we refer to $\mathcal{J}_{0}(a;T,q_{0})$ as the _optimal expected cost for
known $a$_ (for time horizon $T$ and starting position $q_{0}$).

Fix a real number $C_{0}$ and an integer $m_{0}\geq 1$. We say that a strategy
$\sigma$ (for time horizon $\hat{T}$) is _$A$ -bounded_ for some $A>0$ if

$|u^{\sigma}(t,a)|\leq C_{0}A^{m_{0}}[|q^{\sigma}(t,a)|+1]\;\text{for
all}\;a\in\mathbb{R},t\in[0,\hat{T}].$

Recall that we assume that our starting position $q_{0}$ is nonzero.

######  Theorem 2.1.

Let $\varepsilon>0$. Then for $A>0$ sufficiently large depending on
$\varepsilon,T,q_{0},C_{0},m_{0}$, the following holds.

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon$ and
starting position $q_{0}$. Then the strategy $\sigma_{*}$ for time horizon $T$
and starting position $q_{0}$ specified in Section 5.2 satisfies the
following.

  1. 1.

If $a\in[-A,A]$, then

$\mathcal{J}(\sigma_{*},a;T,q_{0})<\varepsilon+(1+\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon,q_{0}):|a-b|<\varepsilon|a|\\}.$

  2. 2.

If $|a|>A$, then

$\mathcal{J}(\sigma_{*},a;T,q_{0})<\varepsilon+(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0}).$

We now state a corollary of Theorem 2.1; this is the variant of Theorem 1.2
for starting position $q_{0}=0$ mentioned in the Introduction. The proof of
this corollary is given in Section 5.4.

######  Corollary 2.1.

Let $\varepsilon>0$. Then for $A>0$ sufficiently large depending on
$\varepsilon,T,C_{0},m_{0}$, the following holds.

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon$ and
starting position $\varepsilon$. Then the strategy $\hat{\sigma}_{*}$ for time
horizon $T$ and starting position $0$ specified in Section 5.4 satisfies the
following.

  1. 1.

If $a\in[-A,A]$, then

$\mathcal{J}(\hat{\sigma}_{*},a;T,0)<\varepsilon+(1+\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon,\varepsilon):|a-b|<\varepsilon|a|\\}.$

  2. 2.

If $|a|>A$, then

$\mathcal{J}(\hat{\sigma}_{*},a;T,0)<\varepsilon+(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,0).$

We remark that Corollary 2.1 implies a variant of Corollary 1.1 for $q_{0}=0$,
but we don’t state it here.

Our proof of Theorem 2.1 makes use of two additional strategies. These
strategies, defined in Sections 6 and 7, respectively, are almost optimal when
$|q_{0}|$ and $a$ are large. Specifically, we prove the following theorems.

######  Theorem 2.2.

Let $\varepsilon>0$. Then there exists $q_{\text{big}}\geq 1$ depending
(continuously) on $\varepsilon,T$ such that the following is true. For any
$q_{0}\geq q_{\text{big}}$, let $\emph{L}q\emph{S}$ be the strategy for time
horizon $T$ and starting position $q_{0}$ defined in Section 6 depending on
$\varepsilon,T,q_{0}$. Then

$\mathcal{J}(\emph{L}q\emph{S},a;T,q_{0})\leq(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})\;\emph{for
any}\;a\in\mathbb{R}.$

In our previous paper [6], we exhibited a strategy $\text{BR}_{0}$ satisfying

$\mathcal{J}(\text{BR}_{0},a;T,0)<C_{T}\cdot\mathcal{J}_{0}(a;T,0)\;\text{for
any}\;a\in\mathbb{R}.$

By making a simple modification to the strategy $\text{L}q\text{S}$ in Theorem
2.2 we can produce, for any $q_{0}\in\mathbb{R}$, a strategy BR satisfying

$\mathcal{J}(\text{BR};a,T,q_{0})<C_{T,q_{0}}\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R};$

we refer to this as a bounded regret strategy for starting position $q_{0}$.

######  Theorem 2.3.

Let $\varepsilon>0$ and let $\emph{L}a\emph{S}$ be the strategy for time
horizon $T$ and starting position $q_{0}$ defined in Section 7 depending on
$\varepsilon,T,q_{0}$. Then for any $A\geq A_{\min}(\varepsilon,T,q_{0})$ we
have

$\mathcal{J}(\emph{L}a\emph{S},a;T,q_{0})\leq(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\geq A$

and

$\mathcal{J}(\emph{L}a\emph{S},a;T,q_{0})\leq C_{T,q_{0}}\cdot
A^{2}\;\text{for any}\;a\leq A.$

##  3 Preliminary results on strategies

We begin this section by stating some properties of strategies.

######  Remark 3.1.

By symmetry, any strategy $\sigma$ for time horizon $T$ and starting position
$q_{0}$ gives rise to a strategy $\sigma_{-}$ for time horizon $T$ and
starting position $-q_{0}$ defined by

$\displaystyle q^{\sigma_{-}}(t,a)=-q^{\sigma}(t,a),\qquad
u^{\sigma_{-}}(t,a)=-u^{\sigma}(t,a)$

and satisfying

$\mathcal{J}(\sigma,a;T,q_{0})=\mathcal{J}(\sigma_{-},a;T,-q_{0}).$

For the remainder of this paper we assume, without loss of generality, that
$q_{0}>0$; this is justified by Remark 3.1.

######  Remark 3.2 (Rescaling property).

Let $\sigma$ be a strategy for time horizon $T$ and starting position $q_{0}$
with particle trajectories $q^{\sigma}(t,a)$ and control variables
$u^{\sigma}(t,a)$. Let $\lambda>0$ and define the rescaled random variables

$\displaystyle\tilde{q}(t,a)=\lambda\cdot
q^{\sigma}\bigg{(}\frac{t}{\lambda^{2}},\lambda^{2}a\bigg{)},\qquad\tilde{u}(t,a)=\frac{1}{\lambda}\cdot
u^{\sigma}\bigg{(}\frac{t}{\lambda^{2}},\lambda^{2}a\bigg{)},$
$\displaystyle\tilde{W}(t)=\lambda\cdot
W\bigg{(}\frac{t}{\lambda^{2}}\bigg{)}.$

Note that $\tilde{W}(t)$ is a standard Brownian motion and that for any
$a\in\mathbb{R}$, $t\in[0,\lambda^{2}T]$ we have

$\tilde{q}(t,a)=\lambda
q_{0}+\tilde{W}(t)+\int_{0}^{t}[a\tilde{q}(\tau,a)+\tilde{u}(\tau,a)]\ d\tau$

with probability 1. It follows that $\tilde{q}(t,a)$, $\tilde{u}(t,a)$
determine a strategy for time horizon $\lambda^{2}T$ and starting position
$\lambda q_{0}$. Denoting this strategy by $\sigma_{\lambda}$, we have

$\displaystyle\mathcal{J}(\sigma_{\lambda},a;\lambda^{2}T,\lambda q_{0})$
$\displaystyle=\emph{E}\bigg{[}\int_{0}^{\lambda^{2}T}\big{(}\tilde{q}^{2}(t,a)+\tilde{u}^{2}(t,a)\big{)}dt\bigg{]}$
$\displaystyle=\emph{E}\bigg{[}\int_{0}^{T}\big{(}\lambda^{4}\cdot(q^{\sigma}(t,\lambda^{2}a))^{2}+(u^{\sigma}(t,\lambda^{2}a))^{2}\big{)}dt\bigg{]}$
$\displaystyle\leq\max\\{\lambda^{4},1\\}\cdot\mathcal{J}(\sigma,\lambda^{2}a;T,q_{0}).$

We say that $\sigma_{\lambda}$ is a _rescaling_ of the strategy $\sigma$. Note
that the rescaled strategy $\sigma_{1}$ is equal to the original strategy
$\sigma$.

######  Remark 3.3 (Branching strategies).

We will often decide to switch from one strategy to another.

To explain how we do that, recall that we denote strategies by $\sigma$,
$\sigma^{\prime}$, $\hat{\sigma}$, etc. We introduce the notion of a
_parametrized strategy_ , denoted $\sigma(\cdot)$. For each parameter value
$\alpha\in\mathbb{R}^{d}$ (some $d\geq 0$), $\sigma(\alpha)$ is a strategy.
(When $d=0$, a parametrized strategy is just a strategy.) For instance, the
strategy $\sigma_{\emph{\text{opt}}}(\beta)$ for time horizon $T$ and starting
position $q_{0}$ is a parametrized strategy; $\beta,T,q_{0}$ are the
parameters. We remark that the parameter $\alpha$ will often include our guess
for the unknown $a$.

Now suppose we are given parametrized strategies $\sigma_{0}(\cdot)$,
$\sigma_{1}(\cdot)$,…, $\sigma_{N}(\cdot)$. We will combine the $\sigma$’s
into a new parametrized strategy $\sigma^{\\#}$ (a _branching strategy_).
Suppose we are given a parameter value $\alpha$ and that $\sigma_{0}(\alpha)$
is a strategy for some time horizon $T$ and starting position $q_{0}$. The
strategy $\sigma^{\\#}(\alpha)$ is then also a strategy for time horizon $T$
and starting position $q_{0}$.

For each $a\in\mathbb{R}$, we pick a stopping time $\tau(a,\alpha)\leq T$
depending on $\alpha$ and satisfying the following: for any
$a,b\in\mathbb{R}$, $t\in[0,T]$, and $\omega\in\Omega$, if
$q^{\sigma_{0}(\alpha)}(s,a,\omega)=q^{\sigma_{0}(\alpha)}(s,b,\omega)$ for
all $s\in[0,t]$ then $\tau(a,\alpha,\omega)>t$ if and only if
$\tau(b,\alpha,\omega)>t$. Note that this condition ensures that the stopping
times are defined only in terms of $q$ and cannot use knowledge of the unknown
$a$. The strategy $\sigma^{\\#}(\alpha)$ proceeds as follows.

Until time $\tau(a,\alpha)$, we execute the strategy $\sigma_{0}(\alpha)$. If
$\tau(a,\alpha)=T$, then we are done.

If $\tau(a,\alpha)<T$, then we will pick a new parametrized strategy
$\hat{\sigma}(\cdot)$ and a new parameter $\hat{\alpha}$. The
$\hat{\sigma}(\cdot)$ will be one of our given parametrized strategies
$\sigma_{1}(\cdot)$, …, $\sigma_{N}(\cdot)$. Our choice of
$\hat{\sigma}(\cdot)$ and $\hat{\alpha}$ is determined by $\alpha$, the
history up to time $\tau(a,\alpha)$, and the requirement that
$\hat{\sigma}(\hat{\alpha})$ is a strategy for starting position
$\hat{q}_{0}=q(\tau(a,\alpha))$ and some time horizon
$\hat{T}\geq(T-\tau(a,\alpha))$.

Once we have picked $\hat{\sigma}(\cdot)$ and $\hat{\alpha}$, we forget the
past, regard $t=\tau(a,\alpha)$ as if we were at $t=0$, and execute the
strategy $\hat{\sigma}(\hat{\alpha})$, starting at position $\hat{q}_{0}$. We
stop playing at time $T$.

Thus, we have combined our parametrized strategies $\sigma_{0}(\cdot)$,
$\sigma_{1}(\cdot),$ …, $\sigma_{N}(\cdot)$ into a branching (parametrized)
strategy $\sigma^{\\#}(\cdot)$.

We may then combine our $\sigma^{\\#}(\cdot)$ with additional parametrized
strategies to form further branching strategies.

We note that the strategies $\sigma_{*}$ and $\tilde{\sigma}$ constructed in
Section 5, the strategy $\text{L}q\text{S}$ constructed in Section 6, and the
strategy $\text{L}a\text{S}$ constructed in Section 7 are all examples of
branching strategies.

###  3.1 Optimal known-$a$ strategies

Let $a\in\mathbb{R}$. In Section 2, we defined the optimal expected cost for
known $a$ by

$\mathcal{J}_{0}(a;T,q_{0})=\mathcal{J}(\sigma_{\text{opt}}(a),a;T,q_{0}),$

where $\sigma_{\text{opt}}(a)$ is the simple feedback strategy with gain
function

$\kappa(T-t,\alpha)=\frac{\tanh((T-t)\sqrt{\alpha^{2}+1})}{\sqrt{\alpha^{2}+1}-\alpha\tanh((T-t)\sqrt{\alpha^{2}+1})};$
(3.1)

recall that we refer to $\sigma_{\text{opt}}(a)$ as an optimal known-$a$
strategy. Observe that (for fixed $\alpha$) $\kappa$ solves a Riccati
equation:

$\frac{d\kappa}{dt}(t,\alpha)=[1+2a\kappa(t,\alpha)-\kappa^{2}(t,\alpha)].$

For $t\in[0,T]$ we define

$K(t,\alpha)=\int_{0}^{t}\kappa(s,\alpha)\ ds.$ (3.2)

Clearly, we have (again for fixed $\alpha$)

$\frac{dK}{dt}(t,\alpha)=\kappa(t,\alpha).$

It is well-known (see, for example, [3]) that

$\mathcal{J}_{0}(a;T,q_{0})=\kappa(T,a)\cdot q_{0}^{2}+K(T,a).$ (3.3)

This implies the following remark.

######  Remark 3.4.

Let $0<q_{0}^{\prime}<q_{0}^{\prime\prime}$. Then

$\mathcal{J}_{0}(a;T,q_{0}^{\prime})<\mathcal{J}_{0}(a;T,q_{0}^{\prime\prime})<\bigg{(}\frac{q_{0}^{\prime\prime}}{q_{0}^{\prime}}\bigg{)}^{2}\mathcal{J}_{0}(a;T,q_{0}^{\prime})\;\text{for
any}\;a\in\mathbb{R}.$

Combining (3.1) and (3.2) and evaluating the resulting integral, we get

$K(T,a)=\big{(}a+\sqrt{a^{2}+1}\big{)}T+\log\bigg{(}\frac{\sqrt{a^{2}+1}-a}{2\sqrt{a^{2}+1}}\bigg{)}\\\
+\log\bigg{(}1+e^{-2T\sqrt{a^{2}+1}}\bigg{(}\frac{\sqrt{a^{2}+1}+a}{\sqrt{a^{2}+1}-a}\bigg{)}\bigg{)}.$

Note that for any $\varepsilon>0$, there exists $A>0$ depending on
$\varepsilon$ and the time horizon $T$ such that:

  * •

For $a>A$, we have

$\displaystyle|\kappa(T,a)-2a|<\varepsilon a,$ (3.4)
$\displaystyle|K(T,a)-2aT|<\varepsilon aT.$ (3.5)

  * •

For $a<-A$, we have

$\displaystyle\bigg{|}\kappa(T,a)-\frac{1}{2|a|}\bigg{|}\leq\frac{\varepsilon}{|a|},$
(3.6) $\displaystyle\bigg{|}K(T,a)-\frac{T}{2|a|}\bigg{|}\leq\frac{\varepsilon
T}{|a|}.$ (3.7)

From (3.3)–(3.7), we deduce that for any $\varepsilon>0$, there exists $A>0$
depending on $\varepsilon$ and $T$ such that

$\displaystyle|\mathcal{J}_{0}(a;T,q_{0})-2a(q_{0}^{2}+T)|<\varepsilon
a(q_{0}^{2}+T)\;\text{when}\;a>A,\;\text{and}$ (3.8)
$\displaystyle\bigg{|}\mathcal{J}_{0}(a;T,q_{0})-\frac{1}{2|a|}(q_{0}^{2}+T)\bigg{|}<\frac{\varepsilon}{|a|}(q_{0}^{2}+T)\;\text{when}\;a<-A.$
(3.9)

Now let $\varepsilon>0$ be arbitrary and introduce $\delta>0$ sufficiently
small depending on $\varepsilon,T,q_{0}$. Suppose that $T^{\prime}>0$ and
$q_{0}^{\prime}\in\mathbb{R}$ satisfy
$|T-T^{\prime}|,|q_{0}-q_{0}^{\prime}|<\delta$. We claim that

$|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|\\\
<\varepsilon\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R},|a-a^{\prime}|<|a|\delta.$ (3.10)

By (3.8) and (3.9) above, there exists $A>0$ depending on $\varepsilon,T$ such
that:

  1. 1.

For any $a,a^{\prime}>A$, we have

$\displaystyle|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-2a^{\prime}((q_{0}^{\prime})^{2}+T^{\prime})|<\varepsilon
a^{\prime}((q_{0}^{\prime})^{2}+T^{\prime})$ (3.11)
$\displaystyle|\mathcal{J}_{0}(a;T,q_{0})-2a(q_{0}^{2}+T)|<\varepsilon
a(q_{0}^{2}+T).$ (3.12)

  2. 2.

For any $a,a^{\prime}<-A$, we have

$\displaystyle\bigg{|}\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\frac{1}{2|a^{\prime}|}((q_{0}^{\prime})^{2}+T^{\prime})\bigg{|}<\frac{\varepsilon}{|a^{\prime}|}((q_{0}^{\prime})^{2}+T^{\prime}),$
(3.13)
$\displaystyle\bigg{|}\mathcal{J}_{0}(a;T,q_{0})-\frac{1}{2|a|}(q_{0}^{2}+T)\bigg{|}<\frac{\varepsilon}{|a|}(q_{0}^{2}+T).$
(3.14)

Combining (3.11), (3.12), and using the assumptions $|T-T^{\prime}|<\delta$
and $|q_{0}-q_{0}^{\prime}|<\delta$, we get

$|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|<C_{T,q_{0}}\cdot
a\cdot(\varepsilon+\delta)\\\ \text{for any}\;a\geq 2A,\;|a-a^{\prime}|<\delta
a.$

Taking $\delta$ sufficiently small depending on $\varepsilon$, we use (3.12)
to deduce that (for $A$ sufficiently large depending on $\varepsilon$ and $T$)
we have

$\begin{split}|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|<C^{\prime}_{T,q_{0}}\cdot\varepsilon\cdot&\mathcal{J}_{0}(a;T,q_{0})\\\
&\text{for any}\;a\geq 2A,\;|a-a^{\prime}|<\delta a.\end{split}$ (3.15)

Similarly, we use (3.13), (3.14) to deduce that

$|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|<C^{\prime}_{T,q_{0}}\cdot\varepsilon\cdot\mathcal{J}_{0}(a;T,q_{0})\\\
\text{for any}\;a\leq-2A,|a-a^{\prime}|<\delta|a|.$ (3.16)

Note that (3.15) and (3.16) imply that for a sufficiently large number
$\tilde{A}>A$ depending on $\varepsilon$, $T$, $q_{0}$, we have

$|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|\\\
<\varepsilon\cdot\mathcal{J}(a;T,q_{0})\;\text{for any}\;|a|\geq
2\tilde{A},|a-a^{\prime}|<\delta|a|.$ (3.17)

Next, we note that (3.3) implies that $\mathcal{J}_{0}(a;T,q_{0})$ is of the
form

$\mathcal{J}_{0}(a;T,q_{0})=f_{1}(a,T)q_{0}^{2}+f_{2}(a,T)$

for smooth functions
$f_{1},f_{2}:\mathbb{R}\times(0,\infty)\rightarrow(0,\infty)$ independent of
$q_{0}$. Therefore (since $\tilde{A}$ is determined by $\varepsilon$, $T$,
$q_{0}$), we have

$|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|<C_{\varepsilon,T,q_{0}}\cdot\delta\\\
\text{for any}\;|a|,|a^{\prime}|\leq
3\tilde{A}\;\text{and}\;|a-a^{\prime}|<\delta|a|$

and

$\mathcal{J}_{0}(a;T,q_{0})>c_{\varepsilon,T,q_{0}}\;\text{for any}\;|a|\leq
3\tilde{A}.$

Combining the last two inequalities gives

$\begin{split}|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|<C_{\varepsilon,T,q_{0}}&\cdot\delta\cdot\mathcal{J}_{0}(a;T,q_{0})\\\
&\text{for any}\;|a|\leq 2\tilde{A},|a-a^{\prime}|<\delta|a|.\end{split}$
(3.18)

Combining (3.15), (3.16), (3.18), and taking $\delta$ sufficiently small
depending on $\varepsilon,T,q_{0}$ proves (3.10).

We summarize the above discussion (specifically (3.3), (3.8), (3.9), and
(3.10)) as a lemma.

######  Lemma 3.1.

The optimal expected cost for known $a$, $\mathcal{J}_{0}$, has the following
properties:

  1. 1.

$\mathcal{J}_{0}(a;T,q_{0})=\kappa(T,a)\cdot q_{0}^{2}+K(T,a).$

  2. 2.

For any $\varepsilon>0$, there exists $A>0$ depending on $\varepsilon$ and $T$
such that

$\displaystyle|\mathcal{J}_{0}(a;T,q_{0})-2a(q_{0}^{2}+T)|<\varepsilon
a(q_{0}^{2}+T)\;\text{when}\;a>A,\;\text{and}$ (3.19)
$\displaystyle\bigg{|}\mathcal{J}_{0}(a;T,q_{0})-\frac{1}{2|a|}(q_{0}^{2}+T)\bigg{|}<\frac{\varepsilon}{|a|}(q_{0}^{2}+T)\;\text{when}\;a<-A.$
(3.20)

  3. 3.

Let $\varepsilon>0$. Let $\delta>0$ be sufficiently small depending on
$\varepsilon$, $T$, $q_{0}$, and suppose that $T^{\prime}>0$ and
$q_{0}^{\prime}\in\mathbb{R}$ satisfy $|T-T^{\prime}|<\delta$ and
$|q_{0}-q_{0}^{\prime}|<\delta$. Then for any $a\in\mathbb{R}$ we have

$|\mathcal{J}_{0}(a^{\prime};T^{\prime},q_{0}^{\prime})-\mathcal{J}_{0}(a;T,q_{0})|<\varepsilon\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;|a-a^{\prime}|<|a|\delta.$

The next lemma says that the strategy $\sigma_{\text{opt}}(a)$ is indeed
optimal for known $a$, i.e., for fixed $a\in\mathbb{R}$ the strategy
$\sigma_{\text{opt}}(a)$ minimizes the quantity
$\mathcal{J}(\sigma,a;T,q_{0})$.

######  Lemma 3.2.

Let $\sigma$ be an arbitrary strategy for time horizon $T$ and starting
position $q_{0}$. Then

$\mathcal{J}(\sigma,a;T,q_{0})\geq\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$

###### Proof.

We suppose that $N\gg 1$ is a sufficiently large integer depending on $a,T$;
we write $c,c^{\prime},C,C^{\prime},\dots$ to denote constants determined by
$a,T$. The symbols $c,c^{\prime},C,C^{\prime},\dots$ may denote different
constants in different occurrences.

We set $h=T/N$ and for $\nu=0,\dots,N$ we set $t_{\nu}=\nu h$.

By downward induction on $\nu$, we will show that

$\text{E}\bigg{[}\int_{t_{\nu}}^{T}((q(s))^{2}+(u(s))^{2})\
ds\bigg{|}\mathcal{F}_{t_{\nu}}\bigg{]}\cdot(1+h^{1/100})\\\
\geq\kappa(T-t_{\nu},a)(q(t_{\nu}))^{2}+K(T-t_{\nu},a)-h^{1/100}(T-t_{\nu}).$
(3.21)

Once we prove (3.21), we take $\nu=0$ and let $N\rightarrow\infty$ to derive
the conclusion of the lemma. So our task is to prove (3.21). We begin our
induction on $\nu$.

In the base case $\nu=N$, (3.21) holds since $\kappa(0,a)=K(0,a)=0$.

For the induction step, we fix $\nu$ ($0\leq\nu<N)$, and assume the inductive
hypothesis

$\text{E}\bigg{[}\int_{t_{\nu+1}}^{T}((q(s))^{2}+(u(s))^{2})\
ds\bigg{|}\mathcal{F}_{t_{\nu+1}}\bigg{]}\cdot(1+h^{1/100})\\\
\geq\kappa(T-t_{\nu+1},a)\cdot(q(t_{\nu+1}))^{2}+K(T-t_{\nu+1},a)-h^{1/100}(T-t_{\nu+1}).$
(3.22)

Our goal is then to prove (3.21) assuming (3.22).

Recall that our Brownian motion is denoted by $(W(t))_{t\geq 0}$.

We set

$\displaystyle\Delta W_{\nu}=W(t_{\nu+1})-W(t_{\nu}),$ (3.23)
$\displaystyle\omega(\nu)=\sup\\{|W(t)-W(t_{\nu})|:t\in[t_{\nu},t_{\nu+1}]\\},$
(3.24) $\displaystyle||u||_{\nu}=\bigg{(}\int_{t_{\nu}}^{t_{\nu+1}}u^{2}\
ds\bigg{)}^{1/2},$ (3.25)
$\displaystyle\bar{u}_{\nu}=\frac{1}{h}\int_{t_{\nu}}^{t_{\nu+1}}u\ ds.$
(3.26)

For the rest of the proof, we condition on $\mathcal{F}_{t_{\nu}}$, and we
write $\text{E}[\cdots]$ to denote the expectation conditioned on
$\mathcal{F}_{t_{\nu}}$.

We have

$\text{E}[\Delta W_{\nu}]=0,\quad\text{E}[(\Delta
W_{\nu})^{2}]=h,\quad\text{E}[(\omega(\nu))^{2}]\leq Ch,$ (3.27)

and

$h|\bar{u}_{\nu}|^{2}\leq||u||_{\nu}^{2};$ (3.28)

more generally,

$\bigg{|}\int_{t_{\nu}}^{t}u\ ds\bigg{|}\leq
h^{1/2}||u||_{\nu}\;\text{for}\;t\in[t_{\nu},t_{\nu+1}].$ (3.29)

By the definition of a strategy, we have

$q(t)-q(t_{\nu})=[W(t)-W(t_{\nu})]+aq(t_{\nu})(t-t_{\nu})+\int_{t_{\nu}}^{t}a[q(s)-q(t_{\nu})]\
ds\\\ +\int_{t_{\nu}}^{t}u\ ds\;\text{for}\;t\in[t_{\nu},t_{\nu+1}].$ (3.30)

Setting

$\text{osc}(\nu)=\sup\\{|q(t)-q(t_{\nu})|:t\in[t_{\nu},t_{\nu+1}]\\},$ (3.31)

we deduce that

$\text{osc}(\nu)\leq\omega(\nu)+|aq(t_{\nu})|h+|a|\text{osc}(\nu)\cdot
h+h^{1/2}||u||_{\nu}.$

Since $h$ is less than a small enough constant determined by $a$, we may
absorb the term $|a|\text{osc}(\nu)h$ into the left-hand side above, to
conclude that

$\text{osc}(\nu)\leq C\omega(\nu)+Ch\cdot|aq(t_{\nu})|+Ch^{1/2}||u||_{\nu}.$
(3.32)

From (3.31), (3.32), we see that

$|q(t)-q(t_{\nu})|\leq
C\omega(\nu)+Ch|q(t_{\nu})|+Ch^{1/2}||u||_{\nu}\;\text{for}\;t\in[t_{\nu},t_{\nu+1}],$

hence

$\int_{t_{\nu}}^{t_{\nu+1}}q^{2}\
ds\geq(1-Ch^{1/10})(q(t_{\nu}))^{2}h-Ch^{9/10}(\omega(\nu))^{2}-Ch^{19/10}||u||_{\nu}^{2}.$
(3.33)

Also, (3.30), (3.31), (3.32) yield

$\displaystyle q(t_{\nu+1})=(1+ah)q(t_{\nu})+\Delta
W_{\nu}+\bar{u}_{\nu}h+\text{ERR}(\nu),\;\text{with}$ (3.34)
$\displaystyle|\text{ERR}(\nu)|\leq
Ch\omega(\nu)+Ch^{2}|q(t_{\nu})|+Ch^{3/2}||u||_{\nu}.$ (3.35)

Using (3.34), (3.35), we estimate

$(q(t_{\nu+1}))^{2}=[(1+ah)q(t_{\nu})+\Delta
W_{\nu}+\bar{u}_{\nu}h]^{2}+(\text{ERR}(\nu))^{2}\\\
+2[(1+ah)q(t_{\nu})+\Delta W_{\nu}+\bar{u}_{\nu}h]\cdot(\text{ERR}(\nu)).$
(3.36)

We have

$\begin{split}|[(1+a&h)q(t_{\nu})+\Delta
W_{\nu}+\bar{u}_{\nu}h]\cdot(\text{ERR}(\nu))|\\\
\leq&C[|q(t_{\nu})|+\omega(\nu)+h^{1/2}||u||_{\nu}]\cdot[h\omega(\nu)+h^{2}|q(t_{\nu})|+Ch^{3/2}||u||_{\nu}]\\\
\leq&Ch^{2}|q(t_{\nu})|^{2}+Ch(\omega(\nu))^{2}+Ch^{2}||u||_{\nu}^{2}+Ch^{3/2}|q(t_{\nu})|\cdot||u||_{\nu}\\\
&+Ch|q(t_{\nu})|\omega(\nu)+Ch^{3/2}||u||_{\nu}\omega(\nu).\end{split}$ (3.37)

Into (3.37) we substitute the estimates

$\displaystyle h^{3/2}|q(t_{\nu})|\cdot||u||_{\nu}\leq
Ch^{3/2}|q(t_{\nu})|^{2}+Ch^{3/2}||u||_{\nu}^{2},$ $\displaystyle
h|q(t_{\nu})|\omega(\nu)\leq
Ch^{5/4}|q(t_{\nu})|^{2}+Ch^{3/4}(\omega(\nu))^{2},\;\text{and}$
$\displaystyle h^{3/2}||u||_{\nu}\omega(\nu)\leq
Ch^{3/2}||u||_{\nu}^{2}+Ch^{3/2}(\omega(\nu))^{2}.$

We find that

$|[(1+ah)q(t_{\nu})+\Delta W_{\nu}+\bar{u}_{\nu}h]\cdot\text{ERR}(\nu)|\\\
\leq
Ch^{5/4}|q(t_{\nu})|^{2}+Ch^{3/2}||u||_{\nu}^{2}+Ch^{3/4}(\omega(\nu))^{2}.$

Consequently, (3.36) implies the estimate

$\begin{split}(q(t_{\nu+1}))^{2}\geq&[(1+ah)q(t_{\nu})+\Delta
W_{\nu}+\bar{u}_{\nu}h]^{2}-Ch^{5/4}|q(t_{\nu})|^{2}\\\
&-Ch^{3/2}||u||_{\nu}^{2}-Ch^{3/4}(\omega(\nu))^{2}\\\
=&\\{(1+ah)^{2}-Ch^{5/4}\\}(q(t_{\nu}))^{2}+(\Delta
W_{\nu})^{2}+\bar{u}_{\nu}^{2}h^{2}\\\ &+2(1+ah)q(t_{\nu})\Delta
W_{\nu}+2(1+ah)q(t_{\nu})\bar{u}_{\nu}h+2\Delta W_{\nu}\bar{u}_{\nu}h\\\
&-Ch^{3/2}||u||_{\nu}^{2}-Ch^{3/4}(\omega(\nu))^{2}.\end{split}$ (3.38)

Since

$\displaystyle|\Delta W_{\nu}\bar{u}_{\nu}h|$ $\displaystyle\leq|\Delta
W_{\nu}|\cdot h^{1/2}||u||_{\nu}$ $\displaystyle\leq Ch^{1/2}|\Delta
W_{\nu}|^{2}+Ch^{1/2}||u||_{\nu}^{2}$ $\displaystyle\leq
Ch^{1/2}(\omega(\nu))^{2}+Ch^{1/2}||u||_{\nu}^{2},$

estimate (3.38) implies the following:

$\begin{split}(q(t_{\nu+1}))^{2}\geq&\\{(1+ah)^{2}-Ch^{5/4}\\}(q(t_{\nu}))^{2}+(\Delta
W_{\nu})^{2}\\\ &+2(1+ah)q(t_{\nu})\Delta
W_{\nu}+2(1+ah)q(t_{\nu})\bar{u}_{\nu}h-Ch^{1/2}||u||_{\nu}^{2}\\\
&-Ch^{1/2}(\omega(\nu))^{2}.\end{split}$ (3.39)

Recall that we are conditioning on $\mathcal{F}_{t_{\nu}}$, so that
$q(t_{\nu})$ is deterministic. From (3.27) and (3.39) we therefore learn that

$\begin{split}\text{E}[(q(t_{\nu+1}))^{2}]\geq&(1+2ah-
Ch^{5/4})(q(t_{\nu}))^{2}+h+2h(1+ah)q(t_{\nu})\text{E}[\bar{u}_{\nu}]\\\
&-Ch^{1/2}\text{E}[||u||_{\nu}^{2}]-Ch^{3/2},\end{split}$ (3.40)

while (3.27) and (3.33) yield

$\begin{split}\text{E}\bigg{[}\int_{t_{\nu}}^{t_{\nu+1}}q^{2}\
ds\bigg{]}\geq&h(1-Ch^{1/10})(q(t_{\nu}))^{2}-Ch^{19/10}\text{E}[||u||_{\nu}^{2}]\\\
&-Ch^{19/10}.\end{split}$ (3.41)

We bring the inductive assumption (3.22) into play. Thanks to (3.22), (3.40),
(3.41), we have

$\begin{split}\text{E}\bigg{[}\int_{t_{\nu}}^{T}&(q^{2}+u^{2})\
ds\bigg{]}\cdot(1+h^{1/100})\\\
=&\text{E}\bigg{[}\int_{t_{\nu}}^{t_{\nu+1}}q^{2}\
ds\bigg{]}\cdot(1+h^{1/100})+\text{E}\bigg{[}\int_{t_{\nu}}^{t_{\nu+1}}u^{2}\
ds\bigg{]}\cdot(1+h^{1/100})\\\
&+\text{E}\bigg{[}\text{E}\bigg{[}\int_{t_{\nu+1}}^{T}(q^{2}+u^{2})\
ds\bigg{|}\mathcal{F}_{t_{\nu+1}}\bigg{]}\cdot(1+h^{1/100})\bigg{]}\\\
\geq&\\{h(1-Ch^{1/10})(1+h^{1/100})(q(t_{\nu}))^{2}-Ch^{19/10}\text{E}[||u||_{\nu}^{2}]-Ch^{19/10}\\}\\\
&+\\{\text{E}[||u||_{\nu}^{2}](1+h^{1/100})\\}\\\
&+\\{\kappa(T-t_{\nu+1},a)\text{E}[(q(t_{\nu+1}))^{2}]+K(T-t_{\nu+1},a)-h^{1/100}(T-t_{\nu+1})\\}\\\
\geq&h\Big{(}1+\frac{1}{2}h^{1/100}\Big{)}(q(t_{\nu}))^{2}+\text{E}\Big{[}||u||_{\nu}^{2}\Big{(}1+\frac{1}{2}h^{1/100}\Big{)}\Big{]}-Ch^{19/10}\\\
&+\kappa(T-t_{\nu+1},a)\Big{\\{}(1+2ah-
Ch^{5/4})(q(t_{\nu}))^{2}+h+2h(1+ah)q(t_{\nu})\text{E}[\bar{u}_{\nu}]\\\
&\qquad-
Ch^{1/2}\text{E}[||u||_{\nu}^{2}]-Ch^{3/2}\Big{\\}}+K(T-t_{\nu+1},a)-h^{1/100}(T-t_{\nu+1}),\end{split}$

and consequently,

$\begin{split}\text{E}\bigg{[}\int_{t_{\nu}}^{T}(q^{2}+&u^{2})\
ds\bigg{]}(1+h^{1/100})\\\
\geq&\Big{\\{}\kappa(T-t_{\nu+1},a)+h[2a\kappa(T-t_{\nu+1},a)+1]+\frac{1}{4}h^{101/100}\Big{\\}}(q(t_{\nu}))^{2}\\\
&+\text{E}[||u||_{\nu}^{2}+2h(1+ah)\kappa(T-t_{\nu+1},a)q(t_{\nu})\bar{u}_{\nu}]\\\
&+\\{K(T-t_{\nu+1},a)-h^{1/100}(T-t_{\nu+1})+\kappa(T-t_{\nu+1},a)h-Ch^{3/2}\\}\end{split}$
(3.42)

Now, recalling (3.28), we see that

$\begin{split}||u||_{\nu}^{2}+2h(1+ah)\kappa(T-t_{\nu+1},&a)q(t_{\nu})\bar{u}_{\nu}\\\
\geq&\bar{u}_{\nu}^{2}h+2h(1+ah)\kappa(T-t_{\nu+1},a)q(t_{\nu})\bar{u}_{\nu}\\\
=&h(\bar{u}_{\nu}+(1+ah)\kappa(T-t_{\nu+1},a)q(t_{\nu}))^{2}\\\
&-h(1+ah)^{2}\kappa^{2}(T-t_{\nu+1},a)(q(t_{\nu}))^{2}\\\
\geq&-h(1+ah)^{2}\kappa^{2}(T-t_{\nu+1},a)(q(t_{\nu}))^{2}.\end{split}$

Therefore, from (3.42), we have

$\begin{split}\text{E}\bigg{[}\int_{t_{\nu}}^{T}&(q^{2}+u^{2})\
ds\bigg{]}\cdot(1+h^{1/100})\\\
\geq&\Big{\\{}\kappa(T-t_{\nu+1},a)+h[1+2a\kappa(T-t_{\nu+1},a)\\\
&\qquad-(1+ah)^{2}\kappa^{2}(T-t_{\nu+1},a)]+\frac{1}{4}h^{101/100}\Big{\\}}(q(t_{\nu}))^{2}\\\
&+\\{K(T-t_{\nu+1},a)-h^{1/100}(T-t_{\nu+1})\\\
&\qquad+\kappa(T-t_{\nu+1},a)h-Ch^{3/2}\\}.\end{split}$ (3.43)

Recall that

$\frac{d}{dt}[\kappa(T-t,a)]=-[1+2a\kappa(T-t,a)-\kappa^{2}(T-t,a)]$

and that

$\frac{d}{dt}[K(T-t,a)]=-\kappa(T-t,a).$

Therefore the expressions in curly brackets on the right in (3.43) are bounded
below, respectively, by $\kappa(T-t_{\nu},a)$ and by

$K(T-t_{\nu})-h^{1/100}(T-t_{\nu+1})-Ch^{3/2}.$

Consequently, (3.43) implies the estimate

$\begin{split}\text{E}\bigg{[}\int_{t_{\nu}}^{T}(q^{2}+&u^{2})\
ds\bigg{]}\cdot(1+h^{1/100})\\\
\geq&\kappa(T-t_{\nu},a)\cdot(q(t_{\nu}))^{2}+K(T-t_{\nu},a)-h^{1/100}(T-t_{\nu+1})-Ch^{3/2}\\\
\geq&\kappa(T-t_{\nu},a)\cdot(q(t_{\nu}))^{2}+K(T-t_{\nu},a)-h^{1/100}(T-t_{\nu}).\end{split}$
(3.44)

Recalling that $\text{E}[\cdots]$ here denotes expectation conditioned on
$\mathcal{F}_{t_{\nu}}$, we see that (3.44) is precisely our desired
inequality (3.21).

This completes our downward induction on $\nu$, proving the lemma. ∎

###  3.2 The expected cost of simple feedback strategies

Let $v:[0,T]\rightarrow\mathbb{R}$ be a smooth function and let $\sigma_{v}$
denote the simple feedback strategy for time horizon $T$ and starting position
$q_{0}$ with gain function $v:[0,T]\rightarrow\mathbb{R}$ (see Section 2 for
the definition of a simple feedback strategy). We fix some $a\in\mathbb{R}$
and let $q$ denote the particle trajectory $q^{\sigma_{v}}(\cdot,a)$. Note
that $q$ solves the stochastic ODE

$dq=(a-v)qdt+dW,\qquad q(0)=q_{0}$ (3.45)

and that

$\mathcal{J}(\sigma_{v},a;T,q_{0})=\text{E}\bigg{[}\int_{0}^{T}q^{2}(\tau)\big{(}1+v^{2}(\tau)\big{)}\
d\tau\bigg{]}.$ (3.46)

Define a (smooth) function $\phi:[0,T]\rightarrow\mathbb{R}$ by

$\phi(t)=\int_{t}^{T}\big{(}1+v^{2}(\tau)\big{)}\exp\bigg{(}2\int_{t}^{\tau}\big{(}a-v(s)\big{)}\
ds\bigg{)}d\tau;$

$\phi$ solves the ODE

$-\phi^{\prime}(t)=2\phi(t)(a-v(t))+1+v^{2}(t),\qquad\phi(T)=0.$ (3.47)

By Itô’s Lemma we have

$d(q^{2}\phi)=[\phi^{\prime}q^{2}+\phi]dt+(2q\phi)dq.$

Combining this with (3.45) and (3.47) gives

$d(q^{2}\phi)=[-(1+v^{2})q^{2}+\phi]dt+(2\phi q)dW.$ (3.48)

With probability 1, we have

$\int_{0}^{T}d(q^{2}\phi)=q^{2}(T)\phi(T)-q^{2}(0)\phi(0)=-q_{0}^{2}\phi(0);$

combining this with (3.48) gives

$\int_{0}^{T}q^{2}(\tau)(1+v^{2}(\tau))\
d\tau=\phi(0)q_{0}^{2}+\int_{0}^{T}\phi(\tau)\
d\tau+\int_{0}^{T}2\phi(\tau)q(\tau)\ dW_{\tau}.$ (3.49)

Taking expectation and using (3.46), we get

$\mathcal{J}(\sigma_{v},a;T,q_{0})=\phi(0)q_{0}^{2}+\int_{0}^{T}\phi(\tau)\
d\tau.$

We summarize the above result as a lemma.

######  Lemma 3.3.

Let $v:[0,T]\rightarrow\mathbb{R}$ be a smooth function and let $\sigma_{v}$
be the simple feedback strategy with gain function $v$. Then

$\mathcal{J}(\sigma_{v},a;T,q_{0})=\phi(0)\cdot
q_{0}^{2}+\int_{0}^{T}\phi(s)ds,$

where

$\phi(t)=\int_{t}^{T}(1+v^{2}(s))\exp\bigg{(}2\int_{t}^{s}(a-v(r))dr\bigg{)}ds.$

Let $\alpha\geq 0$ be a real number. We define the _constant gain strategy_
$\text{CG}(\alpha)$ to be the simple feedback strategy with the constant gain
function $v(t)\equiv\alpha$. We remark that $\text{CG}(\alpha)$ is independent
of the time horizon $T$ and the starting position $q_{0}$.

Lemma 3.3 then implies that for any $a\in\mathbb{R}$ we have

$\mathcal{J}(\text{\text{CG}}(\alpha),a;T,q_{0})=(1+\alpha^{2})\Big{[}\frac{1}{2(a-\alpha)}\Big{[}\Big{(}\frac{e^{2T(a-\alpha)}-1}{2(a-\alpha)}\Big{)}-T\Big{]}\\\
+\Big{(}\frac{e^{2T(a-\alpha)}-1}{2(a-\alpha)}\Big{)}q_{0}^{2}\Big{]}\;\text{for
any}\;\alpha\geq 0,\alpha\neq a,$ (3.50)

and for any $a\geq 0$ we have

$\mathcal{J}(\text{CG}(a),a;T,q_{0})=(1+a^{2})T\Big{(}q_{0}^{2}+\frac{1}{2}T\Big{)}.$
(3.51)

Using (3.50) and (3.51) we deduce the following corollary.

######  Corollary 3.1.

For $\alpha\geq 0$ and $a\in\mathbb{R}$ we have

$\mathcal{J}(\emph{CG}(\alpha),a;T,q_{0})\leq\begin{cases}C_{T}(1+\alpha^{2})(1+q_{0}^{2})e^{2T(a-\alpha)}&\text{when}\;(a-\alpha)>1/T,\\\
C_{T}(1+\alpha^{2})(1+q_{0}^{2})&\text{when}\;|a-\alpha|\leq 1/T,\\\
\frac{(1+\alpha^{2})}{2|a-\alpha|}(q_{0}^{2}+T)&\text{when}\;(a-\alpha)<-1/T.\end{cases}$

For any $\alpha\in\mathbb{R}$ the strategy $\sigma_{\text{opt}}(\alpha)$ is a
simple feedback strategy with gain function $\kappa(T-t,\alpha)$. Note that
this strategy depends on $T$ but is independent of $q_{0}$. By Lemma 3.1, and
because $\kappa(T-t,a)\leq C\max\\{1,a\\}$ for all $a\in\mathbb{R}$,
$t\in[0,T]$, we have $\mathcal{J}_{0}(a;T,q_{0})\leq
C\max\\{1,a\\}(q_{0}^{2}+T)$. We combine this with Lemma 3.3 to deduce the
following corollary.

######  Corollary 3.2.

For any $a\in\mathbb{R}$ the following holds.

$\mathcal{J}(\sigma_{\emph{opt}}(\alpha),a;T,q_{0})\leq\begin{cases}C\max\\{1,a\\}(q_{0}^{2}+T)&\text{if}\;\alpha=a,\\\
C_{T}(1+\alpha^{2})e^{2|a|T}(1+q_{0}^{2})&\text{for
any}\;\alpha\in\mathbb{R}.\end{cases}$

We remark that the first upper bound in Corollary 3.2 (for $\alpha=a$) is
sharp when $a$ is large. The second upper bound is far from sharp unless
$a\gg\alpha\gg 1$.

##  4 The uncontrolled system

Let $T>0$, $q_{0}>0$, and let $a\in\mathbb{R}$ be arbitrary. In this section
we consider the dynamics

$dq=(aq)dt+dW_{t},\qquad q(0)=q_{0}.$ (4.1)

We define a random process

$X_{t}=e^{-at}q(t)-q_{0}=\int_{0}^{t}e^{-as}dW_{s}.$ (4.2)

If $a=0$, then $X_{t}$ is standard Brownian motion. If $a\neq 0$, then $X_{t}$
is a normal random variable with

$\text{E}[X_{t}]=0,\qquad\text{Var}[X_{t}]=\frac{1-e^{-2at}}{2a}.$ (4.3)

For the remainder of this paper, we adopt the convention that
$(1-e^{-2at})/2a$ is equal to $t$ when $a=0$. With this convention in place,
(4.3) holds for all $a\in\mathbb{R}$. As a consequence of the above, for any
$\delta>0$ we have

$\text{Prob}(|X_{t}|>\delta)\leq\begin{cases}C\exp(-c\delta^{2}a)\;\text{for
any}\;a\geq 0,t\geq 0,\\\ C\exp(-c\delta^{2}/t)\;\text{for any}\;|a|t\leq
1/10.\end{cases}$ (4.4)

Note that these two cases are not mutually exclusive.

We also note that $X_{t}$ satisfies the reflection principle, i.e., for any
$M>0$ we have

$\text{Prob}\left(\sup_{0\leq s\leq t}X_{s}\geq
M\right)=2\cdot\text{Prob}(X_{t}\geq M).$ (4.5)

This is true because (1) $X_{t}$ has almost surely continuous paths, (2)
$X_{t}$ satisfies the strong Markov property, and (3) the random variable
$(X_{t+t^{\prime}}-X_{t})$ is equal in distribution to
$e^{-at}X_{t^{\prime}}$, which is symmetric. Examining the proof of the
Reflection Principle for Brownian motion in [17], one sees that properties
(1)–(3) are sufficient to prove (4.5).

###  4.1 Stopping times

We let $\varepsilon>0$ be a given parameter. We define two stopping times.

  * •

$\tau_{+}$ is equal to the first time $t\in(0,T)$ for which
$q(t)=(1+\varepsilon)q_{0}$ if such a time exists and equal to $T$ if no such
time exists.

  * •

$\tau_{-}$ is equal to the first time $t\in(0,T)$ for which
$q(t)=(1-\varepsilon)q_{0}$ if such a time exists and equal to $T$ if no such
time exists.

We will make use of the following claim throughout this section.

######  Claim 1.

Let $a\neq 0$ and let $\eta\geq\eta_{0}$, where $\eta_{0}>1$ is a sufficiently
large absolute constant. Define

$t_{0}=\frac{\eta\varepsilon}{|a|}.$

Suppose that $t_{0}<T$ and that $t_{0}|a|<1/10$. Then, provided $\varepsilon$
is sufficiently small depending on $T$, the following hold.

  1. _(i)_

If $a>0$, then

$\emph{Prob}(\tau_{+}>t_{0})\leq C\exp(-c\varepsilon\eta q_{0}^{2}a).$

  2. _(ii)_

If $a<0$, then

$\emph{Prob}(\tau_{-}>t_{0})\leq C\exp(-c\varepsilon\eta q_{0}^{2}|a|).$

###### Proof.

We will only prove (i); the proof of (ii) is nearly identical. Assume that
$a>0$. By our assumption that $t_{0}<T$, we have

$\begin{split}\text{Prob}(\tau_{+}>t_{0})=&\text{Prob}(q(t)<(1+\varepsilon)q_{0}\;\text{for
all}\;t\in[0,t_{0}])\\\
\leq&\text{Prob}(q(t_{0})<(1+\varepsilon)q_{0}).\end{split}$ (4.6)

Let $X_{t}$ be as in (4.2). If $q(t_{0})<(1+\varepsilon)q_{0}$, then (since we
assume $at_{0}=\eta\varepsilon<1/10$) we have

$\displaystyle X_{t_{0}}$
$\displaystyle<e^{-at_{0}}(1+\varepsilon)q_{0}-q_{0}$
$\displaystyle\leq(1-c\eta\varepsilon)(1+\varepsilon)q_{0}-q_{0}.$
$\displaystyle\leq-c^{\prime}\eta\varepsilon q_{0}$

provided $\eta$ is larger than an absolute constant and $\varepsilon$ is
smaller than an absolute constant. This shows that

$\text{Prob}(\tau_{+}>t_{0})\leq\text{Prob}(X_{t_{0}}\leq-c^{\prime}\eta\varepsilon
q_{0});$

applying (4.4) (and again using the assumption $t_{0}|a|<1/10$) proves (i). ∎

######  Lemma 4.1.

Let $c_{0}>0$ be a sufficiently small absolute constant. Define

$\displaystyle t_{\emph{max}}=c_{0}\varepsilon^{1/2},\qquad
a_{\emph{tiny}}=\varepsilon^{1/2},\qquad a_{\emph{small}}=\varepsilon^{1/4}.$

Then, provided $\varepsilon$ is sufficiently small depending on $T$, the
following hold.

  1. _(i)_

For any $a\leq a_{\emph{tiny}}$,

$\emph{Prob}((\tau_{+}<t_{\emph{max}})\;\emph{AND}\;(\tau_{+}<\tau_{-}))\leq
C\exp(-c_{\varepsilon}q_{0}^{2}(|a|+1)).$

  2. _(ii)_

For any $a\geq-a_{\emph{tiny}}$,

$\emph{Prob}((\tau_{-}<t_{\emph{max}})\;\emph{AND}\;(\tau_{-}<\tau_{+}))\leq
C\exp(-c_{\varepsilon}q_{0}^{2}(|a|+1)).$

  3. _(iii)_

For any $|a|\geq a_{\emph{small}}$,

$\emph{Prob}((\tau_{+}\geq t_{\emph{max}})\;\emph{AND}\;(\tau_{-}\geq
t_{\emph{max}}))\leq C\exp(-c_{\varepsilon}q_{0}^{2}|a|).$

  4. _(iv)_

Define a stopping time
$\tilde{\tau}=\min\\{\tau_{+},\tau_{-},t_{\emph{max}}\\}$. Then provided
$q_{0}$ is sufficiently large depending on $\varepsilon$ and $T$ we have

$\emph{E}\bigg{[}\int_{0}^{\tilde{\tau}}q^{2}(t)\
dt\bigg{]}<C\varepsilon^{1/2}\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$

###### Proof.

We note that by taking $\varepsilon$ sufficiently small depending on $T$ we
can assume that $t_{\text{max}}<T$.

We first claim that

$\displaystyle\text{Prob}(\tau_{+}<t_{\text{max}})\leq
C\exp(-c\varepsilon^{3/2}q_{0}^{2})\;\text{for any}\;0\leq a\leq
a_{\text{tiny}},$ (4.7) $\displaystyle\text{Prob}(\tau_{-}<t_{\text{max}})\leq
C\exp(-c\varepsilon^{3/2}q_{0}^{2})\;\text{for any}\;-a_{\text{tiny}}\leq
a\leq 0.$ (4.8)

Assume that $0\leq a\leq a_{\text{tiny}}$. Since $t_{\text{max}}<T$ we have

$\text{Prob}(\tau_{+}<t_{\text{max}})=\text{Prob}(\exists
t\in(0,t_{\text{max}}):q(t)\geq(1+\varepsilon)q_{0}).$

Note that we have $0\leq at\leq c_{0}\varepsilon$ and thus
$e^{-at}\geq(1-c_{0}\varepsilon)$ for any $t\in(0,t_{\text{max}})$. Therefore,
if $q(t)\geq(1+\varepsilon)q_{0}$ for any $t\in(0,t_{\text{max}})$, then

$\displaystyle X_{t}$ $\displaystyle=e^{-at}q(t)-q_{0}$
$\displaystyle\geq(1-c_{0}\varepsilon)(1+\varepsilon)q_{0}-q_{0}$
$\displaystyle>\varepsilon q_{0}/2$

provided $c_{0}$, $\varepsilon$ are smaller than certain absolute constants.
We have shown that

$\displaystyle\text{Prob}(\tau_{+}<t_{\text{max}})\leq\text{Prob}(\exists
t\in(0,t_{\text{max}}):X_{t}>\varepsilon q_{0}/2).$

Applying (4.5) and then (4.4) (we use that $t_{\text{max}}a\leq
c_{0}\varepsilon<1/10$) proves (4.7). We omit the proof of (4.8) as it can be
easily inferred from the proof of (4.7).

We now claim that

$\displaystyle\text{Prob}(\tau_{-}<t_{\text{max}})\leq
C\exp(-c\varepsilon^{3/2}q_{0}^{2})\;\text{for any}\;0\leq a\leq
a_{\text{small}},$ (4.9)
$\displaystyle\text{Prob}(\tau_{+}<t_{\text{max}})\leq
C\exp(-c\varepsilon^{3/2}q_{0}^{2})\;\text{for any}\;-a_{\text{small}}\leq
a\leq 0.$ (4.10)

Assume that $0\leq a\leq a_{\text{small}}$. If $q(t)\leq(1-\varepsilon)q_{0}$
for some $t\in(0,t_{\text{max}})$, then

$X_{t}\leq e^{-at}(1-\varepsilon)q_{0}-q_{0}\leq-\varepsilon q_{0}.$

This implies that

$\text{Prob}(\tau_{-}<t_{\text{max}})\leq\text{Prob}(\exists
t\in(0,t_{\text{max}}):X_{t}\leq-\varepsilon q_{0}).$

Applying (4.5) and then (4.4) (note that
$t_{\text{max}}a<c_{0}\varepsilon^{3/4}<1/10$ for any $0\leq a\leq
a_{\text{small}}$) proves (4.9). The proof of (4.10) is very similar; we omit
it.

Now assume that $a\geq a_{\text{small}}$. We claim that the following
estimates hold:

$\displaystyle\text{Prob}(\tau_{+}\geq t_{\text{max}})<C\exp(-c\varepsilon
q_{0}^{2}a),$ (4.11)
$\displaystyle\text{Prob}((\tau_{-}<t_{\text{max}})\;\text{AND}\;(\tau_{-}<\tau_{+}))<C\exp(-c\varepsilon^{2}q_{0}^{2}a).$
(4.12)

Let $\eta_{0}>0$ be the absolute constant in Claim 1 and define

$\tilde{t}_{0}=\frac{\eta_{0}\varepsilon}{a}.$

By our assumption that $a\geq a_{\text{small}}$, we have

$\tilde{t}_{0}\leq\eta_{0}\varepsilon^{3/4}<c_{0}\varepsilon^{1/2}=t_{\text{max}}<T$
(4.13)

provided $\varepsilon$ is smaller than an absolute constant. Therefore

$\text{Prob}(\tau_{+}\geq
t_{\text{max}})\leq\text{Prob}(\tau_{+}\geq\tilde{t}_{0}).$ (4.14)

Provided $\varepsilon$ is smaller than an absolute constant we have
$\tilde{t}_{0}a=\eta_{0}\varepsilon<1/10$. Together with Claim 1, (4.14)
implies (4.11).

Define

$t_{0}^{*}=\min\bigg{\\{}t_{\text{max}},\frac{1}{10a}\bigg{\\}}.$

Observe that $t_{0}^{*}<T$ and so we have

$\text{Prob}(\tau_{-}<t_{0}^{*})=\text{Prob}(\exists
t\in(0,t_{0}^{*}):q(t)<(1-\varepsilon)q_{0}).$

If $q(t)<(1-\varepsilon)q_{0}$ for some $t\in(0,t_{0}^{*})$, then (since
$a>0$)

$X_{t}<e^{-at}(1-\varepsilon)q_{0}-q_{0}<-\varepsilon q_{0}.$

Therefore

$\text{Prob}(\tau_{-}<t_{0}^{*})\leq\text{Prob}(\exists
t\in(0,t_{0}^{*}):X_{t}<-\varepsilon q_{0}).$

Combining this with (4.5) gives

$\text{Prob}(\tau_{-}<t_{0}^{*})\leq
2\cdot\text{Prob}(X_{t_{0}^{*}}<-\varepsilon q_{0})$

Using (4.4) and the fact that $at_{0}^{*}<1/10$ gives

$\text{Prob}(\tau_{-}<t_{0}^{*})\leq
C\exp(-c\varepsilon^{2}q_{0}^{2}/t_{0}^{*}).$ (4.15)

We claim that (4.15) implies (4.12) under the assumption that

$a_{\text{small}}\leq a\leq\frac{1}{10c_{0}\varepsilon^{1/2}}.$ (4.16)

To see this, note that (4.16) implies that $t_{0}^{*}=t_{\text{max}}$, and
therefore (4.15) gives

$\text{Prob}(\tau_{-}<t_{\text{max}})\leq
C\exp(-c\varepsilon^{3/2}q_{0}^{2}).$ (4.17)

We then use (4.16) to deduce that

$\text{Prob}(\tau_{-}<t_{\text{max}})\leq C\exp(-c\varepsilon^{2}q_{0}^{2}a).$

This proves (4.12) assuming (4.16).

We now prove (4.12) assuming that

$a>\frac{1}{10c_{0}\varepsilon^{1/2}}.$ (4.18)

Note that this assumption implies that $t_{0}^{*}<t_{\text{max}}$. We have

$\begin{split}\text{Prob}((\tau_{-}<t_{\text{max}})\;\text{AND}\;(\tau_{-}<\tau_{+}))\leq\text{Prob}(\tau_{-}<t_{0}^{*})+\text{Prob}(\tau_{+}>t_{0}^{*}).\end{split}$
(4.19)

By (4.15) (and using that assumption (4.18) implies that
$t_{0}^{*}=(10a)^{-1}$), we have

$\text{Prob}(\tau_{-}<t_{0}^{*})\leq C\exp(-c\varepsilon^{2}q_{0}^{2}a).$
(4.20)

Observe that $t_{0}^{*}<T$ and that $t_{0}^{*}a=1/10$. We can therefore apply
Claim 1 with $\eta=1/(10\varepsilon)$ to get

$\text{Prob}(\tau_{+}>t_{0}^{*})\leq C\exp(-cq_{0}^{2}a).$ (4.21)

Combining (4.19)–(4.21) proves (4.12) under assumption (4.18). This completes
the proof of (4.12).

By mirroring the proofs of (4.11) and (4.12), we can show that for $a\leq-
a_{\text{small}}$ we have

$\displaystyle\text{Prob}(\tau_{-}\geq t_{\text{max}})<C\exp(-c\varepsilon
q_{0}^{2}|a|),$ (4.22)
$\displaystyle\text{Prob}((\tau_{+}<t_{\text{max}})\;\text{AND}\;(\tau_{+}<\tau_{-}))<C\exp(-c\varepsilon^{2}q_{0}^{2}|a|).$
(4.23)

Combining (4.7), (4.10), (4.23) proves (i). Similarly, combining (4.8), (4.9),
(4.12) proves (ii). Equations (4.11) and (4.22) prove (iii).

We now prove (iv). Note that with probability 1 we have that $\tilde{\tau}\leq
t_{\text{max}}=c_{0}\varepsilon^{1/2}$ and that
$|q(t)|\leq(1+\varepsilon)q_{0}$ for all $t\in(0,\tilde{\tau})$. Therefore

$\text{E}\bigg{[}\int_{0}^{\tilde{\tau}}q^{2}(t)\
dt\bigg{]}<Cq_{0}^{2}\varepsilon^{1/2}.$ (4.24)

By Lemma 3.1, there exists $\tilde{A}>0$ depending only on $T$ such that

$\mathcal{J}_{0}(a;T,q_{0})>\frac{q_{0}^{2}}{100|a|}\;\text{for
any}\;a<-\tilde{A}$ (4.25)

and

$\mathcal{J}_{0}(a;T,q_{0})>c_{T}q_{0}^{2}\;\text{for any}\;a>-\tilde{A}.$
(4.26)

Combining (4.24) and (4.26) gives

$\text{E}\bigg{[}\int_{0}^{\tilde{\tau}}q^{2}(t)\
dt\bigg{]}<C_{T}\varepsilon^{1/2}\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a>-\tilde{A}.$ (4.27)

This proves (iv) when $a>-\tilde{A}$.

Now assume that $a<-\tilde{A}$. Let $\eta_{0}$ be as in Claim 1 and define

$\bar{t}_{0}=\frac{\eta_{0}\varepsilon}{|a|}.$

By taking $\varepsilon$ smaller than an absolute constant we can ensure that
$\bar{t}_{0}<t_{\text{max}}$ and that $\bar{t}_{0}|a|<1/10$. Therefore we can
apply Claim 1 to get

$\text{Prob}(\tilde{\tau}>\bar{t}_{0})\leq\text{Prob}(\tau_{-}>\bar{t}_{0})\leq
C\exp(-c\varepsilon q_{0}^{2}|a|).$

Recall that with probability 1 we have $|q(t)|\leq(1+\varepsilon)q_{0}$ for
all $t\in[0,\tilde{\tau}]$. Therefore

$\displaystyle\text{E}\bigg{[}\int_{0}^{\tilde{\tau}}q^{2}(t)\ dt\bigg{]}$
$\displaystyle<Cq_{0}^{2}\bar{t}_{0}+Cq_{0}^{2}t_{\text{max}}\text{Prob}(\tilde{\tau}>\bar{t}_{0})$
$\displaystyle<\frac{Cq_{0}^{2}\varepsilon}{|a|}+Cq_{0}^{2}t_{\text{max}}\exp(-c\varepsilon
q_{0}^{2}|a|).$

Taking $q_{0}$ sufficiently large depending on $\varepsilon$ and using (4.25)
gives

$\text{E}\bigg{[}\int_{0}^{\tilde{\tau}}q^{2}(t)\
dt\bigg{]}<C\varepsilon\mathcal{J}_{0}(a,T,q_{0})\;\text{for
any}\;a<-\tilde{A}.$ (4.28)

Combining (4.27) and (4.28) proves (iv). ∎

We now let $q_{0}^{*}>q_{0}$ be a real number and we define two additional
stopping times.

  * •

$\tau^{*}_{+}$ is equal to the first time $t\in(0,T)$ for which
$q(t)=q_{0}^{*}$ if such a time exists and equal to $T$ if no such time
exists.

  * •

$\tau^{*}_{-}$ is equal to the first time $t\in(0,T)$ for which
$q(t)=-q_{0}^{*}$ if such a time exists and equal to $T$ if no such time
exists.

######  Lemma 4.2.

Provided $\varepsilon$ is sufficiently small depending on $T$, the following
hold.

  1. _(i)_

For any $a\geq-\varepsilon^{-1/2}$

$\emph{Prob}(\tau_{-}^{*}<\tau_{+})\leq C_{q_{0}}\varepsilon^{1/4}.$

  2. _(ii)_

Define a stopping time

$\bar{\tau}=\min\\{\tau_{+},\tau_{-}^{*}\\}.$

Then

$\emph{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\
dt\bigg{]}<C_{T,q_{0},q_{0}^{*}}\varepsilon^{1/4}\;\text{for
any}\;a\in\mathbb{R}.$

###### Proof.

We first prove a claim. Define

$\tilde{t}_{1}=\varepsilon\min\\{1,1/|a|\\}$

(when $a=0$ we set $\tilde{t}_{1}=\varepsilon$). We claim that

$\text{Prob}(\tau_{+}>\tilde{t}_{1})\leq Cq_{0}\varepsilon^{1/4}\;\text{for
any}\;|a|\leq\varepsilon^{-1/2}.$ (4.29)

Assume that $|a|\leq\varepsilon^{-1/2}$. By taking $\varepsilon$ sufficiently
small depending on $T$ we can assume that $\tilde{t}_{1}<T$. We have

$\text{Prob}(\tau_{+}>\tilde{t}_{1})=\text{Prob}(q(t)<(1+\varepsilon)q_{0}\;\text{for
all}\;t\in[0,\tilde{t}_{1}]).$

Note that $|a|\tilde{t}_{1}<\varepsilon$, so if $q(t)<(1+\varepsilon)q_{0}$
for any $t\in[0,\tilde{t}_{1}]$, then

$\begin{split}X_{t}&<e^{-at}(1+\varepsilon)q_{0}-q_{0}\\\ &<C\varepsilon
q_{0}.\end{split}$ (4.30)

Therefore

$\begin{split}\text{Prob}(\tau_{+}>\tilde{t}_{1})&\leq\text{Prob}(X_{t}<C\varepsilon
q_{0}\;\text{for all}\;t\in[0,\tilde{t}_{1}])\\\ &=1-\text{Prob}(\exists
t\in[0,\tilde{t}_{1}]:X_{t}>C\varepsilon q_{0})\\\
&=1-2\cdot\text{Prob}(X_{\tilde{t}_{1}}>C\varepsilon q_{0}),\end{split}$
(4.31)

where the last equality follows from (4.5). Recall (see (4.3)) that
$X_{\tilde{t}_{1}}$ is a normal random variable with mean 0 and variance
$(1-e^{-2a\tilde{t}_{1}})/2a$. Also recall that
$|a|\tilde{t}_{1}<\varepsilon$, so provided $\varepsilon$ is smaller than some
absolute constant the variance of $X_{\tilde{t}_{1}}$ is bounded above and
below by constant multiples of $\tilde{t}_{1}$. Therefore

$\begin{split}\text{Prob}(X_{\tilde{t}_{1}}>C\varepsilon
q_{0})&\geq\frac{1}{2}-C\int_{0}^{C\varepsilon
q_{0}/\tilde{t}_{1}^{1/2}}e^{-t^{2}/2}\ dt\\\
&\geq\frac{1}{2}-\frac{C\varepsilon q_{0}}{\tilde{t}_{1}^{1/2}},\end{split}$
(4.32)

so

$\text{Prob}(\tau_{+}>\tilde{t}_{1})\leq\frac{C\varepsilon
q_{0}}{\tilde{t}_{1}^{1/2}}.$

Using the assumption $|a|\leq\varepsilon^{-1/2}$ and the definition of
$\tilde{t}_{1}$ implies (4.29).

We now prove (i). Note that for any $t^{*}\in(0,T)$ we have

$\text{Prob}(\tau_{-}^{*}<\tau_{+})\leq\text{Prob}(\tau_{-}^{*}<t^{*})+\text{Prob}(\tau_{+}>t^{*}).$
(4.33)

In the event that $q(t)=-q_{0}^{*}$ for some $t\in(0,T)$, then

$X_{t}=-e^{-at}q_{0}^{*}-q_{0}<-q_{0}.$

Therefore

$\displaystyle\text{Prob}(\tau_{-}^{*}<t^{*})$
$\displaystyle=\text{Prob}(\exists t\in(0,t^{*}):q(t)=-q_{0}^{*})$
$\displaystyle\leq\text{Prob}(\exists t\in(0,t^{*}):X_{t}<-q_{0}).$

Equation (4.5) implies

$\text{Prob}(\tau_{-}^{*}<t^{*})\leq 2\cdot\text{Prob}(X_{t^{*}}<-q_{0}).$
(4.34)

We let $\tilde{t}_{1}$ be as above; note that by definition
$\tilde{t}_{1}|a|<\varepsilon$ and $1/\tilde{t}_{1}>1/\varepsilon$. Combining
(4.34) and (4.4) gives

$\text{Prob}(\tau_{-}^{*}<\tilde{t}_{1})\leq
C\exp(-cq_{0}^{2}/\varepsilon)\;\text{for}\;|a|\leq\varepsilon^{-1/2}.$

Combining this with (4.33) and (4.29) proves (i) for
$|a|\leq\varepsilon^{-1/2}$.

Assume that $a\geq\varepsilon^{-1/2}$. Define

$\bar{t}_{1}=\frac{1}{10a}.$

Let $\eta_{0}$ be as in Claim 1. Taking $\varepsilon$ sufficiently small
depending on $T$ ensures that $\bar{t}_{1}<T$ and that
$(10\varepsilon)^{-1}>\eta_{0}$. We can therefore apply Claim 1 with
$\eta=(10\varepsilon)^{-1}$ to get

$\text{Prob}(\tau_{+}>\bar{t}_{1})\leq C\exp(-cq_{0}^{2}a).$ (4.35)

Taking $\varepsilon$ smaller than an absolute constant gives
$1/\bar{t}_{1}>1$. Combined with (4.34), (4.4) this gives

$\text{Prob}(\tau_{-}^{*}<\bar{t}_{1})\leq C\exp(-cq_{0}^{2}a).$

By (4.33), we have therefore shown that

$\text{Prob}(\tau_{-}^{*}<\tau_{+})\leq C\exp(-cq_{0}^{2}a)\;\text{for
any}\;a>\varepsilon^{-1/2}.$

This implies (i) for $a>\varepsilon^{-1/2}$ (here we use the assumption that
$q_{0}$ is nonzero).

We now prove (ii). We split the analysis into cases.

Case I: (Large negative $a$)

Assume that $a<-\varepsilon^{-1/2}$. Note that the system (4.1) satisfies

$q(t)=q_{0}+W(t)+\int_{0}^{t}aq(\tau)\ d\tau,$

with probability 1. Therefore the expected value of the integral of $q^{2}$
from time 0 to time $T$ is equal to the expected cost incurred from time $0$
to time $T$ by the constant gain strategy $\text{CG}(0)$, i.e., the strategy
that sets $u=0$ (see Section 3). Applying Corollary 3.1 with $\alpha=0$,
taking $\varepsilon$ sufficiently small depending on $T$, and using that
$\bar{\tau}\leq T$ with probability 1, we have

$\text{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\
dt\bigg{]}\leq\frac{q_{0}^{2}+T}{2|a|}\;\text{for
any}\;a<-\varepsilon^{-1/2},$

and therefore

$\text{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\
dt\bigg{]}<C_{T,q_{0}}\varepsilon^{1/2}\;\text{for
any}\;a<-\varepsilon^{-1/2}.$ (4.36)

Case II: (Large positive $a$)

Assume that $a>\varepsilon^{-1/2}$ and let $\bar{t}_{1}$ be as above. Since
$\bar{\tau}<T$ and since $|q(t)|\leq\min\\{(1+\varepsilon)q_{0},q_{0}^{*}\\}$
for all $t\in(0,\bar{\tau})$ with probability 1, we have

$\text{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\ dt\bigg{]}\leq
C_{q_{0},q_{0}^{*}}(\bar{t}_{1}+T\cdot\text{Prob}(\bar{\tau}>\bar{t}_{1})).$
(4.37)

Note that our assumption that $a>\varepsilon^{-1/2}$ implies that
$\bar{t}_{1}<c\varepsilon^{1/2}$. The event $\bar{\tau}>\bar{t}_{1}$ implies
the event $\tau_{+}>\bar{t}_{1}$, and therefore we combine (4.37) with (4.35)
to get

$\text{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\
dt\bigg{]}<C_{T,q_{0},q_{0}^{*}}\varepsilon^{1/2}\;\text{for
any}\;a>\varepsilon^{-1/2}$ (4.38)

(note that we also use the assumption that $q_{0}$ is nonzero).

Case III: (Bounded $a$) Let $\tilde{t}_{1}$ be as above. Then

$\text{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\
dt\bigg{]}<C_{q_{0},q_{0}^{*}}(\tilde{t}_{1}+T\cdot\text{Prob}(\bar{\tau}>\tilde{t}_{1}))\;\text{for
any}\;|a|\leq\varepsilon^{-1/2}.$

The event $\bar{\tau}>\tilde{t}_{1}$ implies the event
$\tau_{+}>\tilde{t}_{1}$. Therefore, by (4.29), we have

$\text{E}\bigg{[}\int_{0}^{\bar{\tau}}q^{2}(t)\
dt\bigg{]}<C_{T,q_{0},q_{0}^{*}}\varepsilon^{1/4}\;\text{for
any}\;|a|\leq\varepsilon^{-1/2}.$ (4.39)

Combining (4.36), (4.38), and (4.39) proves (ii). ∎

######  Lemma 4.3.

Assume $a<0$ and define $\rho=q_{0}^{*}/q_{0}$ (recall that $q_{0}^{*}>q_{0}$
and so $\rho>1$). Then

$\emph{Prob}((\tau_{+}^{*}<T)\;\emph{OR}\;(\tau_{-}^{*}<T))\leq
C_{T,\rho}(1+q_{0}^{-2})\exp(-c_{\rho}q_{0}^{2}|a|).$

###### Proof.

Let $N$ be the smallest positive integer such that

$10|a|T\leq N.$

Note that

$N<(1+10|a|T).$ (4.40)

Define $\Delta t=\frac{T}{N}$ (observe that our choice of $N$ ensures that
$\Delta t|a|\leq\frac{1}{10}$) and $I_{j}=[j\Delta t,(j+1)\Delta t]$ for
$j=0,\dots,N-1$. Note that

$\text{Prob}((\tau_{+}^{*}<T)\;\text{OR}\;(\tau_{-}^{*}<T))\leq\sum_{j=0}^{N-1}\text{Prob}(\exists
t\in I_{j}:|q(t)|\geq q_{0}^{*}).$ (4.41)

We claim that

$\text{Prob}(\exists t\in I_{j}:|q(t)|\geq q_{0}^{*})\leq
C\exp(-c_{\rho}q_{0}^{2}|a|)\;\text{for any}\;j=0,\dots,N-1.$ (4.42)

Combining (4.40)-(4.42) proves the lemma. Therefore, it just remains to
establish (4.42).

Since $a<0$, we have $e^{-at}\geq e^{-aj\Delta t}$ for all $t\in I_{j}$.
Therefore, in the event that $q(t)\geq q_{0}^{*}$,

$X_{t}=q(t)e^{-at}-q_{0}\geq
q_{0}^{*}e^{-at}\left(1-\frac{1}{\rho}e^{at}\right)\geq
c_{\rho}q_{0}^{*}e^{-aj\Delta t}$ (4.43)

(we’ve used that $\rho>1$ and $e^{at}\leq 1$). In the event that $q(t)\leq-
q_{0}^{*}$,

$X_{t}=q(t)e^{-at}-q_{0}\leq-q_{0}^{*}e^{-aj\Delta t}.$ (4.44)

Combining (4.43) and (4.44) implies that

$\text{Prob}(\exists t\in I_{j}:|q(t)|\geq q_{0}^{*})\leq\text{Prob}(\exists
t\in I_{j}:|X_{t}|\geq c_{\rho}q_{0}^{*}e^{-aj\Delta t}).$ (4.45)

Since $I_{j}\subset[0,(j+1)\Delta t]$, we have

$\text{Prob}(\exists t\in I_{j}:|X_{t}|\geq c_{\rho}q_{0}^{*}e^{-aj\Delta
t})\\\ \leq\text{Prob}(\exists t\in[0,(j+1)\Delta t]:|X_{t}|\geq
c_{\rho}q_{0}^{*}e^{-aj\Delta t}).$ (4.46)

Equation (4.5) implies that

$\text{Prob}(\exists t\in[0,(j+1)\Delta t]:|X_{t}|\geq
c_{\rho}q_{0}^{*}e^{-aj\Delta t})\\\ =2\cdot\text{Prob}\left(|X_{(j+1)\Delta
t}|\geq c_{\rho}q_{0}^{*}e^{-aj\Delta t}\right).$ (4.47)

Recall that $X_{(j+1)\Delta t}$ is a normal random variable with mean $0$ and
standard deviation

$\left(\frac{e^{2|a|(j+1)\Delta t}-1}{2|a|}\right)^{1/2}$

Recall also that our choice of $N$ ensures that $\Delta t|a|<\frac{1}{10}$.
Therefore $c<e^{-|a|\Delta t}<1$, and we have

$\frac{c_{\rho}q_{0}^{*}e^{|a|j\Delta t}|a|^{1/2}}{(e^{2|a|(j+1)\Delta
t}-1)^{1/2}}=\frac{c_{\rho}q_{0}^{*}e^{-|a|\Delta
t}|a|^{1/2}}{(1-e^{-2|a|(j+1)\Delta t})^{1/2}}\geq
c_{\rho}^{\prime}q_{0}|a|^{1/2}.$

Thus, when $|X_{(j+1)\Delta t}|\geq c_{\rho}q_{0}^{*}e^{-aj\Delta t}$, the
normal random variable $X_{(j+1)\Delta t}$ is at least
$c_{\rho}^{\prime}q_{0}|a|^{1/2}$ standard deviations from its mean of 0.
Therefore

$\text{Prob}\left(|X_{(j+1)\Delta t}|\geq c_{\rho}q_{0}^{*}e^{-aj\Delta
t}\right)\leq C\exp(-c_{\rho}^{\prime}q_{0}^{2}|a|).$ (4.48)

Combining (4.45) - (4.48) proves (4.42), finishing the proof of the lemma. ∎

###  4.2 Estimating the parameter $a$

We remain in the setting of the previous section.

In the event that $\tau_{+}<T$ we define a random variable

$\bar{a}_{+}=\frac{\log(1+\varepsilon)}{\tau_{+}}.$

Note that $\bar{a}_{+}$ is an estimate for the parameter $a$ in (4.1).
Similarly, in the event that $\tau_{-}<T$ we define a random variable

$\bar{a}_{-}=\frac{\log(1-\varepsilon)}{\tau_{-}}.$

Let $X\subset(0,\infty)$ be a subset. We will be interested in estimating the
probability of events of the form “$\tau_{+}<T$ and $\bar{a}_{+}\in X$”. We
will abbreviate such events to “$\bar{a}_{+}\in X$”; note that when
$\tau_{+}=T$ the random variable $\bar{a}_{+}$ is undefined and so the event
$\bar{a}_{+}\in X$ is meaningless. Similarly, for $Y\subset(-\infty,0)$ we let
“$\bar{a}_{-}\in Y$” denote the event “$\tau_{-}<T$ and $\bar{a}_{-}\in Y$”.

######  Lemma 4.4.

Let $A^{\\#}>1$. Then provided $\varepsilon$ is sufficiently small depending
on $T$ we have

$\emph{Prob}(\bar{a}_{+}>A^{\\#})\leq C\exp(-c_{\varepsilon}q_{0}^{2}A^{\\#})$

for any $|a|\leq A^{\\#}/10$.

###### Proof.

Define

$t_{2}=\frac{\log(1+\varepsilon)}{A^{\\#}}.$ (4.49)

By taking $\varepsilon$ sufficiently small depending on $T$ we ensure that
$t_{2}<T$. Therefore

$\text{Prob}(\bar{a}_{+}>A^{\\#})=\text{Prob}(\tau_{+}<t_{2}).$ (4.50)

Suppose that $0\leq a\leq A^{\\#}/10$. Note that for any $t\in[0,t_{2})$ we
have

$ta<\frac{a}{A^{\\#}}\log(1+\varepsilon)<\frac{\varepsilon}{10},$

and thus

$e^{-at}\geq(1-\varepsilon/10).$

Consequently, if $q(t)>(1+\varepsilon)q_{0}$ for any $t\in[0,t_{2})$, then

$\displaystyle X_{t}$ $\displaystyle=e^{-at}q(t)-q_{0}$
$\displaystyle>e^{-at}(1+\varepsilon)q_{0}-q_{0}$ $\displaystyle\geq
c\varepsilon q_{0}.$

Now suppose that $-A^{\\#}/10\leq a<0$. If $q(t)>(1+\varepsilon)q_{0}$ for
some $t\in[0,t_{2})$, then

$X_{t}=e^{|a|t}q(t)-q_{0}>\varepsilon q_{0}.$

We have shown that

$\text{Prob}(\tau_{+}<t_{2})\leq\text{Prob}(\exists t\in[0,t_{2}):X_{t}\geq
c\varepsilon q_{0})\;\text{for any}\;|a|\leq\frac{A^{\\#}}{10}.$

Combining this with (4.50) and (4.5), we deduce that

$\begin{split}\text{Prob}(\bar{a}_{+}\geq A^{\\#})&\leq\text{Prob}(\exists
t\in[0,t_{2}):X_{t}\geq c\varepsilon q_{0})\\\
&=2\cdot\text{Prob}(X_{t_{2}}\geq c\varepsilon q_{0}).\end{split}$ (4.51)

Since $t_{2}|a|<C\varepsilon$, we apply (4.4) to get

$\text{Prob}(X_{t_{2}}\geq c\varepsilon q_{0})\leq
C\exp(-c\varepsilon^{2}q_{0}^{2}/t_{2})\leq\exp(-c_{\varepsilon}q_{0}^{2}A^{\\#}).$

Combining this with (4.51) proves the lemma. ∎

######  Lemma 4.5.

Let $\delta>0$. Then provided $\varepsilon$ is sufficiently small depending on
$T$ the following hold.

  1. _(i)_

$\emph{Prob}(|a-\bar{a}_{+}|>\delta a)\leq
C\exp(-c_{\varepsilon,\delta}q_{0}^{2}a)$ for any $a\geq\varepsilon^{1/2}$.

  2. _(ii)_

$\emph{Prob}(|a-\bar{a}_{-}|>\delta|a|)\leq
C\exp(-c_{\varepsilon,\delta}q_{0}^{2}|a|)$ for any $a\leq-\varepsilon^{1/2}$.

###### Proof.

We will just prove (i), as essentially the same argument can be used to prove
(ii).

Without loss of generality we assume that $\delta<1/10$. Note that

$\text{Prob}(|a-\bar{a}_{+}|>\delta
a)=\text{Prob}(\bar{a}_{+}>(1+\delta)a)+\text{Prob}(0<\bar{a}_{+}<(1-\delta)a).$
(4.52)

Now define

$t_{3}=\frac{\log(1+\varepsilon)}{(1+\delta)a}.$

By taking $\varepsilon$ sufficiently small depending on $T$ we ensure that
$t_{3}<T$, and therefore

$\text{Prob}(\bar{a}_{+}>(1+\delta)a)=\text{Prob}(\tau_{+}<t_{3}).$

For any $t\in[0,t_{3})$, we have

$at\leq at_{3}\leq\frac{\log(1+\varepsilon)}{1+\delta}.$

Therefore, in the event that $q(t)>(1+\varepsilon)q_{0}$ for some
$t\in[0,t_{3})$, we have

$X_{t}=e^{-at}q(t)-q_{0}\geq
q_{0}\big{(}(1+\varepsilon)^{1-1/(1+\delta)}-1\big{)}=c_{\varepsilon,\delta}q_{0}.$

This implies that

$\text{Prob}(\bar{a}_{+}>(1+\delta)a)\leq\text{Prob}(\exists
t\in(0,t_{3}):X_{t}>c_{\varepsilon,\delta}q_{0}).$

We use (4.5) to deduce that

$\text{Prob}(\bar{a}_{+}>(1+\delta)a)\leq
2\cdot\text{Prob}(X_{t_{3}}>c_{\varepsilon,\delta}q_{0});$

we then note that $t_{3}a<C\varepsilon^{1/2}<1/10$ and apply (4.4) to get

$\text{Prob}(\bar{a}_{+}>(1+\delta)a)\leq
C\exp(-c_{\varepsilon,\delta}q_{0}^{2}a).$ (4.53)

Now define

$t_{4}=\frac{\log(1+\varepsilon)}{(1-\delta)a}.$

By taking $\varepsilon$ sufficiently small depending on $T$ we ensure that
$t_{4}<T$, and therefore

$\text{Prob}(0<\bar{a}_{+}<(1-\delta)a)\leq\text{Prob}(\tau_{+}>t_{4}).$

If $q(t_{4})<(1+\varepsilon)q_{0}$, then

$\displaystyle X_{t_{4}}$
$\displaystyle<e^{-at_{4}}(1+\varepsilon)q_{0}-q_{0}$
$\displaystyle=q_{0}((1+\varepsilon)^{-\delta/(1-\delta)}-1)$
$\displaystyle<-c_{\varepsilon,\delta}q_{0}.$

Therefore

$\text{Prob}(0<\bar{a}_{+}<(1-\delta)a)\leq\text{Prob}(X_{t_{4}}<-c_{\varepsilon,\delta}q_{0});$

applying (4.4) gives

$\text{Prob}(0<\bar{a}_{+}<(1-\delta)a)\leq
C\exp(-c_{\varepsilon,\delta}q_{0}^{2}a).$ (4.54)

Combining (4.52), (4.53), (4.54) proves (i). ∎

##  5 The almost optimal strategy

Throughout this section we fix a time horizon $T>0$ and a starting position
$q_{0}>0$.

We fix constants $C_{0},m_{0}$ as in the definition of an $A$-bounded strategy
in Section 2. Recall that a strategy $\sigma$ (for time horizon $T$) is
$A$-bounded for some $A>0$ if

$|u^{\sigma}(t,a)|\leq C_{0}A^{m_{0}}[|q^{\sigma}(t,a)|+1]\;\text{for
all}\;a\in\mathbb{R},t\in[0,T].$

Throughout this section, we allow all constants and parameters to depend on
$C_{0},m_{0}$.

In this section we prove the following theorem.

######  Theorem 5.1.

Let $\varepsilon>0$. Then for $\varepsilon_{0}>0$ sufficiently small depending
on $\varepsilon$ and $A>0$ sufficiently large depending on
$\varepsilon,\varepsilon_{0}$, the following holds.

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon_{0}$
and starting position $q_{0}$. Then the strategy $\sigma_{*}$ for time horizon
$T$ and starting position $q_{0}$ specified in Section 5.2 satisfies the
following.

  1. 1.

If $a\in[-A,A]$, then

$\mathcal{J}(\sigma_{*},a;T,q_{0})<\varepsilon+(1+\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}.$

  2. 2.

If $|a|>A$, then

$\mathcal{J}(\sigma_{*},a;T,q_{0})<\varepsilon+(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0}).$

We now show that Theorem 5.1 implies Theorem 2.1. Let $\varepsilon>0$. Let
$\varepsilon_{0}$ be sufficiently small (depending on $\varepsilon$) and let
$A$ be sufficiently large (depending on $\varepsilon$,$\varepsilon_{0}$) so
that the conclusion of Theorem 5.1 holds. Note that we can assume that
$\varepsilon_{0}<\varepsilon$.

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon$ and
starting position $q_{0}$. Since $\varepsilon_{0}<\varepsilon$, $\sigma$ is
also an $A$-bounded strategy for time horizon $T+\varepsilon_{0}$ and starting
position $q_{0}$. Moreover,

$\mathcal{J}(\sigma,a;T+\varepsilon_{0},q_{0})\leq\mathcal{J}(\sigma,a;T+\varepsilon,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (5.1)

Let $\sigma_{*}$ denote the strategy defined in Section 5.2. Observe that Part
(B) of Theorem 2.1 follows immediately from Part (B) of Theorem 5.1. To prove
Part (A) of Theorem 2.1 we simply combine equation (5.1) with Part (B) of
Theorem 5.1. This proves Theorem 2.1.

The remainder of Section 5 is devoted to proving Theorem 5.1. For the
remainder of Section 5 we assume that we are given $\varepsilon>0$ smaller
than some constant. We let $\varepsilon_{0}>0$ be sufficiently small depending
on $\varepsilon$, and $A>0$ be sufficiently large depending on
$\varepsilon,\varepsilon_{0}$.

In Section 5.2 we define the strategy $\sigma_{*}$. First, in Section 5.1, we
establish some preliminary results. In Section 5.3 we prove Theorem 5.1.

###  5.1 Preliminaries

####  5.1.1 Averting disaster when $a$ is large

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon_{0}$
and starting position $q_{0}$. Because $\sigma$ is $A$-bounded, if $a\gg A$
then with high probability the control $u^{\sigma}$ will fail to control the
particle and so the expected cost of $\sigma$ will be much larger than
$\mathcal{J}_{0}(a;T,q_{0})$ (see [7]). We now show how to use Theorem 2.2 to
obtain a strategy $\tilde{\sigma}$ that performs almost as well as $\sigma$
when $|a|\leq A$ and much better than $\sigma$ when $a\gg A$.

By Theorem 2.2, there exists a number $q_{0}^{*}>\max\\{1,2|q_{0}|\\}$
depending on $\varepsilon,\varepsilon_{0}$, $T$, and $q_{0}$, but independent
of $A$, such that for any $T^{\prime}\in[\varepsilon_{0},2T]$ there exists a
strategy $\text{L}q\text{S}(T^{\prime})$ for time horizon $T^{\prime}$ and
starting position $q_{0}^{*}$ satisfying

$\mathcal{J}(\text{L}q\text{S}(T^{\prime}),a;T^{\prime},q_{0}^{*})<(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T^{\prime},q_{0}^{*})\;\text{for
any}\;a\in\mathbb{R}.$ (5.2)

We now define the strategy $\tilde{\sigma}$ for time horizon $T$ and starting
position $q_{0}$.

We execute the strategy $\sigma$ from time 0 until time $t^{*}$, where $t^{*}$
is equal to the first time $t\in(0,T)$ for which $|q^{\sigma}(t)|=q_{0}^{*}$
if such a time exists and $t^{*}$ is equal to $T$ if no such time exists. Note
that $t^{*}$ is a stopping time.

If $t^{*}=T$, then $\tilde{\sigma}$ exercises the same control variable as
$\sigma$ at all times $t\in[0,T]$.

If $t^{*}<T$, then we execute the strategy
$\text{L}q\text{S}(T+\varepsilon_{0}-t^{*})$ (from (5.2)) starting from time
$t^{*}$ and position $|q^{\tilde{\sigma}}(t^{*})|=q_{0}^{*}$. For any
$s\in(0,T)$, we have $(T+\varepsilon_{0}-s)>\varepsilon_{0}$. By taking
$\varepsilon_{0}$ sufficiently small depending on $T$ we ensure that
$(T+\varepsilon_{0})<2T$ and therefore that the strategy
$\text{L}q\text{S}(T+\varepsilon_{0}-s)$ is well-defined for any $s\in(0,T)$.

This concludes the definition of the strategy $\tilde{\sigma}$. We now
estimate its expected cost.

If we never encounter $|q^{\tilde{\sigma}}|=q_{0}^{*}$, i.e., if $t^{*}=T$,
then the strategies $\sigma$ and $\tilde{\sigma}$ exercise the same control
from time 0 to time $T$, hence they incur the same cost.

Suppose instead that we first encounter $|q^{\tilde{\sigma}}|=q_{0}^{*}$ at
some time $t^{*}<T$. Until time $t^{*}$, the strategies $\sigma$,
$\tilde{\sigma}$ exercise the same control and incur the same cost. Let $S$
denote the expected cost of $\sigma$ starting from position $q_{0}^{*}$ and
time $t^{*}$ and continuing until time $T+\varepsilon_{0}$ and let $\tilde{S}$
denote the expected cost of $\tilde{\sigma}$ starting from position
$q_{0}^{*}$ and time $t^{*}$ and continuing until time $T$. Note that

$\displaystyle\tilde{S}$
$\displaystyle=\mathcal{J}(\text{L}q\text{S}(T+\varepsilon_{0}-t^{*}),a;T-t^{*},q_{0})$
$\displaystyle<\mathcal{J}(\text{L}q\text{S}(T+\varepsilon_{0}-t^{*}),a;T+\varepsilon_{0}-t^{*},q_{0}).$

Therefore, by (5.2),

$\tilde{S}<(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T+\varepsilon_{0}-t^{*},q_{0}).$

By Lemma 3.2,

$\mathcal{J}_{0}(a;T+\varepsilon_{0}-t^{*},q_{0})\leq S,$

and therefore $\tilde{S}\leq(1+\varepsilon)\cdot S$.

As a consequence of the above discussion, we have

$\mathcal{J}(\tilde{\sigma},a;T,q_{0})<(1+\varepsilon)\cdot\mathcal{J}(\sigma,a;T+\varepsilon_{0},q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (5.3)

We now derive another estimate on the expected cost of $\tilde{\sigma}$—this
one is much sharper than (5.3) when $|a|\gg A$.

From time $0$ until time $t^{*}$, we execute the strategy $\sigma$ and, by
construction, have $|q^{\tilde{\sigma}}(t)|\leq q_{0}^{*}$ for all
$t\in[0,t^{*}]$. Since $\sigma$ is $A$-bounded, we therefore have

$|u^{\tilde{\sigma}}(t)|<C_{0}A^{m_{0}}(|q(t)|+1)\;\text{for
any}\;t\in[0,t^{*}).$

Therefore, from time $0$ until time $t^{*}$ we incur a cost of at most
$C_{T}A^{2m_{0}}(q_{0}^{*})^{2}$ with probability 1.

In the event that $t^{*}<T$, then from time $t^{*}$ until time $T$ we execute
the strategy $\text{L}q\text{S}(T+\varepsilon_{0}-t^{*})$ (starting from
position $\pm q_{0}^{*}$). Therefore, from time $t^{*}$ until time $T$ we
incur an expected cost that is at most $(1+\varepsilon)$ times the expected
cost of the optimal known-$a$ strategy $\sigma_{\text{opt}}(a)$ for time
horizon $(T+\varepsilon_{0}-t^{*})$ and starting position $q_{0}^{*}$. By
Corollary 3.2, this is at most $C_{T}(q_{0}^{*})^{2}\max\\{a,1\\}$. We
therefore have

$\mathcal{J}(\tilde{\sigma},a;T,q_{0})<C_{T}(q_{0}^{*})^{2}\max\\{A,a\\}^{2m_{0}}\;\text{for
any}\;a\in\mathbb{R}.$

Since $q_{0}^{*}$ is determined by $\varepsilon$, $\varepsilon_{0}$, $T$, and
$q_{0}$ we have

$\mathcal{J}(\tilde{\sigma},a;T,q_{0})<C_{T,q_{0},\varepsilon,\varepsilon_{0}}\max\\{A,a\\}^{2m_{0}}\;\text{for
any}\;a\in\mathbb{R}.$ (5.4)

####  5.1.2 Rescaling strategies

Remark 3.2 implies the following: Given $\lambda>1$ and a strategy $\sigma$
for time horizon $T$ and starting position $q_{0}$, we can define a strategy
$\sigma_{\lambda}$ for time horizon $\lambda^{2}T$ and starting position
$\lambda q_{0}$ that satisfies

$\mathcal{J}(\sigma_{\lambda},a;\lambda^{2}T,\lambda
q_{0})\leq\lambda^{4}\cdot\mathcal{J}(\sigma,\lambda^{2}a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (5.5)

Moreover, since $T<\lambda^{2}T$, $\sigma_{\lambda}$ is also a strategy for
time horizon $T$ and starting position $\lambda q_{0}$, and we have

$\mathcal{J}(\sigma_{\lambda},a;T,\lambda
q_{0})\leq\mathcal{J}(\sigma_{\lambda},a;\lambda^{2}T,\lambda
q_{0})\;\text{for any}\;a\in\mathbb{R}.$ (5.6)

Combining (5.5), (5.6), we deduce that

$\mathcal{J}(\sigma_{\lambda},a;T,\lambda
q_{0})\leq\lambda^{4}\cdot\mathcal{J}(\sigma,\lambda^{2}a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (5.7)

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon_{0}$
and starting position $q_{0}$.

By the results of the previous section (specifically, see (5.3) and (5.4)),
there exists a strategy $\tilde{\sigma}$ for time horizon $T$ and starting
position $q_{0}$ satisfying

$\mathcal{J}(\tilde{\sigma},a;T,q_{0})<(1+\varepsilon)\cdot\mathcal{J}(\sigma,a;T+\varepsilon_{0},q_{0})\;\text{for
any}\;a\in\mathbb{R}$ (5.8)

and

$\mathcal{J}(\tilde{\sigma},a;T,q_{0})<C_{T,q_{0},\varepsilon,\varepsilon_{0}}\cdot\max\\{A,a\\}^{2m_{0}}\;\text{for
any}\;a\in\mathbb{R}.$ (5.9)

By the discussion above, there then exists a strategy
$\tilde{\sigma}_{1+\varepsilon_{0}}$ for time horizon $T$ and starting
position $(1+\varepsilon_{0})q_{0}$ satisfying

$\mathcal{J}(\tilde{\sigma}_{1+\varepsilon_{0}},a;T,(1+\varepsilon_{0})q_{0})<(1+C\varepsilon)\cdot\mathcal{J}(\sigma,(1+\varepsilon_{0})^{2}a;T+\varepsilon_{0},q_{0})\\\
\text{for any}\;a\in\mathbb{R}$ (5.10)

(recall that $\varepsilon_{0}$ is sufficiently small depending on
$\varepsilon$; in particular, to deduce (5.10) we assume that
$\varepsilon_{0}<\varepsilon$) and

$\mathcal{J}(\tilde{\sigma}_{1+\varepsilon_{0}},a;T,(1+\varepsilon_{0})q_{0})<C_{T,q_{0},\varepsilon,\varepsilon_{0}}\cdot\max\\{A,a\\}^{2m_{0}}\;\text{for
any}\;a\in\mathbb{R}.$ (5.11)

From equation (5.10), we deduce that

$\mathcal{J}(\tilde{\sigma}_{1+\varepsilon_{0}},a;T,(1+\varepsilon_{0})q_{0})\\\
<(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}\;\text{for
any}\;a\in\mathbb{R}$ (5.12)

(again taking $\varepsilon_{0}$ sufficiently small depending on
$\varepsilon$).

###  5.2 Definition of the almost optimal strategy

Let $\sigma$ be an $A$-bounded strategy for time horizon $T+\varepsilon_{0}$
and starting position $q_{0}$.

To prove the Main Theorem, we must exhibit a strategy $\sigma_{*}$ for time
horizon $T$ and starting position $q_{0}$ satisfying

$\mathcal{J}(\sigma_{*},a;T,q_{0})<\varepsilon+(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|b-a|<\varepsilon|a|\\}\\\
\text{for any}\;a\in[-A,A]$ (5.13)

and

$\mathcal{J}(\sigma_{*},a;T,q_{0})<\varepsilon+(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;|a|>A.$ (5.14)

The definition of $\sigma_{*}$ requires a bit of setup.

By Theorem 2.3, provided $A$ is sufficiently large depending on
$\varepsilon,T,q_{0}$ there exists a strategy $\text{L}a\text{S}$ for time
horizon $T$ and starting position $(1+\varepsilon_{0})q_{0}$ such that

$\begin{split}\mathcal{J}(\text{L}a\text{S},a;T,(&1+\varepsilon_{0})q_{0})\\\
&<(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,(1+\varepsilon_{0})q_{0})\;\text{for
any}\;a>\frac{1}{100}A,\end{split}$ (5.15)

and

$\mathcal{J}(\text{L}a\text{S},a;T,(1+\varepsilon_{0})q_{0})<C_{T,q_{0}}A^{2}\;\text{for
any}\;a<\frac{1}{100}A.$ (5.16)

By Lemma 3.1, provided $\varepsilon_{0}$ is sufficiently small depending on
$\varepsilon,T,q_{0}$ we have

$|\mathcal{J}_{0}(a;T,(1+\varepsilon_{0})q_{0})-\mathcal{J}_{0}(a;T,q_{0})|<\varepsilon\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (5.17)

Combining (5.15) and (5.17) gives

$\begin{split}\mathcal{J}(\text{L}a\text{S},a;T,(1+\varepsilon_{0}&)q_{0})\\\
&<(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a>\frac{1}{100}A.\end{split}$ (5.18)

By Section 5.1.2 (see equations (5.11), (5.12)), provided $\varepsilon_{0}$ is
sufficiently small depending on $\varepsilon,T,q_{0}$ there exists a strategy
$\bar{\sigma}$ for time horizon $T$ and starting position
$(1+\varepsilon_{0})q_{0}$ such that

$\mathcal{J}(\bar{\sigma},a;T,(1+\varepsilon_{0})q_{0})\\\
<(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}\;\text{for
any}\;a\in\mathbb{R}$ (5.19)

and

$\mathcal{J}(\bar{\sigma},a;T,(1+\varepsilon_{0})q_{0})<C_{T,q_{0},\varepsilon,\varepsilon_{0}}\max\\{A,a\\}^{2m_{0}}\;\text{for
any}\;a\in\mathbb{R}.$ (5.20)

Last, we introduce a constant $q_{\text{rare}}>q_{0}$ depending on $T,q_{0}$
and a strategy BR (“BR” for bounded regret) for time horizon $T$ and starting
position $-q_{\text{rare}}$ satisfying

$\mathcal{J}(\text{BR},a;T,-q_{\text{rare}})<C\cdot\mathcal{J}_{0}(a;T,-q_{\text{rare}})\;\text{for
any}\;a\in\mathbb{R}.$

This is possible due to Theorem 2.2; see, in particular, the discussion of
bounded regret strategies following the statement of Theorem 2.2. We then
observe, by Remark 3.4, that

$\mathcal{J}_{0}(a;T,-q_{\text{rare}})<C_{T,q_{0}}\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$

This implies that the strategy BR satisfies

$\mathcal{J}(\text{BR},a;T,-q_{\text{rare}})<C_{T,q_{0}}\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (5.21)

We fix the strategies $\text{L}a\text{S},\bar{\sigma},\text{BR}$ for the
remainder of Section 5. We are now ready to define the strategy $\sigma_{*}$.

The strategy $\sigma_{*}$ consists of two epochs: the Prologue and the Main
Act. Only the Prologue is guaranteed to occur. In fact, for large negative $a$
we do not expect the Main Act to occur.

For the remainder of Section 5 we write $q,u$ to denote, respectively, the
particle trajectories $q^{\sigma_{*}}$ and the control variables
$u^{\sigma_{*}}$.

Prologue: During the Prologue we set $u=0$. We define a stopping time
$\tau_{1}$ by setting $\tau_{1}$ equal to the first time $t\in(0,T)$ for which
either $q(t)=(1+\varepsilon_{0})q_{0}$ or $q(t)=-q_{\text{rare}}$ if such a
time exists and setting $\tau_{1}$ to be equal to $T$ if no such time exists.
The Prologue lasts from time $0$ until time $\tau_{1}$. If $\tau_{1}=T$ then
at time $\tau_{1}$ the game ends along with the Prologue. If $\tau_{1}<T$,
then at time $\tau_{1}$ we enter the Main Act.

Main Act: Suppose that we enter the Main Act at some time $\tau_{1}\in(0,T)$.
We either have $q(\tau_{1})=(1+\varepsilon_{0})q_{0}$ or
$q(\tau_{1})=-q_{\text{rare}}$; we proceed differently in each case. If
$q(\tau_{1})=(1+\varepsilon_{0})q_{0}$, then we define

$\bar{a}=\frac{\log(1+\varepsilon_{0})}{\tau_{1}}.$

The value of $\bar{a}$ then determines our strategy during the Main Act. Note
that in the event that $\bar{a}$ is defined (i.e., $\tau_{1}<T$ and
$q(\tau_{1})=(1+\varepsilon_{0})q_{0}$) we have $\bar{a}>0$ with probability
1. If $\bar{a}\geq A/10$, then we play strategy $\text{L}a\text{S}$ beginning
at time $\tau_{1}$ and position $q(\tau_{1})=(1+\varepsilon_{0})q_{0}$ until
the game ends at time $T$. If $\bar{a}<A/10$, then we play strategy
$\bar{\sigma}$ beginning at time $\tau_{1}$ and position
$q(\tau_{1})=(1+\varepsilon_{0})q_{0}$ until the game ends at time $T$. This
completes the description of our strategy during the Main Act in the event
that $q(\tau_{1})=(1+\varepsilon_{0})q_{0}$. If
$q(\tau_{1})=-q_{\text{rare}}$, then we play strategy BR beginning at time
$\tau_{1}$ and position $q(\tau_{1})=-q_{\text{rare}}$ until the end of the
game at time $T$.

This concludes the definition of the strategy $\sigma_{*}$.

###  5.3 Proof of Theorem 5.1

Recall that the Prologue ends at time $\tau_{1}$ and that during the Prologue
we set $u=0$. We define a random variable $\textsc{Cost}_{P}$ to be the cost
incurred during the Prologue for a given realization of the noise, i.e.,

$\textsc{Cost}_{P}=\int_{0}^{\tau_{1}}q^{2}(t)\ dt.$

Note that $\textsc{Cost}_{P}$ depends on $a$.

Taking $\varepsilon_{0}$ sufficiently small depending on $T$, we see from
Lemma 4.2 that

$\text{E}[\textsc{Cost}_{P}]<C_{T,q_{0}}\varepsilon_{0}^{1/4}\;\text{for
any}\;a\in\mathbb{R}$ (5.22)

(recall that $q_{\text{rare}}$ is determined by $T,q_{0}$) and that

$\text{Prob}(q(\tau_{1})=-q_{\text{rare}})\leq
C_{q_{0}}\varepsilon_{0}^{1/4}\;\text{for
any}\;a\geq-{\varepsilon_{0}^{-1/2}}.$ (5.23)

Recall that, if it occurs, the Main Act begins at time $\tau_{1}<T$, in which
case we have either $q(\tau_{1})=(1+\varepsilon_{0})q_{0}$ or
$q(\tau_{1})=-q_{\text{rare}}$. In the event that the Main Act occurs and
$q(\tau_{1})=(1+\varepsilon_{0})q_{0}$, we define the random variable

$\bar{a}=\frac{\log(1+\varepsilon_{0})}{\tau_{1}};$

the value of $\bar{a}$ then determines our strategy during the Main Act. We
will consider events of the form “$\bar{a}\in X$” for $X\subset\mathbb{R}$.
This is shorthand for the event
“$\tau_{1}<T,q(\tau_{1})=(1+\varepsilon_{0})q_{0}$, and $\bar{a}\in X$”
(recall that $\bar{a}$ is not defined unless $\tau_{1}<T$ and
$q(\tau_{1})=(1+\varepsilon_{0})q_{0}$).

Let $\alpha>1$. We claim that, provided $\varepsilon_{0}$ is sufficiently
small depending on $T$, we have the following estimates:

$\displaystyle\text{If}\;a>10\alpha\;\text{then}\;\text{Prob}(\bar{a}<\alpha)<C\exp(-c_{\varepsilon_{0}}q_{0}^{2}a).$
(5.24)
$\displaystyle\text{If}\;|a|<\alpha/10,\;\text{then}\;\text{Prob}(\bar{a}>\alpha)<C\exp(-c_{\varepsilon_{0}}q_{0}^{2}\alpha).$
(5.25)
$\displaystyle\text{If}\;a<0,\;\text{then}\;\text{Prob}(\bar{a}>0)<C_{T,q_{0},\varepsilon_{0}}\exp(-c_{\varepsilon_{0}}q_{0}^{2}|a|).$
(5.26)

These estimates follow, respectively, from Lemmas 4.5, 4.4, and 4.3 in Section
4.

We define a random variable $\textsc{Cost}_{M}$ to be the cost incurred during
the Main Act for a given realization of the noise, i.e.,

$\textsc{Cost}_{M}=\int_{\tau_{1}}^{T}((q(t))^{2}+(u(t))^{2})\ dt.$

We use the remainder of this section to prove the estimates

$\text{E}[\textsc{Cost}_{M}]<C\varepsilon+(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|b-a|<\varepsilon|a|\\}\\\
\text{for any}\;|a|\leq A$ (5.27)

and

$\text{E}[\textsc{Cost}_{M}]<C\varepsilon+(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;|a|>A.$ (5.28)

Combining (5.27), (5.28) with the fact that

$\mathcal{J}(\sigma_{*},a;T,q_{0})=\text{E}[\textsc{Cost}_{P}]+\text{E}[\textsc{Cost}_{M}]$

and the estimate (5.22) above, and taking $\varepsilon_{0}$ sufficiently small
depending on $\varepsilon,T,q_{0}$, we deduce (5.13) and (5.14), which in turn
imply the conclusion of the Main Theorem.

Note that

$\text{E}[\textsc{Cost}_{M}]=\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>0}]+\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{q(\tau_{1})=-q_{\text{rare}}}]$
(5.29)

In the event that we enter the Main Act at some time $\tau_{1}\in(0,T)$ for
which $q(\tau_{1})=-q_{\text{rare}}$, we execute the strategy BR starting from
time $\tau_{1}$ and position $-q_{\text{rare}}$. Combining (5.21) and (5.23)
gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{q(\tau_{1})=-q_{\text{rare}}}]<C_{T,q_{0}}\cdot\varepsilon_{0}^{1/4}\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\geq-{\varepsilon_{0}^{-1/2}}.$ (5.30)

Provided $\varepsilon_{0}$ is sufficiently small (depending on $T$), Lemma 3.1
implies that

$\mathcal{J}_{0}(a;T,q_{0})<C_{T,q_{0}}\varepsilon_{0}^{1/2}\;\text{for
any}\;a<-{\varepsilon_{0}^{-1/2}};$

combining this with (5.21) gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{q(\tau_{1})=-q_{\text{rare}}}]<C_{T,q_{0}}\varepsilon_{0}^{1/2}\;\text{for
any}\;a<-{\varepsilon_{0}^{-1/2}}.$ (5.31)

We combine (5.30), (5.31), and take $\varepsilon_{0}$ sufficiently small
depending on $\varepsilon,T,q_{0}$ to get

$\begin{split}\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{q(\tau_{1})=-q_{\text{rare}}}]<\varepsilon+\varepsilon\cdot\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.\end{split}$ (5.32)

Throughout the remainder of this section we will make use of the fact that

$\mathcal{J}_{0}(a;T,q_{0})<\mathcal{J}(\sigma,a;T+\varepsilon_{0},q_{0})\;\text{for
any}\;a\in\mathbb{R};$ (5.33)

this is a consequence of Lemma 3.2. We note that (5.32) and (5.33) imply that

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{q(\tau_{1})=-q_{\text{rare}}}]\\\
<\varepsilon+\varepsilon\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|b-a|<\varepsilon|a|\\}\;\text{for
any}\;a\in\mathbb{R}.$ (5.34)

It remains to control the expected value of $\textsc{Cost}_{M}$ when
$\bar{a}>0$. We will consider 4 cases.

Case I: $a$ is large, positive

Suppose that $a>A$. In the event that $\bar{a}\geq A/10$, we execute the
strategy $\text{L}a\text{S}$ during the Main Act. Therefore, by (5.18), we
have

$\begin{split}\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}\geq
A/10}]&<\mathcal{J}(\text{L}a\text{S},a;T,(1+\varepsilon_{0})q_{0})\\\
&<(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0}).\end{split}$ (5.35)

In the event that $0<\bar{a}<A/10$, we execute strategy $\bar{\sigma}$ during
the Main Act. Therefore, by (5.20) and (5.24), we have

$\begin{split}\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{0<\bar{a}<A/10}]&<\mathcal{J}(\bar{\sigma},a;T,(1+\varepsilon_{0})q_{0})\cdot\text{Prob}(\bar{a}<A/10)\\\
&<C_{T,q_{0},\varepsilon,\varepsilon_{0}}a^{2m_{0}}\exp(-c_{\varepsilon_{0}}q_{0}^{2}a).\end{split}$
(5.36)

Combining (5.35) and (5.36) and taking $A$ sufficiently large depending on
$T,q_{0},\varepsilon,\varepsilon_{0}$ gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>0}]<(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})+\varepsilon\;\text{for
any}\;a>A.$ (5.37)

Case II: $a$ is positive, medium-sized

Suppose that $\frac{1}{100}A<a<A$.

If the event $\bar{a}\geq A/10$ occurs, then during the Main Act we execute
the strategy $\text{L}a\text{S}$. By (5.18), we then have

$\begin{split}\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>A/10}]&<\mathcal{J}(\text{L}a\text{S},a;T,(1+\varepsilon_{0})q_{0})\cdot\text{Prob}(\bar{a}\geq
A/10)\\\
&<(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})\cdot\text{Prob}(\bar{a}\geq
A/10).\end{split}$ (5.38)

In the event that $0<\bar{a}<A/10$, we execute the strategy $\bar{\sigma}$
during the Main Act. By (5.19), we then have

$\begin{split}\text{E}[\textsc{Cost}_{M}\cdot&\mathbbm{1}_{0<\bar{a}<A/10}]\\\
&<\mathcal{J}(\bar{\sigma},a;T,(1+\varepsilon_{0})q_{0})\cdot\text{Prob}(\bar{a}<A/10)\\\
&<(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}\\\
&\qquad\cdot\text{Prob}(\bar{a}<A/10).\end{split}$ (5.39)

Combining (5.38), (5.39), and (5.33) we get

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>0}]<(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}\\\
\text{for any}\;\frac{1}{100}A<a<A.$ (5.40)

Case III: $a$ is bounded

Suppose that $|a|<\frac{1}{100}A$.

In the event that $0<\bar{a}<A/10$, we execute the strategy $\bar{\sigma}$
during the Main Act. By (5.19), we have

$\begin{split}\text{E}[\textsc{Cost}_{M}\cdot&\mathbbm{1}_{0<\bar{a}<A/10}]\\\
&<\mathcal{J}(\bar{\sigma},a;T,(1+\varepsilon_{0})q_{0})\\\
&<(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}.\end{split}$
(5.41)

In the event that $\bar{a}\geq A/10$, we execute the strategy
$\text{L}a\text{S}$ during the Main Act. By (5.16) and (5.25), we therefore
have

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>A/10}]<C_{T,q_{0}}A^{2}\exp(-c_{\varepsilon_{0}}q_{0}^{2}A).$
(5.42)

Combining (5.41) and (5.42), and taking $A$ sufficiently large depending on
$T,q_{0},\varepsilon$, $\varepsilon_{0}$ gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>0}]<\varepsilon+(1+C\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon_{0},q_{0}):|a-b|<\varepsilon|a|\\}\\\
\text{for any}\;|a|<\frac{A}{100}.$ (5.43)

Case IV: $a$ is large, negative

Suppose that $a<-\frac{1}{100}A$.

In the event that $\bar{a}>0$ we execute either the strategy
$\text{L}a\text{S}$ or the strategy $\bar{\sigma}$ during the Main Act.
Combining (5.16), (5.20), and (5.26) gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>0}]<C_{T,q_{0},\varepsilon,\varepsilon_{0}}|a|^{2m_{0}}\exp(-c_{\varepsilon_{0}}q_{0}^{2}|a|).$

Taking $A$ sufficiently large depending on
$T,q_{0},\varepsilon,\varepsilon_{0}$ then gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\bar{a}>0}]<\varepsilon\;\text{for
any}\;a<-\frac{A}{100}.$ (5.44)

Combining (5.37), (5.40), (5.43), and (5.44) with (5.29), (5.32), and (5.34)
proves (5.27) and (5.28).

###  5.4 Proof of Corollary 2.1

Let $\varepsilon>0$ be given and let $A$ be sufficiently large so that the
conclusion of Theorem 1.2 holds. Let $\sigma$ be an $A$-bounded strategy for
time horizon $T+\varepsilon$ and starting position $\varepsilon$.

Then the strategy $\sigma_{*}$ (as in Theorem 1.2) for time horizon $T$ and
starting position $\varepsilon$ satisfies

$\mathcal{J}(\sigma_{*},a;T,\varepsilon)<\varepsilon+(1+\varepsilon)\cdot\sup\\{\mathcal{J}(\sigma,b;T+\varepsilon,\varepsilon):|a-b|<\varepsilon|a|\\}\\\
\text{for any}\;a\in[-A,A]$ (5.45)

and

$\mathcal{J}(\sigma_{*},a;T,\varepsilon)<\varepsilon+(1+\varepsilon)\cdot\mathcal{J}_{0}(a;T,\varepsilon)\;\text{for
any}\;|a|>A.$ (5.46)

Combining (5.46) with Lemma 3.1 (specifically, Parts 1 and 2 of Lemma 3.1), we
deduce that, provided $A$ is sufficiently large depending on $\varepsilon$ and
$T$, we have

$\mathcal{J}(\sigma_{*},a;T,\varepsilon)<\varepsilon+(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,0)\;\text{for
any}\;|a|>A.$ (5.47)

By Remark 3.1, $\sigma_{*}$ gives rise to a strategy for time horizon $T$ and
starting position $-\varepsilon$; we also denote this strategy by $\sigma_{*}$
and recall that

$\mathcal{J}(\sigma_{*},a;T,\varepsilon)=\mathcal{J}(\sigma_{*},a;T,-\varepsilon)$

We now construct the strategy $\hat{\sigma}_{*}$ for time horizon $T$ and
starting position $0$. We set $u^{\hat{\sigma}_{*}}(t)=0$ from time 0 until
time $\hat{t}$, where $\hat{t}$ is equal to the first time $t\in(0,T)$ for
which $|q^{\hat{\sigma}_{*}}(t)|=\varepsilon$ if such a time exists and
$\hat{t}$ is equal to $T$ if no such time exists.

If $\hat{t}=T$, then we set $u^{\hat{\sigma}_{*}}\equiv 0$ until the game ends
at time $T$. In this case, we incur a cost of at most $T\varepsilon$ with
probability 1.

If $\hat{t}<T$, then we execute the strategy $\sigma_{*}$ starting from time
$\hat{t}$ and position $|q(\hat{t})|=\varepsilon$ until the game ends at time
$T$. In this case, our expected cost from time 0 until time $T$ is at most
$T\varepsilon+\mathcal{J}(\sigma_{*},a;T,\varepsilon)$.

We have defined the strategy $\hat{\sigma}^{*}$ and shown that

$\mathcal{J}(\hat{\sigma}^{*},a;T,0)<T\varepsilon+\mathcal{J}(\sigma_{*},a;T,\varepsilon).$

Combining this with (5.45) and (5.47) implies the conclusion of the corollary.

##  6 The Large $q$ Strategy

In this section we prove Theorem 2.2.

Fix a time horizon $T>0$. Let $\varepsilon>0$ be given. Note that it suffices
to prove Theorem 2.2 under the assumption that $\varepsilon$ is sufficiently
small depending on $T$.

We let $t_{\text{max}}\in(0,T)$ denote a real number that we will choose in
Section 6.1 depending on $\varepsilon$.

Let $A_{1}\geq 1$ be a sufficiently large real number depending on
$\varepsilon,T$.

We let $q_{\text{big}}\geq 1$ be a sufficiently large real number depending on
$\varepsilon,A_{1},T$. Note that since $A_{1}$ is determined by $\varepsilon$
and $T$, $q_{\text{big}}$ depends only on $\varepsilon$ and $T$. We fix a
starting position $q_{0}\geq q_{\text{big}}$.

For $\alpha\in\mathbb{R}$, recall that $\sigma_{\text{opt}}(\alpha)$ denotes
the known-$a$ strategy for time horizon $T$ (recall that this strategy is
independent of the starting position; see Section 2). The corresponding
control variable is

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

for any $a\in\mathbb{R}$, $t\in[0,T]$, where

$\kappa(T-t,\alpha)=\frac{\tanh((T-t)\sqrt{\alpha^{2}+1})}{\sqrt{\alpha^{2}+1}-\alpha\tanh((T-t)\sqrt{\alpha^{2}+1})}.$

We will occasionally refer to the known-$a$ strategy for an arbitrary time
horizon $T^{\prime}\in(0,T]$; we denote this strategy by
$\sigma_{\text{opt}}(\alpha;T^{\prime})$ for $\alpha\in\mathbb{R}$. We note
that $\kappa(T^{\prime}-t,\alpha)$ is the gain function corresponding to
$\sigma_{\text{opt}}(\alpha;T^{\prime})$ and we remark that

$0\leq\kappa(T^{\prime}-t,\alpha)\leq C\cdot\max\\{\alpha,1\\}\;\text{for
all}\;t\in[0,T^{\prime}],\alpha\in\mathbb{R}$ (6.1)

with the constant $C$ independent of $T^{\prime}$.

We are now ready to define the strategy $\text{L}q\text{S}$. For the remainder
of Section 6 we write $q,u$ to denote, respectively, the particle trajectories
$q^{\text{L}q\text{S}}$ and the control variables $u^{\text{L}q\text{S}}$.

We note that the strategy $\text{L}q\text{S}$ consists of two epochs: the
Prologue and the Main Act. Both epochs are guaranteed to occur.

Prologue: We define a stopping time $\tau_{M}$ by setting $\tau_{M}$ equal to
the first time $t\in(0,t_{\text{max}})$ for which
$q(t)\notin((1-\varepsilon)q_{0},(1+\varepsilon)q_{0})$ if such a time exists,
and $\tau_{M}=t_{\text{max}}$ if no such time exists.

The Prologue lasts from time $0$ to time $\tau_{M}$. During the Prologue we
exercise no control, i.e. we set $u\equiv 0$. At time $\tau_{M}$, we enter the
Main Act.

Main Act: The Main Act lasts from time $\tau_{M}$ until the end of the game at
time $T$. Our strategy during the Main Act depends on what happens during the
Prologue. We define some events that capture the possible outcomes of the
Prologue:

$\displaystyle\textsc{Pro}_{+}=\\{q(\tau_{M})=(1+\varepsilon)q_{0}\\},$
$\displaystyle\textsc{Pro}_{-}=\\{q(\tau_{M})=(1-\varepsilon)q_{0}\\},$
$\displaystyle\textsc{Pro}_{\text{max}}=\\{\tau_{M}=t_{\text{max}}\\}.$

The events $\textsc{Pro}_{+}$, $\textsc{Pro}_{-}$, $\textsc{Pro}_{\text{max}}$
partition our probability space.

If the event $\textsc{Pro}_{+}$ occurs with $\tau_{M}=s$ for some
$s\in(0,t_{\text{max}})$, then we define

$\bar{a}=\frac{\log(1+\varepsilon)}{s}.$

If the event $\textsc{Pro}_{-}$ occurs with $\tau_{M}=s$ for some
$s\in(0,t_{\text{max}})$, then we define

$\bar{a}=\frac{\log(1-\varepsilon)}{s}.$

If $\textsc{Pro}_{+}$ (respectively $\textsc{Pro}_{-}$) occurs, then we have
$\bar{a}>0$ (resp. $\bar{a}<0$) with probability 1.

If the event $\textsc{Pro}_{\text{max}}$ occurs, then we leave $\bar{a}$
undefined.

For $X\subset(0,\infty)$ we will sometimes write “$\bar{a}\in X$” as shorthand
for the event “$\bar{a}\in X$ and $\textsc{Pro}_{+}$”. Similarly, for
$Y\subset(-\infty,0)$ we write “$\bar{a}\in Y$” for the event “$\bar{a}\in Y$
and $\textsc{Pro}_{-}$”.

We now specify our strategy during the Main Act.

Case I: (We believe $a$ is small)

If the event $\textsc{Pro}_{\text{max}}$ occurs, then we set

$u(t)=-\kappa(T-t,0)\cdot q(t)$

during the Main Act. In this case, the expected cost incurred during the Main
Act is equal to the expected cost of the known-$a$ strategy
$\sigma_{\text{opt}}(0;T-t_{\text{max}})$ for time horizon
$(T-t_{\text{max}})$ and starting position $q(t_{\text{max}})$.

Case II: (We believe $a$ is large, positive)

If the event $\textsc{Pro}_{+}$ occurs and $\bar{a}\geq A_{1}$, then we set

$u(t)=-2\bar{a}q(t)$

during the Main Act. Note that this is the control variable corresponding to
the constant gain strategy $\text{CG}(2\bar{a})$ (see Section 3) with starting
position $(1+\varepsilon)q_{0}$.

Case III: (We believe that $a$ is bounded, positive)

If the event $\textsc{Pro}_{+}$ occurs and $0<\bar{a}<A_{1}$ and $\tau_{M}=s$
for some $s\in(0,t_{\text{max}})$, then we set

$u(t)=-\kappa(T-t,\bar{a})\cdot q(t)$

during the Main Act. In this case, the expected cost incurred during the Main
Act is equal to the expected cost of the optimal known-$a$ strategy
$\sigma_{\text{opt}}(\bar{a};T-s)$ for time horizon $T-s$ and starting
position $(1+\varepsilon)q_{0}$.

Case IV: (We believe that $a$ is large, negative)

If the event $\textsc{Pro}_{-}$ occurs and $\bar{a}\leq-A_{1}$, then we set

$u(t)=0$

during the Main Act. Note that this is the control variable corresponding to
the constant gain strategy $\text{CG}(0)$ with starting position
$(1-\varepsilon)q_{0}$.

Case V: (We believe that $a$ is bounded, negative)

If the event $\textsc{Pro}_{-}$ occurs and $-A_{1}<\bar{a}<0$ and $\tau_{M}=s$
for some $s\in(0,t_{\text{max}})$, then we set

$u(t)=-\kappa(T-s,\bar{a})\cdot q(t)$

during the Main Act. In this case, the expected cost incurred during the Main
Act is equal to the expected cost of the optimal known-$a$ strategy
$\sigma_{\text{opt}}(\bar{a};T-s)$ for time horizon $T-s$ and starting
position $(1-\varepsilon)q_{0}$.

This concludes the definition of the strategy $\text{L}q\text{S}$.

###  6.1 The parameter $t_{\text{max}}$

We will now choose the parameter $t_{\text{max}}$. We set

$t_{\text{max}}=c_{0}\varepsilon^{1/2},$

where $c_{0}$ is a sufficiently small absolute constant. We define

$a_{\text{tiny}}=\varepsilon^{1/2},\qquad a_{\text{small}}=\varepsilon^{1/4}.$

Provided $\varepsilon$ is sufficiently small depending on $T$, we apply Lemma
4.1 to deduce the following:

$\displaystyle\text{Prob}(\textsc{Pro}_{+})\leq
C\exp(-c_{\varepsilon}q_{0}^{2}(|a|+1))\;\text{for any}\;a\leq
a_{\text{tiny}},$ (6.2) $\displaystyle\text{Prob}(\textsc{Pro}_{-})\leq
C\exp(-c_{\varepsilon}q_{0}^{2}(|a|+1))\;\text{for any}\;a\geq-
a_{\text{tiny}},$ (6.3)
$\displaystyle\text{Prob}(\textsc{Pro}_{\text{max}})\leq
C\exp(-c_{\varepsilon}q_{0}^{2}|a|)\;\text{for any}\;|a|\geq
a_{\text{small}}.$ (6.4)

###  6.2 Bounding the expected cost

Define random variables

$\displaystyle\textsc{Cost}_{P}=\int_{0}^{\tau_{M}}q^{2}(t)\ dt,$
$\displaystyle\textsc{Cost}_{M}=\int_{\tau_{M}}^{T}\left((q(t))^{2}+(u(t))^{2})\right)dt.$

$\textsc{Cost}_{P}$ and $\textsc{Cost}_{M}$ are, respectively, the costs
incurred during the Prologue and Main Act for a given realization of the
noise. Note that both random variables depend on $a$.

Provided $q_{\text{big}}$ is sufficiently large depending on $\varepsilon$ and
$T$, Lemma 4.1 implies that

$\text{E}[\textsc{Cost}_{P}]<C\varepsilon^{1/2}\mathcal{J}_{0}(a;T,q_{0})\;\text{for
any}\;a\in\mathbb{R}.$ (6.5)

Our goal in the remainder of this section is to control the expected value of
$\textsc{Cost}_{M}$. Recall that we play a different strategy during the Main
Act depending on which one of 5 events occur during the Prologue. We analyze
each of these cases separately in Sections 6.2.1–6.2.5. In Section 6.2.6 we
prove Theorem 2.2.

####  6.2.1 $\textsc{Cost}_{M}$ when we believe that $a$ is small

Recall that if the event $\textsc{Pro}_{\text{max}}$ occurs, then the Main Act
begins at time $t_{\text{max}}$ and we set

$u(t)=-\kappa(T-t,0)\cdot q(t)$

during the Main Act. In this case our expected cost during the Main Act is
equal to the expected cost of the optimal known-$a$ strategy
$\sigma_{\text{opt}}(0;T-t_{\text{max}})$ for time horizon $T-t_{\text{max}}$
starting from position $q(t_{\text{max}})=\tilde{q}_{0}$ for some
$\tilde{q}_{0}\in((1-\varepsilon)q_{0},(1+\varepsilon)q_{0})$. By Corollary
3.2, we thus have

$\text{E}[\textsc{Cost}_{M}|\textsc{Pro}_{\text{max}}]\leq
C_{T}q_{0}^{2}e^{2|a|T}\;\text{for any}\;a\in\mathbb{R}.$ (6.6)

Combining (6.4) and (6.6) gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\textsc{Pro}_{\text{max}}}]<C_{T}q_{0}^{2}\cdot\exp(2|a|T-c_{\varepsilon}q_{0}^{2}|a|)\;\text{for
any}\;|a|\geq a_{\text{small}}.$

Taking $q_{\text{big}}$ sufficiently large depending on $\varepsilon,T$, we
get

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\textsc{Pro}_{\text{max}}}]<\varepsilon\cdot\min\\{1,1/|a|\\}\;\text{for
any}\;|a|\geq a_{\text{small}}.$ (6.7)

By Lemma 3.1, there exists a constant $\tilde{A}>1$ depending only on $T$ such
that

$\displaystyle\mathcal{J}_{0}(a;T,q_{0})>\frac{c_{T}}{|a|}\;\text{for
any}\;a<-\tilde{A},$ (6.8)
$\displaystyle\mathcal{J}_{0}(a;T,q_{0})>c_{T}\;\text{for any}\;a>\tilde{A}.$
(6.9)

Again by Lemma 3.1,

$\mathcal{J}_{0}(a;T,q_{0})\geq\int_{0}^{T}\kappa(t,a)\ dt>c_{T}\;\text{for
any}\;|a|\leq\tilde{A}.$ (6.10)

Combining (6.7)–(6.10) gives

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\textsc{Pro}_{\text{max}}}]\leq\varepsilon
C_{T}\mathcal{J}_{0}(a;T,q_{0})\;\text{for any}\;|a|\geq a_{\text{small}}.$
(6.11)

By Lemma 3.3, we have

$\mathcal{J}(\sigma_{\text{opt}}(\alpha),a;T,q_{0})=h(\alpha,a)q_{0}^{2}+j(\alpha,a)\;\text{for
any}\;\alpha\in\mathbb{R},a\in\mathbb{R}$

where $h,j:\mathbb{R}^{2}\rightarrow(0,\infty)$ are smooth functions depending
on $T$ but not on $q_{0}$. This implies that

$\text{E}[\textsc{Cost}_{M}|\textsc{Pro}_{\text{max}}]\leq
h(0,a)(1+\varepsilon)^{2}q_{0}^{2}+j(0,a)$

and

$\mathcal{J}_{0}(a;T,q_{0})=h(a,a)q_{0}^{2}+j(a,a).$ (6.12)

Therefore

$\begin{split}\text{E}[\textsc{Cost}_{M}|\textsc{Pro}_{\text{max}}]\leq&\mathcal{J}_{0}(a;T,q_{0})+|j(a,a)-j(0,a)|+h(a,a)C\varepsilon
q_{0}^{2}\\\ &+Cq_{0}^{2}|h(a,a)-h(0,a)|.\end{split}$

Since $h,j$ are smooth functions (depending on $T$), we have

$\text{E}[\textsc{Cost}_{M}|\textsc{Pro}_{\text{max}}]\\\
\leq\mathcal{J}_{0}(a;T,q_{0})+C_{T}q_{0}^{2}|a|+h(a,a)C\varepsilon
q_{0}^{2}\;\text{for any}\;|a|\leq a_{\text{small}}.$ (6.13)

We combine this with (6.12) to get

$\text{E}[\textsc{Cost}_{M}|\textsc{Pro}_{\text{max}}]<(1+C\varepsilon)\cdot\mathcal{J}_{0}(a;T,q_{0})+C_{T}q_{0}^{2}\varepsilon^{1/4}\;\text{for
any}\;|a|\leq a_{\text{small}}.$

Equation (6.12) also implies that

$\mathcal{J}_{0}(a;T,q_{0})\geq c_{T}q_{0}^{2}\;\text{for any}\;|a|\leq
a_{\text{small}}.$

We have therefore shown that

$\text{E}[\textsc{Cost}_{M}\cdot\mathbbm{1}_{\textsc{Pro}_{\text{max}}}]\\\
\leq\mathcal{J}_{0}(a;T,q_{0})\cdot(1+C_{T}\varepsilon^{1/4})\cdot\text{Prob}(\textsc{Pro}_{\text{max}})\;\text{for
any}\;|a|\leq a_{\text{small}}.$ (6.14)

####  6.2.2 $\textsc{Cost}_{M}$ when we believe that $a$ is large, positive

Let $\alpha\geq 0$ be a positive real number. Recall that $\text{CG}(\alpha)$
denotes the simple feedback strategy with constant gain function $\alpha$ (see
Section 3).

Suppose that the event $\textsc{Pro}_{+}$ occurs and that we have
$\bar{a}=\tilde{a}$ for some $\tilde{a}\geq A_{1}$. In this case we set
$u=-2\tilde{a}q$ during the Main Act. We therefore have

$\text{E}[\textsc{Cost}_{M}|\bar{a}=\tilde{a}]\leq\mathcal{J}(\text{CG}(2\tilde{a}),a;T,(1+\varepsilon)q_{0})\;\text{for
any}\;\tilde{a}\geq A_{1},a\in\mathbb{R}.$ (6.15)

Define

$A^{*}=\max\\{|a|,A_{1}\\}.$

Combining (6.15) with Corollary 3.1 implies the following estimates:

$\text{E}[\textsc{Cost}_{M}|10^{n}A^{*}<\bar{a}<10^{n+1}A^{*}]\\\
<C_{T}10^{2n}(A^{*})^{2}q_{0}^{2}\;\text{for any}\;a\in\mathbb{R},n\geq 0,$
(6.16)

and

$\text{E}[\textsc{Cost}_{M}|A_{1}\leq\bar{a}<10|a|]<C_{T}|a|^{2}q_{0}^{2}\;\text{for
any}\;a<-A_{1}/10.$ (6.17)

Now let $0<\delta\ll 1$ be a sufficiently small parameter depending on
$\varepsilon$. Using Corollary 3.1 again, we get

$\text{E}[\textsc{Cost}_{M}|(A_{1}\leq\bar{a}<10a)\;\text{AND}\;(|a-\bar{a}|>\delta
a)]\\\ <C_{T}a^{2}e^{2aT}q_{0}^{2}\;\text{for any}\;a\geq A_{1}/10,$ (6.18)